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 . . . |
| Restart | Iteration log . . . |
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. Iteration log . . . |
| Restart with LPMETHOD=2 | Dual crossover. |
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).
I have a good guess on what is going on.
ReplyDeleteAre you by any change restarting from a interior point solution ?
I see in the two last output it says "cross over" i.e both dual and primal superbasics has to be moved either to bound or in the basis. A lot of tricks goes on in the cross over phase. My bet is, that in the first restart, CPLEX just squashes the superbasics and recalculates a basis, then you will see lots of degenerated moves.
On another note. When will we see you on twitter ? It has become a great tool for sharing O.R info. People like you with a practical view on O.R is badly needed :-)
ReplyDeleteBo is correct, Twitter is a great tool to publicize your blog. Some of your blog entries have been tweeted already, but the best way is to have the tweets originally come from you. Then we can retweet them, when we think they are of interest to our followers.
ReplyDeleteOne of the good things about blogs is when debate arise in the comments. There are often quality comments to your blog, but I mis some of them because the RSS feed does not pick up comments. Maybe I am doing it wrong, can you get notify on comments from RSS feed ?
ReplyDeleteNo interior point solution, it was restarted from an optimal basis. I believe Cplex uses crossover technique to setup a basis if they have levels available. Still, no idea why LPMETHOD=0 is behaving differently.
ReplyDeleteConsider this :
ReplyDelete1) You have a optimal basis.
2) Now you change objectives of certain variables.
3) Some of these variables are basic.
4) The dual solution from 1) is not basic any more i.e it's got reduced cost not zero for basic variables (dual superbasics). So the solution is interior (or exterior).
5) You now have two choices :
a) Recalc duals on constraints i.e c_b-yB=0
b) Do dual cross over i.e clean dual solution in number of pivots equal to number of dual super basics.
I will bet a) is done in the bad run and b) is done in the good run :-)
When you do a) you have no control over dual infeasibility and can not exploit structure, so in some cases b) is preferred and much more elegant.
Even if you don't change the objective, dual superbasic may still arise in the presolve phase. I am not sure if CPLEX currently presolves on hotstart, but if they do, then the scenario with dual superbasic created in presolve is possible.
ReplyDelete