Our latest activity report is available here.

Presentation

The goal of the DOLPHIN (Discrete multiobjective Optimization for Large-scale Problems with Hybrid dIstributed techNiques) project team is the modeling and resolution of large multicriteria combinatorial problems using parallel and distributed hybrid techniques. We are interested in algorithms using Pareto approaches which generate the whole Pareto set of a given multiobjective problem (MOP). For this purpose, the research actions can be resumed as follows.

Modeling and Analysis of MOPs:

Solving a multiobjective problem requires an important analysis phase to find the best suitable solution method. This analysis deals with the modeling of the problem and the analysis of its structure.
To propose efficient models for a multiobjective optimization problem, an important aspect is to integrate all the constraints of the problem. Therefore, an interesting preliminary approach is to develop efficient models for the problem in its mono-objective forms in order to be able to develop methods that are taking into account characteristics of the studied problem. While studying the problem in its multiobjective form, the analysis of the structure is another interesting way.
The analysis of the structure of the Pareto front by means of different approaches (statistical indicators, meta-modeling, etc.) allows the design of efficient and robust hybrid optimization techniques. In general, the current theory does not allow the complete analysis of optimization algorithms. Several questions are unanswered: (i) why a given method is efficient? (ii) why certain instances are difficult to solve? Some work is needed to guide the user in the design of efficient methods.
The NFL (No Free Lunch) theorem shows that two optimization methods have the same global performance on the whole set of uniform optimization problems. Then, it is crucial to make some hypotheses on the studied problem. This may be done in two steps:

  • analyzing the target problem to identify its landscape properties,
  • including this knowledge in the proposed optimization method.

Our interest in this project is to answer these questions and remarks for the multiobjective case. Another point considered is the performance evaluation of multiobjective optimization methods. We are also working on approximation algorithms with performance guarantee and the convergence properties of stochastic algorithms.

Cooperation of optimization methods (metaheuristics and/or exact methods):

The hybridization of optimization methods allows the cooperation of complementary different methods. For instance, the cooperation between a metaheuristic and an exact method allows to take advantage of the intensification process of an exact method in finding the best solution(s) in a subspace, and the diversification process of the metaheuristic in reducing the search space to explore.
In this context, different types of cooperation may be proposed. Those approaches are under study in the project and we are applying them to different generic MOPs (flow-shop scheduling problem, vehicle routing problem, covering tour problem, access network design, and the association rule problem in data mining).

Parallel optimization methods:

Parallel and distributed computing may be considered as a tool to speedup the search to solve large MOPs and/or to improve the robustness of a given method. Following this objective, we design and implement parallel metaheuristics (evolutionary algorithms, tabu search approach) and parallel exact methods (branch and bound algorithm, branch and cut algorithm) for solving different large MOPs. Moreover, the joint use of parallelism and cooperation allows the improvement of the quality of the obtained solutions.

Framework for parallel and distributed hybrid metaheuristics:

Our team contributes to the development of an open source framework for metaheuristics, namely ParadisEO (PARAllel and DIStributed Evolving Objects). Our contribution in this project is the extension of the EO (Evolving Objects) framework (this framework, http://paradiseo.gforge.inria.fr, was initially developed by Geneura TEAM (Spain), INRIA (France), LIACS (Netherlands)), which consists in: (i) the generalization of the framework to single solution metaheuristics such as local search, tabu search and simulated annealing; (ii) the design of metaheuristics for multiobjective optimization; (iii) the design of hybrid methods; and (iv) the development of parallel and distributed models.

In this project, our goal is the efficient design and implementation of this framework on different types of parallel and distributed hardware platforms: cluster of workstations (COW), networks of workstations (NOW) and GRID computing platforms, using the different suited programming environments (MPI, Condor, Globus, PThreads). The coupling with well-known frameworks for exact methods (such as COIN) will also be considered. The exact methods for MOPs developed in this project will be integrated in those software frameworks.

The experimentation of this framework by different users and the application outside the DOLPHIN project team are considered. These are done in order to validate the design and implementation issues of ParadisEO.

Validation:

the designed approaches are validated on generic and real-life MOPs, such as:

  • scheduling problems: Flow-shop scheduling problem;
  • routing problems: Vehicle routing problem (VRP), covering tour problem (CTP)...;
  • mobile telecommunications: Design of mobile telecommunications networks (contract with France Telecom R&D) and design of access networks (contract with Mobinets);
  • genomics: Association rule discovery (data mining task) for mining genomic data, protein identification, docking and conformational sampling of molecules.
  • engineering design problems: Design of polymers.

Some benchmarks and their associated optimal Pareto fronts or the best known Pareto fronts have been defined and made available on the Web. We are also developing an open source software, namely GUIMOO (Graphical User Interface for Multi-Objective Optimization), http://guimoo.gforge.inria.fr, which integrates different performance evaluation metrics and 2D/3D visualization tools of Pareto fronts.