Xi, we have Xi ≤ s(i + 1, i). We assign max(Xi) ← min(max(Xi), s(i + 1, i)). It is not hard to prove this is sound and complete, removing all values that cause negative cycles. Following [10], we can make the propagator incremental using the algorithm by Cotton and Maler [21] to maintain the shortest path between |P| pairs of nodes in O(|E| + |V | log |V | + |P|) time upon edge reduction. Each time a lower bound aiis increased or an upper bound biis decreased, the shortest paths can be recomputed in O(m + n log n) time.

## 8 Experimental Results

To evaluate the performance of our filtering algorithms we carried out a series of experiments on random problems. The experimental setup is similar to that in [10]. The first set of experiments compares performance of the flow-based propagator F B on single instance of the SEQUENCE constraint against the **HP RS** propagator3(the third propagator in [9]), the CS encoding of [10], and the AMONG decomposition (AD) of SEQUENCE. The second set of experiments compares the flow-based propagator F BS
for the SOFTSEQUENCE constraint and its decomposition into soft AMONG constraints. Experiments were run with ILOG 6.1 on an Intel Xeon 4 CPU, 2.0 Ghz, 4G RAM. Boost graph library version 1.34.1 was used to implement the flow-based algorithms.

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

Fig. 4. Randomly generated instances with a single SEQUENCE constraints for different combinations of ∆ and k.

For each possible combination of n ∈ {500, 1000, 2000, 3000, 4000, **5000**}, k ∈
{5, 15, 50}, ∆ = u − l ∈ {1, 5}, we generated twenty instances with random lower bounds in the interval (0, k − ∆). We used random value and variable ordering and a time out of 300 sec. We used the Ford-Fulkerson algorithm to find a maximum flow. Results for different values of ∆ are presented in Tables 1, 2 and Figure 4. Table 1 shows results for tight problems with ∆ = 1 and Table 2 for easy problems with ∆ = 5.

3 We would like to thank Willem-Jan van Hoeve for providing us with the implementation of the **HP RS** algorithm.