Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
3 Answers
This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, thus $x = 0$ and/or $y = 0$ implies that $z$ must equal zero.
$$z \leq x\\z \leq y$$
The only thing left is to force $z$ to equal one if the product of $x$ and $y$ equals one, which only happens if both of them equal one.
$$ z \geq x + y - 1. $$
The general case with $n$ binary variables
This method can also directly be applied to the general case where we have the product of multiple binary variables. Suppose we have $n$ binary variables $x_i$ and we want to linearize the product $$ \prod_{i=1}^n x_i. $$ Then you can introduce a new binary variable $z$ that represents the value of this product and model it by introducing the following constraints $$ \begin{align} z &\leq x_i \quad \text{ for } i = 1, \ldots, n.\\ z &\geq \sum_{i=1}^n x_i - (n-1). \end{align} $$
Further reading
As mentioned by 4er in a comment below this answer: "for quadratic functions of many binary variables, you can often do better than to linearize each product of variables separately". Some suggested references are:
- F. Glover and E. Woolsey (1973). Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Operations Research 21 156-161.
- F. Glover (1975). Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science 22 455-460.
- M. Oral and O. Kettani (1992). A linearization procedure for quadratic and cubic mixed-integer problems. Operations Research 40 S109-S116.
- W.P. Adams and R.J. Forrester (2005). A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters 33 55-61.
-
$\begingroup$ And in the general case, look at the McCormick relaxation. If someone is at CPAIOR next week, please write here anything of interest in Toby’s talk. $\endgroup$ May 31, 2019 at 13:33
-
$\begingroup$ If you have a quadratic function of many binary variables, then you can often do better than to linearize each product of variables separately. I'll give some references in the next comment. $\endgroup$– 4erJun 2, 2019 at 23:16
-
3$\begingroup$ [1] F Glover and E Woolsey, Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Operations Research 21 (1973) 156-161. [2] Glover, F. Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science 22 (1975) 455-460. [3] M Oral and O Kettani, A linearization procedure for quadratic and cubic mixed-integer problems. Operations Research 40 (1992) S109-S116. [4] WP Adams and RJ Forrester, A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters 33 (2005) 55-61. $\endgroup$– 4erJun 2, 2019 at 23:16
-
$\begingroup$ @4er is it oke if I add your paper suggestions to my answer such that they are better visible? Of course you will be mentioned :) $\endgroup$ Jun 5, 2019 at 8:52
-
It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form: \begin{align*} & z \iff x \wedge y \\ & \left(z \implies (x \wedge y)\right) \bigwedge \left((x \wedge y) \implies z\right) \\ & \left(\neg z \vee (x \wedge y)\right) \bigwedge \left(\neg(x \wedge y) \vee z\right) \\ & \left((\neg z \vee x) \wedge (\neg z \vee y)\right) \bigwedge \left((\neg x \vee \neg y) \vee z\right) \\ & (\neg z \vee x) \bigwedge (\neg z \vee y) \bigwedge (\neg x \vee \neg y \vee z) \\ & \left((1 - z) + x \ge 1\right) \bigwedge \left((1 - z) + y \ge 1\right) \bigwedge \left((1 - x) + (1 - y) + z \ge 1\right) \\ & (x \ge z) \bigwedge (y \ge z) \bigwedge (z \ge x + y - 1) \end{align*}
-
$\begingroup$ Do you know the reason for all constraint obtained from the conjunctive normal form result in disaggregated family of constraints? $\endgroup$ Jul 28, 2022 at 13:41
-
1$\begingroup$ @AlexandreFrias I guess you could say it is a consequence of DeMorgan's law: $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$. $\endgroup$– RobPrattJul 28, 2022 at 13:49
As the first answer:
$$ \begin{align} z &\leq x_i \quad \forall i = 1, \ldots, n.\\ z &\geq \sum_{i=1}^n x_i - (n-1). \end{align} $$
We should note that, the property holds for an aggregated version of these constraints (obtained from the sum of the $z \leq x_i \quad \forall i = 1, \ldots, n$.
$$ \begin{align} n.z & \leq \sum_{i=1}^{n} x_i \\ z & \geq \sum_{i=1}^n x_i -(n-1) \end{align} $$
I prefer to use less constraints.
-
3$\begingroup$ The aggregated version is correct but weaker. It is worth trying both ways. $\endgroup$– RobPrattJul 28, 2022 at 13:47
-
$\begingroup$ When I use aggregated constraints in Facility Location Problem, ($\sum_{j=1}^{m} x_{ij} \leq m.y_j $) in place of ($x_{ij}\leq y_j$), the running time is faster, almost ever. I think simplex algorithm works better using less constraints due to the number of vertex in the polytope. $\endgroup$ Jul 28, 2022 at 16:49
-
$\begingroup$ Yes, and cut generation probably finds the disaggregated constraints as needed. It depends on the problem and instance, and so it is worth trying both ways. $\endgroup$– RobPrattJul 28, 2022 at 17:29