Robustness Concepts for Knapsack and Network Design Problems under Data Uncertainty

Gamma-, Multi-band, Submodular, and Recoverable Robustness

Vorschau

Leseprobe, PDF (160 KB)
Inhaltsverzeichnis, PDF (55 KB)

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.