• Gurobi Staff

Hi Martina,

For nonconvex models, Gurobi introduces a bilinear constraint for every unique bilinear product of two variables. For example

\begin{align*} x_1 \cdot x_2 + x_3 \cdot x_4 + x_5 \cdot x_6 = 0 \end{align*}

is reformulated as

\begin{align*} z_{12} + z_{34} + z_{56} &= 0\\ z_{12} &= x_1 \cdot x_2\\ z_{34} &= x_3 \cdot x_4\\ z_{56} &= x_5 \cdot x_6 \end{align*}

Thus, the original constraint is now a linear one and we introduced 3 bilinear constraints. There is no way to avoid this reformulation in Gurobi. Please note that this reformulation is standard in current state-of-the-art and is performed by almost any nonconvex global optimization solver under the hood.

If your model is convex, then Gurobi works with the original convex constraints and does not introduce auxiliary bilinear constrains.

I hope this clarifies your situation.

Best regards,
Jaromił

Hi Jaromił,

If it is possible, I would like to ask you also another question related to the model: the log file shows "Continuous model is non-convex – solving as a MIP"

I followed your video A Practical Tour Through Non-convex Optimization but I didn't totally understand why the continuous problem becomes mixed-integer with the application of the Spatial Branch and Bound. Indeed, the application of the McCormick relaxation should not require binaries (just the introduction of new continuous variables z as in your example). Are the binaries used in splitting the domain of the variables of the nonconvex terms? What is the meaning of the optimality gap?

Best Regards,

Martina

• Gurobi Staff

Hi Martina,

If it is possible, I would like to ask you also another question related to the model: the log file shows "Continuous model is non-convex – solving as a MIP"

The message does not mean that a continuous non-convex model is reformulated as a MIP. The message indicates that Gurobi will use the spatial B&B algorithm where Gurobi will branch on continuous variables present in nonlinear terms just as if they would be integer variables in a traditional B&B algorithm. Thus, the "solving as a MIP" message does not refer to a reformulation but rather to the algorithm type used (spatial B&B in this case) where continuous variables are treated just as integer variables in a MIP algorithm.

Best regards,
Jaromił

Hi Jaromił,

Thank you.

Since the model is not reformulated in a mixed integer model, I still do not understand the meaning of the (optimality) gap that I see when I solve my model. Could you help me with this?

Best regards,

Martina

• Gurobi Staff

Hi Martina,

Similar to a traditional integer B&B algorithm, Gurobi computes a best bound when solving nonconvex models. The difference in a spatial B&B algorithm is that the relaxation of a nonconvex model does not only involve relaxing integer conditions but also constructing valid relaxations for all bilinear terms, e.g., the McCormick envelopes. The difference between the best bound proven so far and the best feasible point found so far is then given by the optimality gap.

Best regards,
Jaromił