formulate this constraint simply and directly as an integer linear program:

l ≤ X1 + X2 + X3 ≤ u,
$$\begin{array}{l}{{l\leq X_{2}+X_{3}+X_{4}\leq u,}}\\ {{l\leq X_{3}+X_{4}+X_{5}\leq u,}}\end{array}$$
l ≤ X4 + X5 + X6 ≤ u where Xi ∈ {0, 1}. By introducing surplus/slack variables, Yi and Zi, we convert this to a set of equalities:

$X_{1}+X_{2}+X_{3}-Y_{1}=l$, $X_{2}+X_{3}+X_{4}-Y_{2}=l$, $X_{3}+X_{4}+X_{5}-Y_{3}=l$, $X_{4}+X_{5}+X_{6}-Y_{4}=l$,
X1 + X2 + X3 − Y1 = **l, X**1 + X2 + X3 + Z1 = u,
X2 + X3 + X4 − Y2 = **l, X**2 + X3 + X4 + Z2 = u,
X3 + X4 + X5 − Y3 = **l, X**3 + X4 + X5 + Z3 = u,
X4 + X5 + X6 − Y4 = **l, X**4 + X5 + X6 + Z4 = u
where Yi, Zi ≥ 0. In matrix form, this is:

$$\begin{array}{l}{{X_{2}+X_{3}+X_{4}+Z_{2}=u,}}\\ {{X_{3}+X_{4}+X_{5}+Z_{3}=u,}}\\ {{X_{4}+X_{5}+X_{6}+Z_{4}=u}}\end{array}$$
  ...X6 Y1 Z1 ... Y4  =   1 1 1 0 0 0 −1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 −1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 −1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 −1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1   lu lu lu lu   

X1

Z4

This matrix has the *consecutive ones* property for columns: each column has a block of consecutive 1's or −1's and the remaining elements are 0's. Consequently, we can apply the method of Veinott and Wagner [11] (also described in Application 9.6 of [3])
to simplify the problem. We create a zero last row and subtract the ith row from i + 1th row for i = 1 to 2n. These operations do not change the set of solutions. This gives:

 1 1 1 0 0 0 −1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 −1 0 0 1 0 0 0 −1 −1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 −1 0 0 1 0 0 0 0 −1 −1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 −1 0 0 1 0 0 0 0 0 −1 −1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 −1 −1 −1 0 0 0 0 0 0 0 −1      X1 ...X6 Y1 Z1 ... Y4 Z4  

![0_image_0.png](0_image_0.png)

This matrix has a single 1 and −1 in each column. Hence, it describes a network flow problem [3] on a graph G = (**V, E**) (that is, it is a network matrix). Each row in the matrix corresponds to a node in V and each column corresponds to an edge in E. Down each column, there is a single row i equal to 1 and a single row j equal to
-1 corresponding to an edge (**i, j**) ∈ E in the graph. We include a source node s and a sink node t in V . Let b be the vector on the right hand side of the equation. If biis positive, then there is an edge (**s, i**) ∈ E that carries exactly bi amount of flow. If biis negative, there is an edge (**i, t**) ∈ E that caries exactly |bi| amount of flow. The bounds