Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Lagrangian Decompositions for the Two-Level FTTx Network Design Problem
Author(s): Bley, Andreas
Ljubić, Ivana
Maurer, Olaf
Type: Research Paper
Abstract: We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its CO. Passive optical splitters installed at the DPs allow k connections to share a single common fiber between the DP and the CO. We consider fixed charge costs for the use of an edge of the underlying street network, of a DP, and of a CO and variable costs for installing fibers along the street edges and for installing splitters at the DPs. We present two Lagrangian decomposition approaches that decompose the problem based on the network structure and on the cost structure, respectively. The subproblems are solved using MIP techniques. We report computational results for realistic instances and compare the efficiency of the Lagrangian approaches to the solutions of an integrated MIP model.
Subject(s): network design
integer programming
Lagrangian decomposition
Issue Date: 25-Jul-2013
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C90 Applications of mathematical programming
90B18 Communication networks
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2013, 19
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 668.13 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.