- Function cp::Sequence(inspectedBinding, inspectedValues, lookupValues, sequenceLength, lowerBound, upperBound, cyclic)
cp::Sequence
The function cp::Sequence
is used to limit the number of occurrences
of a group of values in each contiguous sequence of a row of variables.
It is used to model that some values may occur only a limited number of
times in a contiguous subset of the variables.
Mathematical Formulation
The function
cp::Sequence(i,x_i,S,q,l,u[,c])
returns 1 if, for each contiguous sequence of length \(q\), the number of times that \(x_i\) is in \(S\) is within the range \(\{ l .. u\}\).cp::Sequence(i,x_i,S,q,l,u,c)
is equivalent to\[\begin{split}\begin{array}{llll} \forall i=1..n-q+1: & l \leq \sum_{j=0}^{q-1} (x_{i+j}\in S) & \leq u & c=0 \\ \forall i=1..n : & l \leq \sum_{j=0}^{q-1} (x_{(i+j-1)\%n+1}\in S) & \leq u & c\neq 0 \\ \end{array}\end{split}\]
Function Prototype
cp::Sequence( inspectedBinding, ! (input) an index binding inspectedValues, ! (input/output) an expression lookupValues, ! (input) a set valued expression sequenceLength, ! (input) an expression lowerBound, ! (input) an expression upperBound, ! (input) an expression cyclic ! (optional, input) an expression )
Arguments
- inspectedBinding
The index binding for which the
inspectedValues
expression should be inspected on occurences of values in thelookupValues
set.- inspectedValues
The expression indexed over
inspectedBinding
for which the number of occurrences of the values inlookupValues
is limited per subsequence. This expression may involve variables, but can only contain integer or element values (i.e. no strings, fractional or unit values).- lookupValues
The set containing the particular values that should occur only a limited number of times in each subsequence. This set valued expression should be a subset of the range of
inspectedValues
and does not involve variables.- sequenceLength
The sequence length. An expression that does not involve variables. This argument should be in the range \(\{1..\texttt{card}(\texttt{range}(\texttt{inspectedValues}))\}\).
- lowerBound
The lower bound on the number of occurences. This expression does not involve variables. This argument should be in the range \(\{0..\texttt{upperBound}\}\).
- upperBound
The upper bound on the number of occurences. This expression does not involve variables. This argument should be in the range \(\{\texttt{lowerBound}..\texttt{sequenceLength}\}\).
- cyclic
An optional expression that indicates whether cyclic subsequences should also be inspected. E.g. when you have a set 1,2,3,4,5 then 4,5,1 is a cyclic subsequence of length 3. The
cyclic
expression cannot involve variables and the default of this argument is 0.
Return Value
This function returns 1 if the above condition is met.
Example
In car sequencing the constraint below ensures that no more
car
s of classc
with optiono
are built in a sequence of lengthblockSize(o)
thanmaxCarsPerBlock(o)
. Here, the indexed setclassesHavingOption(o)
is, for each optiono
, the classes of car that have that option.Constraint respectCapacity { IndexDomain : (o); Definition : { cp::Sequence( inspectedBinding : i, inspectedValues : car(i), lookupValues : classesHavingOption(o), sequenceLength : blockSize(o), lowerBound : 0, upperBound : maxCarsPerBlock(o) ) } }In crew scheduling the constraint below ensures that after a flight an attendant
att
has at least two days off (works at most one day in each sequence of three days). The value1
is converted to the set{1}
by AIMMS.Constraint AssureDaysOff { IndexDomain : (att); Definition : { cp::Sequence( inspectedBinding : f, inspectedValues : CrewOnFlight(att, f), lookupValues : 1, sequenceLength : 3, lowerBound : 0, upperBound : 1, cyclic : 1) } }
See also
The functions
cp::Count
andcp::Cardinality
.Constraint Programming on Constraint Programming in the Language Reference.
The Global Constraint Catalog, which references this function as
among_seq
.