A polyhedral approach to reroute sequence planning in MPLS networks

Renaud Sirdey (renaudsnortel.com)

Abstract: This paper is devoted to the study of the reroute sequence planning problem in multi-protocol label switching networks from the polyhedral viewpoint. The reroute sequence plan polytope, defined as the convex hull of the incidence vectors of the reroute sequences which do not violate the network link capacities, is introduced and some of its properties are investigated. Drawing heavily on previous theoretical work on a seemingly unrelated distributed system reconfiguration problem, pseudopolynomially separable classes of facet-defining inequalities are introduced. These results are then embedded in a branch-and-cut algorithm which practical relevance is empirically assessed.

Keywords: Polyhedral combinatorics, scheduling, branch-and-cut, MPLS networks.

Category 1: Applications -- OR and Management Sciences

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

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Technical Report n° PE/BSC/INF/20291 V01/EN, Nortel GSM Access R&D, 2006.

Download: [Postscript]

Entry Submitted: 08/24/2006
Entry Accepted: 08/24/2006
Entry Last Modified: 08/24/2006

Modify/Update this entry