کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903411 | 1632567 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The asymmetric VPN tree problem: polyhedral results and Branch-and-Cut
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 64, February 2018, Pages 315-324
Journal: Electronic Notes in Discrete Mathematics - Volume 64, February 2018, Pages 315-324
نویسندگان
Ibrahima Diarrassouba, Pedro Henrique P.V. Liguori, A. Ridha Mahjoub,