Integer linear programming constraint for maximum number of consecutive ones in a binary sequence Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces  the maximum number of consecutive ones in successive sequence. That is, if the maximum number of consecutive ones is three then a solution with the sequence $x_i = 1, x_{i+1}=1, x_{i+2} = 1, x_{i+3}=1$ is unfeasible (4 consecutive ones in sequence).
One way to model this (I think) is to add constraints for every interval $[i, i+3]$ of length four periods so that it can have the sum of at most 3. E.g.
\begin{align}
x_1+x_2+x_3+x_4 &\leq 3 \\
x_2+x_3+x_4+x_5 &\leq 3 \\
&\vdots \\
x_{n-3}+x_{n-2}+x_{n-1}+x_n &\leq 3
\end{align}
But I know you can do smart things with integer programming, so I'm wondering can this constraint be modeled more easily.
 A: There is a way to deduce these constraints. You want
$$x_i=1, x_{i+1}=1, x_{i+2}=1 \implies x_{i+3}=0, ~ \forall i\in I_{n-3}$$
Let $p_i$ be a logical variable meaning ($p_i$ is $x_i$ and $\neg p_i$ is $1-x_i$).
$$p_i \wedge p_{i+1} \wedge p_{i+2} \implies \neg p_{i+3}, ~ \forall i\in I_{n-3}$$
$$ \neg (p_i \wedge p_{i+1} \wedge p_{i+2}) \vee \neg p_{i+3}, ~ \forall i\in I_{n-3}$$
applying De Morgan's law 
$$\neg p_i \vee \neg p_{i+1} \vee \neg p_{i+2} \vee \neg p_{i+3}, ~ \forall i\in I_{n-3}$$
$$(1-x_i) + (1-x_{i+1}) + (1-x_{i+2}) + (1-x_{i+3}) \geq 1, ~ \forall i\in I_{n-3}$$
$$x_i + x_{i+1} + x_{i+2} + x_{i+3} \leq 3, ~ \forall i\in I_{n-3}$$
I think this is the best way.
A: The answer to this question depends on what kinds of descriptions are taken into consideration (with or without auxiliary variables) and how the complexity of a description is measured. Here is an answer in the case of descriptions in the original space (that is, no auxiliary variables are introduced) whose complexity is  measured in terms of the number of inequalities. In this setting, one can show that the set in question will not have a significantly more concise description than the natural one.
Consider integer values $n$ and $k$ with $0 < k < n$. Within the ambient set $\{0,1\}^n$ of binary vectors, the set $X$ of all $x \in \{0,1\}^n$ that have at most $k$ consecutive ones can be described by a system of $n-k$ linear inequalities but cannot be described by a system of fewer than $\lfloor (n + 1 - k) / 2 \rfloor$ linear inequalities.
The system of $n-k$ linear inequalities
$$
   \sum_{j=i}^{i+k} x_j \le k \qquad (i=1,\ldots,n-k)
$$
describes $X$ within $\{0,1\}^n$ since the $i$-th inequality of this system rules out $k+1$ consecutive ones in the components from $i$ to $i+k$.
Consider an arbitrary linear system $Ax \le b$ of $m$ inequalities, with $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, that describes $X$ as  $X = \{ x \in \{0,1\}^n \,:\, A x \le b\}$. A lower bound on $m$ can be derived using the set
$$
    Y = \{ (\underbrace{0,\ldots, 0}_{2(i-1)}, \underbrace{1,\ldots,1}_{k+1},\underbrace{0,\ldots,0}_{n-2i+1}) \,: \, i  = 1,\ldots, \lfloor (n+1 - k) /2 \rfloor \}.
$$
Vectors in $Y$ have exactly $k+1$ consecutive ones preceded by an even number of zeros.
Clearly, $X$ and $Y$ are disjoint subsets of $\{0,1\}^n$.
It suffices to show that no inequality in the system $Ax \le b$ separates more than one point of $Y$. To see this, pick two arbitrary distinct points $p$ and $q$ in $Y$ and generate out of $p$ and $q$ points $p'$ and $q'$ by an exchange of the components between $p$ and $q$ at two positions: the first and the last position at which the components of $p$ and $q$ differ. For example, if $n=6$, $k=3$,  $p= ( \color{red} 1,\color{red} 1, \color{red}  1,\color{red} 1, \color{red} 0, \color{red} 0)$ and $q=( \color{blue} 0, \color{blue} 0, \color{blue} 1, \color{blue} 1, \color{blue} 1, \color{blue} 1)$, then $p' = (\color{blue} 0, \color{red} 1, \color{red} 1, \color{red} 1,\color{red} 0,\color{blue} 1)$ and $q' = (\color{red} 1, \color{blue} 0, \color{blue} 1, \color{blue} 1, \color{blue} 1, \color{red} 0).$ It is clear that $p+ q = p' + q'$ and that $p',q' \in X$. For an arbitrary inequality $a_i x \le b_i$ of the system $Ax \le b$ one has $a_i p' \le b_i$ and $a_i q' \le b$ since the system is valid on $X$. This implies $a_i \cdot ( (p'+q')/2) \le b_i$. In view of $p+q = p'+q'$, one has $a_i \cdot ( (p+ q)/2) \le b_i$. Hence, one has $a_i p \le b_i$ or $a_i q \le b_i$, which means that the inequality $a_i x \le b_i$ cannot separate both $p \in Y$ and $q \in Y$ from $X$. It follows that $Ax \le b$ has at least $|Y| = \lfloor (n+1 - k) /2 \rfloor$ inequalities.
