In bilevel optimization problems, two players, the leader and the follower, make their decisions in a hierarchy, and both decisions may influence each other. Usually one assumes that both players have full knowledge also of the other player’s data. In a more realistic model, uncertainty can be quantified, e.g., using the robust optimization approach: We assume that the leader does not know the follower’s objective function precisely, but only knows an uncertainty set of potential follower’s objectives, and her aim is to optimize the worst case of the corresponding scenarios. Now the question arises how the computational complexity of bilevel optimization problems changes under the additional complications of this type of uncertainty.
We make a further step towards answering this question by examining an easy bilevel problem. In the Bilevel Selection Problem, the leader and the follower each select some items from their own item set, while a common number of items to select in total is given, and each of the two players minimizes the total costs of the selected items, according to different sets of item costs. We show that this problem can be solved in polynomial time without uncertainty and then investigate the complexity of its robust version. If the leader’s item set and the follower’s item set are disjoint, it can still be solved in polynomial time in case of discrete uncertainty, interval uncertainty, and discrete uncorrelated uncertainty, using ideas from [6]. Otherwise, we show that the Robust Bilevel Selection Problem becomes NP-hard, even for discrete uncertainty. We present a 2-approximation algorithm and exact exponential-time approaches for this setting, including an algorithm that runs in polynomial time if the number of scenarios is a constant.
Furthermore, we investigate variants of the Bilevel Selection Problem where one or both of the two decision makers take a continuous decision. One variant leads to an example of a bilevel optimization problem whose optimal value may not be attained. For the Robust Continuous Bilevel Selection Problem, where all variables are continuous, we generalize results from [6] and also develop a new approach for the setting of discrete uncorrelated uncertainty, which gives a polynomial-time algorithm for the Robust Continuous Bilevel Selection Problem and a pseudopolynomial-time algorithm for the Robust Bilevel Continuous Knapsack Problem, answering an open question from [6].
Revised:
Accepted:
Published online:
Dorothee Henke 1
CC-BY 4.0
@article{OJMO_2025__6__A4_0,
author = {Dorothee Henke},
title = {The {Robust} {Bilevel} {Selection} {Problem}},
journal = {Open Journal of Mathematical Optimization},
eid = {4},
pages = {1--35},
publisher = {Universit\'e de Montpellier},
volume = {6},
year = {2025},
doi = {10.5802/ojmo.40},
language = {en},
url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.40/}
}
TY - JOUR AU - Dorothee Henke TI - The Robust Bilevel Selection Problem JO - Open Journal of Mathematical Optimization PY - 2025 SP - 1 EP - 35 VL - 6 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.40/ DO - 10.5802/ojmo.40 LA - en ID - OJMO_2025__6__A4_0 ER -
Dorothee Henke. The Robust Bilevel Selection Problem. Open Journal of Mathematical Optimization, Volume 6 (2025), article no. 4, 35 p. doi : 10.5802/ojmo.40. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.40/
[1] A survey on bilevel optimization under uncertainty, Eur. J. Oper. Res., Volume 311 (2023) no. 2, pp. 401-426 | DOI | MR | Zbl
[2] A Gentle and Incomplete Introduction to Bilevel Optimization, https://optimization-online.org/?p=17182, 2021
[3] Robust Optimization, Princeton Series in Applied Mathematics, Princeton University Press, 2009 no. 28 | DOI | MR
[4] Time bounds for selection, J. Comput. Syst. Sci., Volume 7 (1973) no. 4, pp. 448-461 | DOI | MR | Zbl
[5] Defending critical infrastructure, Interfaces, Volume 36 (2006) no. 6, pp. 530-544 | DOI
[6] The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective, J. Glob. Optim., Volume 83 (2022) no. 4, pp. 803-824 | DOI | MR | Zbl
[7] On the complexity of robust bilevel optimization with uncertain follower’s objective, Oper. Res. Lett., Volume 49 (2021) no. 5, pp. 703-707 | DOI | MR | Zbl
[8] On the complexity of the bilevel minimum spanning tree problem, Networks, Volume 80 (2022) no. 3, pp. 338-355 | DOI | MR | Zbl
[9] The stochastic bilevel continuous knapsack problem with uncertain follower’s objective, J. Optim. Theory Appl., Volume 194 (2022) no. 2, pp. 521-542 | DOI | Zbl
[10] Robust combinatorial optimization under convex and discrete cost uncertainty, EURO J. Comput. Optim., Volume 6 (2018) no. 3, pp. 211-238 | DOI | MR | Zbl
[11] A study on the computational complexity of the bilevel knapsack problem, SIAM J. Optim., Volume 24 (2014) no. 2, pp. 823-838 | DOI | MR | Zbl
[12] An overview of bilevel optimization, Ann. Oper. Res., Volume 153 (2007) no. 1, pp. 235-256 | DOI | MR | Zbl
[13] Parameterized Algorithms, Springer, 2015 | DOI | MR
[14] Discrete-variable extremum problems, Oper. Res., Volume 5 (1957) no. 2, pp. 266-277 | DOI | MR | Zbl
[15] Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography, Bilevel Optimization (Stephan Dempe; Alain Zemkoho, eds.) (Springer Optimization and Its Applications), Springer, 2020 no. 161, pp. 581-672 | DOI | Zbl
[16] Bilevel Programming Problems, Springer, 2015 | DOI | MR
[17] Bilevel programming with knapsack constraints, Cent. Eur. J. Oper. Res., Volume 8 (2000) no. 2, pp. 93-107 | MR | Zbl
[18] Interdiction and discrete bilevel linear programming, Ph. D. Thesis, Lehigh University, Bethlehem, Pennsylvania (2011)
[19] A note on the complexity of the bilevel bottleneck assignment problem, 4OR, Volume 20 (2022) no. 4, pp. 713-718 | DOI | MR | Zbl
[20] Computers and Intractability. A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Company, 1979 | MR
[21] The computational complexity of bilevel assignment problems, 4OR, Volume 7 (2009) no. 4, pp. 379-394 | DOI | MR | Zbl
[22] Connections between robust and bilevel optimization, Open J. Math. Optim., Volume 6 (2025), 2, 17 pages | DOI | MR
[23] The robust bilevel selection problem, Masters thesis, TU Dortmund University (2021) (unpublished)
[24] Finding the upper envelope of line segments in time, Inf. Process. Lett., Volume 33 (1989) no. 4, pp. 169-174 | DOI | MR | Zbl
[25] The polynomial hierarchy and a simple model for competitive analysis, Math. Program., Volume 32 (1985) no. 2, pp. 146-164 | DOI | MR | Zbl
[26] A randomized algorithm for the min–max selecting items problem with uncertain weights, Ann. Oper. Res., Volume 172 (2009) no. 1, pp. 221-230 | DOI | MR | Zbl
[27] Knapsack Problems, Springer, 2004 | DOI | MR
[28] Combinatorial Optimization, Algorithms and Combinatorics, Springer, 2018 no. 21 | DOI | MR
[29] Robust Discrete Optimization and Its Applications, Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, 1997 no. 14 | DOI | MR
[30] An exact algorithm for bilevel 0-1 knapsack problems, Math. Probl. Eng., Volume 2012 (2012), 504713, 23 pages | DOI | MR | Zbl
[31] Bilevel programming: A combinatorial perspective, Graph Theory and Combinatorial Optimization (David Avis; Alain Hertz; Odile Marcotte, eds.), Springer, 2005, pp. 191-217 | DOI | Zbl
[32] Computationally tractable classes of ordered sets, Algorithms and Order (Ivan Rival, ed.) (NATO ASI Series. Series C. Mathematical and Physical Sciences), Kluwer Academic Publishers, 1989 no. 255, pp. 105-193 | DOI | Zbl
[33] On bilevel minimum and bottleneck spanning tree problems, Networks, Volume 74 (2019) no. 3, pp. 251-273 | DOI | MR | Zbl
[34] Discrete linear bilevel programming problem, J. Optim. Theory Appl., Volume 89 (1996) no. 3, pp. 597-614 | DOI | MR | Zbl
[35] On the approximability of average completion time scheduling under precedence constraints, Discrete Appl. Math., Volume 131 (2003) no. 1, pp. 237-252 | DOI | MR | Zbl
[36] The trouble with the second quantifier, 4OR, Volume 19 (2021) no. 2, pp. 157-181 | DOI | MR | Zbl
Cited by Sources: