We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the difficulty of virtual private network instances.
- Authors
Moradi, Ahmad; Lodi, Andrea; Hashemi, S. Mehdi
- 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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 327-333 2014
- Subjects
VIRTUAL private networks; COMPUTATIONAL complexity; ROUTING (Computer network management); MIXED integer linear programming; ROBUST control
- Publication
Networks, 2014, Vol 63, Issue 4, p327
- ISSN
0028-3045
- Publication type
Article
- DOI
10.1002/net.21548