Virtual private network design over the first Chvátal closure

Moradi, Ahmad; Lodi, Andrea; Mehdi Hashemi, S.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 569-588.

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.

Classification : 90C10, 90C11, 90C57
Mots clés : Binary formulation, Chvátal-Gomory closure, cutting planes, computational analysis, VPN design problem

A. Alın, E. Amaldi, P. Belotti and M.C. Pınar, Provisioning virtual private networks under traffic uncertainty. Networks 49 (2007) 100–115. | DOI | MR | Zbl

G. Andreello, A. Caprara and M. Fischetti, 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

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

P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti and A. Lodi, Projected Chvátal-Gomory cuts for mixed integer linear programs. Math. Program. 113 (2008) 241–257. | DOI | MR | Zbl

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

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

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

S. Dash, O. Günlük and A. Lodi, MIR closures of polyhedral sets. Math. Program. 121 (2010) 33–60. | DOI | MR | Zbl

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

F. Eisenbrand, F. Grandoni, G. Oriolo and M. Skutella, New approaches for virtual private network design. SIAM J. Comput. 37 (2007) 706–721. | DOI | MR | Zbl

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

S. Fiorini, $\{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

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

R.E. Gomory, 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

F. Grandoni, T. Rothvoß and L. Sanitá, From uncertainty to nonlinearity: Solving virtual private network via single-sink buy-at-bulk. Math. Oper. Res. 36 (2011) 185–204. | DOI | MR | Zbl

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

A.M.C.A. Koster and A. Zymolka, Stable multi-sets. Math. Meth. Oper. Res. 56 (2002) 45–65. | DOI | MR | Zbl

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

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

A. Moradi, A. Lodi and S.M. Hashemi, On the difficulty of virtual private network instances. Networks 63 (2014) 327–333. | DOI | MR | Zbl

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

M. Padberg, 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