Doctorat (H/F) - Résoudre les problèmes de programmation mixte en nombres entiers non linéaires (MINLP)

Sujet de thèse :
Objectifs : Les méthodes classiques pour résoudre les problèmes de programmation non linéaires en nombres entiers (MINLP) reposent souvent sur la résolution de relaxations continues ou linéaires/convexes. Ces approches s’appuient sur le fait que leur région réalisable est plus grande que celle du problème original, de sorte que la fonction objectif sous-estime celle du problème initial (dans le cas de problèmes de minimisation). Le sujet de thèse consiste à proposer des méthodes alternatives basées sur des approximations, c’est-à-dire des reformulations du problème qui, en général, ne préservent pas cette propriété. L’objectif est de développer de nouvelles formulations approchées pour des classes de MINLP, qui, sous certaines conditions, présentent d’autres propriétés intéressantes, par exemple :
- des approximations (ou relaxations) linéaires par morceaux classiques,
- des projections aléatoires de problèmes d’optimisation mathématique,
- des approximations à base de "splines" (peu explorées en optimisation mais utilisées en statistiques),
- des enveloppes convexes inexactes,
- ou encore des approximations univariées en dimensions supérieures.
Le défi sera de trouver un bon compromis entre la qualité de l’approximation et l’efficacité des méthodes de résolution, en combinant des approximations/relaxations classiques et non conventionnelles. Les nouvelles méthodes seront appliquées à des applications réelles, telles que :
- le *lux de puissance optimal en courant alternatif (ACOPF),
- le problème de commutation optimale de transmission (OTS),
- ou encore le problème d’engagement des unités hydrauliques (HUC).

Résultats attendus :
- Étudier de nouvelles approximations pour les problèmes de programmation mixte en nombres entiers non linéaires.
- Concevoir des méthodes pour résoudre ces approximations.
- Démontrer certaines propriétés des approximations, comme :
- une borne supérieure sur l’erreur introduite par l’approximation,
- ou le fait que, pour certaines classes de MINLP, certaines approximations constituent des relaxations.
- Appliquer les nouvelles méthodes à des applications réelles marquantes.

Séjours prévus :
- 3 mois au CNR (avec C. Gentile) pendant la 2ᵉ année pour étudier le renforcement de formulations.
- 3 mois chez EDF (avec W. van Ackooij)*pendant la 3ᵉ année pour travailler sur l’engagement des unités de production (Unit Commitment) et y appliquer les techniques développées.
Contexte :
Le Laboratoire d'Informatique de l'X (LIX) est une unité mixte de recherche (UMR 7161) associée au CNRS et à l'École Polytechnique. Ses activités de recherche couvrent un large spectre de l'informatique fondamentale et appliquée, avec une forte interdisciplinarité. Parmi les autres, on retrouve de la recherche à la pointe sur les sujets suivants : algorithmes et complexité ; optimisation mathématique ; intelligence artificielle et apprentissage automatique ; bioinformatiq
Voir plus sur le site emploi.cnrs.fr...