Single-layer Cuts for Multi-layer Network Design Problems

  • Georg Baier
  • Arie M.C.A. Koster
  • Sebastian Orlowski
  • Thomas Engel
  • Christian Raack
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Telecommunications Tags , , , Short URL: https://optimization-online.org/?p=10212

    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.

    Citation

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

    Article

    Download

    View Single-layer Cuts for Multi-layer Network Design Problems