Brevet FR2850472A1 — publié le 20040730

PROCEDE PERMETTANT DE PRODUIRE DES SOLUTIONS A UN PROBLEME CONCRET D'OPTIMISATION MULTICRITERE La présente invention se rapporte à un procédé permettant de produire des solutions à un problème concret d'optimisation multicritère. De nombreux problèmes industriels relèvent à la fois de la décision multicritère et de l'optimisation. D'un côté, les techniques de recherche arborescente permettent de résoudre un grand nombre de problèmes d'optimisation combinatoire ou continue dans le cas monoobjectif. L'aide à la décision multicritère, d'un autre côté, propose des outils et des méthodes pour modéliser les préférences d'un décideur et comparer les solutions d'un problème multicritère. Pourtant, de nombreux systèmes d'optimisation nécessiteraient une modélisation multicritère de la relation de préférence entre les solutions, qui permettrait de mieux modéliser le problème rencontré et de pouvoir y répondre par des solutions de meilleure qualité. De même, dans le cadre de problèmes abordés par l'aide à la décision multicritère, l'ensemble des solutions est parfois trop vaste et il est impossible d'en comparer tous les éléments. L'invention s'intéresse plus particulièrement à l'utilisation de méthodes arborescentes pour la résolution des problèmes d'optimisation multicritère. Dans le cas mono-objectif, la fonction objectif détermine en grande partie la manière dont est construit l'arbre de recherche et la stratégie adoptée pour son exploration. Le choix de ces éléments qui constituent une stratégie de recherche de solutions a une grande influence sur l'efficacité du processus de résolution. Dans le cas multicritère, par contre, il est souvent très difficile de déterminer une stratégie de recherche permettant que la résolution d'un problème soit efficace dans la plupart des cas. La présente invention a pour objet un procédé permettant de produire semiautomatiquement ou, de préférence, automatiquement, des solutions à un problème d'optimisation multicritère, qui soit applicable de façon efficace dans la plupart des cas, c'est- à-dire capable d'accélérer la convergence du processus de recherche vers une solution optimale. Le procédé conforme à l'invention est un procédé selon lequel : # on établit plusieurs critères de décision et une relation de préférence basée sur ces critères entre les solutions du problème ; # on établit une modélisation du problème à résoudre et il est caractérisé par le fait : # que les solutions sont obtenues de manière constructive via un processus de recherche arborescente ; # qu'une stratégie de recherche arborescente a été établie pour chaque critère ; # que l'on alterne les stratégies pour trouver des solutions de qualité croissante ; # que les stratégies sont choisies dynamiquement en fonction de la dernière solution trouvée ; # que l'alternance des stratégies continue jusqu'à la satisfaction d'une condition d'arrêt ; # que la dernière solution trouvée avant la vérification de la condition d'arrêt est exhibée comme la solution du problème posé. Selon une autre caractéristique de l'invention, la relation de préférence entre les solutions du problème est modélisée par une fonction d'agrégation H, qui est, de préférence, une intégrale de Choquet . Selon encore une autre caractéristique de l'invention, suite à chaque recherche, la valeur d'un indicateur est déterminée pour chaque critère en fonction de la dernière solution trouvée et cet indicateur permet de déterminer la stratégie qui sera utilisée lors de la recherche suivante. Selon encore une autre caractéristique de l'invention, l'indicateur utilisé pour le choix dynamique d'une stratégie est l'indicateur d'utilité maximale. Selon encore une autre caractéristique de l'invention, l'indicateur utilisé pour le choix dynamique d'une stratégie est l'indicateur d'utilité moyenne. Selon encore une autre caractéristique de l'invention, on pose des contraintes locales aux différentes recherches. De façon avantageuse, la contrainte locale posée pour une recherche sur un critère est une contrainte d'amélioration de ce critère et cette contrainte est posée à chaque recherche. Alternativement, la contrainte locale posée pour une recherche sur un critère est une contrainte d'amélioration de ce critère et cette contrainte est posée uniquement lorsqu'un critère est sélectionné plusieurs fois de suite pour guider la recherche, à partir de la seconde recherche consécutive sur ce critère. Selon encore une autre caractéristique de l'invention, les stratégies associées aux différents critères, les contraintes locales aux recherches et la condition d'arrêt du processus de recherche sont utilisées pour trouver une solution optimale du problème et de prouver l'optimalité de cette solution. Selon encore une autre caractéristique de l'invention, la modélisation du problème et la recherche de solutions sont réalisées dans un solveur de contraintes. La présente invention sera mieux comprise à la lecture de la description détaillée d'un mode de mise en oeuvre, pris à titre d'exemple non limitatif. Le procédé de l'invention est donc un procédé de résolution des problèmes d'optimisation multicritère basée sur l'alternance de recherches suivant différentes stratégies mono-objectif (une par critère). Pour que le procédé soit efficace, le choix d'une stratégie à un moment de la recherche doit être effectué de manière adaptative en fonction des données du problème et de l'état de la recherche. Dans un premier temps, on définit les notions importantes à la compréhension du procédé de l'invention, ainsi que les notations et appellations utilisées dans la suite de la description. Un problème d'optimisation se définit par un ensemble de variables de décision prenant chacune leur valeur parmi un ensemble appelé domaine, par un ensemble de relations logiques, ces variables restreignant les combinaisons de valeurs permises appelées contraintes. Enfin, ce problème se définit par une fonction objectif qui caractérise la qualité d'une solution (on parle souvent de fonction de coût dans le cas d'un problème de minimisation et de fonction de profit ou fonction d'utilité s'il s'agit d'un problème de maximisation). Une solution à un tel problème est une affectation d'une valeur de son domaine à chaque variable de décision qui satisfait toutes les contraintes. L'ensemble des solutions optimales, dans le cas d'un problème de minimisation, correspond aux solutions ayant la plus petite valeur de la fonction de coût parmi l'ensemble des solutions existantes. Le traitement d'un problème d'optimisation consiste à rechercher des solutions de faible coût, si possible optimales, ou le cas échéant à prouver l'absence de solution. Lorsque les domaines des variables sont des ensembles finis de valeurs, le problème est un problème d'optimisation combinatoire. Lorsque les domaines sont des intervalles de l'ensemble des réels, le problème est un problème d'optimisation continu. Pour un problème d'optimisation donné, l'espace de recherche de solutions correspond à l'espace formé par le produit cartésien des domaines des variables. L'espace des solutions correspond à l'ensemble des solutions du problème. Les problèmes d'optimisation sont couramment rencontrés dans la plupart des branches de l'industrie et des services. Un exemple de problème consiste à livrer à moindre coût un certain nombre de commandes à des clients dispersés géographiquement. Les variables de décision du problème sont les dates et heures de livraison de ces marchandises. Les contraintes décrivent le réseau de transport, les horaires de disponibilité des clients pour la réception des marchandises, la capacité des véhicules de livraison, les horaires des employés qui effectuent les livraisons. La fonction de coût à minimiser est calculée en fonction de la distance parcourue pour la satisfaction des commandes. Les problèmes de transport sont rencontrés dans des domaines très variés, parmi lesquels les télécommunications, l'aéronautique, la défense. Les autres grandes classes de problèmes d'optimisation sont, entre autres, les problèmes d'ordonnancement (ordonnancement d'une chaîne de production, séquencement des tâches traitées par un processeur), les problèmes de configuration, les problèmes d'emploi du temps et de planification, les problèmes de découpe. Les techniques d'aide à la décision multicritère ont pour but de modéliser de la manière la plus fidèle possible les préférences d'un expert. Une telle modélisation permet ensuite la construction d'outils adaptés et capables d'assister ou de remplacer un décideur sur des problèmes complexes. Résoudre un problème de décision multicritère consiste à modéliser la manière dont un expert ou un décideur classe un ensemble de solutions potentielles (appelées chacune alternative ) décrites par un ensemble d'attributs ou points de vue. Afin d'effectuer le classement (ou même simplement le choix d'une alternative), on évalue les performances (niveau de satisfaction) des différentes alternatives possibles selon chacun des points de vues jugés pertinents pour le problème. La modélisation des préférences d'un expert est réalisée à l'aide d'une fonction agrégeant les performances des différentes alternatives. Deux approches sont utilisées : l'approche Comparer puis Agréger (CA) consiste tout d'abord en une comparaison par paires, critère par critère, des performances des alternatives, puis en une agrégation de ces comparaisons afin d'établir la relation de préférence ; l'approche Agréger puis Comparer (AC) résume la valeur d'une alternative par une note globale calculée à partir des performances d'une alternative sur les différents critères. La meilleure alternative au sens des préférences de l'expert est appelée solution préférée. Par exemple, on considère différentes solutions au problème de livraison de marchandises cité précédemment. Le coût de la solution permettant de livrer les marchandises peut ne pas être l'unique critère de choix. On peut également vouloir minimiser la durée de la livraison (la solution la moins chère n'est pas nécessairement la plus rapide), donner la priorité à des commandes plus importantes, minimiser le nombre de livraisons en retard ou le cumul des retards lorsqu'il est impossible de tenir des délais donnés. Un décideur peut alors préférer une solution qui offre un compromis entre les différents critères à la solution de coût minimum. Les techniques d'aide à la décision multicritère permettent de classer un certain nombre d'alternatives connues (par exemple, pour le choix d'un site pour l'implantation d'une centrale nucléaire). De manière plus générale, elles permettent d'évaluer des situations ou l'aptitude des individus (évaluation de la pertinence de la réponse à un appel d'offres, évaluation d'élèves, etc.). Les problèmes que l'invention doit modéliser et résoudre sont des problèmes d'optimisation multicritère caractérisés par le fait que l'espace des solutions est modélisé, comme dans un problème d'optimisation classique, par un ensemble de variables de décision et de contraintes, et que la relation de préférence entre les solutions est modélisée par une fonction multicritère. Résoudre un problème d'optimisation multicritère revient donc à trouver une solution préférée au problème, ou au moins une solution de bonne qualité. Dans le cadre des problèmes d'optimisation multicritère, une solution optimale est donc une solution préférée. Il est en général impossible de comparer toutes les solutions d'un problème d'optimisation, et on peut noter que l'introduction de critères multiples rend souvent encore plus complexe la recherche d'une solution optimale. L'invention propose donc un procédé permettant de prendre en compte la spécificité des problèmes d'optimisation multicritère et permettre leur résolution dans des temps raisonnables. Ce procédé est basé sur l'utilisation de méthodes arborescentes pour la recherche de solutions au problème. La recherche d'une solution à un problème d'optimisation peut être réalisée de différentes manières. Une des méthodes de résolution les plus répandues est le processus de séparation- évaluation (branch and bound) qui permet d'effectuer un parcours implicite de l'espace des solutions à l'aide d'un arbre de recherche. Le principe de la construction d'un arbre de recherche est le suivant : à chaque n#ud de l'arbre, un sous-problème père est divisé en sous-problèmes fils plus simples, jusqu'à ce que les sous-problèmes à résoudre soient triviaux. La division en sous-problèmes (appelée séparation) est réalisée de telle sorte qu'une solution d'un sous-problème fils soit solution du sous-problème père et que l'union des sous-problèmes fils soit équivalente au sous-problème père. Le problème principal est le n#ud à la racine de l'arbre. Toute solution d'un sousproblème est donc solution du problème principal. Lorsqu'un sous-problème n'a pas de solution, le n#ud correspondant à ce sous-problème est élagué de l'arbre de recherche. Si tous les fils d'un sous-problème père ont été élagués, alors il n'existe pas de solution au sousproblème père et il peut à son tour être élagué. La règle de séparation donne la manière dont les n#uds sont séparés (c'est-à-dire la manière dont un sous-problème père est divisé en sousproblèmes fils). Par exemple, on considère un problème de livraison avec un seul véhicule, et p variables de décision T1,...,tp qui représentent les dates de livraisons des p prochaines commandes. Si l'on décide d'effectuer les livraisons aussi vite que possible, alors seul l'ordre entre les livraisons est important : il permet de déterminer de manière exacte la date au plus tôt où chaque livraison est effectuée. Une solution peut donc être obtenue en déterminant pour tout couple i,j, i tj. A un n#ud de l'arbre correspondant au sous-problème P, on sélectionne donc un couple i,j de variables pour lequel on n'a pas encore résolu cette disjonction et on sépare P en P1={P # (ti Il existe diverses manières de rechercher des solutions dans un arbre de recherche en fonction de l'ordre dans lequel on construit les n#uds. Étant donné un arbre de recherche en cours de construction, il faut choisir le prochain n#ud à séparer et une des décisions de séparation qui peut lui être appliquée. La composante qui détermine le prochain n#ud à séparer est appelée stratégie d'exploration. La stratégie d'exploration la plus communément employée est la stratégie en profondeur d'abord : à chaque fois qu'un n#ud est créé, il est séparé. Dans cette stratégie on n'explore le deuxième fils d'un n#ud que lorsque tous les descendants du premier fils ont été explorés. Cette stratégie est intéressante car elle permet de trouver des solutions très rapidement et peut être implémentée facilement à l'aide d'une pile. Une deuxième stratégie est la stratégie en largeur d'abord où l'on sépare tous les n#uds d'un niveau de l'arbre avant de séparer les suivants. De manière pratique, cette stratégie n'est jamais utilisée car elle consomme trop de mémoire. Enfin, une troisième stratégie est la stratégie du meilleur d'abord où une fonction d'évaluation attribue un score aux n#uds non encore séparés, le n#ud ayant obtenu le meilleur score est alors sélectionné pour être séparé. Le choix de la décision de séparation appliqué à un n#ud détermine l'ordre dans lequel s'enchaînent ces séparations (dans l'exemple ci-dessus,, l'ordre dans lequel on choisit les couples i,j, et si on crée le n#ud Pl={Pfl (ti tj)} ou l'inverse). Cet ordre, généralement choisi de manière empirique, est souvent donné par un critère heuristique. Son but est en général de précipiter la découverte d'une nouvelle solution, ou, au contraire, de détecter plus vite des contradictions prouvant qu'un n#ud n'admet pas de solution. En optimisation, on utilise le principe du Branch and Bound : lorsqu'une solution est trouvée, on ne sépare que les n#uds pouvant mener à une meilleure solution. A chaque n#ud, la fonction d'évaluation permet de déterminer une borne (inférieure en minimisation) de la fonction objectif pour le sous-problème correspondant : c'est la meilleure valeur qui pourra être obtenue pour ce sous-problème. Si cette borne est de moins bonne qualité que la meilleure solution déjà trouvée, le n#ud est élagué. Ce processus permet de ne trouver que des solutions de qualité croissante et d'éviter le parcours inutile de grandes parties de l'arbre de recherche. On a prouvé que la solution optimale a été atteinte lorsqu'on ne trouve plus de solution améliorant l'objectif. En conclusion, la recherche d'une solution à un problème d'optimisation dans un arbre de recherche dépend de la règle de séparation, de la fonction d'évaluation, de la stratégie d'exploration et d'un critère heuristique. La règle de séparation, la stratégie d'exploration et le critère heuristique déterminent l'ordre dans lequel les n#uds seront construits et donc l'ordre dans lequel les solutions seront trouvées. On appelle stratégie de recherche la combinaison de ces différents éléments. Selon la fonction objectif ou le critère à optimiser il est important d'adopter une stratégie de recherche permettant de trouver rapidement des solutions de bonne qualité pour ensuite pouvoir élaguer de grandes parties de l'arbre de recherche ne pouvant mener à de meilleures solutions. Dans ce sens, dans la suite de la description,, on dira qu'un critère guide une recherche lorsque c'est lui qui détermine la stratégie de recherche adoptée. Une stratégie de recherche permet d'orienter la recherche le plus rapidement possible vers des solutions de bonne qualité (et si possible vers une solution optimale). Trouver une bonne solution rapidement permet ensuite, selon le principe du branch and bound , d'élaguer de grandes parties de l'arbre de recherche ne pouvant mener à de meilleures solutions. Dans le cas multicritère, une stratégie permettant d'obtenir rapidement des solutions de bonne qualité sur un critère peut être très inefficace pour un autre. Ainsi, les phénomènes de compensation et plus généralement d'interaction entre critères rendent souvent très difficile la définition d'une stratégie globale permettant la résolution efficace d'un problème dans tous les cas de figure. De nombreuses méthodes ont été développées pour la résolution de problèmes d'optimisation multicritère. Néanmoins peu d'entre elles proposent de combiner l'efficacité des méthodes arborescentes à la capacité de modélisation des préférences des techniques d'aide à la décision multicritère. Parmi ces approches l'invention a retenu le formalisme des CP-Nets, le formalisme des contraintes flexibles, une approche pour la résolution de problèmes d'ordonnancement multicritère et le formalisme PBS. Parmi les différentes approches, les CP-nets (C. Boutilier et al., A Constraint-Based Approach to Preference Elicitation and Decision Making , Working Papers of the AAAI Spring Symposium on Qualitative Preferences in Deliberation and Practical Reasoning, Jon Doyle and Richmond H. Thomason editors, pp. 19-28, Menlo Park, California, 1997) proposent un formalisme où les préférences sont modélisées par un ensemble de règles qui semblent engendrer néanmoins des problèmes de complexité à la fois lors de la modélisation de la relation de préférence entre les solutions et lors de la recherche de solutions (un très grand nombre de règles semblent nécessaires et difficiles à obtenir de la part d'un expert). Les problèmes de modélisation des préférences sont également abordés via l'utilisation de contraintes flexibles (S. Bistarelli et al., Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison, CONSTRAINTS, N 4, 199-240,1999). Cette approche est jugée particulièrement intéressante lorsqu'on traite des problèmes sur-contraints et qu'on cherche des solutions violant le moins possible ces contraintes. Cependant, l'approche multicritère est plus adaptée pour la modélisation des préférences en présence de critères multiples. Dans les deux cas (CP-Nets et contraintes flexibles), le problème de la recherche de solutions reste complexe et aucune approche spécifique n'a été proposée. Une approche plus pragmatique est adoptée dans (F. Focacci and D. Godard, A practical approach to multi-criteria optimization problems in constraint programming , Proceedings of the Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR'02), pp. 65-75, N. Jussien and F. Laburthe editors, Le Croisic, France, 2002) pour résoudre un problème d'ordonnancement à trois objectifs agrégés par une somme pondérée. L'objectif de l'approche est de produire une solution de bonne qualité en un temps limité. Ainsi, à chaque fois qu'une solution est trouvée, la méthode impose soit une amélioration simultanée de tous les objectifs, soit une amélioration d'un objectif et, dans une certaine mesure, la non-dégradation des autres objectifs (on peut, par exemple, tolérer une dégradation de 10%). Selon les auteurs, les meilleurs résultats sont obtenus en utilisant successivement les différents modes de pose de contraintes d'amélioration pour différents objectifs. L'approche est intéressante car, même si c'est la même stratégie de recherche qui est utilisée pour toutes les recherches, elle met déjà en évidence l'intérêt d'alterner des optimisations sur les critères du problème pour améliorer un objectif global. Néanmoins, la méthode d'alternance des différentes recherches apparaît avoir été conçue de manière empirique et être plus particulièrement dédiée au problème d'ordonnancement. On note également l'intérêt des contraintes sur les critères qui permettent d'accélérer la recherche mais qui peuvent également supprimer des solutions intéressantes. Les travaux sur la programmation basée sur les préférences dans les problèmes d'optimisation combinatoire sont issus du raisonnement non-monotone. Ils permettent la modélisation de préférences (le plus souvent sous forme de règles) entre des décisions qui devront être prises au cours de la recherche de solutions (par exemple, traiter une tâche avant une autre en ordonnancement). Ces préférences sont ensuite utilisées pour déterminer l'ordre dans lequel les décisions sont prises durant la recherche, qui est réalisée par un solveur de contraintes. Ces travaux ont débouché sur la conception d'une procédure appelée "Preference Based Search" (PAS). PBS a été développée et mise en #uvre pour la résolution de problèmes d'ordonnancement et de problèmes de configuration. Elle utilise les préférences sur les décisions à la fois pour guider la recherche et pour réduire l'espace de recherche en supprimant des solutions non préférées. Les plus récents développements sur PBS généralisent la procédure pour prendre en compte des préférences sur des critères (U. Junker, "Preference-based search and multi-criteria optimization", Proceedings of the Fourth International Workshop on Intégration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR'02), pp. 33-47, N. Jussien and F. Laburthe editors, Le Croisic, France, 2002). Le formalisme est étendu de manière à pouvoir exprimer qu'un critère c1 est préféré à un autre c2 (c1# ci) ou qu'un ensemble de critères doivent être équilibrés (c1#c2). L'équilibre entre deux critères est établi grâce à un opérateur de type lexi-max (voir H. Moulin, Axioms of Coopérative Decision-Making. Cambridge Univ. Press, 1988). Pour la recherche de solutions, un programme maître PBS sélectionne des critères sur la base des préférences du décideur et les renvoie comme objectifs à un solveur de contraintes. Cet algorithme effectue en fait plusieurs optimisations lexicographiques successives pour les différents ordres de critères autorisés par les préférences. Ainsi, en utilisant le principe de la méthode s-contraintes (K. M. Miettinen, Nonlinear multiobjective optimization, édition Kluwer academic publisher, 1999), PBS permet d'exhiber l'ensemble des solutions préférées du problème. PBS utilise l'alternance d'optimisations sur les critères pour parcourir l'espace de recherche et exhiber l'ensemble des solutions préférées (et non pas améliorer une solution). En effet, le formalisme utilisé pour la modélisation des préférence présente l'avantage d'être relativement simple mais il ne permet pas une représentation fine des préférences (notamment des phénomènes de compensation). La méthode doit donc renvoyer un grand nombre de solutions au décideur qui devra alors faire un choix parmi celles-ci. Ceci peut-être souhaitable dans certains cas (pour la recherche d'un voyage sur Internet par exemple), mais particulièrement gênant dans un contexte de décision automatique (gestion automatique de conflits aériens, évaluation de la menace et protection d'un bâtiment). L'invention propose donc une approche dédiée à la recherche de solutions dans le contexte de la résolution de problèmes d'optimisation multicritère. L'approche proposée pour le guidage d'une recherche multicritère est de définir une stratégie de guidage adaptée par critère et d'employer ces différentes stratégies pour la recherche de solutions multicritères de qualité croissante. L'idée est d'alterner des recherches mono-critères utilisant ces stratégies tout en imposant une amélioration du niveau de satisfaction global à chaque nouvelle solution jusqu'à la satisfaction d'une condition d'arrêt donnée (par exemple, jusqu'à ce qu'on ait prouvé l'optimalité de la dernière solution trouvée). A la fin d'une recherche sur un critère, on détermine le critère qui guidera la prochaine recherche en fonction : de la dernière solution trouvée ; des améliorations possibles sur chaque critère ; et de la relation de préférence entre les solutions. C'est en quelque sorte le critère sur lequel on a le plus grand intérêt à s'améliorer. A chaque recherche, pour essayer d'accroître encore la vitesse de convergence vers une bonne solution, on peut de plus imposer des améliorations sur les critères via un ensemble de contraintes additionnelles, valable uniquement le temps d'une recherche. On appellera ce type de contrainte des contraintes locales à une recherche. Ces contraintes éphémères viennent s'ajouter à la contrainte d'amélioration de la qualité globale des solutions recherchées. Elles permettent également exprimer le fait qu'il est interdit de dégrader un critère de plus de 10% au cours d'une recherche, comme présenté dans l'article FocacciGodard 2002. Comme dans cet article, ces contraintes doivent être employées avec précaution, car elles peuvent retarder, voire empêcher la découverte de bonnes solutions (et plus particulièrement de solutions optimales). Le processus termine lorsqu'une condition d'arrêt définie par l'utilisateur a été vérifiée, (par exemple, lorsqu'une recherche n'arrive pas à trouver de solution améliorante). L'alternance des différentes stratégies permet ainsi de parcourir différentes régions intéressantes de l'espace de recherche alors que les contraintes ajoutées à chaque solution trouvée permettent de converger vers une solution optimale. Le processus décrit dans les étapes précédentes, dédié à la recherche de solutions pour un problème multicritère a été nommé MCS (Multi-Criteria Search). D'un point de vue algorithmique, les principes exposés précédemment peuvent être traduits de la manière suivante : MCS u := (u1,...,un), s* := nil,s := nil, c :=0, local := false while not( (local,s*,s,u,c)) c := (s*,u), local:= (s*,u,c), s := maximize(u[c], getStrategy(c)), if (s # nil) s* := s endif endwhile retu rn s* end Les critères à maximiser sont représentés par le vecteur de variables u=(u1,...,un), la meilleure solution trouvée par l'algorithme est stockée dans la variable s* et la variable s est utilisée pour le stockage de solutions intermédiaires. La variable c contient l'indice du critère sur lequel on va lancer une recherche et la variable local indique si une contrainte locale a été posée lors de la dernière recherche de solutions. Les chevrons ( , , ) indiquent les fonctions caractéristiques de l'algorithme MCS qui devront être définies par l'utilisateur en fonction de son problème. L'algorithme fonctionne de la manière suivante : une boucle while est répétée tant que la condition d'arrêt contenue dans la fonction n'a pas été vérifiée. A chaque itération, la fonction détermine le critère qui guidera la prochaine recherche. Une ou plusieurs contraintes locales peuvent être posées par la fonction (dans ce cas, la fonction renvoie la valeur booléenne true ). La recherche de solutions optimisant le critère c est effectuée par la fonction maximize en fonction de la stratégie définie pour ce critère, qui est donnée par getStrategy(c). La fonction maximize ne recherche que des solutions globalement préférées à s* . maximize renvoie nil si aucune solution n'a été trouvée, sinon, la variable s* est mise à jour. MCS donne la trame d'un algorithme générique, paramétrable en fonction des problèmes abordés. Ce procédé peut donc être qualifié de framework dont on produira des instances en définissant les différentes fonctions qui le composent. Dans la suite de la description, on utilise un ensemble u1,...,un de valeurs appelées bornes supérieures des performances sur chaque critère. Pour un critère i # 1,...,n, u1 indique la valeur maximale pouvant être atteinte sur le critère i dans une solution optimale. Ces valeurs sont donc régulièrement mises à jour au fur et à mesure de la recherche de solutions, soit grâce à des fonctions qui calculent un majorant pour chaque critère, soit lorsqu'une recherche monocritère prouve qu'elle a atteint un optimum pour le critère qu'elle optimise. Le détail du contenu des différentes composantes de ce framework donne un aperçu de la variété des algorithmes qui peuvent être ainsi construits. La fonction maximize(u[c], getStrategy(c)) lance une recherche arborescente de solutions suivant une stratégie spécifiée pour un critère sélectionné, noté c. Dans tous les cas, l'optimisation est réalisée suivant le principe du branch and bound en élaguant les branches de l'arbre de recherche ne pouvant mener à une solution plus satisfaisante à la fois au sens de la relation de préférence globale et sur le critère c. On définit donc une stratégie de recherche différente pour chaque critère. Ceci a pour but de pouvoir trouver le plus rapidement possible des solutions de bonne qualité sur un critère donné. La stratégie associée à un critère c serait donc, en théorie, celle qui serait utilisée si le problème à résoudre était l'optimisation de ce critère. Pour un même problème, on peut définir un grand nombre de stratégies de recherche en définissant plusieurs fonctions de séparation ou en utilisant différentes stratégies d'exploration. Selon la complexité et les contraintes temporelles du problème, il peut également être intéressant d'employer des stratégies de recherche partielle (une stratégie de recherche partielle ne garantit pas d'atteindre l'optimum sur le critère sélectionné). Par exemple, pour chaque recherche mono-critère, on pourra : ne chercher qu'une solution et non une solution optimale ; spécifier un contrat de temps ; utiliser une stratégie combinant recherche arborescente et recherche locale ou même lancer une séquence de plusieurs recherches différentes. La définition de la fonction détermine la manière dont les recherches sur les critères se succèdent. Bien sûr, il est possible de programmer cette fonction pour que l'algorithme enchaîne les recherches toujours dans le même ordre. Cependant il est plus intéressant de construire une fonction qui prend en compte les informations disponibles au moment de la recherche où elle est sollicitée pour effectuer un choix dynamique. Ces informations sont, par exemple, la dernière solution trouvée, les bornes supérieures des performances pouvant être atteintes sur chaque critère, l'importance de chaque critère dans la relation de préférence. Elles peuvent permettent de déterminer sur quel critère il est le plus intéressant de lancer une recherche. Par exemple, on considère une solution s *, on note (uI*, ..., un *) la représentation de s* sur les n critères du problème et u1,...,un les valeurs maximales pouvant être atteintes sur ces critères. Si l'on fait l'hypothèse qu'une recherche sur un critère i permettrait d'atteindre le maximum sur ce critère sans affecter les autres, on peut comparer les n solutions représentées sur l'espace des critères : (ul*,..., u"...,un*), i=1,...,n. La solution préférée indique alors le critère sur lequel on a le plus grand intérêt à s'améliorer. Le terme contrainte locale est ici employé pour qualifier une contrainte qui ne sera valable que le temps d'une recherche, contrairement aux contraintes du problème qui doivent être constamment vérifiées. L'ajout d'une ou de plusieurs contraintes locales a pour but de contraindre une recherche à explorer des parties de l'espace de recherche jugées particulièrement intéressantes à un moment donné. En d'autres termes, contraindre la recherche à produire une solution ayant une caractéristique particulière qui devrait en faire une solution plus satisfaisante que celles déjà trouvées. Par exemple, si l'heuristique de choix de critère a déterminé qu'il était plus intéressant d'améliorer la valeur uc* de la dernière solution trouvée suivant le critère c , ajouter une contrainte u > Me* ou même met 1.1 1 x u, peut permettre de trouver plus rapidement une solution de meilleure qualité que la solution trouvée. En effet, le choix d'une stratégie dédiée à l'optimisation d'un critère particulier peut être plus efficace mais elle ne garantit pas de trouver en priorité des solutions améliorant ce critère. L'utilisation de contraintes locales peut permettre d'accélérer la convergence de l'algorithme vers une solution de bonne qualité mais elle présente également quelques désavantages, surtout si l'on cherche une solution optimale du problème : lorsqu'une recherche qui a été sur-contrainte par une contrainte locale ne trouve pas de solution, cela ne signifie pas nécessairement que la solution optimale ait été atteinte mais qu'il n'existe pas de meilleure solution vérifiant la contrainte locale. En utilisant ce type de contrainte, on risque donc de construire des algorithmes qui ne garantissent pas de trouver une solution optimale. La fonction renvoie un booléen qui pourra être pris en compte dans la condition d'arrêt et qui permet d'indiquer si une contrainte locale a été posée. L'algorithme termine son déroulement lorsque les conditions contenues dans la fonction sont vérifiées ou lorsque le temps d'exécution imparti à la recherche a été dépassé (si un contrat de temps a été spécifié). Les conditions d'arrêt de l'algorithme peuvent être par exemple : la dernière recherche n'a pas trouvé de solution (s=nil) , la dernière recherche n'a pas trouvé de solution alors qu'aucune contrainte locale n'avait été posée ((s=nil)&(not(local))) . Le framework MCS repose sur des principes communs aux problèmes d'optimisation multicritère et reste donc un cadre relativement général pour la définition d'algorithmes de recherche de solutions. On présente dans cette section quelques outils pour l'utilisation du procédé : tout d'abord dans le cadre d'un problème où les préférences sont modélisées par une fonction d'agrégation à maximiser ; puis dans le cas où l'on désire trouver une solution optimale du problème. On va présenter maintenant quelques exemples d'heuristiques de choix de critère lorsque la modélisation des préférences est réalisée suivant l'approche Agréger puis Comparer . L'approche Agréger puis Comparer (AC) calcule une note globale pour chaque solution par agrégation des performances des solutions sur chaque critère. Dans le contexte MAUT (MultiAtribute Utility Theory), la modélisation des préférences du décideur est réalisée grâce à une fonction d'agrégation H, qui agrège les valeurs des critères u1,...,un et calcule l'évaluation globale d'une solution. Soient a et b deux solutions. On note u1a,...,una et u1b,...,unb les performances des solutions a et b sur les critères du problème. La fonction Hest telle que, pour tout couple de solutions a et b, a préféré à b est équivalent à 7f,...,)>77(,...,). Dans ce cadre, on propose deux heuristiques de choix de critère, chacune basée sur la construction d'un indicateur. Ces indicateurs sont fonction de la dernière solution trouvée s*, de ses performances u1*,...,un* sur chaque critère et des valeurs maximales u1,...,un pouvant être atteintes sur ces critères. Dans les deux cas, l'indicateur repose sur l'hypothèse qu'une recherche sur un critère permettra de trouver une solution de meilleure qualité sur ce critère et de qualité égale sur les autres critères. On note u*= (u1*,...,un*) et u = (u1,...,un) # Indicateur d'utilité maximale : pour tout critère i # {1,...,n}, l'indicateur d'utilité maximale, noté #1(H)(u*,u), est la valeur x, (H)(u*, u) = H(u; , ..., u; 1, u,, u,+,, ..., un ) . C'est le niveau de satisfaction global qui serait atteint si une recherche sur le critère i permettait d'atteindre une solution de niveau de satisfaction maximal sur ce critère sans dégrader la satisfaction des autres critères par rapport à la solution précédente. # Indicateur d'utilité moyenne: la valeur u1 est une borne supérieure de la valeur maximum pouvant être atteinte sur le critère i. Dans la majorité des problèmes d'optimisation, il est peu probable qu'il soit toujours possible de trouver une solution qui permette d'atteindre cette valeur, surtout sans dégrader les performances sur les autres critères. Dans certain cas il peut donc être plus judicieux de calculer la valeur moyenne de la fonction H pour des valeurs du critère i variant entre ui* et ui. Cette valeur, notée #1(H)(u*,u) peut être obtenue en calculant l'intégrale Une heuristique de choix de critère construite à partir de ce type d'indicateur renvoie l'indice du critère qui a obtenu la plus forte valeur de l'indicateur. L'intégrale de Choquet (M. Grabisch, The application of fuzzy integrals in multicriteria décision making , European Journal of Operational Research, 89,1996, pp. 445-456) est une fonction d'agrégation très générale, qui contient comme cas particulier les opérateurs d'agrégation usuels tels que le minimum, le maximum, la médiane, la moyenne pondérée et la moyenne ordonnée pondérée (OWA). Elle permet de modéliser non seulement les importances des critères, mais également les phénomènes d'interactions entre les différentes coalitions de critères. Soit N= {1,...,n} l'ensemble des critères. Une mesure floue sur N associe à chaque A#N un nombre ,u(A) c [0,1] tel que (#)=0, (N)=1 et A c B ,u(A) 5 ,u(B) . On rappelle ici la définition de l'Intégrale de Choquet : Soit une mesure floue sur N et u=(u1, ...,un). L'intégrale de Choquet C du vecteur u n par rapport à ,u est définie par: CJu1,...,ult) = (utKl)-utK,~xju(AtKaLvec I= 0 Dans le cas où l'intégrale de Choquet est utilisée comme fonction d'agrégation, les indicateurs présentés précédemment sont donc les suivants : #Indicateur d'utilité maximale : ,, (C )(u*, u) = C (ul , ... , u,~1, ut , ut+, , ... , un ) . Indicateur d'utilité moyenne : Suivant la définition de ses composantes, le framework peut être utilisé pour implicitement effectuer un parcours complet de l'arbre de recherche et permettre de trouver une solution optimale à coup sûr. Une stratégie de recherche est dite complète si elle permet de trouver une solution à un problème lorsqu'elle existe. En conséquence, si une recherche complète ne trouve pas de solution, c'est qu'il n'en existe pas. En général on dit qu'une recherche est complète lorsqu'elle n'oublie pas de solution. On peut donc dire qu'on a trouvé une solution optimale pour le problème multicritère dans deux cas : # lorsqu'on a trouvé une solution dont la performance sur chaque critère est égale à la borne supérieure de la performance du critère ; # lorsqu'une recherche mono-critère ayant la propriété d'être complète n'a pas trouvé de solution de meilleure qualité que les solutions trouvées lors des recherches précédentes. (Remarque : si aucune solution n'avait été trouvée auparavant, alors le problème n'admet pas de solution) De même, dans le cadre MCS il existe deux types de recherche incomplète : # les recherches dont la stratégie de parcours de l'arbre sont incomplètes (également appelées recherches partielles) ; # les recherches de solutions sur des problèmes plus contraints que le problème initial. Typiquement, si une recherche sur-contrainte par une contrainte locale ne trouve pas de solution, on ne peut pas conclure qu'il n'existe pas de solution au problème qui soit meilleure que les solutions trouvées lors des recherches précédentes. Cela permet simplement de dire qu'il n'existe pas de solution vérifiant la contrainte posée (et éventuellement de diminuer la valeur de la borne supérieure d'un critère si la contrainte locale était une contrainte d'amélioration d'un critère). En revanche, en l'absence de contraintes locales, la recherche de l'optimum sur un critère, même si on limite le nombre de solutions trouvées, est une recherche complète, puisqu'elle garantit de trouver au moins une solution au problème si elle existe. On propose donc une condition d'arrêt et deux fonctions pour l'ajout de contraintes locales qui, associées à des stratégies de recherche mono-critère complètes permettent de trouver une solution optimale du problème global. Soit s* la dernière solution trouvée, c le critère sélectionné par la fonction . La variable u[c] modélise le critère c à maximiser et la fonction getValue(s*,c) renvoie la performance de la solution s* pour le critère c . Le principe proposé est de ne poser qu'un type de contrainte lorsqu'un critère c a été sélectionné par la fonction : la contrainte u[c] > getValue(s*,c). Cette contrainte est appelée contrainte d'amélioration du critère c . On propose deux modes pour la poser : # Un mode systématique : la contrainte est posée à chaque recherche. # Un mode consécutif : la contrainte n'est posée que lorsque le critère c a été également sélectionné pour guider la recherche précédente. Lorsque MCS est utilisé avec une des deux fonctions d'ajout de contraintes locales précédentes, la fonction peut être redéfinie pour que MCS ne s'arrête qu'après avoir trouvé une solution optimale. La fonction optimalityCondition ci-dessous assure ce rôle dans les deux cas : optimalityCondition(local,s*,s,u,c) if (c = 0) return false else if checkUpperBounds(s *,u) return true else if (s = nil) if (local) setconstraint(u [c] :9 get Value(s c , returnfalse else return true endif else return false endif end Le cas c=0 permet de ne pas vérifier la condition avant la première itération. Tout d'abord, la fonction checkUpperBounds vérifie si la performance de la solution s * sur chaque critère est égale à la borne supérieure de la performance du critère. Sinon, la variable local permet d'arrêter l'algorithme lorsqu'une recherche qui n'a pas été soumise à une contrainte locale ne trouve pas de solution (une recherche qui ne trouve pas de solution renvoie nil ). Si une recherche sur le critère c , soumise à une contrainte locale renvoie nil , la fonction setConstraint réduit la borne supérieure du critère c en posant la contrainte u[c] # getValue(s*,c). En supposant que la fonction ne sélectionne pas un critère lorsque la performance de s* sur ce critère est égale à sa borne supérieure, l'algorithme termine nécessairement et retourne une solution optimale. La fonction optimalityCondition permet également de trouver l'optimum lorsqu'aucune contrainte locale n'est posée. De manière plus générale, on note que la fonction est lancée après chaque recherche et qu'elle peut donc également être utilisée pour introduire de nouvelles coupes de l'espace de recherche (par exemple, réduire les bornes supérieures des critères). La Programmation Par Contraintes (PPC) offre un cadre technique pour la modélisation des problèmes d'optimisation combinatoire. Le processus de résolution est basé sur la collaboration entre un processus qui construit un arbre de recherche pour la recherche de solutions et un processus qui propage les contraintes du problème à chaque n#ud de l'arbre afin de réduire l'espace de recherche et assurer la validité des solutions trouvées. En PPC, un certain nombre d'outils ont été conçus pour l'aide à la conception d'algorithmes d'optimisation. Ils permettent de définir relativement facilement des stratégies de recherche de solutions pour les problèmes mono-objectifs. La modélisation de préférences multicritères est également réalisable dans ce cadre, notamment en intégrant des fonction d'agrégation telles que l'intégrale de Choquet (F. Le Huédé, P. Gérard, M. Grabisch, C. Labreuche and P. Savéant, Intégration of a Multicriteria Decision Model in Constraint Programming, proceedings of the AIPS'02 Workshop on Planning and Scheduling with Multiple Criteria, Toulouse, France, April 23-27,2002). La PPC est donc un cadre idéal pour la mise en #uvre du framework MCS, car un grand nombre d'outils ont déjà été créés pour la modélisation des contraintes du problèmes, la modélisation des préférences entre les solution et la description des stratégies de recherche. Dans l'objectif de faciliter l'emploi de MCS, on pourra constituer une bibliothèque contenant les différentes instances des fonctions du framework présentées dans la présente description. En conclusion, le framework MCS permet de construire des algorithmes de recherche de solutions à un problème d'optimisation multicritère. Le principe de l'algorithme repose sur l'alternance de stratégies de recherche mono-critères pour la recherche d'une solution préférée au sens d'une relation de préférence multicritère. MCS est conçu pour pouvoir fonctionner avec des outils issus de l'aide à la décision multicritère qui possède d'importantes capacités pour la modélisation des préférences d'un expert. On utilise donc différentes stratégies de recherche, non pas pour exhiber un ensemble important de solutions non dominées, mais pour accélérer la convergence de l'algorithme vers une solution optimale. Dans ce cadre, une recherche mono-critère peut prendre diverses formes (par exemple : une stratégie incomplète, être interrompue dès qu'elle a trouvé une solution, etc...). Entre chaque recherche, un critère est sélectionné par une heuristique de choix de critère. Il détermine la stratégie qui sera adoptée pour la prochaine recherche de solutions. Cette sélection permet de déterminer le critère sur lequel on a le plus intérêt à s'améliorer à un moment de la recherche et de trouver plus rapidement des solutions plus satisfaisantes. L'ajout de contraintes locales aux différentes recherches peut également permettre d'accélérer la convergence de l'algorithme vers la solution optimale. Finalement, on définit la condition d'arrêt de l'algorithme, ce qui permet de construire des recherches partielles ou d'apporter la preuve de l'optimalité de la dernière solution trouvée. REVENDICATIONS 1. Procédé pour produire des solutions à un problème concret d'optimisation multicritère selon lequel on établit plusieurs critères de décision et une relation de préférence basée sur ces critères entre les solutions du problème ; caractérisé par le fait que : # l'on établit une modélisation du problème à résoudre # que les solutions sont obtenues de manière constructive via un processus de recherche arborescente ; # qu'une stratégie de recherche arborescente a été établie pour chaque critère ; # que l'on alterne les stratégies pour trouver des solutions de qualité croissante ; # que les stratégies sont choisies dynamiquement en fonction de la dernière solution trouvée ; # que l'alternance des stratégies continue jusqu'à la satisfaction d'une condition d'arrêt ; # que la dernière solution trouvée avant la vérification de la condition d'arrêt est exhibée comme la solution du problème posé. 2. Procédé selon la revendication 1 caractérisé par le fait que la relation de préférence entre les solutions du problème est modélisée par une fonction d'agrégation (H). 3. Procédé selon la revendication 2 caractérisé par le fait que la fonction d'agrégation des critères H est une intégrale de Choquet (C ). 4. Procédé selon l'une des revendications 1 à 3 caractérisé par le fait que suite à chaque recherche, la valeur d'un indicateur est déterminée pour chaque critère en fonction de la dernière solution trouvée et que cet indicateur permet de déterminer la stratégie qui sera utilisée lors de la recherche suivante. 5. Procédé selon la revendication 4 caractérisé par le fait que l'indicateur utilisé pour le choix dynamique d'une stratégie est l'indicateur d'utilité maximale (#i ). 6. Procédé selon la revendication 4 caractérisé par le fait que l'indicateur utilisé pour le choix dynamique d'une stratégie est l'indicateur d'utilité moyenne (#@ ). 7. Procédé selon l'une des revendications 1 à 4 caractérisé par le fait qu'on pose des contraintes locales aux différentes recherches. 8. Procédé selon la revendication 7 caractérisé par le fait que la contrainte locale posée pour une recherche sur un critère est une contrainte d'amélioration de ce critère et que cette contrainte est posée à chaque recherche. 9. Procédé selon la revendication 7 caractérisé par le fait que la contrainte locale posée pour une recherche sur un critère est une contrainte d'amélioration de ce critère et que cette contrainte est posée uniquement lorsqu'un critère est sélectionné plusieurs fois de suite pour guider la recherche, à partir de la seconde recherche consécutive sur ce critère. 10. Procédé selon l'une des revendications 1 à 9 caractérisé par le fait que les stratégies associées aux différents critères, les contraintes locales aux recherches et la condition d'arrêt du processus de recherche sont utilisées pour trouver une solution optimale du problème et pour prouver l'optimalité de cette solution. 11. Procédé selon l'une des revendications 1 à 9 caractérisé par le fait que la modélisation du problème et la recherche de solutions sont réalisées dans un solveur de contraintes.