Virtual private network design over the first Chvátal closure

In this paper we consider the virtual private network (VPN) design problem. Given upper bounds on the amount of traf- fic 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 ca- pacities and the total reservation cost is minimized. In [A. Moradi, A. Lodi and S.M. Hashemi. Networks 63 (2014) 327–333.] it is argued that the computational investigation on exact mathematical program- ming 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 Chva ́tal closure and demonstrate that tight so- lutions could be found for the VPN design problem only by optimizing over the closure. First, we perform theoretical investigation on adding rank-1 Chva ́tal–Gomory cuts to the problem. Along the way, an im- portant 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 Chva ́tal closure for the VPN design problem. Here, the binary re- duction 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 ́atal closure of the VPN design problem in rais- ing dual bound is due to zero-half cuts. Our experiments on the bench- mark instances in [A. Moradi, A. Lodi and S.M. Hashemi. Networks 63 (2014) 327–333.] show that a state-of-the-art IP solver without using zero-half cuts could not even hit the challenging benchmarks. As a re- sults 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.