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$.

## No comments:

## Post a Comment

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.