Bounding the Number of Light Paths for Robust LSP Routing

Summary form only given. We consider a routing problem where we want to minimize the maximal relative congestion on the arcs of the network with a bounded number of paths. This problem is relevant in the context of MPLS core networks where one looks for a compromise between higher QoS and fewer splitting of the point-to-point connections. We consider modelling that problem by mixed-integer non linear programs and analyze different solution approaches, focusing on Approximation algorithms based on the flow deviation algorithm on the one hand, and on exact procedures based on the branch-and-price method on the other hand