Friday, April 2, 2010

GAMS/Cplex: final solve can be expensive

GAMS likes to display marginals on MIP models. It does this by solving an LP with all integers fixed at their current values. This final solve can be very expensive. Here is an example:

---   31,617 rows  92,289 columns  276,386 non-zeroes
---   128 discrete-columns



Root relaxation solution time =    8.08 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap

      0     0      154.2800     3                    154.2800    45818        
*     0+    0                          154.2800      154.2800    45818    0.00%
      0     0        cutoff            154.2800      154.2800    45818    0.00%
MIP status(101): integer optimal solution
                                                      
B&B time: not displayed but estimated at < 1 sec
Fixing integer variables, and solving final LP...
Tried aggregator 1 time.
LP Presolve eliminated 129 rows and 257 columns.
Aggregator did 239 substitutions.
Reduced LP has 31249 rows, 91793 columns, and 275012 nonzeros.
Presolve time =    0.16 sec.
Initializing dual steep norms . . .

Iteration log . . .
Iteration:     1   Dual objective     =             0.000000
Perturbation started.
Iteration:   102   Dual objective     =             0.000000
Iteration:   538   Dual objective     =            13.863577
Iteration:  1033   Dual objective     =            14.787416

….
Iteration: 54455   Dual objective     =           151.954457
Iteration: 54694   Dual objective     =           153.771165
Iteration: 54911   Dual objective     =           153.771165
Elapsed time =  188.09 sec. (55000 iterations).
Iteration: 55190   Dual objective     =           153.771165
Iteration: 55452   Dual objective     =           154.280180
Removing perturbation.
Fixed MIP status(1): optimal  
                                                       Final LP: time not displayed but estimated at > 188 sec

So we have approximately:

  1. Root LP: 8 sec
  2. B&B: 1 sec
  3. Final LP: 188 sec

If we are not interested in duals (for most MIP models this is the case), the last step be omitted with an option (SOLVEFINAL=0). That would reduce the total solution time from 200 seconds to 10 seconds.

Only the root time is displayed, so I had to guess the other times.

5 comments:

  1. The last LP solve should use the optimal MIP solution as a hotstart and not start all over again as it obviously does.

    ReplyDelete
  2. I think they just leave that up to Cplex: i.e. change Cplex problem type to fixed and resolve.

    ReplyDelete
  3. They should use primal to do that final solve, not dual.

    ReplyDelete
  4. As a GAMS user I think I cannot do that with the current Cplex link. I have passed on the model to the GAMS people so they can have a look.

    ReplyDelete
  5. Actually there is an undocumented GAMS option to use a option file for the fixed model. I.e. we can use:

    $onecho > cplex.opt
    startalg 1
    mipsearch 1
    *solvefinal 0
    fixoptfile fix.opt
    $offecho

    $onecho > fix.opt
    lpmethod 1
    $offecho

    This solves the final LP very fast.

    In the mean time the problem has been passed on to the Cplex people to see if something needs to be done inside Cplex to do this better automatically.

    ReplyDelete