Inclusive Or in Mathematical Programs

This is a FAQ in various optimization/mathematical programming forums, so it's worth putting the answer someplace to which I can point. How do you model a constraint of the form "either A or B must hold"?

The first thing to observe is that the conditions A and B must, like any other constraints, be expressed as equalities or weak inequalities; strong inequalities are to be avoided because they make the feasible region an open set. In what follows we'll assume that A and B are expressed respectively as $a \le b$ and $c \le d$, where $a,\ldots,d$ are expressions involving model variables. We'll also assume that what is intended is an inclusive or, meaning it is acceptable that both conditions are satisfied simultaneously.

To model the disjunction, we will need two positive constants $M_1$ and $M_2$ such that we are absolutely certain that $a \le b + M_1$ and $c \le d + M_2$ in the optimal solution (or in at least one optimal solution). Choosing $M_1$ or $M_2$ too small can make the optimal solution infeasible, which would be a serious error. Choosing $M_1$ or $M_2$ unnecessarily large can slow down the progress of the solver (by making bounds looser than is necessary); that can be annoying, but it's not fatal. So one typically errs on side of making $M_1$ and $M_2$ if anything too large, but it pays not to go overboard with them.


We will also need two new binary variables, $z_1$ and $z_2$. We add the following three constraints: $$\begin{array}{cccc} a & \le & b + M_1*\left(1 - z_1\right) & (1) \\ c & \le & d + M_1*\left(1 - z_2\right) & (2)\\ z_1 + z_2 & \ge & 1 & (3) \end{array}.$$ Constraint (1) enforces $z_1 = 1 \Longrightarrow a > b$, and similarly constraint (2) enforces $z_2 = 1 \Longrightarrow c > d$. Finally, constraint (3) forces at least one of $z_1$ and $z_2$ to be 1, which in turn forces at least one of the original inequalities to hold.

Imposing an exclusive or (requiring exactly one of the inequalities to hold) is considerably trickier. The easy part is converting (3) to an equation: $z_1 + z_2 = 1$. The hard part is converting (1) and (2) so that $z_1 = 1$ if and only if $a \le b$, and similarly for $z_2$. This requires that $z_1 = 0 \Longrightarrow a > b$; but enforcing a strict inequality is not possible. The one exception is that if $a$ and $b$ are integer valued, then $a>b$ equates to $a\geb+1$, which can be handled. For continuous expressions, though, the best workaround may be to introduce a small positive constant $\epsilon>0$ and enforce $z_1=0 \Longrightarrow a \ge b + \epsilon$, which has the unfortunate effect of cutting off any (possibly optimal) solution where $b<a<b+\epsilon$.