HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Cast to boolean, for integer linear programming

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
linearbooleanprogrammingcastforinteger

Problem

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

Solution

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

Context

StackExchange Computer Science Q#51025, answer score: 7

Revisions (0)

No revisions yet.