Single-layer Cuts for Multi-layer Network Design Problems

Arie M.C.A. Koster(arie.kosterwbs.ac.uk)
Sebastian Orlowski(orlowskizib.de)
Christian Raack(raackzib.de)
Thomas Engel(thomas.1.engelnsn.com)
Georg Baier(georg.baiernsn.com)

Abstract: We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context, helping to increase the dual bound and to reduce the optimality gaps.

Keywords: telecommunication networks, multi-layer network design, mixed-integer programming, cutting planes

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: ZIB report ZR-07-21, Zuse-Institute Berlin, Germany, August 2007

Download: [Compressed Postscript][PDF]

Entry Submitted: 08/14/2007
Entry Accepted: 08/15/2007
Entry Last Modified: 08/14/2007

Modify/Update this entry