Skip to main content

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 xA,xB∈Z≥0x_A,x_B\in\mathbb{Z}_{\ge 0} 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 ss, recourse variables uEs,uWs≥0u_{Es},u_{Ws}\ge0 record capacity shortfall at EUR 50 per package. With scenario probability psp_s, the sample-average objective is

min⁡80xA+70xB+50∑sps(uEs+uWs).\min 80x_A+70x_B+50\sum_s p_s(u_{Es}+u_{Ws}).

Capacity constraints are repeated per scenario, but xA,xBx_A,x_B 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.