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.

6 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. you state in the parting note that if f(x) is known to be integer-valued then f(x)>0 equates to f(x)>=1, f(x)<0 equates to f(x)<=-1, and f(x)<>0 is the disjunction of them. So:
    a) when you state that "f(x)>0 equates to f(x)>=1" you mean that one should combine f(x)-1>=L(1-y) with f(x)-1<=Uy ?
    b) when you state that "f(x)<>0 is the disjunction of the two previous cases" you mean that one must add an extra binary variable in order to model the condition that either the former or the latter case is true (but not both) ?

    ReplyDelete
  3. a) Not exactly. If you are trying to model $y=1$ if and only if $f(x)\gt 0$, then you want $f(x)\le 0$, not $f(x)\le 1$, when $y=0$. Also, you need to remember that $L$ and $U$ are the bounds for $f$, not $f-1$, and adjust accordingly.

    b) Yes, you need two binary variables to distinguish among three cases ($f$ positive, zero or negative).

    ReplyDelete
  4. Hello,
    i have a decision variable Zik equal to 1 if a given parameter Tk is in [sik,sjk] were sik and sjk are decision variable please how model that,thank for advance for the reply

    ReplyDelete
  5. What you wrote looks incorrect. Z is subscripted by i and k but not j, so the condition T_k in [S_ik, S_jk] is tested for what value(s) of j?

    ReplyDelete

Due to intermittent spamming, comments are being moderated. 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 Operations Research Stack Exchange.