Nonconvex=2 and Presolve
Answered
Hi,
I have a problem that contains 9 bilinear constraints: each constraint has a product of 2 continuous variables. Note that the problem has only continuous variables.
I modeled the problem in GAMS as QCP, adding the Gurobi Option nonConvex=2. Therefore, the original bilinear constraints are treated as quadratic constraints (9 quadratic constraints) but then the log file shows "Presolved model has 216 bilinear constraints"
Is there a way to avoid the translation of quadratic constraints into bilinear constraints? In other words, how to ensure that the resolution considers just the original 9 bilinear constraints and not the translation (216 constraints)? I tried to disable the Presolve phase (Presolve=0) but I am not sure it is the best way to do that.
Thank you in advance
-
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ł0 -
Hi Jaromił,
Thank you for your very clear answer.
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
0 -
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ł0 -
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
0 -
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ł0
Please sign in to leave a comment.
Comments
5 comments