Optimization Online


Single-layer Cuts for Multi-layer Network Design Problems

Arie M.C.A. Koster(arie.koster***at***wbs.ac.uk)
Sebastian Orlowski(orlowski***at***zib.de)
Christian Raack(raack***at***zib.de)
Thomas Engel(thomas.1.engel***at***nsn.com)
Georg Baier(georg.baier***at***nsn.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society