Faculté informatique et communications IC, Section d'informatique, Institut d'informatique fondamentale IIF (Laboratoire d'intelligence artificielle LIA)

Distributed constraint satisfaction for coordinating and integrating a large-scale, heterogeneous enterprise

Eisenberg, Carlos ; Faltings, Boi V. (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2003 ; no 2817.

Ajouter à la liste personnelle
    Summary
    Market forces are continuously driving public and private organisations towards higher productivity, shorter process and production times, and fewer labour hours. To cope with these changes, organisations are adopting new organisational models of coordination and cooperation that increase their flexibility, consistency, efficiency, productivity and profit margins. In this thesis an organisational model of coordination and cooperation is examined using a real life example; the technical integration of a distributed large-scale project of an international physics collaboration. The distributed resource constraint project scheduling problem is modelled and solved with the methods of distributed constraint satisfaction. A distributed local search method, the distributed breakout algorithm (DisBO), is used as the basis for the coordination scheme. The efficiency of the local search method is improved by extending it with an incremental problem solving scheme with variable ordering. The scheme is implemented as central algorithm, incremental breakout algorithm (IncBO), and as distributed algorithm, distributed incremental breakout algorithm (DisIncBO). In both cases, strong performance gains are observed for solving underconstrained problems. Distributed local search algorithms are incomplete and lack a termination guarantee. When problems contain hard or unsolvable subproblems and are tightly or overconstrained, local search falls into infinite cycles without explanation. A scheme is developed that identifies hard or unsolvable subproblems and orders these to size. This scheme is based on the constraint weight information generated by the breakout algorithm during search. This information, combined with the graph structure, is used to derive a fail first variable order. Empirical results show that the derived variable order is 'perfect'. When it guides simple backtracking, exceptionally hard problems do not occur, and, when problems are unsolvable, the fail depth is always the shortest. Two hybrid algorithms, BOBT and BOBT-SUSP are developed. When the problem is unsolvable, BOBT returns the minimal subproblem within the search scope and BOBT-SUSP returns the smallest unsolvable subproblem using a powerful weight sum constraint. A distributed hybrid algorithm (DisBOBT) is developed that combines DisBO with DisBT. The distributed hybrid algorithm first attempts to solve the problem with DisBO. If no solution is available after a bounded number of breakouts, DisBO is terminated, and DisBT solves the problem. DisBT is guided by a distributed variable order that is derived from the constraint weight information and the graph structure. The variable order is incrementally established, every time the partial solution needs to be extended, the next variable within the order is identified. Empirical results show strong performance gains, especially when problems are overconstrained and contain small unsolvable subproblems.
    Résumé
    Les mécanismes du marché ont souvent conduit les organisations publiques et privées à augmenter leur productivité, à optimiser les processus et à réduire les temps de production et par conséquent réduire le temps de travail. Pour s'accommoder à de tels changements, les organisations adoptent aujourd'hui de nouveaux modèles de coopération et de coordination. Ces modèles ont permis aux organisations d'accroître leur flexibilité, efficacité et productivité tout en augmentant leurs marges de profit. Dans cette thèse, nous examinons un modèle organisationnel de coopération et de coordination en s'appuyant sur un exemple réel : l'intégration technique d'un projet de collaboration entre physiciens travaillant au sein d'une organisation internationale géographiquement distribuée. Le problème de gestion distribuée des resources de ce projet de collaboration est modélisé par la résolution d'un problème à satisfaction de contraintes distribuées. Une méthode de recherche locale distribuée, dite "the distributed breakout algorithm (DisBO)", est à la base du schéma de coordination. La performance de cette méthode de recherche locale est améliorée par l'introduction d'un schéma de résolution incrémentale utilisant l'ordonnancement des variables. le schéma suggéré a été implémenté sous les différentes formes suivantes: algorithme centralisé, breakout algorithm incrémental (IncBO), et finalement comme algorithme distribué, le breakout algorithm incrémental et distribué (DisIncBO). Dans les deux cas, que ça soit centralisé ou distribué, un important gain en performance est constaté pour la résoltion des problèmes sous-contraints. Les algorithmes distribués de recherche locale sont incomplets et souffrent de l'absence de conditions de terminaison. Quand les problèmes sont difficile à résoudre ou sur-contraints, la recheche locale échoue dans des cycles infinis et aucune explication ne peut être obtenue. Un schéma de résolution est proposé permettant d'identifier les sous-problèmes difficiles à résoudre ou sans solution et les ordonner selon leur taille. Pour ce faire, le schéma est basé sur l'information de poids de la contrainte qui est générée par "breakout algorithm" lors de la recherhe. Cette information, combinée avec la structure graphe obtenue, est utilisée pour contrôler l'ordonnancement des variables de type "échec en premier". Des résultats expérimentaux montrent que l'ordre des variables obtenu est parfait. Quand un simple en arrière (backtracking) est employé, les problèmes difficiles ne surgissent pas. De même, quand les problèmes sont sans solution, le chemin de l'échec est toujours le plus court. Deux algorithmes hybrides, le BOBT et le BOBT-SUSP sont développés. Quand le problème est sans solution, le BOBT retourne le sous-problème minimal à l'interieur de l'espace de recherche. Quant au BOBT-SUSP, il retourne le plus petit sous-problème sans solution en utilisant une contrainte dite somme de poids. Un algorithme hybride distribué (DisBOBT) est développée en combinant le DisBO avec le DisBT. Cet algorithme tente dans un premier temps à résoudre le problème en utilisant le DisBO. Si aucune solution n'est trouvée après un certain nombre de "breakouts", le DisBO est terminé et le DisBT prend le relais pour résoudre le problème. le DisBT est guidé par ordonnancement distribué des variables qui est dérivé de l'information de poids de contrainte et la structure du graphe. L'ordonnancement des variables est incrémentalement établi, à chaque fois où la solution partielle a besoin d'être étendue, la prochaine variable dans l'ordre est identifiée. Les résultats expérimentaux montrent un gain en performance très considérable, particulièrement quand les problèmes sont sur-contraints et contiennent des petits problèmes sans solution.