The ProblemAssume you have a linear programming model and called
optimize()on the model. Now you want to slightly modify your model and use the previous solution as an initial starting point to speed things up. This is called warm start.
Gurobi would do a warm start in certain cases, you don't need to do any extra work. When you change
- variable bounds
- coefficients in the objective value
- right hand side of the constraints
- coefficients of variables in the constraints
However, when you
- add/remove a variable
- add/remove a constraint
The remedyThere are two different ways of achieving warm start:
- Setting primal and dual variables values using PStart and DStart attributes.
- Setting the simplex basic using VBasis and CBasis attributes. (CBasis corresponds to slack variables if you were wondering)
According to Gurobi documentation using VBasis/CBasis method performs better. This is almost always true. However, in my comparisons PStart/DStart method led to increased speed gains for my model. Although I can't exactly explain why this happens, I suspect it has something to do with my problem structure. See the discussion here if you are interested. To summarize, you should check which warm start method works best for you. If you are lazy, use the VBasis/CBasis method.
Below I give code snippets on how to store and load relevant values for each method. There is also GitHub repo available for the full code. The code is written in Java but you will get the idea.
PStart/DStartFirst save the actual values for both primal and dual variables:
After modifying the model load variable values using
PSTARTS = new double[vars.length]; for (int i = 0; i < vars.length; i++) PSTARTS[i] = vars[i].get(DoubleAttr.X); DSTARTS = new double[constrs.length]; for (int i = 0; i < constrs.length; i++) DSTARTS[i] = constrs[i].get(DoubleAttr.Pi);
for (int i = 0; i < vars.length; i++) vars[i].set(PStart, PSTARTS[i]); for (int i = 0; i < constrs.length; i++) constrs[i].set(DStart, DSTARTS[i]);
CBasis/VBasisFirst save the information about the bases:
Then after modifying the model, load the stored basis information:
VBASES = new int[vars.length]; for (int i = 0; i < vars.length; i++) VBASES[i] = vars[i].get(VBasis); CBASES = new int[constrs.length]; for (int i = 0; i < constrs.length; i++) CBASES[i] = constrs[i].get(CBasis);
for (int i = 0; i < vars.length; i++) vars[i].set(VBasis, VBASES[i]); for (int i = 0; i < constrs.length; i++) constrs[i].set(CBasis, CBASES[i]);
Below is an example output comparing three methods. As you can see warm starting makes a dramatic difference.
Cold start: 1.271 secs. Warm start with PStart/Dstart: 0.230 secs. Warm start with VBasis/CBasis: 0.110 secs.
The full code can be found in this GitHub repo.