On the difficulty of virtual private network instances

On the difficulty of virtual private network instances

0.00 Avg rating0 Votes
Article ID: iaor201522246
Volume: 63
Issue: 4
Start Page Number: 327
End Page Number: 333
Publication Date: Jul 2014
Journal: Networks
Authors: , ,
Keywords: combinatorial optimization, internet
Abstract:

The virtual private network design problem has attracted an impressive number of theoretical contributions but, surprisingly, very little computational attempts. This might be due to the fact that the compact formulation proposed in [Altın et al. Networks 49 (2007), 100–115] turned out to be very tight, that is, showing very little or no integrality gap in the computational experiments. In this short note, we first confirm the observations in [Altın et al. Networks 49 (2007), 100–115] by analyzing in detail the behavior of the compact formulation on a larger but similar testbed, and then we provide a set of difficult instances exposing large integrality gaps. This new insight is likely to reinvigorate efforts to develop effective exact computational approaches.

Reviews

Required fields are marked *. Your email address will not be published.