## 5.294. sliding_sum

 DESCRIPTION LINKS GRAPH
Origin

CHIP

Constraint

$\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}\left(\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿},\mathrm{𝚂𝙴𝚀},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙻𝙾𝚆}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚄𝙿}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚂𝙴𝚀}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚄𝙿}\ge \mathrm{𝙻𝙾𝚆}$ $\mathrm{𝚂𝙴𝚀}>0$ $\mathrm{𝚂𝙴𝚀}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

Constrains all sequences of $\mathrm{𝚂𝙴𝚀}$ consecutive variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ so that the sum of the variables belongs to interval $\left[\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿}\right]$.

Example
$\left(\begin{array}{c}3,7,4,〈\begin{array}{c}\mathrm{𝚟𝚊𝚛}-1,\hfill \\ \mathrm{𝚟𝚊𝚛}-4,\hfill \\ \mathrm{𝚟𝚊𝚛}-2,\hfill \\ \mathrm{𝚟𝚊𝚛}-0,\hfill \\ \mathrm{𝚟𝚊𝚛}-0,\hfill \\ \mathrm{𝚟𝚊𝚛}-3,\hfill \\ \mathrm{𝚟𝚊𝚛}-4\hfill \end{array}〉\hfill \end{array}\right)$

The example considers all sliding sequences of $\mathrm{𝚂𝙴𝚀}=4$ consecutive values of $〈1,4,2,0,0,3,4〉$ collection and constraints the sum to be in $\left[\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿}\right]=\left[3,7\right]$. The $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ constraint holds since the sum associated with the corresponding subsequences $1420$, $4200$, $2003$, and $0034$ are respectively 7, 6, 5 and 7.

Symmetry

Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

Algorithm

Beldiceanu and Carlsson [BeldiceanuCarlsson01] have proposed a first incomplete filtering algorithm for the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ constraint. In 2008, Maher et al. showed in [MaherNarodytskaQuimperWalsh08] that the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ constraint has a solution “if and only there are no negative cycles in the flow graph associated with the dual linear program” that encodes the conjunction of inequalities. They derive a bound-consistency filtering algorithm from this fact.

See also
Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
$\mathrm{𝑃𝐴𝑇𝐻}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}$

Arc arity
$\mathrm{𝚂𝙴𝚀}$
Arc constraint(s)
 $•$$\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$$\left(\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗},\ge ,\mathrm{𝙻𝙾𝚆}\right)$ $•$$\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$$\left(\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗},\le ,\mathrm{𝚄𝙿}\right)$
Graph property(ies)
$\mathrm{𝐍𝐀𝐑𝐂}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$

Graph model

We use $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$ as an arc constraint. $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$ takes a collection of domain variables as its first argument.

Parts (A) and (B) of Figure 5.294.1 respectively show the initial and final graph associated with the Example slot. Since all arc constraints hold (i.e., because of the graph property $\mathrm{𝐍𝐀𝐑𝐂}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$) the final graph corresponds to the initial graph.

##### Figure 5.294.1. Initial and final graph of the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ constraint Signature

Since we use the $\mathrm{𝑃𝐴𝑇𝐻}$ arc generator with an arity of $\mathrm{𝚂𝙴𝚀}$ on the items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection, the expression $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$ corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property $\mathrm{𝐍𝐀𝐑𝐂}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$ to $\mathrm{𝐍𝐀𝐑𝐂}\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$ and simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.