On the difficulty of virtual private network instances. Issue 4 (7th March 2014)

• Record Type: Journal Article
• Authors: Moradi, Ahmad; Lodi, Andrea; Hashemi, S. Mehdi
• Is Part Of: Networks. Volume 63:Issue 4(2014:Jul.)
• Page Start: 327
• Page End: 333
• Publication Date: 2014-03-07
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21548
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 327–333 2014</p> </abstract>