Stochastic Optimization
Stochastic optimization uses a probability model inside the decision problem. It is appropriate only when the scenarios, their probabilities, and the timing of information are defensible enough to support that use.
Prerequisites
Complete nonlinear optimization and review sensitivity and scenario analysis.
Learning goals
- Separate first-stage decisions from recourse after uncertainty is observed.
- Enforce nonanticipativity: today's plan cannot depend on tomorrow's realized scenario.
- Compute an expected objective from explicit scenario probabilities and units.
- Distinguish solver evidence, sampling error, and model uncertainty.
A two-stage delivery model
Let be route runs chosen before demand is known. Route A costs EUR 80 and supplies 4 east/1 west package slots; route B costs EUR 70 and supplies 1 east/4 west slots. The plan uses at most 14 driver-hours and three depot slots.
For scenario , recourse variables record capacity shortfall at EUR 50 per package. With scenario probability , the sample-average objective is
Capacity constraints are repeated per scenario, but are shared. Giving each scenario its own route plan would violate nonanticipativity and produce an impossible wait-and-see benchmark.
The fixture uses low, base, and peak probabilities 0.2, 0.5, and 0.3. They are planning inputs, not automatically calibrated forecasts. A sample-average approximation replaces a population expectation with a finite weighted sample; more scenarios do not repair a wrong data-generating model.
Worked example
from itertools import product
scenarios = [("low", 0.2, 4, 4), ("base", 0.5, 7, 6), ("peak", 0.3, 9, 8)]
def cost(plan, east, west):
route_a, route_b = plan
east_capacity = 4 * route_a + route_b
west_capacity = route_a + 4 * route_b
shortage = max(0, east - east_capacity) + max(0, west - west_capacity)
return 80 * route_a + 70 * route_b + 50 * shortage
plans = [(a, b) for a, b in product(range(4), repeat=2)
if a + b <= 3 and 5 * a + 4 * b <= 14]
expected = {plan: sum(p * cost(plan, east, west) for _, p, east, west in scenarios)
for plan in plans}
best = min(plans, key=lambda plan: (expected[plan], plan))
scenario_costs = [cost(best, east, west) for _, _, east, west in scenarios]
print(f"probability_sum={sum(row[1] for row in scenarios):.1f} scenarios={[row[0] for row in scenarios]}")
print(f"plan=(route_a={best[0]},route_b={best[1]}) expected_cost_eur={expected[best]:.2f}")
print(f"scenario_costs_eur={scenario_costs} nonanticipative=True")
Expected output:
probability_sum=1.0 scenarios=['low', 'base', 'peak']
plan=(route_a=2,route_b=1) expected_cost_eur=260.00
scenario_costs_eur=[230, 230, 330] nonanticipative=True
The exhaustive enumeration is independent evidence for this tiny instance. The capstone later solves the algebraic mixed-integer formulation with HiGHS.
Limitations and common mistakes
- Scenario probabilities must sum to one, have provenance, and be stress-tested; equal weights are not neutral when sampling is biased.
- Expected cost can hide unacceptable tails. Report scenario outcomes and service failures alongside the mean.
- Recourse must represent an action that is actually available after uncertainty resolves.
- A zero solver gap concerns the finite declared model, not probability calibration, unseen events, or external validity.
Practice
Raise the peak probability to 0.5, renormalize the other two probabilities, and re-enumerate. Explain whether a changed plan comes from the probability model or from a solver improvement.
Next steps
Replace probabilities with an explicit protection set in robust optimization.
Primary sources
Checked 2026-10-19: Kleywegt, Shapiro, and Homem-de-Mello, The Sample Average Approximation Method for Stochastic Discrete Optimization and the author-hosted manuscript; SciPy 1.18.1, milp.