mehdi.dr...@student.uclouvain.be

unread,

Apr 9, 2014, 8:02:59 AM4/9/14

to ai...@googlegroups.com

Hello did someone know How to linearize the product of a binary variable X and a continuous variable Y ? This makes problem in my objective function

mehdi.dr...@student.uclouvain.be

unread,

Apr 9, 2014, 9:39:54 AM4/9/14

to ai...@googlegroups.com

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 both $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}$

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 - b)\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!

Sergio Bruno

unread,

Apr 9, 2014, 10:10:33 AM4/9/14

to ai...@googlegroups.com

You need McCormick envelope:

say you need x1*x2, where l1<=x1<=u1 and l2<=x2<=u2

the mccormick envelope is done by replacing the product by a new variable w (w=x1*x2) and creating constraints

w <= l2*x1 + u1*x2 - l2*u1

w <= u2*x1 + l1*x2 - u2*l1

w >= l2*x1 + l1*x2 - l1*l2

w >= u2*x1 + u1*x2 - u1*u2

some of the constraints may become redundant depending on the problem.

best,

Sergio

--
You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling System" group.
To unsubscribe from this group and stop receiving emails from it, send an email to aimms+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Reply all

Reply to author

Forward

Message has been deleted