## Wednesday, May 2, 2012

### Indicator Implies Relation

This is a follow-up to an earlier post on logical indicators in mathematical programming models. A common occurrence is to use a binary variable $y$ to turn a relation constraint (involving variables $x$) on or off.  Let $\sim$ denote any of the relations $=,\le,\ge$.  Without loss of generality, by moving all terms to the left side, we can write a generic relation involving $x$ as $f(x)\sim 0$ where $f()$ is an arbitrary function (linear if your model is to be a mixed integer linear program). To proceed, we will need to know a priori upper and lower bounds ($U$ and $L$ respectively) for $f(x)$, so that $L\le f(x) \le U \quad \forall x.$ Note that, in general, $L < 0 < U$ will hold, although we require neither $L < 0$ nor $0 < U$. If $L \ge 0$, then $f(x)\ge 0$ is automatic and needs no constraint.  Similarly $U \le 0$ guarantees $f(x) \le 0$ without additional constraints.

Let's start with the case where we want to say that $y=1 \implies f(x)\sim 0.$ If $\sim$ is $\ge$, we accomplish this with $f(x) \ge L(1-y)\qquad (1).$ Similarly, if $\sim$ is $\le$, we use $f(x) \le U(1-y)\qquad (2).$ For the case where $\sim$ is $=$, we combine (1) and (2).

I have excluded the case where $\sim$ is $>$ or $<$ because strict inequalities are anathema to mathematical programs: they cause the feasible region not to be closed.   That ties in to the next scenario: what if  $y = 1 \Leftrightarrow f(x)\sim 0$is the relation we want (i.e., we want equivalence rather then implication)? This can be broken down into two implications: \begin{eqnarray*}y=1 & \implies & f(x)\sim0\\ y=0 & \implies & f(x)\nsim0.\end{eqnarray*}
The difficulty is that $\nsim$ is either $>$, $>$ or $\neq$, all of which cause the feasible region not to be closed. So we will have to compromise. For the case where $\sim$ is $\ge$, combine (1) with $f(x)\le Uy.$With that combination, $y=1\implies f(x)\ge 0$ and $y=0\implies f(x)\le 0$, leaving the possibility that $f(x)=0$ for either value of $y$. Similarly, if $\sim$ is $\le$, combine (2) with $f(x)\ge Ly,$ so that $y=1\implies f(x)\le 0$ and $y=0\implies f(x)\ge 0$, again with ambiguity if $f(x)=0$. Sadly, there is no way to impose $y=1\Leftrightarrow f(x)=0$ when $f(x)$ takes values in a continuum.

As a parting note, $y=1\Leftrightarrow f(x)\sim 0$ can be modeled accurately for any relation (including equality and strict inequality) if $f(x)$ is known to be integer-valued.  In that case, $f(x) \gt 0$ equates to $f(x)\ge 1$, $f(x) \lt 0$ equates to $f(x)\le -1$, and $f(x)\neq 0$ is the disjunction of the two previous cases.