Nouvelles approches pour l'optimisation bi-niveaux linéaire // New Approaches for Linear Bilevel Optimization

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.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The topic is linear bilevel optimization, where a leader chooses decisions while anticipating the optimal response of a follower (who solves an optimization problem). Although the models are linear, the hierarchical structure induces a nonconvex feasible set and makes the problems computationally challenging (NP-hard).

The goal is to develop new algorithmic approaches beyond standard KKT-based single-level MILP reformulations, focusing on:
• strengthening relaxations (valid inequalities / cutting planes, linear overestimators of value functions);
• computing reliable and tight Big-M bounds, especially for follower dual variables, in a way that avoids application-specific tuning;
• designing decomposition methods for multi-follower variants, leveraging separability once the leader's decision is fixed.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2026

Contrat doctoral

Concours pour un contrat doctoral

Université de Montpellier

166 I2S - Information, Structures, Systèmes

optimisation convexe, optimisation en nombres entiers, optimisation bi-niveaux
convex optimization, integer programming, bilevel optimization