MIP Modeling: preventing a bit-pattern

From (1):

Let us say we have \(n\) binary variables \(x_i\) for all \(i=1,2,…,n\) i.e., \(x_i \in \{0,1\}\) for all \(i=1,2,…,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.

Basically we want to prevent the sequence \([1,0,1]\) but allow all other patterns. This can be accomplished with the constraint:

\[\boxed{x_i-x_{i+1}+x_{i+2} \le 1}\]

This is actually a special case of (2). Of course for this small example we can inspect all possible combinations (there are \(2^3=8\) of them) to verify we do the right thing:

Counting Start-ups

What about if you want to have all your \(x_i=1\) consecutive. I.e. we only allow something like \([0,0,1,1,1,1,0,0,0]\) where there are no holes in the series of ones. This can be best modeled by counting the number of times we go from \(0\) to \(1\). A compact formulation is:

\[\boxed{\begin{align}&s_i \ge x_i – x_{i-1}\\                      &\sum_i s_i \le 1\\                      &s_i \in \{0,1\}\end{align}}\]

Here we force \(s_i=1\) if we go from \(0\) to \(1\). Note that we can relax \(s_i\) to be continuous (i.e. \(s_i \in [0,1]\)).

This example would show:

\[\begin{array}{cccccccccc}x_i=&[0&0&1&1&1&1&0&0&0]\\                                         s_i=&[0&0&1&0&0&0&0&0&0]\end{array}\]

References

1. How to model a consecutive binary constraint? http://math.stackexchange.com/questions/2218389/how-to-model-a-consecutive-binary-constraint
2. Integer Cuts, http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/integer-cuts.html
3. Modeling number of machine start-ups, http://yetanothermathprogrammingconsultant.blogspot.com/2014/12/modeling-number-of-machine-start-ups.html