No Overlap Constraints

The no_overlap constraint ensures that a set of interval variables do not overlap in time. This is used for disjunctive resources - resources that can handle only one task at a time.

Basic Usage

The simplest form takes a list of intervals:

Python
TypeScript

import optalcp as cp

model = cp.Model()

task1 = model.interval_var(length=10, name="task1")
task2 = model.interval_var(length=15, name="task2")
task3 = model.interval_var(length=20, name="task3")

# These tasks cannot overlap
model.no_overlap([task1, task2, task3])

model.minimize(model.max([task1.end(), task2.end(), task3.end()]))
result = model.solve()

if result.solution:
    print(f"Task1: [{result.solution.get_start(task1)}, {result.solution.get_end(task1)})")
    print(f"Task2: [{result.solution.get_start(task2)}, {result.solution.get_end(task2)})")
    print(f"Task3: [{result.solution.get_start(task3)}, {result.solution.get_end(task3)})")

import * as CP from '@scheduleopt/optalcp';

const model = new CP.Model();

const task1 = model.intervalVar({ length: 10, name: "task1" });
const task2 = model.intervalVar({ length: 15, name: "task2" });
const task3 = model.intervalVar({ length: 20, name: "task3" });

// These tasks cannot overlap
model.noOverlap([task1, task2, task3]);

model.minimize(model.max([task1.end(), task2.end(), task3.end()]));
const result = await model.solve();

if (result.solution) {
    console.log(`Task1: [${result.solution.getStart(task1)}, ${result.solution.getEnd(task1)})`);
    console.log(`Task2: [${result.solution.getStart(task2)}, ${result.solution.getEnd(task2)})`);
    console.log(`Task3: [${result.solution.getStart(task3)}, ${result.solution.getEnd(task3)})`);
}

Signature

Python
TypeScript

model.no_overlap(
    intervals: Iterable[IntervalVar],
    transitions: Iterable[Iterable[int]] | None = None
) -> Constraint

model.noOverlap(
    intervals: IntervalVar[],
    transitions?: number[][]
): Constraint

Parameters:

intervals: Interval variables that must not overlap
transitions: Optional transition time matrix (see Transition Times)

Returns: Constraint object (auto-registered with the model)

Semantics

Intervals are scheduled sequentially with no time overlap
The order is determined by the solver
If an interval is optional and absent, it is not part of the sequence
There is no enforced ordering beyond non-overlap (use precedence constraints for that)

Sequence Variables

For more control over task ordering, use a SequenceVar:

Python
TypeScript

import optalcp as cp

model = cp.Model()

task1 = model.interval_var(length=10, name="task1")
task2 = model.interval_var(length=15, name="task2")
task3 = model.interval_var(length=20, name="task3")

# Create sequence variable
seq = model.sequence_var([task1, task2, task3])

# No overlap constraint using sequence
model.no_overlap(seq)

# Query position in sequence (0-indexed)
pos1 = task1.position(seq)

# Example: task1 must be scheduled in the first two positions
model.enforce(pos1 <= 1)

result = model.solve()

import * as CP from '@scheduleopt/optalcp';

const model = new CP.Model();

const task1 = model.intervalVar({ length: 10, name: "task1" });
const task2 = model.intervalVar({ length: 15, name: "task2" });
const task3 = model.intervalVar({ length: 20, name: "task3" });

// Create sequence variable
const seq = model.sequenceVar([task1, task2, task3]);

// No overlap constraint using sequence
model.noOverlap(seq);

// Query position in sequence (0-indexed)
const pos1 = task1.position(seq);

// Example: task1 must be scheduled in the first two positions
model.enforce(pos1.le(1));

const result = await model.solve();

SequenceVar Signature

Python
TypeScript

model.sequence_var(
    intervals: Iterable[IntervalVar],
    types: Iterable[int] | None = None,
    name: str | None = None
) -> SequenceVar

model.sequenceVar(
    intervals: IntervalVar[],
    types?: number[],
    name?: string
): SequenceVar

Parameters:

intervals: Interval variables in the sequence
types: Optional type index for each interval (used with transition times)
name: Optional name for the sequence variable

Returns: SequenceVar object

Requirement: Each SequenceVar must be used by exactly one no_overlap constraint.

position() Function

Python
TypeScript

interval.position(sequence: SequenceVar) -> IntExpr
# Or equivalently:
model.position(interval: IntervalVar, sequence: SequenceVar) -> IntExpr

interval.position(sequence: SequenceVar): IntExpr
// Or equivalently:
model.position(interval: IntervalVar, sequence: SequenceVar): IntExpr

Returns: Integer expression representing the 0-indexed position of the interval in the sequence.

Behavior: If the interval is optional and absent, the position expression is also absent.

Limitations:

Cannot be used with intervals that may have zero length (position of simultaneous zero-length intervals is undefined)
Cannot be used when the no_overlap constraint has transition times

Python
TypeScript

# Optional intervals in sequence
task_a = model.interval_var(length=10, optional=True, name="task_a")
task_b = model.interval_var(length=15, optional=True, name="task_b")

seq = model.sequence_var([task_a, task_b])
model.no_overlap(seq)

pos_a = task_a.position(seq)

# If task_a is present, it must be first (position 0)
# When task_a is absent, pos_a is absent and the constraint is satisfied
model.enforce(pos_a == 0)

// Optional intervals in sequence
const taskA = model.intervalVar({ length: 10, optional: true, name: "task_a" });
const taskB = model.intervalVar({ length: 15, optional: true, name: "task_b" });

const seq = model.sequenceVar([taskA, taskB]);
model.noOverlap(seq);

const posA = taskA.position(seq);

// If taskA is present, it must be first (position 0)
// When taskA is absent, posA is absent and the constraint is satisfied
model.enforce(posA.eq(0));

Transition Times

Transition times model setup or changeover times between consecutive tasks. The transition time is added between the end of one task and the start of the next.

Basic Transition Times

Provide a square matrix where transitions[i][j] is the time required between task i and task j:

Python
TypeScript

import optalcp as cp

model = cp.Model()

task1 = model.interval_var(length=10, name="task1")
task2 = model.interval_var(length=15, name="task2")
task3 = model.interval_var(length=20, name="task3")

# Transition time matrix (3x3 for 3 tasks)
transitions = [
    [0, 5, 10],   # From task1 to task1/task2/task3
    [8, 0, 3],    # From task2 to task1/task2/task3
    [12, 7, 0],   # From task3 to task1/task2/task3
]

model.no_overlap([task1, task2, task3], transitions)

result = model.solve()

import * as CP from '@scheduleopt/optalcp';

const model = new CP.Model();

const task1 = model.intervalVar({ length: 10, name: "task1" });
const task2 = model.intervalVar({ length: 15, name: "task2" });
const task3 = model.intervalVar({ length: 20, name: "task3" });

// Transition time matrix (3x3 for 3 tasks)
const transitions = [
    [0, 5, 10],   // From task1 to task1/task2/task3
    [8, 0, 3],    // From task2 to task1/task2/task3
    [12, 7, 0],   // From task3 to task1/task2/task3
];

model.noOverlap([task1, task2, task3], transitions);

const result = await model.solve();

Matrix requirements:

Square matrix: N×N where N is the number of intervals
transitions[i][j] ≥ 0 for all i, j
Diagonal entries (same task to itself) are typically 0 but can be non-zero

Semantics:

For any pair of tasks i and j where task i precedes task j in the sequence, then task_i.end() + transitions[i][j] <= task_j.start()
This applies to all pairs, not just consecutive tasks. For example, if the sequence is A → B → C, then both A.end() + transitions[A][C] <= C.start() and A.end() + transitions[A][B] <= B.start() must hold.

Type-Based Transition Times

For tasks with types (e.g., job types, colors, tools), use the types parameter to reduce matrix size:

Python
TypeScript

import optalcp as cp

model = cp.Model()

# 5 tasks with 3 different types
task1 = model.interval_var(length=10, name="task1")  # Type 0
task2 = model.interval_var(length=15, name="task2")  # Type 1
task3 = model.interval_var(length=12, name="task3")  # Type 0
task4 = model.interval_var(length=18, name="task4")  # Type 2
task5 = model.interval_var(length=14, name="task5")  # Type 1

# Task types (parallel to intervals list)
types = [0, 1, 0, 2, 1]

# Type-based transition matrix (3x3 for 3 types)
transitions = [
    [0, 10, 15],   # From type 0 to type 0/1/2
    [12, 0, 8],    # From type 1 to type 0/1/2
    [20, 5, 0],    # From type 2 to type 0/1/2
]

seq = model.sequence_var([task1, task2, task3, task4, task5], types)
model.no_overlap(seq, transitions)

result = model.solve()

import * as CP from '@scheduleopt/optalcp';

const model = new CP.Model();

// 5 tasks with 3 different types
const task1 = model.intervalVar({ length: 10, name: "task1" });  // Type 0
const task2 = model.intervalVar({ length: 15, name: "task2" });  // Type 1
const task3 = model.intervalVar({ length: 12, name: "task3" });  // Type 0
const task4 = model.intervalVar({ length: 18, name: "task4" });  // Type 2
const task5 = model.intervalVar({ length: 14, name: "task5" });  // Type 1

// Task types (parallel to intervals list)
const types = [0, 1, 0, 2, 1];

// Type-based transition matrix (3x3 for 3 types)
const transitions = [
    [0, 10, 15],   // From type 0 to type 0/1/2
    [12, 0, 8],    // From type 1 to type 0/1/2
    [20, 5, 0],    // From type 2 to type 0/1/2
];

const seq = model.sequenceVar([task1, task2, task3, task4, task5], types);
model.noOverlap(seq, transitions);

const result = await model.solve();

Usage:

types must be a list parallel to intervals, with type index for each interval
Type indices must be in range [0, num_types)
Transition matrix is num_types × num_types
Significantly reduces matrix size for large problems with few types

Use Cases

Machine Scheduling

A single machine processes multiple jobs:

Python
TypeScript

jobs = [model.interval_var(length=durations[i], name=f"job{i}")
        for i in range(num_jobs)]
model.no_overlap(jobs)

const jobs = Array.from({ length: numJobs }, (_, i) =>
    model.intervalVar({ length: durations[i], name: `job${i}` })
);
model.noOverlap(jobs);

Resource Scheduling with Setup Times

Painting tasks with cleaning time between different colors:

Python
TypeScript

# Paint colors: 0=red, 1=blue, 2=green
types = [0, 0, 1, 2, 1, 0]  # Color for each task

# Cleaning times between colors
cleaning_times = [
    [0, 10, 15],   # Red to red/blue/green
    [10, 0, 12],   # Blue to red/blue/green
    [15, 12, 0],   # Green to red/blue/green
]

seq = model.sequence_var(paint_tasks, types)
model.no_overlap(seq, cleaning_times)

// Paint colors: 0=red, 1=blue, 2=green
const types = [0, 0, 1, 2, 1, 0];  // Color for each task

// Cleaning times between colors
const cleaningTimes = [
    [0, 10, 15],   // Red to red/blue/green
    [10, 0, 12],   // Blue to red/blue/green
    [15, 12, 0],   // Green to red/blue/green
];

const seq = model.sequenceVar(paintTasks, types);
model.noOverlap(seq, cleaningTimes);

Ordering Constraints

Enforce specific orderings using position():

Python
TypeScript

seq = model.sequence_var(tasks)
model.no_overlap(seq)

# Task C must be first or last
pos_c = task_c.position(seq)
model.enforce((pos_c == 0) | (pos_c == len(tasks) - 1))

const seq = model.sequenceVar(tasks);
model.noOverlap(seq);

// Task C must be first or last
const posC = taskC.position(seq);
model.enforce(posC.eq(0).or(posC.eq(tasks.length - 1)));

Use Precedence for Simple Ordering

If you only need "task A before task B", use precedence constraints instead of position():

Python
TypeScript

# BAD: using position() for simple ordering
seq = model.sequence_var(tasks)
model.no_overlap(seq)
model.enforce(task_a.position(seq) < task_b.position(seq))

# GOOD: use precedence constraint
task_a.end_before_start(task_b)

// BAD: using position() for simple ordering
const seq = model.sequenceVar(tasks);
model.noOverlap(seq);
model.enforce(taskA.position(seq).lt(taskB.position(seq)));

// GOOD: use precedence constraint
taskA.endBeforeStart(taskB);

Precedence constraints are simpler and propagate more efficiently. Use position() when you need to synchronize positions across two sequences or constrain the actual position value.

Synchronizing Two Sequences

Use position() when tasks must maintain the same order on two different machines:

Python
TypeScript

# Jobs visit machine A then machine B
# Jobs must be processed in the same order on both machines

jobs_on_a = [model.interval_var(length=10, name=f"job{i}_A") for i in range(5)]
jobs_on_b = [model.interval_var(length=15, name=f"job{i}_B") for i in range(5)]

seq_a = model.sequence_var(jobs_on_a)
seq_b = model.sequence_var(jobs_on_b)

model.no_overlap(seq_a)
model.no_overlap(seq_b)

# Synchronize: same position on both machines
for i in range(5):
    model.enforce(jobs_on_a[i].position(seq_a) == jobs_on_b[i].position(seq_b))

// Jobs visit machine A then machine B
// Jobs must be processed in the same order on both machines

const jobsOnA = Array.from({ length: 5 }, (_, i) =>
    model.intervalVar({ length: 10, name: `job${i}_A` })
);
const jobsOnB = Array.from({ length: 5 }, (_, i) =>
    model.intervalVar({ length: 15, name: `job${i}_B` })
);

const seqA = model.sequenceVar(jobsOnA);
const seqB = model.sequenceVar(jobsOnB);

model.noOverlap(seqA);
model.noOverlap(seqB);

// Synchronize: same position on both machines
for (let i = 0; i < 5; i++) {
    model.enforce(jobsOnA[i].position(seqA).eq(jobsOnB[i].position(seqB)));
}

Edge Cases

Empty Interval List

An empty list is valid and creates a trivially satisfied constraint:

Python
TypeScript

model.no_overlap([])  # Valid, no effect

model.noOverlap([]);  // Valid, no effect

Single Interval

A single interval is valid and creates a trivially satisfied constraint:

Python
TypeScript

model.no_overlap([task])  # Valid, always satisfied

model.noOverlap([task]);  // Valid, always satisfied

All Intervals Absent

If all intervals in a no_overlap constraint are optional and absent, the constraint is satisfied:

Python
TypeScript

task1 = model.interval_var(length=10, optional=True)
task2 = model.interval_var(length=15, optional=True)

model.no_overlap([task1, task2])
task1.optional = None
task2.optional = None

result = model.solve()  # Feasible

const task1 = model.intervalVar({ length: 10, optional: true });
const task2 = model.intervalVar({ length: 15, optional: true });

model.noOverlap([task1, task2]);
task1.optional = null;
task2.optional = null;

const result = await model.solve();  // Feasible

Transition Matrix Dimension Mismatch

The transition matrix must match the number of intervals (or types):

Python
TypeScript

# ERROR: 3 tasks but 2x2 matrix
tasks = [task1, task2, task3]
transitions = [[0, 5], [5, 0]]
model.no_overlap(tasks, transitions=transitions)  # Runtime error

// ERROR: 3 tasks but 2x2 matrix
const tasks = [task1, task2, task3];
const transitions = [[0, 5], [5, 0]];
model.noOverlap(tasks, transitions);  // Runtime error

Performance Considerations

Propagation level: Controlled by noOverlapPropagationLevel parameter (1-4, default 4)
- Level 1: Basic timetabling
- Level 4: Full propagation (slowest but strongest)
- Reduce for very large problems
Transition times: Add complexity to the constraint
- Use type-based transitions to reduce matrix size
- Consider modeling as separate precedence constraints if transitions are sparse
Sequence variables: No overhead - a sequence variable is created automatically when not specified by the user

Basic Usage​

Signature​

Semantics​

Sequence Variables​

SequenceVar Signature​

position() Function​

Transition Times​

Basic Transition Times​

Type-Based Transition Times​

Use Cases​

Machine Scheduling​

Resource Scheduling with Setup Times​

Ordering Constraints​

Synchronizing Two Sequences​

Edge Cases​

Empty Interval List​

Single Interval​

All Intervals Absent​

Transition Matrix Dimension Mismatch​

Performance Considerations​

See also​