For the first time in the literature, this paper considers computational aspects of concave cost virtual private network design problems. It introduces careful bound tightening mechanisms and computationally demonstrates how such bound tightening could impressively improve convex relaxations of the problem. It turns out that, incorporating such bound tightening with a general solution approach could significantly enhance the behavior of the solution approach over the problem.
