Warm start linear programs with Gurobi

The Gurobi documentation is a little bit confusing about warm starting linear programs. Warm start is sometimes referred as advanced start. I decided to gather everything about it in a single post because recently a colleague had the same issue. Especially if you are applying column generation you should warm start your linear programs at each iteration to significantly speed up the optimization.

The Problem

Assume 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

Gurobi will do a warm start automatically.

However, when you

• add/remove a variable
• add/remove a constraint

Gurobi will discard the previous solution and start optimizing from scratch.

The remedy

There 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)

Whichever method you choose, you need to store the corresponding values before modifying the model. Then restore these values after the modification.

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/DStart

First save the actual values for both primal and dual variables:

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);

After modifying the model load variable values using PStart/DStart attributes:

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/VBasis

First save the information about the bases:

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);

Then after modifying the model, load the stored basis information:

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.

PROTIP

When you incorrectly set the warm start basis or solution Gurobi discards it and solves from scratch. When working with the warm start for the first time, turn on the Gurobi log and look out for the warning: "Warning, invalid warm-start [basis/solution] discarded". This is the only way that you can understand Gurobi is not warm starting the optimization procedure.