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.

14 comments:

  1. Looks really surprising indeed - these solvers should be able to tackle that pretty easily. It may be the case that your branching got stuck in local minimum because of a few variables. At least in CPLEX you can try setting priorities for branching which can be helpful here, unfortunately Gurobi is not as good in customization AFAIK.

    ReplyDelete
  2. Can you share the model? I like these examples. Non-binary MIP can be pretty hard.

    ReplyDelete
  3. "It may be the case that your branching got stuck in local minimum because of a few variables."

    To be honest, I have no idea what this means.

    "At least in CPLEX you can try setting priorities for branching which can be helpful here".

    May be. It is not so common a fixed user-provided branching order will beat Cplex.

    ReplyDelete
  4. "Can you share the model?"

    Here you go:
    http://amsterdamoptimization.com/models/metolius12.mps

    ReplyDelete
  5. Cplex 12.3 on my laptop Core2 Duo T7250

    http://pastebin.com/tnyzTZtT

    MIP - Integer optimal, tolerance (0/1e-06): Objective = 6.1571157793e-04
    Current MIP best bound = 6.1480313939e-04 (gap = 9.08439e-07, 0.15%)
    Solution time = 111.11 sec. Iterations = 1066356 Nodes = 1250094 (63)

    ReplyDelete
  6. Sorry if I didn't make it clear. What I meant is that some of your variables may have so heavy impact on the solution that not branching on them early may cause solver to explore space where no big improvement is possible.

    I'm not experienced with CPLEX, neither I know the details of the problem we're discussing here, so it's just guessing on my end if customizing branching rules and priorities is worth the hassle or not in this software. But since in general choosing node/branching and tight bound are the essence of B&B, when default heuristic fails or takes much more time than is allowed, there's probably most space for some experimentation in these areas.

    Now, all that probably sounded trivial to you, but I'm still new to this so this is non trivial and cool to me :)

    ReplyDelete
  7. "gap = 9.08439e-07, 0.15%"

    Looks like it is not completely there yet...

    ReplyDelete
  8. well, with:
    CPX_PARAM_EPAGAP 0.0
    CPX_PARAM_EPGAP 0.0
    CPX_PARAM_EPINT 0.0

    the output is:

    MIP - Integer optimal solution: Objective = 6.1571157793e-04
    Solution time = 61.21 sec. Iterations = 520679 Nodes = 859677

    ReplyDelete
  9. With Cplex I see different results on different machines (with different thread counts). I'll show the log for 4 threads.

    ReplyDelete
  10. Thanks Erwin. Interesting model. I can see why it might be hard.
    My intuition is that it comes from the level of precision in the instance data. (To me, it seems to share some similarities to some very hard knapsack-type problems). FWIW, I "solved" it in 1 sec on my laptop by changing all coefficients and RHS to have only 2 coefficients.


    gurobi> m = read("approx.lp")
    Read LP format model from file approx.lp
    Reading time = 0.00 seconds
    (null): 24 rows, 54 columns, 132 nonzeros
    gurobi> m.optimize()
    Optimize a model with 24 rows, 54 columns and 132 nonzeros
    Presolve removed 6 rows and 6 columns
    Presolve time: 0.02s
    Presolved: 18 rows, 48 columns, 114 nonzeros
    Variable types: 12 continuous, 36 integer (0 binary)
    Found heuristic solution: objective 39.2500000
    Found heuristic solution: objective 35.1200000

    Root relaxation: objective 0.000000e+00, 30 iterations, 0.00 seconds

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

    0 0 0.00000 0 16 35.12000 0.00000 100% - 0s
    H 0 0 1.4000000 0.00000 100% - 0s
    0 0 0.00000 0 14 1.40000 0.00000 100% - 0s
    0 0 0.00000 0 14 1.40000 0.00000 100% - 0s
    0 0 0.00000 0 14 1.40000 0.00000 100% - 0s
    0 0 0.00000 0 14 1.40000 0.00000 100% - 0s
    * 42 0 36 0.4000000 0.00000 100% 2.2 0s
    * 318 193 38 0.3600000 0.00000 100% 1.7 0s
    * 403 259 32 0.3500000 0.00000 100% 1.7 0s
    * 423 213 27 0.2200000 0.00000 100% 1.7 0s
    H 505 248 0.2000000 0.00000 100% 1.6 0s
    H 528 240 0.1800000 0.00000 100% 1.6 0s
    H 748 319 0.1700000 0.00000 100% 1.6 0s
    * 959 354 37 0.1400000 0.00000 100% 1.5 0s
    * 3841 1437 86 0.1200000 0.00000 100% 1.6 0s
    H 4098 1547 0.1100000 0.00000 100% 1.6 0s
    * 4109 1483 82 0.1000000 0.00000 100% 1.6 0s
    H 4603 1584 0.0800000 0.00000 100% 1.7 0s
    H 7431 2438 0.0700000 0.00000 100% 1.7 0s
    * 9920 2920 65 0.0500000 0.00000 100% 1.7 0s
    H 9958 2759 0.0400000 0.00000 100% 1.7 0s
    H11572 2579 0.0200000 0.00000 100% 1.7 0s
    H15613 2474 0.0100000 0.00000 100% 1.6 0s
    H26945 17 0.0000000 0.00000 0.0% 1.6 0s

    Cutting planes:
    Gomory: 2
    MIR: 3

    Explored 27147 nodes (44625 simplex iterations) in 0.97 seconds
    Thread count was 4 (of 4 available processors)

    Optimal solution found (tolerance 1.00e-04)
    Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0%

    I'm an engineering, so this is good enough for me. :-)

    ReplyDelete
  11. Ugh. I should have said "all coefficients and RHS to have only 2 *decimal places.* And I'm *in* engineering.

    ReplyDelete
  12. Is that just luck or is there a good reason why this rounded number makes the problem easier? My intuition (often wrong) says this is just luck.

    ReplyDelete
  13. In order to prove optimality the solver has to definitively rule out the possibility of better solutions than the one it's got. When you have more decimal places in the input in some cases this can be harder to do since there may be competing solutions that are "really darn close". Truncating may make it easier to sort things out (loosely speaking - I am in software so I get to do that).

    ReplyDelete
  14. Yes -- finding a solution is often just luck. But I don't think it is completely luck in this case. With all those extra decimal places, it is just *waaay* to easy for the LP to 'cheat' and find relaxations of value 0. By limiting the decimal places, you remove some of the LPs flexibility for getting solutions of value 0, so that maybe the branching will 'hit' on one more easily. This is essentially what Nate suggests as well. And I also get to speak loosely, since I am an engineer.

    That said, if you have many similar instances in this family, and you rounded them all, I'd still be willing to bet that the rounded ones are quite a bit easier.

    ReplyDelete