Volume 49, Number 3, July-September 2015
|569 - 588
|23 February 2015
Virtual private network design over the first Chvátal closure
1 Department of Mathematics and Computer Science, Amirkabir University of Technology, No. 424, Hafez Avenue, Tehran, Iran.
2 DEI, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy.
Received: 26 June 2014
Accepted: 5 November 2014
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.
Mathematics Subject Classification: 90C10 / 90C11 / 90C57
Key words: Binary formulation / Chvátal-Gomory closure / cutting planes / computational analysis / VPN design problem
© EDP Sciences, ROADEF, SMAI, 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.