Overview | Group | Tree | Graph | Deprecated | Index | Concepts |
Interval variables |
Precedence and presence constraints between pairs of interval variables |
Cumul element variables |
Interval sequence variables |
While the modeling objects provided by Concert Technology and the algorithms provided by CP Optimizer will generally be sufficient to model and solve your problem, in some situations you may need the full flexibility of writing and maintaining the solution process in various ways, such as writing custom constraints or custom constructive search by means of goals.
A number of classes and functions are provided in the CP Optimizer engine extensions
for implementing custom constraints and custom search. The classes include
IlcConstraint
,
IlcGoal
and IlcDemon
.
For scheduling applications, the engine classes
IlcIntervalVar
,
IlcIntervalSequenceVar
and
IlcCumulElementVar
can be used in writing custom constraints and search.
These classes of decision variables make it possible to write custom search procedures and constraints. Each class has members and member functions to aid the user in implementing customizations:
The instances of these classes are counterparts in the optimizer to instances of modeling classes. They are available via member
functions of the class IloCP
. For example, IlcIntervalVar IloCP::getInterval(const IloIntervalVar var) const
.
Moreover, member functions of IloCP
give access to the values of the domain of a variable after a successful
search.
For more information on the counterpart modeling classes of IlcIntervalVar
, IlcCumulElementVar
and IlcIntervalSequenceVar
, please refer to Introduction to Scheduling Concepts in CP Optimizer.
An instance of the class IlcIntervalVar
is a constrained interval variable in
the CP Optimizer engine. This class is the counterpart of the modeling class IloIntervalVar
,
discussed in the concept Interval variables in CP Optimizer.
The member functions of this class give access to the domain
of an optimizer engine interval variable. The domain of an interval variable
is comprised of the integer range
domains for start, end, length, and size as well as the Boolean range
for the presence.
Recall the start, end, length and size range are meaningless if the interval is absent.
A solution for an interval is fixed integers for the start, end, length and size if the interval is present;
see IloCP
for more information on how to access these values after
a successful solve.
Member functions give access to the delta domains and events for constraint propagation implementations. These members functions are available only during the search process of the optimizer engine. These domain-deltas are also valid outside of the processing of the interval variable.
Figure 1 shows the domain-deltas for the change in the interval integer ranges start, end, length, and size from the last processing of the variable; for example the old domain is [oldstart_{min}, oldstart_{max}]) and the current domain is [start_{min}, start_{max}] which is included in the unchanged range [oldstart_{min}, oldstart_{max}]).
Figure 1: Interval Variables Anytime Delta Domain Interval Domain Change Event
The domain-delta of change of the range of the presence Boolean is trivial: the change is from an unfixed presence status to present or absent.
Member functions isOldAbsent()
and isOldPresent()
access the old value of the presence Boolean. Recall the interval
integer domain ranges start, end, length, and size are meaningless if the interval is absent. Similarly, the domain-delta for the old interval
integer ranges start, end, length, and size are meaningless if the interval is old absent; in other words, if the interval was absent the last time it was
processed by the optimizer engine. Figure 2 shows the domain-delta of a change in the presence of an interval variable. Note that if the presence
status is set to absent, the domain range of start, end, length and size are no longer displayed.
Figure 2: Interval Variables, Anytime Delta Domain Presence Fixing Event
A large range of useful algorithms for scheduling concerns pairs of intervals. These algorithms may involve:
For implementing these algorithms, CP Optimizer provides access to binary constraints. Note that these constraints do not support the logical constraint protocol of the optimizer engines. You may consider them as arcs on the temporal and logical networks of interval variable in the optimizer engines. For more information on constraints, see the concept page Basic constraints on interval variables in CP Optimizer.
The precedence constraints on interval constraints are:
void IlcEndBeforeStart(const IlcIntervalVar x1, const IlcIntervalVar x2, const IlcInt z=0)
and
its companions IlcStartBeforeStart
, IlcStartBeforeEnd
, and IlcEndBeforeEnd
.void IlcEndAtStart(const IlcIntervalVar x1, const IlcIntervalVar x2, const IlcInt z=0)
and its companions IlcStartAtStart
, IlcStartAtEnd
, and IlcEndAtEnd
.Recall these constraints depend on the presence state of the interval variables. In other words, if one of the interval variables is absent, then the constraint no longer has an effect on the schedule.
For the specific binary constraints on interval variables that are members of an interval variable sequence, two constraints regarding sequences are available in the optimizer engine:
void IlcIntervalSequenceVar::setPrevious(const IlcIntervalVar prev, const IlcIntervalVar next) const;
. void IlcIntervalSequenceVar::setBefore(const IlcIntervalVar before, const IlcIntervalVar after) const;
.For more information, please refer to the concept page Interval variable sequencing in CP Optimizer.
The logical presence constraints are:
void IlcPresenceImply(const IlcIntervalVar x1, const IlcIntervalVar x2);
,
which is useful for constraint propagation.IlcPresenceImplyNot(const IlcIntervalVar x1, const IlcIntervalVar x2);
,
which is its own opposite and is particularly useful for constraint propagation.IlcPresenceOr(const IlcIntervalVar x1, const IlcIntervalVar x2);
, which is the
opposite of both intervals being present and is useful for building choice points on the absolute presence of the interval variables.IlcPresenceEqual(const IlcIntervalVar x1, const IlcIntervalVar x2);
and
its opposite exclude disjunction constraint IlcPresenceDiffferent(const IlcIntervalVar x1, const IlcIntervalVar x2);
,
which are useful for building choice points on the relative presence of the interval variables.Note all the constraints presented in this paragraph do not support the mechanism of logical constraints in the pptimizer engine.
An instance of the class IlcCumulElementVar
is a constrained cumul element function in
the optimizer engine. A cumul element function in the
model layer is built by the shape functions
IloPulse
,
IloStepAtStart
or IloStepAtEnd
with an
instance of IloIntervalVar
as the first argument. See Cumul functions in CP Optimizer
for more information.
Taking start
and end
as the end points
of the instance of IlcIntervalVar
in the cumul element function,
an instance of IlcCumulElementVar
is a constrained
positive integer range function that is nonzero everywhere except for
on the segment related to its shape: [start, end)
for a pulse, from start
for a step at start function and from
end
for a step at end function. The value on this segment is a
positive integer range domain, the height, that is to be fixed
by the search if the element function is not the null function.
The cumul element is zero everywhere (the null function) if the
interval variable is absent, the height range is
fixed to zero, or if length = end - start = 0
for a
pulse. The propagation may find that the cumul element
function is to be the null function without fixing the presence, height or length.
In such a case, the height range domain is meaningless. To summarize, an instance of the
class IlcCumulElementVar
is a constrained integer range domain for the height decision, except in some special cases
where the function is the null function.
Figure 3 shows the domain of the cumul function for a pulse shaped element with present and non-absent intervals. Two cases appear, if the maximum start point of the interval is strictly less than the minimum end point of the interval (left side of the figure), the minimum cumul function is at least the minimum of the height if the interval is present. Otherwise, there is no abscissa point where the function is surely not null at this point.
Figure 3: Pulse Cumul Element Domain
Figure 4 shows the domain of the cumul function for step at start and step at end shaped elements with present and non-absent intervals. For a present interval and a nonzero minimum height, the function is nonzero everywhere after its starting point.
Figure 4: Step Cumul Element Domain
The member functions of this class give access to the search engine data structure of the cumul element function, including the interval variable, the shape, the integer range domain for the height. The member functions also include the height domain setters and getters and give access to the delta domains and events for custom constraint propagation implementations. These members functions are available only at search time of the optimizer engine.
An instance of the IlcIntervalSequenceVar
class is a constrained interval
sequence variable in the optimizer engine. The purpose of this class is to sequence a set of intervals,
instances of IlcIntervalVariable
. The modeling counterpart of this class is
IloIntervalSequenceVar
,
discussed in the concept Interval variable sequencing in CP Optimizer.
The sequence is a succession of interval variables that is associated with a chronology
in a scheduling model.
IlcIntervalVariable
. Similarly, after all intervals
in the sequence there exits
a formal sink for the reverse chronological sequence, in the programming interface of the sequence variable; this sink is a
null handle instance of IlcIntervalVariable
.The full constrained representation of a sequence is a precedence graph whose nodes are the sinks and the intervals valued by the presence value. The arcs are directed from a non-absent interval or a sink and point to another non-absent interval or a sink. The arcs are valued by the enumeration: possibly/surely/not immediate successor, possibly/surely/not immediate predecessor, possibly/surely/not successor and possibly/surely/not predecessor. In other words, the arcs define the sets of immediate successors and predecessors or indirect successors and predecessors of an interval. Reducing the domain consists in setting an interval present or absent and removing intervals from the different sets of the domain (that is changing the valuation of an arc). The main drawbacks of the precedence graph is the quadratic data structure (in terms of the number of intervals) for memory usage and the at least linear time maintenance for a change or a decision. Moreover, the precedence graph contains more information than needed for chronological heuristics scheduling solution building.
CP Optimizer supplies a more accurate constrained data structure: the Head-Tail Sequence Graph. The constrained domain of the Head-Tail Sequence Graph is a restriction of the precedence by a chronologically based partition of the intervals of the sequence. Figure 5 shows this restriction with a present interval as a plain circle, and a non-absent interval as a dashed circle.
Figure 5: Interval Sequence Variable Head-Tail Graph Domain
The sequence is sequenced when any non-absent interval is in the tail or in the head. The sequence is fixed when it is sequenced and
any interval in the tail or in the head is present in the sequence. Note that if the Head-Tail Graph is not sequenced, there
is at least one candidate head interval and one candidate tail interval. The sequence solution is given by joining the
latest interval in the head and latest interval in the tail as immediate neighbors. The solution available from the instance of
IloCP
consists in the first and last intervals and the next and previous interval of a
present interval.
The Head-Tail Sequence Graph is linear in memory and changes need O(1) or at most linear algorithms for propagation and decision making in the context of a chronological a reverse chronological) schedule building.
An iterator traverses the subsets of the sequence: tail, head, not sequenced, candidate head or candidate tail. As shown on Figure 5, the traversal is oriented by the chronology for the head subsequence and by reverse chronology for the tail subsequences. Note the iterator is not stable in the case of a change of the Head-Tail Sequence Graph.
Figure 6 shows the changes that can affect the head subsequence of the Head-Tail graph. Tail subsequence changes are similar.
Figure 6: Interval Sequence Variable Head-Tail Graph Head Changes
The presence in sequence of intervals in one subsequence, the head/tail extension, or removing of a candidate from the other subsequence are the events on the Head-Tail Graph. Each of these events corresponds to a domain-delta only available at the processing time of the Head-Tail Graph by the optimizer engine. Figure 7 shows the domain-delta for presence change and head extension change.
Figure 7: Interval Sequence Variable Head-Tail Graph Delta Domain
Notes about decision making:
Suppose that a chronological schedule is being built. Sequencing an interval sequence variable consists of choosing from among the candidate head intervals the one that will extend the head subsequence. We suggest that before any extension decision, the search traversal fix the presence of all intervals in head. When the sequence is sequenced, it may not be fixed because the constraint propagation engine could have placed some not present intervals in the tail. In such a case, the search traversal must (chronologically) fix the presence of the intervals in the tail. By chronologically, we means from the "latest in tail" interval to the "earliest in tail" interval.
Sequencing an interval sequence variable is not scheduling the intervals in the sequence, nor is it scheduling the entirety of the interval variables in the model. The start and end dates of the intervals must be fixed, and this in a chronological manner. We emphasize you may need to interleave sequencing decisions with scheduling and presence setting decisions in a custom search.
To help you with decisions, CP Optimizer provides an iterator on the in head, in tail, candidate head and candidate tail intervals.
Furthermore, it defines two choice points for Head-Tail extension:
IlcGoal IlcIntervalSequenceVar::tryExtendHead(const IlcIntervalVar var) const;
and
IlcGoal IlcIntervalSequenceVar::tryExtendHead(const IlcIntervalVar var) const;
.
Notes about constraint propagation:
Propagating a constraint on a head-tail interval consists of implementing the filtering algorithm on the events of presence change and head-tail extension. The presence change for an interval in head and the head extension filtering algorithm must ensure that the constraint conditions hold on the head subsequence. This generally makes it possible to set as absent some intervals in the head. A similar filtering algorithm exists for the presence in tail change and tail extension.
The second aspect to consider is the sets of candidate head and tail intervals. An interval must be removed from the set of candidate head intervals when it cannot be the immediate successor of an interval between the "latest present in head" interval and the "latest in head" interval.
Lastly, when the sequence variable is sequenced, the head and tail subsequences must be joined. The constraint condition must be enforced on the full sequence "earliest in head"->...->"latest in head"->"latest in tail"->"earliest in tail".
To help you with writing the filtering algorithm, CP Optimizer provides access to the immediate neighborhood of an interval
in head and tail, to the domain-deltas of all events and to two pure sequencing modifiers that constrain the Head-Tail
Graph: void IlcIntervalSequenceVar::setPrevious(const IlcIntervalVar prev, const IlcIntervalVar next) const
and
IlcIntervalSequenceVar::setBefore(const IlcIntervalVar before, const IlcIntervalVar after) const
.