0

Given a binary variable $x$ and an integer variable $y=1,\dotsc,10$. I would like to express that $x=1$ if $y=5, x=0$ otherwise. Is this possible using purely linear constraints?

What I'm looking for is the following. Given for instance 2 integer variables $y=1,\dotsc,10$ and $z=1,\dotsc,10$. I want to express that $y=3 \wedge z=7$ cannot occur. To do so, I wanted to introduce 2 new binary variables: $x_{y3}$ and $x_{z7}$.Next, I want to use the linear constraints to state that $x_{y3}=1$ iff $y=3$, and $x_{z7}=1$ iff $z=7$. Finally I would add the constraint: $x_{y3}+x_{z7} \leq 1$ to enforce that $y=3$ and $z=7$ cannot occur simultaneously.

Joris Kinable
  • 142

2 Answers2

0

If you want that $y$ and $z$ take just one value in the range $1,\ldots,10$ $$\lambda_1,\ldots,\lambda_{10} \in\{0,1\}$$

$$\mu_1,\ldots,\mu_{10} \in \{0,1\}$$

$$y=\sum_{i=1}^{10}i\lambda_i$$

$$z=\sum_{i=1}^{10}i\mu_i$$

$$\sum_{i=1}^{10}\lambda_i=1$$ $$\sum_{i=1}^{10}\mu_i=1$$

Then add the incompatible constraints you need. In the specific example you report

$$\lambda_3+\mu_7 \leq 1$$

Hope this can help you

Marcello Sammarra
  • 385
0

The answer lies in the following question: Given an integer variable $y=0,1, \dots, U$, how to enforce that $y\neq c$, for $0\leq c \leq U$? In the following approaches, we will use a binary variable $x_{(y=c)}$ which is forced to 1 if and only if $y=c$. To enforce $y\neq c$, we simply post a constraint: $x_{(y=c)}=0$. This logic can be simply extended to state for instance $y_1\neq c_1 \wedge y_2\neq c_2$ through the following constraint: $x_{(y_1=c_1)}+x_{(y_2=c_2)}\leq 1$

Warning: from a linear programming perspective, neither of these approaches is very effective when they are used to express no-good cuts over a set of general integer variables, for instance in the context of a logic based benders decomposition.

Approach 1

Introduce 3 binary variables $v^-$, $v^+$, $x_{(y=c)}$. \begin{align*} &v^++v^-\leq 1\\ &y \leq c + (U-c)v^+ - v^-\\ &y \geq c+v^+-cv^-\\ &x_{(y=c)}= 1-v^- - v^+ \end{align*} If $v^-=v^+=0$, then $y=c$, if $v^-=1,v^+=0$, then $0\leq y\leq c-1$, if $v^-=0,v^+=1$, then $c+1\leq y\leq U$. Variable $x_{(y=c)}=1$ if and only if $y=c$.

Summary: requires $2|U|$ variables to exclude any value from the domain of $y$.

Approach 2 # (Suggested by Marcello Sammarra)

Introduce binary variables $x_{(y=0)}, x_{(y=1)}, \dots, x_{(y=U)}$. \begin{align*} &y=\sum_{i=0}^U i x_{(y=i)}\\ &\sum_{i=0}^U x_{(y=i)}=1 \end{align*} Variable $x_{(y=c)}=1$ if and only if $y=c$.

Summary: requires $|U|$ variables to exclude any value from the domain of $y$. LP relaxation is possibly weak due to large number of convex combinations.

Approach 3 (Binary encoding)

Let $n=\lceil \log_2 U \rceil$ be the number of bits required to represent any value in the domain of $y$. Introduce $n$ binary variables $x_i$. \begin{align*} &y=\sum_{i=0}^n 2^i x_i\\ \end{align*} Let $c_2$ be the base 2 (binary) encoding of the constant $c$, let $P^c=\{i | \mbox{ith bit equals 1 in }c_2\}$ and $N^c=\{i | \mbox{ith bit equals 0 in }c_2\}$. \begin{align*} &x_{(y=c)}\geq 1-\sum_{i \in P^c}(1-x_i)- \sum_{i \in N^c}x_i\\ \end{align*} Variable $x_{(y=c)}=1$ if and only if $y=c$.

Summary: requires $\lceil \log_2 U \rceil$ variables to exclude any value from the domain of $y$. Weak due to large number of convex combinations.

Joris Kinable
  • 142