Class SequenceVar

Namespace

OptalCP

Assembly

OptalCP.dll

Ordered sequence of intervals for routing and sequencing problems.

public class SequenceVar : ModelElement

Inheritance

object

ModelElement

SequenceVar

Inherited Members

ModelElement.Name

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Remarks

Models a sequence (order) of interval variables.

A sequence variable represents an ordered arrangement of interval variables where no two intervals overlap. The sequence captures not just that the intervals don't overlap, but also their relative ordering in the solution.

Sequence variables are created using Model.SequenceVar and are typically used with the SequenceVar.NoOverlap constraint to enforce non-overlapping with optional transition times between intervals.

The position of each interval in the sequence can be queried using Model.Position or IntervalVar.Position, which returns an integer expression representing the interval's index in the final ordering (0-based). Absent intervals have an absent position.

See also:

• Model.SequenceVar — to create sequence variables.
• SequenceVar.NoOverlap — for the no-overlap constraint with transitions.
• Model.Position — to get an interval's position in the sequence.

Methods

NoOverlap(IEnumerable<IEnumerable<int>>?)

Constrain the interval variables forming the sequence to not overlap.

public Constraint NoOverlap(IEnumerable<IEnumerable<int>>? transitions = null)

Parameters

transitions IEnumerable<IEnumerable<int>>

2D square array of minimum transition distances between the intervals. The first index is the type (index) of the first interval in the sequence, the second index is the type (index) of the second interval in the sequence

Returns

Constraint

The no-overlap constraint.

Remarks

The noOverlap constraint makes sure that the intervals in the sequence do not overlap. That is, for every pair of interval variables x and y at least one of the following conditions must hold (in a solution):

1. Interval variable x is absent. This means that the interval is not present in the solution (not performed), so it cannot overlap with any other interval. Only optional interval variables can be absent.
2. Interval variable y is absent.
3. x ends before y starts, i.e. x.end() is less or equal to y.start().
4. y ends before x starts, i.e. y.end() is less or equal to x.start().

In addition, if the transitions parameter is specified, then the cases 3 and 4 are further constrained by the minimum transition distance between the intervals:

3. x.end() + transitions[x.type][y.type] is less or equal to y.start().
4. y.end() + transitions[y.type][x.type] is less or equal to x.start().

where x.type and y.type are the types of the interval variables x and y as given in Model.SequenceVar. If types were not specified, then they are equal to the indices of the interval variables in the array passed to Model.SequenceVar. Transition times cannot be negative.

Note that transition times are enforced between every pair of interval variables, not only between direct neighbors.

The size of the 2D array transitions must be equal to the number of types of the interval variables.

This constraint is equivalent to Model.NoOverlap called with the sequence variable's intervals and types.

Example:

A worker must perform a set of tasks. Each task is characterized by:

• length of the task (how long it takes to perform it),
• location of the task (where it must be performed),
• a time window earliest to deadline when the task must be performed.

There are three locations, 0, 1, and 2. The minimum travel times between the locations are given by a transition matrix transitions. Transition times are not symmetric. For example, it takes 10 minutes to travel from location 0 to location 1 but 15 minutes to travel back from location 1 to location 0.

We will model this problem using noOverlap constraint with transition times.

// Travel times between locations:
int[][] transitions = {
    new[] { 0, 10, 10 },
    new[] { 15,  0, 10 },
    new[] {  5,  5,  0 },
};
// Tasks to be scheduled:
var tasks = new[] {
    (location: 0, length: 20, earliest: 0, deadline: 100),
    (location: 0, length: 40, earliest: 70, deadline: 200),
    (location: 1, length: 10, earliest: 0, deadline: 200),
    (location: 1, length: 30, earliest: 100, deadline: 200),
    (location: 1, length: 10, earliest: 0, deadline: 150),
    (location: 2, length: 15, earliest: 50, deadline: 250),
    (location: 2, length: 10, earliest: 20, deadline: 60),
    (location: 2, length: 20, earliest: 110, deadline: 250),
};

var model = new Model();

var taskVars = tasks.Select((t, i) => model.IntervalVar(
    name: $"Task{i}", length: t.length,
    start: (t.earliest, null), end: (null, t.deadline)
)).ToArray();
var types = tasks.Select(t => t.location).ToArray();

// Create the sequence variable for the tasks, location is the type:
var sequence = model.SequenceVar(taskVars, types);
// Tasks must not overlap and transitions must be respected:
sequence.NoOverlap(transitions);

// Solve the model:
var result = model.Solve(new Parameters { solutionLimit = 1 });