Linearizing product of two integer variables
AnsweredHi,
I am wondering if it is possible to linearize a constraint of the form Z * Z = Y where Y and Z are integer variables.
I have read that it is possible to somehow convert these integer variables into binary representations to make this product linear however I am unsure how to do this in Gurobi.
-
-
Gurobi Staff
Hi Harrison,
There are a few ways I can think of to encode an integer variable with binary variables, each requiring the variable to have a lower and upper bound. By way of example let's assume \(Z\) is an integer variable with lb = 3 and ub = 5.
The first approach requires a binary variable for each possible value of \(Z\), and a cardinality constraint to restrict exactly one binary variable to have a value of 1, i.e.
\[\begin{eqnarray}Z = 3z_1 + 4z_2 + 5z_3\\ z_1 + z_2 + z_3 = 1\end{eqnarray}\]
The second approach uses a base 2 encoding using binary variables, and possibly a constraint to enforce the upper bound
\[\begin{eqnarray}Z = 3 + z_1 + 2z_2 \\ 3 + z_1 + 2z_2 \leq 5\end{eqnarray}\]
Which approach is best may be dependent on the range of the variable. Best way to make a choice is to try both and see what works best in practice for your model.
Let's say we take the first approach, we can replace \(Z^2\) with
\[\begin{eqnarray}Z^2 & = & (3z_1 + 4z_2 + 5z_3)(3z_1 + 4z_2 + 5z_3) \\
& = & 9z^2_1 + 16z^2_2 + 25z^2_3 + 24z_1z_2 + 30z_1z_3 + 40z_2z_3 \\
& = & 9z_1 + 16z_2 + 25z_3 + 24z_1z_2 + 30z_1z_3 + 40z_2z_3 \end{eqnarray}\]Then we can replace terms of the form \(z_iz_j\) by introducing a binary variable \(\bar{z}_{ij}\) and the following constraints
\[\begin{eqnarray}\bar{z}_{ij} & \leq & z_i \\ \bar{z}_{ij} & \leq & z_j \\ \bar{z}_{ij} & \geq & z_i + z_j - 1\end{eqnarray}\]
The linearization with the base 2 approach is similar. A couple of notes:
- When attempting to linearize, or working with non-linear constraints, having the tightest possible bounds on variables is important
- Our solver (9.0+) can accept constraints of the form Y = Z*Z, and may work better than the linearization approaches suggested above
- You may enjoy our Models with Products of Binary Variables Webinar Video
As an aside, if memory serves me correct you are a new starter at one of our Australian partners (congrats!). You are eligible to submit questions direct to us on the support team if they're related to your work there, to receive a faster response.
- Riley
0 -
-
Thankyou so much for your response Riley! This was very informative. Also thankyou for letting me know about the support team, this question was unrelated to work but I will keep that in mind.
- Harrison
0 -
-
-
Hi Harrison,
No problem. On reflection it occurred to me that since in the example I provided we have \(z_1 + z_2 + z_3 = 1\) then for any valid solution \(z_1z_2 = z_1z_3 = z_2z_3 = 0\) so when using the first approach the case for \(Z^2\) is quite straightforward.
The linearizations I provided would be more relevant if say the example was \(XZ\) for \(X,Z\) integer.- Riley
0 -
Please sign in to leave a comment.
Comments
3 comments