A polyhedral approach to reroute sequence planning in MPLS networks

Published: 2006/08/24

Applications - OR and Management Sciences, Branch and Cut Algorithms, Telecommunications branch-and-cut, mpls networks, polyhedral combinatorics, scheduling Short URL: https://optimization-online.org/?p=9070

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.

A polyhedral approach to reroute sequence planning in MPLS networks

Citation

Article