Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903411 | Electronic Notes in Discrete Mathematics | 2018 | 10 Pages |
Abstract
In this paper we consider a variant of the virtual private network design problem (VPNDP). Given an uncapacitated physical network, represented by a graph G=(VâªP,E), where V is the set of VPN routers and P is the set of clients for which it is given thresholds on the amount of traffic that each client can send (bp+) or receive (bpâ), the VPNDP asks for (1) a connected sub-network Gâ²=(Vâ²âªP,Eâ²), (2) a client assignments (p, v), pâP and vâVâ², and (3) a bandwidth allocation ue,eâEâ² in order to accommodate any traffic demand matrix that respects client thresholds. When Gâ² is acyclic, we have a VPN tree (VPNT). Also, when client thresholds are asymmetric, i.e., âpâPbp+â âbâPbpâ, the problem has been shown to be NP-hard. In this paper, we give MILP formulations for the asymmetric VPN tree problem. Also, we discuss the polytope associated with one of these formulations and describe several classes of valid inequalities. Moreover, we present necessary and sufficient conditions under which these inequalities define facets. We also devise separation routines. Using these routines, we propose a Branch-and-Cut algorithm and present a computational study.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ibrahima Diarrassouba, Pedro Henrique P.V. Liguori, A. Ridha Mahjoub,