## 5.351. sliding_sum

Origin

CHIP

Constraint

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

Synonym

$\mathrm{𝚜𝚎𝚚𝚞𝚎𝚗𝚌𝚎}$.

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(3,7,4,〈1,4,2,0,0,3,4〉\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.

Typical
 $\mathrm{𝙻𝙾𝚆}\ge 0$ $\mathrm{𝚄𝙿}>0$ $\mathrm{𝚂𝙴𝚀}>1$ $\mathrm{𝚂𝙴𝚀}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\ge 0$ $\mathrm{𝚄𝙿}<$$\mathrm{𝚜𝚞𝚖}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)$
Symmetry

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

Arg. properties
• Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ when $\mathrm{𝚂𝙴𝚀}=1$.

• Prefix-contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• Suffix-contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

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.

Systems
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.351.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.351.1. (A) Initial and (B) final graph of the $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$$\left(3,7,\mathbf{4},〈1,\mathbf{4},\mathbf{2},\mathbf{0},\mathbf{0},\mathbf{3},\mathbf{4}〉\right)$ constraint of the Example slot where each ellipse represents an hyperedge involving $\mathrm{𝚂𝙴𝚀}=\mathbf{4}$ vertices (e.g., the first ellipse represents the constraint $1+4+2+0\in \left[3,7\right]$) 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{𝐍𝐀𝐑𝐂}}$.