L'exposé commencera par une introduction à la programmation par contraintes, accessible aux personnes ne connaissant pas ce domaine. Plusieurs types d'applications, provenant essentiellement des domaines de la planification et de l'ordonnancement, seront presentées en exemples. L'exposé se terminera par une ouverture sur divers sujets de recherche et notamment les méthodes hybrides.

L'application prétexte à notre exposé s'inscrit dans le cadre du dimensionnement des centres d'appels d'un opérateur téléphonique mobile, et de la gestion des emplois du temps de ses milliers de conseillers. Répartis sur une demi-douzaine de sites sur le territoire français, les conseillers de clientèle doivent assurer une couverture de la charge d'appels par type d'activité. Le dimensionnement des centres pose une succession de problèmes enchevêtrés aux équipes de planification, citons :

La planification s'effectue par périodes de 13, 26 ou 52 semaines, pour des sites d'environ 500 personnes, chacune ayant un objectif personnel de quantité de travail pour la période. Il s'agit donc de construire 500 séquences de semaines, telles qu'individuellement les quantités de travail et les contraintes de jours de congé soient respectées et que globalement les courbes de charges soient proches de la demande estimée. Après avoir insisté sur la structure de flot sous-jacente, nous en évoquerons les limites, en montrant que le problème général se ramène à des questions classiques (et NP-complètes) de coloration de tableaux à partir de leurs vues tomographiques. Dans un premier temps, nous présenterons des approches délibérément naïves et infructueuses reposant i) exclusivement sur un Programme Linéaire (implémentant un flot contraint) ii) exclusivement sur un solveur de contraintes. Nous présenterons ensuite un schéma général de coopération étroite à trois niveaux entre une relaxation lagrangienne (consistant à traiter isolément les individus et à relâcher les contraintes couplantes de couverture de charge), de la programmation dynamique (qui résout ici 500 problèmes individuels s,apparentant à des plus courts chemins contraints dans un graphe aux arêtes valuées par les multiplicateurs de Lagrange), et de la programmation par contrainte qui assure la consistance dans la fixation des variables et opère les stratégies de branchement idoines.

Nous nous intéressons à la résolution et la modélisation de problèmes sur-contraints. Tout d'abord, nous présentons des méthodes exactes de
résolution du problème Max-CSP, où l'objectif consiste à minimiser le nombre de violations; ces méthodes peuvent être généralisées à de nombreux autres problèmes. Les algorithmes existants sont basés sur le calcul de bornes inférieures du nombre de violations. Ils sont relatifs à des réseaux de contraintes binaires. Nous proposons une généralisation du meilleur algorithme existant au cas général (tel qu'aucune hypothèse ne soit posée sur la nature et l'arité des contraintes). Nous proposons également une nouvelle borne basée sur le calcul de conflict-sets, qui prend en compte des inconsistances ignorées dans les autres bornes. Nous montrons comment combiner ces deux méthodes. En outre, je présenterai nos travaux sur la modélisation de problèmes sur-contraints réels : quantification des violations, règles d'interaction entre violations, etc.

L'utilisation de la programmation par contraintes s'est fortement développée ces dix dernières années et de nombreux problèmes industriels d'ordonnancement sont aujourd'hui résolus par cette technique. Au cours de cet exposé, nous montrerons que l'intégration de méthodes de Recherche Opérationnelle dans les outils de contraintes a été l'un des facteurs essentiels de leurs succès. Nous présenterons aussi les limites actuelles de ces outils et nous détaillerons quelques pistes de recherches qui pourraient améliorer sensiblement leurs performances sur des problèmes d'ordonnancement.