Reservoir Constraints

Reservoir constraints model resources that are produced and consumed over time, where the level changes instantaneously at specific points. Unlike cumulative resources (which track capacity usage), reservoirs track the absolute level of a resource.

Overview

A reservoir has:

• Level: Amount of resource available, changing over time (e.g., inventory count, fuel remaining)
• Steps: Operations that change the level at specific times
  • Production: Positive steps that increase the level
  • Consumption: Negative steps that decrease the level
• Bounds: Minimum and maximum level constraints

The reservoir level is the cumulative result of all steps and must stay within bounds at all times.

Reservoir Steps

Reservoir steps create cumulative expressions that change the level at specific points in time.

stepAtStart / stepAtEnd

Models a level change at the start or end of an interval:

Python

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

TypeScript

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

Parameters:

• interval: The interval variable
• height: Height value (constant or expression, can be positive or negative)

Returns: CumulExpr representing the level change

stepAt

Models a level change at a fixed time point:

Python

model.step_at(x: int, height: int | IntExpr) -> CumulExpr

TypeScript

model.stepAt(x: number, height: number | IntExpr): CumulExpr

Parameters:

• x: Constant time point when the level change occurs
• height: Height value (constant or expression, can be positive or negative)

Returns: CumulExpr representing the level change

When steps have no effect:

• If the interval is absent (for stepAtStart/stepAtEnd)
• If the height is 0
• If the height expression is absent

CumulExpr

CumulExpr represents a reservoir level profile over time. Cumulative expressions are created by step functions and can be combined using arithmetic operators.

Mathematical perspective

A CumulExpr is a piecewise constant function over time. Steps create elementary step functions, and arithmetic operators (+, -, sum) perform pointwise operations on these functions.

Combining CumulExpr

Like cumulative constraints, reservoir expressions can be combined using addition:

Python

# Addition
level = step1 + step2

# Using sum for multiple expressions
level = model.sum([step1, step2, step3])

TypeScript

// Addition
const level = step1.plus(step2);

// Using sum for multiple expressions
const level = model.sum([step1, step2, step3]);

Negation and Subtraction

Unlike cumulative constraints (which only support + and sum), reservoir expressions also support negation and subtraction:

Python

# Unary negation
consumption = -production

# Binary subtraction
net_flow = arrivals - departures

TypeScript

// Unary negation
const consumption = production.neg();

// Binary subtraction
const netFlow = arrivals.minus(departures);

note

Python uses - for both unary negation and binary subtraction. TypeScript uses .neg() for negation and .minus() for subtraction.

Level Constraints

Constrain the cumulative expression with bounds:

Python

# Upper bound (maximum level)
model.enforce(level <= max_level)

# Lower bound (minimum level) - reservoir only
model.enforce(level >= min_level)

TypeScript

// Upper bound (maximum level)
model.enforce(level.le(maxLevel));

// Lower bound (minimum level) - reservoir only
model.enforce(level.ge(minLevel));

note

Lower bounds are supported only for reservoir constraints, not cumulative. This is because reservoirs track absolute level while cumulative tracks capacity usage.

Basic Usage

Battery Charging Example

A mobile robot has a battery that can be charged at two charging stations. It must complete three tasks that consume power. The solver decides when to charge based on battery level constraints—no explicit precedences between charging and tasks.

Python

import optalcp as cp

model = cp.Model()

# Two charging opportunities (at different stations)
charge1 = model.interval_var(length=20, name="charge1")
charge2 = model.interval_var(length=15, name="charge2")

# Three tasks that consume battery
task1 = model.interval_var(length=30, name="task1")
task2 = model.interval_var(length=25, name="task2")
task3 = model.interval_var(length=20, name="task3")

# Battery level: starts at 50, charges add, tasks subtract
battery = model.sum([
    model.step_at(cp.IntervalMin, 50),      # Initial charge: 50%
    model.step_at_end(charge1, 30),         # Charge adds 30%
    model.step_at_end(charge2, 25),         # Charge adds 25%
    model.step_at_start(task1, -35),        # Task uses 35%
    model.step_at_start(task2, -30),        # Task uses 30%
    model.step_at_start(task3, -25),        # Task uses 25%
])

# Battery constraints: 10-100%
model.enforce(battery >= 10)  # Safety buffer
model.enforce(battery <= 100)

# Minimize makespan
model.minimize(model.max([
    charge1.end(), charge2.end(),
    task1.end(), task2.end(), task3.end()
]))

result = model.solve()

TypeScript

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

const model = new CP.Model();

// Two charging opportunities (at different stations)
const charge1 = model.intervalVar({ length: 20, name: "charge1" });
const charge2 = model.intervalVar({ length: 15, name: "charge2" });

// Three tasks that consume battery
const task1 = model.intervalVar({ length: 30, name: "task1" });
const task2 = model.intervalVar({ length: 25, name: "task2" });
const task3 = model.intervalVar({ length: 20, name: "task3" });

// Battery level: starts at 50, charges add, tasks subtract
const battery = model.sum([
    model.stepAt(CP.IntervalMin, 50),       // Initial charge: 50%
    model.stepAtEnd(charge1, 30),           // Charge adds 30%
    model.stepAtEnd(charge2, 25),           // Charge adds 25%
    model.stepAtStart(task1, -35),          // Task uses 35%
    model.stepAtStart(task2, -30),          // Task uses 30%
    model.stepAtStart(task3, -25),          // Task uses 25%
]);

// Battery constraints: 10-100%
model.enforce(battery.ge(10));  // Safety buffer
model.enforce(battery.le(100));

// Minimize makespan
model.minimize(model.max([
    charge1.end(), charge2.end(),
    task1.end(), task2.end(), task3.end()
]));

const result = await model.solve();

The solver determines when to interleave charging with tasks to keep the battery within bounds.

Initial Level

The initial level is implicitly 0. Level constraints must hold at all times, including before any task starts. Use IntervalMin to set the initial level at the beginning of time:

Python

import optalcp as cp

level = model.sum([
    model.step_at(cp.IntervalMin, 50),  # Initial: 50
    model.step_at_end(charge, 30),
    model.step_at_start(task, -40),
])

model.enforce(level >= 10)  # Must hold at all times

TypeScript

const level = model.sum([
    model.stepAt(CP.IntervalMin, 50),  // Initial: 50
    model.stepAtEnd(charge, 30),
    model.stepAtStart(task, -40),
]);

model.enforce(level.ge(10));  // Must hold at all times

Why IntervalMin?

If you use stepAt(0, initial) instead, the level is 0 before time 0, which may violate lower bound constraints.

Python

# WRONG: level is 0 before time 0, violating the >= 10 constraint
level = model.sum([
    model.step_at(0, 50),  # Level jumps to 50 at time 0
    ...
])
model.enforce(level >= 10)  # Fails: level is 0 before time 0!

# CORRECT: level is 50 from the beginning of time
level = model.sum([
    model.step_at(cp.IntervalMin, 50),  # Level is 50 from -∞
    ...
])
model.enforce(level >= 10)  # OK: always satisfied

TypeScript

// WRONG: level is 0 before time 0, violating the >= 10 constraint
const level = model.sum([
    model.stepAt(0, 50),  // Level jumps to 50 at time 0
    ...
]);
model.enforce(level.ge(10));  // Fails: level is 0 before time 0!

// CORRECT: level is 50 from the beginning of time
const level = model.sum([
    model.stepAt(CP.IntervalMin, 50),  // Level is 50 from -∞
    ...
]);
model.enforce(level.ge(10));  // OK: always satisfied

Use Cases

Inventory Management

Track parts from multiple deliveries consumed by multiple orders. This example combines reservoir constraints with resource constraints:

Python

import optalcp as cp

model = cp.Model()

# Three deliveries bringing parts
delivery1 = model.interval_var(length=10, name="delivery1")
delivery2 = model.interval_var(length=10, name="delivery2")
delivery3 = model.interval_var(length=10, name="delivery3")

# Three orders consuming parts
order1 = model.interval_var(length=20, name="order1")
order2 = model.interval_var(length=25, name="order2")
order3 = model.interval_var(length=15, name="order3")

# Resource: one loading dock (deliveries can't overlap)
model.no_overlap([delivery1, delivery2, delivery3])

# Resource: one worker processes orders
model.no_overlap([order1, order2, order3])

# Inventory level (reservoir)
inventory = model.sum([
    model.step_at_end(delivery1, 40),     # Delivery adds 40 parts
    model.step_at_end(delivery2, 35),     # Delivery adds 35 parts
    model.step_at_end(delivery3, 30),     # Delivery adds 30 parts
    model.step_at_start(order1, -30),     # Order needs 30 parts
    model.step_at_start(order2, -35),     # Order needs 35 parts
    model.step_at_start(order3, -25),     # Order needs 25 parts
])

# Reservoir constraints
model.enforce(inventory >= 0)   # Can't fulfill without stock
model.enforce(inventory <= 60)  # Limited storage

model.minimize(model.max([
    delivery1.end(), delivery2.end(), delivery3.end(),
    order1.end(), order2.end(), order3.end()
]))

result = model.solve()

TypeScript

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

const model = new CP.Model();

// Three deliveries bringing parts
const delivery1 = model.intervalVar({ length: 10, name: "delivery1" });
const delivery2 = model.intervalVar({ length: 10, name: "delivery2" });
const delivery3 = model.intervalVar({ length: 10, name: "delivery3" });

// Three orders consuming parts
const order1 = model.intervalVar({ length: 20, name: "order1" });
const order2 = model.intervalVar({ length: 25, name: "order2" });
const order3 = model.intervalVar({ length: 15, name: "order3" });

// Resource: one loading dock (deliveries can't overlap)
model.noOverlap([delivery1, delivery2, delivery3]);

// Resource: one worker processes orders
model.noOverlap([order1, order2, order3]);

// Inventory level (reservoir)
const inventory = model.sum([
    model.stepAtEnd(delivery1, 40),       // Delivery adds 40 parts
    model.stepAtEnd(delivery2, 35),       // Delivery adds 35 parts
    model.stepAtEnd(delivery3, 30),       // Delivery adds 30 parts
    model.stepAtStart(order1, -30),       // Order needs 30 parts
    model.stepAtStart(order2, -35),       // Order needs 35 parts
    model.stepAtStart(order3, -25),       // Order needs 25 parts
]);

// Reservoir constraints
model.enforce(inventory.ge(0));   // Can't fulfill without stock
model.enforce(inventory.le(60));  // Limited storage

model.minimize(model.max([
    delivery1.end(), delivery2.end(), delivery3.end(),
    order1.end(), order2.end(), order3.end()
]));

const result = await model.solve();

Budget or Cash Flow

Track budget earned and spent, maintaining minimum reserves:

Python

import optalcp as cp

model = cp.Model()

# Revenue-generating tasks
revenue1 = model.interval_var(length=20, name="revenue1")
revenue2 = model.interval_var(length=30, name="revenue2")

# Cost-incurring tasks
expense1 = model.interval_var(length=15, name="expense1")
expense2 = model.interval_var(length=25, name="expense2")

# Budget tracking
budget = model.sum([
    model.step_at(cp.IntervalMin, 500),      # Initial budget
    model.step_at_end(revenue1, 500),        # Earn $500
    model.step_at_end(revenue2, 750),        # Earn $750
    model.step_at_start(expense1, -300),     # Spend $300
    model.step_at_start(expense2, -450),     # Spend $450
])

# Must maintain minimum reserves
model.enforce(budget >= 100)

result = model.solve()

TypeScript

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

const model = new CP.Model();

// Revenue-generating tasks
const revenue1 = model.intervalVar({ length: 20, name: "revenue1" });
const revenue2 = model.intervalVar({ length: 30, name: "revenue2" });

// Cost-incurring tasks
const expense1 = model.intervalVar({ length: 15, name: "expense1" });
const expense2 = model.intervalVar({ length: 25, name: "expense2" });

// Budget tracking
const budget = model.sum([
    model.stepAt(CP.IntervalMin, 500),       // Initial budget
    model.stepAtEnd(revenue1, 500),          // Earn $500
    model.stepAtEnd(revenue2, 750),          // Earn $750
    model.stepAtStart(expense1, -300),       // Spend $300
    model.stepAtStart(expense2, -450),       // Spend $450
]);

// Must maintain minimum reserves
model.enforce(budget.ge(100));

const result = await model.solve();

Variable Heights

The height can be any IntExpr to model variable production or consumption:

Python

import optalcp as cp

model = cp.Model()

produce = model.interval_var(length=30, name="produce")
consume = model.interval_var(length=20, name="consume")

# Variable production amount
production_amount = model.int_var(min=50, max=150, name="production_amount")

# Variable consumption amount
consumption_amount = model.int_var(min=20, max=80, name="consumption_amount")

inventory = model.sum([
    model.step_at_end(produce, production_amount),
    model.step_at_start(consume, -consumption_amount),
])

model.enforce(inventory >= 0)

# Objective: minimize total production (minimize waste)
model.minimize(production_amount)

# Ensure consumption is satisfied
model.enforce(consumption_amount >= 50)

result = model.solve()

if result.solution:
    prod = result.solution.get_value(production_amount)
    cons = result.solution.get_value(consumption_amount)
    print(f"Produced: {prod}, Consumed: {cons}")

TypeScript

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

const model = new CP.Model();

const produce = model.intervalVar({ length: 30, name: "produce" });
const consume = model.intervalVar({ length: 20, name: "consume" });

// Variable production amount
const productionAmount = model.intVar({ min: 50, max: 150, name: "production_amount" });

// Variable consumption amount
const consumptionAmount = model.intVar({ min: 20, max: 80, name: "consumption_amount" });

const inventory = model.sum([
    model.stepAtEnd(produce, productionAmount),
    model.stepAtStart(consume, consumptionAmount.neg()),
]);

model.enforce(inventory.ge(0));

// Objective: minimize total production (minimize waste)
model.minimize(productionAmount);

// Ensure consumption is satisfied
model.enforce(consumptionAmount.ge(50));

const result = await model.solve();

if (result.solution) {
    const prod = result.solution.getValue(productionAmount);
    const cons = result.solution.getValue(consumptionAmount);
    console.log(`Produced: ${prod}, Consumed: ${cons}`);
}

Variable Heights with Optional Intervals

When using variable heights with optional intervals, make the height optional too and synchronize presence:

Python

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

# CORRECT: optional height with synchronized presence
task = model.interval_var(length=10, optional=True)
amount = model.int_var(min=1, max=10, optional=True)
model.enforce(amount.presence() == task.presence())

TypeScript

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

// CORRECT: optional height with synchronized presence
const task = model.intervalVar({ length: 10, optional: true });
const amount = model.intVar({ min: 1, max: 10, optional: true });
model.enforce(amount.presence().eq(task.presence()));

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

Edge Cases

Zero Height

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

Python

step = model.step_at_end(task, 0)  # Valid, no level change

TypeScript

const step = model.stepAtEnd(task, 0);  // Valid, no level change

Simultaneous Steps

Multiple steps can occur at the same time. Level constraints are checked against the net effect, not intermediate values:

Python

# Both happen at time 100
step1 = model.step_at(100, 10)
step2 = model.step_at(100, -5)
# Net effect: +5 at time 100

# With constraint 0 <= level <= 5:
# This is SATISFIED - the +10 step is not seen independently

TypeScript

// Both happen at time 100
const step1 = model.stepAt(100, 10);
const step2 = model.stepAt(100, -5);
// Net effect: +5 at time 100

// With constraint 0 <= level <= 5:
// This is SATISFIED - the +10 step is not seen independently

Infeasible Constraints

If production cannot meet consumption, the problem is infeasible:

Python

level = model.sum([
    model.step_at_end(produce, 50),      # Produce 50
    model.step_at_start(consume, -100),  # Consume 100
])

model.enforce(level >= 0)  # Infeasible: cannot consume more than produced

TypeScript

const level = model.sum([
    model.stepAtEnd(produce, 50),      // Produce 50
    model.stepAtStart(consume, -100),  // Consume 100
]);

model.enforce(level.ge(0));  // Infeasible: cannot consume more than produced

Performance Considerations

• Propagation level: Controlled by reservoirPropagationLevel parameter (1-2, default 2)

  • Level 1: Basic propagation
  • Level 2: Full propagation
  • Reduce for very large problems

• Variable heights: More expensive than fixed heights

  • Use fixed heights when possible

See also

• Resource Types Overview - Choosing between resource types
• Cumulative Constraints - Capacity-constrained resources
• Tutorial: Reservoir - Learning path with examples

• Step Functions - Time-varying values and constraints