TY - GEN A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Combinatorial Online Optimization N2 - In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material. T3 - ZIB-Report - SC-98-24 KW - Online Optimization KW - competitiveness KW - combinatorial optimization KW - real-world problems Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3674 ER - TY - GEN A1 - Koster, Arie M.C.A. T1 - Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring N2 - In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality. T3 - ZIB-Report - 05-13 KW - wavelength assignment KW - optical networks KW - graph theory KW - combinatorial optimization KW - integer programming Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8478 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - A Configuration Model for the Line Planning Problem N2 - We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model. T3 - ZIB-Report - 13-40 KW - combinatorial optimization KW - polyhedral combinatorics KW - line planning Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41903 SN - 1438-0064 ER - TY - THES A1 - Helmberg, Christoph T1 - Semidefinite Programming for Combinatorial Optimization N2 - This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems. T3 - ZIB-Report - 00-34 KW - positive semidefinite matrices KW - semidefinite cone KW - semidefinite Programming KW - semidefinite duality KW - combinatorial optimization KW - max-cut KW - quadrati Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6022 ER - TY - THES A1 - Bley, Andreas T1 - Routing and Capacity Optimization for IP Networks N2 - This thesis is concerned with dimensioning and routing optimization problems for communication networks that employ a shortest path routing protocol such as OSPF, IS-IS, or RIP. These protocols are widely used in the Internet. With these routing protocols, all end-to-end data streams are routed along shortest paths with respect to a metric of link lengths. The network administrator can configure the routing only by modifying this metric. In this thesis we consider the unsplittable shortest path routing variant, where each communication demand must be sent unsplit through the network. This requires that all shortest paths are uniquely determined. The major difficulties in planning such networks are that the routing can be controlled only indirectly via the routing metric and that all routing paths depend on the same routing metric. This leads to rather complicated and subtle interdependencies among the paths that comprise a valid routing. In contrast to most other routing schemes, the paths for different communication demands cannot be configured independent of each other. Part I of the thesis is dedicated to the relation between path sets and routing metrics and to the combinatorial properties of those path sets that comprise a valid unsplittable shortest path routing. Besides reviewing known approaches to find a compatible metric for a given path set (or to prove that none exists) and discussing some properties of valid path sets, we show that the problem of finding a compatible metric with integer lengths as small as possible and the problem of finding a smallest possible conflict in the given path set are both NP-hard to approximate within a constant factor. In Part II of the thesis we discuss the relation between unsplittable shortest path routing and several other routing schemes and we analyze the computational complexity of three basic unsplittable shortest path routing problems. We show that the lowest congestion that can be obtained with unsplittable shortest path routing may significantly exceed that achievable with other routing paradigms and we prove several non-approximability results for unsplittable shortest path routing problems that are stronger than those for the corresponding unsplittable flow problems. In addition, we derive various polynomial time approximation algorithms for general and special cases of these problems. In Part III of the thesis we finally develop an integer linear programming approach to solve these and more realistic unsplittable shortest path routing problems to optimality. We present alternative formulations for these problems, discuss their strength and computational complexity, and show how to derive strong valid inequalities. Eventually, we describe our implementation of this solution approach and report on the numerical results obtained for real-world problems that came up in the planning the German National Research and Education Networks G-WiN and X-WiN and for several benchmark instances. N2 - Die Arbeit befasst sich mit der Kapazitäts- und Routenplanung für Kommunikationsnetze, die ein kürzeste-Wege Routingprotokoll verwenden. Diese Art von Protokollen ist im Internet weit verbreitet. Bei diesen Routingverfahren wird für jede Verbindung im Netz ein Längenwert festgelegt, diese Längen formen die sogenannte Routingmetrik. Die Routingwege der Kommunikationsbedarfe sind dann die jeweiligen kürzesten Wege bezüglich dieser Metrik. Bei der in der Arbeit untersuchten Variante dieser Routingprotokolle wird zusätzlich verlangt, dass es je Kommunikationsbedarf genau einen eindeutigen kürzesten Weg gibt. Die Schwierigkeit bei der Planung solcher Netze besteht darin, dass sich die Routingwege einerseits nur indirekt über die Routingmetrik beeinflussen lassen, andererseits aber alle Routingwege von der gleichen Metrik abhängen. Dadurch können die Wege verschiedener Kommunikationsanforderungen nicht wie bei anderen Routingverfahren unabhängig voneinander gewählt werden. Im erstem Teil der Arbeit werden der Zusammenhang zwischen gegebenen Wegesystemen und kompatiblen Routingmetriken sowie die Beziehungen der Wege eines zulässigen eindeutige-kürzeste-Wege-Routings untereinander untersucht. Dabei wird unter Anderem gezeigt, dass es NP-schwer ist, eine kompatible Metrik mit kleinstmöglichen Routinglängen zu einem gegebenen Wegesystem zu finden. Es wird auch bewiesen, dass das Finden eines kleinstmöglichen Konfliktes in einem gegebenen Wegesystem, zu dem keine kompatible Metrik existiert, NP-schwer ist. Im zweiten Teil der Arbeit wird die Approximierbarkeit von drei grundlegenden Netz- und Routenplanungsproblemen mit eindeutige-kürzeste-Wege-Routing untersucht. Für diese Probleme werden stärkere Nichtapproximierbarkeitsresultate als für die entsprechenden Einwege-Routing Probleme bewiesen und es werden verschiedene polynomiale Approximationsverfahren für allgemeine und Spezialfälle entworfen. Ausserdem wird die Beziehung zwischen eindeutige-kürzeste-Wege-Routing und anderen Routingverfahren diskutiert. Im dritten und letzten Teil der Arbeit wird ein (gemischt-) ganzzahliger Lösungsansatz für Planungsprobleme mit eindeutige-kürzeste-Wege-Routing vorgestellt. Für die im zweiten Teil diskutierten grundlegenden Netz- und Routenplanungsprobleme werden verschiedene (gemischt-) ganzzahlige lineare Modelle vorgestellt und es wird deren Lösbarkeit und die Stärke ihrer LP Relaxierungen untersucht. Es wird auch gezeigt, wie sich starke gültig Ungleichungen aus den in diesen Modellen enthalten Substrukturen ableiten lassen. Schlielich werden am Ende der Arbeit die Software-Implementierung dieses Lösungsverfahrens für eine praxisrelevante Verallgemeinerung der Planungsprobleme sowie die damit erzielten numerischen Ergebnisse vorgestellt und diskutiert. KW - kombinatorische Optimierung KW - gemischt-ganzzahlige Programmierung KW - kürzeste-Wege Routing KW - Approximationsalgorithmen KW - combinatorial optimization KW - mixed-integer programming KW - shortest path routing KW - approximation algorithms Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-15530 SN - 978-3-86727-281-0 ER - TY - GEN A1 - Bley, Andreas T1 - Routing and Capacity Optimization for IP networks N2 - This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years. T3 - ZIB-Report - 07-33 KW - kombinatorische Optimierung KW - gemischt-ganzzahlige Programmierung KW - kürzeste-Wege Routing KW - Approximationsalgorithmen KW - combinatorial optimization KW - mixed-integer programming KW - shortest path routing KW - approximation algorithms Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10323 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Metric Inequalities for Routings on Direct Connections with Application in Line Planning N2 - We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers. T3 - ZIB-Report - 15-07 KW - combinatorial optimization KW - integer programming KW - line planning KW - transfers KW - direct connection KW - metric inequalities Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53507 SN - 1438-0064 ER -