Class: SequenceVar

Ordered sequence of intervals for routing and sequencing problems.

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

• 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.

Extends

• ModelElement

Accessors

name

Get Signature

get name(): string | undefined

The name assigned to this model element.

Remarks

The name is optional and primarily useful for debugging purposes. When set, it helps identify the element in solver logs, error messages, and when inspecting solutions.

Names can be assigned to any model element including variables, expressions, and constraints.

Example

import * as CP from "optalcp";

const model = new CP.Model();

// Name a variable at creation
const task = model.intervalVar({ length: 10, name: "assembly" });

// Or set name later
const x = model.intVar({ min: 0, max: 100 });
x.name = "quantity";

console.log(task.name);  // "assembly"
console.log(x.name);     // "quantity"

Returns

string | undefined

Set Signature

set name(value: string): void

Parameters

Parameter	Type
value	string

Returns

void

Inherited from

ModelElement.name

Constructors

Constructor

new SequenceVar(): SequenceVar

Returns

SequenceVar

Inherited from

ModelElement.constructor

Methods

noOverlap()

noOverlap(transitions?: number[][]): Constraint

Constrain the interval variables forming the sequence to not overlap.

Parameters

Parameter	Type	Description
transitions?	number[][]	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:
let transitions = [
  [ 0, 10, 10],
  [15,  0, 10],
  [ 5,  5,  0]
];
// Tasks to be scheduled:
const tasks = [
  {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},
];

let model = new CP.Model;

// From the array tasks create an array of interval variables:
let taskVars = tasks.map((t, i) => model.intervalVar(
  { name: "Task" + i, length: t.length, start: [t.earliest,], end: [, t.deadline] }
));
// And an array of locations:
let types = tasks.map(t => t.location);

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

// Solve the model:
let result = await model.solve({ solutionLimit: 1 });