Linearization of the product of two variables

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!