## 5.331. relaxed_sliding_sum

Origin

CHIP

Constraint

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

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

There are between $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ and $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}$ sequences of $\mathrm{𝚂𝙴𝚀}$ consecutive variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ such that the sum of the variables of the sequence is in $\left[\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿}\right]$.

Example
$\left(3,4,3,7,4,〈2,4,2,0,0,3,4〉\right)$

Within the sequence $2420034$ we have exactly 3 subsequences of $\mathrm{𝚂𝙴𝚀}=4$ consecutive values such that their sum is located within the interval $\left[\mathrm{𝙻𝙾𝚆},\mathrm{𝚄𝙿}\right]=\left[3,7\right]$: subsequences $4200$, $2003$ and $0034$. Consequently the $\mathrm{𝚛𝚎𝚕𝚊𝚡𝚎𝚍}_\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ constraint holds since the number of such subsequences is located within the interval $\left[\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃},\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}\right]=\left[3,4\right]$.

Typical
 $\mathrm{𝚂𝙴𝚀}>1$ $\mathrm{𝚂𝙴𝚀}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$ $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}>0\vee \mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$
Symmetries
• $\mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ can be decreased to any value $\ge 0$.

• $\mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}$ can be increased to any value $\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-\mathrm{𝚂𝙴𝚀}+1$.

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

Algorithm

used in graph description: $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$ (the sliding constraint).

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{𝐍𝐀𝐑𝐂}$$\ge \mathrm{𝙰𝚃𝙻𝙴𝙰𝚂𝚃}$ $•$$\mathrm{𝐍𝐀𝐑𝐂}$$\le \mathrm{𝙰𝚃𝙼𝙾𝚂𝚃}$

Graph model

Parts (A) and (B) of Figure 5.331.1 respectively show the initial and final graph associated with the Example slot. For each vertex of the graph we show its corresponding position within the collection of variables. The constraint associated with each arc corresponds to a conjunction of two $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$ constraints involving 4 consecutive variables. In Part (B), we did not put vertex 1 since the single arc constraint that mentions vertex 1 does not hold (i.e., the sum $2+4+2+0=8$ is not located in interval $\left[3,7\right]$). However, the directed hypergraph contains 3 arcs, so the $\mathrm{𝚛𝚎𝚕𝚊𝚡𝚎𝚍}_\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚜𝚞𝚖}$ constraint is satisfied since it was requested to have between 3 and 4 arcs.