Rarement identifiés par les industriels, les problèmes d'optimisation combinatoire sont cependant très nombreux dans la vie quotidienne des entreprises. Un chercheur de l'Unité mixte de recherche "Heuristique et diagnostic des systèmes complexes" (HeuDiaSyC)¹, Philippe Baptiste, s'est penché sur des problèmes d'optimisation combinatoire et d'ordonnancement. La dimension théorique (théorie de la complexité) et la dimension appliquée (résolution de problèmes pratiques, programmation par contraintes) de ses travaux sont complémentaires.

Étant donné une flotte de véhicules, un ensemble de conducteurs et des trajets à effectuer, comment répartir les véhicules et les trajets entre les conducteurs en respectant des contraintes temporelles (fenêtres de temps) et des contraintes légales (temps maximal de conduite) ? Comment ordonnancer des tâches soumises à des contraintes de "précédence" et à des contraintes de ressources (par exemple, au plus dix personnes pouvant travailler simultanément sur un même ensemble de tâches) ? Comment construire l'emploi du temps d'un lycée pour satisfaire "au mieux" les contraintes des élèves et des professeurs ? Ce sont autant de questions auxquelles tentent de répondre les chercheurs opérationnels. Leur but : proposer une résolution pratique de telles problématiques.

La théorie de la complexité a, depuis longtemps, permis d'identifier une classe de problèmes "difficiles" pour lesquels on conjecture qu'il n'existe pas de méthode de résolution efficace. Il est très important de déterminer si un problème rentre ou non dans ce cas de figure. Malheureusement, il s'avère que la plupart des problèmes réels sont "difficiles". Un arsenal de techniques est utilisé pour les résoudre, malgré tout, en un temps raisonnable. Les méthodes exactes s'attachent à calculer la meilleure de toutes les solutions. Les méthodes approchées comme le recuit simulé² ou les algorithmes génétiques³ se contentent d'une solution recevable sans pour autant garantir qu'elle est la meilleure.

Du fait de l'énorme complexité des problèmes combinatoires, les méthodes exactes sont souvent limitées à des instances de petite taille. Cependant, une méthode efficace de résolution exacte peut s'intégrer de manière pertinente au sein d'une méthode plus générale de résolution approchée. Celles-ci conservent donc un intérêt pratique considérable. L'originalité de l'approche menée au Laboratoire HeuDiaSyC est de combiner des techniques classiques de recherche opérationnelle avec des outils extrêmement flexibles venant du monde de l'intelligence artificielle comme la programmation par contraintes. Il est alors possible de créer des outils d'optimisation à la fois très efficaces et facilement utilisables par des industriels qui ne sont pas obligatoirement des spécialistes de l'optimisation combinatoire. En pratique, des problèmes de gestion de projet ont été résolus avec succès pour plusieurs industriels. D'autre part, d'excellents résultats ont été obtenus sur des problèmes "tests" qui préoccupent l'ensemble de la communauté scientifique.

¹ CNRS-Université de technologie de Compiègne.

² Technique qui s'inspire d'un mécanisme naturel observé dans les aciéries : lors du refroidissement d'une pièce, les atomes de la matière s'organisent de façon optimale. En mimant ce mécanisme, on espère trouver une bonne solution à un problème d'optimisation.

³ Les solutions sont représentées par des "gènes" et en simulant un mécanisme de reproduction et de croisement de ces gènes, on espère trouver un individu avec de "très bons gènes", i.e., une très bonne solution.