La Programmation Par Contraintes
Langage de Modélisation
Formalisme CSP
Un Problème de Satisfaction de Contraintes (CSP) est défini par un ensemble de variables, chacune munie d'un domaine de valeurs, et d'un ensemble de contraintes définissant les combinaisons de valeurs autorisées. Résoudre un CSP revient à affecter à chaque variable une valeur de son domaine, de sorte que les contraintes du modèle soient vérifiées. On parle de Programmation Par Contraintes (PPC), car le problème à résoudre est décrit de manière déclarative par l'ensemble de ses contraintes.
De la satisfaction à l'optimisation sous contraintes
Lorsque le problème possède, en plus des contraintes à satisfaire, une ou plusieurs fonctions à optimiser, on parle alors de Problème d'Optimisation sous Contraintes (COP). De tels critères peuvent émerger de considération économiques (minimiser le coût de la solution), organisationnelles (lisser au maximum la charge de travail), ou encore techniques (maximisation du respect des contraintes lorsqu'elles ne peuvent pas toutes être satisfaites. On parle alors de contraintes souples.). Si la littérature scientifique académique se focalise souvent sur les problèmes de satisfaction de contraintes, la quasi-totalité des problèmes industriels traités par Cosling sont des problèmes d'optimisation multi-objectifs.
Une approche déclarative
La PPC est un paradigme de programmation dit déclaratif : au lieu d'indiquer une procédure à suivre pour obtenir une solution, on se contente de spécifier les propriétés qui caractérisent la solution recherchée. Cette séparation nette entre les aspects fonctionnels et les aspects techniques va bien au dela de la programmation informatique, il s'agit d'une autre manière de penser qui facilite grandement les échanges avec le métier lors de projets industriels. En savoir plus.
"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."
[Eugene C. Freuder, Constraints, 1997]
Résolution du modèle
Mécanismes du solveur
Une fois le travail de modélisation effectué, un modèle de Programmation Par Contraintes peut être résolu par un solveur de contraintes générique, tel que Choco Solver. Les algorithmes de filtrage des contraintes vont éliminer les valeurs inconsistantes par déductions logiques tandis que les heuristiques de recherche du solveur vont explorer de manière intelligente l'espace de recherche résiduel, via un ensemble d'hypothèses réfutables. La résolution d'un CSP par un solveur de contraintes repose donc sur l'alternance de ces deux concepts fondamentaux, filtrage et exploration, jusqu'à obtenir une solution réalisable ou prouver qu'il n'en existe pas.
Optimisation des Temps de calcul
Les problèmes industriels étant souvent à la fois très complexes et de grande taille, le temps de calcul peut rapidement devenir un enjeu important. Pour augmenter les performances du solveur, il est parfois judicieux d'enrichir le modèle avec des composants avancés, comme une contraintes globales, une heuristique de recherche intégrant un savoir-faire métier ou encore de la recherche locale. Cette activité nécessitant une expertise en Programmation Par Contraintes et une bonne connaissance du solveur, faites appel à nos experts pour résoudre efficacement vos problèmes complexes!
