Thèse Nouvelles Approches pour l'Optimisation Bi-Niveaux Linéaire H/F - 34

Établissement : Université de Montpellier
École doctorale : I2S - Information, Structures, Systèmes
Laboratoire de recherche : Laboratoire d'Informatique, de Robotique et de Micro-électronique de Montpellier
Direction de la thèse : Michael POSS ORCID 0000000291452525
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-04T23:59:59

Le sujet porte sur l'optimisation bilevel linéaire, c'est-à-dire des problèmes où une décision de leader doit être prise en anticipant la réaction optimale d'un follower (qui résout lui-même un problème d'optimisation). Malgré une structure linéaire, l'interaction hiérarchique engendre une région faisable non convexe et des difficultés de calcul importantes (NP-dureté).

L'objectif est de proposer de nouvelles approches algorithmiques au-delà des reformulations classiques basées sur les conditions KKT et la résolution via MILP, en ciblant notamment :
-le renforcement des relaxations (coupes/inégalités valides, sur-approximations linéaires de fonctions valeur) ;
-le calcul de bornes Big-M fiables et suffisamment serrées (en particulier pour les variables duales du follower) sans réglages ad hoc par application ;
-des méthodes de décomposition adaptées aux variantes à multi-followers, où les reformulations monolithiques deviennent trop volumineuses.

L'optimisation bilevel apparaît naturellement dans les situations de décision hiérarchique (régulation, tarification, conception de réseaux, marchés de l'énergie, etc.). Le cadre formel relie deux niveaux d'optimisation : le leader optimise son objectif sous la contrainte que certaines variables correspondent à une solution optimale du follower.

Une approche standard consiste à remplacer le problème du follower par ses conditions d'optimalité (KKT) puis à obtenir une reformulation MILP. En pratique, trois points restent critiques :
1.Relaxations faibles : dans la relaxation linéaire, la cohérence leader follower optimal est mal capturée, ce qui dégrade fortement le branch-and-bound.
2.Choix des Big-M : des bornes trop grandes rendent la formulation inefficace ; des bornes trop petites la rendent incorrecte.
3.Scalabilité : avec plusieurs followers ou des structures plus riches, les formulations tout-en-un grossissent rapidement, d'où l'intérêt de la décomposition et de schémas plus structurés.