The Robust Network Loading Problem Under Hose Demand Uncertainty: Formulation, Polyhedral Analysis, and Computations

References

• Altın A., Belotti P., Pınar M. Ç. OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty. Optim. Engrg. (2010) 11(3):395–422Crossref, Google Scholar
• Altın A., Amaldi E., Belotti P., Pınar M. Ç. Provisioning virtual private networks under traffic uncertainty. Networks (2007) 49(1):100–115Crossref, Google Scholar
• Atamtürk A. On capacitated network design cut-set polyhedra. Math. Programming B (2002) 92(3):425–437Crossref, Google Scholar
• Atamtürk A. Strong reformulations of robust mixed 0–1 programming. Math. Programming (2006) 108(2–3):235–250Crossref, Google Scholar
• Atamtürk A., Günlük O. Network design arc set with variable upper bounds. Networks (2007) 50(1):17–28Crossref, Google Scholar
• Atamtürk A., Rajan D. On splittable and unsplittable capacitated network design arc-set polyhedra. Math. Programming (2002) 92(2):315–333Crossref, Google Scholar
• Atamtürk A., Zhang M. Two-stage robust network flow and design under demand uncertainty. Oper. Res. (2007) 55(4):662–673Link, Google Scholar
• Avella P., Mattia S., Sassano A. Metric inequalities and the network loading problem. Discrete Optim. (2007) 4(1):103–114Crossref, Google Scholar
• Belotti P., Pınar M. Ç. Optimal oblivious routing under linear and ellipsoidal uncertainty. Optim. Engrg. (2008) 9(3):257–271Crossref, Google Scholar
• Ben-Ameur W., Kerivin H. Routing of uncertain traffic demands. Optim. Engrg. (2005) 6(3):283–313Crossref, Google Scholar
• Ben-Tal A., Nemirovski A. Robust convex optimization. Math. Oper. Res. (1998) 23(4):769–805Link, Google Scholar
• Ben-Tal A., Nemirovski A. Robust solutions of uncertain linear programs. Oper. Res. Lett. (1999) 25(1):1–13Crossref, Google Scholar
• Ben-Tal A., Nemirovski A. Selected topics in robust convex optimization. Math. Programming (2008) 112(1):125–158Crossref, Google Scholar
• Ben-Tal A., Goryashko A., Guslitzer E., Nemirovski A. Adjustable robust solutions of uncertain linear programs. Math. Programming (2004) 99(2):351–376Crossref, Google Scholar
• Berger D., Gendron B., Potvin J.-Y., Raghavan S., Soriano P. Tabu search for a network loading problem with multiple facilities. J. Heuristics (2000) 6(2):253–267Crossref, Google Scholar
• Bertsimas D., Sim M. Robust discrete optimization and network flows. Math. Programming (2003) 98(1–3):49–71Crossref, Google Scholar
• Bertsimas D., Sim M. The price of robustness. Oper. Res. (2004) 52(1):35–53Link, Google Scholar
• Bienstock D., Günlük O. Capacitated network design—Polyhedral structure and computation. INFORMS J. Comput. (1996) 8(3):243–259Link, Google Scholar
• Bienstock D., Chopra S., Günlük O., Tsai C.-Y. Minimum cost capacity installation for multicommodity network flows. Math. Programming (1998) 81(2):177–199Crossref, Google Scholar
• Brockmüller B., Günlük O., Wolsey L. A. Designing private line networks—Polyhedral analysis and computation. Trans. Oper. Res. (2004) 16(1, 2):7–24Google Scholar
• Cornuéjols G. Valid inequalities for mixed integer linear programs. Math. Programming (2008) 112(1):3–44Crossref, Google Scholar
• Duffield N., Goyal P., Greenberg A., Mishra P., Ramakrishnan K. K., van der Merive J. E. A flexible model for resource management in virtual private networks. Proc. ACM SIGCOMM (1999) (ACM, New York) 95–108Crossref, Google Scholar
• Fingerhut J. A., Suri S., Turner J. S. Designing least-cost nonblocking broadband networks. J. Algorithms (1997) 24(2):287–309Crossref, Google Scholar
• Goyal N., Olver N., Shepherd F. B. The VPN conjecture is true. Proc. ACM STOC (2008) (ACM, New York) 443–450Crossref, Google Scholar
• Grandoni F., Kaibel V., Oriolo G., Skutella M. A short proof of the VPN tree routing conjecture on ring networks. Oper. Res. Lett. (2008) 36(3):361–365Crossref, Google Scholar
• Günlük O. A branch-and-cut algorithm for capacitated network design problems. Math. Programming (1999) 86(1):17–39Crossref, Google Scholar
• Gupta A., Kumar A., Roughgarden T. Simpler and better approximation algorithms for network design. Proc. ACM STOC (2003) (ACM, New York) 365–372Crossref, Google Scholar
• Gupta A., Kleinberg J., Kumar A., Rastogi R., Yener B. Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. ACM STOC (2001) Hersonissos, Greece(ACM, New York) 389–398Crossref, Google Scholar
• Hurkens C. A. J., Keijsper J. C. M., Stougie L. Virtual private network design: A proof of the tree routing conjecture on ring networks. SIDMA (2007) 21(2):482–503Crossref, Google Scholar
• Italiano G. F., Rastogi R., Yener B. Restoration algorithms for virtual private networks in the hose model. INFOCOM Proc 21st Annual Joint Conf. IEEE Comput. Comm. Soc. (2002) 1(IEEE, Washington, DC) 131–139Crossref, Google Scholar
• Karaşan O., Pınar M. Ç., Yaman H. Robust DWDM routing and provisioning under polyhedral demand uncertainty. (2005) . Technical report, Bilkent University, Bilkent, Ankara, TurkeyGoogle Scholar
• Kumar A., Rastogi R., Silberschatz A., Yener B. Algorithms for provisioning virtual private networks in the hose model. ACM SIGCOMM Comput. Comm. Rev. (2001) 31(4):135–146Crossref, Google Scholar
• Labbé M., Yaman H. Projecting the flow variables for hub location problems. Networks (2004) 44(2):84–93Crossref, Google Scholar
• Magnanti T. L., Mirchandani P. Shortest paths, single origin-destination network design, and associated polyhedra. Networks (1993) 23(2):103–121Crossref, Google Scholar
• Magnanti T. L., Mirchandani P., Vachani R. The convex hull of two core capacitated network design problems. Math. Programming (1993) 60(1–3):233–250Crossref, Google Scholar
• Magnanti T. L., Mirchandani P., Vachani R. Modeling and solving the two-facility capacitated network loading problem. Oper. Res. (1995) 43(1):142–157Link, Google Scholar
• Mirchandani P. Projections of the capacitated network loading problem. Eur. J. Oper. Res. (2000) 122(3):534–560Crossref, Google Scholar
• Mudchanatongsuk S., Ordoñez F., Liu J. Robust solutions for network design under transportation cost and demand uncertainty. J. Oper. Res. Soc. (2008) 59(5):652–662Crossref, Google Scholar
• Nemhauser G. L., Savelsbergh M. W. P., Sigismondi G. C. MINTO, a mixed INTeger optimizer. Oper. Res. Lett. (1994) 15(1):47–58Crossref, Google Scholar
• Onaga K., Kakusho O. On feasibility conditions of multicommodity flows in networks. IEEE Trans. Circuit Theory (1971) 18(4):425–429Crossref, Google Scholar
• Ordoñez F., Zhao J. Robust capacity expansion of network flows. Networks (2007) 50(2):136–145Crossref, Google Scholar
• Raack C., Koster A. M. C. A., Orlowski S., Wessäly R. On cut-based inequalities for capacitated network design polyhedra. Networks (2010) . ePub ahead of print June 30, http://onlinelibrary.wiley.com/doi/10.1002/net.20395/abstractCrossref, Google Scholar
• Rardin R. L., Wolsey L. A. Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems. Eur. J. Oper. Res. (1993) 71(1):95–109Crossref, Google Scholar
• Soyster A. L. Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. (1973) 21(5):1154–1157Link, Google Scholar
• Swamy C., Kumar A. Primal-dual algorithms for connected facility location problems. Proc. Internat. Workshop Approximation Algorithms Combinatorial Optim. (APPROX) (2002) 2462(Springer, Berlin) 256–270Lecture Notes in Computer Science SeriesCrossref, Google Scholar
• van Hoesel S. P. M., Koster A. M. C. A., van de Leensel R. L. M. J., Savelsbergh M. W. P. Polyhedral results for the edge capacity polytope. Math. Programming (2002) 92(2):335–358Crossref, Google Scholar
• Wolsey L. A.Integer Programming (1998) (Wiley-Interscience, New York) Google Scholar
• Yaman H. The integer knapsack cover polyhedron. SIAM J. Discrete Math. (2007) 21(3):551–572Crossref, Google Scholar
• Yaman H., Karaşan O. E., Pınar M. Ç. Restricted robust uniform matroid maximization under interval uncertainty. Math. Programming (2007) 110(2):431–441Crossref, Google Scholar
• Zuse-Institute Berlin SNDlib. . Accessed March 8, 2010, http://sndlib.zib.de/home.actionGoogle Scholar