In [1] following modeling question is posed:
Given binary variables xi∈{0,1}, I want to form an integer variable zi that has the length of the preceding string of ones (this is sometimes called the run-length). I.e.:
 |
| Given x(i) find z(i) |
This is not so easy to do. Here is my attempt. The idea behind my approach, is to use another intermediate integer variable
ai (accumulator) defined by
ai={ai−1+1if xi=1 0otherwise
 |
| Additional variable a(i) |
Step 1: form ai
The calculation of variable
ai can be stated as a quadratic constraint:
ai=xi(ai−1+1)
In terms of
indicator constraints (implications as available in many MIP solvers) this would look as follows:
xi=0⇒ai=0xi=1⇒ai=ai−1+1
If the MIP solver does not support indicator constraints, we can write this as a bunch of linear inequalities:
(ai−1+1)−(1−xi)M≤ai≤(ai−1+1)+(1−xi)M0≤ai≤xiM Here
M is the length of the largest possible string of consecutive 1's, e.g.
M=card(i).
We can also linearize the quadratic constraint, but that leads to extra variables.
Step 2: form zi
To go from ai to zi, we can define: zi={ai−1if xi=0 and xi−1=1 0otherwise In implication form this is:xi=0 and xi−1=1⇒zi=ai−1xi=1 or xi−1=0⇒zi=0 This is not immediately ready for use with indicator constraints (these constraints want a single binary variable at the left of ⇒). We can introduce a new binary variable yi∈{0,1} and linearize yi=xi−1(1−xi) using: yi=xi−1(1−xi)⇔{yi≤xi−1yi≤1−xiyi≥xi−1−xiyi∈{0,1} (We can relax yi to yi∈[0,1]). Now we are able to implement the indicator constraints:yi≥xi−1−xiyi≤xi−1yi≤1−xiyi=1⇒zi=ai−1yi=0⇒zi=0yi∈{0,1}
Written as linear inequalities, we have: ai−1−xiM−(1−xi−1)M≤zi≤ai−1+xiM+(1−xi−1)M0≤zi≤1−xi−1Mzi≤(1−xi)M
An MINLP formulation is simpler: zi=ai−1(1−xi)xi−1
Putting things together
To summarize: we can come up with (at least) three different formulations:
| big-M inequalities | Indicator constraints | MINLP formulation |
|---|
| ai≤(ai−1+1)+(1−xi)Mai≥(ai−1+1)−(1−xi)Mai≤xiMzi≤ai−1+(1−xi−1+xi)Mzi≥ai−1−(1−xi−1+xi)Mzi≤xi−1Mzi≤(1−xi)Mai∈{0,1,2,…}zi∈{0,1,2,…} |
xi=0⇒ai=0xi=1⇒ai=ai−1+1yi≤1−xiyi≤xi−1yi≥xi−1−xiyi=0⇒zi=0yi=1⇒zi=ai−1ai∈{0,1,2,…}yi∈{0,1}zi∈{0,1,2,…} |
ai=xi(ai−1+1)zi=ai−1(1−xi)xi−1ai∈{0,1,2,…}zi∈{0,1,2,…} |
This is complex enough, we really have to try this out. The results of the big-
M inequality approach look like:
---- 71 VARIABLE x.L
i3 1.000, i4 1.000, i7 1.000, i8 1.000, i9 1.000
---- 71 VARIABLE a.L
i3 1.000, i4 2.000, i7 1.000, i8 2.000, i9 3.000
---- 71 VARIABLE z.L
i5 2.000, i10 3.000
The MINLP formulation is the most elegant: just two equations.
Can we do this without intermediate variables ai?
Yes, at the expense of more nonzero elements in the LP matrix. We can define:
zi={∑k<ixk−∑k<izkif xi=0 and xi−1=1 0otherwise
 |
| z(i10) = green cells − blue cells |
In big-
M inequality form we can write:
∑k<i(xk−zk)−(1−xi−1+xi)M≤zi≤∑k<i(xk−zk)+(1−xi−1+xi)M0≤zi≤1−xi−1Mzi≤(1−xi)M I prefer the versions with extra variables
ai.
A stronger formulation
In the comments of [1] a much stronger formulation is proposed: no big-
M's needed. A disadvantage is that we need many variables (
n2/2) and even more constraints. The idea is to find occurrences of a run starting at position
i and ending at position
j.
 |
| y(i,j)=1 represents a run from i to j |
Such a run can be found by:
yi,j=(1−xi−1)(j∏k=ixk)(1−xj+1) This is a product of binary variables. The basic linearization is:
y=x1x2⇔{y≤x1y≤x2y≥x1+x2−1y∈{0,1} This formulation allows us to relax
y∈{0,1} to
y∈[0,1] Generalizing this, leads to:
yi,j≤1−xi−1yi,j≤xkk=i,…,jyi,j≤1−xj+1yi,j≥j∑k=ixk−xi−1−xj+1−(j−i)yi,j∈{0,1}j≥i Again, if we want, we can relax
yi,j to be continuous between zero and one. With these
yi,j we can calculate
zj as:
zj=∑i≤j(j−i+1)yi,j
When we try this out we see:
---- 134 VARIABLE x.L
i3 1.000, i4 1.000, i7 1.000, i8 1.000, i9 1.000
---- 134 VARIABLE y.L
i4 i9
i3 1.000
i7 1.000
---- 134 VARIABLE z.L
i4 2.000, i9 3.000
For our small example with
n=card(i)=11 we end up with a total of 88 variables (66 are
yi,j's) and 495 constraints. If we would have
n=card(i)=100 these numbers increase to 5,250 variables and 186,950 equations. The number of equations is roughly
n3/6.
With some invented models, this formulation did not seem competitive with the earlier MIP models. There may well be models where this formulation work better. Modern MIP solvers are very good in generating cuts. This means that "smaller" (fewer variables and equations) but weaker formulations are not so bad anymore: the solver will strengthen the model as it goes.
Maximum run-length
I doubt the user really needs this. Usually if we know more about the rest of the problem, we can simplify things considerably. For instance, suppose the model really only needs to establish an upper bound on the run-length. If we only need
zi≤R, we can drop a boatload of constraints. One formulation can be:
xi=1⇒zi=zi−1+1zi≤R A formulation only involving the original
xi variables can be:
i+R∑k=ixk≤R∀i
This is a good example where we need to look at the whole model to give the best possible advice on how to model things. Just looking at a fragment may lead to formulations that are too general and thus way too complicated.
References
- Linear/Integer Programming: Counting Consecutive Ones, https://math.stackexchange.com/questions/2732897/linear-integer-programming-count-consecutive-ones
