Programmation par contraintes

La programmation par contraintes est un paradigme de programmation qui distingue d'une part le problème à traiter, formalisé sous forme d'un ensemble de variables prises dans un domaine et d'un ensemble de contraintes, et d'autre part la méthode de résolution, qui propage les contraintes sur les variables pendant l'exploration de l'espace des solutions candidates, de façon à réduire les domaines associés aux variables.

Cette méthode permet de résoudre des problèmes combinatoires de grande taille. Elle est particulièrement bien adaptée aux problèmes de planification et d'ordonnancement.

Selon les problèmes, l'objectif pourra être :

Application à la gestion du trafic aérien

Le domaine ATM comporte de nombreux problèmes de planification ou d'ordonnancement. En voici quelques exemples :

Travaux menés au MAIAA

Notre activité de recherche autour de la programmation par contraintes porte principalement sur la modélisation des problèmes de trafic aérien, et la définition d'heuristiques efficaces adaptée à ces problèmes.

FaCiLe: une librairie de PPC en Ocaml

Nous avons développé une librairie de programmation par contraintes pour des domaines entiers de dimension finie. Cette librairie offre toutes les possibilités usuelles de créer et manipuler des domaines finis de variables, des espressions arithmétiques et des contraintes, y compris non-linéaires.

Programmée en langage fonctionnel Ocaml, FaCiLe permet à l'utilisateur de spécifier facilement les variables, les domaines, les contraintes et les objectifs, à travers des primitives de haut-niveau.

Le code est disponible sous forme de paquet Debian (libfacile-ocaml-dev). Par défaut, l'installation se fait dans le répertoire /usr/lib/ocaml/facile/)

Voir également la documentation en ligne.