Error: Malformed quadratic term in expression
Answered
Dear Gurobi community,
I recently started using GUROBI for solving MIP problems. As an exercise, I was trying to solve the following problem, having linear objective function and quadratic term in constraint. But it keeps saying 'Malformed quadratic term in expression'. The error message specifies that the problem is in constraint 'a22' and 'a23'. Can you please help me ?
Maximize TOT
subject to
A1 : 5 X11 + 5 X12 + 5 X13 + 12 X21 + 13 X22 + 23 X23 + 7 X31 + 5 X32 + 12 X33 + 12 X41 + 13 X42 + 9 X43 - P1 = 0
A2 : 9 X11 + 6 X12 + 7 X13 + 13 X21 + 14 X22 + 24 X23 + 8 X31 + 7 X32 + 14 X33 + 16 X41 + 21 X42 + 10 X43 - P2 = 0
A3 : 5 X11 + 5 X12 + 5 X13 + 12 X21 + 13 X22 + 23 X23 + 7 X31 + 5 X32 + 12 X33 + 12 X41 + 13 X42 + 9 X43 - P3 = 0
A4 : 9 X11 + 6 X12 + 7 X13 + 13 X21 + 14 X22 + 24 X23 + 8 X31 + 7 X32 + 14 X33 + 16 X41 + 21 X42 + 10 X43 - P4 = 0
a5 : 5 X11 + 5 X12 + 5 X13 + 12 X21 + 13 X22 + 23 X23 + 7 X31 + 5 X32 + 12 X33 + 12 X41 + 13 X42 + 9 X43 - P5 = 0
a6 : 9 X11 + 6 X12 + 7 X13 + 13 X21 + 14 X22 + 24 X23 + 8 X31 + 7 X32 + 14 X33 + 16 X41 + 21 X42 + 10 X43 - P6 = 0
a7 : 5 X11 + 5 X12 + 5 X13 + 12 X21 + 13 X22 + 23 X23 + 7 X31 + 5 X32 + 12 X33 + 12 X41 + 13 X42 + 9 X43 - P7 = 0
a8 : 9 X11 + 6 X12 + 7 X13 + 13 X21 + 14 X22 + 24 X23 + 8 X31 + 7 X32 + 14 X33 + 16 X41 + 21 X42 + 10 X43 - P8 = 0
a13 : P1 + P2 + P3 + P4 + P5 + P6 + P8 - TOT = 0
a14 : X11 + X12 + X13 = 1
a15 : X21 + X22 + X23 = 1
a16 : X31 + X32 + X33 = 1
a17 : X41 + X42 + X43 = 1
a18 : X11 + X12 - Y1 = 0
a19 : X21 + X22 + X23 - Y2 = 0
a20 : X31 + X33 - Y3 = 0
a21 : X41 + X42 - Y4 = 0
a22 : [ Y1 * Y3 * Y4 ] <= 0
a23 : [ Y2 * Y4 ] <= 0
BINARY
X11 X12 X13 X21 X22 X23 X31 X32 X33 X41 X42 X43 Y1 Y2 Y3 Y4
End
-
Hi Dagm,
The error is coming from constraint 'a22' in your example, as it contains a product of three variables.
Modelling multilinear terms directly is not supported in Gurobi at present. However, as explained in our Knowledge Base article "How do I model multilinear terms in Gurobi?", you can reformulate them into bilinear and quadratic terms.
For your specific case, you can create a new variable Z and substitute constraint a22 with the following constraints in your LP file:
c1 : Z - [ Y1 * Y3 ] = 0
c2 : [ Z * Y4 ] <= 0Regards,
Simran
0 -
Hello Simran,
Thank you so much for the suggestion. I corrected it accordingly and it works well. The challenge now is I have almost one million equations of that type and most of which have more than four variables in the term. E.g:
Y1P_1: [ Y740_1 * Y6_1 * Y264_1 * Y265_1 * Y719_1 ] <= 0
Y2P_1: [ Y514_1 * Y690_1 * Y691_1 * Y515_1 * Y284_1 * Y286_1 * Y111_1 ] <= 0
Y3P_1: [ Y576_1 * Y578_1 * Y579_1 * Y42_1 * Y170_1 * Y597_1 * Y598_1 * Y572_1 * Y253_1 ] <= 0
Y4P_1: [ Y33_1 * Y516_1 * Y294_1 * Y395_1 * Y722_1 * Y595_1 * Y634_1 * Y509_1 ] <= 0
Y5P_1: [ Y518_1 * Y520_1 * Y396_1 * Y654_1 * Y15_1 * Y722_1 * Y595_1 * Y632_1 * Y634_1 * Y507_1 * Y509_1 ] <= 0
Y6P_1: [ Y515_1 * Y292_1 * Y725_1 * Y759_1 * Y699_1 * Y687_1 ] <= 0
[I am working on spatial optimization, and the original MIP problem can not be solved (as it is very large, with 90 thousand vars and one million constraints). So, I am exploring other 'exact' approaches, including this one].
So, do you have any suggestion?
Thanks again0 -
Hi Dagm,
In general, to model a product of n variables, you will need to add (n-1) auxiliary variables and constraints as described in How do I model multilinear terms in Gurobi?
However, from your original post, it seems all "Y" variables in your model are binary. In this case, the constraint
Y_1 * Y_2 * Y_3 *....* Y_n = 0
is equivalent to saying that at least one of the Y variables in the product must be zero, which is equivalent to saying that at most (n-1) of the Y variables in the product can be 1. So, we can model this constraint via the simple linear constraint
Y_1 + Y_2 + Y_3 + .. + Y_n <= n-1
I hope this helps!
Regards,
Simran
0 -
Dear Simran,
Thank you very much.
The constraint in my original MIP problem was actually formulated with linear equations similar to what you are suggesting me now (Y_1 + Y_2 + Y_3 + .. + Y_n <= n-1). The idea now is (as the original MIP problem couldn't be solved) to change the linear equations to quadratic and add a Lagrange penalization term to each constraint and include them in the objective function. So, changing the linear constraint into a quadratic one (that I am doing currently) is the first task.
That is my proposal, any different suggestions are very welcome, please.
I thank you again0 -
Hi Dagm,
Assuming the rest of your model is linear, adding the constraints Y_1 + Y_2 + Y_3 + .. + Y_n <= n-1 and keeping the model linear should work better than making the model non-linear by adding the multilinear terms.
I am not sure by what you mean by the "original MIP problem couldn't be solved". Did you try using non-default values of Gurobi parameters? Our Parameter tuning tool can help you find parameter settings that improve the solver's performance for your model. You can also refer to our webinar on using the parameter tuning tool for more details.
To answer your question on modelling the product of binary variables - I did find out that the product of binary variables can also be modelled using Model.addGenConstrAnd(). You can read more about how to model logical constraints in our Knowledge Base article "How do I model logical and general expressions?"
-Simran
0
Please sign in to leave a comment.
Comments
5 comments