Une approche efficace pour le passage sur grilles de calcul de méthodes d'optimisation combinatoire
Institution:
Lille 1Disciplines:
Directors:
Abstract EN:
The exact resolution of large combinatorial optimization problems is a challenge for grids. Indeed, it is necessary to rethink the resolution algorithms to take into account the characteristics of such environments, in particular their large-scale, the heterogeneity and the dynamic availability of their resources, and their multi-domain administration. Ln this thesis, we propose a new approach, called B&B@Grid, to adapt exact methods for grids. This approach is based on coding work units in the form of intervals in order to minimize the cost of communications caused by the operations of load balancing, fault tolerance and detection of termination. This approach, about 100 times more efficient than the best known approach in term of communication cost, led to the optimal resolution on the Grid5000 of a standard instance of the Flow-Shop problem remained unsolved for fifteen years. To accelerate the resolution, we also deal with cooperation on the grid of exact methods with meta-heuristics. Two cooperation modes have been considered: the relay mode where a meta-heuristic is performed before an exact method, and the co-evolutionary mode where both methods are executed in parallel. The implementation of this cooperation on a grid has led us to propose an extension of the Linda coordination model.
Abstract FR:
La résolution exacte de problèmes d'optimisation combinatoire de grande taille constitue un défi pour les grilles. En effet, il est nécessaire de repenser les algorithmes de résolution pour prendre en compte les caractéristiques de tels environnements. Notamment leur grande échelle. L'hétérogénéité et la disponibilité dynamique de leurs ressources. Et leur nature multi-domaine d'administration. Dans cette thèse, nous avons proposé une nouvelle approche de passage sur grilles des méthodes exactes de type Branch-and-Bound appelée B&B@Grid. Cette approche est basée sur un codage des unités de travail sous forme d'intervalles permettant de minimiser le coût des communications induites par les opérations de régulation de charge, de tolérance aux pannes et de détection de la terminaison. Cette approche. Environ 100 fois plus performante en terme de coût de communication que la meilleure approche connue. A permis la résolution optimale sur la grille nationale Grid5000 d'une instance standard du problème du Flow-Shop restée non résolue depuis une quinzaine d'années. Pour accélérer la résolution. Nous avons également étudié la coopération sur la grille de la méthode exacte avec une méta-heuristique parallèle hybride. Deux modes de coopération ont été considérés : le mode relais où la méta-heuristique est exécutée avant la méthode exacte, le mode co-évolutionnaire où les deux méthodes sont exécutées en parallèle. La mise en oeuvre d'une telle coopération sur la grille nous a amené il proposer une extension du modèle de coopération Linda.