5.288. sliding_sum
| DESCRIPTION | LINKS | GRAPH |
- Origin
CHIP
- Constraint
sliding_sum(LOW,UP,SEQ,VARIABLES)
- Argument(s)
-
LOW int UP int SEQ int VARIABLES collection(var−dvar) - Restriction(s)
-
UP≥LOW SEQ>0 SEQ≤|VARIABLES| required(VARIABLES,var) - Purpose
Constrains all sequences of SEQ consecutive variables of the collection VARIABLES so that the sum of the variables belongs to interval [LOW,UP].
- Example
-
(
)3,7,4,〈1,4,2,0,0,3,4〉 The example considers all sliding sequences of SEQ=4 consecutive values of 〈1,4,2,0,0,3,4〉 collection and constraints the sum to be in [LOW,UP]=[3,7]. The sliding_sum 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.
- Algorithm
Beldiceanu and Carlsson [BeldiceanuCarlsson01] have proposed a first incomplete filtering algorithm for the among_seq constraint. In 2008, Maher et al. showed in [MaherNarodytskaQuimperWalsh08] that the sliding_sum 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.
- Key words
characteristic of a constraint: hypergraph, sum.
combinatorial object: sequence.
constraint type: decomposition, sliding sequence constraint.
- Arc input(s)
VARIABLES
- Arc generator
-
PATH↦collection - Arc arity
-
SEQ - Arc constraint(s)
-
• sum_ctr(collection,≥,LOW) • sum_ctr(collection,≤,UP) - Graph property(ies)
-
NARC=|VARIABLES|−SEQ+1
- Graph model
We use sum_ctr as an arc constraint. sum_ctr takes a collection of domain variables as its first argument.
Parts (A) and (B) of Figure 5.288.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 NARC=|VARIABLES|−SEQ+1) the final graph corresponds to the initial graph.
Figure 5.288.1. Initial and final graph of the sliding_sum constraint
- Signature
Since we use the PATH arc generator with an arity of SEQ on the items of the VARIABLES collection, the expression |VARIABLES|−SEQ+1 corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property NARC=|VARIABLES|−SEQ+1 to NARC≥|VARIABLES|−SEQ+1 and simplify to .