Alternative Constraint

The alternative constraint models a choice between multiple optional intervals. When the main interval is present, exactly one of the option intervals must be present. When the main interval is absent, all option intervals must be absent.

Signature

Python

model.alternative(
    main: IntervalVar,
    options: Iterable[IntervalVar]
) -> Constraint

TypeScript

model.alternative(
    main: IntervalVar,
    options: IntervalVar[]
): Constraint

Parameters:

• main: The main interval (may be optional or mandatory)
• options: The alternative intervals (should be optional)

Returns: Constraint (auto-registered with the model)

Semantics

The alternative constraint enforces:

1. When main is present: Exactly one option must be present
2. When main is absent: All options must be absent
3. Start/end synchronization: The present option's start/end matches the main's start/end

Formally, let $m$ be the main interval and $o_1, \ldots, o_n$ be the options:

$$\begin{aligned} \text{present}(m) &\Leftrightarrow \sum_{i=1}^{n} \text{present}(o_i) = 1 \\ \text{present}(o_i) &\Rightarrow \text{start}(m) = \text{start}(o_i) \land \text{end}(m) = \text{end}(o_i) \end{aligned}$$

Options Should Be Optional

Option intervals should be declared optional=True. If an option is mandatory, it forces both its own presence AND the main interval's presence:

Python

# WRONG: mandatory option forces everything to be present
opt1 = model.interval_var(length=10, name="opt1")  # Missing optional=True!
opt2 = model.interval_var(length=15, optional=True, name="opt2")
model.alternative(task, [opt1, opt2])  # opt1 is always chosen

# CORRECT: all options are optional
opt1 = model.interval_var(length=10, optional=True, name="opt1")
opt2 = model.interval_var(length=15, optional=True, name="opt2")
model.alternative(task, [opt1, opt2])

TypeScript

// WRONG: mandatory option forces everything to be present
const opt1 = model.intervalVar({ length: 10, name: "opt1" });  // Missing optional!
const opt2 = model.intervalVar({ length: 15, optional: true, name: "opt2" });
model.alternative(task, [opt1, opt2]);  // opt1 is always chosen

// CORRECT: all options are optional
const opt1 = model.intervalVar({ length: 10, optional: true, name: "opt1" });
const opt2 = model.intervalVar({ length: 15, optional: true, name: "opt2" });
model.alternative(task, [opt1, opt2]);

Basic Usage

Python

import optalcp as cp

model = cp.Model()

# Main task
task = model.interval_var(name="task")

# Options: different machines with different durations
on_machine_a = model.interval_var(length=10, optional=True, name="machine_a")
on_machine_b = model.interval_var(length=15, optional=True, name="machine_b")
on_machine_c = model.interval_var(length=12, optional=True, name="machine_c")

# Exactly one machine must be chosen
model.alternative(task, [on_machine_a, on_machine_b, on_machine_c])

# Minimize completion time (chooses fastest machine)
model.minimize(task.end())

TypeScript

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

const model = new CP.Model();

// Main task
const task = model.intervalVar({ name: "task" });

// Options: different machines with different durations
const onMachineA = model.intervalVar({ length: 10, optional: true, name: "machine_a" });
const onMachineB = model.intervalVar({ length: 15, optional: true, name: "machine_b" });
const onMachineC = model.intervalVar({ length: 12, optional: true, name: "machine_c" });

// Exactly one machine must be chosen
model.alternative(task, [onMachineA, onMachineB, onMachineC]);

// Minimize completion time (chooses fastest machine)
model.minimize(task.end());

Use Cases

Machine Selection

Choose which machine processes a task:

Python

# Operation can run on multiple machines
operation = model.interval_var(name="operation")

machines = []
for machine_id in range(3):
    duration = 10 + machine_id * 5  # Different processing times
    opt = model.interval_var(
        length=duration,
        optional=True,
        name=f"on_machine_{machine_id}"
    )
    machines.append(opt)

model.alternative(operation, machines)

# Each machine has capacity constraint
for machine_id in range(3):
    machine_tasks = [machines[machine_id]]  # Collect all tasks for this machine
    model.no_overlap(machine_tasks)

TypeScript

// Operation can run on multiple machines
const operation = model.intervalVar({ name: "operation" });

const machines = [];
for (let machineId = 0; machineId < 3; machineId++) {
    const duration = 10 + machineId * 5;  // Different processing times
    const opt = model.intervalVar({
        length: duration,
        optional: true,
        name: `on_machine_${machineId}`
    });
    machines.push(opt);
}

model.alternative(operation, machines);

// Each machine has capacity constraint
for (let machineId = 0; machineId < 3; machineId++) {
    const machineTasks = [machines[machineId]];  // Collect all tasks for this machine
    model.noOverlap(machineTasks);
}

Worker Assignment

Assign tasks to workers with different skill levels:

Python

# Task that can be performed by different workers
task = model.interval_var(name="task")

# Expert worker: fast
by_expert = model.interval_var(length=10, optional=True, name="expert")

# Regular worker: medium speed
by_regular = model.interval_var(length=15, optional=True, name="regular")

# Trainee: slow
by_trainee = model.interval_var(length=25, optional=True, name="trainee")

model.alternative(task, [by_expert, by_regular, by_trainee])

# Worker availability constraints
expert_tasks = [by_expert]  # All tasks for expert
model.no_overlap(expert_tasks)

TypeScript

// Task that can be performed by different workers
const task = model.intervalVar({ name: "task" });

// Expert worker: fast
const byExpert = model.intervalVar({ length: 10, optional: true, name: "expert" });

// Regular worker: medium speed
const byRegular = model.intervalVar({ length: 15, optional: true, name: "regular" });

// Trainee: slow
const byTrainee = model.intervalVar({ length: 25, optional: true, name: "trainee" });

model.alternative(task, [byExpert, byRegular, byTrainee]);

// Worker availability constraints
const expertTasks = [byExpert];  // All tasks for expert
model.noOverlap(expertTasks);

Transportation Mode

Choose transportation method:

Python

# Delivery task
delivery = model.interval_var(name="delivery")

# By truck: slower but cheaper
by_truck = model.interval_var(length=120, optional=True, name="truck")
truck_cost = 100

# By air: faster but more expensive
by_air = model.interval_var(length=30, optional=True, name="air")
air_cost = 500

model.alternative(delivery, [by_truck, by_air])

# Objective: minimize cost
cost = (
    by_truck.presence() * truck_cost +
    by_air.presence() * air_cost
)
model.minimize(cost)

TypeScript

// Delivery task
const delivery = model.intervalVar({ name: "delivery" });

// By truck: slower but cheaper
const byTruck = model.intervalVar({ length: 120, optional: true, name: "truck" });
const truckCost = 100;

// By air: faster but more expensive
const byAir = model.intervalVar({ length: 30, optional: true, name: "air" });
const airCost = 500;

model.alternative(delivery, [byTruck, byAir]);

// Objective: minimize cost
const cost = byTruck.presence().times(truckCost).plus(
    byAir.presence().times(airCost)
);
model.minimize(cost);

Optional Main Interval

The main interval can be optional, allowing the entire choice to be absent:

Python

# Optional task
task = model.interval_var(optional=True, name="task")

# Options
option1 = model.interval_var(length=10, optional=True, name="option1")
option2 = model.interval_var(length=15, optional=True, name="option2")

model.alternative(task, [option1, option2])

# If task is absent, both options are absent
# If task is present, exactly one option is present

TypeScript

// Optional task
const task = model.intervalVar({ optional: true, name: "task" });

// Options
const option1 = model.intervalVar({ length: 10, optional: true, name: "option1" });
const option2 = model.intervalVar({ length: 15, optional: true, name: "option2" });

model.alternative(task, [option1, option2]);

// If task is absent, both options are absent
// If task is present, exactly one option is present

Constrain the Main Interval

Use the main interval in constraints and objectives whenever possible—not the individual options. This has two benefits:

1. Simpler model: Write one constraint instead of duplicating for each option
2. Better performance: The solver propagates constraints more effectively through the main interval

Python

# Precedence uses the main interval, not options
cut.end_before_start(sand)  # Works regardless of which sanding method
sand.end_before_start(assemble)

TypeScript

// Precedence uses the main interval, not options
cut.endBeforeStart(sand);  // Works regardless of which sanding method
sand.endBeforeStart(assemble);

Constrain option intervals only when the constraint is specific to that option (e.g., machine-specific no-overlap).

Combining with Other Constraints

Python

# Task with alternatives and precedence
task1 = model.interval_var(name="task1")
task2 = model.interval_var(name="task2")

# task1 alternatives
task1_opt1 = model.interval_var(length=10, optional=True, name="t1_opt1")
task1_opt2 = model.interval_var(length=15, optional=True, name="t1_opt2")
model.alternative(task1, [task1_opt1, task1_opt2])

# task2 alternatives
task2_opt1 = model.interval_var(length=12, optional=True, name="t2_opt1")
task2_opt2 = model.interval_var(length=18, optional=True, name="t2_opt2")
model.alternative(task2, [task2_opt1, task2_opt2])

# Precedence on main intervals
task1.end_before_start(task2, delay=5)

# Machine constraints on options
machine_a_tasks = [task1_opt1, task2_opt1]
machine_b_tasks = [task1_opt2, task2_opt2]
model.no_overlap(machine_a_tasks)
model.no_overlap(machine_b_tasks)

TypeScript

// Task with alternatives and precedence
const task1 = model.intervalVar({ name: "task1" });
const task2 = model.intervalVar({ name: "task2" });

// task1 alternatives
const task1Opt1 = model.intervalVar({ length: 10, optional: true, name: "t1_opt1" });
const task1Opt2 = model.intervalVar({ length: 15, optional: true, name: "t1_opt2" });
model.alternative(task1, [task1Opt1, task1Opt2]);

// task2 alternatives
const task2Opt1 = model.intervalVar({ length: 12, optional: true, name: "t2_opt1" });
const task2Opt2 = model.intervalVar({ length: 18, optional: true, name: "t2_opt2" });
model.alternative(task2, [task2Opt1, task2Opt2]);

// Precedence on main intervals
task1.endBeforeStart(task2, 5);

// Machine constraints on options
const machineATasks = [task1Opt1, task2Opt1];
const machineBTasks = [task1Opt2, task2Opt2];
model.noOverlap(machineATasks);
model.noOverlap(machineBTasks);

Reading the Solution

Python

result = model.solve()

if result.solution:
    # Check which option was chosen
    if result.solution.is_present(option1):
        print("Chose option 1")
        start = result.solution.get_start(option1)
        end = result.solution.get_end(option1)
        print(f"  {start}-{end}")

    elif result.solution.is_present(option2):
        print("Chose option 2")
        start = result.solution.get_start(option2)
        end = result.solution.get_end(option2)
        print(f"  {start}-{end}")

    # Main interval has same start/end as chosen option
    main_start = result.solution.get_start(task)
    main_end = result.solution.get_end(task)
    print(f"Main task: {main_start}-{main_end}")

TypeScript

const result = await model.solve();

if (result.solution) {
    // Check which option was chosen
    if (result.solution.isPresent(option1)) {
        console.log("Chose option 1");
        const start = result.solution.getStart(option1);
        const end = result.solution.getEnd(option1);
        console.log(`  ${start}-${end}`);

    } else if (result.solution.isPresent(option2)) {
        console.log("Chose option 2");
        const start = result.solution.getStart(option2);
        const end = result.solution.getEnd(option2);
        console.log(`  ${start}-${end}`);
    }

    // Main interval has same start/end as chosen option
    const mainStart = result.solution.getStart(task);
    const mainEnd = result.solution.getEnd(task);
    console.log(`Main task: ${mainStart}-${mainEnd}`);
}

Complete Example

Python

import optalcp as cp

model = cp.Model()

# Three operations, each can run on two machines
operations = []
options_by_machine = [[], []]  # Track options for each machine

for op_id in range(3):
    operation = model.interval_var(name=f"op_{op_id}")

    # Machine 0: fast
    opt0 = model.interval_var(
        length=10 + op_id * 2,
        optional=True,
        name=f"op{op_id}_m0"
    )
    options_by_machine[0].append(opt0)

    # Machine 1: slow
    opt1 = model.interval_var(
        length=15 + op_id * 3,
        optional=True,
        name=f"op{op_id}_m1"
    )
    options_by_machine[1].append(opt1)

    model.alternative(operation, [opt0, opt1])
    operations.append(operation)

# Sequential operations
for i in range(len(operations) - 1):
    operations[i].end_before_start(operations[i + 1])

# Machine capacity
model.no_overlap(options_by_machine[0])
model.no_overlap(options_by_machine[1])

# Minimize makespan
model.minimize(operations[-1].end())

# Solve
result = model.solve()
if result.solution:
    print(f"Makespan: {result.objective}")
    for op_id, operation in enumerate(operations):
        start = result.solution.get_start(operation)
        end = result.solution.get_end(operation)

        # Find which machine
        for machine_id in range(2):
            opt = options_by_machine[machine_id][op_id]
            if result.solution.is_present(opt):
                print(f"Op {op_id} on machine {machine_id}: {start}-{end}")

TypeScript

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

const model = new CP.Model();

// Three operations, each can run on two machines
const operations = [];
const optionsByMachine: CP.IntervalVar[][] = [[], []];  // Track options for each machine

for (let opId = 0; opId < 3; opId++) {
    const operation = model.intervalVar({ name: `op_${opId}` });

    // Machine 0: fast
    const opt0 = model.intervalVar({
        length: 10 + opId * 2,
        optional: true,
        name: `op${opId}_m0`
    });
    optionsByMachine[0].push(opt0);

    // Machine 1: slow
    const opt1 = model.intervalVar({
        length: 15 + opId * 3,
        optional: true,
        name: `op${opId}_m1`
    });
    optionsByMachine[1].push(opt1);

    model.alternative(operation, [opt0, opt1]);
    operations.push(operation);
}

// Sequential operations
for (let i = 0; i < operations.length - 1; i++) {
    operations[i].endBeforeStart(operations[i + 1]);
}

// Machine capacity
model.noOverlap(optionsByMachine[0]);
model.noOverlap(optionsByMachine[1]);

// Minimize makespan
model.minimize(operations[operations.length - 1].end());

// Solve
const result = await model.solve();
if (result.solution) {
    console.log(`Makespan: ${result.objective}`);
    operations.forEach((operation, opId) => {
        const start = result.solution.getStart(operation);
        const end = result.solution.getEnd(operation);

        // Find which machine
        for (let machineId = 0; machineId < 2; machineId++) {
            const opt = optionsByMachine[machineId][opId];
            if (result.solution.isPresent(opt)) {
                console.log(`Op ${opId} on machine ${machineId}: ${start}-${end}`);
            }
        }
    });
}

See Also

• Intervals — Optional intervals and presence semantics
• Constraints — Constraint types and enforcement
• Span — Aggregation constraint (parent covers children)
• Tutorial/Alternatives — Step-by-step tutorial with alternatives