Christian Raack

Robust Network Design: Formulations, Valid Inequalities, and Computations

  • Arie M.C.A. Koster
  • Manuel Kutschka
  • Christian Raack
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , , ,

    Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim (2004). We present three different mathematical formulations for this problem, provide valid inequalities, … Read more

    Affine recourse for the robust network design problem: between static and dynamic routing

  • Michael Poss
  • Christian Raack
    • Categories Combinatorial Optimization, Network Optimization, Robust Optimization Tags , , , , ,

    Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework … Read more

    A note on the MIR closure and basic relaxations of polyhedra

  • Sanjeeb Dash
  • Oktay Gunluk
  • Christian Raack
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    Anderson, Cornuejols and Li (2005) show that for a polyhedral mixed integer set defined by a constraint system Ax >= b, where x is n-dimensional, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a “basic relaxation”, i.e., one defined by a subset of linearly … Read more

    The Mcf-Separator – Detecting and Exploiting Multi-Commodity Flow Structures in MIPs

  • Tobias Achterberg
  • Christian Raack
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Network Optimization Tags , , , , ,

    Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip … Read more

    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 , , ,

    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 … Read more

    On the strength of cut-based inequalities for capacitated network design polyhedra

  • Arie M.C.A. Koster
  • Christian Raack
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Polyhedra Tags , , ,

    In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show … Read more

    Capacitated network design using general flow-cutset inequalities

  • Arie M.C.A. Koster
  • Sebastian Orlowski
  • Christian Raack
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Telecommunications Tags , , ,

    This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), … Read more