Theoretical and Numerical Comparison of Nine Single-Level Reformulations for Bilevel Programs

References

• Ben-Ayed O, Blair CE (1990) Computational difficulties of bilevel linear programming. Oper. Res. 38(3):556–560.Link, Google Scholar
• Byeon G, Van Hentenryck P (2022) Benders subproblem decomposition for bilevel problems with convex follower. INFORMS J. Comput. 34(3):1749–1767.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
• Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153:235–256.Crossref, Google Scholar
• Dempe S, Zemkoho A (2020) Bilevel Optimization: Advances and Next Challenges, Springer Optimization and Its Applications, vol. 161 (Springer, Berlin).Crossref, Google Scholar
• Goyal A, Zhang Y, He C (2023) Decision rule approaches for pessimistic bilevel linear programs under moment ambiguity with facility location applications. INFORMS J. Comput. 35(6):1342–1360.Link, Google Scholar
• Guo L, Lin GH, Ye JJ (2015) Solving mathematical programs with equilibrium constraints. J. Optim. Theory Appl. 166(1):234–256.Crossref, Google Scholar
• Hong M, Wai HT, Wang Z, Yang Z (2023) A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM J. Optim. 33(1):147–180.Crossref, Google Scholar
• Izmailov AF, Pogosyan AL, Solodov MV (2012) Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Comput. Optim. Appl. 51(1):199–221.Crossref, Google Scholar
• Khorramfar R, Özaltın OY, Kempf KG, Uzsoy R (2022) Managing product transitions: A bilevel programming approach. INFORMS J. Comput. 34(5):2828–2844.Link, Google Scholar
• Kleinert T, Schmidt M (2021) Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS J. Comput. 33(1):198–215.Link, Google Scholar
• Leyffer S, López-Calva G, Nocedal J (2006) Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17(1):52–77.Crossref, Google Scholar
• Li YW, Lin GH, Zhu X (2024a) Notes on lower-level duality approach for bilevel programs. Pacific J. Optim. 20(3):475–488.Google Scholar
• Li YW, Lin GH, Zhu X (2024b) Solving bilevel programs based on lower-level Mond-Weir duality. INFORMS J. Comput. 36(5):1225–1241.Link, Google Scholar
• Li YW, Lin GH, Zhu X (2026) Theoretical and numerical comparison of nine single-level reformulations for bilevel programs. https://doi.org/10.1287/ijoc.2025.1159.cd, https://github.com/INFORMSJoC/2025.1159.Google Scholar
• Li YW, Lin GH, Zhang J, Zhu X (2023) A novel approach for bilevel programs based on Wolfe duality. Preprint, submitted February 14, https://arxiv.org/abs/2302.06838.Google Scholar
• Lin GH, Fukushima M (2006) Hybrid approach with active set identification for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 128(1):1–28.Crossref, Google Scholar
• Lin GH, Chen X, Fukushima M (2009) Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization. Math. Programming 116(1):343–368.Crossref, Google Scholar
• Lin GH, Xu M, Ye JJ (2014) On solving simple bilevel programs with a nonconvex lower level program. Math. Programming 144(1):277–305.Crossref, Google Scholar
• Liu R, Liu X, Zeng S, Zhang J, Zhang Y (2023) Hierarchical optimization-derived learning. IEEE Trans. Pattern Anal. Machine Intelligence 45(12):14693–14708.Crossref, Google Scholar
• Lu Z, Mei S (2024) First-order penalty methods for bilevel optimization. SIAM J. Optim. 34(2):1937–1969.Crossref, Google Scholar
• Luo ZQ, Pang JS, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Mehlitz P, Zemkoho AB (2021) Sufficient optimality conditions in bilevel programming. Math. Oper. Res. 46(4):1573–1598.Link, Google Scholar
• Mond B, Weir T (1981) Generalized concavity and duality. Schaible S, Ziemba WT, eds. Generalized Concavity in Optimization and Economics (Academic Press, San Diego), 263–279.Google Scholar
• Sabach S, Shtern S (2017) A first order method for solving convex bilevel optimization problems. SIAM J. Optim. 27(2):640–660.Crossref, Google Scholar
• Scholtes S (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11(4):918–936.Crossref, Google Scholar
• Wolfe P (1961) A duality theorem for non-linear programming. Quart. Appl. Math. 19(3):239–244.Crossref, Google Scholar
• Xu M, Ye JJ (2014) A smoothing augmented Lagrangian method for solving simple bilevel programs. Comput. Optim. Appl. 59(1–2):353–377.Crossref, Google Scholar
• Ye JJ, Zhu D (2010) New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM J. Optim. 20(4):1885–1905.Crossref, Google Scholar
• Ye JJ, Yuan X, Zeng S, Zhang J (2023) Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. Math. Programming 198(2):1583–1616.Crossref, Google Scholar
• Zemkoho AB, Zhou S (2021) Theoretical and numerical comparison of the Karush-Kuhn-Tucker and value function reformulations in bilevel optimization. Comput. Optim. Appl. 78(2):625–674.Crossref, Google Scholar
• Zeng B (2020) A practical scheme to compute the pessimistic bilevel optimization problem. INFORMS J. Comput. 32(4):1128–1142.Abstract, Google Scholar