24
$\begingroup$

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

$\endgroup$
  • 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 Broek May 31 at 6:16
  • 1
    $\begingroup$ That's definitely the way to go. Especially while in beta. $\endgroup$ – ayhan May 31 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 at 21:08
  • 1
    $\begingroup$ @prubin edited :) $\endgroup$ – Michiel uit het Broek Jun 6 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 Trick Jun 6 at 3:04
27
$\begingroup$

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:

  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.
$\endgroup$
  • $\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$ – Edward Lam May 31 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$ – 4er Jun 2 at 23:16
  • 2
    $\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$ – 4er Jun 2 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$ – Michiel uit het Broek Jun 5 at 8:52
  • $\begingroup$ It's OK. Please go ahead and add them. $\endgroup$ – 4er Jun 6 at 22:25
10
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.