How to use warm start to solve MIPs efficiently?

Question

I'm working on the scheduling model which takes a long time to solve to optimality (even for a small instance), therefore I would like to use a warm start (MIP start) to solve the problem. I'm using the following two different methods:

1. Determine a feasible solution and feed that into the model.
2. Using B&B GAP control to achieve a sub-optimal solution and then feeding that into the model.

The original model, a small instance, is solved in 2 minutes. Its objective function value is 5966. In the first case, the model is solved quickly (less than 1 second) and the objective function value is 6737. In the second case, I set the GAP to be 0.20. The model is solved in 12 seconds and the objective function value is 5966.

According to the above comments, I was wondering if:

1. Is my approach suitable to use a warm start into the model?
2. Is there any way to improve the objective function value of 6737 (first case)?
3. Are there any other ways to execute a warm start to solve the problem as quickly as possible?

Answer 1

Just for concreteness, I'll phrase this in terms of a minimization problem, but the same arguments apply to maximization as well. Warm-starting a model is essentially a gamble. You are gambling that the time spent computing the initial solution will be compensated by a reduction in solution time (most likely resulting from earlier pruning of nodes due to a better upper bound on the objective value). There are several things to consider.

1. Sometimes a better starting solution actually results in worse solver performance. This seems to be due to the better start altering some of the cuts the solver generates and/or leading the solver to explore less productive portions of search space and/or bad karma (on your part, not the solver's). AFAIK there is no way to anticipate this occurring.
2. If the solver, without a warm start (or with an inferior warm start), finds as good an incumbent as your starting solution (or better) in an amount of time shorter than what you spent finding the starting solution, it's probably not worth warm starting. This can happen if the solver's heuristics are either better than yours or just luckier.
3. Assuming that you are seeking proven optimality, a slow solve can be the result of either or both of two factors: slow improvement of the upper bound to the optimal value; and slow improvement of the lower bound to the optimal value. A good warm start may help the first but not the second. If your lower bound is far from optimal and improving slowly, extra effort generating a better warm start will not help. You need to investigate bound tightening procedures, options in the solver, or tighter formulations ... or just accept that the solution will take forever. (I'm in that boat myself right now.)

Answer 2

1. Is my approach suitable to use a warm start into the model?

If I understand you correctly, you first compute some solution, either by using the first feasible solution you get (variant 1) or by solving the model till a certain optimality gap is achieved (e.g. 20%), and then use the found solution as a warm start for your original model.
This is a suitable approach: It will help the solver to fathom certain nodes in the branch-and-bound-tree which have a higher (relaxed) objective value than the warm start solution you provide (or the current best solution if a better was found).

2. Is there any way to improve the objective function value of 6737 (first case)?

It depends on how you get the feasible solution... If you use a heuristic, you would want to tweak it or give it more computation time. If you also use the MIP and then just take the first found solution you could also try to give the solver more time to find a better solution.
Another idea would be to provide just a partial solution and then let the solver try to repair the solution. Sometimes the solver is able to not only repair the partial solution but also find one with better objective value.

3. Are there any other ways to execute a warm start to solve the problem as quickly as possible

It seems that for your problem it takes more time to prove optimality rather than finding the best solution. You could try to give more emphasis on proving optimality (which you usually can adjust via some of the solver's parameters).