Either-Or Constraints

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

Either: 5x_{1} + 2x_{2} 10

Or: 3x_{1} - 4x_{2} 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:

5x_{1} + 2x_{2} 10 + My

3x_{1} - 4x_{2} 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.