Flagging a Specific Variable Value

Written by: Paul Rubin

Primary Source: OR in an OB World

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

\(y = m \implies x = 1\)

\(y \neq m \implies x = 0\)

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

\(y \le (m – 1)z_1 +mx + Uz_2\)

\(y \ge Lz_1 + mx + (m +1)z_2\)

\(z_1 + x + z_2 = 1\)

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\):

\(y \le (m – \epsilon)z_1 +mx + Uz_2\)

\(y \ge Lz_1 + mx + (m + \epsilon)z_2\)

\(z_1 + x + z_2 = 1\)

Note that this precludes \(y \in (m-\epsilon, m) \cup (m, m+\epsilon)\), i.e., the only value between \(m-\epsilon, m\) and \(m+\epsilon, m\) 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.

The following two tabs change content below.
I'm an apostate mathematician, retired from a business school after 33 years of teaching mostly (but not exclusively) quantitative methods courses. My academic interests lie in operations research. I also study Tae Kwon Do a bit on the side.

Latest posts by Paul Rubin (see all)