Hose Workload based Exact Algorithm for the Optimal Design of Virtual Private Networks
Diarrassouba, Ibrahima; Youssef, Habib; Mahjoub, Ali Ridha; Lourimi, Ali (2013), Hose Workload based Exact Algorithm for the Optimal Design of Virtual Private Networks, Computer Networks, 57, 14, p. 2766-2774. 10.1016/j.comnet.2013.06.009
TypeArticle accepté pour publication ou publié
Journal nameComputer Networks
MetadataShow full item record
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)The 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. . 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.
Subjects / KeywordsPolynomial algorithm; Separation problem; Cutting plane; Maximum flow problem; Branch-and-cut; Hose model; Virtual private network
Showing items related by title and author.
Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem Diarrassouba, Ibrahima; Gabrel, Virginie; Mahjoub, Ali Ridha; Gouveia, Luis; Pesneau, Pierre (2016) Article accepté pour publication ou publié
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié