Should I linearize my non-linear pseudo-Boolean model before passing it to Gurobi?

Answered

Fengyu Xie

May 09, 2021 02:03

• 
• 

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

 

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:55 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  May 10, 2021 11:39

  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

Post is closed for comments.