Linear/Integer Programming - Count consecutive ones.

Question

I am trying to model the following scenario:

If $L_0=0, L_1=0, L_2=0, L_3=1, L_4=1, L_5=0, L_6=0, L_7=1, L_8=1, L_9=1, L_{10}=0$

I would like to create a new variable that keeps track of consecutive times L is 1 before turning back to zero.

That is, I would like to create a new variable with the following output: $Z_1=0, Z_2=0, Z_3=0, Z_4=0, Z_5=2, Z_6=0, Z_7=0, Z_8=0, Z_9=0, Z_{10}=3$.

I need help with modelling this in an LP.

thanks in advance

Answer 1

Exactly doing what you want is difficult. Usually we can get away with simpler things because we know more about the model. But let's try anyway: call the original binary variables $x_i \in \{0,1\}$.

First introduce an integer variable $a_i$ (accumulator) that is defined by: $$a_i = \begin{cases} a_{i-1}+1 & \text{if $x_i=1$ }\\ 0 & \text{otherwise}\end{cases} $$

This can be modeled as: $$\begin{align} & a_{i-1}+1 - (1-x_i)M \le a_i \le a_{i-1}+1 + (1-x_i)M\\ & 0 \le a_i \le x_i M \end{align}$$

Now we need: $$z_i = \begin{cases} a_{i-1} & \text{if $x_i=0$ and $x_{i-1}=1$ }\\ 0 & \text{otherwise}\end{cases} $$

This can be modeled as: $$\begin{align} & a_{i-1} - x_i M - (1-x_{i-1})M \le z_i \le a_{i-1} + x_i M + (1-x_{i-1})M\\ & 0 \le z_i \le x_{i-1} M \\& z_i\le (1-x_i)M \end{align}$$

The results 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

(Only nonzero values are printed).

Notes:

• I doubt this is actually what you need in your model as there is usually a way to exploit knowledge from the rest of the model.
• This is impossible to model as an LP: you need a MIP.
• A good value for $M$ is the largest possible number of consecutive ones. E.g. $M= \mathit{card}(i)$.

Answer 2

At the price of more variables ($n²$), you can get a much stronger formulation avoiding big-M indicator constraints. Let $y_{ij} = (1-L_{i-1}) L_i \dots L_j (1-L_{j+1})$, this can be linearized as $$ y_{ij} \leq 1-L_{i-1} $$ $$ y_{ij} \leq L_k \quad i \leq k \leq j $$ $$ y_{ij} \leq 1-L_{j+1} $$ $$ y_{ij} \ge \sum_{k=i,\dots,j} L_k - L_{i-1} - L_{j+1} - (j-i)$$ and finally $$ z_j = \sum_{i=1,\dots,j} (j-i+1) y_{ij}$$ (assuming border cases $L_0=0$ and $L_{n+1} = 0$).

I think this gives the convex hull (assuming $L_i$ are binaries).