Computational Stochastic Programming. Models, Algorithms, and Implementation

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