Open Journal of Mathematical Optimization

Connections between Robust and Bilevel Optimization
Marc Goerigk1; Jannis Kurtz2; Martin Schmidt3; Johannes Thürauf4
1 University of Passau, Business Decisions and Data Science, Dr.-Hans-Kapfinger Str. 30, 94032 Passau, Germany
2 Amsterdam Business School, University of Amsterdam, 1018 TV Amsterdam, Netherlands
3 Trier University, Department of Mathematics, Universitätsring 15, 54296 Trier, Germany
4 University of Technology Nuremberg (UTN), Department Liberal Arts and Social Sciences, Discrete Optimization Lab, Dr.-Luise-Herzberg-Str. 4, 90461 Nuremberg, Germany
Open Journal of Mathematical Optimization, Volume 6 (2025), article no. 2, 17 p.

Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (static robust problems with and without decision-dependence of their uncertainty sets, worst-case regret problems, and two-stage robust problems) as well as of bilevel problems (optimistic problems, pessimistic problems, and robust bilevel problems). It turns out that bilevel optimization seems to be more general in the sense that for most types of robust problems, one can find proper reformulations as bilevel problems but not necessarily the other way around. We hope that these results pave the way for a stronger connection between the two fields—in particular to use both theory and algorithms from one field in the other and vice versa.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.38
Classification: 90C70, 91A65
Mots-clés : Bilevel optimization, Robust optimization, Reformulations
Marc Goerigk 1; Jannis Kurtz 2; Martin Schmidt 3; Johannes Thürauf 4

1 University of Passau, Business Decisions and Data Science, Dr.-Hans-Kapfinger Str. 30, 94032 Passau, Germany
2 Amsterdam Business School, University of Amsterdam, 1018 TV Amsterdam, Netherlands
3 Trier University, Department of Mathematics, Universitätsring 15, 54296 Trier, Germany
4 University of Technology Nuremberg (UTN), Department Liberal Arts and Social Sciences, Discrete Optimization Lab, Dr.-Luise-Herzberg-Str. 4, 90461 Nuremberg, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{OJMO_2025__6__A2_0,
     author = {Marc Goerigk and Jannis Kurtz and Martin Schmidt and Johannes Th\"urauf},
     title = {Connections between {Robust} and {Bilevel} {Optimization}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {2},
     pages = {1--17},
     publisher = {Universit\'e de Montpellier},
     volume = {6},
     year = {2025},
     doi = {10.5802/ojmo.38},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.38/}
}
TY  - JOUR
AU  - Marc Goerigk
AU  - Jannis Kurtz
AU  - Martin Schmidt
AU  - Johannes Thürauf
TI  - Connections between Robust and Bilevel Optimization
JO  - Open Journal of Mathematical Optimization
PY  - 2025
SP  - 1
EP  - 17
VL  - 6
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.38/
DO  - 10.5802/ojmo.38
LA  - en
ID  - OJMO_2025__6__A2_0
ER  - 
%0 Journal Article
%A Marc Goerigk
%A Jannis Kurtz
%A Martin Schmidt
%A Johannes Thürauf
%T Connections between Robust and Bilevel Optimization
%J Open Journal of Mathematical Optimization
%D 2025
%P 1-17
%V 6
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.38/
%R 10.5802/ojmo.38
%G en
%F OJMO_2025__6__A2_0
Marc Goerigk; Jannis Kurtz; Martin Schmidt; Johannes Thürauf. Connections between Robust and Bilevel Optimization. Open Journal of Mathematical Optimization, Volume 6 (2025), article  no. 2, 17 p. doi : 10.5802/ojmo.38. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.38/

[1] Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten Min–max and min–max regret versions of combinatorial optimization problems: A survey, Eur. J. Oper. Res., Volume 197 (2009) no. 2, pp. 427-438 | DOI | MR | Zbl

[2] Yasmine Beck; Ivana Ljubić; Martin Schmidt A Brief Introduction to Robust Bilevel Optimization (2022) | arXiv

[3] Yasmine Beck; Ivana Ljubić; Martin Schmidt A survey on bilevel optimization under uncertainty, Eur. J. Oper. Res., Volume 311 (2023) no. 2, pp. 401-426 | DOI | MR | Zbl

[4] Aharon Ben-Tal; Dick den Hertog; Jean-Philippe Vial Deriving robust counterparts of nonlinear uncertain inequalities, Math. Program., Volume 149 (2015) no. 1-2, pp. 265-299 | DOI | MR | Zbl

[5] Aharon Ben-Tal; Laurent El Ghaoui; Arkadi Nemirovski Robust Optimization, Princeton Series in Applied Mathematics, Princeton University Press, 2009, xxii+542 pages | DOI | MR

[6] Aharon Ben-Tal; Alexander Goryashko; Elana Guslitzer; Arkadi Nemirovski Adjustable robust solutions of uncertain linear programs, Math. Program., Volume 99 (2004) no. 2, pp. 351-376 | DOI | MR | Zbl

[7] Aharon Ben-Tal; Arkadi Nemirovski Robust Convex Optimization, Math. Oper. Res., Volume 23 (1998) no. 4, pp. 769-805 | DOI | MR

[8] Dimitris Bertsimas; David B. Brown; Constantine Caramanis Theory and Applications of Robust Optimization, SIAM Rev., Volume 53 (2011) no. 3, pp. 464-501 | DOI | MR | Zbl

[9] Dimitris Bertsimas; Dick den Hertog Robust and Adaptive Optimization, Dynamic Ideas LLC, 2022 https://www.dynamic-ideas.com/books/robust-and-adaptive-optimization

[10] Dimitris Bertsimas; Iain Dunning Relative robust and adaptive optimization, INFORMS J. Comput., Volume 32 (2020) no. 2, pp. 408-427 | DOI | MR | Zbl

[11] Luce Brotcorne; Christoph Buchheim; Dick den Hertog; Dorothee Henke Optimization at the Second Level (Dagstuhl Seminar 22441), Dagstuhl Reports, Volume 12 (2023) no. 10, pp. 207-224 | DOI

[12] Christoph Buchheim; Jannis Kurtz Min–max–min robust combinatorial optimization, Math. Program., Volume 163 (2017), pp. 1-23 | DOI | MR | Zbl

[13] Christoph Buchheim; Jannis Kurtz Robust combinatorial optimization under convex and discrete cost uncertainty, EURO J. Comput. Optim., Volume 6 (2018) no. 3, pp. 211-238 | DOI | MR | Zbl

[14] Martina Cerulli Bilevel optimization and applications, Ph. D. Thesis, Institut Polytechnique de Paris (2021) https://theses.hal.science/tel-03587548/document

[15] Stephan Dempe Foundations of Bilevel Programming, Springer, 2002 | DOI | MR

[16] Stephan Dempe Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography, Bilevel Optimization: Advances and Next Challenges (Stephan Dempe; Alain Zemkoho, eds.), Springer, 2020, pp. 581-672 | DOI | Zbl

[17] Stephan Dempe; Vyacheslav Kalashnikov; Gerardo A. Pérez-Valdés; Nataliya Kalashnykova Bilevel Programming Problems, Springer, 2015 | DOI | MR

[18] Simon French Decision theory: an introduction to the mathematics of rationality, Halsted Press, 1986 | MR

[19] Marc Goerigk; Adam Kasperski; Paweł Zieliński Combinatorial two-stage minmax regret problems under interval uncertainty, Ann. Oper. Res., Volume 300 (2021) no. 1, pp. 23-50 | DOI | MR | Zbl

[20] Adam Kasperski; Paweł Zieliński Robust Discrete Optimization Under Discrete and Interval Uncertainty: A Survey, Robustness analysis in decision aiding, optimization, and analytics (International Series in Operations Research & Management Science), Volume 241, Springer, 2016, pp. 113-143 | DOI

[21] Thomas Kleinert; Martine Labbé; Ivana Ljubić; Martin Schmidt A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization, EURO J. Comput. Optim., Volume 9 (2021), 100007, 21 pages | DOI | MR | Zbl

[22] Thomas Kleinert; Martine Labbé; Fränk Plein; Martin Schmidt There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization, Oper. Res., Volume 68 (2020) no. 6, pp. 1716-1721 | DOI | MR | Zbl

[23] Panos Kouvelis; Gang Yu Robust Discrete Optimization and Its Applications, Nonconvex Optimization and Its Applications, 14, Kluwer Academic Publishers, 1997 | DOI | MR | Zbl

[24] Sven Leyffer; Matt Menickelly; Todd Munson; Charlie Vanaret; Stefan M. Wild A survey of nonlinear robust optimization, INFOR: Inf. Syst. Oper. Res., Volume 58 (2020) no. 2, pp. 342-373 | DOI | MR | Zbl

[25] Ahmadreza Marandi; Dick den Hertog When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?, Math. Program., Volume 170 (2018), pp. 555-568 | DOI | MR | Zbl

[26] Omid Nohadani; Kartikey Sharma Optimization under Decision-Dependent Uncertainty, SIAM J. Optim., Volume 28 (2018) no. 2, pp. 1773-1795 | DOI | MR | Zbl

[27] Mehran Poursoltani; Erick Delage Adjustable robust optimization reformulations of two-stage worst-case regret minimization problems, Oper. Res., Volume 70 (2022) no. 5, pp. 2906-2930 | DOI | MR | Zbl

[28] Mikhail Solodov An explicit descent method for bilevel convex optimization, J. Convex Anal., Volume 14 (2007) no. 2, pp. 227-237 | MR | Zbl

[29] Allen L. Soyster Convex programming with set-inclusive constraints and applications to inexact linear programming, Oper. Res., Volume 21 (1973) no. 5, pp. 1154-1157 | DOI | Zbl

[30] Oliver Stein Bi-Level Strategies in Semi-Infinite Programming, Springer, 2013 | DOI | MR

[31] Sahar Tahernejad; Ted K. Ralphs; Scott T. DeNegre A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation, Math. Program. Comput., Volume 12 (2020) no. 4, pp. 529-568 | DOI | MR | Zbl

[32] Hoang Tuy; Athanasios Migdalas; Peter Värbrand A global optimization approach for the linear two-level program, J. Glob. Optim., Volume 3 (1993), pp. 1-23 | DOI | MR | Zbl

[33] Wolfram Wiesemann; Angelos Tsoukalas; Polyxeni-Margarita Kleniati; Berç Rustem Pessimistic Bilevel Optimization, SIAM J. Optim., Volume 23 (2013) no. 1, pp. 353-380 | DOI | MR | Zbl

[34] İhsan Yanıkoğlu; Bram L. Gorissen; Dick den Hertog A survey of adjustable robust optimization, Eur. J. Oper. Res., Volume 277 (2019) no. 3, pp. 799-813 | DOI | MR | Zbl

[35] Bo Zeng; Yu An Solving bilevel mixed integer program by reformulations and decomposition (2014) (https://optimization-online.org/?p=12967)

Cited by Sources: