Interdiction Games and Monotonicity, with Application to Knapsack Problems

References

• Balas E (1989) The prize collecting traveling salesman problem. Networks 19(6):621–636.Crossref, Google Scholar
• Balas E (2007) The prize collecting traveling salesman problem and its applications. Gutin G, Punnen AP, eds. The Travelling Salesman Problem and Its Variations, Combinatorial Optimization, vol. 12 (Springer, Boston), 663–695.Google Scholar
• Bazgan C, Toubaline S, Tuza Z (2011) The most vital nodes with respect to independent set and vertex cover. Discrete Appl. Math. 159(17):1933–1946.Crossref, Google Scholar
• Bienstock D, Goemans MX, Simchi-Levi D, Williamson D (1993) A note on the prize collecting traveling salesman problem. Math. Programming 59(1–3):413–420.Crossref, Google Scholar
• Brown G, Carlyle M, Salmeron J, Wood K (2005) Analyzing the vulnerability of critical infrastructure to attack and planning defenses. Smith JC, ed. Emerging Theory, Methods, and Applications, TutORials in Operations Research (INFORMS, Catonsville, MD), 102–123.Link, Google Scholar
• Brown G, Carlyle M, Salmeron J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530–544.Link, Google Scholar
• Brown G, Carlyle M, Harney R, Skroch E, Wood K (2009) Interdicting a nuclear-weapons project. Oper. Res. 57(4):866–877.Link, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2014) A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2):823–838.Crossref, 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
• Cormican K, Morton D, Wood K (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Dinitz M, Gupta A (2013) Packing interdiction and partial covering problems. Goemans M, Correa J, eds. Proc. 16th Internat. Conf. Integer Programming Combin. Optim. (Springer-Verlag, Berlin), 157–168.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2016) Intersection cuts for bilevel optimization. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combin. Optim. (Springer International Publishing, Cham, Switzerland), 77–88.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017a) An improved branch-and-cut algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6):1615–1637.Link, Google Scholar
• Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, Salvagnin D, Sinnl M (2017b) Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Programming Comput. 9(2):203–229.Crossref, Google Scholar
• Freville A, Plateau G (1990) Hard 0-1 multiknapsack test problems for size reduction methods. Investigation Oper. 1:251–270.Google Scholar
• Halldórsson MM (2000) Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl. 4(1):1–16.Crossref, Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Khuri S, Baeck T, Heitkoetter J (1994) SAC94 suite: Collection of multiple knapsack problems. Accessed October 31, 2016, http://www.cs.cmu.edu/Groups/AI/areas/genetic/ga/test/sac/0.html.Google Scholar
• Kleniati PM, Adjiman CS (2015) A generalization of the branch-and-sandwich algorithm: From continuous to mixed-integer nonlinear bilevel problems. Comput. Chemical Engrg. 72:373–386.Crossref, Google Scholar
• Lim C, Smith J (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1):15–26.Crossref, Google Scholar
• Ljubić I, Weiskircher R, Pferschy U, Klau GW, Mutzel P, Fischetti M (2006) An algorithmic framework for the exact solution of the prize-collecting steiner tree problem. Math. Programming 105(2-3):427–449.Crossref, Google Scholar
• Lozano L, Smith J (2017) A value-function-based exact approach for the bilevel mixed integer programming problem. Oper. Res. 65(3):768–786.Link, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Chichester, NY).Google Scholar
• Martello S, Pisinger D, Toth P (1999) Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Sci. 45(3):414–424.Link, Google Scholar
• Moore J, Bard J (1990) The mixed integer linear bilevel programming problem. Oper. Res. 38(5):911–921.Link, Google Scholar
• Morton DP, Pan F, Saeger KJ (2007) Models for nuclear smuggling interdiction. IIE Trans. 39(1):3–14.Crossref, Google Scholar
• Petersen CC (1967) Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Sci. 13(9):736–750.Link, Google Scholar
• Prodon A, DeNegre S, Liebling TM (2010) Locating leak detecting sensors in a water distribution network by solving prize-collecting steiner arborescence problems. Math. Programming 124(1/2):119–141.Crossref, Google Scholar
• Ralphs T (2015) Bilevel integer optimization: Theory and algorithms. Proc. 22nd Internat. Sympos. Math. Programming, Pittsburgh, 1–44.Google Scholar
• Senju S, Toyoda Y (1968) An approach to linear programming with 0-1 variables. Management Sci. 15(4):B196–B207.Link, Google Scholar
• Shih W (1979) A branch and bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. 30(4):369–378.Crossref, Google Scholar
• Smith JC, Lim C (2008) Algorithms for Network Interdiction and Fortification Games (Springer, New York), 609–644.Crossref, Google Scholar
• Song Y, Shen S (2016) Risk averse shortest path interdiction. INFORMS J. Comput. 28(3):527–539.Link, Google Scholar
• Tang Y, Richard JPP, Smith JC (2015) A class of algorithms for mixed-integer bilevel min–max optimization. J. Global Optim. 66(2):225–262.Crossref, Google Scholar
• Vansteenwegen P, Souffriau W, Van Oudheusden D (2011) The orienteering problem: A survey. Eur. J. Oper. Res. 209(1):1–10.Crossref, Google Scholar
• von Stackelberg H (1952) The Theory of the Market Economy (Oxford University Press, London, UK).Google Scholar
• Washburn A, Wood K (1995) Two-person zero-sum games for network interdiction. Oper. Res. 43(2):243–251.Link, Google Scholar
• Weingartner HM, Ness DN (1967) Methods for the solution of the multidimensional 0/1 knapsack problem. Oper. Res. 15(1):83–103.Link, Google Scholar
• Wood RK (2010) Bilevel Network Interdiction Models: Formulations and Solutions (John Wiley & Sons, Chichester, NY).Google Scholar
• Xu P (2012) Three essays on bilevel optimization algorithms and applications. PhD thesis, Iowa State University, Ames.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
• Zeng B, An Y (2014) Solving bilevel mixed integer program by reformulations and decomposition. Accessed August 20, 2016, http://www.optimization-online.org/DB_FILE/2014/07/4455.pdf.Google Scholar
• Zenklusen R (2010) Matching interdiction. Discrete Appl. Math. 158(15):1676–1690.Crossref, Google Scholar