to avoid unsatisfiable instances. We used a random variable and value ordering, and a time-out of 300 sec. All SEQUENCE constraints were enforced on disjoint sets of cardinality one. Instances with ∆ = 1 are hard instances for SEQUENCE propagators [10], so that any DC propagator could solve only few instances. Instances with ∆ = 5 are much looser problems, but they are still hard do solve because each instance includes four overlapping SEQUENCE constraints. To relax these instances, we allow the SEQUENCE
constraint to be violated with a cost that has to be less than or equal to 15% of the length of the sequence. Experimental results are presented in Table 3. As can be seen from the table, the F BS algorithms is competitive with the decomposition into soft AMONG constraints on relatively easy problems and outperforms the decomposition on hard problems in terms of the number of solved problems.

We observed that the flow-based propagator for the SOFTSEQUENCE constraint
(F BS) is very slow. Note that the number of backtracks of F BS is three order of magnitudes smaller compared to ADS. We profiled the algorithm and found that it spends most of the time performing the all pairs shortest path algorithm. Unfortunately, this is difficult to compute incrementally because the residual graph can be different on every invocation of the propagator.

Table 3. Randomly generated instances with 4 soft SEQUENCE s. Number of instances solved in 300 sec / average time to solve.

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

## 9 Conclusion

We have proposed new filtering algorithms for the SEQUENCE constraint and several extensions including the soft SEQUENCE and generalized SEQUENCE constraints which are based on network flows. Our propagator for the SEQUENCE constraint enforces domain consistency in O(n 2) time down a branch of the search tree. This improves upon the best existing domain consistency algorithm by a factor of O**(log** n). We also introduced a soft version of the SEQUENCE constraint and propose an O(n 2log n **log log** u)
time domain consistency algorithm based on minimum cost network flows. These algorithms are derived from linear programs which represent a network flow. They differ from the flows used to propagate global constraints like GCC since the domains of the variables are encoded as costs on the edges rather than capacities. Such flows are efficient for maintaining bounds consistency over large domains. Experimental results demonstrate that the F B filtering algorithm is more robust than existing propagators.

We conjecture that similar flow based propagators derived from linear programs may be useful for other global constraints.