Sunday, October 2, 2011

Integer cuts

I received a few questions about how to form constraints that exclude a known 0-1 integer solution. Assume our solution we want to exclude is called y* then we can write:

image

This can be linearized as follows:

image

The final result is also sometimes written as the following constraint:

image

Note that y is a binary decision variable.