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:

• Building a non-chronological schedule based on precedence between interval variables.
• Constraints that deduce the conjunction or disjunction of presence of interval variables.
• Constraints that deduce the temporal disjunction or synchronization of interval variables.

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:

• The constraints that state the relative distance of the end-points of an interval variable such as void IlcEndBeforeStart(const IlcIntervalVar x1, const IlcIntervalVar x2, const IlcInt z=0) and its companions IlcStartBeforeStart, IlcStartBeforeEnd, and IlcEndBeforeEnd.
• The constraints that synchronize the end-points of an interval variable such as 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:

• The previous constraint constrains the immediate neighbor of two present interval variables in the sequence: void IlcIntervalSequenceVar::setPrevious(const IlcIntervalVar prev, const IlcIntervalVar next) const;.
• The before constraint constrains the relative position of two present interval variables in the sequence: 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:

• the implication constraint void IlcPresenceImply(const IlcIntervalVar x1, const IlcIntervalVar x2);, which is useful for constraint propagation.
• the not implication constraint IlcPresenceImplyNot(const IlcIntervalVar x1, const IlcIntervalVar x2);, which is its own opposite and is particularly useful for constraint propagation.
• the disjunction constraint 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.
• the equality of presence constraint 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.

• In a solution, an interval can be present or absent. In CP Optimizer, an absent interval does not participate in the schedule. Similarly, an interval can be present or absent in the sequence. If absent, the interval does not participate in the sequence. Note that being present (absent) for an interval or present (absent) in the sequence may not be identical during the propagation of the optimizer.
• In a solution, any interval in the chronological sequence is present, and the chronology begins with the first interval of the sequence and traverses the immediate successor (next) intervals until reaching the last interval of the sequence. Conversely, the reverse chronology begins with the last interval of the sequence and traverses the immediate predecessor (previous) intervals until reaching the first interval of the sequence.
• Before any interval in the sequence, we define a formal sink for the chronological sequence. In the programming interface of the sequence variable, this sink is a null handle instance of 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 head of the sequence is a chronologically ordered set (a subsequence) from the head sink. These intervals are "in head" and sequenced. The sink of the head is also in the head and is always present. Upon becoming absent, an interval in the head is removed from this subsequence. The first interval in the head is the "earliest in head" interval, and the last interval in the head is the "latest in head" interval.
• The tail of the sequence is a reverse chronologically ordered set (a subsequence) from the tail sink. These intervals are "in tail" and sequenced. The sink of the tail is also in the tail and is always present. Upon becoming absent, an interval in the tail is removed from this subsequence. The first interval in the tail is the "earliest in tail" interval, and the last interval in the tail is the "latest in tail" interval.
• The remaining intervals are not sequenced. In order of to have a complete description of the not sequenced neighborhood of the head and tail subsequences, these intervals may belong to two unordered subsets. From the head point of view, the set of "candidate head" intervals are the intervals that can chronologically extend the head subsequence. From the tail point of view, the set of "candidate tail" intervals are the intervals that can extend the tail subsequence.

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.

• The first change is the setting of the presence or absence of an interval. Note that, for sake of regularity, you can set as present the head or tail sink (no effect) or set as absent the head or tail sink (failure raised by the optimizer engine).
• Building the sequence consists of extending the head with a candidate head interval or extending the tail with a candidate tail interval.
• If the head (tail) extension by a candidate head (tail) interval is not allowed, then a remove candidate head (tail) change applies. Note that each time the head is extended, the candidate head list of intervals is fully recomputed.

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

• Presence change: The interval whose presence is fixed is the domain-delta of this event. If the interval becomes absent, it is removed from the partition of the sequence after the change has been processed; for example, it remains in the head if it was there. This makes it possible to initialize an iterator on a newly absent interval in a propagation algorithm.
• Extension change: the domain-delta is defined from the interval that is the latest in head from the last time the head extension was processed: the "earliest newly in head" interval. The head subsequence is partitioned into two chronological oriented sets: from the "earliest in head" interval to the "latest in old head", which is possibly empty, and from the "earliest newly in head" interval to the "latest in head" interval is the head-delta, this subsequence being surely non-empty. A similar domain-delta is defined on tail extension events.

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.