5.294. sliding_sum

DESCRIPTIONLINKSGRAPH
Origin

CHIP

Constraint

πšœπš•πš’πšπš’πš—πš_πšœπšžπš–(π™»π™Ύπš†,πš„π™Ώ,πš‚π™΄πš€,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™»π™Ύπš†πš’πš—πš
πš„π™Ώπš’πš—πš
πš‚π™΄πš€πš’πš—πš
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš„π™Ώβ‰₯π™»π™Ύπš†
πš‚π™΄πš€>0
πš‚π™΄πš€β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Constrains all sequences of πš‚π™΄πš€ consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ so that the sum of the variables belongs to interval [π™»π™Ύπš†,πš„π™Ώ].

Example
3,7,4,πšŸπšŠπš›-1,πšŸπšŠπš›-4,πšŸπšŠπš›-2,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-3,πšŸπšŠπš›-4

The example considers all sliding sequences of πš‚π™΄πš€=4 consecutive values of 〈1,4,2,0,0,3,4βŒͺ collection and constraints the sum to be in [π™»π™Ύπš†,πš„π™Ώ]=[3,7]. The πšœπš•πš’πšπš’πš—πš_πšœπšžπš– constraint holds since the sum associated with the corresponding subsequences 1 4 2 0, 4 2 0 0, 2 0 0 3, and 0 0 3 4 are respectively 7, 6, 5 and 7.

Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

Algorithm

Beldiceanu and CarlssonΒ [BeldiceanuCarlsson01] have proposed a first incomplete filtering algorithm for the πšœπš•πš’πšπš’πš—πš_πšœπšžπš– constraint. In 2008, Maher et al. showed inΒ [MaherNarodytskaQuimperWalsh08] that the πšœπš•πš’πšπš’πš—πš_πšœπšžπš– 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

common keyword: πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—Β (sliding sequence constraint).

part of system of constraints: πšœπšžπš–_πšŒπšπš›.

soft variant: πš›πšŽπš•πšŠπš‘πšŽπš_πšœπš•πš’πšπš’πš—πš_πšœπšžπš–.

used in graph description: πšœπšžπš–_πšŒπšπš›.

Keywords

characteristic of a constraint: hypergraph, sum.

combinatorial object: sequence.

constraint type: decomposition, sliding sequence constraint, system of constraints.

filtering: linear programming, flow, bound-consistency.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—

Arc arity
πš‚π™΄πš€
Arc constraint(s)
β€’ πšœπšžπš–_πšŒπšπš›(πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—,β‰₯,π™»π™Ύπš†)
β€’ πšœπšžπš–_πšŒπšπš›(πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—,≀,πš„π™Ώ)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1

Graph model

We use πšœπšžπš–_πšŒπšπš› as an arc constraint. πšœπšžπš–_πšŒπšπš› 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 𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1) the final graph corresponds to the initial graph.

Figure 5.294.1. Initial and final graph of the πšœπš•πš’πšπš’πš—πš_πšœπšžπš– constraint
ctrs/sliding_sum1
Signature

Since we use the 𝑃𝐴𝑇𝐻 arc generator with an arity of πš‚π™΄πš€ on the items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, the expression |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1 corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1 to 𝐍𝐀𝐑𝐂β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.