How does Gurobi 10.0.0 handle quadratic constraints?
Answered
I have a quadratic constraint in my model (with linear objective) and while I solve it in Gurobi, I didn't see the error message GRB_ERROR_Q_NOT_PSD. Given that, I got questions:
1. Since I didn't' see the error message, is it safe to say that the constraint is convex?
2. How does Gurobi 10.0.0 handle such constraint? Is the constraint directly linearized before actual solving? If yes, how can I see the linearized format of that constraint? If no, what algorithm is used to handle the convex quadratic constraint?
3. Is the solution guaranteed to be globally optimal? If not, where can I see the gap?
-
Since I didn't' see the error message, is it safe to say that the constraint is convex?
If you are using Gurobi version 10, you did not set the NonConvex parameter, and you did not get the GRB_ERROR_Q_NOT_PSD error, then this means that Gurobi detected that your model is convex, so yes, it is safe to say that all constraint in your model are either convex or can be linearized. Linearization comes into play only if at least one variable of each product term \(x \cdot y \) is a binary variable.
Note that with Gurobi version 11 you no longer have to set the NonConvex parameter. If you still want to get an error if your model is not recognized as convex, you have to set NonConvex=1.
2. How does Gurobi 10.0.0 handle such constraint? If no, what algorithm is used to handle the convex quadratic constraint?
For handling of (non)convex constraints and the algorithms, I recommend to have a look at our webinars
- Non-Convex Quadratic Optimization
- Graph based Approaches to Solving Binary Quadratic Programs
- Tech Talk - A Practical Tour Through Non-Convex Optimization
Is the constraint directly linearized before actual solving? If yes, how can I see the linearized format of that constraint?
Yes, the constraint is linearized before going into the B&B algorithm. It is currently not possible to see the linearized constraint.
3. Is the solution guaranteed to be globally optimal? If not, where can I see the gap?
If your model is continuous and convex, then the optimal solution is guaranteed to be optimal. There is no gap involved.
If your model has products with binary variables which Gurobi linearizes, then global optimality is guaranteed up to the set MIPGap value. The MIPGap threshold is computed in the same way as for MIPs. The same is guaranteed for a model with nonconvex terms.
Best regards,
Jaromił0 -
Hi Jaromił,
Thank you so much for the informative response! If you allow, I have 2 follow-up questions based on your answers:
1. I have two x*y terms in the quadratic constraint, one is linearizable, and the other one is not, given the requirement that at least one variable of each product term is binary.
In that case, will Gurobi still linearize the term it could (if yes, what will Gurobi do to the other term?) or Gurobi will handle the entire constraint in a different way other than linearization?
2. I see from the manuscript and one of the webinars that the piecewise-linearization approximation (adding tangent cuts outside covex objective space?) is used to handle such convex constraint. Is it the technique used to handle my constraint in Gurobi version 10?
3. As my model is MIQCP and I never set the MIPGap to other values, I assume my model is sovled to global optimality with a default gap of 1e-4?
0 -
Hi Lin,
1. I have two x*y terms in the quadratic constraint, one is linearizable, and the other one is not, given the requirement that at least one variable of each product term is binary.
In that case, will Gurobi still linearize the term it could (if yes, what will Gurobi do to the other term?) or Gurobi will handle the entire constraint in a different way other than linearization?
Gurobi will linearize the term with a binary variable in it and handle the continuous \(x \cdot y\) term via McCormick relaxation (as described in the Non-Convex Quadratic Optimization). There may be some specific structure recognized by Gurobi when this situation would be handled differently, but this is not the general case.
2. I see from the manuscript and one of the webinars that the piecewise-linearization approximation (adding tangent cuts outside covex objective space?) is used to handle such convex constraint. Is it the technique used to handle my constraint in Gurobi version 10?
Yes, this is the standard technique to deal with convex quadratic term when the whole model is determined to be nonconvex.
3. As my model is MIQCP and I never set the MIPGap to other values, I assume my model is sovled to global optimality with a default gap of 1e-4?
Correct. You should be able to see output similar to the following when your model has been solved to optimality
Best objective ..., best bound ..., gap ...%
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for the extensive answer. Please allow me for a few more questions:
Yes, this is the standard technique to deal with convex quadratic term when the whole model is determined to be nonconvex.
1. I believe my MIQCP model is convex per our previous discussion regarding no error message. Does this mean that the "piecewise-linearization approximation" is actually NOT used in solving my model?
Gurobi will linearize the term with a binary variable in it and handle the continuous
term via McCormick relaxation (as described in the Non-Convex Quadratic Optimization).2. I'm not sure whether I understand the "continous" in your answer.
I only have one quadratic constraint in my MIQCP model, within which there are two quadratic terms, let's say x1*y1 and x2*y2. The x1 and x2 are actually exactly same as a summation over a binary variable with upper limit 130. And y1 is a summation over another binary variable with upper limit 150, and y2 is again a summation over a third binary variable, but limited to 0 or 1 by other constraint.
Given that, I assume x2*y2 is linerized, while the x1*y1 is not since it does not containt an "actual" binary variable as all of them are summations, and there is no "continous" terms in either x1*y1 or x2*y2 (or anywhere in that constraint) since they are either binary or integer.
If my statements above are correct, meaning that neither "piecewise-linearization approximation" nor "McCormick relaxation" are used in solving my model, then what exactly technique is used in Gurobi ver10 to handle this quadratic constraint (especially for x1*y1) in my model?
0 -
Hi Lin,
1. I believe my MIQCP model is convex per our previous discussion regarding no error message. Does this mean that the "piecewise-linearization approximation" is actually NOT used in solving my model?
You are correct, since you did not set the NonConvex parameter and you do not get an error message with Gurobi v10, your model is determined to be convex and/or can be reformulated as a MILP.
2. I'm not sure whether I understand the "continous" in your answer.
I was referring to a bilinear product \(x \cdot y\), where both variables are continuous.
If my statements above are correct, meaning that neither "piecewise-linearization approximation" nor "McCormick relaxation" are used in solving my model, then what exactly technique is used in Gurobi ver10 to handle this quadratic constraint (especially for x1*y1) in my model?
If I understand you correctly your quadratic term contains products of which at least one variable is binary, is this correct? If not, could you please explicitly state the product terms together with variable bounds and types in your model?
If you have products in your quadratic expression, which contain at least one binary variable, then Gurobi can try to convexify the quadratic expression by adding squares of binary variables to the expression. In general, this would mean that Gurobi can do the transformation, where it exploits that for a binary variable \(b\) it holds that \(b^2 = b\)\[\begin{align*}
x^T Q x = x^T Q x + x^T D x - d^T x = x^T (Q + D) x - d^T x
\end{align*}\]In the above \(Q + D\) would be a PSD matrix and the resulting quadratic expression convex. In this case, Gurobi would not linearize the products. Instead, when solving the LP relaxation, it would relax the discrete variables to continuous variables and solve the convex quadratic continuous relaxation. This can be sometimes faster than linearization.
You can find more details in the webinar on Models with Product of Binary Variables starting at around the 2 min mark.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks again for the answer!
So here is the quadratic constraint in my model (with a linear objective):
where A is the linear terms in that constraint, Cij is a known parameter that is either 0 or 1, and M is a big number. The upper limits for summation of zij over j is limited to 1 by other constraint (so this could be the binary variable in the term), and for other summations are as >100. Given that,
If you have products in your quadratic expression, which contain at least one binary variable, then Gurobi can try to convexify the quadratic expression by adding squares of binary variables to the expression.
I'm still unsure about whether the first quadratic term with xij and yj satisfies this. I assume not, though both xij and yj are binary, with the summation over them and an upper bound for the summations > 100, that basically becomes the product of two integer variables, is that correct?
I'm actually looking for a statement I could use for my model, like "In Gurobi, this quadratic constraint is not linearized, but directly solved through a " xxx technique" to a global optimality with gap of 1e-4". Currently I'm just still not sure about the name of the technique, assuming the piecewise-linearization approximation or McCormick relaxation are not the ones used in solving my model.
If my statement above is correct, could you please help to identify the exact name of the technique, and if possible, a reference I could use?
Thanks again!
0 -
Hi Lin,
Thank you for sharing the formulation of the quadratic constraint.
In this case, the formulation used by Gurobi depends on how you formulate and implement your model.
I see 3 possible cases for your constraint.
1. You can intuitively implement the multiplication of the sums
... + gp.quicksum(x) * gp.quicksum(y) - gp.quicksum(x) * gp.quicksum(z) ...
In this case, Gurobi would expand the multiplications, i.e., it would formulate
\[\begin{align*}
\sum_i x_i \cdot \sum_j y_j
\end{align*}\]as
\[\begin{align*}
\sum_{i,j} x_i \cdot y_j
\end{align*}\]Here, Gurobi would linearize each product term and solve the resulting MILP model. This is the recommended way of formulating such constraints. This technique is called the "Standard Linearization". Two references can be found at ~3:46 of the Binary Quadratic Programming Webinar.
2. You could introduce an auxiliary discrete variable for the sum of \(x\) variables
aux = m.addVar(vtype=GRB.INTEGER, name="aux")
m.addConstr(aux == gp.quicksum(x))
... + aux * gp.quicksum(y) - aux * gp.quicksum(z) ...Here Gurobi would again expand the products to get
\[\begin{align*}
\sum_j aux \cdot y_j
\end{align*}\]In this case, Gurobi would again linearize the products, because one of the variables is always a binary. This formulation might be better suited, if you have some additional information about the bounds of the discrete auxiliary variable.
3. You could introduce a discrete auxiliary variable for every sum
auxx = m.addVar(vtype=GRB.INTEGER, name="auxx")
auxy = m.addVar(vtype=GRB.INTEGER, name="auxy")
auxz = m.addVar(vtype=GRB.INTEGER, name="auxz")
m.addConstr(auxx == gp.quicksum(x))
m.addConstr(auxy == gp.quicksum(y))
m.addConstr(auxz == gp.quicksum(z))
... + auxx * auxy - auxx * auxz ...In this case, Gurobi would not linearize the products and would use the spatial B&B algorithm to solve the model. One would have to set the parameter NonConvex=2 for Gurobi v10, because the model is recognized as non-convex. This formulation might be useful, when you have additional information about bounds of the auxiliary variables.
Best regards,
Jaromił0 -
Does the setting of Gurobi parameter PreQLinearize make any difference in this situation?
0 -
Does the setting of Gurobi parameter PreQLinearize make any difference in this situation?
Yes, the PreQLinearize parameter may affect the linearized formulation. My colleague Ed Klotz explains the setting PreQLinearize=1 in detail at ~6:33 of the Binary Products Webinar. The setting PreQLinearize=2 is explained starting at 10:26 of this webinar (you can also skip the details and jump directly to the formula at 16:29 of the webinar). The setting PreQLinearize=-1 tries to guess which of the two technique would produce the best formulation for the given model's performance.
Best regards,
Jaromił0 -
Hi Jaromił,
I believe I implemented my model as you described in the first case, and all my questions are resolved! Thank you so much for all the help!
Best regards,
Lin
0
Please sign in to leave a comment.
Comments
10 comments