Heuristic Methods for Γ-Robust Mixed-Integer Linear Bilevel Problems

References

• Álvarez-Miranda E, Ljubić I, Toth P (2013) A note on the Bertsimas & Sim algorithm for robust combinatorial optimization problems. 4OR Quart. J. Oper. Res. 11(4):349–360.Crossref, Google Scholar
• Beck Y, Ljubić I, Schmidt M (2022) A brief introduction to robust bilevel optimization. SIAG Optim. Views News 30(2):1–10.Google Scholar
• Beck Y, Ljubić I, Schmidt M (2023a) A survey on bilevel optimization under uncertainty. Eur. J. Oper. Res. 311(2):401–426.Crossref, Google Scholar
• Beck Y, Ljubić I, Schmidt M (2023b) Exact methods for discrete Γ-robust interdiction problems with an application to the bilevel knapsack problem. Math. Programming Comput. 15(4):733–782.Crossref, Google Scholar
• Beck Y, Ljubić I, Schmidt M (2025) Heuristic methods for Γ-robust mixed-integer linear bilevel problems. http://dx.doi.org/10.1287/ijoc.2023.0239.cd, https://github.com/INFORMSJoC/2023.0239.Google Scholar
• Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769–805.Link, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Bertsekas DP (2009) Convex Optimization Theory (Athena Scientific, Nashua, NH).Google Scholar
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1):49–71.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer-Verlag, New York).Crossref, Google Scholar
• Brown G, Carlyle M, Salmerón J, Wood R (2006) Defending critical infrastructure. Interfaces 36(6):530–544.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
• Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• Dempe S (2002) Foundations of Bilevel Programming (Springer, New York).Google Scholar
• Dempe S (2020) Bilevel optimization: Theory, algorithms, applications and a bibliography. Dempe S, Zemkoho A, eds. Bilevel Optimization, Springer Optimization and Its Applications, vol. 161 (Springer International Publishing, Cham, Switzerland), 581–672.Crossref, Google Scholar
• DeNegre ST (2011) Interdiction and discrete bilevel linear programming. Dissertation, Computational Optimization Research at Lehigh (COR@L) Laboratory of the Industrial and Systems Engineering Department, Lehigh University, Bethlehem, PA.Google Scholar
• Fischetti M, Monaci M, Sinnl M (2018) A dynamic reformulation heuristic for generalized interdiction problems. Eur. J. Oper. Res. 267(1):40–51.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, Malaguti E, Paronuzzi P (2022) Casting light on the hidden bilevel combinatorial structure of the capacitated vertex separator problem. Oper. Res. 70(4):2399–2420.Link, Google Scholar
• Grüne C, Wulf L (2024) Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization. Preprint, submitted November 27, https://arxiv.org/abs/2311.10540.Google Scholar
• Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Statist. Comput. 13(5):1194–1217.Crossref, 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
• Kall P, Wallace SW (1994) Stochastic Programming, Wiley-Interscience Series in Systems and Optimization (Wiley, New York).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:100007.Crossref, Google Scholar
• Lee T, Kwon C (2014) A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty. 4OR Quart. J. Oper. Res. 12(4):373–378.Crossref, 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
• Pisinger D, Toth P (1998) Knapsack Problems (Springer, Boston).Google Scholar
• Schmidt M, Beck Y (2023) A gentle and incomplete introduction to bilevel optimization. Preprint, submitted July 26, https://optimization-online.org/?p=17182.Google Scholar
• Sim M (2004) Robust optimization. PhD thesis, Operations Research Center, Sloan School of Management, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Soyster AL (1973) Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21(5):1154–1157.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
• von Stackelberg H (1932) Marktform und Gleichgewicht (Springer, Vienna).Google Scholar
• von Stackelberg H (1954) The Theory of the Market Economy (Oxford University Press, Oxford, UK).Google Scholar
• Weninger N, Fukasawa R (2023) A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints. Del Pia A, Kaibel V, eds. Integer Programming and Combinatorial Optimization, IPCO 2023, Lecture Notes in Computer Science, vol. 13904 (Springer, Cham, Switzerland), 438–452.Crossref, Google Scholar
• Wood RK (2011) Bilevel network interdiction models: Formulations and solutions. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (Wiley, Hoboken, NJ).Crossref, Google Scholar