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.
Best Answer
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.