Dagstuhl Seminar 22441
Optimization at the Second Level
( Oct 30 – Nov 04, 2022 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/22441
Organizers
- Luce Brotcorne (INRIA Lille, FR)
- Christoph Buchheim (TU Dortmund, DE)
- Dick den Hertog (University of Amsterdam, NL)
- Gerhard J. Woeginger ( in memoriam; † April 1, 2022)
Contact
- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)
Impacts
- Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations - Buchheim, Christoph - Amsterdam : Elsevier, 2023. - pp. 618-622 - (Operations Research Letters ; 51. 2023, 6).
- Connections and Reformulations between Robust and Bilevel Optimization - Goerigk, Marc; Kurtz, Jannis; Schmidt, Martin; Thürauf, Johannes - Optimization Online, 2023. - 20 pp..
- A Framework for Data-Driven Explainability in Mathematical Optimization - Aigner, Kevin-Martin; Goerigk, Marc; Hartisch, Michael; Miehlich, Arthur - Cornell University : arXiv.org, 2023. - 18 pp..
Schedule
Topic of the Seminar
The second level of the polynomial hierarchy contains a variety of problems that allow natural simple formulations with one existential and one universal quantifier. For instance, a typical problem in robust optimization asks whether there EXISTS some production plan that performs reasonably well under ALL possible price scenarios for electricity in the coming two years. A typical problem in bilevel optimization asks whether there EXISTS a way of setting taxes so that ALL possible behaviors of the citizens generate a reasonable tax revenue. A typical problem in Stackelberg games asks whether there EXISTS a starting move for the first player that wins the game against ALL possible counter-moves of the second player.
Problems of this type are usually complete for the class Σ2p and hence are most likely not contained in the class NP. For that reason, the methodologies that have been developed for NP-complete problems over the last 50 years do not directly apply to robust and/or bilevel optimization problems. Up to the current moment, most of the work on such problems is purely computational and without any deeper theoretical understanding. Most approaches simply try to carry over the well-developed machinery from integer programming to concrete robust problems and bilevel problems. We will need to develop new techniques, new tricks, new insights, new algorithms, and new theorems to get a grip on this area.
The goal of this Dagstuhl Seminar was to bring together experts in theoretical computer science and experts in combinatorial optimization, and to work towards the following goals:
- summarize the status quo of robust optimization and bilevel optimization,
- identify central research lines on the computational and implementational front,
- identify central research lines in theoretical computer science, as for instance in parameterized complexity and approximability.
The list of participants perfectly reflected these goals, it included experts in complexity theory as well as researchers interested in the development of effective algorithms and the practical solution of real-world bilevel or robust optimization problems.
Implementation and Conclusions
In this seminar we brought together, for the first time, leading researchers from three different communities (robust optimization, stochastic optimization, and bilevel optimization) in order to bridge the gap between these fields from a theoretical and practical point of view.
Considering the different backgrounds of participants, we scheduled several talks with an introductory character in the first half of the week: Marc Goerigk and Frauke Liers gave overview talks on robust optimization, from a combinatorial and continuous perspective, respectively. Martine Labbé presented the state of the art of bilevel optimization, while Martin Schmidt combined both topics in his talk on bilevel optimization under uncertainty. Bernardo Pagnoncelli gave an introduction into the related topic of stochastic optimization. These presentations laid a common foundation for all further presentations and discussions and were thus a crucial prerequisite for the success of the seminar.
The contributed talks covered a wide range of topics, including complexity theoretic results for (certain or uncertain) bilevel optimization, new models and new methods for bilevel or robust optimization, and new approaches for solving bilevel or robust optimization problems arising in practice. Apart from the exciting contents of these talks, a particularly positive aspect was the large representation of young researchers. In fact, seven out of 18 contributed talks were given by PhD students.
The whole seminar was marked by a very open and constructive atmosphere and by an extraordinarily interactive approach: many presentations quickly turned into lively discussions involving many different participants, often making the original schedule obsolete, but with the benefit of a better common understanding and often new insights. One of the recurrent topics arising in many of these discussions was the connection between bilevel and robust optimization, the two main subjects of the seminar. The fact that both problem classes lead to potentially Σ2p-hard problems, as mentioned above, yields a connection of rather theoretical nature. From a more concrete point of view, the discussion was about whether one of the two problem classes can be seen (or modeled) as a special case of the other. Additionally, interesting links to game theory and stochastic optimization were identified.
Even though a conclusive answer to these questions could not be given (and probably does not exist), one of the main insights of the seminar was that bilevel and robust optimization, though being investigated in separate communities, share many structural and algorithmic properties. It is worth studying these connections and sharing the knowledge of both communities in order to profit from one another. The Dagstuhl Seminar on "Optimization at the Second Level" was a first significant step into this direction, which is hopefully followed by further progress.
The seminar was a big success, it stimulated new and very fruitful collaborations. We got laudatory feedback from many participants who were already thinking of organizing another seminar on a the same topic in the future.
In memoriam
At this point, our thoughts go out to our late colleague and friend Gerhard J. Woeginger. It was his idea to organize a seminar on "Optimization at the Second Level", and without him the seminar would never have become real. Unfortunately, he could no longer witness how his idea was put into practice and how fruitful it turned out to be.
References
- Gerhard J. Woeginger: “The trouble with the second quantifier”, 4OR – A Quarterly Journal of Operations Research, Vol. 19(2), pp. 157–181, 2021.
Creative Commons BY 4.0
Luce Brotcorne, Christoph Buchheim, and Dick den Hertog
The second level of the polynomial hierarchy contains a variety of problems that allow natural simple formulations with one existential and one universal quantifier. For instance, a typical problem in robust optimization asks whether there EXISTS some production plan that performs reasonably well under ALL possible price scenarios for electricity in the coming two years. A typical problem in bilevel optimization asks whether there EXISTS a way of setting taxes so that ALL possible behaviors of the citizens generate a reasonable tax revenue. A typical problem in Stackelberg games asks whether there EXISTS a starting move for the first player that wins the game against ALL possible counter-moves of the second player.
Problems of this type are usually complete for the class Σ2p and hence are most likely not contained in the class NP. For that reason, the methodologies that have been developed for NP-complete problems over the last 50 years do not directly apply to robust and/or bilevel optimization problems. Up to the current moment, most of the work on such problems is purely computational and without any deeper theoretical understanding. Most approaches simply try to carry over the well-developed machinery from integer programming to concrete robust problems and bilevel problems. We will need to develop new techniques, new tricks, new insights, new algorithms, and new theorems to get a grip on this area.
The goal of this Dagstuhl Seminar is to bring together experts in theoretical computer science and experts in combinatorial optimization, and we plan to work towards the following goals:
- summarize the status quo of robust optimization and bilevel optimization,
- identify central research lines on the computational and implementational front,
- identify central research lines in theoretical computer science, as for instance in parameterized complexity and approximability.
Luce Brotcorne, Christoph Buchheim, Dick den Hertog, and Gerhard J. Woeginger
- Yasmine Beck (Universität Trier, DE)
- Luce Brotcorne (INRIA Lille, FR)
- Christoph Buchheim (TU Dortmund, DE)
- Martina Cerulli (ESSEC Business School - Cergy Pontoise, FR)
- Claudia D'Ambrosio (CNRS & Ecole Polytechnique - Palaiseau) [dblp]
- Danique de Moor (University of Amsterdam, NL)
- Dick den Hertog (University of Amsterdam, NL)
- Boris Detienne (University of Bordeaux, FR)
- Gabriele Dragotto (Princeton University, US)
- Marc Goerigk (Universität Siegen, DE) [dblp]
- Dorothee Henke (TU Dortmund, DE)
- Felix Hommelsheim (Universität Bremen, DE) [dblp]
- Quentin Jacquet (EDF - Paris, FR)
- Jannis Kurtz (University of Amsterdam, NL)
- Martine Labbé (UL - Brussels, BE)
- Christina Liepold (TU München, DE)
- Frauke Liers (Universität Erlangen-Nürnberg, DE) [dblp]
- Ivana Ljubic (ESSEC Business School - Cergy Pontoise, FR)
- Ahmadreza Marandi (TU Eindhoven, NL)
- Komal Muluk (RWTH Aachen, DE)
- Bernardo Pagnoncelli (SKEMA Business School - Lille, FR)
- Jean Pauphilet (London Business School, GB)
- Michael Poss (University of Montpellier & CNRS, FR)
- Krzysztof Postek (TU Delft, NL)
- Ted Ralphs (Lehigh University - Bethlehem, US)
- Martin Schmidt (Universität Trier, DE)
- Juan Pablo Sepulveda Adriazola (INRIA Lille, FR)
- Shimrit Shtern (Technion - Haifa, IL)
- Nathalia Wolf (INRIA Lille, FR)
- Pawel Zielinski (Wroclaw University of Technology, PL)
Classification
- Computational Complexity
- Computer Science and Game Theory
- Data Structures and Algorithms
Keywords
- bilevel optimization
- robust optimization
- algorithmics
- computational complexity
