A Branch-and-Cut Algorithm for Submodular Interdiction Games

References

• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1–2):149–169.Crossref, Google Scholar
• Aksen D, Akca SŞ, Aras N (2014) A bilevel partial interdiction problem with capacitated facilities and demand outsourcing. Comput. Oper. Res. 41:346–358.Crossref, Google Scholar
• Aksen D, Piyade N, Aras N (2010) The budget constrained r-interdiction median problem with capacity expansion. Central Eur. J. Oper. Res. 18(3):269–291.Crossref, Google Scholar
• Alon N, Gamzu I, Tennenholtz M (2012) Optimizing budget allocation among channels and influencers. Mille A, Gandon F, Misselis J, Rabinovich M, Staab S, eds. Proc. 21st Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 381–388.Google Scholar
• Bayrak H, Bailey MD (2008) Shortest path network interdiction with asymmetric information. Networks 52(3):133–140.Crossref, Google Scholar
• Ben-Ayed O, Blair CE (1990) Computational difficulties of bilevel linear programming. Oper. Res. 38(3):556–560.Link, Google Scholar
• Bogunovic I, Mitrović S, Scarlett J, Cevher V (2017) Robust submodular maximization: A non-uniform partitioning approach. Precup D, Teh YW, eds. Internat. Conf. Machine Learn. (PMLR), 508–516.Google Scholar
• Bonnet C, Simioni M (2001) Assessing consumer response to protected designation of origin labelling: A mixed multinomial logit approach. Eur. Rev. Agricultural Econom. 28(4):433–449.Crossref, Google Scholar
• Borrero JS, Lozano L (2021) Modeling defender-attacker problems as robust linear programs with mixed-integer uncertainty sets. INFORMS J. Comput. 33(4):1570–1589.Abstract, Google Scholar
• Brotcorne L, Hanafi S, Mansi R (2013) One-level reformulation of the bilevel knapsack problem using dynamic programming. Discrete Optim. 10(1):1–10.Crossref, Google Scholar
• Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530–544.Link, Google Scholar
• Calinescu G, Chekuri C, Pál M, Vondrák J (2007) Maximizing a submodular set function subject to a matroid constraint. Fischetti M, Williamson DP, eds. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin, Heidelberg, Germany), 182–196.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
• Church R, ReVelle C (1974) The maximal covering location problem. Papers Regional Sci. Assoc. 32:101–118.Crossref, Google Scholar
• Church RL, Scaparra MP, Middleton RS (2004) Identifying critical infrastructure: The median and covering facility interdiction problems. Ann. Assoc. Amer. Geographers 94(3):491–502.Crossref, Google Scholar
• Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, Wood RK (2011) Bilevel network interdiction models: Formulations and solutions. Wiley Encyclopedia of Operations Research and Management Science (Wiley, Hoboken, NJ).Crossref, Google Scholar
• Coniglio S, Furini F, Ljubic I (2020) Maximizing submodular utility functions combined with a set-union operator over a discrete set Working paper, Mathematical Sciences, University of Southampton, England. http://www.optimization-online.org/DB_HTML/2020/04/7715.html.Google Scholar
• Contardo C, Sefair JA (2021) 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
• Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• Cornuejols G, Fisher M, Nemhauser G (1977) Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci. 23:789–810.Link, Google Scholar
• Della Croce F, Scatamacchia R (2020) An exact approach for the bilevel knapsack problem with interdiction constraints and extensions. Math. Programming 183(1):249–281.Crossref, Google Scholar
• Dempe S, Zemkoho A (2020) Bilevel optimization (Springer, Cham, Switzerland).Crossref, Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Dong L, Xu-chen L, Xiang-tao Y, Fei W (2010) A model for allocating protection resources in military logistics distribution system based on maximal covering problem. 2010 Internat. Conf. Logist. Systems Intelligent Management (ICLSIM), vol. 1 (IEEE, New York), 98–101.Google Scholar
• Du D, Ko KI, Hu X (2012) Design and Analysis of Approximation Algorithms, vol. 62 (Springer, New York).Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017) A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6):1615–1637.Link, 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
• Furini F, Ljubić I, Martin S, San Segundo P (2019) The maximum clique interdiction problem. Eur. J. Oper. Res. 277(1):112–127.Crossref, Google Scholar
• Furini F, Ljubić I, San Segundo P, Zhao Y (2021) A branch-and-cut algorithm for the edge interdiction clique problem. Eur. J. Oper. Res. 294(1):54–69.Crossref, Google Scholar
• Golden B (1978) A problem in network interdiction. Naval Res. Logist. Quart. 25(4):711–713.Crossref, Google Scholar
• Guestrin C, Krause A, Singh AP (2005) Near-optimal sensor placements in Gaussian processes. Dzeroski S, Raedt LD, Wrobel S, eds. Proc. 22nd Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 265–272.Google Scholar
• Han, S, Gómez, A, Prokopyev, OA (2022) Fractional 0–1 programming and submodularity. J. Glob. Optim. https://doi.org/10.1007/s10898-022-01131-5.Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Kazemi E, Zadimoghaddam M, Karbasi A (2018) Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. Dy J, Krause A, eds. Internat. Conf. Machine Learn. (PMLR), 2544–2553.Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. Getoor L, Senator T, Domingos P, Faloutsos C, eds. Proc. 9th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 137–146.Google Scholar
• Krause A, Golovin D (2014) Submodular function maximization. Tractability 3:71–104.Crossref, Google Scholar
• Krause A, McMahan HB, Guestrin C, Gupta A (2008) Robust submodular observation selection. J. Machine Learn. Res. 9(12):2761–2801.Google Scholar
• Kunnumkal S, Martínez-de Albéniz V (2019) Tractable approximations for assortment planning with product costs. Oper. Res. 67(2):436–452.Abstract, Google Scholar
• Laporte G, Nickel S, Saldanha da Gama F, eds. (2015) Location Science, 1st ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• Ljubić I, Moreno E (2018) Outer approximation and submodular cuts for maximum capture facility location problems with random utilities. Eur. J. Oper. Res. 266(1):46–56.Crossref, Google Scholar
• Lozano L, Smith JC (2017a) A backward sampling framework for interdiction problems with fortification. INFORMS J. Comput. 29(1):123–139.Link, Google Scholar
• Lozano L, Smith JC (2017b) A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65(3):768–786.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
• Mc Carthy SM, Tambe M, Kiekintveld C, Gore M, Killion A (2016) Preventing illegal logging: Simultaneous optimization of resource teams and tactics for security. Schuurmans D, Wellman M, eds. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), vol. 30.Google Scholar
• McFadden D, Train K (2000) Mixed MNL models for discrete response. J. Appl. Econometrics 15(5):447–470.Crossref, Google Scholar
• Morton DP, Pan F, Saeger KJ (2007) Models for nuclear smuggling interdiction. IIE Trans. 39(1):3–14.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Orlin JB, Schulz AS, Udwani R (2016) Robust monotone submodular function maximization. Louveaux Q, Skutella M, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham), 312–324.Crossref, Google Scholar
• ReVelle C, Scholssberg M, Williams J (2008) Solving the maximal covering location problem with heuristic concentration. Comput. Oper. Res. 35(2):427–435.Crossref, Google Scholar
• Roboredo MC, Aizemberg L, Pessoa AA (2019) An exact approach for the r-interdiction covering problem with fortification. Central Eur. J. Oper. Res. 27(1):111–131.Crossref, Google Scholar
• Sakaue S, Ishihata M (2018) Accelerated best-first search with upper-bound computation for submodular function maximization. McIlraith S, Weinberger K, eds. Proc. AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), vol. 32.Google Scholar
• Salvagnin D (2019) Some experiments with submodular function maximization via integer programming. Rousseau L-M, Stergiou K, eds. Internat. Conf. Integration Constraint Programming Artificial Intelligence Oper Res. (Springer, Cham, Switzerland), 488–501.Google Scholar
• Scaparra MP, Church RL (2008a) A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35(6):1905–1923.Crossref, Google Scholar
• Scaparra MP, Church RL (2008b) An exact solution approach for the interdiction median problem with fortification. Eur. J. Oper. Res. 189(1):76–92.Crossref, Google Scholar
• Sefair JA, Smith JC, Acevedo MA, Fletcher RJ Jr (2017) A defender-attacker model and algorithm for maximizing weighted expected hitting time with application to conservation planning. IISE Trans. 49(12):1112–1128.Crossref, 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 (2010) Basic interdiction models. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (Wiley, Hoboken, NJ).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
• 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
• Tang Y, Richard JPP, Smith JC (2016) A class of algorithms for mixed-integer bilevel min–max optimization. J. Global Optim. 66(2):225–262.Crossref, Google Scholar
• Tanınmış K, Aras N, Altınel İK (2021) Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks. Eur. J. Oper. Res. 297(1):40–52.Google Scholar
• Tawarmalani M, Ahmed S, Sahinidis NV (2002) Global optimization of 0-1 hyperbolic programs. J. Global Optim. 24(4):385–416.Crossref, Google Scholar
• Vohra RV, Hall NG (1993) A probabilistic analysis of the maximal covering location problem. Discrete Appl. Math. 43(2):175–183.Crossref, Google Scholar
• Von Stackelberg H (1952) The Theory of the Market Economy (Oxford University Press, New York).Google Scholar
• Wollmer R (1964) Removing arcs from a network. Oper. Res. 12(6):934–940.Link, Google Scholar
• Wood RK (1993) Deterministic network interdiction. Math. Comput. Model. 17(2):1–18.Crossref, Google Scholar
• Xu P, Wang L (2014) An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41:309–318.Crossref, Google Scholar
• Yue D, Gao J, Zeng B, You F (2019) A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs. J. Global Optim. 73(1):27–57.Crossref, Google Scholar
• Zheng K, Albert LA (2018) An exact algorithm for solving the bilevel facility interdiction and fortification problem. Oper. Res. Lett. 46(6):573–578.Crossref, Google Scholar