Un problème d'optimisation combinatoire (POC) consiste à rechercher une solution dans un ensemble discret (l'ensemble admissible) qui optimise une fonction (éventuellement multidimensionnelle). Les contributions de l'équipe peuvent être classées selon la spécification de l'ensemble admissible considérée. L'un des objectifs de l'équipe est d'étudier les propriétés structurelles des problèmes appartenant aux catégories ci-dessous afin de fournir, à terme, des outils efficaces pour les résoudre de manière optimale.

Problèmes d'ordonnancement

L'ensemble des solutions réalisables est un ensemble d'ordonnancements défini par une spécification ad hoc décrivant comment un ensemble de tâches peut être positionné dans le temps sous contraintes temporelles (précédences, dates de disponibilité, échéances) et, éventuellement, avec des ressources limitées. L'équipe considère différents contextes d'ordonnancement (ordonnancement de machines, ordonnancement de projets avec contraintes de ressources) et objectifs (durée totale d'exécution, retard maximal, équité, durée totale d'exécution). Elle propose des algorithmes de propagation des contraintes de ressources, des formulations MILP compactes et étendues, des métaheuristiques, ainsi que des études de complexité et des algorithmes de résolution dédiés. Une attention particulière est également portée aux problèmes d'ordonnancement robustes et multi-agents.

Quelques publications sur les problèmes d'ordonnancement

Allocation de ressources

L'ensemble des solutions admissibles correspond à l'affectation de ressources à des tâches, soit sans planification préalable, soit avec une planification déjà établie. L'objectif est de minimiser une fonction de coût d'affectation sous diverses contraintes. Cela inclut les problèmes d'affectation de fréquence, la planification des horaires des employés, la planification de la production, l'affectation d'énergie, les problèmes de type sac à dos, etc. L'équipe privilégie les approches de résolution basées sur les CSP et/ou les formulations MILP. Des méthodes hybrides sont également développées pour résoudre les problèmes complexes d'allocation et de planification intégrées des ressources.

Quelques publications sur les problèmes d'allocation des ressources

Problèmes de conception de réseaux et de tournées de véhicules

L'ensemble des itinéraires réalisables est constitué de trajets de véhicules respectant différentes contraintes de capacité, de longueur, de forme, de créneaux horaires, etc. Outre les objectifs classiques de temps et de distance, l'équipe considère d'autres objectifs, éventuellement dans un contexte multiobjectif, par exemple liés à la multimodalité, à l'équité ou à la consommation d'énergie. Des problèmes de conception de réseaux multi-commodités sont également étudiés. L'équipe étudie différentes approches : programmation linéaire en nombres entiers mixtes (MILP), techniques de séparation et d'évaluation des coûts, approches de Benders, méthodes de discrétisation dynamique et métaheuristiques.

Quelques publications sur les problèmes de routage des véhicules

Optimisation combinatoire en contexte d'incertitude

Dans la réalité, les paramètres des problèmes d'optimisation combinatoire sont sujets à incertitude. Bien qu'il existe de multiples façons de modéliser et de gérer cette incertitude, l'équipe s'est concentrée sur l'optimisation réactive (qui vise à coordonner la résolution itérative de problèmes déterministes par le biais d'horizons glissants ou de procédures de réparation) et l'optimisation robuste. Dans cette dernière, l'incertitude est modélisée par un ensemble de scénarios (chaque scénario correspondant à un ensemble fixe de paramètres) et une fonction objectif, prenant en compte le pire cas sur l'ensemble des scénarios, est utilisée pour évaluer un ensemble de décisions. L'équipe propose des méthodes de résolution pour les problèmes d'ordonnancement robustes, par exemple lorsque les durées de traitement des tâches ne sont connues que sous forme d'intervalles. Des approches stochastiques/robustes en deux étapes, basées sur des structures d'ordonnancement flexibles, sont également proposées.

Quelques publications sur l'optimisation combinatoire robuste