Still not proven optimal…

This is a very small MIP:

Starting Gurobi... Optimize a model with 24 rows, 54 columns and 132 nonzeros Presolve removed 6 rows and 6 columns Presolve time: 0.11s Presolved: 18 rows, 48 columns, 114 nonzeros Variable types: 12 continuous, 36 integer (0 binary)

so I expected to run this very quickly on a fast 8 core Xeon machine. The time limit of 9999 seconds should be no problem even with the OPTCR (rel. gap tolerance) of 0.0. But I see:

835689342 7572026 infeasible   63         0.00062    0.00000   100%   1.0 9980s 836077602 7576642    0.00000   65   14    0.00062    0.00000   100%   1.0 9985s 836454289 7582365    0.00000   56   15    0.00062    0.00000   100%   1.0 9990s 836850333 7587882    0.00000   45   15    0.00062    0.00000   100%   1.0 9995s Cutting planes:   Gomory: 1   MIR: 2 Explored 837155963 nodes (841647794 simplex iterations) in 9999.00 seconds Thread count was 8 (of 8 available processors) Time limit reached Best objective 6.179540598832e-04, best bound 0.000000000000e+00, gap 100.0000% MIP status(9): Optimization terminated due to time limit.

This is not a Gurobi problem: Cplex is just as bad. Apparently these branch and bound methods are just not suited very well for this problem. I have solved some huge problems with hundreds of thousands of binary variables, but here we see some evidence, not all problems are that easy.

Recently I saw someone writing:

gurobi> m.setParam('Threads',80)
You may all drool now.

Guess we need something like that to solve my tiny 36 integer variable problem….

Notes:

• The OPTCR (gap tolerance) setting is not an issue as it turns out the best bound remains at 0.0, so a gap of 100% is reported.
• Gurobi is solving the nodes pretty efficiently. Approx. 1 simplex iteration per node, and > 80k nodes per second.

Update

Some Cplex runs solve this fast (see comments below), but on some machines I see the same problem:

Cplex 12.3.0.0 Reading data... Starting Cplex... Tried aggregator 2 times. MIP Presolve eliminated 1 rows and 1 columns. MIP Presolve modified 36 coefficients. Aggregator did 6 substitutions. Reduced MIP has 18 rows, 48 columns, and 114 nonzeros. Reduced MIP has 0 binaries, 36 generals, 0 SOSs, and 0 indicators. … Elapsed real time = 9880.28 sec. (tree size = 1251.36 MB, solutions = 70) Nodefile size = 1123.85 MB (527.18 MB after compression) 478309344 6481362        0.0000    15        0.0012        0.0000 5.26e+008  100.00% 479049990 6483695        0.0000    15        0.0012        0.0000 5.27e+008  100.00% 479749224 6499596        0.0000    15        0.0012        0.0000 5.27e+008  100.00% 480524806 6502892    infeasible              0.0012        0.0000 5.28e+008  100.00% 481284148 6500253        0.0000    16        0.0012        0.0000 5.29e+008  100.00% 482022525 6501343        0.0000    16        0.0012        0.0000 5.30e+008  100.00% 482764367 6511470        0.0000    16        0.0012        0.0000 5.31e+008  100.00% Mixed integer rounding cuts applied:  2 Zero-half cuts applied:  2 Gomory fractional cuts applied:  2 Root node processing (before b&c):   Real time             =    0.03 Parallel b&c, 4 threads:   Real time             = 9998.98   Sync time (average)   =  420.45   Wait time (average)   =   45.69                           ------- Total (root+branch&cut) = 9999.01 sec. MIP status(107): time limit exceeded Fixing integer variables, and solving final LP... Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 25 rows and 55 columns. All rows and columns eliminated. Fixed MIP status(1): optimal Resource limit exceeded. MIP Solution:            0.001230    (530937464 iterations, 482992718 nodes) Final Solve:             0.001230    (0 iterations) Best possible:           0.000000 Absolute gap:            0.001230 Relative gap:            1.000000

This is a worse solution than Gurobi found. But on a different machine using 8 threads:

Cplex 12.3.0.0 Reading data... Starting Cplex... Tried aggregator 2 times. MIP Presolve eliminated 1 rows and 1 columns. MIP Presolve modified 36 coefficients. Aggregator did 6 substitutions. Reduced MIP has 18 rows, 48 columns, and 114 nonzeros. Reduced MIP has 0 binaries, 36 generals, 0 SOSs, and 0 indicators. … 129959  4046        0.0003    10        0.0031        0.0003   113627   91.54% *165794  5594      integral     0        0.0027        0.0005   146606   81.09% *170030  4859      integral     0        0.0019        0.0005   149634   72.63% *193953  3702      integral     0        0.0007        0.0006   171409   15.85% *195840   418      integral     0        0.0006        0.0006   172394    2.03% Mixed integer rounding cuts applied:  3 Gomory fractional cuts applied:  1 Root node processing (before b&c):   Real time             =    0.12 Parallel b&c, 8 threads:   Real time             =    4.10   Sync time (average)   =    0.39   Wait time (average)   =    0.02                           ------- Total (root+branch&cut) =    4.23 sec. MIP status(101): integer optimal solution Fixing integer variables, and solving final LP... Parallel mode: deterministic, using up to 2 threads for concurrent optimization. Tried aggregator 1 time. LP Presolve eliminated 25 rows and 55 columns. All rows and columns eliminated. Fixed MIP status(1): optimal Proven optimal solution. MIP Solution:            0.000616    (175023 iterations, 203294 nodes) Final Solve:             0.000616    (0 iterations) Best possible:           0.000616 Absolute gap:            0.000000 Relative gap:            0.000000

So we have some very different behavior here: optimal in just 4 seconds.