Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
-
5$\begingroup$ To generate more expected content for our new OR forum and since it is allowed to answers your own questions: I added this basic OR questions. see: stackoverflow.blog/2011/07/01/… $\endgroup$– Michiel uit het BroekMay 31, 2019 at 6:16
-
1$\begingroup$ That's definitely the way to go. Especially while in beta. $\endgroup$– ayhanMay 31, 2019 at 6:52
-
$\begingroup$ I'd suggest an edit of the question. You actually answered the more general question how to linearize $x\cdot y$. The constraint $x\cdot y \le b$ can be eliminated in presolve: if $0\le b < 1$ then it implies $x=0=y$, and if $b\ge 1$ it does not constrain the binary variables $x$ and $y$ at all. $\endgroup$– prubin ♦Jun 5, 2019 at 21:08
-
1$\begingroup$ @prubin edited :) $\endgroup$– Michiel uit het BroekJun 6, 2019 at 2:19
-
2$\begingroup$ My guess is that within a year this will be the most valuable Q/A! We'll have to make it obvious to new users. $\endgroup$– Michael TrickJun 6, 2019 at 3:04
2 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*}