A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints

References

• Adámek J, Koubek V (1971) Remarks on flows in network with short paths. Commentationes Mathematicae Universitatis Carolinae 12(4):661–667.Google Scholar
• Arslan O, Karaşan OE, Majhoub AR, Yaman H (2019) A branch-and-cut approach for the alternative fuel refueling station location problem with routing. Transportation Sci., ePub ahead of print June 13, https://doi.org/10.1287/trsc.2018.0869.Link, Google Scholar
• Baier G, Erlebach T, Hall A, Köhler E, Schilling H, Skutella M (2006) Length-bounded cuts and flows. Bugliesi M, Preneel B, Sassone V, Wegener I, eds. Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 4051 (Springer, Berlin Heidelberg), 679–690.Crossref, Google Scholar
• Balakrishnan A, Altinkemer K (1992) Using a hop-constrained model to generate alternative communication network design. ORSA J. Comput. 4(2):192–205.Link, Google Scholar
• Bendali F, Diarrassouba I, Mahjoub AR, Didi Biha M, Mailfert J (2010) A branch-and-cut algorithm for the k-edge connected subgraph problem. Networks 55(1):13–32.Crossref, Google Scholar
• Botton Q, Fortz B, Gouveia L, Poss M (2013) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25(1):13–26.Link, Google Scholar
• Dahl G, Gouveia L, Requejo C (2006) On formulations and methods for the hop-constrained minimum spanning tree problem. Resende MGC, Pardalos PM, eds. Handbook of Optimization in Telecommunications (Springer US, Boston), 493–515.Crossref, Google Scholar
• Ford LR, Fulkerson DR (1956) Maximal flow through a network. Canadian J. Math. 8(3):399–404.Crossref, Google Scholar
• Fortz B, Labbé M (2002) Polyhedral results for two-connected networks with bounded rings. Math. Programming 93(1):27–54.Crossref, Google Scholar
• Fortz B, Labbé M, Maffioli F (2000) Solving the two-connected network with bounded meshes problem. Oper. Res. 48(6):866–877.Link, Google Scholar
• Fortz B, Mahjoub AR, McCormick ST, Pesneau P (2006) Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut. Math. Programming 105(1):85–111.Crossref, Google Scholar
• Golovach PA, Thilikos DM (2011) Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optim. 8(1):72–86.Crossref, Google Scholar
• Gouveia L (1996) Multicommodity flow models for spanning trees with hop constraints. Eur. J. Oper. Res. 95(1):178–190.Crossref, Google Scholar
• Gouveia L (1998) Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2):180–188.Link, Google Scholar
• Gouveia L, Leitner M (2017a) Design of survivable networks with vulnerability constraints. Eur. J. Oper. Res. 258(1):89–103.Crossref, Google Scholar
• Gouveia L, Leitner M (2017b) Online data repository. Accessed October 12, 2017, http://homepage.univie.ac.at/markus.leitner/research/instances/NDPVC-instances.tar.gz.Google Scholar
• Gouveia L, Joyce-Moniz M, Leitner M (2018) Branch-and-cut methods for the network design problem with vulnerability constraints. Comput. Oper. Res. 91:190–208.Crossref, Google Scholar
• Grötschel M, Monma CL, Stoer M (1995) Design of survivable networks. Ball M, Magnanti T, Monma C, Nemhauser G, eds. Network Models, Handbooks in Operations Research and Management Science, vol. 7 (Elsevier, Amsterdam), 617–672.Crossref, Google Scholar
• Kerivin H, Mahjoub AR (2005) Design of survivable networks: A survey. Networks 46(1):1–21.Crossref, Google Scholar
• Koch T, Martin A (1998) Solving steiner tree problems in graphs to optimality. Networks 32(3):207–232.Crossref, Google Scholar
• Lovász L, Neumann-Lara V, Plummer M (1978) Mengerian theorems for paths of bounded length. Periodica Mathematica Hungarica 9(4):269–276.Google Scholar
• Mahjoub AR, McCormick ST (2010) Max flow and min cut with bounded-length paths: Complexity, algorithms, and approximation. Math. Programming 124(1–2):271–284.Crossref, Google Scholar
• Menger K (1927) Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10(1):96–115.Crossref, Google Scholar
• Savelsbergh MWP (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4):445–454.Link, Google Scholar
• Sherali HD, Driscoll PJ (2000) Evolution and state-of-the-art in integer programming. J. Comput. Appl. Math. 124(1):319–340.Crossref, Google Scholar
• Stoer M (1992) Design of Survivable Networks, Lecture Notes in Mathematics, vol. 1531 (Springer, Berlin Heidelberg).Crossref, Google Scholar