On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

References

• Abello J, Butenko S, Pardalos PM, Resende MG (2001) Finding independent sets in a graph using continuous multivariable polynomial formulations. J. Global Optim. 21(2):111–137. Crossref, Google Scholar
• Ahmadi AA, Zhang J (2022) On the complexity of finding a local minimizer of a quadratic function over a polytope. Math. Programming 195(1–2):783–792.Crossref, Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (1997) Links between linear bilevel and mixed 0-1 programming problems. J. Optim. Theory Appl. 93(2):273–300.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
• 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
• Ben-Ayed O, Blair CE (1990) Computational difficulties of bilevel linear programming. Oper. Res. 38(3):556–560.Link, Google Scholar
• Borrero JS, Prokopyev OA, Sauré D (2019) Sequential interdiction with incomplete information and learning. Oper. Res. 67(1):72–89.Link, Google Scholar
• Brenner J, Cummings L (1972) The Hadamard maximum determinant problem. Amer. Math. Monthly 79(6):626–630.Crossref, Google Scholar
• Buchheim C (2023) Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations. Oper. Res. Lett. 51(6):618–622.Crossref, Google Scholar
• Busygin S (2006) A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. (1979) 154(15):2080–2096.Crossref, Google Scholar
• De Santis M, Rinaldi F (2012) Continuous reformulations for zero–one programming problems. J. Optim. Theory Appl. 153(1):75–84. Crossref, Google Scholar
• Dempe S (2002) Foundations of Bilevel Programming (Springer Science & Business Media, Boston).Google Scholar
• Deng X (1998) Complexity issues in bilevel linear programming. Pardalos P, Migdalas A, Värbrand P, eds. Multilevel Optimization: Algorithms and Applications (Springer, Berlin), 149–164.Crossref, Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco).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
• Hiriart-Urruty JB, Seeger A (2010) A variational approach to copositive matrices. SIAM Rev. 52(4):593–629.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
• Khachiyan LG (1979) A polynomial algorithm in linear programming. Doklady Akademii Nauk. Sciences. 244(5):1093–1096. 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
• Kleinert T, Labbé M, Plein F, Schmidt M (2020) There’s no free lunch: On the hardness of choosing a correct big-M in bilevel optimization. Oper. Res. 68(6):1716–1721.Link, Google Scholar
• Lagos T, Prokopyev OA (2023) On complexity of finding strong-weak solutions in bilevel linear programming. Oper. Res. Lett. 51(6):612–617.Crossref, Google Scholar
• Marcotte P, Savard G (2005) Bilevel programming: A combinatorial perspective. Avis D, Hertz A, Marcotte O, eds. Graph Theory and Combinatorial Optimization (Springer, Berlin), 191–217.Crossref, Google Scholar
• Marcotte P, Mercier A, Savard G, Verter V (2009) Toll policies for mitigating hazardous materials transport risk. Transportation Sci. 43(2):228–243.Link, Google Scholar
• Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of Turán. Canadian J. Math. 17:533–540. Crossref, Google Scholar
• Pardalos PM, Schnitger G (1988) Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1):33–35.Crossref, Google Scholar
• Pardalos PM, Vavasis SA (1991) Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1):15–22.Crossref, Google Scholar
• Pardalos PM, Vavasis SA (1992) Open questions in complexity theory for numerical optimization. Math. Programming 57(1–3):337–339.Crossref, Google Scholar
• Pardalos PM, Xue J (1994) The maximum clique problem. J. Glob. Optim. 4(3):301–328. Crossref, Google Scholar
• Shi X, Prokopyev OA, Ralphs TK (2023) Mixed integer bilevel optimization with a k-optimal follower: A hierarchy of bounds. Math. Programming Comput. 15(1):1–51.Crossref, Google Scholar
• Stozhkov V, Buchanan A, Butenko S, Boginski V (2022) Continuous cubic formulations for cluster detection problems in networks. Math. Programming 196(1):279–307.Crossref, Google Scholar
• Vicente L, Savard G, Júdice J (1994) Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2):379–399.Crossref, Google Scholar
• Xia W, Vera JC, Zuluaga LF (2020) Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput. 32(1):40–56.Link, Google Scholar
• Yang J, Shi X, Prokopyev OA (2023) Exact solution approaches for a class of bilevel fractional programs. Optim. Lett. 17(1):191–210.Crossref, 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:99–117.Crossref, Google Scholar