# How to linearize the product of two binary variables?

Suppose we have two binary variables $$x$$ and $$y$$. How can we linearize the product $$xy$$?

• 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/… May 31, 2019 at 6:16
• That's definitely the way to go. Especially while in beta. May 31, 2019 at 6:52
• 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.
– prubin
Jun 5, 2019 at 21:08
• @prubin edited :) Jun 6, 2019 at 2:19
• 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. Jun 6, 2019 at 3:04

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}

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:

1. 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.
2. F. Glover (1975). Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science 22 455-460.
3. M. Oral and O. Kettani (1992). A linearization procedure for quadratic and cubic mixed-integer problems. Operations Research 40 S109-S116.
4. W.P. Adams and R.J. Forrester (2005). A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters 33 55-61.
• 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. May 31, 2019 at 13:33
• 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.
– 4er
Jun 2, 2019 at 23:16
•  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.  Glover, F. Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science 22 (1975) 455-460.  M Oral and O Kettani, A linearization procedure for quadratic and cubic mixed-integer problems. Operations Research 40 (1992) S109-S116.  WP Adams and RJ Forrester, A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters 33 (2005) 55-61.
– 4er
Jun 2, 2019 at 23:16
• @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 :) Jun 5, 2019 at 8:52
– 4er
Jun 6, 2019 at 22:25

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*}

• Do you know the reason for all constraint obtained from the conjunctive normal form result in disaggregated family of constraints? Jul 28, 2022 at 13:41
• @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)$. Jul 28, 2022 at 13:49

\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}
• 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. Jul 28, 2022 at 16:49