Computational Stochastic Programming: Models, Algorithms, and Implementation (Springer Optimization and Its Applications, 774)

✍ Scribed by Lewis Ntaimo

• Publisher: Springer
• Year: 2024
• Tongue: English
• Leaves: 518
• Edition: 2024
• Category: Library

✦ Synopsis

This book provides a foundation in stochastic, linear, and mixed-integer programming algorithms with a focus on practical computer algorithm implementation. The purpose of this book is to provide a foundational and thorough treatment of the subject with a focus on models and algorithms and their computer implementation. The book’s most important features include a focus on both risk-neutral and risk-averse models, a variety of real-life example applications of stochastic programming, decomposition algorithms, detailed illustrative numerical examples of the models and algorithms, and an emphasis on computational experimentation. With a focus on both theory and implementation of the models and algorithms for solving practical optimization problems, this monograph is suitable for readers with fundamental knowledge of linear programming, elementary analysis, probability and statistics, and some computer programming background. Several examples of stochastic programming applications areincluded, providing numerical examples to illustrate the models and algorithms for both stochastic linear and mixed-integer programming, and showing the reader how to implement the models and algorithms using computer software.

✦ Table of Contents

Preface
Contents
Acronyms
Part I Foundations
1 Introduction
1.1 Introduction
1.2 Preliminaries
1.2.1 Basic Notations
1.2.2 Vectors and Matrices
1.2.3 Convex Sets and Functions
1.2.4 Separation Hyperplanes
1.2.5 Random Variables
1.3 Deterministic to Stochastic Programming
1.3.1 Scenario Trees
1.3.2 Expected Value Solution
1.3.3 Scenario Analysis Solution
1.3.4 Extreme Event Solution
1.3.5 Two-Stage Recourse Model
1.3.6 Relationships Among EV, SA, and RP Models
1.3.7 Probabilistic (Chance) Constraints Model
1.3.8 Integrated-Chance Constraints
1.3.9 Multistage Model
Bibliographic Notes
Problems
References
2 Stochastic Programming Models
2.1 Introduction
2.2 Risk-Neutral Models
2.2.1 Structural Properties
2.2.2 Scenario Formulation
2.3 Mean-Risk Models
2.3.1 Quantile Risk Measures
Excess Probability
Quantile Deviation
Conditional Value-at-Risk
2.3.2 Deviation Risk Measures
Expected Excess
Absolute Semideviation
Central Deviation
2.4 Checking Coherence Properties of a Risk Measure
2.4.1 Example: Conditional Value-at-Risk
2.4.2 Example: Mean-Risk Conditional Value-at-Risk
2.4.3 Example: Alternative Mean-Risk Conditional Value-at-Risk
2.4.4 Example: Expected Excess
2.4.5 Example: Mean-Risk Expected Excess
2.5 Deterministic Equivalent Problem Formulations
2.5.1 Risk-Neutral Case
2.5.2 Excess Probability
2.5.3 Quantile Deviation
2.5.4 Conditional Value-at-Risk
2.5.5 Expected Excess
2.5.6 Absolute Semideviation
2.5.7 Central Deviation
2.6 Probabilistically Constrained Models
2.6.1 Probabilistically Constrained Models
2.6.2 Single-Chance Constrained Models
2.6.3 Deterministic Equivalent Problem Formulation
2.7 Other Models
Problems
References
Part II Modeling and Example Applications
3 Modeling and Illustrative Numerical Examples
3.1 Introduction
3.2 Motivating Example
3.2.1 Deterministic Setting
3.2.2 Stochastic Setting
3.3 Risk-Neutral Approaches
3.3.1 Linear Programming and Simple Profit Analysis
3.3.2 Expected Value Solution
3.3.3 Scenario Analysis Solution
3.3.4 Extreme Event Solution
3.3.5 Two-Stage Risk-Neural Recourse Model
3.3.6 Putting Everything Together
3.4 Risk-Averse Approaches
3.4.1 Excess Probability Model
3.4.2 Conditional Value-at-Risk Model
3.4.3 Expected Excess Model
3.4.4 Probabilistic (Chance) Constraints Model
Problems
References
4 Example Applications of Stochastic Programming
4.1 Introduction
4.2 Capacity Expansion Problem (CEP)
4.3 Stochastic Server Location Problem (SSLP)
4.4 Stochastic Supply Chain Planning Problem
4.5 Fuel Treatment Planning
4.6 Appointment Scheduling in Nuclear Medicine
4.7 Airport Time Slot Allocation Under Uncertainty
4.8 Stochastic Air Traffic Flow Management
4.9 Satellite Constellation Scheduling Under Uncertainty
4.10 Wildfire Response Planning
4.11 Optimal Vaccine Allocation for Epidemics
Problems
References
Part III Deterministic and Risk-Neutral Decomposition Methods
5 Deterministic Large-Scale Decomposition Methods
5.1 Introduction
5.2 Kelley's Cutting-Plane Method
5.2.1 Algorithm
5.2.2 Numerical Example
5.2.3 Convergence of Kelley's Cutting-Plane Algorithm
5.3 Benders Decomposition
5.3.1 Decomposition Approach
5.3.2 Algorithm
5.3.3 Numerical Examples
5.3.4 Regularized Benders Decomposition
5.4 Dantzig–Wolfe Decomposition
5.4.1 Decomposition Approach
5.4.2 Algorithm
5.4.3 Numerical Example
5.5 Lagrangian Decomposition
5.5.1 Decomposition Approach
5.5.2 Algorithm
5.5.3 Numerical Example
Problems
References
6 Risk-Neutral Stochastic Linear Programming Methods
6.1 Introduction
6.2 The L-Shaped Method
6.2.1 Decomposition Approach
6.2.2 The L-Shaped Algorithm
6.2.3 Numerical Example
6.3 The Multicut Method
6.3.1 Multicut Decomposition
6.3.2 Multicut L-Shaped Algorithm
6.3.3 Numerical Example
6.4 Adaptive Multicut Method
6.4.1 Adaptive Multicut Decomposition Approach
6.4.2 Basic Adaptive Multicut Algorithm
6.4.3 Numerical Example
6.5 Lagrangian Based Methods
6.5.1 Progressive Hedging Decomposition Approach
6.5.2 Progressive Hedging Algorithm
Bibliographic Notes
Problems
References
Part IV Risk-Averse, Statistical, and Discrete Decomposition Methods
7 Mean-Risk Stochastic Linear Programming Methods
7.1 Introduction
7.2 Aggregated Cut Decomposition for QDEV, CVaR, and EE
7.2.1 Quantile Deviation
7.2.2 Conditional Value-at-Risk
7.2.3 Expected Excess
7.2.4 D-AGG Algorithm
7.2.5 Numerical Example
7.3 Separate Cut Decomposition for QDEV, CVaR, and EE
7.3.1 Quantile Deviation
7.3.2 Conditional Value-at-Risk
7.3.3 Expected Excess
7.3.4 D-SEP Algorithm
7.3.5 Numerical Example
7.4 Aggregated Cut Decomposition for ASD
7.4.1 Subgradient Optimization Approach
7.4.2 ASD-AGG Algorithm
7.4.3 Numerical Example
7.5 Separate Cut Decomposition for ASD
7.5.1 Subgradient Optimization Approach
7.5.2 ASD-SEP Algorithm
7.5.3 Numerical Example
Bibliographic Notes
Problems
References
8 Sampling-Based Stochastic Linear Programming Methods
8.1 Introduction
8.2 Example Numerical Instance
8.3 Generating Random Samples
8.3.1 Numerical Example 1: Continuous Distribution
8.3.2 Numerical Example 2: Discrete Distribution
8.3.3 Numerical Example 3: STOCH File
8.4 Exterior Sampling
8.4.1 Sample Average Approximation
8.4.2 The Sample Average Approximation Scheme
8.4.3 Numerical Examples
8.5 Interior Sampling
8.5.1 Stochastic Decomposition
8.5.2 Stochastic Decomposition Algorithm
8.5.3 Numerical Example
8.5.4 Stabilizing the Stochastic Decomposition Algorithm
Bibliographic Notes
Problems
References
9 Stochastic Mixed-Integer Programming Methods
9.1 Introduction
9.2 Basic Structural Properties
9.3 Designing Algorithms for SMIP
9.4 Example Instance
9.5 Binary First-Stage
9.5.1 BFS Algorithm
9.5.2 Numerical Illustration of the BFS Algorithm
9.6 Fenchel Decomposition
9.6.1 Preliminaries
9.6.2 FD Algorithm
9.6.3 FD Cut Generation
9.6.4 Numerical Illustration of the FD Algorithm
9.7 Disjunctive Decomposition
9.7.1 Preliminaries
9.7.2 D2 Cut Generation
Generating the Common-Cut-Coefficients π
Convexifying π0(x,ω)
9.7.3 D2 Algorithm
9.7.4 Numerical Illustration of the D2 Algorithm
Bibliographic Notes
Problems
References
Part V Computational Considerations
10 Computational Experimentation
10.1 Introduction
10.2 Problem Data Input Formats
10.2.1 LP and MPS File Formats
10.2.2 SMPS File Format
CORE File
TIME File
STOCH File
10.3 Sparse Matrices
10.4 Program Design for SP Algorithm Implementation
10.5 Performing Computational Experiments
10.5.1 Solution Methods and Analysis of Algorithms
10.5.2 Empirical Analysis and Test Problems
10.5.3 Standard Test Instances
gbd
pgp2
LandS
ssn
Storm
cep1
20term
SIZES
SEMI
DCAP
SSLP
MPTSP
SMKP
VACCINE
PROBPORT
10.5.4 Reporting Computational Experiments
Bibliographic Notes
Problems
References
Index