Either-Or Constraints

Sometimes, in a decision situation, either one or another constraint must hold, but not both. For example:

Either: 5x1 + 2x2 10

Or: 3x1 - 4x2 24

But not both

We can handle this in integer programming with the use of a zero/one y variable by using both of the following modified constraints:

5x1 + 2x2 10 + My

3x1 - 4x2 24 + M(1-y)

When y = 0, the first constraint is binding, but the right-hand side of the second becomes very large and hence is not binding. And conversely, when y = 1, the second constraint binds but the first does not because My is very large.