5.28. among_seq
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
Constrains all sequences of consecutive variables of the collection to take at least values in and at most values in .
- Example
-
The constraint holds since the different sequences of 4 consecutive variables contains respectively 2, 2, 1 and 1 even numbers.
- Typical
- Symmetries
Items of can be reversed.
Items of are permutable.
can be decreased to any value .
can be increased to any value .
An occurrence of a value of that belongs to (resp. does not belong to ) can be replaced by any other value in (resp. not in ).
- Arg. properties
Contractible wrt. when .
Contractible wrt. when .
Prefix-contractible wrt. .
Suffix-contractible wrt. .
- Usage
The constraint occurs in many timetabling problems. As a typical example taken from [HoevePesantRousseauSabharwal06], consider for instance a nurse-rostering problem where each nurse can work at most 2 night shifts during every period of 7 consecutive days.
- Algorithm
Beldiceanu and CarlssonΒ [BeldiceanuCarlsson01] have proposed a first incomplete filtering algorithm for the constraint. Later on, W.-J.Β vanΒ Hoeve et al. proposed two filtering algorithmsΒ [HoevePesantRousseauSabharwal06] establishing arc-consistency as well as an incomplete filtering algorithm based on dynamic programming concepts. In 2007 Brand et al. came up with a reformulationΒ [BrandNarodytskaQuimperStuckeyWalsh07] that provides a complete filtering algorithm. One year later, Maher et al. use a reformulation in term of a linear programΒ [MaherNarodytskaQuimperWalsh08] where (1)Β each coefficient is an integer in , (2)Β each column has a block of consecutive 1's or 's. From this reformulation they derive a flow model that leads to an algorithm that achieves a complete filtering in along a branch of the search tree.
- Systems
- See also
generalisation: Β (single set of values replaced by individual values).
- Keywords
characteristic of a constraint: hypergraph.
combinatorial object: sequence.
constraint type: system of constraints, decomposition, sliding sequence constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
A constraint on sliding sequences of consecutive variables. Each vertex of the graph corresponds to a variable. Since they link variables, the arcs of the graph correspond to hyperarcs. In order to link consecutive variables we use the arc generator . The constraint associated with an arc corresponds to the constraint defined at another entry of this catalogue.
- Signature
Since we use the arc generator with an arity of on the items of the collection, the expression corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property to and simplify to .