does not have the consecutive ones property. It may be possible to re-order the windows to achieve the consecutive ones property. If such a re-ordering exists, it can be found and performed in O(m + n + r) time, where r is the number of non-zero entries in the matrix [17]. Even when re-ordering cannot achieve the consecutive ones property there may, nevertheless, be an equivalent network matrix. Bixby and Cunningham [18] give a procedure to find an equivalent network matrix, when it exists, in O(mr) time. Another procedure is given in [19]. In these cases, the method in Section 4 can be applied to propagate the GEN-SEQUENCE constraint in O(n 2) time down the branch of a search tree.

Not all GEN-SEQUENCE constraints can be expressed as network flows. Consider the GEN-SEQUENCE constraint with n = 5, identical upper and lower bounds (l and u), and 4 windows: [1,5], [2,4], [3,5], and [1,3]. We can express it as an integer linear program:

1 1 1 1 1

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

$$\quad(2)$$. 
Applying the test described in Section 20.1 of [19] to Example 2, we find that the matrix of this problem is not equivalent to any network matrix.

However, all GEN-SEQUENCE constraint matrices satisfy the weaker property of total unimodularity. A matrix is *totally unimodular* iff every square non-singular submatrix has a determinant of +1 or −1. The advantage of this property is that any totally unimodular system of inequalities with integral constants is solvable in Z iff it is solvable in R.

Theorem 3. *The matrix of the inequalities associated with* GEN-SEQUENCE *constraint* is totally unimodular.

In practice, only integral values for the bounds li and ui are used. Thus the consistency of a GEN-SEQUENCE constraint can be determined via interior point algorithms for LP in O(n 3.5log u) time. Using the failed literal test, we can enforce DC at a cost of O(n 5.5log u) down the branch of a search tree for any GEN-SEQUENCE constraint.

This is too expensive to be practical. We can, instead, exploit the fact that the matrix for each GEN-SEQUENCE constraint has the consecutive ones property *for rows* (before the introduction of slack/surplus variables). Corresponding to the row transformation for matrices with consecutive ones for columns is a change-of-variables transformation into variable Sj =Pj i=1 Xi for matrices with consecutive ones for rows. This gives the dual of a network matrix. This is the basis of an encoding of SEQUENCE in [10] (denoted there CD). Consequently that encoding extends to GEN-SEQUENCE. Adapting the analysis in [10] to GEN-SEQUENCE, we can enforce DC in O(nm + n 2log n) time down the branch of a search tree.

In summary, for a compilation cost of O(mr), we can enforce DC on a GEN-SEQUENCE constraint in O(n 2) down the branch of a search tree, when it has a flow representation, and in O(nm + n 2log n) when it does not.