How to model a consecutive binary constraint?

Question

Let us say we have $n$ binary variables $x_i$ for all $i=1,2,\ldots,n$, i.e., $x_i\in\{0,1\}$ for all $i=1,2,\ldots,n$.

I need to write the following constraint:

• If $x_i=1$ and $x_{i+2}=1$, then $x_{i+1}=1$. In other words, the variables $x_i$ must be consecutives.

I tried with this one:

$$x_i+x_{i+2}\leqslant 2x_{i+1},\tag{1}$$

which does not quite translate what I need. In fact, inequality $(1)$ says that: if $x_i=1$ and $x_{i+2}=1$, then $x_{i+1}=1$. But it also says that: if, for example, $x_i=1$ and $x_{i+2}=0$, then $x_{i+1}=1$, which does not have to be true.

Answer 1

To model the implication as described in the question $$ x_i=1 \text{ and } x_{i+2}=1 \Rightarrow x_{i+1} = 1 $$ add the constraints: $$ x_i -x_{i+1} + x_{i+2} \le 1 $$ (no extra variables needed with this formulation)

Different interpretation of the question

Suppose you want all $x_i =1$ to be contiguous (i.e, no holes). A standard formulation for this is to limit the number of "start-ups" to one: $$ \begin{align} &s_i \ge x_i-x_{i-1}\\ &\sum_i s_i \le 1\\ &s_i \in \{0,1\} \end{align} $$ A "start-up" occurs when we switch from $0$ to $1$, in which case we force $s_i=1$. Note that $s_i$ can be relaxed to be continuous between $0$ and $1$.

Answer 2

Add $2n-2$ extra variables $t_i = x_{i+1}-x_i$ and $s_i = -x_i-x_{i+1}$.

Then $$\sum_1^{n-1} t_i + \sum_1^{n-1} s_i \leq 2 $$