
## 7 A Slidingsum Constraint

The SLIDINGSUM constraint [20] is a generalization of the SEQUENCE constraint from Boolean to integer variables, which we extend to allow arbitrary windows.

SLIDINGSUM ([X1, . . . , Xn], [p1**, . . . ,** pm]) holds iff li ≤Psi+ki−1 j=si Xi ≤ ui holds where pi = hli, ui, ki, sii is, as with the generalized SEQUENCE, a window. The constraint can be expressed as a linear program P called the *primal* where W is a matrix encoding the inequalities. Since the constraint represents a satisfaction problem, we minimize the constant 0. The *dual* D is however an optimization problem.

$$\left.\begin{array}{c}\min\ 0\\ \left[\begin{array}{c}W\\ -W\\ I\\ -I\end{array}\right]X\geq\left[\begin{array}{c}l\\ -u\\ a\\ -b\end{array}\right]\right\}\mathcal{P}\qquad\qquad\left.\begin{array}{c}\min\left[-l\ u\ -a\ b\right]Y\\ \left[W^{T}\ -W^{T}\ I\ -I\right]Y=0\\ Y\geq0\end{array}\right\}\mathcal{D}\tag{3}$$

Von Neumann's Strong Duality Theorem states that if the primal and the dual problems are feasible, then they have the same objective value. Moreover, if the primal is unsatisfiable, the dual is unbounded. The SLIDINGSUM constraint is thus satisfiable if the objective function of the dual problem is zero. It is unsatisfiable if it tends to negative infinity.

Note that the matrix WT has the consecutive ones property on the columns. The dual problem can thus be converted to a network flow using the same transformation as with the SEQUENCE constraint. Consider the dual LP of our running example:

Minimize −P4
$-\sum_{i=1}^4l_i Y_i+\sum_{i=1}^4u_i Y_{4+i}-\sum_{i=1}^5u_i$
i=1 biY13+i subject to:
$_1\:a_i Y_{8+i}+\sum_{i=1}^5b_i Y_{13+i}\quad\text{s}$ . 
 1 0 0 1 −1 0 0 −1 1 0 0 0 0 −1 0 0 0 0 1 1 0 1 −1 −1 0 −1 0 1 0 0 0 0 −1 0 0 0 1 1 1 1 −1 −1 −1 −1 0 0 1 0 0 0 0 −1 0 0 1 1 1 0 −1 −1 −1 0 0 0 0 1 0 0 0 0 −1 0 1 0 1 0 −1 0 −1 0 0 0 0 0 1 0 0 0 0 −1 ! Y1 ... Y18 !=  0 ...0 !
Our usual transformation will turn this into a network flow problem:
Minimize −P4 i=1 liYi +P4 i=1 uiY4+i −P5 i=1 aiY8+i +P5 i=1 biY13+i subject to:

 1 0 0 1 −1 0 0 −1 1 0 0 0 0 −1 0 0 0 0 0 1 0 0 0 −1 0 0 −1 1 0 0 0 1 −1 0 0 0 0 0 1 0 0 0 −1 0 0 −1 1 0 0 0 1 −1 0 0 0 0 0 −1 0 0 0 1 0 0 −1 1 0 0 0 1 −1 0 0 −1 0 0 0 1 0 0 0 0 0 −1 1 0 0 0 1 −1 −1 0 −1 0 1 0 1 0 0 0 0 0 −1 0 0 0 0 1     Y1 ... Y18 !=  0 ...0 !
The flow associated with this example is given in Figure 3. There are n + 1 nodes labelled from 1 to n + 1 where node i is connected to node i + 1 with an edge of cost
−ai and node i + 1 is connected to node i with an edge of cost bi. For each window pi, we have an edge from sito si + ki with cost −li and an edge from si + kito si with cost ui. All nodes have a null supply and a null demand. A flow is therefore simply a circulation i.e., an amount of flow pushed on the cycles of the graph.