Should I linearize my non-linear pseudo-Boolean model before passing it to Gurobi?
Answered
Dear Gurobi users and developers,
Recently I'm using Gurobi to optimize a variety of non-linear polynomial pseudo Boolean-optimization problems. Both the objective function and the constraints may have non-linear terms, such as sigma_1*sigma_2*sigma_3, and so on.
A linearization of term sigma_1*sigma_2 looks like this:
sigma_1*sigma_2 = sigma_3
which is equivalent to 3 linear constraints:
sigma_3 <= sigma_1
sigma_3 <= sigma_2
sigma_1 + sigma_2 - sigma_3 <= 1
In some open-source pseudo Boolean tools such as Open-WBO, you need to linearize first because these tools can not handle non-linear inputs at all. In gurobi, it seems you are allowed to give it a non-linear input in .opb format, but the effect of not doing linearization is not clear.
Will gurobi do the linearization automatically before solving? If this is the case, will Gurobi automatically handle propagation in branch-and-bound nodes (for what propagation is, see this paper by Timo et al.: (PDF) Nonlinear Pseudo-Boolean Optimization: Relaxation or Propagation? (researchgate.net))? If I already linearized the model before writing OPB input, can gurobi still benefit from propagation, or it would not be able to do propagation at all (which can lower efficiency.)
In one word, should I linearize before writing OPB input? Or should I just write the non-linear objective and constraints into OPB?
Your answers will be highly appreciated!
Best,
Fengyu Xie
-
Hi Fengyu Xie,
Gurobi will always linearize your constraints provided in the OPB format. There is no parameter to apply the propagation described in the paper you mentioned. Thus, in order to test linearization vs. propagation for your model, you could refer to the open-source solver SCIP, which handles the non-linear terms as a special \(\texttt{and}\) object. If you conclude that linearization works best, you can then still switch back to Gurobi.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment