Journée du 6 juin 2003

Paris

Programme et accès aux présentations

09h30Accueil - Café

10h00Introduction

Présentations courtes (5mn) de Abderrahmane Aggoun (Cosytec) (.pdf), Jacques Carlier (HeuDiaSyc) (.doc), François Fages (INRIA) (.ps), Éric Monfroy (IRIN) (.pdf), Jean-François Puget (Ilog) (.ppt) et Thomas Schiex (INRA) (.pdf)

11h00Table ronde

12h00Déjeuner (libre)

13h45Fabien Le Huédé (Thalès Research & Technology)

Intégration d'une méthode d'aide à la décision multi-critère en programmation par contraintes (.ppt)

L'Aide à la Décision Multicritère a pour objectif de modéliser les préférences subjectives d'un expert. Le modèle élaboré permet d'assister ou d'automatiser le processus de choix d'une solution préférée parmi un ensemble d'alternatives décrites par plusieurs attributs. Pour les problèmes combinatoires, l'évaluation de chaque solution est rarement réalisable en raison de la trop grande taille de l'espace de recherche. La PPC propose une méthode de résolution de ces problèmes combinatoires qui alterne la construction d'un arbre de recherche avec la propagation partielle des contraintes du problème. Notre objectif est d'intégrer un modèle multicritère dans un solveur de contraintes afin de permettre la détermination d'une solution optimale d'un problème combinatoire au sens d'une relation de préférence multicritère.

Dans un premier temps nous présentons la modélisation des préférences dans le cadre de la théorie MAUT (Multi-Attribute Utility Theory) et l'intégrale de Choquet, fonction d'agrégation des critères qui permet de modéliser un grand nombre de comportements décisionnels. Pour permettre la modélisation d'un modèle multicritère basé sur l'intégrale de Choquet en PPC on étudie la représentation en contraintes d'un modèle de type MAUT. Suivant les propriétés du modèle, on en déduit comment la cohérence des contraintes identifiées peut être vérifiée et quelles sont les propagations qui en découlent. Enfin, on montre comment les principes présentés dans le cadre du modèle MAUT s'appliquent au cas de l'intégrale de Choquet et on évalue l'apport de la propagation pour cette fonction.

La seconde problématique étudiée concerne le guidage de la recherche de solutions en optimisation multicritère.Dans le cadre de problèmes multicritères, la présence de critères contradictoires dans la fonction objectif et les phénomènes de compensation rendent difficile la définition d'heuristiques de recherche efficaces. En conséquence, un algorithme de recherche doit être capable à la fois de se diriger rapidement vers de bonnes solutions et d'explorer des parties éloignées de l'espace de recherche afin d'exhiber des solutions diversifiées. Pour répondre à cette problématique, on propose l'algorithme MCS qui utilise n stratégies de recherches, dédiée chacune à l'optimisation d'un des critères du problème. Dans cet algorithme, les stratégies sont choisies itérativement et dynamiquement pour trouver des solutions de qualité croissante. MCS et ses composants sont implémentés sous la forme d'un framework afin de faciliter son utilisation. Plusieurs instances de l'algorithme pour la recherche complète sont testées sur le problème de planification d'examens multicritère.

14h25Frédéric Prost (IMAG)

Coopération de la Réécriture et de la Recherche Opérationelle pour la planification de personnel médical (.pdf)

L'objectif de ce travail est de modéliser et de résoudre des problèmes génériques ayant de nombreux types de contraintes complexes. L'approche choisie, combinant réécriture et recherche opérationelle, est illustrée par l'application à un cas réel : la planification de personnel médical dans un service de radiologie d'un hôpital parisien.

L'idée principale est d'intégrer les techniques de description de contraintes sous forme de règles de réécriture et de résolution de contraintes (méthodes de la recherche opérationnelle). De nombreuses méthodes en recherche opérationelle ont été proposées pour traiter de manière efficace des contraintes spécifiques. Néanmoins, ces méthodes sont en général statiques (elles ne tiennent pas compte des évolutions dynamiques) et souvent trop spécifiques. Dans un problème de la vie courante il est fréquent que différents types de contraintes soient mélangés. Si la méthode de recherche opérationnelle est naturelle pour certaines, il faut souvent se livrer à un codage non trivial pour d'autres contraintes . D'un autre coté, les langages de programmation de très haut niveau permettent des descriptions aisées et rapides (par ce que symboliques) de systèmes de contraintes statiques et dynamiques. Cependant, les méthodes utilisées en programmation pour la résolution de contraintes symboliques ou numériques ne sont pas aussi efficaces que celles proposées par la recherche opérationnelle.

Pour illustrer notre méthode, nous traitons un problème de génération hebdomadaire d'emploi du temps de médecins dans un service de radiologie. La personne chargée de la planification dispose d'un certain nombre de postes et d'une équipe de médecins avec des compétences diverses à affecter à ces postes par demi-journées. Cette partie, en tant que telle, peut se traiter de manière standard en Recherche Opérationelle (affectation linéaire suivant la méthode hongroise). Une autre partie du problème consiste à prendre en compte de nombreuses autres contraintes. Par exemple, sur une journée, sur certains postes, le médecin affecté doit être le même le matin et l'après-midi alors que sur d'autres postes, le médecin du matin doit être différent de celui de l'après-midi. Chaque médecin exprime des préférences et est plus ou moins compétent pour travailler sur les différents postes. Ceci implique par exemple que certains médecins ne peuvent pas être seuls sur certains postes tant qu'ils n'ont pas été formés. De plus, un médecin ne peut pas être affecté plus de trois fois par semaine sur le même poste.

Ces exemples montrent que le problème possède des contraintes de types très variés. De plus, les niveaux de contraintes sont différents : certaines contraintes peuvent être violées alors que d'autres sont très fortes. La méthode doit également permettre une gestion dynamique des contraintes : les contraintes et les types de contraintes sont susceptibles de changer d'une semaine à l'autre. Toutes ces caractéristiques les rendent difficiles à coder correctement dans une approche R. O. pure.

Nous avons procédé de la façon suivante. La semaine est découpée en une liste de blocs (un bloc correspondant à une demi-journée), dans chacun des blocs on utilisera une méthode de la R.O. pour réaliser l'affectation et les règles de réécritures pour gérer les contraintes inter-blocs ainsi que les données d'initialisation (pré-affectation des médecins, emploi du temps des postes etc.).

15h05Pause Café

15h20Guillaume Rochart (École des Mines de Nantes)

Des explications "opérationnelles" pour les contraintes globales (.pdf)

La programmation par contraintes permet de modéliser des problèmes de manière modulaire et réutilisable. Différentes techniques de résolution sont offertes que ce soit au niveau de la propagation ou de la recherche, pour améliorer le temps de solution et/ou la qualité des solutions trouvées. De plus, des techniques d'apprentissage comme les explications (sous-ensemble de contraintes justifiant une inférence du solveur) permettent d'une part d'accélérer ces calculs, mais aussi d'apporter de l'information supplémentaire à l'utilisateur et/ou le développeur.

La notion de contrainte globale est de plus en plus utilisée en programmation par contraintes. Elle offre, en effet, entre autres, une sémantique plus simple, des algorithmes de filtrage plus performants, ... Ces contraintes globales sont basées pour la plupart sur des algorithmes bien connus de RO : couplage dans un graphe bi-parti pour allDifferent, ordonnancement cumulatif pour la contraintes cumulative, la recherche de flot (compatible et maximal),...

L'utilisation d'explications pour les contraintes globales n'est pas triviale car des explications précises (c'est-à-dire de tailles minimales) sont nécessaires pour obtenir des résultats satisfaisants. Pour cela, la recherche opérationnelle nous offre des algorithmes et des notions qui nous permettent, par exemple, d'implémenter des contraintes de flots expliquées et efficaces.

16h00Julien Bidot (LGP, Ilog)

Planification et ordonnancement sous incertitudes - Application à la gestion de projet (.pps)

Les problèmes de gestion de projet sont entachés d'incertitudes et révèlent parfois un caractère fortement combinatoire. La construction de barrages, notre domaine d'application, présente des caractéristiques relevant aussi bien de l'ordonnancement que de la planification sous incertitudes. Nous utilisons l'approche par contraintes et une modélisation probabiliste des aléas pour résoudre ce type de problème. L'environnement est simulé et les distributions de probabilités sont mises à jour en utilisant la simulation.

Au cours de cette présentation nous rappellerons ce que sont les problèmes de planification et d'ordonnancement. Notre domaine d'application sera ensuite décrit, ainsi que les types d'incertitudes que nous y rencontrons. Nous ferons ensuite une synthèse des techniques existantes permettant de gérer ces incertitudes, après quoi notre approche sera abordée ainsi que le modèle d'exécution qu'elle sous-tend. Enfin, nous donnerons les premiers résultats expérimentaux obtenus en appliquant cette approche à une instance de problème de Job-shop ainsi que les débuts de réponses qu'ils apportent.

16h40Fin de la journée.