A la frontière entre programmation mathématique et intelligence artificielle, la programmation par contraintes se démarque par son paradigme et sa polyvalence. L’approche est basée sur la réduction du domaine de décisions par la propagation des contraintes dans un arbre de branchement.
L’efficacité de la programmation par contraintes se révèle pour des problèmes de décision dans lesquels il y a beaucoup d’interaction forte entre les différentes décisions. Elle est également très utilisée pour résoudre des sous-problèmes d’autres méthodes de recherche opérationnelle.
Chaque variable peut prendre un certain nombre de valeurs qui constituent son domaine. Les contraintes créent des relations entre les variables et limitent donc leurs domaines. La programmation par contraintes résout les problèmes d’optimisation en s’appuyant sur deux techniques qu’elle combine entre elles :
- La sélection et l’instanciation de variables : il s’agit de choisir la prochaine variable à prendre en compte et la valeur qui va lui être affectée dans son domaine
- La propagation de contraintes : elle consiste à répercuter sur le domaine des autres variables le choix qui a été effectué lors de l’étape précédente.
Si le domaine d’une variable est vide suite à l’étape de propagation de contraintes, le choix effectué lors de l’étape précédente de sélection et d’instanciation de variables est remis en cause. Sinon le processus continue. Le traitement s’arrête s’il est possible d’affecter une valeur à toutes les variables du problème (on a alors une solution) ou si aucune solution ne peut être trouvée (le problème est alors infaisable).
La puissance (autrement dit la capacité à traiter des problèmes « industriels ») de la propagation par contraintes passe notamment par le soin apporté à la recherche de solution :
- il est possible d’introduire la connaissance métier que l’on a du problème lors de l’étape de sélection et d’instanciation de variables pour accélérer l’obtention d’une solution
- mais les stratégies de recherche ne sont pas toujours basées sur une expérience « métier », car il n‘est pas toujours opportun de transposer les pratiques acquises à l’occasion d’une résolution « manuelle » ou basée sur d’autres techniques, il faut alors s’appuyer sur l’expertise en modélisation pour développer des stratégies spécifiques faisant appel à la résolution de sous problèmes. C’est dans ce contexte que…
- …la propagation de contraintes peut être associée avec bonheur à d’autres techniques qu’un parcours d’arbre
- tabou, recuit simulé
- programmation linéaire, encore appelée optimisation linéaire (ce qui permet de propager des contraintes non linéaires couplées à un système d’équations linéaires).
L’efficacité de la propagation est vitale car c’est elle qui « casse » la combinatoire. Elle est conditionnée par la qualité de la modélisation et la puissance de représentation des outils utilisés. On peut appliquer une méthodologie consistant, par itérations, à analyser finement le comportement d’une recherche (en disséquant les tenants et aboutissants des « mauvaises décisions » pénalisantes) pour en déduire une amélioration :
- de la complétude de la propagation
- des critères de pilotage de la recherche.
Les experts en mathématiques décisionnelles d’EURODECISION utilisent régulièrement la programmation par contraintes dans leurs missions chez les clients.