Stochastic & Robust Optimization

Decision-Making Under Uncertainty

A comprehensive collection of optimization problems that address uncertainty in data, parameters, and outcomes. From classical newsvendor models and stochastic programming to distributionally robust optimization, these formulations capture the spectrum of approaches for making optimal decisions when the future is unknown.

Problems

110

Tests

Algorithms

Paradigms

View Source on GitHub

Problem Overview

Three paradigms of optimization under uncertainty

Stochastic Probability distributions known

Robust Worst-case over uncertainty sets

DRO Worst-case over distribution families

Stochastic

Newsvendor

Single-period inventory under demand uncertainty with critical fractile solution.

13 tests

Stochastic

Two-Stage SP

First-stage decisions before uncertainty, second-stage recourse after.

10 tests

Robust

Robust Shortest Path

Shortest path minimizing worst-case cost or regret across scenarios.

13 tests

Stochastic

Stochastic Knapsack

Item selection with random weights and chance constraints on feasibility.

11 tests

Stochastic

Chance-Constrained FL

Facility location with stochastic demands and probabilistic capacity constraints.

11 tests

Robust

Robust Portfolio

Markowitz mean-variance with ellipsoidal uncertainty on expected returns.

14 tests

Stochastic

Stochastic VRP

Vehicle routing with random customer demands and recourse for overflow.

13 tests

Robust

Robust Scheduling

Single machine scheduling minimizing worst-case regret under uncertain processing times.

13 tests

DRO

Distributionally Robust

Optimize against worst-case distribution within an ambiguity set.

12 tests

Optimization Paradigms

Three approaches to handling uncertainty in optimization

Stochastic Programming

Known Distributions

Assumes probability distributions of uncertain parameters are known. Optimizes the expected value of the objective, possibly with chance constraints.

Newsvendor
Two-Stage SP
Stochastic Knapsack
Chance-Constrained FL
Stochastic VRP

Robust Optimization

Worst-Case Scenarios

Makes no distributional assumptions. Protects against worst-case realizations within an uncertainty set, minimizing regret or cost.

Robust Shortest Path
Robust Portfolio
Robust Scheduling

Distributionally Robust

Ambiguity Sets

Bridges stochastic and robust: optimizes against the worst-case distribution within an ambiguity set defined by distance or moment constraints.

Wasserstein DRO
Moment-Based DRO

When to Use Each Paradigm

Distribution known?

Yes — fully specified

No — only bounds / sets

Partially — ambiguity set

Objective focus

Expected cost / profit

Worst-case cost / regret

Worst-case expected cost

Risk attitude

Risk-neutral (or chance-constrained)

Extremely risk-averse

Moderately risk-averse

Data requirement

Large sample / known family

Expert-defined bounds

Limited data + moments

Conservatism

Low — may underprotect

High — may overprotect

Tunable via ε / δ

Key concepts

EVPI, VSS, recourse

Price of robustness, regret

Ambiguity radius, Wasserstein

Key Stochastic Programming Concepts

Three fundamental quantities measure the value of modeling uncertainty:

WS (Wait-and-See) — Expected cost if we could know each scenario before deciding. Unachievable lower bound.
RP (Recourse Problem) — Expected cost of the optimal here-and-now stochastic solution.
EEV (Expected result of EV solution) — Expected cost when using the deterministic mean-scenario decision.

EVPI = RP − WS (value of perfect information — how much you would pay for an oracle)
VSS = EEV − RP (value of the stochastic solution — benefit of modeling uncertainty vs. using averages)

Problem Details

Mathematical formulations, algorithms, and complexity analysis

Quick Navigation

Newsvendor Two-Stage SP Robust Shortest Path Stochastic Knapsack Chance-Constrained FL Robust Portfolio Stochastic VRP Robust Scheduling DRO Paradigms Tests

Newsvendor Problem

13 TESTS

NV | stochastic demand | min E[cost]

A retailer orders Q units of a perishable product before uncertain demand D is realized. Overage cost c_o = c - v for excess inventory; underage cost c_u = p - c for lost sales. The optimal order quantity satisfies the critical fractile condition.

Applications: Retail inventory, fashion goods, seasonal products, airline overbooking, event ticketing.

minQ   E[co · max(0, Q - D) + cu · max(0, D - Q)] Optimal:   Q* = F-1(cu / (cu + co))    // Critical fractile

Algorithm	Type	Complexity	Reference	Description
Critical Fractile	Exact	O(S log S)	Arrow et al. (1951)	Sort scenarios, scan empirical CDF to find optimal quantile
Grid Search	Heuristic	O(S × G)	—	Discretized evaluation over demand range grid; approximate unless grid contains optimum
Marginal Allocation	Heuristic	O(n × Q_max)	Fox (1966)	Greedy marginal analysis for multi-product with budget constraint
Independent + Scale	Heuristic	O(n × S log S)	—	Solve independently per product, scale to fit budget

Try It Yourself

Cost Parameters

Unit Cost (c): 10

Selling Price (p): 25

Salvage Value (v): 5

Scenarios: 20

Instance Generation

Derived Parameters

c_u (underage) = p - c = 15
c_o (overage) = c - v = 5
Critical fractile = c_u / (c_u + c_o) = 0.750

Visualization

Generate demand scenarios and click Solve to find the optimal order quantity.

Results

Metric	Value
No results yet

Benchmarks: Classical discrete demand scenarios (Arrow et al.); log-normal and Poisson demand distributions; multi-product budget-constrained instances

Interested in Stochastic Optimization?

Explore the full implementation with critical fractile, grid search, multi-product heuristics, and 13 comprehensive tests.

Contact LinkedIn Source Code

Two-Stage Stochastic Programming

10 TESTS

2SSP | scenarios | min c'x + E[q(s)'y(s)]

First-stage decisions x are made before uncertainty is revealed. After observing scenario s, second-stage recourse decisions y(s) compensate for any constraint violations. The goal is to minimize the sum of first-stage cost and expected second-stage recourse cost.

Applications: Capacity planning, supply chain design, energy systems, financial planning, network design.

min x c T x + E s [Q (x, s)] where Q (x, s) = min y {q (s) T y : W y = h (s) - T (s) x, y \geq 0 }

Algorithm	Type	Complexity	Reference	Description
Deterministic Equivalent LP	Exact	O(S × LP)	Dantzig (1955)	Extensive form expanding all scenarios into a single LP (HiGHS solver)
L-Shaped Method	Exact	Iterative	Van Slyke & Wets (1969)	Benders decomposition for two-stage SP; generates optimality cuts iteratively
Expected Value (EV) Solution	Heuristic	O(LP)	Birge & Louveaux (2011)	Solve on mean scenario; yields EEV when evaluated stochastically. VSS = EEV − RP measures stochastic solution value
Sample Average Approximation	Approximation	O(R × S' × LP)	Kleywegt et al. (2002)	Sampling-based approximation; solve on random scenario subsets with replications for confidence bounds
Progressive Hedging	Approximation	Iterative	Rockafellar & Wets (1991)	Scenario decomposition with augmented Lagrangian; enforces non-anticipativity via penalty terms

Stochastic Programming Relationships

For a minimization two-stage SP: WS ≤ RP ≤ EEV. The gap EVPI = RP − WS tells you how much perfect foresight is worth. The gap VSS = EEV − RP tells you the benefit of modeling uncertainty explicitly versus using deterministic averages. If VSS is small, the deterministic model suffices; if EVPI is large, invest in better forecasting.

Benchmarks: Birge & Louveaux newsvendor/capacity planning instances; SIPLIB (Stochastic Integer Programming Library); farmer problem (Birge & Louveaux, 2011)

Two-Stage Recourse Explorer

Problem Parameters

Capacity cost (c): 5

Revenue (p): 20

Penalty (q): 10

Scenarios: 8

Actions

Scenario Demands

Generate scenarios to see demand values.

Cost vs. First-Stage Capacity

Generate demand scenarios and click Solve to compare RP, EV, and WS solutions.

Solution Comparison

Method	Capacity (x)	Expected Cost	Interpretation
No results yet

Robust Shortest Path

13 TESTS

RSP | S scenarios | min max-cost / min max-regret

Find a path from source to target that performs well across all possible edge-weight scenarios. Two criteria: minimize the worst-case path cost (min-max cost), or minimize the worst-case deviation from the scenario-optimal path (min-max regret).

Applications: Transportation under weather uncertainty, evacuation routing, military logistics, network reliability.

Min-Max Cost: min P max s \in S Σ (i,j) \in P w ij (s) Min-Max Regret: min P max s \in S [cost (P, s) - cost (P* s, s) ]

Algorithm	Type	Complexity	Reference	Description
Label-Setting	Exact	O(S × (V+E) log V)	Yu & Yang (1998)	Multi-objective Dijkstra with dominance pruning for min-max cost
Scenario Enumeration	Exact	O(S × (V+E) log V)	Kouvelis & Yu (1997)	Dijkstra per scenario, cross-evaluate all candidate paths
Regret Enumeration	Heuristic	O(S² × V)	Kouvelis & Yu (1997)	Evaluate candidate paths against per-scenario optima for regret
Midpoint	Heuristic	O((V+E) log V)	—	Shortest path on mean-weight graph; robust approximation for scenario-based uncertainty

Budgeted Uncertainty (Bertsimas & Sim, 2003)

The scenario-based approach above considers discrete scenarios. An influential alternative is budgeted uncertainty: each edge weight lies in an interval [w̄_ij, w̄_ij + d̂_ij], and at most Γ edges deviate simultaneously. The parameter Γ controls the price of robustness — the trade-off between solution quality and protection level. At Γ = 0 the solution is nominal; at Γ = |E| it is fully worst-case. This framework applies broadly to robust network, scheduling, and combinatorial optimization problems.

Benchmarks: Random graph instances with interval-based edge weights; Kouvelis & Yu scenario sets

Stochastic Knapsack

11 TESTS

SKP | random weights | max value s.t. P(feasible) ≥ 1 - α

Select items with deterministic values but random weights to maximize total value. The total weight must satisfy the capacity constraint with probability at least 1 - α (chance constraint). Combines combinatorial optimization with probabilistic feasibility.

Applications: Project selection under cost uncertainty, resource allocation, investment planning.

max x Σ i v i x i s.t. P (Σ i w̃ i x i \leq W) \geq 1 - α x i \in {0, 1}

Algorithm	Type	Complexity	Reference	Description
Greedy (Mean Weight)	Heuristic	O(n log n)	—	Value-density ranking using expected weights as deterministic proxy
Chance-Constrained Greedy	Heuristic	O(n² × S)	Kleinberg et al. (2000)	Add items greedily while maintaining P(feasible) ≥ 1 - α
Simulated Annealing	Metaheuristic	Varies	—	Flip-bit neighborhood with infeasibility penalty in objective

Benchmarks: Random instances with normally-distributed weights; correlated weight scenarios; Kleinberg et al. adaptive instances

Chance-Constrained Facility Location

11 TESTS

CCFL | stochastic demands | min cost s.t. P(capacity) ≥ 1 - α

Open facilities and assign customers to minimize total fixed and assignment cost, subject to a probabilistic capacity constraint: the probability that demand assigned to each open facility exceeds its capacity must be at most α.

Applications: Warehouse location, hospital planning, disaster relief depot siting, cell tower placement.

min Σ i f i y i + Σ i,j c ij x ij s.t. P (Σ j d̃ j x ij \leq Q i) \geq 1 - α \forall i

Algorithm	Type	Complexity	Reference	Description
Greedy Open	Heuristic	O(m × n × S)	—	Iteratively open most cost-reducing facility with chance constraint checks
Mean-Demand Greedy	Heuristic	O(m × n)	—	Deterministic proxy using expected demands for capacity planning
Simulated Annealing	Metaheuristic	Varies	—	Toggle/swap moves with Boltzmann acceptance and violation penalty

Benchmarks: Stochastic facility location instances with Gaussian demands; Snyder (2006) CCFL test cases

Robust Portfolio Optimization

14 TESTS

RPO | ellipsoidal uncertainty | max robust return - λ · variance

Markowitz mean-variance portfolio optimization extended with ellipsoidal uncertainty on expected returns. The robust formulation penalizes exposure to estimation error in mean returns, producing portfolios that are less sensitive to input misspecification. Reduces to a second-order cone program (SOCP).

Applications: Asset allocation, pension fund management, hedge fund strategy, index tracking.

max w μ T w - δ \cdot || Σ 1/2 w || 2 - λ \cdot w T Σ w s.t. Σ i w i = 1, w i \geq 0

Algorithm	Type	Complexity	Reference	Description
QP Solver (Mean-Variance)	Exact	O(n³)	Markowitz (1952)	SLSQP on classical Markowitz objective without robustness
QP Solver (Robust SOCP)	Exact	O(n³)	Goldfarb & Iyengar (2003)	SLSQP on SOCP-representable objective with ellipsoidal uncertainty penalty (general NLP solver, not dedicated conic)
Equal Weight (1/n)	Heuristic	O(1)	DeMiguel et al. (2009)	Naive diversification; surprisingly competitive baseline
Minimum Variance	Heuristic	O(n³)	—	Σ^-11 (normalized) closed-form; minimizes portfolio variance regardless of return
Maximum Return	Heuristic	O(n)	—	Concentrate on asset with highest expected return

CVaR — Conditional Value-at-Risk

Rockafellar & Uryasev (2000) showed that CVaR (expected loss beyond the α-quantile) can be minimized via linear programming, making it a tractable alternative to variance for measuring downside risk. The key insight: minimizing CVaR simultaneously yields the optimal VaR. For portfolio optimization, replacing variance with CVaR produces:

min w CVaR α (- w T r) // minimizes expected tail loss at confidence level α

This is a convex LP for discrete scenarios, making it more computationally tractable than the robust SOCP above for large-scale problems. CVaR is a coherent risk measure (satisfying subadditivity, monotonicity, positive homogeneity, and translation invariance).

Uncertainty Radius δ

In the robust formulation above, δ controls the size of the ellipsoidal uncertainty set around the estimated mean return μ. Larger δ provides more protection against estimation error but sacrifices expected return. Setting δ = 0 recovers the classical Markowitz model. The parameter can be calibrated from data via cross-validation or set based on the number of historical observations (e.g., δ ≈ √(n) for n samples).

Benchmarks: Fama-French factor datasets; historical S&P 500 sector returns; DeMiguel et al. (2009) test portfolios

Efficient Frontier Explorer

Portfolio Parameters

Assets (n): 5

Risk aversion (λ): 0.50

Uncertainty (δ): 0.30

Actions

Efficient Frontier

Generate assets and click Compute Frontier to compare Markowitz vs. Robust portfolios.

Portfolio Weights

Strategy	Return	Risk (σ)	Weights
No results yet

Stochastic Vehicle Routing

13 TESTS

SVRP | stochastic demands | min E[routing + recourse cost]

Capacitated vehicle routing where customer demands are random variables. Routes are designed a priori; when a vehicle's capacity is exceeded during service, a recourse action (e.g., return to depot to unload) is triggered. The objective includes both planned routing cost and expected recourse cost.

Applications: Delivery logistics, waste collection, fuel distribution, last-mile delivery.

min cost (routes) + E [recourse (routes, D̃)] s.t. P (Σ i \in r d̃ i \leq Q) \geq 1 - α \forall route r

Algorithm	Type	Complexity	Reference	Description
CC Clarke-Wright Savings	Heuristic	O(n² log n)	Laporte et al. (2002)	Chance-constrained savings-based merging with probabilistic route overflow check
Mean-Demand Savings	Heuristic	O(n² log n)	Clarke & Wright (1964)	Classical Clarke-Wright using expected demands as deterministic proxy
Simulated Annealing	Metaheuristic	Varies	—	Relocate/swap/2-opt with recourse penalty for constraint violations

Benchmarks: Modified Solomon VRPTW instances with stochastic demands; Gendreau et al. (1996) SVRP instances; Laporte et al. recourse benchmarks

Robust Scheduling

13 TESTS

1 | uncertain p_j | min max-regret Σw_jC_j

Single machine scheduling where processing times are uncertain, specified as intervals [p_j^min, p_j^max] or discrete scenarios. The objective is to find a job sequence minimizing the worst-case regret of total weighted completion time compared to the optimal schedule for each scenario.

Applications: Manufacturing with variable task durations, operating room scheduling, maintenance planning.

min π max s \in S [Σ j w j C j (π, s) - Σ j w j C j (π* s, s) ] where π* s = WSPT (s) // Optimal for each scenario

Algorithm	Type	Complexity	Reference	Description
Midpoint WSPT	Heuristic	O(n log n)	Daniels & Kouvelis (1995)	WSPT on mean processing times as robust approximation
Scenario Enumeration	Heuristic	O(S × n log n)	Kouvelis & Yu (1997)	WSPT per scenario, cross-evaluate regret, select minimum
Worst-Case WSPT	Heuristic	O(n log n)	—	WSPT using maximum processing times for conservative schedule
Simulated Annealing	Metaheuristic	Varies	—	Swap/insertion neighborhood to minimize max regret across scenarios

Benchmarks: Interval-based processing time instances; Daniels & Kouvelis (1995) scenario sets; OR-Library single-machine scheduling instances with uncertainty

Distributionally Robust Optimization

12 TESTS

DRO | ambiguity set A | min max_P∈A E_P[f(x, ξ)]

Optimize against the worst-case probability distribution within an ambiguity set. This bridges stochastic optimization (known distribution) and robust optimization (worst-case over uncertainty set) by considering families of distributions defined via Wasserstein distance or moment constraints.

Applications: Supply chain under distributional ambiguity, data-driven decision-making, machine learning robustness, risk management.

Wasserstein DRO: min x max P : W (P, P̂) \leq ε E P [f (x, ξ)] Moment-Based DRO: min x max P : E [ξ] = μ, Cov [ξ] ⪯ Σ E P [f (x, ξ)]

Algorithm	Type	Complexity	Reference	Description
Wasserstein DRO LP	Exact	O(S × LP)	Mohajerin Esfahani & Kuhn (2018)	LP reformulation with L1-norm regularization for 1-Wasserstein ambiguity set
Nominal LP	Baseline	O(LP)	—	Standard LP without distributional robustness; comparison benchmark for DRO methods
Moment-Based DRO	Heuristic	O(G × S × LP)	Delage & Ye (2010)	Inner LP for worst-case distribution over moment ambiguity set, outer grid search over decisions

Other Ambiguity Sets in DRO

Beyond Wasserstein and moment-based sets, a major family uses φ-divergence (Ben-Tal et al., 2013): the ambiguity set contains all distributions P such that D_φ(P || P̂) ≤ ρ, where D_φ is a divergence measure (KL divergence, χ²-distance, total variation, etc.). Key properties:

KL-divergence DRO — Equivalent to entropic risk minimization; connects DRO to regularization in machine learning.
χ²-divergence DRO — Yields SOCP reformulations for linear loss functions; tractable for large-scale problems.
Total Variation — Bounds the maximum pointwise probability shift; useful when contamination is sparse.

The choice of ambiguity set reflects prior knowledge: Wasserstein is natural for metric spaces with limited data, φ-divergence for problems with a reliable reference distribution, and moment-based when only summary statistics are available.

Benchmarks: Newsvendor and portfolio instances from Mohajerin Esfahani & Kuhn (2018); synthetic moment-ambiguity instances from Delage & Ye (2010)

Test Coverage

110 tests across 9 problem implementations

Problem	Tests	Test Classes	Paradigm	Run Command
Newsvendor	13	3	Stochastic	pytest .../newsvendor/tests/ -v
Two-Stage SP	10	4	Stochastic	pytest .../two_stage_sp/tests/ -v
Robust Shortest Path	13	4	Robust	pytest .../robust_shortest_path/tests/ -v
Stochastic Knapsack	11	3	Stochastic	pytest .../stochastic_knapsack/tests/ -v
Chance-Constrained FL	11	3	Stochastic	pytest .../chance_constrained_fl/tests/ -v
Robust Portfolio	14	3	Robust	pytest .../robust_portfolio/tests/ -v
Stochastic VRP	13	3	Stochastic	pytest .../stochastic_vrp/tests/ -v
Robust Scheduling	13	3	Robust	pytest .../robust_scheduling/tests/ -v
DRO	12	4	DRO	pytest .../dro/tests/ -v
Total	110	30		pytest problems/9_uncertainty_modeling/ -v