Linearize $(a = cst) \implies (b = 0)$

Question

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.

Answer 1

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.