Abstract
In this article, we summarize a subset of the findings of the cumulative dissertation “Algorithms for Mixed-Integer Bilevel Problems with Convex Followers”; see [4]. First, we present a result that renders the application of the well-known and widely used big-M reformulation of linear bilevel problems infeasible for many practical applications. Second, we present valid inequalities and demonstrate that an SOS1-based approach is a competitive alternative to the error-prone big-M method in case both approaches are equipped with these valid inequalities. Third, we introduce a penalty alternating direction method, which computes (close-to-)optimal feasible points in extremely short computation times and outperforms a state-of-the-art local method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Dempe, S. (2019). Computing locally optimal solutions of the bilevel optimization problem using the KKT approach. In M. Khachay, Y. Kochetov, & P. Pardalos (Eds.), Mathematical Optimization Theory and Operations Research (pp. 147-157). Springer,2019. https://doi.org/10.1007/978-3-030-22629-911
Fortuny-Amat, J., & McCarl, B. (1981). A representation and economic interpretation of a two-level programming problem. The Journal of the Operational Research Society 32(9), pp. 783-792. https://doi.org/10.1057/jors.1981.156
Hansen, P., Jaumard, B., & Savard, G. (1992). New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing 13(5), 1194-1217. https://doi.org/10.1137/0913069
Kleinert, T. (2021). Algorithms for mixed-integer bilevel problems with convex followers. PhD thesis. Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), pp. 1 -272. url: https://opus4.kobv.de/opus4-fau/files/16225/dissertationkleinert published digital.pdf (visited on 08/15/2022).
Kleinert, T., Labbé, M., Plein, F., & Schmidt, M. (2021). Closing the gap in linear bilevel optimization: a new valid primal-dual inequality. Optimization Letters, 15, 1027–1040. https://doi.org/10.1007/s11590-020-01660-6
Kleinert, T., Labbé, M., Plein, F., Schmidt, M. (2020). Technical note-there’s no free lunch: On the hardness of choosing a correct big-M in cilevel optimization. Operations Research 68(6), pp. 1716-1721. https://doi.org/10.1287/opre.2019.1944
Kleinert, T., & Schmidt, M. (2021). Computing feasible points of bilevel problems with a penalty alternating direction method. INFORMS Journal on Computing 33(1) , 198-215. https://doi.org/10.1287/ijoc.2019.0945
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kleinert, T. (2023). Computational Linear Bilevel Optimization. In: Grothe, O., Nickel, S., Rebennack, S., Stein, O. (eds) Operations Research Proceedings 2022. OR 2022. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-24907-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-24907-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-24906-8
Online ISBN: 978-3-031-24907-5
eBook Packages: Business and ManagementBusiness and Management (R0)