How to model this constraint linearly?

Question

I want to model the following constraint linearly. Let $x_{i}$ be a binary variable that is equal to $1$ if a process is happening at time $i \in \mathbb Z$ and $0$ otherwise. I would like to express the fact that $x_{i}$ must hold $1$ "per batches", namely, $x_{i}$ must hold $1$ during $t$ consecutive periods. For example, if $t=3$, the sequency $0011100000001110$ must be possible but not $0011000$ (there always should be (a multiple of) three "1" successively ($1111110000$ is ok, as 6 "1" follow each other). How would it possible to model this constraint? Thanks!

Answer 1

One way to handle this is to introduce a new set of binary variables $y_t$ signaling whether a sequence of three ones starts at time $t$. The constraint on $y$ is that $y_t + y_{t+1} + y_{t+2} \le 1$ (you cannot start a new batch while an earlier batch is in progress). The relationship between $x$ and $y$ is that $x_t = y_t + y_{t-1} + y_{t-2}$. (Both sets of constraints have some rather obvious adjustments near the start and end of the time frame.) Note that, since $y$ is integer, you can relax $x$ to real and still be sure, courtesy of the constraints, that it will take values in $\{0,1\}$. So the number of binary variables does not increase. (Continuous variables tend to be computationally "cheap".)

Answer 2

We could use the conjunctive normal form (CNF) — known as product of sums (POS) in Boolean algebra — and then translate to (binary) integer programming. Each clause in the CNF produces a linear inequality. For instance, the clause $x_i \lor \neg x_j$ produces $x_i + (1-x_j) \geq 1$.

---

Example

Suppose we have binary strings of length $5$ and "batches" whose length is a multiple of $2$. Using SymPy, we can find the CNF:

>>> from sympy import *
>>> x1, x2, x3, x4, x5 = symbols('x1 x2 x3 x4 x5')
>>> minterms = [ [1,1,0,0,0],
                 [1,1,1,1,0],
                 [0,1,1,0,0],
                 [0,1,1,1,1],
                 [0,0,1,1,0],
                 [0,0,0,1,1] ]
>>> POSform([x1, x2, x3, x4, x5], minterms)
And(Or(Not(x1), Not(x3), x4), Or(Not(x1), Not(x5)), Or(Not(x1), x2), Or(Not(x2), Not(x4), x1, x5), Or(Not(x2), x1, x3), Or(Not(x3), Not(x5), x2), Or(Not(x4), x3, x5), Or(Not(x5), x4), Or(x1, x3, x5), Or(x2, x4))

Translating to (binary) integer programming, we obtain $10$ linear inequalities

$$\begin{array}{rl} -x_1 -x_3 + x_4 &\geq -1\\ -x_1 -x_5 &\geq -1\\ -x_1 + x_2 &\geq 0\\ x_1 - x_2 - x_4 + x_5 &\geq -1\\ x_1 - x_2 + x_3 &\geq 0\\ x_2 - x_3 - x_5 &\geq -1\\ x_3 - x_4 + x_5 &\geq 0\\ x_4 - x_5 &\geq 0\\ x_1 + x_3 + x_5 &\geq 1\\ x_2 + x_4 &\geq 1\end{array}$$

where the binary constraints $x_1, x_2, x_3, x_4, x_5 \in \{0, 1\}$ can be written as follows

$$\begin{array}{c} 0 \leq x_1 \leq 1\\ 0 \leq x_2 \leq 1\\ 0 \leq x_3 \leq 1\\ 0 \leq x_4 \leq 1\\ 0 \leq x_5 \leq 1\\ x_1, x_2, x_3, x_4, x_5 \in \mathbb Z\end{array}$$

Thus, we have a total of $10 + 5 + 5 = 20$ linear inequality constraints. Verifying using Haskell:

λ> tuples = [ (x1,x2,x3,x4,x5) | x1 <- [0,1], x2 <- [0,1], x3 <- [0,1], x4 <- [0,1], x5 <- [0,1] ]
λ> filter (\(x1,x2,x3,x4,x5)-> (-x1-x3+x4 >= -1) && (-x1-x5 >= -1) && (x2-x1 >= 0) && (x1-x2-x4+x5 >= -1) && (x1-x2+x3 >= 0) && (x2-x3-x5 >= -1) && (x3-x4+x5 >= 0) && (x4-x5 >= 0) && (x1+x3+x5 >= 1) && (x2+x4 >= 1)) tuples
[(0,0,0,1,1),(0,0,1,1,0),(0,1,1,0,0),(0,1,1,1,1),(1,1,0,0,0),(1,1,1,1,0)]