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

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)})")

C#

using OptalCP;

var model = new Model();

var task1 = model.IntervalVar(length: 10, name: "task1");
var task2 = model.IntervalVar(length: 15, name: "task2");
var task3 = model.IntervalVar(length: 20, name: "task3");

// These tasks cannot overlap
model.NoOverlap(new[] { task1, task2, task3 });

model.Minimize(model.Max(new[] { task1.End(), task2.End(), task3.End() }));
var result = model.Solve();

if (result.Solution != null)
{
    Console.WriteLine($"Task1: [{result.Solution.GetStart(task1)}, {result.Solution.GetEnd(task1)})");
    Console.WriteLine($"Task2: [{result.Solution.GetStart(task2)}, {result.Solution.GetEnd(task2)})");
    Console.WriteLine($"Task3: [{result.Solution.GetStart(task3)}, {result.Solution.GetEnd(task3)})");
}

TypeScript

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

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

C#

model.NoOverlap(
    IEnumerable<IntervalVar> intervals,
    int[][]? transitions = null
): Constraint

TypeScript

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

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()

C#

using OptalCP;

var model = new Model();

var task1 = model.IntervalVar(length: 10, name: "task1");
var task2 = model.IntervalVar(length: 15, name: "task2");
var task3 = model.IntervalVar(length: 20, name: "task3");

// Create sequence variable
var seq = model.SequenceVar(new[] { task1, task2, task3 });

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

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

// Example: task1 must be scheduled in the first two positions
model.Enforce(pos1 <= 1);

var result = model.Solve();

TypeScript

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

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

C#

model.SequenceVar(
    IEnumerable<IntervalVar> intervals,
    IEnumerable<int>? types = null,
    string? name = null
): SequenceVar

TypeScript

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

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

C#

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

TypeScript

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

# 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)

C#

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

var seq = model.SequenceVar(new[] { taskA, taskB });
model.NoOverlap(seq);

var 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 == 0);

TypeScript

// 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

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()

C#

using OptalCP;

var model = new Model();

var task1 = model.IntervalVar(length: 10, name: "task1");
var task2 = model.IntervalVar(length: 15, name: "task2");
var task3 = model.IntervalVar(length: 20, name: "task3");

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

model.NoOverlap(new[] { task1, task2, task3 }, transitions);

var result = model.Solve();

TypeScript

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

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()

C#

using OptalCP;

var model = new Model();

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

// Task types (parallel to intervals list)
var types = new[] { 0, 1, 0, 2, 1 };

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

var seq = model.SequenceVar(new[] { task1, task2, task3, task4, task5 }, types);
model.NoOverlap(seq, transitions);

var result = model.Solve();

TypeScript

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

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

C#

var jobs = Enumerable.Range(0, numJobs)
    .Select(i => model.IntervalVar(length: durations[i], name: $"job{i}"))
    .ToArray();
model.NoOverlap(jobs);

TypeScript

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

# 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)

C#

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

// Cleaning times between colors
var cleaningTimes = new int[][]
{
    new[] { 0, 10, 15 },   // Red to red/blue/green
    new[] { 10, 0, 12 },   // Blue to red/blue/green
    new[] { 15, 12, 0 },   // Green to red/blue/green
};

var seq = model.SequenceVar(paintTasks, types);
model.NoOverlap(seq, cleaningTimes);

TypeScript

// 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

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))

C#

var seq = model.SequenceVar(tasks);
model.NoOverlap(seq);

// Task C must be first or last
var posC = taskC.Position(seq);
model.Enforce((posC == 0) | (posC == tasks.Length - 1));

TypeScript

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

# 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)

C#

// BAD: using position() for simple ordering
var seq = model.SequenceVar(tasks);
model.NoOverlap(seq);
model.Enforce(taskA.Position(seq) < taskB.Position(seq));

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

TypeScript

// 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

# 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))

C#

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

var jobsOnA = Enumerable.Range(0, 5)
    .Select(i => model.IntervalVar(length: 10, name: $"job{i}_A"))
    .ToArray();
var jobsOnB = Enumerable.Range(0, 5)
    .Select(i => model.IntervalVar(length: 15, name: $"job{i}_B"))
    .ToArray();

var seqA = model.SequenceVar(jobsOnA);
var seqB = model.SequenceVar(jobsOnB);

model.NoOverlap(seqA);
model.NoOverlap(seqB);

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

TypeScript

// 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

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

C#

model.NoOverlap(Array.Empty<IntervalVar>());  // Valid, no effect

TypeScript

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

Single Interval

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

Python

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

C#

model.NoOverlap(new[] { task });  // Valid, always satisfied

TypeScript

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

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

model.no_overlap([task1, task2])
model.enforce(~task1.presence())
model.enforce(~task2.presence())

result = model.solve()  # Feasible

C#

var task1 = model.IntervalVar(length: 10, optional: true);
var task2 = model.IntervalVar(length: 15, optional: true);

model.NoOverlap(new[] { task1, task2 });
model.Enforce(!task1.Presence());
model.Enforce(!task2.Presence());

var result = model.Solve();  // Feasible

TypeScript

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

model.noOverlap([task1, task2]);
model.enforce(task1.presence().not());
model.enforce(task2.presence().not());

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

Transition Matrix Dimension Mismatch

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

Python

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

C#

// ERROR: 3 tasks but 2x2 matrix
var tasks = new[] { task1, task2, task3 };
var transitions = new int[][] { new[] { 0, 5 }, new[] { 5, 0 } };
model.NoOverlap(tasks, transitions);  // Runtime error

TypeScript

// 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

See also

• Resource Types Overview - Choosing between resource types
• Cumulative Constraints - Resources with capacity > 1
• Tutorial: No Overlap - Learning path with examples
• Tutorial: Transition Times - Setup times example