5.276. relaxed_sliding_sum

DESCRIPTIONLINKSGRAPH
Origin

CHIP

Constraint

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

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

There are between π™°πšƒπ™»π™΄π™°πš‚πšƒ and π™°πšƒπ™Όπ™Ύπš‚πšƒ sequences of πš‚π™΄πš€ consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ such that the sum of the variables of the sequence is in [π™»π™Ύπš†,πš„π™Ώ].

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

Within the sequence 2 4 2 0 0 3 4 we have exactly 3 subsequences of πš‚π™΄πš€=4 consecutive values such that their sum is located within the interval [π™»π™Ύπš†,πš„π™Ώ]=[3,7]: subsequences 4 2 0 0, 2 0 0 3 and 0 0 3 4. Consequently the πš›πšŽπš•πšŠπš‘πšŽπš_πšœπš•πš’πšπš’πš—πš_πšœπšžπš– constraint holds since the number of such subsequences is located within the interval [π™°πšƒπ™»π™΄π™°πš‚πšƒ,π™°πšƒπ™Όπ™Ύπš‚πšƒ]=[3,4].

Symmetries
  • π™°πšƒπ™»π™΄π™°πš‚πšƒ can be decreased to any value β‰₯0.

  • π™°πšƒπ™Όπ™Ύπš‚πšƒ can be increased to any value ≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1.

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

Algorithm

[BeldiceanuCarlsson01].

See also

hard version: πšœπš•πš’πšπš’πš—πš_πšœπšžπš–.

used in graph description: πšœπšžπš–_πšŒπšπš›Β (the sliding constraint).

Keywords

characteristic of a constraint: hypergraph.

combinatorial object: sequence.

constraint type: sliding sequence constraint, soft constraint, relaxation.

Arc input(s)

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

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

Arc arity
πš‚π™΄πš€
Arc constraint(s)
β€’ πšœπšžπš–_πšŒπšπš›(πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—,β‰₯,π™»π™Ύπš†)
β€’ πšœπšžπš–_πšŒπšπš›(πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—,≀,πš„π™Ώ)
Graph property(ies)
β€’ 𝐍𝐀𝐑𝐂β‰₯π™°πšƒπ™»π™΄π™°πš‚πšƒ
β€’ ππ€π‘π‚β‰€π™°πšƒπ™Όπ™Ύπš‚πšƒ

Graph model

Within the context of the Example slot, the corresponding final directed hypergraph is given by FigureΒ 5.276.1. 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 πšœπšžπš–_πšŒπšπš› constraints involving 4 consecutive variables. 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 [3,7]). However, the directed hypergraph contains 3 arcs, so the πš›πšŽπš•πšŠπš‘πšŽπš_πšœπš•πš’πšπš’πš—πš_πšœπšžπš– constraint is satisfied since it was requested to have between 3 and 4 arcs.

Figure 5.276.1. Final directed hypergraph associated with the example
ctrs/relaxed_sliding_sum1