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!
Please sign in to leave a comment.