It common that you want to select a set of something from a row, and ensure the selected somthings are consecutive, i.e. continous block of something, and the something (e.g. use a unit or not is a binary variable). The problem is selecting a continuous set of variables from a row of binary variables.
contiguity formulation for a binary row
Let:
x[i] in {0,1}, i = 1..n
x[i] = 1 means position i is selected.
Enforcing AT MOST ONE contiguous block of 1s
Idea:
A contiguous block starts at a position where the pattern changes from 0 to 1.
Step 1: Boundary handling
Define:
x[0] = 0
Step 2: Transition indicator variables
Introduce:
y[i] in {0,1}, i = 0..n-1
Add constraints:
y[i] >= x[i+1] - x[i] for i = 0..n-1
Interpretation:
y[i] = 1 if there is a 0 -> 1 transition at position i+1
Each y[i] corresponds to the start of a block.
Step 3: Limit the number of block starts
Sum_{i=0..n-1} y[i] <= 1
Result:
The sequence x[1..n] contains at most ONE contiguous block of 1s
(allowing also the cases of all zeros or all ones).
Enforcing AT MOST K contiguous blocks of 1s
Use the same variables and constraints as above, but replace:
Sum_{i=0..n-1} y[i] <= K
Result:
The sequence x[1..n] contains at most K contiguous blocks of 1s.
Key takeaway
Contiguity is enforced by counting 0 -> 1 transitions
Each transition corresponds to the start of a block
Limiting the number of starts limits the number of blocks