2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.