Two-Stage Stochastic Programming

These are the strategic commitments made before the random variables are observed. They must be feasible for all possible future scenarios and are often capital-intensive or difficult to reverse.

• Examples: Fleet size acquisition, warehouse location selection, long-term supplier contracts
• Mathematical form: Decision vector x that minimizes immediate cost plus expected future cost
• Key property: Non-anticipativity — the decision cannot depend on which scenario will materialize

After uncertainty is revealed, corrective operational actions are taken to adapt to the realized scenario. These decisions compensate for any infeasibility or suboptimality caused by the first-stage choice.

• Examples: Expedited shipping from alternate depots, spot-market capacity purchases, overtime labor scheduling
• Mathematical form: Recourse function Q(x, ξ) representing the optimal cost of adapting decision x to scenario ξ
• Recourse types: Simple recourse (penalty costs), general recourse (full re-optimization)

The continuous distribution of uncertain parameters is approximated by a discrete set of scenarios, each with an associated probability weight. This transforms the stochastic problem into a large deterministic equivalent.

• Scenario generation methods: Monte Carlo sampling, Latin Hypercube Sampling, moment matching
• Scenario reduction: Techniques like fast-forward selection prune similar scenarios to maintain tractability while preserving distributional fidelity
• Typical parameters: Customer demand at each node, travel times on arcs, service time variability

When scenarios are discrete and finite, the two-stage problem collapses into a single large-scale linear or mixed-integer program that can be solved with commercial solvers.

• Structure: Block-angular constraint matrix with first-stage variables linking all scenario subproblems
• Solution methods: Benders decomposition (L-shaped method) exploits this structure by separating the master problem from scenario subproblems
• Solver compatibility: Directly solvable in Gurobi, CPLEX, or OR-Tools for moderate scenario counts

A metric quantifying the benefit of explicitly modeling uncertainty versus using a deterministic model with expected values. It measures the cost of ignoring variability.

• Calculation: VSS = EEV − RP, where EEV is the expected result of using the deterministic solution, and RP is the recourse problem solution
• Interpretation: A positive VSS justifies the computational expense of stochastic modeling
• Contrast with EVPI: The Expected Value of Perfect Information measures the value of eliminating uncertainty entirely

These constraints enforce that first-stage decisions cannot foresee the future. In scenario-based formulations, they explicitly bind decision variables across scenarios to be identical until uncertainty is resolved.

• Implementation: Equality constraints forcing x₁ = x₂ = ... = xₙ across all scenarios for first-stage variables
• Lagrangian relaxation: Dualizing these constraints decomposes the problem into independent scenario subproblems, enabling parallel solution via progressive hedging
• Dynamic extension: Multi-stage stochastic programming relaxes these constraints sequentially as information is revealed over time

The corrective decision taken in the second stage after the uncertain parameters are revealed. In logistics, this is the real-time adjustment—such as dispatching an additional vehicle or rerouting a driver—made to compensate for a first-stage plan that became suboptimal due to a disruption. The cost of this action is the recourse cost, and the goal of two-stage programming is to minimize the sum of first-stage costs plus the expected recourse cost.

A structured representation of how uncertainty unfolds over time, used to discretize continuous probability distributions into a finite set of realizations. Each path from the root to a leaf represents a distinct scenario. For dynamic route optimization, a scenario tree might model:

• Branch 1: No traffic incident (probability 0.7)
• Branch 2: Minor delay on arterial A (probability 0.2)
• Branch 3: Major highway closure (probability 0.1) The first-stage decision must be feasible across all branches.

The maximum amount a decision-maker should be willing to pay to obtain a perfect forecast before committing to a first-stage decision. Mathematically, EVPI is the difference between the wait-and-see solution (optimal decision if uncertainty is resolved first) and the here-and-now solution (optimal stochastic solution). In fleet routing, a high EVPI indicates that investing in better predictive telemetry or traffic APIs yields significant operational savings.

A metric quantifying the benefit of explicitly modeling uncertainty versus using a deterministic approximation. VSS is calculated by taking the expected performance of the expected value solution (solving the problem with average parameter values) and comparing it to the true stochastic solution. A VSS near zero suggests a deterministic model suffices; a large VSS proves that ignoring variability leads to brittle, costly plans.

A fundamental principle in stochastic programming stating that decisions made at a given stage cannot depend on future realizations of uncertainty. In a two-stage model, this means the first-stage decision vector must be identical across all scenarios. When solving via scenario decomposition, these constraints are often dualized using Lagrangian relaxation, allowing the large problem to be split into independent scenario subproblems solved in parallel.

A Monte Carlo simulation-based method for solving stochastic programs when the underlying probability distribution is continuous or has an astronomically large scenario set. SAA works by:

• Generating N independent random samples from the distribution
• Solving the deterministic equivalent problem on this finite sample
• Repeating the process M times to build confidence intervals on the optimality gap This is the practical workhorse for applying two-stage programming to real-world logistics data.