Programmation par contraintes  

Présentation

Située à la confluence de domaines tels que l’intelligence artificielle, la recherche opérationnelle ou encore le calcul symbolique, la programmation par contraintes (PPC) a connu son essor dans les années 80. Elle fournit un cadre de modélisation et de résolution des problèmes d’optimisation très souple basé sur des inconnues (les variables) reliées entre elles par des contraintes.

Principes généraux

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 (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.

Avantages

Une des grandes forces de la programmation par contraintes est la richesse qu’elle offre en termes de modélisation des problèmes d’optimisation. Contrairement à la programmation linéaire, l’expression des contraintes n’est pas limitée à des relations linéaires entre les variables, ce qui offre de grandes possibilités.
Un autre avantage de la programmation par contraintes est de permettre un pilotage fin de la résolution d’un problème d’optimisation, permettant de trouver rapidement une solution.

Limites

La programmation par contraintes est une méthode de recherche arborescente, qui énumère les différentes solutions du problème. Sur certains problèmes de grande taille, ce parcours d'arbre peut devenir très combinatoire et s’avérer très pénalisant en termes de temps de traitement.

Bien utilisée, la Programmation Par Contraintes permet cependant de trouver des solutions en des temps très raisonnables. Les deux principales limites restant :

• pas de garantie « théorique » sur les temps de recherche
• pas de garantie de trouver l’optimal, ni d’être en mesure de prouver qu’on l’a trouvé même si tel est le cas.

Quelques exemples de solveurs de programmation par contraintes :

• CP Optimizer (IBM/ILOG)
• OR Tools (Google)
• CHOCO (Ecole des Mines de Nantes)