Représentation et traitement pratique de la flexibilité dans les problèmes sous contraintes
Abstract
En premier lieu, après un rapide rappel des principales définitions relatives aux CSP, nous donnons une description des applications nécessitant ou ayant nécessité une extension du formalisme classique. Différentes origines de la flexibilité sont ensuite recensées en s'appuyant sur ces applications ; on distingue principalement les causes suivantes : existence de préférences, nature imprécise et incertaine des connaissances, complexité d'un problème nécessitant une hiérarchisation et évolution dans le temps. Afin d'illustrer ces formes de flexibilité, nous présentons un problème typique d'emploi du temps. Nous abordons ensuite le problème du traitement de la flexibilité. Pour chacune des origines, nous discutons des énoncés de problèmes sous-jacents et des différentes approches envisageables. La conclusion donne une synthèse des besoins soulevés. Une série d'annexes est consacrée à la résolution de CSP flexibles. Après un rapide état de l'art, nous présentons les travaux réalisés par les membres du projet constituant des éléments de réponse pour le traitement de certains cas de flexibilité.