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.
Citation
Technical Report n° PE/BSC/INF/20291 V01/EN, Nortel GSM Access R&D, 2006.