Programmation par contraintes

Programmation par contraintes

 Principes généraux

La programmation par contraintes (PPC) est un paradigme de programmation déclarative, désignant à la fois un formalisme pour la définition de CSPs (Constraint Satisfaction Problems) et un ensemble de méthodes pour les résoudre. La donnée d’un CSP consiste en l’énumération de relations logiques (ou contraintes) portant sur les variables du problème. Le problème est résolu dès que l’on découvre une configuration dite consistante, c’est-à-dire un ensemble de valeurs telles que toutes les relations logiques entre les variables du problème soit vérifiées.

S’il n’existe aucune configuration consistante, le problème est dit surcontraint. La formulation d’un problème de satisfaction de contraintes est donné par un ensemble de variables V1,…,VN à valeurs dans des domaines D1,…,DN (finis ou infinis), ainsi que d’un 69 70 CHAPITRE 6. PROGRAMMATION PAR CONTRAINTES jeu de contraintes (ou réseau de contraintes) C1,…,Cp, fonctions booléennes sur ( Di)i∈I, où I est un sous-ensemble de {1,…,N}. On parle de contrainte unaire (ou de filtre) si I est un singleton, de contrainte binaire si I est un couple, de contrainte N-aire sinon.

De façon générale, une contrainte représente une information partielle sur les valeurs que peuvent prendre les variables d’un problème donné. La programmation par contraintes propose des méthodes de résolution basées sur la manipulation et la propagation de ces informations partielles au cours du calcul. Lorsqu’on « avance » dans la résolution, les incertitudes sur les valeurs autorisées pour les variables sont peu à peu levées, et une configuration consistante est alors synonyme d’information totale.

En pratique, de nombreux domaines d’application se prêtent à la programmation par contraintes, en raison notamment du fort pouvoir expressif de ce paradigme. De la mise en page des documents multimédia aux problèmes de planification, d’ordonnancement, de gestion de ressources ou d’emplois du temps, les contraintes ont été employées avec succès dans des situations complexes, difficiles à formaliser autrement que par un ensemble de conditions logiques sur les variables. Le lecteur désirant approfondir ses connaissances sur la programmtion par contraintes pourra consulter les ouvrages de Tsang [Tsa93] ou Mariott & Stuckey [MS98]. 

Contraintes et informatique musicale

La programmation par contraintes entretient depuis une vingtaine d’années des liens étroits avec l’informatique musicale1, et en particulier la composition assistée par ordinateur, en raison de la facilité avec laquelle la musique symbolique se prête à une formalisation sous forme de règles. L’utilisation de contraintes en CAO commence à la fin des années 80 avec des problèmes d’harmonisation automatique de mélodies.

Avec son système Choral conçu pour l’harmonisation de chorals à quatre voix dans le style de Jean-Sébastien Bach, Kemal Ebcioglu [Ebc88] fut le précurseur d’un champ de recherche à part entière (pour état de l’art complet du domaine, voir la revue de Pachet & Roy [PR01]). A un niveau plus général, le moteur PWConstraints de Mikaël Laurson [Lau93] permet de définir des contraintes sur des séquences dans l’environnement de CAO PatchWork [LD89].

Plus tard, Rueda & Bonnet [RLBA98] ont développé dans PatchWork la bibliothèque Si tuation, dans laquelle les structures musicales sont représentées sous forme d’objets bi-dimen sionnels, permettant de prendre en compte contraintes harmoniques et contraintes temporelles au sein d’une même représentation. Situation est aujourd’hui intégré dans l’environnement OpenMusic [Ago98]. Enfin les travaux de Charlotte Truchet [Tru04] au sein de l’équipe Représentations musicales de l’Ircam ont débouché sur la création dans OpenMusic de la bibliothèque OMClouds.

Cette dernière tire parti du paradigme de programmation visuelle d’OpenMusic pour établir une correspondance entre un graphe de contraintes et la repré sentation visuelle d’un programme. L’originalité d’OMClouds est de proposer une collection d’opérateurs et de fonctions suffisamment génériques pour formaliser un grand nombre de problèmes musicaux

Méthodes complètes de résolution

A l’instar de l’optimisation multicritère (voir chapitre 5), les méthodes de résolution en programmation par contraintes se distinguent en deux catégories : • les méthodes complètes, qui garantissent la découverte d’une configuration consistante si le problème n’est pas surcontraint, mais au prix d’un temps de calcul souvent très long; • les métaheuristiques, qui permettent de trouver rapidement une solution dont la consis tance peut être seulement partielle (i.e. toutes les contraintes ne sont pas satisfaites). Elle feront l’objet du paragraphe suivant.

Recherche systématique

Les méthodes de recherche systématique utilisent une représentation arborescente de l’es pace de recherche. Chaque nœud correspond à l’instanciation d’une variable et chaque feuille représente une configuration. L’idée la plus simple pour résoudre un problème de satisfac tion de contraintes consiste à parcourir l’arbre de recherche en profondeur jusqu’à l’obtention d’une configuration consistante : c’est la méthode dite generate-and-test.

Une telle procédure est évidemment totalement inefficace en pratique, en raison du caractère NP de la plupart des problèmes. L’alternative la plus courante est le backtracking, exploitant la notion d’« instanciation partielle ». Dans la plupart de problèmes, chaque contrainte est d’arité faible : elle n’implique qu’un nombre réduit de variables3. Il n’est donc pas nécessaire de connaître les valeurs de toutes les variables pour savoir si la contrainte est violée ou non.