

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

assignment with Xi = 0, pushing a unit of flow on (**u, v**) results in a solution with Xi = 1. Symmetrically, if the flow corresponds to an assignment with Xi = 1, pushing a unit of flow on (**u, v**) results in a solution with Xi = 0. If the shortest path in the residual graph between v and u is k(v,u), then the shortest cycle that contains (**u, v**) has length k(u,v) + k(v,u). Pushing a unit of flow through this cycle results in a flow of cost c + k(u,v) + k(v,u) which is the minimum-cost flow that contains the edge (**u, v**).

If c + k(u,v) + k(v,u) > max(dom(T )), then no flows containing the edge (**u, v**) exist with a cost smaller or equal to max(dom(T )). The variable Xi must therefore be fixed to the value taken in the current flow. Following Equation 1, the cost of the variable T
must be no smaller than the cost of the solution. To enforce BC on the cost variable, we increase the lower bound of dom(T ) to the cost of the minimum flow in the graph G.

To enforce DC on the X variables efficiently we can use an all pairs shortest path algorithm on the residual graph [15]. This takes O(n 2log n) time using Johnson's algorithm [12]. This gives an O(n 2log n **log log** u) time complexity to enforce DC on SOFTSEQUENCE. The penalty variables used for SOFTSEQUENCE arise directly out of the problem description and occur naturally in the LP formulation. We could also view them as arising through the methodology of [16], where edges with costs are added to the network graph for the hard constraint to represent the softened constraint.

## 6 Generalized Sequence Constraint

To model real world problems, we may want to have different size or positioned windows. For example, the window size in a rostering problem may depend on whether it includes a weekend or not. An extension of the SEQUENCE constraint proposed in
[9] is that each AMONG constraint can have different parameters (start position, l, u, and k). More precisely, GEN-SEQUENCE(p1, . . . , pm, [X1, X2, . . . , Xn], v) holds iff AMONG(li, ui, ki, [Xsi
, . . . , Xsi+ki−1], v) for 1 ≤ i ≤ m where pi = hli, ui, ki, sii.

Whilst the methods in Section 4 easily extend to allow different boundsl and u for each window, dealing with different windows is more difficult. In general, the matrix now