@misc{Bley, author = {Bley, Andreas}, title = {A Lagrangian Approach for Integrated Network Design and Routing in IP Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7515}, number = {03-29}, abstract = {We consider the problem of designing a network that employs a non-bifurcated shortest path routing protocol. The network's nodes and the set of potential links are given together with a set of forecasted end-to-end traffic demands. All relevant hardware components installable at links or nodes are considered. The goal is to simultaneously choose the network's topology, to decide which hardware components to install on which links and nodes, and to find appropriate routing weights such that the overall network cost is minimized. In this paper, we present a mathematical optimization model for this problem and an algorithmic solution approach based on a Lagrangian relaxation. Computational results achieved with this approach for several real-world network planning problems are reported.}, language = {en} } @misc{BleyKosterKroelleretal., author = {Bley, Andreas and Koster, Arie M.C.A. and Kr{\"o}ller, Alexander and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {Kosten- und Qualit{\"a}tsoptimierung in Kommunikationsnetzen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7537}, number = {03-31}, abstract = {Der scharfe Wettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu, ihre Investitionen genau zu planen und immer wieder Einsparungsmanahmen durchzuf{\"u}hren. Gleichzeitig ist es jedoch wichtig, die Qualit{\"a}t der angebotenen Dienste zu verbessern, um neue Kunden zu gewinnen und langfristig an sich zu binden. Die mathematische Optimierung bietet sich f{\"u}r viele solcher Aufgabenstellungen als hervorragend geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung speziell zur Kosten- und Qualit{\"a}tsoptimierung in Kommunikationsnetzen vorzustellen. Anhand von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie sich komplexe Zusammenh{\"a}nge in flexiblen mathematischen Modellen abbilden lassen und welche Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden k{\"o}nnen. Die hier vorgestellten Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen L{\"o}sungen auch eine Qualittsgarantie liefern, mit der sich die Lsungen fundiert bewerten lassen. Die dokumentierten Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und G{\"u}te der mathematischen Optimierung f{\"u}r die Praxis.}, language = {de} } @misc{BleyZymolka, author = {Bley, Andreas and Zymolka, Adrian}, title = {Planung kostenoptimaler Informations- und Kommunikations-Infrastrukturen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7591}, number = {03-37}, abstract = {Beim Entwurf und Ausbau von Informations- und Kommunikationsnetzwerken m{{\"u}}ssen zahlreiche interdependente Entscheidungen getroffen und gleichzeitig mannigfaltige Bedingungen ber{{\"u}}cksichtigt werden. Die verf{{\"u}}gbaren technischen und organisatorischen Alternativm{{\"o}}glichkeiten sind normalerweise so vielf{{\"a}}ltig und komplex, dass eine manuelle Planung praktisch nicht m{{\"o}}glich ist. In diesem Artikel wird das Potential und die Methodik der mathematischen Optimierung bei der kostenoptimalen Planung von Kommunikationsnetzen vorgestellt. Als Ausgangspunkt wird exemplarisch eine typische praktische Aufgabe, die Struktur- und Konfigurationsplanung mehrstufiger Telekommunikationsnetzwerke, dargestellt. Anschließend werden kurz die wesentlichen Modellierungstechniken und Verfahrensans{{\"a}}tze der mathematischen Optimierung skizziert. Abschließend gehen wir auf die Planung einer ad{{\"a}}quaten Informations- und Kommunikations- Infrastruktur f{{\"u}}r ein dezentrales Energieversorgungsnetz ein.}, language = {de} } @misc{BleyKoch, author = {Bley, Andreas and Koch, Thorsten}, title = {Integer programming approaches to access and backbone IP-network planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7081}, number = {02-41}, abstract = {In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the next layer in a tree-like fashion. The backbone layer has to satisfy certain survivability and routing constraints. Given the node locations, the demands between them, the possible connections and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network level, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone. Mixed integer linear programming models and solution methods are presented for both the access and the backbone network design problem. The focus is on the design of IP-over-SDH networks, but the access network design model and large parts of the backbone network design models are general and also applicable for other types of communication networks. Results obtained with these methods in the planning of the German research network are presented.}, language = {en} } @misc{BleyKoch, author = {Bley, Andreas and Koch, Thorsten}, title = {Optimierung in der Planung und beim Aufbau des G-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6169}, number = {00-48}, abstract = {Ende Juni diesen Jahres wurde das Gigabit-Wissenschaftsnetz offiziell gestartet. In der zweij{\"a}hrigen Vorbereitungsphase wurden nicht nur die technischen M{\"o}glichkeiten der neuen {\"U}bertragungstechniken und Dienste getestet. Es wurden auch verschiedene Fragestellungen zum effizienten Einsatz der verf{\"u}gbaren Ressourcen f{\"u}r den Betrieb des G-WiN untersucht. In diesem Artikel beschreiben wir, wie das G-WiN zu seiner jetzigen Struktur und Topologie gekommen ist.}, language = {de} } @misc{BienstockBley, author = {Bienstock, Daniel and Bley, Andreas}, title = {Capacitated Network Design with Multicast Commodities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5823}, number = {00-14}, abstract = {This paper addresses the problem of designing a minimum cost network whose capacities are sufficiently large to allow a feasible routing of a given set of multicast commodities. A multicast commodity consists of a set of two or mo re terminals that need to be connected by a so called broadcast tree, which consumes on all of its edges a capacity as large as the demand value associated with that commodity. We model the network design problem with multicast commodities as the problem of packing capacitated Steiner trees in a graph. In the first part of the paper we present three mixed-integer programming formulations for this problem. The first natural formulation uses only one integer capacity variable for each edge and and one binary tree variable for each commodity-edge pair. Applying well-known techniques from the Steiner tree problem, we then develop a stronger directed and a multicommodity flow based mixed-integer programming formulation. In the second part of the paper we study the associated polyhedra and derive valid and even facet defining inequalities for the natural formulation. Finally, we describe separation algorithms for these inequalities and present computational results that demonstrate the strength of our extended formulations.}, language = {en} } @inproceedings{BleyGroetschelWessaely2000, author = {Bley, Andreas and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Design of broadband virtual private networks: Model and Heuristics for the B-WiN}, series = {Robust communication networks: Interconnection and survivability. DIMACS workshop, Princeton, NJ, USA, 1998 at Rutgers University}, volume = {53}, booktitle = {Robust communication networks: Interconnection and survivability. DIMACS workshop, Princeton, NJ, USA, 1998 at Rutgers University}, editor = {Dean, Nathaniel and Hsu, D. and Ravi, R.}, publisher = {American Mathematical Society}, address = {Providence, RI}, pages = {1 -- 16}, year = {2000}, language = {en} } @article{BleyKoch2000, author = {Bley, Andreas and Koch, Thorsten}, title = {Optimierung des G-WiN}, series = {DFN-Mitteilungen}, journal = {DFN-Mitteilungen}, number = {54}, pages = {13 -- 15}, year = {2000}, language = {en} } @misc{Bley, author = {Bley, Andreas}, title = {On the Complexity of Vertex-Disjoint Length-Restricted Path Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3639}, number = {SC-98-20}, abstract = {Let \$G=(V,E)\$ be a simple graph and \$s\$ and \$t\$ be two distinct vertices of \$G\$. A path in \$G\$ is called \$\ell\$-bounded for some \$\ell\in\mathbb{N}\$, if it does not contain more than \$\ell\$ edges. We study the computational complexity of approximating the optimum value for two optimization problems of finding sets of vertex-disjoint \$\ell\$-bounded \$s,t\$-paths in \$G\$. First, we show that computing the maximum number of vertex-disjoint \$\ell\$-bounded \$s,t\$-paths is \$\mathcal{AP\kern-1pt X}\$--complete for any fixed length bound \$\ell\geq 5\$. Second, for a given number \$k\in\mathbb{N}\$, \$1\leq k \leq |V|-1\$, and non-negative weights on the edges of \$G\$, the problem of finding \$k\$ vertex-disjoint \$\ell\$-bounded \$s,t\$-paths with minimal total weight is proven to be \$\mathcal{NPO}\$--complete for any length bound \$\ell\geq 5\$. Furthermore, we show that, even if \$G\$ is complete, it is \$\mathcal{NP}\$--complete to approximate the optimal solution value of this problem within a factor of \$2^{\langle\phi\rangle^\epsilon}\$ for any constant \$0<\epsilon<1\$, where \$\langle\phi\rangle\$ denotes the encoding size of the given problem instance \$\phi\$. We prove that these results are tight in the sense that for lengths \$\ell\leq 4\$ both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. All results presented also hold for directed and non-simple graphs. For the analogous problems where the path length restriction is replaced by the condition that all paths must have length equal to \$\ell\$ or where vertex-disjointness is replaced by edge-disjointness we obtain similar results.}, language = {en} } @misc{BleyGroetschelWessaely, author = {Bley, Andreas and Gr{\"o}tschel, Martin and Wess{\"a}ly, Roland}, title = {Design of Broadband Virtual Private Networks: Model and Heuristics for the B-WiN}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3565}, number = {SC-98-13}, abstract = {We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data.}, language = {en} }