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

✍ Scribed by Marc Goerigk, Michael Hartisch

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

✦ Synopsis

This book offers a self-contained introduction to the world of robust combinatorial optimization. It explores decision-making using the min-max and min-max regret criteria, while also delving into the two-stage and recoverable robust optimization paradigms. It begins by introducing readers to general results for interval, discrete, and budgeted uncertainty sets, and subsequently provides a comprehensive examination of specific combinatorial problems, including the selection, shortest path, spanning tree, assignment, knapsack, and traveling salesperson problems.

The book equips both students and newcomers to the field with a grasp of the fundamental questions and ongoing advancements in robust optimization. Based on the authors’ years of teaching and refining numerous courses, it not only offers essential tools but also highlights the open questions that define this subject area.

✦ Table of Contents

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