Goerigk M. An Introduction to Robust Combinatorial Optimization...2024 torrent

Textbook in PDF format

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.
Preface
Contents
Symbols
Introduction
A Robust Decision-Making Problem
Purpose and Structure of This Book
References
Basic Concepts
Complexity
Big-O Notation
Polynomial-Time Complexity
NP-Hardness
Approximation Algorithms
Linear and Integer Linear Programming
Graph Structures
Combinatorial Problems
The Knapsack Problem
The Selection Problem
The Shortest Path Problem
The Minimum Spanning Tree Problem
The Assignment Problem
The Traveling Salesperson Problem
Scheduling Problems
The Matroid Optimization Problem
Further Reading
Exercises
Solutions
References
Robust Problems
Robust Decision Criteria
Uncertainty Sets
Comparing Criteria
Relationships to Multi-Criteria Optimization
Further Reading
Exercises
Solutions
References
General Reformulation Results
Convexity of Uncertainty Sets
Interval Uncertainty
Min-Max Problems
Two-Stage and Recoverable Problems
Min-Max Regret Problems
Discrete Uncertainty
Min-Max Problems
Two-Stage and Recoverable Problems
Min-Max Regret Problems
Polytopal Uncertainty
Min-Max Problems
Two-Stage and Recoverable Problems
Min-Max Regret Problems
Budgeted Uncertainty
Min-Max Problems
Two-Stage and Recoverable Problems
Min-Max Regret Problems
Relationships Between Uncertainty Sets
Further Reading
Exercises
Solutions
References
General Solution Methods
Scenario Generation
Abstract Method
Scenario Generation for Min-Max Problems
Scenario Generation for Min-Max Regret Problems
Scenario Generation for Two-Stage and Recoverable Problems
Approximation Methods
Reducing Discrete Uncertainty Sets
Norm-Based Approximation for Discrete Uncertainty Sets
Reducing Interval Uncertainty Sets
Pseudopolynomial Methods and Approximation Schemes
Further Reading
Exercises
Solutions
References
Robust Selection Problems
Min-Max Selection
Min-Max Regret Selection
Discrete Uncertainty
Interval Uncertainty
Budgeted Uncertainty
Two-Stage Selection
Discrete Uncertainty
Polytopal Uncertainty
Continuous Budgeted Uncertainty
Discrete Budgeted Uncertainty
Recoverable Selection
Discrete Uncertainty
Interval Uncertainty
Continuous Budgeted Uncertainty
Discrete Budgeted Uncertainty
Further Reading
Exercises
Solutions
References
Robust Shortest Path Problems
Min-Max Shortest Path
Min-Max Regret Shortest Path
Discrete Uncertainty
Interval Uncertainty
Two-Stage Shortest Path
Discrete Uncertainty
Discrete Budgeted Uncertainty
Recoverable Shortest Path
Discrete Uncertainty
Interval Uncertainty
Further Reading
Exercises
Solutions
References
Robust Spanning Tree Problems
Min-Max Spanning Tree
Min-Max Regret Spanning Tree
Discrete Uncertainty
Interval Uncertainty
Two-Stage Spanning Tree
Recoverable Spanning Tree
Discrete Uncertainty
Interval Uncertainty
Discrete Budgeted Uncertainty
Further Reading
Exercises
Solutions
References
Other Combinatorial Problems
Robust Assignment Problems
Robust Knapsack Problems
Robust Traveling Salesperson Problems
Robust Scheduling Problems
Further Reading
Exercises
Solutions
References
Other Models for Robust Optimization
Ordered Weighted Averaging
Ellipsoidal Uncertainty
K-Adaptability and Min-Max-Min
Decision-Dependent Uncertainty
Further Reading
Exercises
Solutions
References
Open Problems
A Problem Definitions
Alphabetical Index