Wednesday, October 26, 2011

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.