An Exact Algorithm for Multicommodity Network Design Under Stochastic Interdictions

References

• Afshari Rad M, Kakhki HT (2017) Two extended formulations for cardinality maximum flow network interdiction problem. Networks 69(4):367–377.Crossref, Google Scholar
• Akgün İ, Tansel BÇ, Wood RK (2011) The multi-terminal maximum-flow network-interdiction problem. Eur. J. Oper. Res. 211(2):241–251.Crossref, Google Scholar
• Alderson DL, Brown GG, Carlyle WM, Wood RK (2011) Solving defender-attacker-defender models for infrastructure defense. Wood RK, Dell RF, eds. ICS 2011 12th INFORMS Comput. Soc. Conf. (INFORMS, Catonsville, MD), 28–49.Google Scholar
• Assimakopoulos N (1987) A network interdiction model for hospital infection control. Comput. Biology Medicine 17(6):413–422.Crossref, Google Scholar
• Azizi N, Chauhan S, Salhi S, Vidyarthi N (2016) The impact of hub failure in hub-and-spoke networks: Mathematical formulations and solution techniques. Comput. Oper. Res. 65(1):174–188.Crossref, Google Scholar
• Baggio A, Carvalho M, Lodi A, Tramontani A (2021) Multilevel approaches for the critical node problem. Oper. Res. 69(2):486–508.Link, Google Scholar
• Balakrishnan A, Li G, Mirchandani P (2017) Optimal network design with end-to-end service requirements. Oper. Res. 65(3):729–750.Link, Google Scholar
• Beck Y, Ljubić I, Schmidt M (2023) A survey on bilevel optimization under uncertainty. Eur. J. Oper. Res. 311(2):401–426.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Crossref, Google Scholar
• Blom D, Hojny C, Smeulders B (2024) Cutting plane approaches for the robust kidney exchange problem. Comput. Oper. Res. 162(2):106470.Crossref, Google Scholar
• Bodur M, Luedtke JR (2017) Mixed-integer rounding enhanced benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty. Management Sci. 63(7):2073–2091.Link, Google Scholar
• Bodur M, Dash S, Günlük O, Luedtke J (2017) Strengthened Benders cuts for stochastic integer programs with continuous recourse. INFORMS J. Comput. 29(1):77–91.Link, Google Scholar
• Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530–544.Link, Google Scholar
• Cappanera P, Scaparra MP (2011) Optimal allocation of protective resources in shortest-path networks. Transportation Sci. 45(1):64–80.Link, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2016) Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2):319–333.Link, Google Scholar
• Collado R, Meisel S, Priekule L (2017) Risk-averse stochastic path detection. Eur. J. Oper. Res. 260(1):195–211.Crossref, Google Scholar
• Contardo C, Sefair JA (2022) A progressive approximation approach for the exact solution of sparse large-scale binary interdiction games. INFORMS J. Comput. 34(2):890–908.Link, Google Scholar
• Contreras I, Cordeau JF, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, Google Scholar
• Costa AM (2005) A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32(6):1429–1450.Crossref, Google Scholar
• Costa AM, Cordeau JF, Gendron B (2009) Benders, metric and cutset inequalities for multicommodity capacitated network design. Comput. Optim. Appl. 42(3):371–392.Crossref, Google Scholar
• Costa AM, França PM, Lyra Filho C (2011) Two-level network design with intermediate facilities: An application to electrical distribution systems. Omega 39(1):3–13.Crossref, Google Scholar
• Crainic TG, Frangioni A, Gendron B (2001) Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112(1–3):73–99.Crossref, Google Scholar
• Crainic TG, Gendreau M, Gendron B, eds. (2021a) Network Design with Applications to Transportation and Logistics (Springer Nature, Cham, Switzerland).Crossref, Google Scholar
• Crainic TG, Hewitt M, Maggioni F, Rei W (2021b) Partial Benders decomposition: General methodology and application to stochastic network design. Transportation Sci. 55(2):414–435.Link, Google Scholar
• DeNegre ST, Ralphs TK (2009) A branch-and-cut algorithm for integer bilevel linear programs. Chinneck JW, Kristjansson B, Saltzman MJ, eds. Operations Research and Cyber-Infrastructure. Operations Research/Computer Science Interfaces, vol. 47 (Springer, Boston), 65–78.Crossref, Google Scholar
• Feremans C, Labbé M, Laporte G (2003) Generalized network design problems. Eur. J. Oper. Res. 148(1):1–13.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2019) Interdiction games and monotonicity, with application to knapsack problems. INFORMS J. Comput. 31(2):390–410.Link, Google Scholar
• Fragkos I, Cordeau JF, Jans R (2021) Decomposition methods for large-scale network expansion problems. Transportation Res. Part B Methodological 144(2):60–80.Crossref, Google Scholar
• Frangioni A (2024) Antonio Frangioni’s home page. University of Pisa, Pisa, Italy. http://www.di.unipi.it/∼frangio. (The instance can be downloaded from https://commalab.di.unipi.it/datasets/mmcf/#NetDesMMCF).Google Scholar
• Garg M, Smith JC (2008) Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios. Omega 36(6):1057–1071.Crossref, Google Scholar
• Ghare PM, Montgomery DC, Turner WC (1971) Optimal interdiction policy for a flow network. Naval Res. Logist. Quart. 18(1):37–45.Crossref, Google Scholar
• Gudapati NV, Malaguti E, Monaci M (2022) Network design with service requirements: Scaling-up the size of solvable problems. INFORMS J. Comput. 34(5):2571–2582.Link, Google Scholar
• Hemmati M, Smith JC (2016) A mixed-integer bilevel programming approach for a competitive prioritized set covering problem. Discrete Optim. 20(5):105–134.Crossref, Google Scholar
• Hien LTK, Sim M, Xu H (2020) Mitigating interdiction risk with fortification. Oper. Res. 68(2):348–362.Abstract, Google Scholar
• Holzmann T, Smith JC (2021) The shortest path interdiction problem with randomized interdiction strategies: Complexity and algorithms. Oper. Res. 69(1):82–99.Link, Google Scholar
• Hunt K, Zhuang J (2024) A review of attacker-defender games: Current state and paths forward. Eur. J. Oper. Res. 313(2):401–417.Crossref, Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Jabarzare Z, Zolfagharinia H, Najafi M (2020) Dynamic interdiction networks with applications in illicit supply chains. Omega 96(10):1–21.Crossref, Google Scholar
• Janjarassuk U, Linderoth J (2008) Reformulation and sampling to solve a stochastic network interdiction problem. Networks 52(3):120–132.Crossref, Google Scholar
• Jin JG, Lu L, Sun L, Yin J (2015) Optimal allocation of protective resources in urban rail transit networks against intentional attacks. Transportation Res. Part E Logist. Transportation Rev. 84(12):73–87.Crossref, Google Scholar
• Kerivin H, Mahjoub AR (2005) Design of survivable networks: A survey. Networks 46(1):1–21.Crossref, Google Scholar
• Kleinert T, Labbé M, Ljubić I, Schmidt M (2021) A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9:1–21.Crossref, Google Scholar
• Lanza G, Crainic TG, Rei W, Ricciardi N (2021) Scheduled service network design with quality targets and stochastic travel times. Eur. J. Oper. Res. 288(1):30–46.Crossref, Google Scholar
• Liberatore F, Scaparra M, Daskin M (2011) Analysis of facility protection strategies against an uncertain number of attacks: The stochastic R-interdiction median problem with fortification. Comput. Oper. Res. 38(1):357–366.Crossref, Google Scholar
• Lim C, Smith JC (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15–26.Crossref, Google Scholar
• Lozano L, Smith JC (2017) A backward sampling framework for interdiction problems with fortification. INFORMS J. Comput. 29(1):123–139.Link, Google Scholar
• Lozano L, Smith JC, Kurz ME (2017) Solving the traveling salesman problem with interdiction and fortification. Oper. Res. Lett. 45(3):210–216.Crossref, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• McMasters AW, Mustin TM (1970) Optimal interdiction of a supply network. Naval Res. Logist. Quart. 17(3):261–268.Crossref, Google Scholar
• Morton DP, Pan F, Saeger KJ (2007) Models for nuclear smuggling interdiction. IIE Trans. 39(1):3–14.Crossref, Google Scholar
• Nguyen DH, Smith JC (2022) Network interdiction with asymmetric cost uncertainty. Eur. J. Oper. Res. 297(1):239–251.Crossref, Google Scholar
• Papadakos N (2008) Practical enhancements to the Magnanti–Wong method. Oper. Res. Lett. 36(4):444–449.Crossref, Google Scholar
• Paraskevopoulos DC, Bektaş T, Crainic TG, Potts CN (2016) A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem. Eur. J. Oper. Res. 253(2):265–279.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2018) Accelerating the Benders decomposition method: Application to stochastic network design problems. SIAM J. Optim. 28(1):875–903.Crossref, Google Scholar
• Ramamoorthy P, Jayaswal S, Sinha A, Vidyarthi N (2018) Multiple allocation hub interdiction and protection problems: Model formulations and solution approaches. Eur. J. Oper. Res. 270(1):230–245.Crossref, Google Scholar
• Ramamoorthy P, Jayaswal S, Sinha A, Vidyarthi N (2024) An exact method for trilevel hub location problem with interdiction. Eur. J. Oper. Res. 319(3):696–710.Crossref, Google Scholar
• Ratliff HD, Sicilia GT, Lubore S (1975) Finding the n most vital links in flow networks. Management Sci. 21(5):531–539.Link, Google Scholar
• Salmeron J, Wood K, Baldick R (2004) Analysis of electric grid security under terrorist threat. IEEE Trans. Power Systems 19(2):905–912.Crossref, Google Scholar
• Salmeron J, Wood K, Baldick R (2009) Worst-case interdiction analysis of large-scale electric power grids. IEEE Trans. Power Systems 24(1):96–104.Crossref, Google Scholar
• Sarayloo F, Crainic TG, Rei W (2021) A learning-based matheuristic for stochastic multicommodity network design. INFORMS J. Comput. 33(2):643–656.Abstract, Google Scholar
• Shen S, Smith JC, Goli R (2012) Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optim. 9(3):172–188.Crossref, Google Scholar
• Smith JC, Song Y (2020) A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3):797–811.Crossref, Google Scholar
• Smith JC, Lim C, Sudargho F (2007) Survivable network design under optimal and heuristic interdiction scenarios. J. Global Optim. 38(2):181–199.Crossref, Google Scholar
• Song Y, Shen S (2016) Risk-averse shortest path interdiction. INFORMS J. Comput. 28(3):527–539.Link, Google Scholar
• Tahernejad S, Ralphs TK, DeNegre ST (2020) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Programming Comput. 12(4):529–568.Crossref, Google Scholar
• Vaziri SM, Kuzgunkaya O, Vidyarthi N (2024) An exact algorithm for multicommodity network design under stochastic interdictions. http://dx.doi.org/10.1287/ijoc.2023.0286.cd, https://github.com/INFORMSJoC/2023.0286.Google Scholar
• Wang X, Crainic TG, Wallace SW (2019) Stochastic network design for planning scheduled transportation services: The value of deterministic solutions. INFORMS J. Comput. 31(1):153–170.Link, Google Scholar
• Washburn A, Wood K (1995) Two-person zero-sum games for network interdiction. Oper. Res. 43(2):243–251.Link, Google Scholar
• Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1–18.Crossref, Google Scholar
• Yaghini M, Karimi M, Rahbar M, Sharifitabar MH (2015) A cutting-plane neighborhood structure for fixed-charge capacitated multicommodity network design problem. INFORMS J. Comput. 27(1):48–58.Link, Google Scholar
• Zare MH, Borrero JS, Zeng B, Prokopyev OA (2019) A note on linearized reformulations for a class of bilevel linear integer problems. Ann. Oper. Res. 272(1):99–117.Crossref, Google Scholar
• Zetina CA, Contreras I, Cordeau JF (2019) Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design. Comput. Oper. Res. 111(11):311–324.Crossref, Google Scholar
• Zetina CA, Contreras I, Jayaswal S (2021) An exact algorithm for large-scale non-convex quadratic facility location. Preprint, submitted July 20, https://arxiv.org/abs/2107.09746.Google Scholar
• Zhang P, Fan N (2017) Analysis of budget for interdiction on multicommodity network flows. J. Global Optim. 67(3):495–525.Crossref, Google Scholar