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

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.

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

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.
• Thank you! I understand, you wanted to say, in your first sentence, $z$ equals 1 if $a \neq c$? – J.Khamphousone May 20 at 14:33
• Actually I have more mistakes than that. Let me rethink this and edit... – LarrySnyder610 May 20 at 15:05
• Edited -- see above and see whether you think it works. – LarrySnyder610 May 20 at 17:08
• Alright that's exactly what I needed ;) – J.Khamphousone May 21 at 7:20