37
$\begingroup$

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

$\endgroup$
1

3 Answers 3

55
$\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$
7
  • $\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, 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$
    – 4er
    Jun 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$
    – 4er
    Jun 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
  • $\begingroup$ It's OK. Please go ahead and add them. $\endgroup$
    – 4er
    Jun 6, 2019 at 22:25
24
$\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$
2
  • $\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$
    – RobPratt
    Jul 28, 2022 at 13:49
3
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ The aggregated version is correct but weaker. It is worth trying both ways. $\endgroup$
    – RobPratt
    Jul 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$
    – RobPratt
    Jul 28, 2022 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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