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.