Custom search strategy for some variables (i.e. Minizinc int_search equivalent)

[baptiste...@gmail.com]

Hi there,

My current (huge) MIP problem has an objective of the form minimize (X0 + ... + Xn), where each Xi is a binary variable, and a lot of auxiliary variables in the model.

In the constraint modeling language Minizinc ( http://www.minizinc.org/ ), you can set a "strategy" for the tree exploration using the int_search function.
For example in my case, it would be something like int_search([X0,...,Xn], smallest, indomain_min, complete).
The idea is that when you want to optimize the model, you tell the solver that you want it to begin with the variables Xi, and since you want to minimize sum(Xi), you start with the lowest possible value of each Xi.
Basically, this just mean that the tree exploration first starts with the Xi variables, and first try to assign them to 0 (in my case). Afterwards the solver decide by himself. I believe that this might speed up the optimization in my case.

Is there anything similar in Gurobi ?

Thanks in advance,
Regards,

Baptiste Lambin

[Michael Winkler]

Hi Baptiste,

the Branch&Bound tree that a MIP solver works through is created (not only) based on information that comes from solving LPs (linear relaxations) in each of the Branch&Bound nodes. This is quite different from a CP solver tree search.
Solving an LP already drives the search in the direction of your objective, e.g., in your case tries to minimize (X0 + ... + Xn) (relaxing integrality on all integral variables). For the root node this gives you a proven lower bound on your objective function.
Now if the variables in the objective function are fractional in the LP solution they are considered (but also all other fractional variables) as branching candidates, i.e, to split the problem into two or more sub-problems. Experiments have shown that it is not always useful to only branch on variables that appear in to objective function.

What you can now do to influence the branching decisions is to install "branch priorities", see https://www.gurobi.com/documentation/7.0/refman/branchpriority.html#attr:BranchPriority and https://www.gurobi.com/documentation/7.5/refman/ord_format.html. But you can also use "variable hints" to guide the search and also heuristics that try to find a (good) feasible solution, see https://www.gurobi.com/documentation/7.5/refman/varhintval.html#attr:VarHintVal and https://www.gurobi.com/documentation/7.5/refman/varhintpri.html#attr:VarHintPri, and https://www.gurobi.com/documentation/7.5/refman/hnt_format.html.
So this is not exactly what I guess "int_search([X0,...,Xn], smallest, indomain_min, complete)" is doing but it should help to try something similar.

Best,
Michael

[baptiste...@gmail.com]

Hi Michael,

Thanks a lot for your answer, this seems to be what I'm looking for !

Regards,

Baptiste