Linear programming IFF with equality constrain

Question

Is it possible to write the following logical constrain in linear programming?

Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is

$y=1 \Longleftrightarrow v=k$.

I need this kind of constraint in linear programming to use it in AMPL, but I really can't find a way to write it down as a linear constraint.

Answer 1

Yes, this is possible. The main idea is that a binary variable can be used to enable/disable a inequality constraint as follows: given an inequality $a\cdot x\leq b$ and a binary variable $v$, pick a constant $L$ such that $a\cdot x - b\leq L$ is true for all variable assignments. Then the inequality $a\cdot x \leq b+ (1-v)L$ will be equal to $a\cdot x\leq b$ if $v=1$ and will always be true if $v=0$.

So, the constraint $y=1\Rightarrow v=k$ part can be modeled by the two inequalities $v\leq k+(1-y)L$ and $v\geq k - (1-y)L$. For the other part, $v=k\Rightarrow y=1$, we first transform this into $y\neq 1\Rightarrow v\neq k$. We can model the $v\neq k$ condition as $v < k \vee v > k$ and to model the 'or' we introduce a new binary variable $q$. In particular, we want $v<k$ if $q=1$ and $y=0$ and $v>k$ if $q=0$ and $y=0$, so we get $v < k + (1-q+y)L$ and $v > k-(q+y)L$.

In summary, the inequalities $$\begin{align} v&\leq k+(1-y)L\\ v&\geq k - (1-y)L\\ v &< k + (1-q+y)L\\ v &> k-(q+y)L\end{align}$$ model the constraint $y=1 \Leftrightarrow v=k$.