An Introduction to Robust Combinatorial Optimization: Concepts, Models and Algorithms for Decision Making under Uncertainty (International Series in Operations Research & Management Science, 361)

Preface
Contents
Symbols
1 Introduction
	1.1 A Robust Decision-Making Problem
	1.2 Purpose and Structure of This Book
	References
2 Basic Concepts
	2.1 Complexity
		2.1.1 Big-O Notation
		2.1.2 Polynomial-Time Complexity
		2.1.3 NP-Hardness
		2.1.4 Approximation Algorithms
	2.2 Linear and Integer Linear Programming
	2.3 Graph Structures
	2.4 Combinatorial Problems
		2.4.1 The Knapsack Problem
		2.4.2 The Selection Problem
		2.4.3 The Shortest Path Problem
		2.4.4 The Minimum Spanning Tree Problem
		2.4.5 The Assignment Problem
		2.4.6 The Traveling Salesperson Problem
		2.4.7 Scheduling Problems
		2.4.8 The Matroid Optimization Problem
	2.5 Further Reading
	2.6 Exercises
	2.7 Solutions
	References
3 Robust Problems
	3.1 Robust Decision Criteria
	3.2 Uncertainty Sets
	3.3 Comparing Criteria
	3.4 Relationships to Multi-Criteria Optimization
	3.5 Further Reading
	3.6 Exercises
	3.7 Solutions
	References
4 General Reformulation Results
	4.1 Convexity of Uncertainty Sets
	4.2 Interval Uncertainty
		4.2.1 Min-Max Problems
		4.2.2 Two-Stage and Recoverable Problems
		4.2.3 Min-Max Regret Problems
	4.3 Discrete Uncertainty
		4.3.1 Min-Max Problems
		4.3.2 Two-Stage and Recoverable Problems
		4.3.3 Min-Max Regret Problems
	4.4 Polytopal Uncertainty
		4.4.1 Min-Max Problems
		4.4.2 Two-Stage and Recoverable Problems
		4.4.3 Min-Max Regret Problems
	4.5 Budgeted Uncertainty
		4.5.1 Min-Max Problems
		4.5.2 Two-Stage and Recoverable Problems
		4.5.3 Min-Max Regret Problems
	4.6 Relationships Between Uncertainty Sets
	4.7 Further Reading
	4.8 Exercises
	4.9 Solutions
	References
5 General Solution Methods
	5.1 Scenario Generation
		5.1.1 Abstract Method
		5.1.2 Scenario Generation for Min-Max Problems
		5.1.3 Scenario Generation for Min-Max Regret Problems
		5.1.4 Scenario Generation for Two-Stage and Recoverable Problems
	5.2 Approximation Methods
		5.2.1 Reducing Discrete Uncertainty Sets
		5.2.2 Norm-Based Approximation for Discrete Uncertainty Sets
		5.2.3 Reducing Interval Uncertainty Sets
	5.3 Pseudopolynomial Methods and Approximation Schemes
	5.4 Further Reading
	5.5 Exercises
	5.6 Solutions
	References
6 Robust Selection Problems
	6.1 Min-Max Selection
	6.2 Min-Max Regret Selection
		6.2.1 Discrete Uncertainty
		6.2.2 Interval Uncertainty
		6.2.3 Budgeted Uncertainty
	6.3 Two-Stage Selection
		6.3.1 Discrete Uncertainty
		6.3.2 Polytopal Uncertainty
		6.3.3 Continuous Budgeted Uncertainty
		6.3.4 Discrete Budgeted Uncertainty
	6.4 Recoverable Selection
		6.4.1 Discrete Uncertainty
		6.4.2 Interval Uncertainty
		6.4.3 Continuous Budgeted Uncertainty
		6.4.4 Discrete Budgeted Uncertainty
	6.5 Further Reading
	6.6 Exercises
	6.7 Solutions
	References
7 Robust Shortest Path Problems
	7.1 Min-Max Shortest Path
	7.2 Min-Max Regret Shortest Path
		7.2.1 Discrete Uncertainty
		7.2.2 Interval Uncertainty
	7.3 Two-Stage Shortest Path
		7.3.1 Discrete Uncertainty
		7.3.2 Discrete Budgeted Uncertainty
	7.4 Recoverable Shortest Path
		7.4.1 Discrete Uncertainty
		7.4.2 Interval Uncertainty
	7.5 Further Reading
	7.6 Exercises
	7.7 Solutions
	References
8 Robust Spanning Tree Problems
	8.1 Min-Max Spanning Tree
	8.2 Min-Max Regret Spanning Tree
		8.2.1 Discrete Uncertainty
		8.2.2 Interval Uncertainty
	8.3 Two-Stage Spanning Tree
	8.4 Recoverable Spanning Tree
		8.4.1 Discrete Uncertainty
		8.4.2 Interval Uncertainty
		8.4.3 Discrete Budgeted Uncertainty
	8.5 Further Reading
	8.6 Exercises
	8.7 Solutions
	References
9 Other Combinatorial Problems
	9.1 Robust Assignment Problems
	9.2 Robust Knapsack Problems
	9.3 Robust Traveling Salesperson Problems
	9.4 Robust Scheduling Problems
	9.5 Further Reading
	9.6 Exercises
	9.7 Solutions
	References
10 Other Models for Robust Optimization
	10.1 Ordered Weighted Averaging
	10.2 Ellipsoidal Uncertainty
	10.3 K-Adaptability and Min-Max-Min
	10.4 Decision-Dependent Uncertainty
	10.5 Further Reading
	10.6 Exercises
	10.7 Solutions
	References
11 Open Problems
A Problem Definitions
Alphabetical Index