Cette page présente l'animation scientifique au sein de l'équipe ROC.

+

L'équipe ROC propose des modèles et des algorithmes variés pour plusieurs classes de problèmes d'optimisation combinatoire, comme les problèmes d'ordonnancement, de tournées de véhicules, d'allocation de ressources et plus généralement des problèmes combinatoires dans des graphes.

+

L'équipe ROC contribue à la résolution efficaces d'instances de problèmes d'optimisation combinatoires difficiles en concevant et implémentant des approches de programmation par contraintes, de programmation mixte en nombres entiers, des méthodes hybrides ainsi que des algorithmes dédiés. L'équipe propose des appriches d'intégration de techniques d'apprentissage automatique au sein des algorithmes d'optimisation et réciproquement l'amélioration des algorithmes d'apprentissage automatique grâce à l'optimisation combinatoire.

+

L'équipe cherche à confronter les méthodes proposées au monde réel en prenant en compte le génie industriel, les facteurs humains et/ou les enjeux environnementaux. Des applications industrielles sont développées dans des domaines variés qui incluent le transport, la production, la gestion de la chaine logistique, la gestion de l'énergie, l'aéronautique et l'espace.

+

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.

+

Au-delà de l’optimisation déterministe, l’équipe a obtenu des résultats en optimisation sous incertitude et en particulier en optimisation robuste en deux étapes, principalement pour des problèmes d’ordonnancement avec durées incertaines avec un critère minmax. Des méthodes de Benders adversariable et de génération de colonnes et de contraintes ont été conçues et appliquées avec succès pour la première fois à des problèmes d’ordonnancement cyclique et l’apport de la programmation par contraintes dans la méthode de Benders a été démontrée. En plus de ces apports algorithmiques, de nouvelles structures plus flexibles ont été proposées pour la représentation des décisions de la première étape (décisions dite « here-and-now ») : les séquences de groupes de tâches permutables permettent d’améliorer significativement les méthodes d’optimisation robuste et stochastique traditionnelles et une méthode qui exploite les arbres de décision robustes, une structure qui propose en première étape une famille d’ordonnancement, se compare favorablement aux approches réactives standard. Nous avons aussi montré l’intérêt de l’apprentissage par réseaux de neurones en graphes pour l’ordonnancement stochastique et, réciproquement, l’intérêt de l’optimisation robuste pour l’apprentissage automatique équitable. L’optimisation robuste par scénarios a été appliquée avec succès à la conception de microréseaux d’énergie Un autre axe d’étude porte sur l’optimisation des trajectoires pour des systèmes dynamiques soumis aux contraintes déterministes et stochastiques dont un exemple caractéristique est celui de la gestion du risque de collision, en orbite basse, des satellites avec des débris spatiaux. Il s'agit de problèmes d'optimisation sous contraintes probabilistes (Chance Constrained en anglais), dont la résolution requiert des algorithmes rapides et fiables, essentiels à la sécurité des missions. Sous certaines hypothèses simplificatrices, un problème de programmation quadratique non convexe, connu pour être NP-difficile, a été proposé. Des relaxations par programmation semi-définie (randomisation, hiérarchies de Lasserre) ainsi que des méthodes de type Branch & Bound ont été conçues et comparées en termes de performances sur des exemples académiques et réalistes. Une classe plus générale de rencontres à long terme a été étudiée via une approche par scénarios et une nouvelle méthode de relaxation directe, optimisant les manoeuvres d’évitement sous contraintes de probabilité cumulée de collision. Ces approches ont été comparées à une méthode de sélection du risque, plus conservatrice mais numériquement efficace grâce à sa convexité

+

L’équipe s’est intéressée à l’apprentissage automatique au travers des possibles relations et synergies avec l’optimisation combinatoire. Parmi celles-ci, une piste classique est l’apprentissage d’heuristiques d’exploration de l’arbre de recherche. Nous avons obtenu des résultats prometteurs en utilisant des modèles simples, appris par renforcement et en utilisant ces modèles dans le cadre de recherche arborescente de Monte-Carlo pour divers problèmes industriels. Nous avons également obtenu des résultats en utilisant des modèles plus complexes, tels que les réseaux neuronaux graphiques sur des problèmes industriels complexes, e.g., avec de nombreuses contraintes et niveaux de décision, et impliquant un aspect stochastique A contrario, l’optimisation combinatoire peut être un outil précieux pour l’apprentissage automatique, en particulier pour la synthèse de modèles d’apprentissage supervisé intrinsèquement interprétables tels que des modèles d’arbres de décision ou de règles de décision. Nous avons contribué à ce domaine selon plusieurs axes : Nous avons proposé deux algorithmes exacts pour le calcul d’arbres de décisions, Murtree et Blossom, tous deux disponibles en sources ouvertes, qui ont significativement amélioré l’état de l’art. Nous avons amélioré et généralisé les méthodes reposant sur la satisfiabilité booléenne et en particulier sur l’exploitation de solveurs MaxSAT pour les arbres et les diagrammes de décision. Et finalement, nous avons étudié l’hybridation de ces modèles interprétables avec des modèles complexes de type boîte noire. D’autre part, le corpus de modèles et méthodes issus de la RO et de la PPC nous ont permis de prendre en compte deux aspects importants dans le contexte de l’IA Responsable : Le premier de ces aspects est l’équité des modèles d’apprentissage. Nous avons proposé des méthodes pour la construction de modèles dépourvus de biais (selon certains critères statistiques connus), et en particulier une méthode pour éviter l'écueil connu dans ce domaine d’un gain en équité qui décroît ou disparaît sur les données inédites. Nous avons également montré qu’aucun critère d’équité ne peut respecter un ensemble d’axiomes simples, s’il ne se résume pas à ignorer les attributs sensibles. Le deuxième aspect concerne les enjeux de vie privée en apprentissage supervisé. Nous avons proposé des modèles d’attaque utilisant la programmation par contraintes pour reconstruire des jeux de données produits par différents modèles interprétables, et nous avons étudié comment évaluer la qualité des reconstructions de jeux de données produites par divers modèles interprétables.Nous avons aussi montré les tensions entre ces deux aspects, en particulier en montrant comment les informations sur l'équité des modèles peuvent être exploitées par un adversaire pour améliorer sa reconstruction des attributs sensibles des données d'apprentissage

+

L’étude de propriétés structurelles de ces problèmes et leur résolution efficace au coeur d’applications en industrie manufacturière, logistique, réseaux énergétiques, télécommunications et spatial ont fait l’objet de nombreux travaux. Des résultats de complexité sur des problèmes ouverts jusqu’à lors ont été produits. La mise en évidence de décompositions adaptées à la structure sous-jacente du problème en des sousproblèmes dont certains sont polynomiaux ou résolus efficacement ont permis de concevoir des algorithmes obtenant les meilleures solutions connues sur des jeux de données de la littérature. Au-delà des critères d’optimisation unique en ordonnancement et en logistique, des méthodes de décomposition mathématique adaptées aux problèmes de tournées de véhicules bi-objectif ont été proposées et des algorithmes d’ordonnancement multi-agent allient optimisation et théorie des jeux en proposant des équilibres de Nash optimaux. Sur le plan des applications, les méthodes proposées ont permis d’améliorer l’état de l’art dans beaucoup de domaines

+

Le développement de nouveaux résultats en calcul formel et arithmétique des ordinateurs en synergie avec la théorie de l’optimisation a permis d'améliorer la précision, la fiabilité et la rapidité de certaines classes d'algorithmes numériques, dont certains sont directement issus de problèmes concrets du domaine spatial. En particulier, nous nous sommes concentrés sur l’implémentation et l’évaluation efficaces et fiables, en précision fixe, de fonctions élémentaires et spéciales (telles que la probit, c'est-à-dire la fonction de répartition inverse de la loi normale standard), ainsi que d’autres routines numériques (comme la transformée de Fourier rapide ou l’arithmétique des quaternions). Un avantage clé de notre approche réside dans la combinaison des propriétés symboliques des fonctions D-finies (solutions d’équations différentielles linéaires à coefficients polynomiaux) avec des routines numériques performantes, issues de la théorie de l’approximation ou de l’optimisation. Cela a conduit au développement d'algorithmes efficaces pour l'évaluation de certaines intégrales. Dans ce cadre, la résolution validée (en donnant de bornes d'erreur effectives) de ces équations différentielles linéaires via des développements en séries de Taylor, Chebyshev a montré son efficacité sur le calcul de certaines intégrales abéliennes. En outre, nous avons aussi exploité le cadre plus général des fonctions D-finies multivariées pour résoudre un problème inverse impliquant des mesures à densités holonomes et un support à frontière algébrique réelle. Dans la même veine, les hiérarchies de Lasserre ont été également utilisées pour l'approximation du volume d'une union d'ensembles semi-algébriques modélisant la probabilité de collision pour les rencontres spatiales long terme. À l’inverse, les outils d’optimisation semi-infinie, initialement étudiés dans le cadre du contrôle optimal pour des problèmes d'optimisation de trajectoires spatiales, ont été adaptés pour répondre à une question théorique et pratique d’approximation en précision finie des implémentations numériques de fonctions élémentaires. Enfin, nous avons récemment utilisé les séries génératrices D-finies pour borner l’erreur d’arrondi d’un de nos algorithmes d’évaluation de la probabilité de collision orbitale, adopté et embarqué par le CNES lors d'une mission de test scientifique.

+