Degree-4 nonlinear constraint disaggregated to bilinear during presolve

回答済み

Paula P.

2026年05月29日 20:08

• 

Dear Gurobi community, 

I am working on a Mixed-Integer Nonlinear Program (MINLP) using Gurobi 13.0.0 (academic license) via gurobipy in Python. In my model, the objective references an auxiliary variable HC_i defined via a degree-4 equality constraint: HC_i = w_i · (Cbar_i - C_i/2) · U_i · L_i    for all i in V ; where w_i is binary and Cbar_i, C_i, U_i, L_i are continuous decision variables. Since Gurobi does not support degree-4 terms in the objective directly, I introduced HC_i as an auxiliary variable so the nonlinearity lives entirely in the constraint while the objective stays linear.

The solver log shows:

  Added 33 variables to disaggregate expressions
  Presolved model has 9 bilinear constraint(s)
  Solving non-convex MIQCP to global optimality
  Optimal solution found (tolerance 1.00e-04), gap 0.0000%

I have three questions:

1. DISAGGREGATION: The log shows 33 variables added to disaggregate expressions. Is Gurobi decomposing the degree-4 product into a chain of bilinear constraints during presolve, e.g.:   t1 = w_i · (Cbar_i - C_i/2) ;   t2 = t1 · U_i ;   HC_i = t2 · L_i  . Is this interpretation correct? Is there documentation on how this disaggregation works internally?

2. MIQCP LABEL: The log reports "Presolved model has 9 bilinear constraint(s)" and "Solving non-convex MIQCP to global optimality", but my original constraints are degree-4, not quadratic. Does Gurobi reclassify the problem as MIQCP after disaggregating the degree-4 terms into chains of bilinear (degree-2) constraints? Is the MIQCP label referring to the presolved model rather than the original formulation?

3. GLOBAL OPTIMALITY GUARANTEE: The log reports gap 0.0000%. Given that the presolved model contains bilinear constraints (which are generally nonconvex), does the spatial branch-and-bound algorithm provide a true global optimality guarantee? Or is the gap metric only guaranteeing local optimality within the branch-and-bound tree?

Any references to documentation would be greatly appreciated.

Thank you :)

関連

• Nonlinear
• Branch-and-Cut
• Bilinear

0

• 

  Riley Clement

  • Gurobi Staff

  2026年05月31日 07:03

  Hi Paula,

  The log shows 33 variables added to disaggregate expressions. Is Gurobi decomposing the degree-4 product into a chain of bilinear constraints during presolve, e.g.:   t1 = w_i · (Cbar_i - C_i/2) ;   t2 = t1 · U_i ;   HC_i = t2 · L_i  . Is this interpretation correct? Is there documentation on how this disaggregation works internally?

  I think the disaggregation is likely to be more similar to this:

  t1 = U_i * L_i
  t2 = w_i * t1
  t3 = Cbar_i*t2
  t4 = C_i*t2
  HC_i = t3 - 0.5*t4

  but there are multiple disaggregations possible, and it will depend on which variables are binary.

  There is no documentation on the exact details of the disaggregation.

  Does Gurobi reclassify the problem as MIQCP after disaggregating the degree-4 terms into chains of bilinear (degree-2) constraints? Is the MIQCP label referring to the presolved model rather than the original formulation?

  Yes, the log line you are referring to is relevant to the presolved model.  For example if the presolved model was convex then you would not see this line.

  GLOBAL OPTIMALITY GUARANTEE: The log reports gap 0.0000%. Given that the presolved model contains bilinear constraints (which are generally nonconvex), does the spatial branch-and-bound algorithm provide a true global optimality guarantee? Or is the gap metric only guaranteeing local optimality within the branch-and-bound tree?

  The gap reported is always a global gap.  As long as the model is well conditioned and numerical issues do not arise, then a solution produced for a 0-gap solve will be globally optimal.

  - Riley

   

  0

サインインしてコメントを残してください。