Hose Workload based Exact Algorithm for the Optimal Design of Virtual Private Networks

International audienceThe Virtual Private Networks (VPN) optimal bandwidth allocation problem with tree toplogy has been widely discussed in the literature. Most of the algorithms proposed by researchers to solve this problem use approximation schemes. In this paper, we propose an exact and efficient Branch-and-Cut algorithm for the problem in the context of a hose workload model. In particular, we consider the case when the ingress and egress traffic at VPN endpoints are asymetric and the links of the network have unbounded capacities. The algorithm proposed here is based on a linear integer programming formulation for the problem introduced by Kumar et al. [2]. Using this and a deep investigation of the polyhedral structure of that formulation, our algorithm permits to solve large instances of the problem having up to 120 nodes and 10 terminals