10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Brika Jan 19 '16 at 0:30
  • 1
    $\begingroup$ 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! $\endgroup$ – D.W. Jan 19 '16 at 0:52
  • $\begingroup$ That's very good. ;) $\endgroup$ – Brika Jan 19 '16 at 16:18
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I verified this correct by testing it exhaustively with a little program. Thank you for the solution! $\endgroup$ – D.W. Apr 24 '16 at 4:03
  • $\begingroup$ @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}. $\endgroup$ – Nick Oct 19 '16 at 0:14
  • 1
    $\begingroup$ @Nick The binary variable is used to model an 'OR' construct. See here for an answer to your question. $\endgroup$ – Erwin Kalvelagen Oct 19 '16 at 1:21
  • $\begingroup$ @ErwinKalvelagen, the great answer, I tried to applied the your approach to my question here cs.stackexchange.com/questions/64794/…. $\endgroup$ – Nick Oct 19 '16 at 7:48
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – D.W. Apr 24 '16 at 4:01
1
$\begingroup$

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*}$$

$\endgroup$
  • $\begingroup$ 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$.) $\endgroup$ – TLW Feb 2 '16 at 2:04
  • $\begingroup$ @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. $\endgroup$ – D.W. Apr 24 '16 at 3:47

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.