Lagrangian Decompositions for the Two-Level FTTx Network Design Problem

Please always quote using this URN: urn:nbn:de:0296-matheon-12419
  • 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.

Download full text files

Additional Services

Share in Twitter Search Google Scholar
Author:Bley Andreas, Ivana Ljubic, Olaf Maurer
Referee:Martin Skutella
Date of first Publication:2013/07/26
Institute:Technische Universit├Ąt Berlin
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Preprint Number:1025