Méthodes avancées pour l’optimisation discrète

Un objectif central de l’équipe ROC est de participer au développement de méthodes génériques, dont l’impact n’est pas nécessairement lié à un projet applicatif précis, mais se situe plus en amont. Ces recherches sont souvent imbriquées avec les applications et les deux aspects se nourrissent mutuellement. Dans divers contextes d'ordonnancement en ateliers flexibles, nous proposons une approche de décomposition de Benders basée sur la logique (LBBD). L’équipe ROC s’intéresse aussi à la résolution de problèmes mathématiques résultant de l’introduction de termes non linéaires dans des modèles qui relèvent de l’optimisation combinatoire. Dans le cas des fonctions de deux variables continues définies sur un domaine polygonal, nous identifié des propriétés d’approximation nous permettant de développer des méthodes de calcul de solutions réalisables surpassant l’état de l’art en termes de qualité de solutions. Dans le domaine de la PPC, l’équipe s’intéresse au développement de solveurs génériques. Au cours de la période, le travail sur le solveur Mistral a été poursuivi, avec des prix dans les compétitions internationales. Un axe important de ces recherches sur les méthodes de résolution porte sur l’adaptation de l’ « apprentissage de clause » utilisée en satisfiabilité booléenne notamment, à des problèmes plus structurés. Nous avons démontré l’efficacité de ces méthodes en particulier pour les problèmes de coloration de graphe, pour lesquels nous avons proposé un modèle original adapté aux graphes de très grande taille qui permis de calculer (et prouver) le nombre chromatique de réseaux ayant plusieurs centaines de milliers de sommets.

---