Span Constraint

The span constraint enforces that a parent interval covers all present child intervals. The parent starts when the earliest present child starts and ends when the latest present child ends.

Signature

Python

model.span(
    parent: IntervalVar,
    children: Iterable[IntervalVar]
) -> Constraint

TypeScript

model.span(
    parent: IntervalVar,
    children: IntervalVar[]
): Constraint

Parameters:

• parent: The parent interval that spans the children
• children: The child intervals (may be optional)

Returns: Constraint (auto-registered with the model)

Semantics

The parent is present iff at least one child is present. When present, the parent starts at the earliest child start and ends at the latest child end.

Formally, let $p$ be the parent interval and $c_1, \ldots, c_n$ be the children:

$$\begin{aligned} \text{present}(p) &\Leftrightarrow \sum_{i=1}^{n} \text{present}(c_i) \geq 1 \\ \text{present}(p) &\Rightarrow \text{start}(p) = \min_{i : \text{present}(c_i)} \text{start}(c_i) \\ \text{present}(p) &\Rightarrow \text{end}(p) = \max_{i : \text{present}(c_i)} \text{end}(c_i) \end{aligned}$$

When Not to Use Span

If you know which child is first and which is last, use startAtStart and endAtEnd instead of span. This gives the solver more information:

Python

# Instead of span when order is known:
parent.start_at_start(first_child)
parent.end_at_end(last_child)

TypeScript

// Instead of span when order is known:
parent.startAtStart(firstChild);
parent.endAtEnd(lastChild);

If you only need the latest end (e.g., makespan), compute it directly:

Python

# Makespan without span:
model.minimize(model.max([c.end() for c in children]))

TypeScript

// Makespan without span:
model.minimize(model.max(children.map(c => c.end())));

Set Parent Length Bounds

The solver may have difficulty determining the minimum length of the parent interval. If you know bounds, set them explicitly:

Python

# Help the solver by setting length bounds
parent = model.interval_var(length=(min_total, max_total), name="parent")

TypeScript

// Help the solver by setting length bounds
const parent = model.intervalVar({ length: [minTotal, maxTotal], name: "parent" });

Basic Usage

Python

import optalcp as cp

model = cp.Model()

# Parent interval
project = model.interval_var(name="project")

# Child intervals (phases)
phase1 = model.interval_var(length=10, name="phase1")
phase2 = model.interval_var(length=20, name="phase2")
phase3 = model.interval_var(length=15, name="phase3")

# Project spans all phases
model.span(project, [phase1, phase2, phase3])

# Minimize project duration
model.minimize(project.length())

TypeScript

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

const model = new CP.Model();

// Parent interval
const project = model.intervalVar({ name: "project" });

// Child intervals (phases)
const phase1 = model.intervalVar({ length: 10, name: "phase1" });
const phase2 = model.intervalVar({ length: 20, name: "phase2" });
const phase3 = model.intervalVar({ length: 15, name: "phase3" });

// Project spans all phases
model.span(project, [phase1, phase2, phase3]);

// Minimize project duration
model.minimize(project.length());

Use Cases

Optional Children

Handle optional children where only present children affect the parent:

Python

# Parent spans only selected children
parent = model.interval_var(name="parent")

# Optional children
optional_tasks = [
    model.interval_var(length=10, optional=True, name=f"optional_{i}")
    for i in range(5)
]

model.span(parent, optional_tasks)

# At least 2 tasks must be selected
num_selected = model.sum([t.presence() for t in optional_tasks])
model.enforce(num_selected >= 2)

# If parent is absent (no children selected), objective is 0
objective = parent.length().guard(0)
model.minimize(objective)

TypeScript

// Parent spans only selected children
const parent = model.intervalVar({ name: "parent" });

// Optional children
const optionalTasks = Array.from({ length: 5 }, (_, i) =>
    model.intervalVar({ length: 10, optional: true, name: `optional_${i}` })
);

model.span(parent, optionalTasks);

// At least 2 tasks must be selected
const numSelected = model.sum(optionalTasks.map(t => t.presence()));
model.enforce(numSelected.ge(2));

// If parent is absent (no children selected), objective is 0
const objective = parent.length().guard(0);
model.minimize(objective);

Resource Occupation

A job occupies storage space for its entire duration, even between operations. Operations run on machines (with noOverlap), but the job's span determines how long it occupies the storage:

Python

# Job occupies storage from first to last operation
job = model.interval_var(name="job")

# Operations can run in any order (solver decides)
op1 = model.interval_var(length=20, name="op1")
op2 = model.interval_var(length=15, name="op2")
op3 = model.interval_var(length=25, name="op3")

# Job spans all operations
model.span(job, [op1, op2, op3])

# Operations share a machine (order determined by solver)
model.no_overlap([op1, op2, op3])

# Storage has limited capacity - jobs cannot overlap
other_job = model.interval_var(name="other_job")
# ... define other_job's operations and span ...
model.no_overlap([job, other_job])

TypeScript

// Job occupies storage from first to last operation
const job = model.intervalVar({ name: "job" });

// Operations can run in any order (solver decides)
const op1 = model.intervalVar({ length: 20, name: "op1" });
const op2 = model.intervalVar({ length: 15, name: "op2" });
const op3 = model.intervalVar({ length: 25, name: "op3" });

// Job spans all operations
model.span(job, [op1, op2, op3]);

// Operations share a machine (order determined by solver)
model.noOverlap([op1, op2, op3]);

// Storage has limited capacity - jobs cannot overlap
const otherJob = model.intervalVar({ name: "other_job" });
// ... define otherJob's operations and span ...
model.noOverlap([job, otherJob]);

Hierarchical Scheduling

Model nested project structure where the project interval can represent resource usage:

Python

# Top-level project (could be used in noOverlap for shared resources)
project = model.interval_var(name="project")

# Sub-projects
subproject1 = model.interval_var(name="subproject1")
subproject2 = model.interval_var(name="subproject2")

# Tasks in subproject1
sub1_tasks = [
    model.interval_var(length=10, name=f"sub1_task_{i}")
    for i in range(3)
]
model.span(subproject1, sub1_tasks)

# Tasks in subproject2
sub2_tasks = [
    model.interval_var(length=15, name=f"sub2_task_{i}")
    for i in range(4)
]
model.span(subproject2, sub2_tasks)

# Project spans both subprojects
model.span(project, [subproject1, subproject2])

# The project interval can now be used for resource constraints,
# e.g., model.no_overlap([project, other_project])

TypeScript

// Top-level project (could be used in noOverlap for shared resources)
const project = model.intervalVar({ name: "project" });

// Sub-projects
const subproject1 = model.intervalVar({ name: "subproject1" });
const subproject2 = model.intervalVar({ name: "subproject2" });

// Tasks in subproject1
const sub1Tasks = Array.from({ length: 3 }, (_, i) =>
    model.intervalVar({ length: 10, name: `sub1_task_${i}` })
);
model.span(subproject1, sub1Tasks);

// Tasks in subproject2
const sub2Tasks = Array.from({ length: 4 }, (_, i) =>
    model.intervalVar({ length: 15, name: `sub2_task_${i}` })
);
model.span(subproject2, sub2Tasks);

// Project spans both subprojects
model.span(project, [subproject1, subproject2]);

// The project interval can now be used for resource constraints,
// e.g., model.noOverlap([project, otherProject])

Difference from Alternative

While both span and alternative relate a parent to children, they serve different purposes:

Constraint	Semantics	Use Case
span	Parent covers all present children	Resource occupation, hierarchical scheduling, optional selection
alternative	Exactly one child is present	Machine selection, mode choice

Python

# Span: parent covers ALL present children
parent_span = model.interval_var(name="parent_span")
children = [model.interval_var(length=10) for _ in range(3)]
model.span(parent_span, children)
# parent_span covers all 3 children

# Alternative: exactly ONE child present
parent_alt = model.interval_var(name="parent_alt")
options = [model.interval_var(length=10, optional=True) for _ in range(3)]
model.alternative(parent_alt, options)
# Exactly 1 of the 3 options is present

TypeScript

// Span: parent covers ALL present children
const parentSpan = model.intervalVar({ name: "parent_span" });
const children = Array.from({ length: 3 }, () => model.intervalVar({ length: 10 }));
model.span(parentSpan, children);
// parentSpan covers all 3 children

// Alternative: exactly ONE child present
const parentAlt = model.intervalVar({ name: "parent_alt" });
const options = Array.from({ length: 3 }, () =>
    model.intervalVar({ length: 10, optional: true })
);
model.alternative(parentAlt, options);
// Exactly 1 of the 3 options is present

Edge Cases

All Children Absent

If all children are absent, the parent is also absent:

Python

parent = model.interval_var(optional=True, name="parent")
children = [
    model.interval_var(length=10, optional=True)
    for _ in range(3)
]

model.span(parent, children)

# Force all children absent
for child in children:
    child.optional = None

# parent is now also absent
result = model.solve()
assert not result.solution.is_present(parent)

TypeScript

const parent = model.intervalVar({ optional: true, name: "parent" });
const children = Array.from({ length: 3 }, () =>
    model.intervalVar({ length: 10, optional: true })
);

model.span(parent, children);

// Force all children absent
children.forEach(child => child.optional = null);

// parent is now also absent
const result = await model.solve();
console.assert(!result.solution.isPresent(parent));

Single Child

Span works with a single child (parent equals child):

Python

parent = model.interval_var(name="parent")
child = model.interval_var(length=10, name="child")

model.span(parent, [child])

# parent.start() == child.start()
# parent.end() == child.end()
# parent.length() == child.length()

TypeScript

const parent = model.intervalVar({ name: "parent" });
const child = model.intervalVar({ length: 10, name: "child" });

model.span(parent, [child]);

// parent.start() == child.start()
// parent.end() == child.end()
// parent.length() == child.length()

Reading the Solution

Python

result = model.solve()

if result.solution:
    if result.solution.is_present(parent):
        parent_start = result.solution.get_start(parent)
        parent_end = result.solution.get_end(parent)
        parent_length = result.solution.get_end(parent) - result.solution.get_start(parent)

        print(f"Parent: {parent_start}-{parent_end} (length: {parent_length})")

        # Check children
        for i, child in enumerate(children):
            if result.solution.is_present(child):
                child_start = result.solution.get_start(child)
                child_end = result.solution.get_end(child)
                print(f"  Child {i}: {child_start}-{child_end}")
    else:
        print("Parent is absent (all children absent)")

TypeScript

const result = await model.solve();

if (result.solution) {
    if (result.solution.isPresent(parent)) {
        const parentStart = result.solution.getStart(parent);
        const parentEnd = result.solution.getEnd(parent);
        // Non-null assertion: we know parent is present from the if check above,
        // but TypeScript can't infer that getStart/getEnd return non-null values
        const parentLength = parentEnd! - parentStart!;

        console.log(`Parent: ${parentStart}-${parentEnd} (length: ${parentLength})`);

        // Check children
        children.forEach((child, i) => {
            if (result.solution.isPresent(child)) {
                const childStart = result.solution.getStart(child);
                const childEnd = result.solution.getEnd(child);
                console.log(`  Child ${i}: ${childStart}-${childEnd}`);
            }
        });
    } else {
        console.log("Parent is absent (all children absent)");
    }
}

Complete Example

Two jobs compete for limited storage space. Each job has operations on a shared machine, but occupies storage for its entire span:

Python

import optalcp as cp

model = cp.Model()

# Job 1: two operations
job1 = model.interval_var(name="job1")
job1_op1 = model.interval_var(length=20, name="job1_op1")
job1_op2 = model.interval_var(length=15, name="job1_op2")
model.span(job1, [job1_op1, job1_op2])

# Job 2: two operations
job2 = model.interval_var(name="job2")
job2_op1 = model.interval_var(length=25, name="job2_op1")
job2_op2 = model.interval_var(length=10, name="job2_op2")
model.span(job2, [job2_op1, job2_op2])

# All operations share a single machine
model.no_overlap([job1_op1, job1_op2, job2_op1, job2_op2])

# Storage can only hold one job at a time
model.no_overlap([job1, job2])

# Minimize total completion time
model.minimize(model.max([job1.end(), job2.end()]))

result = model.solve()
if result.solution:
    for job, ops in [(job1, [job1_op1, job1_op2]), (job2, [job2_op1, job2_op2])]:
        print(f"{job.name}: {result.solution.get_start(job)}-{result.solution.get_end(job)}")
        for op in ops:
            print(f"  {op.name}: {result.solution.get_start(op)}-{result.solution.get_end(op)}")

TypeScript

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

const model = new CP.Model();

// Job 1: two operations
const job1 = model.intervalVar({ name: "job1" });
const job1Op1 = model.intervalVar({ length: 20, name: "job1_op1" });
const job1Op2 = model.intervalVar({ length: 15, name: "job1_op2" });
model.span(job1, [job1Op1, job1Op2]);

// Job 2: two operations
const job2 = model.intervalVar({ name: "job2" });
const job2Op1 = model.intervalVar({ length: 25, name: "job2_op1" });
const job2Op2 = model.intervalVar({ length: 10, name: "job2_op2" });
model.span(job2, [job2Op1, job2Op2]);

// All operations share a single machine
model.noOverlap([job1Op1, job1Op2, job2Op1, job2Op2]);

// Storage can only hold one job at a time (span constraint is essential here)
model.noOverlap([job1, job2]);

// Minimize total completion time
model.minimize(model.max([job1.end(), job2.end()]));

const result = await model.solve();
if (result.solution) {
    for (const [job, ops] of [[job1, [job1Op1, job1Op2]], [job2, [job2Op1, job2Op2]]] as const) {
        console.log(`${job.name}: ${result.solution.getStart(job)}-${result.solution.getEnd(job)}`);
        for (const op of ops) {
            console.log(`  ${op.name}: ${result.solution.getStart(op)}-${result.solution.getEnd(op)}`);
        }
    }
}

See Also

• Intervals — Optional intervals and presence semantics
• Alternative — Alternative constraint for exclusive choices
• Constraints — Constraint types and enforcement
• Expressions — Using parent/child expressions