Polyèdres et enveloppes convexes
Je m'intéresse à l'étude des polyèdres issus de problèmes d'optimisation combinatoire. Je cherche à décrire l'enveloppe convexe des solutions à l'aide d'un système d'inégalités linéaires. Ces inégalités peuvent alors être utilisées dans des algorithmes de résolution exacte pour améliorer les bornes et diminuer drastiquement les temps de résolution des problèmes.
Une question majeure est de savoir sous quelles conditions un système d'inégalités définit un polyèdre entier, c'est-à-dire un polyèdre dont tous les sommets sont des points ayant toutes leurs coordonnées entières. Cette propriété est cruciale car la recherche d'une meilleure solution entière vérifiant les inégalités du système se ramène alors à la résolution d'un problème linéaire en variables continues qui est polynomial (si les contraintes du système peuvent être séparées en temps polynomial). La propriété de (box-)total dual intégralité d'un système fournit généralement une condition suffisante pour qu'un système définisse un polyèdre entier. Mes recherches s'attachent à caractériser sous quelles conditions des systèmes sont (box-)total dual intégraux
Algorithmes de résolution efficaces
Je m'attache à développer des algorithmes pour la résolution de problèmes d'optimisation combinatoire de grande taille. L'efficacité de ces algorithmes repose notamment sur la formulation du problème. Il existe en effet une multitude de formulations d'optimisation linéaire en variables mixtes d'un même problème pour lesquelles l'efficacité des algorithmes diffèrent significativement.
Il existe également plusieurs algorithmes pour résoudre un même problème linéaire en variables mixtes. Je travaille sur l'ajout d'inégalités valides pour renforcer la relaxation linéaire afin d'obtenir des meilleurs bornes, diminuant ainsi l'espace des solutions à explorer. Je développe également des algorithmes basés sur la décomposition du problème en sous-problèmes qui sont liés entre eux par des contraintes linéaires.
Apprentissage automatique pour l'optimisation linéaire en variables mixtes
Je travaille sur l'utilisation de l'apprentissage automatique pour l'amélioration des solveurs exacts de problèmes linéaires en variables mixtes. Bien qu'exacts, ces algorithmes embarquent beaucoup d'algorithmes heuristiques (tels que les heuristiques primales pour trouver des solutions réalisables de bonne qualité) dont l'efficacité impacte grandement celle de l'algorithme exact. L'idée est d'utiliser l'apprentissage automatique pour spécialiser ces heuristiques pour des problèmes spécifiques à partir des données issues de la résolution d'instances du même type.
Mes travaux portent notamment sur la prédiction de solutions duales pour la relaxation Lagrangienne permettant d'obtenir des bornes duales et ainsi d'accélerer la résolution de problèmes linéaires en variables mixtes.
