E-Medien mit freiem Zugriff (Kölner Universitäts-Publikations-Server)
Titel | Robust Design of Single-Commodity Networks |
---|---|
Verfasser | Schmidt, Daniel Rainer |
Urheber | Abteilung Informatik |
Ersch. Jahr | 2014 |
Web-Link | Volltext |
Sprache | Englisch |
Abstract | The results in the present work were obtained in a collaboration with Eduardo Álvarez-Miranda, Valentina Cacchiani, Tim Dorneth, Michael Jünger, Frauke Liers, Andrea Lodiand Tiziano Parriani.The subject of this thesis is a robust network design problem, i.e., a problem of the type“dimension a network such that it has sufficient capacity in all likely scenarios.” In our case,we model the network with an undirected graph in which each scenario defines a supply ordemand for each node. We say that a flow in the network is feasible for a scenario if it canbalance out its supplies and demands. A scenario polytope B defines which scenarios arerelevant. The task is now to find integer capacities that minimize the total installation costswhile allowing for a feasible flow in each scenario. This problem is called Single-CommodityRobust Network Design Problem (sRND) and was introduced by Buchheim, Liers and Sanità(INOC 2011). The problem contains the Steiner Tree Problem (given an undirected graphand a terminal set, find a minimum cost subtree that connects all terminals) and thereforeis N P-hard. The problem is also a natural extension of minimum cost flows.The network design literature treats the case that the scenario polytope B is given asthe finite set of its extreme points (finite case) and that it is given as the feasible regionof finitely many linear inequalities (polyhedral case). Both descriptions are equivalent,however, an efficient transformation is not possible in general.Buchheim, Liers and Sanità (INOC 2011) propose a Branch-and-Cut algorithm for thefinite case. In this case, there exists a canonical problem formulation as a mixed integerlinear program (MIP). It contains a set of flow variables for every scenario. Buchheim, Liersand Sanità enhance the formulation with general cutting planes that are called target cuts.The first part of the dissertation considers the problem variant where every scenario hasexactly two terminal nodes. If the underlying network is a complete, unweighted graph,then this problem is the Network Synthesis Problem as defined by Chien (IBM Journal ofR&D 1960). There exist polynomial time algorithms by Gomory and Hu (SIAM J. of Appl.Math 1961) and by Kabadi, Yan, Du and Nair (SIAM J. on Discr. Math.) for this specialcase. However, these algorithms are based on the fact that complete graphs are Hamiltonian.The result of this part is a similar algorithm for hypercube graphs that assumes a specialdistribution of the supplies and demands. These graphs are also Hamiltonian.The second part of the thesis discusses the structure of the polyhedron of feasible sRNDsolutions. Here, the first result is a new MIP-based capacity formulation for the sRNDproblem. The size of this formulation is independent of the number of extreme pointsof B and therefore, it is also suited for the polyhedral case. The formulation uses so-calledcut-set inequalities that are known in similar form from other network design problems. Byadapting a proof by Mattia (Computational Optimization and Applications 2013), we showthat cut-set inequalities induce facets of the sRND polyhedron. To obtain a better linearprogramming relaxation of the capacity formulation, we interpret certain general mixedinteger cuts as 3-partition inequalities and show that these inequalities induce facets as well.The capacity formulation has exponential size and we therefore need a separation algorithmfor cut-set inequalities. In the finite case, we reduce the cut-set separation problem toa minimum cut problem that can be solved in polynomial time. In the polyhedral case,however, the separation problem is N P-hard, even if we assume that the scenario polytopeis basically a cube. Such a scenario polytope is called Hose polytope. Nonetheless, we cansolve the separation problem in practice: We show a MIP based separation procedure forthe Hose scenario polytope. Additionally, the thesis presents two separation methods for3-partition inequalities. These methods are independent of the encoding of the scenariopolytope. Additionally, we present several rounding heuristics.The result is a Branch-and-Cut algorithm for the capacity formulation. We analyze thealgorithm in the last part of the thesis. There, we show experimentally that the algorithmworks in practice, both in the finite and in the polyhedral case. As a reference point, weuse a CPLEX implementation of the flow based formulation and the computational results byBuchheim, Liers and Sanità. Our experiments show that the new Branch-and-Cut algorithmis an improvement over the existing approach. Here, the algorithm excels on probleminstances with many scenarios. In particular, we can show that the MIP separation of thecut-set inequalities is practical. ; Die vorliegende Dissertation ist im Rahmen einer Kooperation mit Valentina Cacchiani, Frauke Liers, Andrea Lodi und Michael Jünger entstanden, an der in Teilen auch Eduardo Álvarez-Miranda, Tim Dorneth und Tiziano Parriani beteiligt waren. Das Thema der Arbeit ist ein robustes Netzwerkdesignproblem, d.h. ein Problem der Art „dimensioniere ein Netzwerk so, dass in allen realistischen Szenarien ausreichend Kapazität vorhanden ist.“ In dem konkreten Problem wird das Netzwerk durch einen ungerichteten Graphen modelliert, in dem jedes Szenario einen Angebots- oder Bedarfswert für jeden Knoten definiert. Ein Fluss im Netzwerk heißt zulässig, wenn er alle Angebote und Bedarfe ausgleicht. Welche Szenarien beachtet werden müssen, bestimmt das Szenarienpolytop B. Gesucht sind ganzzahlige Kapazitäten, die zwar die insgesamten Installationskosten min- imieren, aber in jedem Szenario b ∈ B die Existenz eines zulässigen Flusses garantieren. Dieses Single-Commodity Robust Network Design Problem (sRND) geht zurück auf eine Arbeit von Buchheim, Liers und Sanità (INOC 2011) und enthält als Spezialfall das Steiner- baumproblem (gegeben einen ungerichteten Graphen und eine Terminalmenge, finde einen Teilbaum mit minimalen Kosten, der alle Terminale verbindet). Es ist daher N P-schwierig. Außerdem ist es eine natürliche Erweiterung von Minimumkostenflüssen. Die Literatur unterscheidet die Fälle, dass B als endliche Menge seiner Extremalpunkte (endlicher Fall) oder als Lösungsmenge eines linearen Ungleichungssystems gegeben ist (polyedrischer Fall). Diese beiden Fälle sind zwar äquivalent, können jedoch im Allgemeinen nicht effizient ineinander überführt werden. Buchheim, Liers und Sanità (INOC 2011) schlagen einen Branch-and-Cut-Algorithmus für den endlichen Fall vor. In diesem Fall existiert eine kanonische Formulierung des Problems als gemischt-ganzzahliges lineares Programm (MIP). Sie enthält Flussvariablen für jedes Szenario. Um bessere Schranken zu erhalten, fügen Buchheim, Liers und Sanità zusätzlich allgemeine Schnittebenen, sog. Target Cuts, ein. Der erste Teil der Dissertation beschäftigt sich nun mit der Variante des Problems, in der jedes Szenario genau zwei Terminalknoten besitzt. Ist das Netzwerk zusätzlich ein ungewichteter vollständiger Graph, so handelt es sich um das Network Synthesis Problem im Sinne von Chien (IBM Journal of R&D, 1960). Für diesen Fall existieren polynomielle Algorithmen von Gomory und Hu (SIAM J. of Appl. Math. 1961) und Kabadi, Yan, Du und Nair (SIAM J. on Discr. Math. 2009), die jedoch darauf beruhen, dass vollständige Graphen hamiltonsch sind. Wir entwickeln unter der Voraussetzung, dass die Angebote und Bedarfe einer bestimmten Verteilung folgen, einen ähnlicher Algorithmus für Hyperwürfelgraphen. Diese Graphen sind ebenfalls hamiltonsch. Im zweiten Teil der Arbeit geht es um die Struktur des sRND-Lösungspolyeders. Hier ist das erste Ergebnis eine neue MIP-Kapazitätsformulierung des sRND-Problems, deren Größe unabhängig von der Anzahl der Extremalpunkte von B ist. Damit ist die For- mulierung auch für den polyedrischen Fall geeignet. Die Formulierung verwendet sogenannte Cut-Set-Ungleichungen, die in ähnlicher Form auch bei anderen Netzwerkdesignproblemen verwendet werden. Wir wandeln einen Beweis von Mattia (Computational Optimization and Applications 2013) ab und so zeigen so, dass die Cut-Set-Ungleichungen Facetten des Lösungpolyeders sind. Um eine bessere Relaxierung des ganzzahligen linearen Pro- gramms zu erreichen, interpretieren wir bestimmte generische Schnittebenen als sogenannte 3-Partitionsungleichungen und zeigen, dass auch diese Ungleichungen Facetten des Lö- sungspolyeders definieren. Da die Kapazitätsformulierung exponentielle Größe hat, benötigen wir einen Separierungsal- gorithmus für Cut-Set-Ungleichungen. Im endlichen Fall führen wir das Separierungsproblem auf ein Minimum-Schnitt-Problem zurück, das in Polynomialzeit gelöst werden kann. Im polyedrischen Fall ist das Separierungsproblem hingegen N P-schwierig, selbst wenn man davon ausgeht, dass das Szenarienpolytop im Wesentlichen ein Quader – das sogenannte Hose-Polytop – ist. Dennoch kann das Separierungsproblem in der Praxis gelöst werden: Wir zeigen hierzu einen MIP basierten Separierungsansatz für Hose-Szenarienpolytope. Weiterhin stellt die Arbeit zwei Separierungsalgorithmen für 3-Partitionsungleichungen vor, die unabhängig von der Codierung des Szenarienpolytops funktionieren. Zusätzlich führen wir einige Rundungsheuristiken ein. Das Ergebnis ist ein Branch-and-Cut-Algorithmus für die Kapazitätsformulierung, den wir im letzten Teil der Dissertation untersuchen. Dort weisen wir experimentell die praktische Leistungsfähigkeit des Branch-and-Cut-Algorithmus für den endlichen und den polyedrischen Fall nach. Als Referenzpunkt dient dazu eine CPLEX-Implementierung der Flussformulierung und die Rechenergebnisse von Buchheim, Liers und Sanità. Die Experimente zeigen, dass unser neuer Branch-and-Cut-Algorithmus eine Verbesserung des bisherigen Ansatzes darstellt. Dabei eignet er sich vorallem für Probleminstanzen mit vielen Szenarien. Es zeigt sich insbesondere, dass die MIP-Separierung der Schnittungleichungen im polyedrischen Fall auch praktisch anwendbar ist. |
Schlagwort | Network Design, Robustness, Combinatorial Optimization, Branch-and-Cut, Integer Linear Programming |
Mehr |
Open Access. Im Internet weltweit frei verfügbar