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 , where , and are binary. There is an easy way of linearizing that equation. Add the three inequalities below
The first two inequalities ensure that will be zero if either or are zero. The last inequality will make sure that 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 , where is a continuous variable and is your binary variable.
If is bounded below by zero and above by (or any Big M), than it is pretty simple:
Note that if is zero, than the first inequality ensures that will be zero as well (note that the third inequality only states that has to be greater than a negative number). On the other hand, if is 1, the first inequality ensures that is less than our Big M, which is further tightened by our second inequality. The last inequality states then that has to be greater than or equal to , exactly as we wanted.
Finally, if is not bounded below by 0, but has bounds (with assumed to be positive due to the last inequality), then the form of the linearized inequalities are the following:
If than has to be zero as well. See how this is automatically enforced by the second inequality. Now if than has to be equal to . 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!