Monday, February 2, 2015

Flagging a Specific Variable Value

A recent question on a web forum, one I've seen asked elsewhere, was the following: in a mathematical programming model, how does one constrain a binary variable to take the value 1 if another variable takes a specific (predefined) value, and 0 otherwise? If the binary variable is $x$, the other variable is $y$, and the target value is $m$, then what we want is \begin{eqnarray*}y = m & \implies & x = 1 \\ y \neq m & \implies & x = 0.\end{eqnarray*}I hinted at the answer to this at the end of a previous post (Indicator Implies Relation), but perhaps a bit more detail is in order.

We will need $y$ to be bounded, say $L\le y \le U$. The easy case is when $y$ is integer valued, in which case $y\neq m$ means either $y \le m-1$ or $y \ge m+1$. One approach (I don't claim it's the only one) is to introduce two new binary variables, $z_1$ and $z_2$. Essentially, $z_1$ will be an indicator for $y\le m-1$, $z_2$ will be an indicator for $y \ge m+1$, and $x$ remains an indicator for $y=m$. To do this, we add the constraints \begin{eqnarray*} y & \le & (m-1)z_1 + mx + Uz_2 \\ y & \ge & Lz_1 + mx + (m+1)z_2 \\ z_1 + x + z_2 & = & 1. \end{eqnarray*} Life gets trickier if $y$ is continuous. For any given choice of values for the discrete variables, we need the projection of the feasible region onto the subspace of continuous variables to be closed, which rules out strict inequalities. In other words, we can't say $y > m$ or $y < m$ when $x = 0$. The best we can do is pick a small positive parameter $\epsilon > 0$ and treat any value of $y$ in $(m-\epsilon, m+\epsilon)$ as if it were $m$. The resulting inequalities are as above, but with $m \pm 1$ changed to $m \pm \epsilon$: \begin{eqnarray*} y & \le & (m-\epsilon)z_1 + mx + Uz_2 \\ y & \ge & Lz_1 + mx + (m+\epsilon)z_2 \\ z_1 + x + z_2 & = & 1. \end{eqnarray*}Note that this precludes $y \in (m-\epsilon, m) \cup (m, m+\epsilon)$, i.e., the only value between $m-\epsilon$ and $m+\epsilon$ that $y$ can take is $m$.

As a practical matter, you should be careful not to pick $\epsilon$ too small. It's tempting to think in terms of the smallest positive double-precision number known to your compiler, but that could result in $x = 0$ when theoretically $y = m$ but actually the computed value of $y$ contains a bit of rounding error.

No comments:

Post a Comment

Due to recent 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 Mathematics Stack Exchange.