Et si, au lieu de dire à l’ordinateur comment résoudre un problème, on lui disait simplement ce qu’on veut — et le laissait se débrouiller ? C’est le principe de la programmation par contraintes : un paradigme où l’on décrit les règles du jeu, et où la machine explore toutes les possibilités pour trouver une solution qui les respecte.

Que ce soit pour planifier un emploi du temps, résoudre un sudoku, organiser des livraisons ou affecter des ressources, la programmation par contraintes permet de modéliser des problèmes complexes sans écrire une seule ligne d’algorithme. Elle repose sur la logique et les mathématiques.

Qu’est-ce que la programmation par contraintes ?

La programmation par contraintes est un paradigme où l’ont décrit un problème sous forme de contraintes logiques, et le système, via un solveur, cherche à les satisfaire toutes. C’est-à-dire qu’au lieu de décrire comment l’ordinateur doit résoudre notre problème, on va simplement décrire notre problème : on va le modéliser. Pour modéliser le problème, la programmation par contraintes met à disposition des développeurs 2 choses : des variables (associées à un domaine) et des contraintes. Le développeur n’a ensuite qu’à décrire les contraintes qu’il souhaite utiliser.

Par exemple un Sudoku : le développeur va simplement indiquer qu’il souhaite 9x9=81 variables pouvant prendre une valeur entière entre 1 et 9 compris. Ensuite, il va poster des contraintes comme quoi toutes les variables d’une même ligne doivent avoir une valeur différente, idem pour les variables d’une même colonne et d’un même carré. Enfin, en fonction de la grille, certaines variables auront leur valeur de fixée. C’est tout, c’est ensuite le solveur qui va essayer chaque valeur du domaine pour chaque variable et donner la solution.

Ainsi, les problèmes que peuvent résoudre la programmation par contraintes sont des problèmes de décision, c’est-à-dire pour savoir s’il existe une solution au problème, ainsi que les problèmes d’optimisation, c’est-à-dire pour savoir quelles sont les meilleures solutions, si elles existent.

Comment ça marche ?

La résolution d’un problème de programmation par contraintes s’effectue par un programme appelé un solveur. C’est lui qui définit la bibliothèque des contraintes utilisables, et c’est lui qui résolve le problème.

Une contrainte peut être de type arithmétique ou logique. Par exemple on peut poster la contrainte que la variable X doit être égale à la valeur de Y plus 2 : X = Y+2 (contrainte arithmétique), ou alors dire que 9 variables doivent être toutes différentes, comme dans l’exemple du Sudoku (contrainte logique).

La résolution s’effectue en deux temps : le premier temps est la propagation, le deuxième est l’énumération.

La propagation de contraintes permet de réduire le domaine de chaque variable en fonction des contraintes. Par exemple au Sudoku, si j’ai la valeur 1 et 4 déjà fixée dans une ligne, on peut supprimer les valeurs 1 et 4 des domaines des autres variables de la ligne.

L’énumération est l’étape où, ne pouvant plus propager de contrainte, on prend une variable et on fixe sa valeur parmi une valeur de son domaine, et ensuite on reprend une étape de propagation puis d’énumération. Si une inconsistance apparaît, c’est-à-dire si une contrainte est violée, autrement dit si la solution en cours de calcul n’est pas possible, alors on revient à la dernière étape d’énumération et on retire la valeur du domaine de la variable : apparemment, avec cette valeur, ça ne fonctionnait pas. Une bonne modélisation d’un problème est une modélisation qui entraîne le plus de propagations possible afin d’éviter à avoir à faire ces retours arrières.

Il y a donc, pour un problème donné, plusieurs stratégies de résolution qui peuvent être appliquées, notamment sur le choix de la variable qui va être affectée, et sur la valeur choisie.

Raisonner avec des contraintes

Plus les problèmes sont complexes, plus il est compliqué de les modéliser. Une modélisation complexe peut entraîner un temps de résolution augmenté.

La programmation logique permet de faire du raisonnement, et de « découvrir » de nouvelles connaissances à partir des connaissances présentes grâce à des règles. Le principe d’une règle logique est simple : si des conditions sont respectées, alors de nouvelles contraintes vont être postées.

Par exemple, lorsqu’on souhaite faire un emploi du temps scolaire, nous avons des variables pour définir la salle dans laquelle le cours aura lieu. On définit une contrainte pour dire qu’une salle doit pouvoir accueillir tous les élèves. On pourrait définir une contrainte pour toutes les combinaisons de cours-salles possible, sinon on peut utiliser une règle qui va poster la contrainte uniquement pour les cours et les salles concernés. Dès lors qu’on va affecter une salle à un cours, la contrainte de capacité de la salle sera postée pour le cours.

Travaux en cours

Nous travaillons actuellement au Laboratoire d’Études et de Recherches en Informatique d’Angers (LERIA) à un solveur qui serait à la croisée de la programmation par contraintes et la programmation logique. Ce solveur serait plus particulièrement axé sur la résolution de contraintes arithmétiques.

Une ébauche de ce solveur a été réalisée et les travaux seront bientôt présentés dans une conférence nationale sur la programmation par contraintes.