Preprint 019-2013

Lagrangian Decompositions for the Two-Level FTTx Network Design Problem

Author(s) : Andreas Bley , Ivana Ljubic , Olaf Maurer

Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 019-2013

MSC 2000

90C90 Applications of mathematical programming

90B18 Communication networks

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.

Keywords : network design, integer programming, Lagrangian decomposition