Saturday, June 18, 2011

Advanced basis with Cplex

Usually Cplex behaves very predictable with LP’s that have an advanced basis to start from. But now I have something that puzzles me. Basically I do a solve from an optimal solution. This should normally run in just a few iterations. But with the default setting I see:

First model

Iteration log . . .
Iteration:     1   Dual objective     =             1.005320
Iteration:   581   Dual objective     =           296.751221
Iteration:  1247   Dual objective     =           511.623938
Iteration:  1681   Dual objective     =           514.072257
LP status(1): optimal

Restart

Iteration log . . .
Iteration:     1    Objective     =           515.104554
Perturbation started.
Iteration:   402    Objective     =           515.104554
Iteration:   806    Objective     =           515.104088
Iteration:  1107    Objective     =           515.103794
Iteration:  1406    Objective     =           515.103557
Iteration:  1684    Objective     =           515.103314
Iteration:  1939    Objective     =           515.103216
Iteration:  2186    Objective     =           515.103124
Iteration:  2434    Objective     =           515.103037
Iteration:  2672    Objective     =           515.102875
Iteration:  2951    Objective     =           515.102790
Iteration:  3210    Objective     =           515.102730
Iteration:  3472    Objective     =           515.102670
Iteration:  3709    Objective     =           515.102630
Iteration:  3943    Objective     =           515.102592
Iteration:  4199    Objective     =           515.102525
Iteration:  4445    Objective     =           515.102493
Iteration:  4692    Objective     =           515.102468
Iteration:  4933    Objective     =           515.102448
Iteration:  5181    Objective     =           515.102428
Iteration:  5431    Objective     =           515.102411
Iteration:  5689    Objective     =           515.102395
Iteration:  5962    Objective     =           515.102379
Iteration:  6224    Objective     =           515.102362
Iteration:  6487    Objective     =           515.102353
Iteration:  6765    Objective     =           515.102342
Iteration:  7041    Objective     =           515.102335
Removing perturbation.
LP status(1): optimal

The restart from an optimal basis takes more iterations than solving from scratch. This is with a default setting of LPMETHOD=0 (automatic). When I use LPMETHOD=1 (Primal Simplex) or LPMETHOD=2 (Dual Simplex) I see:

Restart with LPMETHOD=1

Primal crossover.
  Primal:  Fixed no variables.
  Dual:  Fixing 993 variables.
      992 DMoves:  Infeasibility 6.76704726e+000  Objective 5.15104554e+002
      394 DMoves:  Infeasibility 1.33823843e+000  Objective 5.15104554e+002
        0 DMoves:  Infeasibility 7.17019911e-001  Objective 5.15104554e+002
  Dual:  Pushed 0, exchanged 993.

Iteration log . . .
Iteration:     1    Objective     =           515.104554
LP status(1): optimal

Restart with LPMETHOD=2

Dual crossover.
  Dual:  Fixing 994 variables.
      993 DMoves:  Infeasibility 2.07167616e-013  Objective 5.15104554e+002
      414 DMoves:  Infeasibility 7.97140132e-014  Objective 5.15104554e+002
        0 DMoves:  Infeasibility 0.00000000e+000  Objective 5.15104554e+002
  Dual:  Pushed 1, exchanged 993.
  Primal:  Fixed no variables.
LP status(1): optimal

These seem indeed to take fewer iterations to solve the restarted model. I always assumed LPMETHOD=0 would just choose primal or dual simplex, but apparently it also does other things, and in this case that is not helping.

Update

I did some more experiments. With LPMETHOD=0 I can now also achieve a restart if I set all variable levels to zero. I.e.

solve m minimizing z using lp;
solve
m minimizing z using lp;

gives a bad restart, while:

solve m minimizing z using lp;
x.l(i,j) = 0;
z.l=0;

solve
m minimizing z using lp;

gives me zero iterations for the restart. Something is not completely right. As Bo suggested in his comments, the reason may be related to Cplex trying to do a presolve on an advanced basis. (I have heard about some ancient solvers that tried a basis preserving presolve, may be more limited than what current presolvers do). The difference between LPMETHOD=0 and both LPMETHOD=1 and LPMETHOD=2 is still a mystery to me.

Update 2

The behavior can be partially explained by looking at the Cplex documentation describing the Advind parameter:

For continuous models solved with simplex, setting 1 (one) will use the currently loaded basis. If a basis is available only for the original, unpresolved model, or if CPLEX has a start vector rather than a simplex basis, then the simplex algorithm will proceed on the unpresolved model. With setting 2, CPLEX will first perform presolve on the model and on the basis or start vector, and then proceed with optimization on the presolved problem.

I was using the model from a GAMS environment. There the default is 2. The documentation for GAMS/Cplex is somewhat more limited than the above paragraph:

Advind (Integer)
Use an Advanced Basis. GAMS/Cplex will automatically use an advanced basis from a previous solve
statement. The GAMS Bratio option can be used to specify when not to use an advanced basis. The Cplex
option advind can be used to ignore a basis passed on by GAMS (it overrides Bratio).
(default = determined by GAMS Bratio)
0 Do not use advanced basis
1 Use advanced basis if available
2 Crash an advanced basis if available (use basis with presolve)

Looks like 1 is better for a very good basis, 2 may be better for models with a basis that is not very good (in that case presolving will pay off even when destroying some basis information).