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.
Entry Submitted: 08/24/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|