MIP Starts sometimes disappoint

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.

Some reasons can be:

• Solvers on their own are very good in finding good solutions quickly: they contain batteries of heuristics to find good integer solutions and improve them.
• Time you spend on calculating a good initial solution can be used by the solver. If you spent n seconds to construct an initial solution, that is time taken away from the solver.
• The solver spends most time in the tail: getting the gap down to zero (or close).

This is probably best illustrated as follows:

The blue line represents the currently best integer solution. I.e. we are minimizing here. When we provide a good integer solution we basically eat away some time from the left of the picture. But that is exactly the part where MIP solvers are very effective: the blue line decreases there very fast (the gradient with respect to time is large). In the picture above if we would have provided a starting solution with an objective value of 1000, we would essentially cut out the shaded area. The long tail at the right is where we spend most cycles.

The red line is the lower bound: the best possible objective. When we skip the shaded box we also miss out on some improvement in this bound.

It is clear that in this case, if we cannot find good solutions very cheaply ourselves, we may as well leave this to the solver.

Of course there are cases where starting with good solutions may make good sense, e.g.:

• We can obtain good solutions quickly.
• We may even have a feasible operating point by nature of the problem (e.g. when optimizing a certain process we may observe the physical state and use that operating point as a starting point).
• Good solutions found outside the solver may improve reliability of the overall process: if the MIP solver fails completely we still have a good solution.

Update

As suggested in the comments stopping on a gap percentage may be more effective in reducing the solution time:



Note that this is a depiction of quite a typical behavior of MIP lower and upper bounds: almost all non-trivial models show this type of narrowing of the gap. Often things are even more pronounced than in this smaller example. Of course stopping on gap does not likely give you the optimal solution, but in practical cases a gap of say a few percent or so may be quite acceptable. Setting a gap tolerance is a very standard approach when solving large MIP models.