Reservoir Constraints

Our final modeling technique addresses a different kind of resource: reservoirs. Unlike disjunctive or cumulative resources, reservoirs track a quantity that changes over time based on task events.

In our furniture workshop, cutting and sanding generate dust and wood shavings. To maintain a safe working environment, the dust level must stay below a safety threshold. We add a CleanWorkshop task that removes accumulated dust. The solver must schedule cleaning at the right time to keep dust under control.

This is modeled with a reservoir resource.

Understanding Reservoirs

A reservoir tracks a level that changes instantaneously at specific points:

• Increases: Tasks that add to the level (e.g., cutting adds 15 units of dust)
• Decreases: Tasks that remove from the level (e.g., cleaning removes 30 units)
• Bounds: The level must stay within limits (e.g., at most 40)

The main insight: reservoirs model situations where the timing of level changes matters. There is no predefined relationship between which task produces for which consumer—the solver figures out the timing based on level constraints.

Cumulative Expressions for Level Changes

OptalCP models reservoirs using cumulative expressions that change instantaneously at specific points in time.

Python

# Change level when interval ENDS
step = interval.step_at_end(height)
step = model.step_at_end(interval, height)  # equivalent

# Change level when interval STARTS
step = interval.step_at_start(height)
step = model.step_at_start(interval, height)  # equivalent

# Change level at any time (integer expression or constant)
step = model.step_at(time_expr, height)

TypeScript

// Change level when interval ENDS
step = interval.stepAtEnd(height);
step = model.stepAtEnd(interval, height);  // equivalent

// Change level when interval STARTS
step = interval.stepAtStart(height);
step = model.stepAtStart(interval, height);  // equivalent

// Change level at any time (integer expression or constant)
step = model.stepAt(timeExpr, height);

For our dust example:

• Tasks add dust at the end — dust is produced when the task finishes
• Cleaning removes dust at the end — the workshop is clean only after cleaning finishes

Combining Level Changes

Cumulative expressions can be combined using arithmetic operators (+, -) or sum:

Python

# Dust accumulates from cutting and sanding
dust_level = model.sum([
    cut_desk_wood.step_at_end(15),
    cut_chair_wood.step_at_end(15),
    sand_desk_parts.step_at_end(20),
    sand_chair_parts.step_at_end(20),
    clean_workshop.step_at_end(-30),  # negative = removes dust
])

TypeScript

// Dust accumulates from cutting and sanding
const dustLevel = model.sum([
    cutDeskWood.stepAtEnd(15),
    cutChairWood.stepAtEnd(15),
    sandDeskParts.stepAtEnd(20),
    sandChairParts.stepAtEnd(20),
    cleanWorkshop.stepAtEnd(-30),  // negative = removes dust
]);

Reservoir Constraints

Now we constrain the dust level to stay below the safety threshold:

Python

# Dust must stay below safety threshold
model.enforce(dust_level <= 40)

TypeScript

// Dust must stay below safety threshold
dustLevel.le(40);

This constraint ensures that at any point in time, dust level is at most 40.

The Solver's "Trick"

If you run the model with just the upper bound, something unexpected happens: the solver schedules cleaning at the very beginning, before any dust has accumulated. The dust level drops to -30, then gradually increases as tasks complete. Technically, the level never exceeds 40—constraint satisfied!

But this doesn't match reality. You can't clean dust that doesn't exist yet. We need to add a lower bound:

Python

# Dust must stay non-negative (can't clean what isn't there)
model.enforce(dust_level >= 0)
# Dust must stay below safety threshold
model.enforce(dust_level <= 40)

TypeScript

// Dust must stay non-negative (can't clean what isn't there)
dustLevel.ge(0);
// Dust must stay below safety threshold
dustLevel.le(40);

Now the solver must schedule cleaning so that:

1. Enough dust has accumulated before cleaning (to satisfy the lower bound after cleaning)
2. Dust doesn't exceed the threshold before cleaning happens

Lesson Learned

Always consider both bounds. Solvers are very good at finding solutions that satisfy your constraints literally but not your intent. When modeling reservoirs, ask yourself: can the level go negative? Can it exceed some maximum? Add constraints for both if needed.

Modeling Pitfalls

Prefer precedences when possible. If you have a single producer and single consumer with a fixed relationship, use precedence constraints instead. Precedences have much stronger propagation than reservoirs.

Prefer cumulative with pulses when possible. If a task consumes a resource and a later task produces it back (like borrowing and returning), consider using a cumulative constraint with pulses and a maximum capacity instead.

Use reservoirs when:

• Multiple tasks contribute to the level independently
• There is no predefined relationship between producers and consumers
• The timing of level changes determines feasibility

Complete Model with Reservoir

Let's add the dust reservoir to our full model. We introduce CleanWorkshop (20 minutes, requires both workers):

Python

import optalcp as cp

model = cp.Model()

# Create interval variables
cut_desk_wood    = model.interval_var(length=30, name="CutDeskWood")
cut_chair_wood   = model.interval_var(length=25, name="CutChairWood")

# Sanding alternatives for desk
sand_desk_parts  = model.interval_var(name="SandDeskParts")
sand_desk_hand   = model.interval_var(length=30, optional=True, name="SandDeskHand")
sand_desk_power  = model.interval_var(length=15, optional=True, name="SandDeskPower")
model.alternative(sand_desk_parts, [sand_desk_hand, sand_desk_power])

# Sanding alternatives for chair
sand_chair_parts = model.interval_var(name="SandChairParts")
sand_chair_hand  = model.interval_var(length=25, optional=True, name="SandChairHand")
sand_chair_power = model.interval_var(length=10, optional=True, name="SandChairPower")
model.alternative(sand_chair_parts, [sand_chair_hand, sand_chair_power])

# Rest of the tasks
assemble_desk    = model.interval_var(length=45, name="AssembleDesk")
assemble_chair   = model.interval_var(length=35, name="AssembleChair")
clean_workshop   = model.interval_var(length=20, name="CleanWorkshop")  # [NEW]
stain_desk       = model.interval_var(length=20, name="StainDesk")
stain_chair      = model.interval_var(length=15, name="StainChair")
apply_finish     = model.interval_var(length=30, name="ApplyFinish")
final_inspect    = model.interval_var(length=10, name="FinalInspect")

# Precedence constraints - Desk
cut_desk_wood.end_before_start(sand_desk_parts)
sand_desk_parts.end_before_start(assemble_desk)
assemble_desk.end_before_start(stain_desk)
stain_desk.end_before_start(apply_finish)

# Precedence constraints - Chair
cut_chair_wood.end_before_start(sand_chair_parts)
sand_chair_parts.end_before_start(assemble_chair)
assemble_chair.end_before_start(stain_chair)
stain_chair.end_before_start(apply_finish)

# Final inspection
apply_finish.end_before_start(final_inspect)

# Resource constraint: one saw
model.no_overlap([cut_desk_wood, cut_chair_wood])

# Resource constraint: power sander
model.no_overlap([sand_desk_power, sand_chair_power])

# Resource constraint: 2 workers
worker_usage = [
    model.pulse(cut_desk_wood, 1),
    model.pulse(cut_chair_wood, 1),
    model.pulse(sand_desk_parts, 1),
    model.pulse(sand_chair_parts, 1),
    model.pulse(assemble_desk, 2),
    model.pulse(assemble_chair, 1),
    model.pulse(clean_workshop, 2),  # [NEW] requires both workers
    model.pulse(stain_desk, 1),
    model.pulse(stain_chair, 1),
    model.pulse(apply_finish, 1),
    model.pulse(final_inspect, 1),
]
model.enforce(model.sum(worker_usage) <= 2)

# Resource constraint: spray booth with transitions
spray_booth_seq = model.sequence_var([stain_desk, stain_chair, apply_finish])
transitions = [
    [0, 10, 5],
    [10, 0, 5],
    [5, 5, 0],
]
model.no_overlap(spray_booth_seq, transitions)

# [NEW] Reservoir constraint: dust accumulation and cleaning
dust_level = model.sum([
    cut_desk_wood.step_at_end(15),
    cut_chair_wood.step_at_end(15),
    sand_desk_parts.step_at_end(20),
    sand_chair_parts.step_at_end(20),
    clean_workshop.step_at_end(-30),
])
model.enforce(dust_level >= 0)
model.enforce(dust_level <= 40)

# Minimize makespan
model.minimize(final_inspect.end())

# Solve
result = model.solve()

if result.solution:
    print(f"Makespan: {result.objective} minutes")
    print(f"Optimal: {result.proof}")

TypeScript

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

const model = new CP.Model();

// Create interval variables
const cutDeskWood    = model.intervalVar({ length: 30, name: "CutDeskWood" });
const cutChairWood   = model.intervalVar({ length: 25, name: "CutChairWood" });

// Sanding alternatives for desk
const sandDeskParts  = model.intervalVar({ name: "SandDeskParts" });
const sandDeskHand   = model.intervalVar({ length: 30, optional: true, name: "SandDeskHand" });
const sandDeskPower  = model.intervalVar({ length: 15, optional: true, name: "SandDeskPower" });
model.alternative(sandDeskParts, [sandDeskHand, sandDeskPower]);

// Sanding alternatives for chair
const sandChairParts = model.intervalVar({ name: "SandChairParts" });
const sandChairHand  = model.intervalVar({ length: 25, optional: true, name: "SandChairHand" });
const sandChairPower = model.intervalVar({ length: 10, optional: true, name: "SandChairPower" });
model.alternative(sandChairParts, [sandChairHand, sandChairPower]);

// Rest of the tasks
const assembleDesk   = model.intervalVar({ length: 45, name: "AssembleDesk" });
const assembleChair  = model.intervalVar({ length: 35, name: "AssembleChair" });
const cleanWorkshop  = model.intervalVar({ length: 20, name: "CleanWorkshop" });  // [NEW]
const stainDesk      = model.intervalVar({ length: 20, name: "StainDesk" });
const stainChair     = model.intervalVar({ length: 15, name: "StainChair" });
const applyFinish    = model.intervalVar({ length: 30, name: "ApplyFinish" });
const finalInspect   = model.intervalVar({ length: 10, name: "FinalInspect" });

// Precedence constraints - Desk
cutDeskWood.endBeforeStart(sandDeskParts);
sandDeskParts.endBeforeStart(assembleDesk);
assembleDesk.endBeforeStart(stainDesk);
stainDesk.endBeforeStart(applyFinish);

// Precedence constraints - Chair
cutChairWood.endBeforeStart(sandChairParts);
sandChairParts.endBeforeStart(assembleChair);
assembleChair.endBeforeStart(stainChair);
stainChair.endBeforeStart(applyFinish);

// Final inspection
applyFinish.endBeforeStart(finalInspect);

// Resource constraint: one saw
model.noOverlap([cutDeskWood, cutChairWood]);

// Resource constraint: power sander
model.noOverlap([sandDeskPower, sandChairPower]);

// Resource constraint: 2 workers
const workerUsage = [
    model.pulse(cutDeskWood, 1),
    model.pulse(cutChairWood, 1),
    model.pulse(sandDeskParts, 1),
    model.pulse(sandChairParts, 1),
    model.pulse(assembleDesk, 2),
    model.pulse(assembleChair, 1),
    model.pulse(cleanWorkshop, 2),  // [NEW] requires both workers
    model.pulse(stainDesk, 1),
    model.pulse(stainChair, 1),
    model.pulse(applyFinish, 1),
    model.pulse(finalInspect, 1),
];
model.enforce(model.sum(workerUsage).le(2));

// Resource constraint: spray booth with transitions
const sprayBoothSeq = model.sequenceVar([stainDesk, stainChair, applyFinish]);
const transitions = [
    [0, 10, 5],
    [10, 0, 5],
    [5, 5, 0],
];
model.noOverlap(sprayBoothSeq, transitions);

// [NEW] Reservoir constraint: dust accumulation and cleaning
const dustLevel = model.sum([
    cutDeskWood.stepAtEnd(15),
    cutChairWood.stepAtEnd(15),
    sandDeskParts.stepAtEnd(20),
    sandChairParts.stepAtEnd(20),
    cleanWorkshop.stepAtEnd(-30),
]);
model.enforce(dustLevel.ge(0));
model.enforce(dustLevel.le(40));

// Minimize makespan
model.minimize(finalInspect.end());

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

if (result.solution) {
    console.log(`Makespan: ${result.objective} minutes`);
    console.log(`Optimal: ${result.proof}`);
}

Impact on Schedule

The dust constraints force cleaning to happen at the right time:

• Total dust generated: 15 + 15 + 20 + 20 = 70 units
• Cleaning removes: 30 units
• Bounds: 0 to 40

The solver must schedule cleaning when:

1. At least 30 units of dust have accumulated (so cleaning doesn't make level negative)
2. Before dust exceeds 40 (safety threshold)

Since cleaning requires both workers, nothing else can run during cleaning.

Building on our previous model with alternatives (makespan: 195 minutes), the optimal makespan is now 215 minutes. The reservoir constraint adds 20 minutes because cleaning blocks all other work.

Other Reservoir Use Cases

Reservoirs are useful for many scenarios:

• Battery charging/discharging: Charge during off-peak, discharge during peak
• Inventory: Produce parts, consume them in assembly
• Cash flow: Revenue events add money, expenses consume it
• Energy grids: Generation adds power, consumption removes it
• Safety limits: Track hazardous conditions that must stay below thresholds

Any problem where you're tracking a quantity that changes over time can use reservoirs.

Initial Level and stepAt

Level constraints must hold at all times, including before any task starts. The initial level is 0 by default. If you need to maintain a safety buffer (e.g., battery must stay above 10%), you must set an initial level.

Use stepAt with IntervalMin (the earliest possible time) to set an initial level:

Python

# Set initial battery level to 50% (at the beginning of time)
initial = model.step_at(cp.IntervalMin, 50)

# Battery changes from charging (+) and usage (-)
# Must stay above 10% safety buffer at all times
level = initial + charging - usage
model.enforce(level >= 10)

TypeScript

// Set initial battery level to 50% (at the beginning of time)
const initial = model.stepAt(CP.IntervalMin, 50);

// Battery changes from charging (+) and usage (-)
// Must stay above 10% safety buffer at all times
const level = initial.plus(charging).minus(usage);
level.ge(10);

You can also use stepAt with variable times and heights for more complex scenarios:

Python

# Variable height based on an IntVar
amount = model.int_var(min=10, max=50)
step = model.step_at(task.end(), amount)

TypeScript

// Variable height based on an IntVar
const amount = model.intVar({ min: 10, max: 50 });
const step = model.stepAt(task.end(), amount);

What We Learned

In this chapter, we:

• Modeled a reservoir resource for tracking quantities over time
• Used cumulative expressions to model level changes
• Enforced level constraints to keep values within bounds
• Integrated the reservoir with other constraints (workers, precedence, etc.)

Reservoirs complete our constraint programming toolkit: we can now model precedence, disjunctive resources, cumulative resources, choices, and level-tracking constraints.

See Also

• Resources / Reservoirs — Complete reference for reservoir constraints
• Resources / Overview — Choosing between resource types

Next Steps

Continue to: Beyond the Tutorial →