1
$\begingroup$

Suppose I have two integer and non-negative decision variables $a$ and $b$ in a linear program and a constant $c$, how can I express with linear inequalities that $(a = c) \implies (b = 0)$?

You can separate the two cases when $c$ is an integer and when it is not.

What I've tried so far is: $a - c \ge b$ but that's a too strict constraint as many values like $a = 0$, $b = c = 1$ don't work anymore.

$\endgroup$
  • $\begingroup$ Is $c$ an integer as well? $\endgroup$ – LarrySnyder610 May 20 at 15:15
  • $\begingroup$ I edited my question according to your relevant comment ;) $\endgroup$ – J.Khamphousone May 21 at 7:06
1
$\begingroup$

Introduce three new binary decision variables, $x$, $y$, and $z$:

  • If $a \le c$, then $x$ will equal 1
  • If $a \ge c$, then $y$ will equal 1
  • If $a = c$, then $z$ will equal 1

Introduce a new constant: $$\delta = \begin{cases} \min\{c - \lfloor c\rfloor, \lceil c\rceil - c\}, & \text{if $c$ is not an integer} \\ 1, & \text{if $c$ is an integer} \end{cases}$$ (i.e., if $c$ is not an integer, $\delta$ is the smaller of the two distances from $c$ to its nearest integers).

Let $M$ be a large positive constant.

Enforce the definitions of the new decision variables with the following constraints: $$\begin{align} c - a + \delta & \le Mx \\ a - c + \delta & \le My \\ x + y - 1 & \le z \end{align}$$

The logic is:

  • If $a \le c$, the LHS of the first constraint is positive, so $x$ must equal 1. If $a > c$, the constraint has no effect because the LHS is non-positive:
    • If $c$ is not an integer, then $a > \lceil c\rceil$ since $a$ is an integer, so $c - a + \delta < c - \lceil c\rceil + \delta \le 0$ by definition of $\delta$.
    • If $c$ is an integer, then $c - a + \delta \le -1 + \delta \le 0$ by definition of $\delta$.
  • If $a \ge c$, the LHS of the second constraint is positive, so $y$ must equal 1. If $a < c$, the constraint has no effect because the LHS is non-positive:
    • If $c$ is not an integer, then $a < \lfloor c\rfloor$ since $a$ is an integer, so $a - c + \delta < \lfloor c\rfloor - c + \delta \le 0$ by definition of $\delta$.
    • If $c$ is an integer, then $a - c + \delta \le -1 + \delta \le 0$ by definition of $\delta$.
  • If $x = y = 1$, then $z$ must equal 1, whereas if either or both of $x$ and $y$ equals 0, then the third constraint has no effect.

Then, the constraint $$b \le M(1-z),$$ ensures that if $z=1$ (i.e., if $a=c$), then $b=0$.

A few notes:

  • There's nothing that forces $z$ to equal 0 if $a \ne c$, but since you said $(a = c) \implies (b = 0)$, I understood this to mean that you don't care what happens if $a \ne c$.
  • "Big-$M$"s are not great. Try to set $M$ as small as possible while still preserving the logic of the constraints.
  • You are likely to run into some numerical issues since it's hard to test for true equality. Instead, you might want to add some tolerance, like: $$\begin{align} c - a + \delta & \le Mx + \epsilon \\ a - c + \delta & \le My + \epsilon \end{align}$$ for small $\epsilon$.
  • You said "integer and non-negative decision variables". I interpreted this to mean they are general integer (0, 1, 2, 3, ...). If they are actually binary, things get simpler.
$\endgroup$
  • $\begingroup$ Thank you! I understand, you wanted to say, in your first sentence, $z$ equals 1 if $a \neq c$? $\endgroup$ – J.Khamphousone May 20 at 14:33
  • $\begingroup$ Actually I have more mistakes than that. Let me rethink this and edit... $\endgroup$ – LarrySnyder610 May 20 at 15:05
  • $\begingroup$ Edited -- see above and see whether you think it works. $\endgroup$ – LarrySnyder610 May 20 at 17:08
  • $\begingroup$ Alright that's exactly what I needed ;) $\endgroup$ – J.Khamphousone May 21 at 7:20

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.