Solution to MIP not optimal?

[ronenm...@gmail.com]

I solved several instances on an MIP problem with Gurobi using API calls from JAVA. I compared the results with those I got using lp_solve (a free solver). For one instance lp_solve found a better solution than Gurobi. I checked feasibility and it seemed to be ok. 

Log of Gurobi below. The better solution I got with lp_solve is: 24292965

I think this is related to tolerance.

Is there a way to make the tolerance smaller?

----

Optimize a model with 199 rows, 588 columns and 1176 nonzeros
Variable types: 0 continuous, 588 integer (588 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+08]
  Objective range  [3e+01, 3e+06]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 7e+08]
Warning: Model contains large matrix coefficients
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Found heuristic solution: objective 1.67615e+07
Presolve removed 26 rows and 221 columns
Presolve time: 0.00s
Presolved: 173 rows, 367 columns, 709 nonzeros
Found heuristic solution: objective 2.280533e+07
Variable types: 0 continuous, 367 integer (366 binary)

Root relaxation: objective 2.429759e+07, 129 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 2.4298e+07    0    3 2.2805e+07 2.4298e+07  6.54%     -    0s
H    0     0                    2.418861e+07 2.4298e+07  0.45%     -    0s
H    0     0                    2.427135e+07 2.4298e+07  0.11%     -    0s
     0     0 2.4295e+07    0    5 2.4271e+07 2.4295e+07  0.10%     -    0s
H    0     0                    2.428789e+07 2.4295e+07  0.03%     -    0s
     0     0 2.4294e+07    0    7 2.4288e+07 2.4294e+07  0.03%     -    0s
     0     0 2.4294e+07    0    2 2.4288e+07 2.4294e+07  0.03%     -    0s
H    0     0                    2.429226e+07 2.4294e+07  0.01%     -    0s

Explored 0 nodes (186 simplex iterations) in 0.03 seconds
Thread count was 4 (of 4 available processors)

Solution count 6: 2.42923e+07 2.42879e+07 2.42713e+07 ... 1.68221e+07
Pool objective bound 2.42942e+07

Optimal solution found (tolerance 1.00e-04)
Best objective 2.429226100000e+07, best bound 2.429415949448e+07, gap 0.0078%

[Sonja Mars]

Hi,

This behavior is indeed related to tolerances. If you take a look at the summary in the log files:

Best objective 2.429226100000e+07, best bound 2.429415949448e+07, gap 0.0078%

You can see that the lp_solve solution is between the two bounds. Gurobi stops its solve, when a particular MIP gap is reached. For this solve you used the default MIP gap which is 0.01%, so Gurobi stops when this gap is reached. The gap in the end was 0.0078%. 

If you are looking for a smaller gap, you can change the parameter MIPGap to a smaller value. Also see here for more details: http://www.gurobi.com/documentation/7.0/refman/mipgap2.html#parameter:MIPGap

Best regards, 

Sonja 

----

Dr. Sonja Mars

Gurobi Optimization - Technical Support 

[Daniel Espinoza]

Hi,

I would also point to the warning

Optimize a model with 199 rows, 588 columns and 1176 nonzeros
Variable types: 0 continuous, 588 integer (588 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+08]
  Objective range  [3e+01, 3e+06]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 7e+08]
Warning: Model contains large matrix coefficients
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.

Numerical problems can be part of the problem, and it might deteriorate running time performance too.

please consider to re-scale columns and/or rows to decrease the matrix range