title: Solver CBC_MIXED_INTEGER_PROGRAMMING is not reaching the optimal result
body: <h1>Problem</h1>
  
  <p>I'm implementing a generalized assignment problem using LINGO (in which I have experience to model mathematical problems) and Or-tools, but results were different.</p>
  
  <h1>Brief explanation of my assignment problem</h1>
  
  <p>I have a set of houses (called 'object' in the model) that need to be build. Each house needs a set of resources. To supply these resources, there are 3 suppliers. The resource cost varies by supplier.</p>
  
  <p>The model should assign those suppliers to the houses in order to minimize the total cost of assignments.</p>
  
  <h1>Model</h1>
  
  <p><strong>Parameters</strong></p>
  
  <ul>
  <li><strong><em>resource_cost_per_supplier[i,j]</em></strong>:  cost of resource <em>i</em> of supplier <em>j</em>.</li>
  <li><strong><em>resource_cost_factor_per_object[i,j]</em></strong>: matrix that signals the resources demanded by the objects (cost factor > 0). In addition, it contains the cost factor of resource <em>i</em> demanded by object <em>j</em>. This factor is calculated based on the duration of use of the resource during the construction of the object and also in others contractual factors.</li>
  <li><strong><em>supplier_budget_limit[j]</em></strong>: supplier budget limit of supplier <em>j</em>. Each supplier has a budget limit that should not be exceded (it's in the contract).</li>
  <li><strong><em>supplier_budget_tolerance_margin_limit[j]</em></strong>: supplier budget tolerance margin limit of supplier <em>j</em>. To the model works, I had to create this tolerance margin, that is applied in the supplier budget limit to create an acceptable range of supplier cost.</li>
  <li><strong><em>object_demand_attended_per_supplier[i,j]</em></strong>: binary matrix that signals if the supplier <em>i</em> has all the resources required by object <em>j</em>.</li>
  </ul>
  
  <p><strong>Variables</strong></p>
  
  <ul>
  <li><strong><em>x[i,j]</em></strong>: binary variable that indicate if the supplier <em>i</em> will be (1) or not (0) assigned to the object <em>j</em>.</li>
  <li><strong><em>supplier_cost[j]</em></strong>: variable that represents the cost of supplier <em>j</em> in the market share. Its value is given by:
  <img src="https://i.stack.imgur.com/bLLco.png" alt="img1"></li>
  <li><strong><em>total_cost</em></strong>: variable that represents the total cost of market share. Its value is given by:
  <img src="https://i.stack.imgur.com/obHRH.png" alt="img2"></li>
  </ul>
  
  <p><strong>Objective function</strong></p>
  
  <p><em>min Z = total_cost</em></p>
  
  <p><strong>Constraints</strong></p>
  
  <p><strong>1</strong> - Ensure that each object <strong><em>j</em></strong> will have only one supplier <strong><em>i</em></strong>.</p>
  
  <p><img src="https://i.stack.imgur.com/6wxb0.png" alt="img3"></p>
  
  <p><strong>2</strong> - For each supplier <strong><em>i</em></strong>, the sum of the cost of all your assignments must be greater than or equal to your budget limit minus the tolerance margin.</p>
  
  <p><img src="https://i.stack.imgur.com/lq2Oq.png" alt="img4"></p>
  
  <p><strong>3</strong> - For each supplier <em>j</em>, the sum of the cost of all your assignments must be less than or equal to your budget limit plus the tolerance margin.</p>
  
  <p><img src="https://i.stack.imgur.com/MPJKS.png" alt="img5"></p>
  
  <p><strong>4</strong> - Ensure that a supplier <strong><em>i</em></strong> will not assigned to an object <strong><em>j</em></strong> if the supplier <strong><em>i</em></strong> cannot provide all the resources of object <strong><em>j</em></strong>.</p>
  
  <p><img src="https://i.stack.imgur.com/g2LeY.png" alt="img6"></p>
  
  <p><strong>5</strong> - Ensure that variable <em>x</em> is binary for every supplier <em>i</em> and object <em>j</em>.</p>
  
  <p><img src="https://i.stack.imgur.com/DCyUq.png" alt="img7"></p>
  
  <h1>Code</h1>
  
  <p><strong>Or-tools (Python)</strong></p>
  
  <pre><code>from __future__ import print_function
  from ortools.linear_solver import pywraplp
  import pandas as pd
  import numpy
  
  ###### [START] parameters ######
  num_objects = 252 #Number of objects
  num_resources = 35 #Number of resources (not every object will use all resources. It depends of the type of the object and other things) 
  num_suppliers = 3 #Number of suppliers
  resource_cost_per_supplier = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/resource_cost_per_supplier.csv', index_col = 0).to_numpy()
  resource_cost_factor_per_object = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/resource_cost_factor_per_object.csv', index_col = 0).to_numpy()
  object_demand_attended_per_supplier = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/object_demand_attended_per_supplier.csv', index_col = 0).to_numpy()
  supplier_budget_limit = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/supplier_budget_limit.csv', index_col = 0)['budget_limit'].values
  supplier_budget_tolerance_margin_limit = pd.read_csv('https://raw.githubusercontent.com/hrassis/divisao-mercado/master/input_prototype/supplier_budget_tolerance_margin_limit.csv', index_col = 0)['tolerance_margin'].values
  ###### [END] parameters ######
  
  ###### [START] variables ######
  #Assignment variable
  x = {}
  
  supplier_cost = []
  
  #Total cost of market share
  total_cost = 0
  
  ###### [END] variables ######
  
  def main():
    #Declare the solver
    solver = pywraplp.Solver('GeneralizedAssignmentProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
  
    #Assignment variable
    #x = {}
  
    #Ensure that the assignment variable is binary
    for i in range(num_suppliers):
        for j in range(num_objects):
          x[i, j] = solver.BoolVar('x[%i,%i]' % (i,j))
  
    #Assigning an expression to each supplier_cost element
    for j in range(num_suppliers):
      supplier_cost.append(solver.Sum(solver.Sum(resource_cost_per_supplier[i,j] * resource_cost_factor_per_object[i,k] * x[j,k] for k in range(num_objects)) for i in range(num_resources)))
  
    #Total cost of market share
    total_cost = solver.Sum(supplier_cost[j] for j in range(num_suppliers))
  
    #Objective function
    solver.Minimize(total_cost)
  
    ###### [START] constraints ######
    # 1 - Ensure that each object will have only one supplier
    for j in range(num_objects):
      solver.Add(solver.Sum([x[i,j] for i in range(num_suppliers)]) == 1)
  
    # 2 - For each supplier j, the sum of the cost of all your allocations must be greater than or equal to your budget limit minus the tolerance margin
    for j in range(num_suppliers):
      solver.Add(supplier_cost[j] &gt;= total_cost * (supplier_budget_limit[j] - supplier_budget_tolerance_margin_limit[j]))
  
    # 3 - For each supplier j, the sum of the cost of all your allocations must be less than or equal to your budget limit plus the tolerance margin
    for j in range(num_suppliers):
      solver.Add(supplier_cost[j] &lt;= total_cost * (supplier_budget_limit[j] + supplier_budget_tolerance_margin_limit[j]))
  
    # 4 - Ensure that a supplier i will not assigned to an object j if the supplier i can not supply all resources demanded by object j
    for i in range(num_suppliers):
        for j in range(num_objects):
          solver.Add(x[i,j] - object_demand_attended_per_supplier[i,j] &lt;= 0)
  
    ###### [END] constraints ######
  
    solution = solver.Solve()
  
    #Print the result
    if solution == pywraplp.Solver.OPTIMAL:
      print('------- Solution -------')
      print('Total cost =', round(total_cost.solution_value(), 2))
      for i in range(num_suppliers):
        print('-----')
        print('Supplier', i)
        print('-&gt; cost:', round(supplier_cost[i].solution_value(), 2))
        print('-&gt; cost percentage:', format(supplier_cost[i].solution_value()/total_cost.solution_value(),'.2%'))
        print('-&gt; supplier budget limit:', format(supplier_budget_limit[i], '.0%'))
        print('-&gt; supplier budget tolerance margin limit:', format(supplier_budget_tolerance_margin_limit[i], '.0%'))
        print('-&gt; acceptable range: {0} &lt;= cost percentage &lt;= {1}'.format(format(supplier_budget_limit[i] - supplier_budget_tolerance_margin_limit[i], '.0%'), format(supplier_budget_limit[i] + supplier_budget_tolerance_margin_limit[i], '.0%'))) 
        # print('-&gt; objects: {0}'.format(i))
    else:
      print('The problem does not have an optimal solution.')
  
    #Generate a result to consult
    assignment_result = pd.DataFrame(columns=['object','supplier','cost','assigned'])
  
    for i in range(num_suppliers):
      for j in range(num_objects):
        assignment_result = assignment_result.append({'object': j, 'supplier': i, 'cost': get_object_cost(j, i), 'assigned': x[i, j].solution_value()}, ignore_index=True)
    assignment_result.to_excel('assignment_result.xlsx')
  
  
  def get_object_cost(object_index, supplier_index):
  
    object_cost = 0.0
  
    for i in range(num_resources):
      object_cost = object_cost + resource_cost_factor_per_object[i,object_index] * resource_cost_per_supplier[i,supplier_index]
  
    return object_cost
  
  #Run main
  main()
  </code></pre>
  
  <p><strong>LINGO</strong></p>
  
  <pre><code>model:
      title: LINGO;
  
      data:
          !Number of objects;
          num_objects = @OLE('LINGO_input.xlsx',num_objects);
  
          !Number of resources (not every object will use all resources. It depends of the type of the object and other things);
          num_resources = @OLE('LINGO_input.xlsx',num_resources);
  
          !Number of suppliers;
          num_suppliers = @OLE('LINGO_input.xlsx',num_suppliers);
      enddata
  
      sets:
          suppliers/1..num_suppliers/:supplier_budget_limit,supplier_tolerance_margin_limit,supplier_cost;
          resources/1..num_resources/:;
          objects/1..num_objects/:;
  
          resources_suppliers(resources,suppliers):resource_cost_per_supplier;
          resources_objects(resources,objects):resource_cost_factor_per_object;
          suppliers_objects(suppliers,objects):x,object_demand_attended_supplier;
      endsets
  
      data:
          resource_cost_per_supplier = @OLE('LINGO_input.xlsx',resource_cost_per_supplier[cost]);
          resource_cost_factor_per_object = @OLE('LINGO_input.xlsx',resource_cost_factor_per_object[cost_factor]);
          supplier_budget_limit = @OLE('LINGO_input.xlsx',supplier_budget_limit[budget_limit_percentage]);
          supplier_tolerance_margin_limit = @OLE('LINGO_input.xlsx',supplier_budget_tolerance_margin_limit[budget_tolerance_percentage]);
          object_demand_attended_supplier = @OLE('LINGO_input.xlsx',object_demand_attended_per_supplier[supply_all_resources]);
      enddata
  
      !The array 'supplier_cost' was created to store the total cost of each supplier;
      @FOR(suppliers(j):supplier_cost(j)= @SUM(resources(i):@SUM(objects(k):resource_cost_per_supplier(i,j)*resource_cost_factor_per_object(i,k)*x(j,k))));
  
      !Total cost of market share;
      total_cost = @SUM(suppliers(i):supplier_cost(i));
  
      !Objective function;
      min = total_cost;
  
      !Ensure that each object will have only one supplier;
      @FOR(objects(j):@SUM(suppliers(i):x(i,j))=1);
  
      !For each supplier j, the sum of the cost of all your assignments must be greater than or equal to your budget limit minus the tolerance margin;
      @FOR(suppliers(j):supplier_cost(j) &gt;= total_cost*(supplier_budget_limit(j)-supplier_tolerance_margin_limit(j)));
  
      !For each supplier j, the sum of the cost of all your assignments must be less than or equal to your budget limit plus the tolerance margin;
      @FOR(suppliers(j):supplier_cost(j) &lt;= total_cost*(supplier_budget_limit(j)+supplier_tolerance_margin_limit(j)));
  
      !Ensure that a supplier j will not assigned to an object k if the supplier j can not supply all resources demanded by object k;
      @FOR(suppliers(j):@FOR(objects(k):x(j,k)-object_demand_attended_supplier(j,k)&lt;=0));
  
      !Ensure that the assignment variable is binary;
      @FOR(suppliers(i):@FOR(objects(j):@BIN(x(i,j))));
  
      data:
          @OLE('LINGO_input.xlsx',output[assigned])=x;        
          @OLE('LINGO_input.xlsx',objective_function_value)=total_cost;       
          @OLE('LINGO_input.xlsx',supplier_cost)=supplier_cost;       
      enddata
  </code></pre>
  
  <h1>Results</h1>
  
  <p>The picture below shows the comparative result between Or-Tools and LINGO. I emphasize that the data used by the two implementations were exactly the same and I checked all the data several times.</p>
  
  <p><img src="https://i.stack.imgur.com/HKuKM.png" alt="img8"></p>
  
  <p>Note that there is a difference of 1.876,20 between the two implementations. LINGO, that uses a Branch and Bound algorithm, found a better solution than Or-Tools. The difference is caused by the assignments inconsistencies shown below.</p>
  
  <p><img src="https://i.stack.imgur.com/LCKUM.png" alt="img9">  </p>
  
  <p>Regarding the processing time of the algorithms, LINGO took around 14 min and Or-Tools less than 1 min.</p>
  
  <p>All the data used in the two implementations are in this repository: <a href="https://github.com/hrassis/divisao-mercado" rel="nofollow noreferrer">https://github.com/hrassis/divisao-mercado</a>. Data used by LINGO is in folder input_lingo and used by Or-Tools is in the folder input_prototype. In addition I uploaded the validation report.</p>