17.2 Two-stage stochastic programs

Two-stage stochastic programming tackles decision-making under uncertainty. It splits choices into "here-and-now" decisions before uncertainty unfolds and "wait-and-see" decisions after. This approach helps balance immediate actions with future flexibility.

The method uses scenarios to represent possible outcomes and aims to minimize overall costs. It's a powerful tool for optimizing complex systems, from energy production to supply chain management, where future conditions are uncertain but critical to success.

Two-Stage Stochastic Programming Formulations

Fundamental Concepts and Structure

• Two-stage stochastic programming models decision-making under uncertainty with decisions made in two stages: before and after uncertain parameter realization
• First stage involves "here-and-now" decisions before uncertainty revelation, second stage involves "wait-and-see" decisions after uncertainty resolution
• Objective function minimizes sum of first-stage costs and expected value of second-stage costs
• Scenario generation creates finite set of possible uncertain parameter realizations (weather patterns, market demands)
• Formulation includes first-stage decision variables (production capacity), second-stage decision variables (actual production), and scenario-dependent constraints linking stages
• Non-anticipativity constraints ensure second-stage decisions depend only on available information at that stage

Mathematical Representation and Solving Approaches

• Deterministic equivalent problem (DEP) represents all scenarios simultaneously as large-scale linear or mixed-integer program
• DEP solved using standard optimization techniques (simplex method, interior point methods)
• General form of two-stage stochastic program: $\min_{x} c^T x + \mathbb{E}_{\xi}[Q(x,\xi)]$ $\text{s.t. } Ax = b, x \geq 0$ where $Q(x,\xi) = \min_{y} q^T y$ $\text{s.t. } Tx + Wy = h(\xi), y \geq 0$
• $x$ represents first-stage decisions, $y$ represents second-stage decisions, $\xi$ represents random vector
• $T$ called technology matrix, $W$ called recourse matrix

Advanced Modeling Techniques

• Incorporate risk measures (Conditional Value-at-Risk) into objective function balancing expected performance and risk exposure
• Multi-stage extensions model sequential decision-making processes (energy production planning)
• Chance constraints handle probabilistic constraints (meeting demand with certain probability)
• Robust optimization techniques address ambiguity in probability distributions
• Integration with machine learning methods for improved scenario generation and solution approaches

Solving Two-Stage Stochastic Programs

Decomposition Methods

• L-shaped method (Benders decomposition) solves two-stage stochastic linear programs by iteratively generating cutting planes
• Algorithm decomposes problem into master problem (first stage) and subproblems (second stage)
• Progressive hedging uses scenario decomposition, effective for problems with integer first-stage variables
• Method relaxes non-anticipativity constraints and uses augmented Lagrangian approach
• Stochastic Dual Dynamic Programming (SDDP) algorithm approximates multi-stage problems as series of two-stage problems
• SDDP builds piecewise linear approximation of future cost function

Simulation-Based Approaches

• Sample Average Approximation (SAA) uses Monte Carlo simulation for problems with large scenario sets
• SAA generates sample of scenarios, solves resulting approximation, repeats process to obtain statistical estimates
• Stochastic approximation methods (stochastic gradient descent) update solution based on sampled scenarios
• Scenario reduction techniques (fast forward selection, backward reduction) reduce computational burden

Direct Solution and Heuristic Methods

• Interior point methods solve deterministic equivalent problem directly, effective for large-scale linear two-stage stochastic programs
• Primal-dual interior point methods exploit problem structure for improved efficiency
• Heuristic methods (genetic algorithms, simulated annealing) employed for complex two-stage stochastic integer programs
• Metaheuristics combine local search with global exploration strategies
• Parallel computing techniques exploit problem's decomposable structure for efficient large-scale problem solving
• Distributed optimization algorithms (alternating direction method of multipliers) enable solving subproblems on separate processors

First-Stage vs Second-Stage Trade-offs

Performance Metrics and Analysis

• Value of the Stochastic Solution (VSS) quantifies benefit of stochastic programming over deterministic approach
• VSS calculated as difference between stochastic solution and expected value solution
• Expected Value of Perfect Information (EVPI) represents maximum amount decision-maker would pay for complete future information
• EVPI calculated as difference between wait-and-see solution and here-and-now solution
• Sensitivity analysis assesses how changes in first-stage decisions affect second-stage costs and decisions across scenarios
• Parametric analysis examines solution behavior as key parameters vary

Risk Management and Decision Strategies

• Risk measures (Conditional Value-at-Risk, Expected Shortfall) incorporated into objective function to balance performance and risk
• CVaR minimizes expected loss in worst-case scenarios, providing more conservative first-stage decisions
• Recourse actions in second stage allow corrective measures compensating for adverse effects of first-stage decisions
• Flexible recourse options (production ramp-up, outsourcing) influence optimal first-stage strategy
• Stability analysis examines solution changes with problem data perturbations, providing insights into first-stage decision robustness
• Multi-criteria decision analysis techniques evaluate trade-offs between conflicting objectives in first and second stages
• Goal programming and interactive methods incorporate decision-maker preferences in trade-off analysis

Uncertainty Impact on Decisions

Comparative Analysis and Bounds

• Expected Value of the Wait-and-See Solution (EVWS) provides lower bound on optimal objective value
• EVWS represents best possible outcome if all uncertainty resolved before decision-making
• Scenario analysis solves problem for different scenario sets to understand decision and objective value changes
• What-if analysis examines impact of specific scenario realizations on optimal solution
• Stochastic dominance criteria compare decision strategies under uncertainty
• First-order stochastic dominance ensures strategy performs better for all possible outcomes
• Second-order stochastic dominance considers risk-averse decision-makers

Advanced Uncertainty Modeling

• Efficient frontier in stochastic programming illustrates trade-off between expected performance and risk
• Frontier helps decision-makers choose appropriate risk aversion level based on preferences
• Robust optimization techniques address ambiguity in probability distributions
• Distributionally robust optimization considers worst-case distribution within specified ambiguity set
• Correlation between uncertain parameters assessed through scenario generation techniques capturing dependencies
• Copula-based methods model complex dependencies between random variables
• Post-optimality analysis calculates optimality gaps and confidence intervals
• Analysis provides insights into solution quality and uncertainty impact on stability