WORKSHOP
Optimization at the second level
Optimisation au second niveau
2 – 5 April, 2024
Organizing Committee
Comité d’organisation
Ivana Ljubić (ESSEC Business School Paris)
Michaël Poss (CNRS, LIRMM Université de Montpellier)
Martin Schmidt (Trier University)
Shimrit Shtern (Technion – Israel Institut of Technology)
The second level of the polynomial hierarchy contains a variety of optimization problems that can be naturally formulated with one existential and one universal quantifier. A typical example in robust optimization would ask whether there EXISTS some production plan that performs reasonably well under ALL possible price scenarios for electricity in the coming two years. Similarly, in bilevel optimization, a typical problem would ask whether there EXISTS a way of setting taxes so that ALL optimal behaviors of the citizens generate reasonable tax revenue.
Problems of this type are particularly difficult to solve from the point of view of mathematical optimization, requiring advanced tools based on decomposition algorithms, convex optimization, and combinatorial optimization. From the point of view of complexity theory, many of these problems are complete for the class Σ2p and 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.
While there has been some progress for purely convex problems, integer recourse (robust optimization) and integer follower problems (bilevel optimization) are still badly understood, yielding to the need to develop new techniques, tricks, insights, and algorithms to get a better grip on these problems.
The goal of this workshop is to bring together experts in combinatorial optimization, integer programming, and convex optimization, and we plan to work towards the following goals:
* summarizing the status quo of robust optimization and bilevel optimization;
* creating innovative connections between robust and bilevel optimization, helping the transfer of algorithms and reductions from one type of problems to the other;
* identifying central research lines for computational and implementational aspects as well as in complexity theory.
Le deuxième niveau de la hiérarchie polynomiale contient une variété de problèmes d’optimisation qui peuvent être naturellement formulés avec un quantificateur existentiel et un quantificateur universel. Un exemple typique de problème d’optimisation robuste demande s’il EXISTE un plan de production qui fonctionne bien dans TOUS les scénarios de prix possibles pour l’électricité au cours des deux prochaines années. De même, en l’optimisation bi-niveaux, un problème typique demande s’il EXISTE un moyen de fixer les impôts de sorte que TOUS les comportements optimaux des citoyens génèrent des recettes fiscales raisonnables.
Les problèmes de ce type sont particulièrement difficiles à résoudre du point de vue de l’optimisation mathématique, nécessitant des outils avancés basés sur les algorithmes de décomposition, l’optimisation convexe et l’optimisation combinatoire. Du point de vue de la théorie de la complexité, beaucoup de ces problèmes sont complets pour la classe Σ2p et ne sont probablement pas contenus dans la classe NP. Pour cette raison, les méthodologies qui ont été développées pour les problèmes NP-complets au cours des 50 dernières années ne s’appliquent pas
directement aux problèmes d’optimisation robustes et/ou à deux niveaux.
Bien qu’il y ait eu des progrès notables pour les problèmes purement convexes, les problèmes avec recours entier (optimisation robuste) et de second niveau entier (optimisation à bi-niveaux) sont encore mal compris, nécessitant le développement de nouvelles techniques et de nouveaux algorithmes pour obtenir une meilleure compréhension de ces problèmes.
Le but de cet atelier est de réunir des experts en optimisation combinatoire, programmation en nombres entiers et optimisation convexe, afin de travailler sur les objectifs suivants :
* résumer le statu quo en l’optimisation robuste et en l’optimisation à deux niveaux ;
* créer des connexions innovantes entre l’optimisation robuste et l’optimisation bi-niveaux, en se basant sur le transfert d’algorithmes et les réductions d’un type de problèmes à l’autre;
* identifier des lignes de recherche fondamentales pour les aspects numériques ainsi que ceux liés à la théorie de la complexité.
TUTORIALS
Ayse Nur Arslan (INRIA Université de Bordeaux) Decision rules for robust adjustable optimization
Luce Brotcorne (INRIA Université de Lille) Bilevel optimization for energy problems
Margarida Carvalho (Université de Montréal) Integer programming games: A standard optimization toolbox perspective
Jannis Kurtz (University of Amsterdam) Deep Learning in Robust and Bilevel Optimization