Overview | Group | Tree | Graph | Deprecated | Index | Concepts |
An interval sequence variable is defined on a set of interval variables A. Informally speaking, the value of an interval sequence variable represents a total ordering of the interval variables of A. Note that any absent interval variables are not considered in the ordering.
More formally, an interval sequence variable p on a set interval variables A represents
a decision variable whose possible values are all the permutations of the intervals of A.
Let be a set of fixed intervals and n denote
the cardinality of
.
A permutation π of
is a
function π :
{
}
[1, n]
such that if we denote length(π) = |{
, x(
)}| the number
of present intervals:
Note that the sequence alone does not enforce any constraint on the relative position of interval end-points. For instance, an interval variable a could be sequenced before an interval variable b in a sequence p without any impact on the relative position between the start/end points of a and b (a could still be fixed to start after the end of b). This is because different semantics can be used to define how a sequence constrains the positions of intervals. We will see later how the noOverlap constraint implements one of these possible semantics.
The following constraints are available on sequence variables:
The formal semantics of these basic constraints are given in Table 3.
The sequence variable also allows the association of a fixed integer type with each interval variable in the sequence. In particular, these integers are used by the noOverlap constraint (see below) and the typeOfNext/Prev integer expressions (see below). T(p, a) denotes the fixed integer type of interval variable a in the sequence variable p.
The constraints involving interval variables and interval sequence variables cannot be used in logical constraints of CP Optimizer (see operator!, operator||). The reason is that any logical constraint involving interval variables must be captured via the presence Boolean value on the interval handled by the presenceOf constraint. The constraints having this limitation are the ordering constraints on a sequence (first, last, previous and before) and the noOverlap constraint.
The noOverlap constraint on an interval sequence variable p states that the sequence defines a chain of non-overlapping intervals, and any interval in the chain is constrained to end before the start of the next interval in the chain. This constraint is typically useful for modeling disjunctive resources.
More formally, the condition for a permutation value π for sequence p to satisfy the noOverlap constraint is defined as:
A sequence variable together with a no-overlap constraint using it are illustrated in Figure 4.
If a transition distance matrix M is specified, it defines the minimal distance that must separate two consecutive intervals in the sequence. Two versions of the constraint are available: one that enforces the transition distance between each interval and its next interval in the sequence (Next), and the other that enforces the transition distance between each interval and all its successors in the sequence (After).
More formally, if T(p,a) denotes the integer type of interval a in the sequence variable p:
Note that if the transition matrix M satisfies the triangular inequality, the semantics of the
two versions of the constraint and
are the same. If M does
not satisfy the triangular inequality,
constraint
is stronger than
.
The sameSequence and sameCommonSubsequence constraints are binary constraints
on a pair of sequence variables and
. These constraints state that the relative position
of some related subsets of interval variables is the same in both sequences: typically, if a is
before b in sequence
then the interval related to
a is before the interval related to b in
sequence
. Here are two examples of use-cases where these constraints are useful:
A constraint sameCommonSubsequence()
is defined on two sequence variables
(defined on a set of interval
variables
) and
(defined on a
set of interval variables
) with two arrays of interval variables
and
of identical size and such
that
. The constraint states that the sub-sequences defined by
and
by only considering the pairs of
present intervals (
) are identical modulo the mapping between
intervals
and
.
For instance, let's suppose sequence variable defined on interval
variables {a,b,c,d,e,f} and sequence variable
defined on interval
variables {u,v,w,x,y,z} with a constraint sameCommonSubsequence(
,
,[a,c,d,e,f],[u,w,v,x,y]). Assuming in a solution, interval
variables d and y are absent while all the other interval variables are present. The pair
of permutations
=(c,f,a,e,b) and
=(w,v,u,x) satisfies the sameCommonSubsequence constraints.
Indeed if one only considers pairs of present intervals, the mapping
maps
[a,c,e] with [u,w,x]. Subsequence of
over
{a,c,e} is (c,a,e), subsequence of
over
{u,w,x} is (w,u,x) and one can see that the two subsequences are the same modulo the
mapping.
More formally, let n denote the size of both interval variable arrays
and
. The condition for permutations
and
of sequencing variables
and
to satisfy constraint
sameCommonSubsequence(
)
is defined as:
A constraint sameSequence() is defined on two sequence
variables of identical size
(defined on a set of interval variables
) and
(defined on a set of interval
variables
) with two arrays of interval variables
and
that are an ordering of sets
and
. The constraint states that sequences
and
are identical modulo a mapping between intervals
and
. A sameSequence
constraint is stronger than a sameCommonSubsequence
constraint; it additionally imposes that arrays
and
contain all the definition intervals
of their relative sequence variables and that the presence status of mapped interval variables
and
is the same.
More formally, let n denote the size of both sequence variables. The condition for permutations
and
of the sequence variables
and
to satisfy constraint
sameSequence(
) is defined as:
when parameters and
are
omitted in the definition of the above constraints, we assume
and
are the definition intervals of
and
, following the order of definition of interval variables in the
sequence.
Two integer expressions are available to get the type of the interval that is next (resp. previous) to a given interval variable a in a sequence p. When interval a is absent or is the last (resp. first) interval of the sequence, specific values can be provided for these integer expressions.
More formally, let π be the permutation value of a fixed sequence variable p, and
be the value
of a fixed interval variable a in the fixed sequence variable p.
If is present and is not the last interval
in π, we denote
the unique interval
that is next to
in π.
If is present and is not the first interval in π, we
denote
the unique interval
that is previous to
in π.
Integer expressions startOfNext, endOfNext, lengthOfNext, sizeOfNext, startOfPrev, endOfPrev, lengthOfPrev, and sizeOfPrev provide access to the different attributes of the interval that is next (resp. previous) to a given interval variable a in a sequence p. When interval a is absent or is the last (resp. first) interval of the sequence, specific values can be provided for these integer expressions.
The semantics of these expressions are given in the table below.