Family 9 · OR Problem Family
Uncertainty Modeling
Mathematical paradigms for optimizing decisions when problem parameters are uncertain. Stochastic programming hedges against random outcomes, robust optimization guards against worst-case realizations, and distributionally robust methods protect against ambiguity in the probability distribution itself.
Quick Navigation
Newsvendor Problem
The Newsvendor Problem is the foundational single-period stochastic inventory model. A retailer orders Q units of a perishable product before random demand D is realized. Unsold units incur overage cost co = c − v, while unmet demand incurs underage cost cu = p − c. The optimal order quantity satisfies the celebrated critical fractile condition, making it one of the few stochastic optimization problems with an elegant closed-form solution.
// Optimal solution (critical fractile):
Q* = F−1(cu / (cu + co)) = F−1((p − c) / (p − v))
// For Normal demand D ~ N(μ, σ²):
Q* = μ + z · σ where z = Φ−1(cu / (cu + co))
The optimal order quantity Q* is the quantile of the demand distribution at level cu / (cu + co). Equivalently, P(D ≤ Q*) = (p − c) / (p − v). A higher shortage-to-total-cost ratio drives a higher fill probability.
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Critical Fractile | Exact | O(S log S) | Sort discrete scenarios, scan CDF to find optimal quantile. Optimal for any demand distribution. |
| Grid Search | Exact | O(S · G) | Brute-force evaluation over a grid of candidate order quantities within the demand range. |
| Marginal Allocation | Heuristic | O(n · B) | Multi-product newsvendor with budget constraint. Greedy allocation of incremental units. |
| Independent + Scale | Heuristic | O(n · S) | Solve each product independently, then scale down proportionally to fit the budget. |
Two-Stage Stochastic Programming
Two-Stage Stochastic Programming is the workhorse framework for sequential decision-making under uncertainty. First-stage decisions x are committed before the random scenario is revealed; second-stage recourse actions y(s) correct for any mismatch after observing the outcome. The deterministic equivalent LP expands all scenarios explicitly, growing linearly with the number of scenarios S.
s.t. Ax = b // first-stage feasibility
T(s)x + W(s)y(s) ≤ h(s) ∀s // recourse feasibility
x ≥ 0, y(s) ≥ 0 ∀s
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Deterministic Equivalent | Exact | O((m1+S·m2) vars) | Extensive form LP expanding all scenarios. Solved via HiGHS. Exact but size grows with S. |
| Expected Value (EV) | Heuristic | O(LP solve) | Solve on mean scenario only. Provides a lower bound; the gap to the stochastic solution is the VSS. |
| Sample Average Approximation | O(R · LP(N)) | Solve on R random scenario subsets of size N, replicate for statistical confidence bounds. |
VSS = EEV − RP, where EEV is the expected cost of the expected-value solution evaluated against all scenarios, and RP is the recourse problem optimum. A large VSS indicates that ignoring uncertainty is costly and the stochastic model adds significant value.
Robust Shortest Path
The Robust Shortest Path Problem finds an s-t path in a directed graph where edge weights vary across S discrete scenarios. Under the min-max cost criterion the path minimizes the worst-case total weight; under the min-max regret criterion it minimizes the worst-case deviation from the scenario-optimal path. Min-max cost is polynomial for discrete scenarios via label-setting; min-max regret is NP-hard for general interval data.
minP maxs ∈ S Σe ∈ P ws(e)
// Min-Max Regret:
minP maxs ∈ S [costs(P) − costs(P*s)]
// where P*s is the optimal path under scenario s
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Label-Setting | Exact | O(S · (V+E) log V) | Multi-objective Dijkstra with S-dimensional cost vectors and dominance pruning. |
| Scenario Enumeration | Exact | O(S · (V+E) log V) | Run Dijkstra per scenario, cross-evaluate all candidate paths under all scenarios. |
| Regret Enumeration | Heuristic | O(S² · (V+E) log V) | Evaluate candidate paths from each scenario against per-scenario optima for regret. |
| Midpoint Heuristic | Heuristic | O((V+E) log V) | Shortest path on the mean-weight graph. Fast single Dijkstra call but ignores worst-case structure. |
Stochastic Knapsack
The Stochastic Knapsack Problem extends the classical 0-1 knapsack by introducing random item weights that vary across S scenarios. Items have deterministic values but uncertain weights, and the capacity constraint must hold with probability at least 1 − α (chance-constrained formulation). This models real-world uncertainty in resource consumption such as project durations, bandwidth requirements, or fuel consumption.
s.t. P(Σi=1..n Wi xi ≤ W) ≥ 1 − α // chance constraint
xi ∈ {0, 1} ∀i
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Greedy (Mean Weight) | Heuristic | O(n log n) | Value-density ranking on E[Wi]. Simple but ignores variance of weights. |
| Greedy (Chance-Constrained) | Heuristic | O(n · S) | Adds items greedily while maintaining P(feasible) ≥ 1 − α by checking all scenarios. |
| Simulated Annealing | O(I · n · S) | Flip-bit neighborhood with infeasibility penalty. Boltzmann acceptance for exploration. |
Distributionally Robust Optimization
Distributionally Robust Optimization (DRO) optimizes against the worst-case distribution within an ambiguity set, rather than a single assumed distribution. The Wasserstein ambiguity set constrains the 1-Wasserstein distance from a nominal (empirical) distribution to at most ε, yielding an LP reformulation with an L1-norm regularization term. Moment-based ambiguity constrains the mean to lie within a tolerance of the empirical mean. DRO bridges stochastic programming (optimistic) and robust optimization (conservative).
s.t. Ax ≤ b
// Wasserstein dual reformulation:
maxP EP[f(x, ξ)] = Ê[f(x, ξ)] + ε · ||x||*
// Ambiguity sets:
Wasserstein: {P : W1(P, P̂) ≤ ε} → LP with L1 regularization
Moment: {P : ||EP[ξ] − μ̂||∞ ≤ τ} → LP over simplex
| Algorithm | Type | Ambiguity | Description |
|---|---|---|---|
| Wasserstein LP | Exact | Wasserstein | Tractable LP reformulation via strong duality. Wasserstein penalty acts as regularization. |
| Nominal LP | Exact | None | Baseline optimization under the empirical distribution P̂ only. No robustness guarantee. |
| Moment-Based DRO | Heuristic | Moment | Grid search over x, with inner LP for the worst-case distribution matching moment constraints. |
For a 1-Wasserstein ball of radius ε around the empirical distribution, the worst-case expected cost equals the nominal expected cost plus ε times the dual norm of x. This elegant regularization connection explains why DRO with Wasserstein ambiguity produces solutions that generalize well out of sample.
More Problems
Additional uncertainty modeling formulations in this family
Chance-Constrained FL
Open facilities and assign customers minimizing total cost, subject to per-facility capacity chance constraints under stochastic demands. Solved via greedy heuristics with feasibility checks and toggle/swap simulated annealing.
Robust Portfolio
Markowitz mean-variance portfolio optimization with ellipsoidal uncertainty on expected returns. The robust penalty δ||Σ1/2w|| shrinks allocations to high-uncertainty assets. Solved via QP (SLSQP) and closed-form baselines.
Stochastic VRP
CVRP with stochastic customer demands. Routes are designed a priori; when a vehicle overflows mid-route it returns to the depot (recourse). Chance-constrained Clarke-Wright savings and SA with recourse penalty.
Robust Scheduling
Single machine scheduling with uncertain processing times across S scenarios. Minimizes worst-case regret of total weighted completion time. Midpoint WSPT, scenario enumeration, and simulated annealing approaches.