Often when writing a model, the most straightforward way of writing a constraint is by multiplying two variables. Then, in order to solve the model we need to linearize it. There comes the problem, as I always have problems reminding how to linearize a product of variables.

Linearizing the product of two binary variables

Suppose your model has the product $z = x \times y$ , where $z$ , $x$ and $y$ are binary. There is an easy way of linearizing that equation. Add the three inequalities below

$z \leq x$

$z \leq y$

$z \geq x + y - 1$

The first two inequalities ensure that $z$ will be zero if either $x$ or $y$ are zero. The last inequality will make sure that $z$ will take value 1 if both binary variables are set to 1.

Linearizing the product of a binary and a continuous variable

Now suppose your expression is $z = A \times x$ , where $A$ is a continuous variable and $x$ is your binary variable.

If $A$ is bounded below by zero and above by $\bar{A}$ (or any Big M), than it is pretty simple:

$z \leq \bar{A} \times x$

$z \leq A$

$z \geq A - (1 - x)\bar{A}$

$z \geq 0$

Note that if $x$ is zero, than the first inequality ensures that $z$ will be zero as well (note that the third inequality only states that $z$ has to be greater than a negative number). On the other hand, if $x$ is 1, the first inequality ensures that $z$ is less than our Big M, which is further tightened by our second inequality. The last inequality states then that $z$ has to be greater than or equal to $A$ , exactly as we wanted.

Finally, if $A$ is not bounded below by 0, but has bounds $[\b{A}, \bar{A}]$ (with $\bar{A}$ assumed to be positive due to the last inequality), then the form of the linearized inequalities are the following:

$min\{0, \b{A}\} \leq z \leq \bar{A}$

$\b{A} x \leq z \leq \bar{A} x$

$A - (1 - x)\bar{A} \leq z \leq A - (1 - x)\b{A}$

$z \leq A + (1 - x)\bar{A}$

If $x = 0$ than $z$ has to be zero as well. See how this is automatically enforced by the second inequality. Now if $x = 1$ than $z$ has to be equal to $A$ . See how this is also enforced by the third inequality. The others are there to ensure everything work and I leave their interpretation for you.

Enjoy it!

(thanks, Arindam!)

This was useful? Buy me a cup of coffee to help me keep this website running!

Linearization of the product of two variables

Linearizing the product of two binary variables

Linearizing the product of a binary and a continuous variable

Related

Published by

Leandro Coelho

Linearizing the product of two binary variables

Linearizing the product of a binary and a continuous variable

Share this:

Related

Published by

Leandro Coelho