group during RAMOO2015

The Operations research and multi-objective optimization group

The Group
With the recruitments of Xavier Gandibleux in 2004 as full professor in Computer Science by the University of Nantes, followed by Anthony Przybylski in 2007 as senior lecturers in Computer Science, the core of the group consists of two permanent members. From 2006 to 2008, Matthias Ehrgott has been permanent member of the group as director of research at the CNRS.

Non-permanent members are involved in the group for some periods. Sana Belmokhtar (from Ecole des Mines de Saint-Etienne) has joined us as researcher in 2006-2007. She is now assistant professor at  ESIEE PARIS. Hadrien Hugot (from LAMSADE, University of Paris-Dauphine) got in 2007-2008 a post-doctoral position funded by the CNRS. Benoit Guédas and Guillaume Pinot (both from IRCCyN, Ecole Centrale de Nantes) have been associated to the group while they served as lecturer in the department. Zohra Aoudia (from Université de Bejaia) has joined us for a period of 18 months.

Master and PhD students contribute to the works of the team. Currently Quentin Delmée is preparing its PhD thesis and another PhD student will joint us soon. Former PhD students who prepared their thesis under our supervision are Xavier Delorme (now professor, Ecole des Mines de Saint Etienne), Anthony Przybylski (now assistant professor, University of Nantes), Fabien Degoutin, Julien Jorge, Benoit Guédas, Hugo Fouchal, Aurélien Mérel, Thomas Vincent, and Audrey Cerqueus (now assistant professor, Ecole des Mines de Saint Etienne).
Research Activities
Our work, mainly based on discrete optimisation in Operations Research, focuses on the accumulation of knowledge towards the development of advanced optimization methods that are capable of solving complex optimization problems in reasonable time. The optimization problems of interest are reference problems in discrete optimization and their application in socio-economic contexts, such as railway transportation (capacity of railway infrastructure), and communication networks (routing policies, deployment of new infrastructure).

In this context, the motivation characterizing the research direction of the group is to study, model, and solve large scale multiobjective (mixed) integer optimization problems. Procedures for these problems are essentially problem dependent and employ, among others, efficient enumerative methods (two phase method; branch and bound/cut) or hybrid optimization techniques (multiobjective metaheuristics and exact algorithms). Our research directions are:
  1. Fundamental:
    Study, characterization, and understanding of (mixed) integer and combinatorial multiobjective optimization problems.
  2. Methodological and algorthmical:
    New techniques and methods for the solution of large scale (mixed) integer and combinatorial multiobjective optimization problems; Development of algorithms to improve the efficient solution of NP-hard single and multiobjective problems.
  3. Validation and verification:
    Application to real world multiobjective optimization problems with the ultimate goal of being able to solve concrete problems in complex real world environments (production systems, transport, communication, environmental policy). Most applications are collaborations with industrial partners such as Alcatel, France Telecom, SNCF.
Some Results of Our Work
  • State of the Art Annotated Bibliographic Survey.
    For many years we collected and summarized the literature on multi-objective combinatorial optimization (MOCO) problems. In 2000 and in 2002, papers reporting our synthesis have been published. Later we did a similar work about multi-objective metaheuristics (MOMH).

    M. Ehrgott, X. Gandibleux (2000). A Survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22(4): 425-460.
  • Path-relinking for multi-objective optimization.
    Approximation methods for MCDM problems have received a lot of attention in recent years. With two Japanese colleagues we introduced the path-relinking concept for MOMH with success for many MOCO problems.

    X. Gandibleux, H. Morita, and N. Katoh (2004). Evolutionary operators based on elite solutions for bi-objective combinatorial optimization. Chapter 23 in Applications of Multi-Objective Evolutionary Algorithms (C. Coello Coello and G. Lamont Eds.), pp. 555-579. Advances in Natural Computation Vol. 1, World Scientific, Singapore.
  • Two phase method for MOCO problems.
    Introduced in the nineties by Ulungu and Teghem, this method has been considered as a generic method for bi-objective optimization problems. One of the major contributions Anthony Przybylski's PhD thesis has been the generalisation of this method for dealing with problems with more than two objectives.

    A. Przybylski (2006) Méthode en deux phases pour la résolution exacte de problèmes d'optimisation combinatoire comportant plusieurs objectifs : nouveaux développements et application au probléme d'affectation linéaire. PhD thesis, University of Nantes, December 2006 (In French).
  • Exact and efficient procedures for solving the linear assigment problem with two and three objectives.
    Considered as a fundament optimization problem, we proposed algorithms for the exact solution. They have been demonstrated to be the most efficient algorithms considering the literature available.

    A. Przybylski, X. Gandibleux and M. Ehrgott (2008). Two-phase algorithms for the bi-objective assignment problem. European Journal of Operational Research 185(2):509-533
  • Railway infrastructure capacity.
    The question investigated here can be stated as follows: «How many trains can go through a junction or a station?». With the cooperation of partners we developed methodologies, algorithms and software dealing with this question. The case studies are real situations from the SNCF (France) and the DB (Germany) networks.

    J. Rodriguez, X. Delorme, X. Gandibleux, Gr. Marlière, R. Bartusiak, F. Degoutin, and S. Sobieraj (2007). RECIFE: models and tools for analyzing rail capacity. Recherche Transports Sécurité, 95:19-36.
Some Major Events Involving the Group Members
The members of the group have been involved in several international scientific events, four of which are immediately related to the MCDM field.
  1. MOMH 2002:
    Multiple Objective Metaheuristics International Workshop, November 4-5, 2002, Paris - France
  2. MOPGP 2006:
    7th International Conference on Multi-Objective Programming and Goal Programming, June 12-14, 2006, Loire Valley (Tours), France
  3. MCDM 2008:
    19th International Conference on Multiple Criteria Decision Making, January 07 - 12, 2008, Auckland, New Zealand
  4. EMO 2009:
    5th International Conference on Evolutionary Multi-Criterion Optimization. April 07-10, 2009, Nantes, France
At the national level, the French Working Group dedicated to Multiple-Objective Programming (PM2O) has been co-founded on 1999 by Xavier Gandibleux. He has served as the coordinator of this group for four years.
Visitors and Collaborators
Invited professors who visited us these last years for a period of one month were Kathrin Klamroth in 2005 (University of Erlangen-Nuremberg, Germany), Eric Taillard in 2006 (HEIG-VD, Switzerland), Margaret Wiecek in 2007 (Clemson University, USA), and Eckart Zitzler (ETH Zürich, Switzerland). The group also hosts visiting PhD students: Daniel Salazar Aponte from University Las Palmas de Gran Canaria (6 months from Sept 2005) and Andrea Raith from Auckland University (3 months from August 2007). If you are interested in visiting us, please contact us.

We have a long tradition of working with colleagues in OR and MCDM. Several collaborations are on-going with Matthias Ehrgott (Lancaster University, UK), Stefan Ruzika (University of Koblenz, Germany), Kathrin Klamroth (Bergische Universität Wuppertal, Germany), Karl Doerner (Johannes Kepler Universität Linz, Austria), Sophie Parragh (University of Vienna, Austria), Dario Da Silva (University of Nottingham, UK), Naoki Katoh (Kyoto University, Japan) and Hiroyuki Morita (Osaka Prefecture University, Japan) to name a few.

Since 1999 we are involved in research works related to railway transportation. Joaquin Rodriguez (from IFSTTAR, the French National Research Institute on Transportation and Security) is one of our collaborators on this topic.

To conclude this section, we are collaborating also with colleagues of regional institutions: Fabien Lehuédé (Ecole des Mines de Nantes), Philippe Dépincé (Ecole Centrale de Nantes), Frédéric Saubion (University of Angers) and Marc Sevaux (University of South Brittany-Lorient).
The group is strongly involved in a large regional project called LigeRO since the regional council « Pays de la Loire » has recognized « Operations Research » as a prioritized research theme. In associating the regional research groups in optimization inside this project, it represents a significant task force in the west of France.
RECIFE is a decision support system specifically designed for the analysis of railway infrastructure capacity. For a given station or node of the network, various functionalities such as verifying the feasibility of expected traffic, studying infrastructure saturation and stability of resulting timetables are offered to a decision maker. Two geographical situations have already been studied: The Pierrefitte-Gonesse node located north of Paris and the Lille-Flandres station.
Some References
  1. M. Ehrgott, C.M. Fonseca , X. Gandibleux, J.-K. Hao, M. Sevaux (editors). Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science 5467. Springer, 2009.
  2. V. Barichard, M. Ehrgott, X. Gandibleux and V. T'kindt (editors). Multi-Objective Programming and Goal Programming. Lecture Notes in Economics and Mathematical Systems 618. Springer, 2009.
  3. M. Ehrgott, J. Figueira, X. Gandibleux (editors). Multiobjective Discrete and Combinatorial Optimization. Annals of Operations Research 147. 2006.
  4. J. Figueira, S. Greco, M. Ehrgott (editors). Multiple Criteria Decision Analysis. State of the Art Surveys. International Series in Operations Research and Management Science 78. Berlin, Springer, 2005.
  5. M. Ehrgott. Multicriteria Optimization. Second edition. Berlin, Springer, 2005.
  6. X. Gandibleux, M. Sevaux, K. Sörensen and V. T'kindt (editors). Meta-heuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems 535. Berlin, Springer, 2004.
  7. M. Ehrgott and M. Luptacik (editors). 16th International Conference on Multiple Criteria Decision Making. Journal of Multi-Criteria Decision Analysis 12(1) 2003.
  8. M. Ehrgott and X. Gandibleux (editors). Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey. International Series in Operations Research and Management Science 52. Boston, Kluwer 2002.
  9. X. Gandibleux, A. Jaszkiewicz, A. Fréville, and R. Slowinski (guest editors). Special issue ``Multiple Objective MetaHeuristics''. Journal of Heuristics 6(3) 2000.
To Contact Us:
Université de Nantes
UFR Sciences / Département informatique
2, rue de la Houssinière BP 92208
F-44322 Nantes Cedex 03 - FRANCE

Picture: Participants to RAMOO'2015 that our group has organized in Nantes.