Robustness Concepts for Knapsack and Network Design Problems under Data Uncertainty
Gamma-, Multi-band, Submodular, and Recoverable Robustness
- 250 pages
- English
- PDF
- Available on iOS & Android
Robustness Concepts for Knapsack and Network Design Problems under Data Uncertainty
Gamma-, Multi-band, Submodular, and Recoverable Robustness
About This Book
This thesis is concerned with mathematical optimization under data uncertainty using mixed integer linear programming (MILP) techniques. Our investigations follow the deterministic paradigm known as robust optimization. It allows to tackle an uncertain variant of a problem without increasing its complexity in theory or decreasing its computational tractability in practice.We consider four robustness concepts for robust optimization and describe their parametrization, application, and evaluation. The concepts are ?-robustness, its generalization multi-band robustness, the more general submodular robustness, and the two-staged adaptive approach called recoverable robustness.For each concept, we investigate the corresponding robust generalization of the knapsack problem (KP), a fundamental combinatorial problem and subproblem of almost every integer linear programming (ILP) problem, and many other optimization problems. We present ILP formulations, detailed polyhedral investigations including new classes of valid inequalities, and algorithms for each robust KP. In particular, our results for the submodular and recoverable robust KP are novel. Additionally, the recoverable robust KP is experimentally evaluated in detail.Further, we consider the ?-robust generalization of the capacitated network design problem (NDP). For example, the NDP arises from many application areas such as telecommunications, transportation, or logistics. We present MILP formulations, detailed polyhedral insights with new classes of valid inequalities, and algorithms for the ?-robustness NDP. Moreover, we consider the multi-band robust NDP, its MILP formulations, and generalized polyhedral results of the ?- robustness NDP.Finally, we present computational results for the ?-robustness NDP using real-world measured uncertain data from telecommunication networks. These detailed representative studies are based on our work with the German ROBUKOM project in cooperation with Partner Nokia Siemens Networks GmbH & Co. KG.Die vorliegende Dissertation untersucht mathematische Optimierung unter Unsicherheiten mittels Methoden der gemischt-ganzzahligen linearen Programmierung (MILP). Dabei folgen wir dem deterministischen Paradigma der robusten Optimierung. Dieses ermöglicht die Lösung unsicherer Problemvarianten ohne Erhöhung der theoretischen KomplexitĂ€t oder Verschlechterung der praktischen Lösbarkeit.Wir untersuchen vier Robustheitskonzepte und beschreiben deren Parametrisierung, Anwendung, und Evaluierung. Die untersuchten Konzepte sind ?-Robustheit (engl. ?-robustness), deren neue Verallgemeinerung Multi-Band-Robustheit (engl. multi-band robustness), die neue allgemeinere submodulare Robustheit (engl. submodular robustness), sowie der adaptive zweistufige Ansatz der wiederherstellbaren Robustheit (engl. recoverable robustness)FĂŒr jedes Konzept untersuchen wir die entsprechende robuste Verallgemeinerung des Rucksackproblems (engl. knapsack problem) (KP), eines der fundamentalen kombinatorischen Probleme und Teilproblem fast jeden Problems der ganzzahligen linearen Programmierung (ILP) und vieler anderer Optimierungsprobleme. Wir prĂ€sentieren ILP-Formulierungen, detaillierte polyedrische Studien mit neuen Klassen gĂŒltiger Ungleichungen und Algorithmen fĂŒr jedes robuste KP. Dabei sind insbesondere unsere Ergebnisse fĂŒr das submodular- und wiederherstellbar-robuste KP neuartig. ZusĂ€tzlich evaluieren wir das wiederherstellbar- robuste KP experimentell in einer detaillierten Rechenstudie.AuĂerdem betrachten wir die ?-robuste Verallgemeinerung des kapazitierten Netzwerkplanungsproblems (engl. capacitated network design problem) (NDP). Das NDP ist z. B. in Anwendungsproblemen aus den Bereichen Telekommunikation, Transport oder Logistik zu finden. FĂŒr das ?-robuste NDP prĂ€sentieren wir MILP-Formulierungen, detaillierte polyedrische Ergebnisse, neue Klassen gĂŒltiger Ungleichungen und Algorithmen. ZusĂ€tzlich untersuchen wir das Multi-Band-robuste NDP, dessen MILP-Formulierungen, sowie dessen polyedrische Struktur als Verallgemeinerung des ?-robusten NDP.AbschlieĂend prĂ€sentieren wir detaillierten Rechenstudien zum ?-robusten NDP mit real gemessenen unsicheren Daten verschiedener Telekommunikationsnetze. Diese reprĂ€sentativen Rechenergebnisse basieren auf unserer Arbeit im Projekt ROBUKOM in Kooperation mit Nokia Siemens Networks GmbH & Co. KG.
Frequently asked questions
Information
Table of contents
- ABSTRACT
- ZUSAMMENFASSUNG
- DANKSAGUNG
- CONTENTS
- INTRODUCTION
- PART ONE CONCEPTS
- CHAPTER ONE MATHEMATICAL PRELIMINARIES
- CHAPTER TWO OPTIMIZATION UNDER DATA UNCERTAINTY
- CHAPTER THREE ROBUSTNESS CONCEPTS
- PART TWO ROBUST KNAPSACK PROBLEMS
- CHAPTER FOUR THE Î-ROBUST KNAPSACK PROBLEM
- CHAPTER FIVE THE MULTI-BAND ROBUST KNAPSACK PROBLEM
- CHAPTER SIX THE SUBMODULAR KNAPSACK PROBLEM
- CHAPTER SEVEN THE RECOVERABLE ROBUST KNAPSACK PROBLEM
- CHAPTER EIGHT COMPUTATIONAL STUDIES
- PART THREE ROBUST NETWORK DESIGN PROBLEMS
- CHAPTER NINE THE Î-ROBUST NETWORK DESIGN PROBLEM
- CHAPTER TEN THE MULTI-BAND ROBUST NETWORK DESIGN PROBLEM
- CHAPTER ELEVEN COMPUTATIONAL STUDIES
- CONCLUSIONS
- LIST OF TABLES
- LIST OF FIGURES
- BIBLIOGRAPHY
- INDEX
- ABOUT THE AUTHOR