5.20. among_seq
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
among_seq(LOW,UP,SEQ,VARIABLES,VALUES)
- Synonym(s)
- Argument(s)
-
LOW int UP int SEQ int VARIABLES collection(var−dvar) VALUES collection(val−int) - Restriction(s)
-
LOW≥0 LOW≤|VARIABLES| UP≥LOW SEQ>0 SEQ≥LOW SEQ≤|VARIABLES| required(VARIABLES,var) required(VALUES,val) distinct(VALUES,val) - Purpose
Constrains all sequences of SEQ consecutive variables of the collection VARIABLES to take at least LOW values in VALUES and at most UP values in VALUES.
- Example
-
(
)1,2,4,〈9,2,4,5,5,7,2〉, 〈0,2,4,6,8〉 The among_seq constraint holds since the different sequences of 4 consecutive variables contains respectively 2, 2, 1 and 1 even numbers.
- Usage
The among_seq 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 among_seq 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 {−1,0,1}, (2) each column has a block of consecutive 1's or −1's. From this reformulation they derive a flow model that leads to an algorithm that achieves a complete filtering in O(n2) along a branch of the search tree.
- Systems
- See also
- Key words
characteristic of a constraint: hypergraph.
combinatorial object: sequence.
constraint type: decomposition, sliding sequence constraint.
- Arc input(s)
VARIABLES
- Arc generator
-
PATH↦collection - Arc arity
-
SEQ - Arc constraint(s)
-
among_low_up(LOW,UP,collection,VALUES) - Graph property(ies)
-
NARC=|VARIABLES|−SEQ+1
- Graph model
A constraint on sliding sequences of consecutive variables. Each vertex of the graph corresponds to a variable. Since they link SEQ variables, the arcs of the graph correspond to hyperarcs. In order to link SEQ consecutive variables we use the arc generator PATH. The constraint associated with an arc corresponds to the among_low_up constraint defined at an other entry of this catalogue.
- 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 .