In this paper we consider the virtual private network (VPN) design problem. Given upper bounds on the amount of traffic that an endpoint could send or receive, the problem needs to reserve enough capacities in such a way that any demand matrix that respects the upper bound could be routed without exceeding the reserved capacities and the total reservation cost is minimized. In On the difficulty of virtual private network instances (Networks 63 (2014) 327–333), we argued that the computational investigation on exact mathematical programming approaches for VPN needs to be revised after that challenging instances have been exposed. To that end, we consider the VPN design problem over the first Chvátal closure and demonstrate that tight solutions could be found for the VPN design problem only by optimizing over the closure. First, we perform theoretical investigation on adding rank-1 Chvátal–Gomory cuts to the problem. Along the way, an important property for such cuts is proved that omits a large number of redundant rank-1 cuts. We then provide interesting insights about the problem and reduce the existing MIP formulations to a binary one. On the computational side, we investigate the idea of adding rank-1 cuts more aggressively in order to computationally evaluate tightness of the first Chvátal closure for the VPN design problem. Here, the binary reduction plays an important role allowing the use of special cuts of the first closure, namely the zero-half cuts. We show that, almost all the success of the first Chvátal closure of the VPN design problem in raising dual bound is due to zero-half cuts. Our experiments on the benchmark instances in this article show that a state-of-the-art IP solver without using zero-half cuts could not even hit the challenging benchmarks. As a results a cut-and-branch framework that aggressively adds such cuts at the root could solve the challenging VPN instances to the extent of zero or small integrality gap in a reasonable amount of time.

Accepted:

DOI: 10.1051/ro/2014056

Keywords: Binary formulation, Chvátal-Gomory closure, cutting planes, computational analysis, VPN design problem

^{1}; Lodi, Andrea

^{2}; Mehdi Hashemi, S.

^{1}

@article{RO_2015__49_3_569_0, author = {Moradi, Ahmad and Lodi, Andrea and Mehdi Hashemi, S.}, title = {Virtual private network design over the first {Chv\'atal} closure}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {569--588}, publisher = {EDP-Sciences}, volume = {49}, number = {3}, year = {2015}, doi = {10.1051/ro/2014056}, mrnumber = {3349135}, zbl = {1326.90050}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2014056/} }

TY - JOUR AU - Moradi, Ahmad AU - Lodi, Andrea AU - Mehdi Hashemi, S. TI - Virtual private network design over the first Chvátal closure JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2015 SP - 569 EP - 588 VL - 49 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2014056/ DO - 10.1051/ro/2014056 LA - en ID - RO_2015__49_3_569_0 ER -

%0 Journal Article %A Moradi, Ahmad %A Lodi, Andrea %A Mehdi Hashemi, S. %T Virtual private network design over the first Chvátal closure %J RAIRO - Operations Research - Recherche Opérationnelle %D 2015 %P 569-588 %V 49 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2014056/ %R 10.1051/ro/2014056 %G en %F RO_2015__49_3_569_0

Moradi, Ahmad; Lodi, Andrea; Mehdi Hashemi, S. Virtual private network design over the first Chvátal closure. RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 3, pp. 569-588. doi : 10.1051/ro/2014056. http://archive.numdam.org/articles/10.1051/ro/2014056/

Provisioning virtual private networks under traffic uncertainty. Networks 49 (2007) 100–115. | DOI | MR | Zbl

, , and ,Embedding cuts in a branch and cut framework: a computational study with $\{0,\frac{1}{2}\}$-cuts. INFORMS J. Comput. 19 (2007) 229–238. | DOI | MR | Zbl

, and ,Optimizing over the split closure. Math. Program. 113 (2008) 219–240. | DOI | MR | Zbl

and ,Projected Chvátal-Gomory cuts for mixed integer linear programs. Math. Program. 113 (2008) 241–257. | DOI | MR | Zbl

, , , and ,$\{0,\frac{1}{2}\}$-Chvátal–Gomory cuts. Math. Program. 74 (1996) 221–235. | DOI | MR | Zbl

and ,Edmonds polytopes and a hierarchy of combinatorial problems. Disc. Math. 4 (1973) 305–337. | DOI | MR | Zbl

,A heuristic to generate rank-1 GMI cuts. Math. Program. Comput. 2 (2010) 231–257. | DOI | MR | Zbl

and ,MIR closures of polyhedral sets. Math. Program. 121 (2010) 33–60. | DOI | MR | Zbl

, and ,N. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. Ramakrishnan and J.E. van der Merive, A flexible model for resource management in Virtual Private Networks, in Proc. of ACM Special Interest Group on Data Communication (SIGCOMM), Cambridge, MA (1999) 95–108.

J. Edmonds and E.L. Johnson, Matching: a well-solved class of integer linear programs. In Combinatorial Structures and Their Applications, edited by R.K. Guy, H. Hanani, N. Sauer. Gordon and Breach, New York (1970) 80–92. | MR | Zbl

New approaches for virtual private network design. SIAM J. Comput. 37 (2007) 706–721. | DOI | MR | Zbl

, , and ,P. Ferguson and G. Huston, What Is a VPN? – Part I. The Internet Protocol J. 1 (1998).

$\{0,\frac{1}{2}\}$-cuts and the linear ordering problem: Surfaces that define facets. SIAM J. Disc. Math. 20 (2006) 893–912. | DOI | MR | Zbl

,Optimizing over the first Chvátal closure. Math. Program. 110 (2007) 3–20. | DOI | MR | Zbl

and ,Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64 (1958) 275–278. | DOI | MR | Zbl

,R.E. Gomory, An algorithm for integer solutions to linear programs. In Recent Advances in Mathematical Programming, edited by R.L. Graves, P. Wolfe. McGraw-Hill, New York (1963) 269–302. | MR | Zbl

From uncertainty to nonlinearity: Solving virtual private network via single-sink buy-at-bulk. Math. Oper. Res. 36 (2011) 185–204. | DOI | MR | Zbl

, and ,A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi and B. Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, in Proc. of the 33rd Annual ACM Symposium on Theory of Computing (STOC) (2001) 389–398. | MR | Zbl

B. Korte and J. Vygen, Combinatorial optimization: Theory and algorithms, 4th ed. Springer Publishing Company, Incorporated (2007). | MR | Zbl

Stable multi-sets. Math. Meth. Oper. Res. 56 (2002) 45–65. | DOI | MR | Zbl

and ,On cycles and the stable multi-set polytope. Discret. Optim. 2 (2005) 241–255. | DOI | MR | Zbl

and ,A.G. Mason, Cisco secure virtual private network. Cisco Press 7 (2002).

On the difficulty of virtual private network instances. Networks 63 (2014) 327–333. | DOI | MR | Zbl

, and ,N.K. Olver, Robust Network Design. Ph.D. thesis, McGill University (2010). | MR

On the facial structure of set packing polyhedra. Math. Program. 5 (1973) 199–215. | DOI | MR | Zbl

,M. Pioro and D. Medhi, Routing, flow and capacity design in communication and computer networks. San Francisco, CA, Morgan Kaufmann (2004). | Zbl

*Cited by Sources: *