Should I linearize my nonlinear pseudoBoolean model before passing it to Gurobi?
AnsweredDear Gurobi users and developers,
Recently I'm using Gurobi to optimize a variety of nonlinear polynomial pseudo Booleanoptimization problems. Both the objective function and the constraints may have nonlinear 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 opensource pseudo Boolean tools such as OpenWBO, you need to linearize first because these tools can not handle nonlinear inputs at all. In gurobi, it seems you are allowed to give it a nonlinear 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 branchandbound nodes (for what propagation is, see this paper by Timo et al.: (PDF) Nonlinear PseudoBoolean 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 nonlinear 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 opensource solver SCIP, which handles the nonlinear 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