14
$\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.)

Improve this question
$\endgroup$
3
  • 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, 2016 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, 2016 at 0:52
  • $\begingroup$ That's very good. ;) $\endgroup$
    – Brika
    Jan 19, 2016 at 16:18

3 Answers 3

Reset to default
7
$\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) $$

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

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I verified this correct by testing it exhaustively with a little program. Thank you for the solution! $\endgroup$
    – D.W. ♦
    Apr 24, 2016 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, 2016 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, 2016 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, 2016 at 7:48
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erwin Kalvelagen
    Dec 16, 2019 at 6:17
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$.

Improve this answer
$\endgroup$
1
  • $\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, 2016 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*}$$

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.