Cumulative Constraints

Cumulative constraints model resources with limited capacity that can handle multiple tasks simultaneously. The total demand on the resource must never exceed its capacity.

Overview

A cumulative resource has:

• Capacity: Maximum available amount (e.g., 5 workers, 16 GB RAM)
• Demand: Amount required by each task (e.g., task needs 2 workers)
• Profile: Resource usage over time

The constraint ensures: sum(demands at time t) ≤ capacity for all time points t.

Pulse Expression

The pulse function creates a cumulative expression representing resource usage during an interval.

Signature

Python

model.pulse(
    interval: IntervalVar,
    height: IntExpr | int
) -> CumulExpr

TypeScript

model.pulse(
    interval: IntervalVar,
    height: IntExpr | number
): CumulExpr

Parameters:

• interval: The interval during which the resource is used
• height: Height value (constant or expression)

Returns: CumulExpr representing the resource usage

Semantics:

• Resource usage is height during the interval [start, end)
• Resource usage is 0 before start and after end
• If the interval is absent, the pulse has no effect (usage is 0 everywhere)
• Height must be ≥ 0 (use negative height in reservoir for consumption)

CumulExpr

CumulExpr represents a cumulative resource profile over time. Cumulative expressions are created by the pulse function and can be combined using addition.

Combining CumulExpr

Multiple cumulative expressions can be combined using addition:

Python

# Addition
cumul_total = cumul1 + cumul2

# Using sum for multiple expressions
cumul_total = model.sum([cumul1, cumul2, cumul3])

TypeScript

// Addition
const cumulTotal = cumul1.plus(cumul2);

// Using sum for multiple expressions
const cumulTotal = model.sum([cumul1, cumul2, cumul3]);

Capacity Constraints

Constrain the cumulative expression with an upper bound (capacity limit):

Python

model.enforce(cumul_expr <= capacity)

TypeScript

model.enforce(cumulExpr.le(capacity));

The capacity can be either a constant integer or an expression (including decision variables). See Variable Capacity for details on using dynamic capacity bounds.

Lower Bounds and Negation

Lower bounds (cumul_expr >= min) and negation are supported only for Reservoir Constraints, which track absolute level rather than capacity usage.

Variable Capacity

The capacity bound can be a decision variable or expression, not just a constant. This enables modeling scenarios where resource capacity itself is a decision.

Signature

Python

model.enforce(cumul_expr <= capacity)  # capacity: int | IntExpr

TypeScript

model.enforce(cumulExpr.le(capacity));  // capacity: number | IntExpr

Parameters:

• capacity: The maximum allowed value of the cumulative expression at any point in time
  • Can be a constant integer
  • Can be an IntVar (decision variable)
  • Can be any IntExpr (arithmetic expression)

Example: Capacity as a Decision Variable

Python

import optalcp as cp

model = cp.Model()

# Tasks with resource demands
task1 = model.interval_var(length=10, name="task1")
task2 = model.interval_var(length=15, name="task2")
task3 = model.interval_var(length=20, name="task3")

# Resource usage (fixed demands)
resource_usage = model.sum([
    model.pulse(task1, 2),
    model.pulse(task2, 3),
    model.pulse(task3, 2),
])

# Capacity is a decision variable
capacity = model.int_var(min=3, max=6, name="capacity")

# Enforce the capacity constraint
model.enforce(resource_usage <= capacity)

# Trade-off: minimize makespan + capacity cost
makespan = model.max([task1.end(), task2.end(), task3.end()])
capacity_cost = capacity * 10  # Higher capacity is more expensive
model.minimize(makespan + capacity_cost)

result = model.solve()

TypeScript

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

const model = new CP.Model();

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

// Resource usage (fixed demands)
const resourceUsage = model.sum([
    model.pulse(task1, 2),
    model.pulse(task2, 3),
    model.pulse(task3, 2),
]);

// Capacity is a decision variable
const capacity = model.intVar({ min: 3, max: 6, name: "capacity" });

// Enforce the capacity constraint
model.enforce(resourceUsage.le(capacity));

// Trade-off: minimize makespan + capacity cost
const makespan = model.max([task1.end(), task2.end(), task3.end()]);
const capacityCost = capacity.times(10);  // Higher capacity is more expensive
model.minimize(makespan.plus(capacityCost));

const result = await model.solve();

This enables modeling scenarios such as capacity planning (how many workers to hire), machine configuration selection, or workforce sizing where team size varies.

Limitations

Variable capacity is supported only for discrete resources (pulse-based cumulative expressions). Reservoir constraints with steps require constant capacity bounds.

The capacity expression must not be optional or absent—it must always have a defined value.

Basic Usage

Fixed Height Demands

Each task has a constant demand on the resource:

Python

import optalcp as cp

model = cp.Model()

# Three tasks with different durations
task1 = model.interval_var(length=10, name="task1")
task2 = model.interval_var(length=15, name="task2")
task3 = model.interval_var(length=20, name="task3")

# Each task uses workers during its execution
# task1: 2 workers, task2: 1 worker, task3: 3 workers
cumul_expr = model.sum([
    model.pulse(task1, 2),
    model.pulse(task2, 1),
    model.pulse(task3, 3),
])

# Capacity constraint: never exceed 4 workers
model.enforce(cumul_expr <= 4)

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)}) - 2 workers")
    print(f"Task2: [{result.solution.get_start(task2)}, {result.solution.get_end(task2)}) - 1 worker")
    print(f"Task3: [{result.solution.get_start(task3)}, {result.solution.get_end(task3)}) - 3 workers")
    print(f"Makespan: {result.objective}")

TypeScript

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

const model = new CP.Model();

// Three tasks with different durations
const task1 = model.intervalVar({ length: 10, name: "task1" });
const task2 = model.intervalVar({ length: 15, name: "task2" });
const task3 = model.intervalVar({ length: 20, name: "task3" });

// Each task uses workers during its execution
// task1: 2 workers, task2: 1 worker, task3: 3 workers
const cumulExpr = model.sum([
    model.pulse(task1, 2),
    model.pulse(task2, 1),
    model.pulse(task3, 3),
]);

// Capacity constraint: never exceed 4 workers
model.enforce(cumulExpr.le(4));

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)}) - 2 workers`);
    console.log(`Task2: [${result.solution.getStart(task2)}, ${result.solution.getEnd(task2)}) - 1 worker`);
    console.log(`Task3: [${result.solution.getStart(task3)}, ${result.solution.getEnd(task3)}) - 3 workers`);
    console.log(`Makespan: ${result.objective}`);
}

Variable Height

The height can be any IntExpr to model tasks with variable resource requirements.

Python

import optalcp as cp

model = cp.Model()

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

# Variable number of workers assigned to each task
workers1 = model.int_var(min=1, max=3, name="workers1")
workers2 = model.int_var(min=1, max=4, name="workers2")

cumul_expr = model.sum([
    model.pulse(task1, workers1),
    model.pulse(task2, workers2),
])

# Capacity constraint
model.enforce(cumul_expr <= 5)

# Objective: minimize total worker usage
total_workers = workers1 * task1.length() + workers2 * task2.length()
model.minimize(total_workers)

result = model.solve()

if result.solution:
    w1 = result.solution.get_value(workers1)
    w2 = result.solution.get_value(workers2)
    print(f"Task1 uses {w1} workers")
    print(f"Task2 uses {w2} workers")

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

// Variable number of workers assigned to each task
const workers1 = model.intVar({ min: 1, max: 3, name: "workers1" });
const workers2 = model.intVar({ min: 1, max: 4, name: "workers2" });

const cumulExpr = model.sum([
    model.pulse(task1, workers1),
    model.pulse(task2, workers2),
]);

// Capacity constraint
model.enforce(cumulExpr.le(5));

// Objective: minimize total worker usage
const totalWorkers = workers1.times(task1.length()).plus(workers2.times(task2.length()));
model.minimize(totalWorkers);

const result = await model.solve();

if (result.solution) {
    const w1 = result.solution.getValue(workers1);
    const w2 = result.solution.getValue(workers2);
    console.log(`Task1 uses ${w1} workers`);
    console.log(`Task2 uses ${w2} workers`);
}

Optional Intervals

When an interval is optional and absent, its pulse contribution is zero.

The pulse also contributes zero when the height expression is absent, even if the interval is present. However, this pattern is not recommended—prefer making both the interval and height present or absent together as shown in the Variable Height section above.

Python

import optalcp as cp

model = cp.Model()

# Required task
task1 = model.interval_var(length=10, name="task1")

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

cumul_expr = model.sum([
    model.pulse(task1, 2),
    model.pulse(task2, 3),  # Only contributes if task2 is present
])

model.enforce(cumul_expr <= 4)

# If task2 is present, minimize makespan; otherwise just schedule task1
model.minimize(model.max([task1.end(), task2.end().guard(0)]))

result = model.solve()

if result.solution:
    if result.solution.isPresent(task2):
        print(f"Task2 is present: [{result.solution.get_start(task2)}, {result.solution.get_end(task2)})")
    else:
        print("Task2 is absent")

TypeScript

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

const model = new CP.Model();

// Required task
const task1 = model.intervalVar({ length: 10, name: "task1" });

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

const cumulExpr = model.sum([
    model.pulse(task1, 2),
    model.pulse(task2, 3),  // Only contributes if task2 is present
]);

model.enforce(cumulExpr.le(4));

// If task2 is present, minimize makespan; otherwise just schedule task1
model.minimize(model.max([task1.end(), task2.end().guard(0)]));

const result = await model.solve();

if (result.solution) {
    if (result.solution.isPresent(task2)) {
        console.log(`Task2 is present: [${result.solution.getStart(task2)}, ${result.solution.getEnd(task2)})`);
    } else {
        console.log("Task2 is absent");
    }
}

Optional Intervals with Variable Heights

When using variable heights with optional intervals:

Python

# WRONG: non-optional height with optional interval
task = model.interval_var(length=10, optional=True, name="task")
demand = model.int_var(min=1, max=3, name="demand")  # Not optional!
# Problem: demand exists even when task is absent

# WRONG: using min=0 to model "no demand when absent"
demand = model.int_var(min=0, max=3, name="demand")  # min=0 is wrong
# Problem: solver may set demand=0 even when task is present

# CORRECT: optional height with synchronized presence
task = model.interval_var(length=10, optional=True, name="task")
demand = model.int_var(min=1, max=3, optional=True, name="demand")
model.enforce(demand.presence() == task.presence())
# Both present or both absent, and demand >= 1 when present

TypeScript

// WRONG: non-optional height with optional interval
const task = model.intervalVar({ length: 10, optional: true, name: "task" });
const demand = model.intVar({ min: 1, max: 3, name: "demand" });  // Not optional!
// Problem: demand exists even when task is absent

// WRONG: using min=0 to model "no demand when absent"
const demand = model.intVar({ min: 0, max: 3, name: "demand" });  // min=0 is wrong
// Problem: solver may set demand=0 even when task is present

// CORRECT: optional height with synchronized presence
const task = model.intervalVar({ length: 10, optional: true, name: "task" });
const demand = model.intVar({ min: 1, max: 3, optional: true, name: "demand" });
model.enforce(demand.presence().eq(task.presence()));
// Both present or both absent, and demand >= 1 when present

Rule: For variable-height pulses/steps, use optional height variables with synchronized presence and minimum value > 0.

Multiple Resources

Model multiple cumulative resources independently:

Python

import optalcp as cp

model = cp.Model()

tasks = [model.interval_var(length=10 + i*5, name=f"task{i}") for i in range(4)]

# Workers resource
worker_demands = [2, 1, 3, 2]
workers = model.sum([model.pulse(tasks[i], worker_demands[i]) for i in range(4)])
model.enforce(workers <= 5)

# Memory resource (MB)
memory_demands = [1024, 512, 2048, 1024]
memory = model.sum([model.pulse(tasks[i], memory_demands[i]) for i in range(4)])
model.enforce(memory <= 4096)

result = model.solve()

TypeScript

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

const model = new CP.Model();

const tasks = Array.from({ length: 4 }, (_, i) =>
    model.intervalVar({ length: 10 + i * 5, name: `task${i}` })
);

// Workers resource
const workerDemands = [2, 1, 3, 2];
const workers = model.sum(tasks.map((t, i) => model.pulse(t, workerDemands[i])));
model.enforce(workers.le(5));

// Memory resource (MB)
const memoryDemands = [1024, 512, 2048, 1024];
const memory = model.sum(tasks.map((t, i) => model.pulse(t, memoryDemands[i])));
model.enforce(memory.le(4096));

const result = await model.solve();

Use Cases

Worker Scheduling

Model a team of workers with varying task requirements:

Python

# Task requirements
tasks = [
    ("AssembleFrame", 30, 2),    # 30 min, 2 workers
    ("InstallEngine", 45, 3),    # 45 min, 3 workers
    ("PaintBody", 60, 1),        # 60 min, 1 worker
    ("FinalInspection", 20, 1),  # 20 min, 1 worker
]

intervals = []
for name, duration, workers_needed in tasks:
    interval = model.interval_var(length=duration, name=name)
    intervals.append((interval, workers_needed))

# Total available workers
total_workers = 4

cumul = model.sum([model.pulse(interval, workers) for interval, workers in intervals])
model.enforce(cumul <= total_workers)

TypeScript

// Task requirements
const tasks = [
    { name: "AssembleFrame", duration: 30, workers: 2 },
    { name: "InstallEngine", duration: 45, workers: 3 },
    { name: "PaintBody", duration: 60, workers: 1 },
    { name: "FinalInspection", duration: 20, workers: 1 },
];

const intervals = tasks.map(t => ({
    interval: model.intervalVar({ length: t.duration, name: t.name }),
    workers: t.workers
}));

// Total available workers
const totalWorkers = 4;

const cumul = model.sum(intervals.map(({ interval, workers }) =>
    model.pulse(interval, workers)
));
model.enforce(cumul.le(totalWorkers));

Memory or Storage Limits

Constrain total memory usage:

Python

# Each task requires memory while running
memory_usage = model.sum([
    model.pulse(task1, 2048),   # 2 GB
    model.pulse(task2, 1024),   # 1 GB
    model.pulse(task3, 4096),   # 4 GB
])

# System has 8 GB total
model.enforce(memory_usage <= 8192)

TypeScript

// Each task requires memory while running
const memoryUsage = model.sum([
    model.pulse(task1, 2048),   // 2 GB
    model.pulse(task2, 1024),   // 1 GB
    model.pulse(task3, 4096),   // 4 GB
]);

// System has 8 GB total
model.enforce(memoryUsage.le(8192));

Bandwidth Constraints

Model network bandwidth allocation:

Python

# Data transfer tasks with bandwidth requirements (Mbps)
transfers = [
    model.interval_var(length=300, name="transfer1"),  # 5 min
    model.interval_var(length=600, name="transfer2"),  # 10 min
    model.interval_var(length=450, name="transfer3"),  # 7.5 min
]

bandwidth_demands = [50, 30, 40]  # Mbps

bandwidth_usage = model.sum([
    model.pulse(transfers[i], bandwidth_demands[i]) for i in range(3)
])

# Network capacity: 100 Mbps
model.enforce(bandwidth_usage <= 100)

TypeScript

// Data transfer tasks with bandwidth requirements (Mbps)
const transfers = [
    model.intervalVar({ length: 300, name: "transfer1" }),  // 5 min
    model.intervalVar({ length: 600, name: "transfer2" }),  // 10 min
    model.intervalVar({ length: 450, name: "transfer3" }),  // 7.5 min
];

const bandwidthDemands = [50, 30, 40];  // Mbps

const bandwidthUsage = model.sum(
    transfers.map((t, i) => model.pulse(t, bandwidthDemands[i]))
);

// Network capacity: 100 Mbps
model.enforce(bandwidthUsage.le(100));

Efficiency Tips

Disjunctive as Special Case

When capacity = 1 and all demands = 1, use no_overlap instead:

Python

# Less efficient
cumul = model.sum([model.pulse(t, 1) for t in tasks])
model.enforce(cumul <= 1)

# More efficient
model.no_overlap(tasks)

TypeScript

// Less efficient
const cumul = model.sum(tasks.map(t => model.pulse(t, 1)));
model.enforce(cumul.le(1));

// More efficient
model.noOverlap(tasks);

Edge Cases

Zero Height

A pulse with height 0 has no effect but is valid:

Python

cumul = model.pulse(task, 0)  # Valid, no resource usage
model.enforce(cumul <= capacity)  # Always satisfied

TypeScript

const cumul = model.pulse(task, 0);  // Valid, no resource usage
model.enforce(cumul.le(capacity));   // Always satisfied

Zero Capacity

Capacity 0 means no tasks can execute (unless all have height 0):

Python

cumul = model.sum([model.pulse(t, 1) for t in tasks])
model.enforce(cumul <= 0)  # Infeasible if any task is present

TypeScript

const cumul = model.sum(tasks.map(t => model.pulse(t, 1)));
model.enforce(cumul.le(0));  // Infeasible if any task is present

Negative Height

Negative height is allowed for reservoir modeling (see Reservoir Constraints):

Python

# For cumulative: heights should be non-negative
# For reservoir: negative heights represent consumption
production = model.pulse(producer_task, 10)
consumption = model.pulse(consumer_task, -5)
level = production + consumption

TypeScript

// For cumulative: heights should be non-negative
// For reservoir: negative heights represent consumption
const production = model.pulse(producerTask, 10);
const consumption = model.pulse(consumerTask, -5);
const level = production.plus(consumption);

Zero-Length Intervals

A zero-length interval has no effect on cumulative constraints—the pulse is essentially zero since there's no time duration during which it consumes resources:

Python

# Zero-length interval doesn't consume resources
task = model.interval_var(length=0, name="task")
cumul = model.pulse(task, 100)
model.enforce(cumul <= 1)  # Always satisfied, regardless of height

TypeScript

// Zero-length interval doesn't consume resources
const task = model.intervalVar({ length: 0, name: "task" });
const cumul = model.pulse(task, 100);
model.enforce(cumul.le(1));  // Always satisfied, regardless of height

warning

Don't use variable-length intervals allowing zero length to model optional resource usage—use optional intervals instead. Optional intervals with positive length enable effective constraint propagation, while zero-length intervals do not.

Python

# WRONG: variable length with min=0 to model "optional" task
task = model.interval_var(length=(0, 10), name="task")
cumul = model.pulse(task, 2)
# Problem: solver can set length=0, bypassing propagation

# CORRECT: optional interval with positive length
task = model.interval_var(length=10, optional=True, name="task")
cumul = model.pulse(task, 2)
# Propagation works effectively

TypeScript

// WRONG: variable length with min=0 to model "optional" task
const task = model.intervalVar({ length: [0, 10], name: "task" });
const cumul = model.pulse(task, 2);
// Problem: solver can set length=0, bypassing propagation

// CORRECT: optional interval with positive length
const task = model.intervalVar({ length: 10, optional: true, name: "task" });
const cumul = model.pulse(task, 2);
// Propagation works effectively

Performance Considerations

• Propagation level: Controlled by cumulPropagationLevel parameter (1-3, default 3)

  • Level 1: Basic propagation
  • Level 3: Full edge finding (slowest but strongest)
  • Reduce for very large problems

• Variable heights: More expensive than fixed heights

  • Use fixed heights when possible
  • Limit domain size of height variables

See also

• Resource Types Overview - Choosing between resource types
• No Overlap Constraints - Disjunctive resources (capacity = 1)
• Reservoir Constraints - Production and consumption with level tracking
• Tutorial: Cumulative - Learning path with examples