Dagstuhl Seminar 22441
Optimization at the Second Level
( Oct 30 – Nov 04, 2022 )
Permalink
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)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
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.

- 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