Warm starting Gurobi's binary variables
Answered
Suppose I have an optimization problem with 1000 binary variables. I predict the binaries, with say a neural network. With the 1000 predicted binaries, 999 are "correct" in the sense that they belong to a feasible solution, but the last binary is incorrect, i.e. it makes the overall binary variable set infeasible.
Can someone explain what Gurobi does in this situation? Does warm starting with the binaries help at all? Clearly, fixing the binaries will make the problem infeasible, but if I just supply these 1000 binaries as an initial guess... what happens in the branch and bound tree?
-
There are two options in Gurobi: providing a MIP start or defining variable hints:
- MIP start: A MIP start can be provided either by using the Start variable attribute or by loading a MIP start (.mst) or a solution (.sol) file. Gurobi will then use this information to generate a feasible start solution. It is not necessary to provide a value for each variable. If you define values for a subset of the binary and integer variables, Gurobi will try to compute feasible values for the remaining variables.
In your case, if you know which 999 variables are the correct ones, you could set only values for these variables. -
Variable hints: These values guide the solver throughout the solution process. If you know that a variable is likely to have a particular value in the solution, you can set the variable hint.
Gurobi considers these values in its heuristics and when deciding which node to process.
See also How do I use MIP starts? for more information.
0 - MIP start: A MIP start can be provided either by using the Start variable attribute or by loading a MIP start (.mst) or a solution (.sol) file. Gurobi will then use this information to generate a feasible start solution. It is not necessary to provide a value for each variable. If you define values for a subset of the binary and integer variables, Gurobi will try to compute feasible values for the remaining variables.
-
Thanks Marika. Can you explain what is happening algorithmically for a few of the heuristics and how they interact exactly with the warm start variables? I understand the overall algorithm is proprietary but perhaps you can share a few out of the many heuristics. It makes it hard to use Gurobi in academic research if we cannot explain how our warm starting method interacts with Gurobi’s variable hints on a technical level.
0 -
In the Heuristics when variables need to be sorted VarHintPri is used and VarHintVal gives the direction for the fixing.
0 -
Yes, but what type of heuristics are these? I saw a reference in a webinar that one heuristic is "large neighborhood search". What else is there?
0 -
If there are variables hints available then two additional heuristics are called. One is a kind of diving heuristic and the other a fixing heuristic that creates and solves a sub-MIP.
All other Gurobi heuristics are not influenced by the variable hints.
0
Please sign in to leave a comment.
Comments
5 comments