Cast to boolean, for integer linear programming

Question

I want to express the following constraint, in an integer linear program:

$$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$$

I already have the integer variables $x,y$ and I'm promised that $-100 \le x \le 100$. How can I express the above constraint, in a form suitable for use with an integer linear programming solver?

This will presumably require introducing some additional variables. What new variables and constraints do I need to add? Can it be done cleanly with one new variable? Two?

Equivalently, this is asking how to enforce the constraint

$$y \ne 0 \text{ if and only if } x \ne 0.$$

in the context where I already have constraints that imply $|x| \le 100$ and 0ドル \le y \le 1$.

---

(My goal is to fix an error in https://cs.stackexchange.com/a/12118/755.)

• Brika: What have you tried? Have you tried working through some examples to see if you see a pattern? If yes, have you tried making a guess and then tried proving it?
• D.W.: Heh! I see what you did there, @Brika. If you're curious to see what I tried, see here as well as this explanation of why that was actually wrong. If you want to see my next attempt, see my answer. Thanks for reading through my old questions, and if they can be improved for the future, I'd love to hear any suggestions you might have!
• Brika: That's very good. ;)

Answer 1

I think I can do it with one extra binary variable $\delta \in \{0,1\}$:

$$ -100y \le x \le 100 y $$ $$ 0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta) $$

Update

This assumes $x$ is a continuous variable. If we restrict $x$ to be integer valued, then the second constraint can be simplified to: $$ y-101\delta \le x \le -y+101 (1-\delta) $$

• D.W.: I verified this correct by testing it exhaustively with a little program. Thank you for the solution!
• Nick: @ErwinKalvelagen, could you please explain the your logic with binary variable delta, for more general case, for instance, if y={a: x>0, b: x<0}.
• Erwin Kalvelagen: @Nick The binary variable is used to model an 'OR' construct. See here for an answer to your question.
• Nick: @ErwinKalvelagen, the great answer, I tried to applied the your approach to my question here cs.stackexchange.com/questions/64794/….
• Erwin Kalvelagen: @GonzaloSolera Actually I was wrong: I assumed $x$ to be a continuous variable. Indeed when $x$ is integer valued we can move 0.001 up to 1 as you suggested.

Answer 2

The following isn't pretty by any means, but it works. Let 0ドル \leq x \leq N,ドル $N=100$ in the specific case in the question. Then we have the following constraints.

1. 0ドル \leq z_1, z_2, z \leq 1$
2. $x - N(1-z_1) \leq 0$
3. $-x -Nz_1 \leq -1$
4. $-x -N(1-z_2) \leq 0$
5. $x -Nz_2 \leq -1$
6. $z_1 + z_2 - 1 \leq z$
7. $z \leq z_1$
8. $z \leq z_2$

The intuition is as follows. $z_1 = 1 \iff x \leq 0$. This is encoded in constraints 2 and 3. Similarly constraints 4 and 5 encode $z_2 = 1 \iff x \geq 0$. The last three constraints express $z = z_1 \land z_2$.

• D.W.: This seems to have a bug. I assume you intend $z=1-y$. However, it's still wrong for $x=100$: we want to force $y=1$ ($z=0$) in this case, but there's no choice for $z_1,z_2$ that satisfies all of the equations, as the equation $x-Nz_2 \le -1$ requires $x<N$ (i.e., $x \le 99$). Thus, this ILP gives the wrong result when $x=99$: we want $y=1,ドル but we got $y=0$. Also the desired range for $x$ as listed in the question is $-N \le x \le N,ドル not 0ドル \le x \le N$.

Answer 3

Here's a solution that uses two temporary variables. Let $t,u$ be integer zero-or-one variables, with the intended meaning that $t=1$ if $x \ge 0,ドル $u=1$ if $x \le 0,ドル and $y=\neg(t \land u)$. These can be enforced with the following constraints:

$$\begin{align*} 0 &\le t,u,y \le 1\\ 1+x &\le 101t \le 101 + x\\ 1-x &\le 101u \le 101-x\\ t+u-1 &\le 1-y\\ 1-y &\le t\\ 1-y &\le u \end{align*}$$

• TLW: This answer is incorrect, unfortunately. It will constrain $x \leq 99$ by the first part of the first non-trivial constraint when the question asks given $x \leq 100$. Aren't fencepost errors fun? (Ditto for $x \geq -99$.)
• D.W.: @TLW, thank you for catching that! I've edited my answer to fix the bug. I tested it exhaustively with a little program and I think it should be correct now.