0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Formatting tips here. $\endgroup$ – Em. Nov 7 '16 at 5:20
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.