How does the "re-optimize" feature work in commercial optimization solvers such as IBM CPLEX and Gurobi? I recently experienced a considerable performance boost by re-solving a model with incremental changes to the model. I was interested to learn how those solvers improve subsequent computations.
1
-
$\begingroup$ What kind of problem are you solving? LP? MILP? $\endgroup$– fontanfFeb 2 at 20:07
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
CPLEX has an advanced start parameter which dictates how it acts when solve is called on a previously solved/partially solved model.
For MIP models with the default setting of the parameter, if you partially solve a model (stopping short of proven optimality) and then tweak solver parameters (without altering the model) and solve again, CPLEX will pick up where it left off, starting from the search tree left at the end of the first run. If you change the model, I don't think the old search tree can be used, but CPLEX can try to use the previous solution as a starting solution (using heuristics to try to "repair" it if changes to the model made it infeasible). A different setting of the parameter tells CPLEX to restart from the root but try to retain the current incumbent solution if there is one. (I'm not sure if CPLEX tries to repair the solution should it no longer be feasible, or just discards it.)
For LP models with advanced start turned on, CPLEX will attempt to start from the final basis of the previous run or, if the barrier method is being used, try to restart from the last "barrier iterate".
So, assuming the model has changed, a "hot start" for an LP might allow the solver to get to a feasible basis faster (perhaps by taking the last basis of the previous run and using dual simplex to restore feasibility) or might provide a feasible incumbent / primal bound sooner (by repairing a feasible solution to the previous model). Note the use of the word "might".
$\begingroup$
$\endgroup$
Probably this link from Gurobi will help. You have to call the optimize() function in gurobi after you change parameters like the rhs of a constraint, add/remove constraints, change bounds of variables, change objective coefficients or hyperparameters like optimal gap, integrality gap (for MIP), turning certain constraints into lazy constraints (kind of delayed row generation), changing warm start etc.
Basically the solver re-solves the model and there's option to consider the last feasible candidate set.
$\begingroup$
$\endgroup$
Here are two threads published by @Erwin Kalvelagen on his blog that would be useful:
Modern MIP solvers allow to use a good integer solution to “warm start” the branch and bound process. This looks like a very good approach to cut down on total solution times, and it sometimes is. But in many cases it turns out, finding good solutions and passing them on to the MIP solver is not worth the while.
NLP solvers can fail for a number of reasons. One way to increase the reliability of a production run is to use a back-up solver in case the main solver fails. In GAMS primal and dual information is passed between SOLVE statements even if different solvers are used. This is actually very useful in a case I just observed.
I was really enjoying both.
