Qu'est ce qu'un problème combinatoire ?
L’analyse combinatoire est rattachée aux mathématiques et ́etudie les collections (souvent finies) d’objets qui respectent certaines propriétés. Dénombrer toutes ces collections ou exhiber la meilleure collection parmi toutes celles possibles, sont des questions combinatoires. Euler, par exemple, pose la question suivante en 1779 : en considérant 6 régiments de 6 officiers de rangs distincts, est-il possible de placer les 36 officiers dans un carré de 6 par 6 de telle sorte qu’il n’y ait pas deux officiers de même rang ou de même régiment dans chaque ligne et colonne ? Le problème est simple à exprimer (sa compréhension ne demande aucune connaissance scientifique particulière) comme le célèbre jeu du Sudoku, et sa difficulté vient du trop grand nombre de combinaisons à évaluer pour pouvoir déterminer la bonne. Il s’agit de limiter autant que possible cette explosion combinatoire, mais même les problèmes les plus simples sont au-delà des capacités humaines. L’ordinateur est donc un outil indispensable de la résolution, au moins depuis 1953 si on en croit Kuhn [Sch05], l’inventeur de la m ́ethode hongroise pour le problème d’affectation. Les jeux et puzzles logiques sont affaires de mathématiciens comme Gauss et Euler, l’optimisation combinatoire a des vues bien plus larges et s’appuie sur les développements des technologies informatiques. Si son histoire proprement dite semble remonter aux années 50, on peut retrouver son origine très loin dans le passé car elle prend racine dans des problèmes qui ne sont pas la seule préoccupation du mathématicien. Ces problèmes historiques, tels que le problème d’affectation, de flot maximal, de voyageur de commerce, ou d’arbres couvrants de poids minimal, ont été abordés et résolus de manière indépendante et différente dans l’histoire car ils sont au cœur de questions pratiques que nos sociétés rencontrent. Transporter des biens, établir des réseaux, planifier des activités sont autant de problématiques qui exigent aujourd’hui de bonnes réponses car elles se posent à des échelles mondiales. La gestion et l’amélioration de ces situations complexes et réelles sont le propre de la Recherche Opérationnelle. La Programmation Par Contraintes (PPC) s’inscrit dans ce cadre. C’est un paradigme de résolution sur lequel des outils génériques, des solveurs, ont été concus pour permettre à des non-spécialistes d’aborder ces problèmes combinatoires. Aujourd’hui, la volonté de construire des outils informatiques capables de résoudre de manière efficace de larges classes de problèmes est de plus en plus forte. Ces outils s’appuient toujours davantage sur des interfaces déclaratives avec lesquelles un utilisateur décrit son problème, sans indiquer la manière de le r ́esoudre. La programmation par contraintes et la programmation linéaire entrent dans ces catégories et touchent ici au domaine de l’intelligence artificielle selon les mots d’Eugene Freuder :
"Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming : the user states the problem, the computer solves it."
[Sch05] A. Schrijver. Handbook of Discrete Optimization, chapter On the history of combinatorial optimization (till 1960), pages 1–68. Elsevier, Amsterdam, 2005.