LocalSolver
Frédéric Gardi
Vice President Products at Innovation 24, subsidiary of Bouygues
Product Manager of LocalSolver

President of the French Operations Research and Decision Support Society (ROADEF)
Member of the Comité National de Recherche Scientifique (CoNRS), section Computer Science (06)

Research


Started 10 years ago, my activities in "operational research" focus on varied problems and business areas : workforce scheduling, financial planning, car sequencing, vehicle routing, marketing campaign planning, TV media planning, energy management, construction site planning (buildings, roads, railways), maintenance planning for large infrastructures. Parallel to my operational research activities in enterprise (see my curriculum vitae for more details), I pursue a basic and applied research activity in combinatorial optimization. After a PhD thesis devoted to issues related to workforce and job scheduling mixing algorithmics and graph theory [5, 9, 11, 12, 15, 16, 17], I have worked on problems arising in banking, and more particularly in real-estate financial planning [7, 13]. Since then, I have focused much of my research on local search techniques for combinatorial and mixed-variable optimization [2, 4, 6, 8, 10, 14] and their integration into a mathematical programming solver [3, LocalSolver]. I also pursue the study of fundamental questions extracted from the concrete problems encountered in business (see for example [1]).

Since 2004, we draw with Bertrand Estellon and Karim Nouioua the outlines of a methodology to tackle systematically combinatorial optimization problems by local search, in particular large-scale real-life problems. This methodology advocates a pure (without hybridization) and direct (without decomposition) approach, even for mixed-variable problems with discrete and continuous decision variables. Contrary to the idea now prevalent that "local search = metaheuristics", our methodology focuses on the diversification by the moves and on the performance of the evaluation machinery behind these moves. In this way, we would say that "local search = diversified neighborhoods + incremental algorithmics" (by "diversified", we mean multiple, variable-size, and rich). Our methodology also provide keys to ensure the quality of a software based on local search (reliability, maintainability). Ultimately, this one aims at industrializing the design and engineering of optimization software based on local search, numerous in industry, in order to reduce their development, integration and maintenance costs (while increasing their performances). This methodology has been successfully applied during several operational projects with high economic stakes, particularly at Bouygues e-lab [2, 4], as well as during several international OR competitions (2005, 2007, 2010 ROADEF Challenges) [6, 8, 10, 14]. Some of the developed software, today operational, offers significant returns on investment.

In 2007 I initiated a research project to develop a model-and-run solver for combinatorial optimization based on the local search paradigm. Relying on a suitable declarative formalism, the user models his problem and the solver resolves it autonomously by local search. Hence, we seek to fill gaps in classical tree-search solvers, powerless against large-scale highly-combinatorial problems. A team has rallied around this project: Thierry Benoist, Bertrand Estellon, Karim Nouioua, as well as Romain Megel and Julien Darlay. Our software LocalSolver [3], operational since the end of 2009, allows to solve in minutes some combinatorial optimization problems that integer or constraint programming cannot resolve within reasonable running times. Since 2012, LocalSolver is commercialized by Innovation 24, subsidiary of the Bouygues Group, in partnership with Aix-Marseille University and CNRS (LIF Marseille). Nevertheless, this one remains free for teaching and non-profit research. Now, we are working with the team to develop LocalSolver toward a generalized, all-in-one, hybrid mathematical programming solver based on neighborhood search for large-scale, real-world mixed-variable non-convex optimization. The 4.0 release of LocalSolver is a first step in this way.

The following monograph provides a synthesis of our works on local search and mathematical programming:

F. Gardi, T. Benoist, J. Darlay, B. Estellon, R. Megel (2014).
Mathematical Programming Solver based on Local Search.
FOCUS Series in Computer Engineering, ISTE Wiley, 112 pages.
ISBN 9781848216860

Below are some short communications which give a good overview of our works:

International Federation of Operational Research Societies (IFORS) Newsletter, September 2013, pp. 19-20.
Integrating local search techniques into a mathematical programming solver

Bulletin of the French Operations Research Society (ROADEF), Number 28, Spring-Summer 2012.
La RO, c'est quoi : des théorèmes ou des logiciels ? (in French)

Bulletin of the French Operations Research Society (ROADEF), Number 27, Autumn-Fall 2011.
LocalSolver: de la recherche locale en programmation mathématique (in French)

Awards


1st Junior and Senior Prize of 2005 ROADEF Challenge (with Bertrand Estellon and Karim Nouioua), awarded by the French Operations Research Society (ROADEF) and the companies EURODECISION and RENAULT, for the best software for sequencing cars in RENAULT plants (55 participating teams from 15 countries, 12 finalists from 7 countries: Bosnia-Herzegovina, Brazil, Canada, France, Germany, Netherlands, Poland).

    Excerpt from the ROADEF newsletter
    Excerpt from the Aix-Marseille II University newsletter
    Excerpt from the magazine OR/MS Today
    Excerpt from the magazine Industrie et Technologies

2nd Senior Prize of 2007 ROADEF Challenge (with Bertrand Estellon and Karim Nouioua), awarded by the ROADEF and the companies EURODECISION, FRANCE TELECOM and ILOG, for the best software for scheduling maintenance interventions on the FRANCE TELECOM network (35 participating teams, 11 finalists).

Finalist of 2009 ROADEF Challenge (with Bertrand Estellon), organized by the ROADEF and the company AMADEUS, on disruption management for commercial aviation (29 participating teams, 9 finalists).

Finalist of 2010 ROADEF/EURO Challenge (with Karim Nouioua), organized by the ROADEF and the company EDF, on medium-term management of the French thermal power park (44 participating teams from 25 countries, 16 finalists from 11 countries). Ranked 1st on instances A (qualification stage) and on instances B (final stage).

1st Prize for "Industrial Applications" at ROADEF 2011 (with Karim Nouioua), yearly meeting of the French Operations Research Society, for the communication "High-performance local search for the mid-term management of the French nuclear power park".

Finalist of 2012 ROADEF/EURO Challenge (with the LocalSolver team), organized by the ROADEF and the company GOOGLE, on the reassignment of processes to machines (82 participating teams coming from 33 countries, 30 finalists). LocalSolver qualified for the final round with 25th: the LSP model, developed in 1 day of work, lies over 100 lines.

2012 Robert Faure Prize, awarded every 3 years by the ROADEF, to a young researcher under 35. This prize awards an original contribution in the field of operations research. A particular attention is given to works which couple the development of theoretical methods to applications, in the spirit of the works of Professor Robert Faure, pioneer in Operations Research in France.

Finalist of 2012 EURO Excellence in Practice Award (with Thierry Benoist and Antoine Jeanjean), awarded by the Association of European Operational Research Societies (EURO). Selected among 6 finalists over 56 submissions (without geographical limit) for our paper "Lessons learned from 15 years of operations research for French TV channel TF1" in Interfaces. This prize awards some exceptional works in the practice of operations research, trhough a recent paper describing an original application of OR, in methodology, application, or engineering.

Publications

Books

F. Gardi, T. Benoist, J. Darlay, B. Estellon, R. Megel (2014).
Mathematical Programming Solver based on Local Search.
FOCUS Series in Computer Engineering, ISTE Wiley, 112 pages.
ISBN 9781848216860

Selective international journals and conferences

[1]  B. Estellon, F. Gardi (2013).
Car sequencing is NP-hard: a short proof.
Journal of the Operational Research Society 64(10), pp. 1503-1504. [pdf]

[2]  T. Benoist, F. Gardi, A. Jeanjean (2012).
Lessons learned from 15 years of operations research for French TV channel TF1.
Interfaces 42(6), pp. 577-584. [pdf]

[3]  T. Benoist, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2011).
LocalSolver 1.x: a black-box local-search solver for 0-1 programming.
4OR, A Quarterly Journal of Operations Research 9(3), pp. 299-316. [pdf]

[4]  T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2011).
Randomized local search for real-life inventory routing.
Transportation Science 45(3), pp. 381-398. [pdf] (extended version [pdf])

[5]  F. Gardi (2011).
On partitioning interval graphs into proper interval subgraphs and related problems.
Journal of Graph Theory 68(1), pp. 38-54. [pdf]

[6]  F. Gardi, K. Nouioua (2011).
Local search for mixed-integer nonlinear optimization: a methodology and an application.
In Proceedings of EvoCOP 2011, the 11th European Conference on Evolutionary Computation in Combinatorial Optimisation
(P. Merz, J.-K. Hao, eds.), Lecture Notes in Computer Science 6622, pp. 167-178.
Springer, Berlin, Germany. [pdf]

[7]  F. Gardi (2010).
Optimisation de plans de financement immobiliers.
RAIRO Operations Research 44(3), pp. 207-239. [pdf] (extended version [pdf])

[8]  B. Estellon, F. Gardi, K. Nouioua (2009).
High-performance local search for task scheduling with human resource allocation.
In Proceedings of SLS 2009, the 2th International Workshop on Engineering Stochastic Local Search Algorithms
(T. Stützle, M. Birattari, H.H. Hoos, eds.), Lecture Notes in Computer Science 5752, pp. 1-15.
Springer, Berlin, Germany. [pdf] [pdf]

[9]  F. Gardi (2009).
Mutual exclusion scheduling with interval graphs or related classes. Part I.
Discrete Applied Mathematics 157(1), pp. 19-35. [pdf]

[10]  B. Estellon, F. Gardi, K. Nouioua (2008).
Two local search approaches for solving real-life car sequencing problems.
In Special Issue: The Car Sequencing Problem (C. Solnon, V.D. Cung, A. Nguyen, C. Artigues, eds.),
European Journal of Operational Research 191(3), pp. 928-944. [pdf]

[11]  F. Gardi (2008).
Mutual exclusion scheduling with interval graphs or related classes. Part II.
Discrete Applied Mathematics 156(5), pp. 794-812. [pdf]

[12]  F. Gardi (2007).
The Roberts characterization of proper and unit interval graphs.
Discrete Mathematics 307(22), pp. 2906-2908. [pdf]

[13]  F. Gardi, A. David (2007).
Optimisation de plans de financement immobiliers : de la recherche opérationnelle en actuariat bancaire.
Bulletin Français d'Actuariat 7(13), pp. 107-121. [pdf]

[14]  B. Estellon, F. Gardi, K. Nouioua (2006).
Large neighborhood improvements for solving car sequencing problems.
In Special Issue: Journées Francophones de Programmation par Contraintes 2005 (F. Fages, N. Jussien, C. Solnon, eds.),
RAIRO Operations Research 40(4), pp. 355-379. [pdf]

[15]  F. Gardi (2006).
Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms.
4OR, A Quarterly Journal of Operations Research 4(1), pp. 87-90. [pdf]

[16]  F. Gardi (2004).
On partitioning interval and circular-arc graphs into proper interval subgraphs with applications.
In Proceedings of LATIN 2004, the 6th Latin American Symposium on Theoretical Informatics
(M. Farach-Colton, ed.), Lecture Notes in Computer Science 2976, pp. 129-140.
Springer, Berlin, Germany. [pdf]

[17]  F. Gardi (2003).
Efficient algorithms for disjoint matchings among intervals and related problems.
In Proceedings of DMTCS 2003, the 4th International Conference on Discrete Mathematics and Theoretical Computer Science
(C.S. Calude, M.J. Dinneen, V. Vajnovszki, eds.), Lecture Notes in Computer Science 2731, pp. 168-180.
Springer, Berlin, Germany. [pdf]

International conferences

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2014).
LocalSolver 4.0: hybrid math programming.
In INFORMS 2014 Conference on Business Analytics and Operations Research.
Boston, US-CA. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2013).
Mathematical programming by local search.
In OR55, the Annual Conference of the Operations Research Society.
Exeter, UK. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2013).
LocalSolver: toward a full mathematical programming solver based on local search.
In OR 2013, the International Conference on Operations Research.
Rotterdam, The Netherlands. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2013).
LocalSolver: toward a full mathematical programming solver based on local search.
In EURO 2013, the 26th International Symposium on Mathematical Programming.
Roma, Italy. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2013).
Mathematical programming by local search.
In ECCO XXVI, the 26th Conference of the European Chapter on Combinatorial Optimization.
Paris, France. [ppt] [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2012).
LocalSolver: a mathematical programming solver based on local search.
In ISMP 2012, the 21th International Symposium on Mathematical Programming.
Berlin, Germany. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2012).
ROADEF/EURO/Google Challenge: how a 100-line LocalSolver model qualifies for the final round.
In EURO 2012, the 25th European Conference of Operational Research.
Vilnius, Lithuania. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2012).
LocalSolver: black-box local-search for combinatorial optimization.
In EURO 2012, the 25th European Conference of Operational Research.
Vilnius, Lithuania. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2012).
LocalSolver: black-box local-search for combinatorial optimization.
In 2012 Optimization Days. Montreal, Canada. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2012).
LocalSolver: black-box local search for combinatorial optimization.
In 16th Aussois Combinatorial Optimization Workshop (organized by F. Margot, D. Naddef, L. Wolsey).
Centre Paul Langevin, Aussois, France. (invited) [pdf]

T. Benoist, F. Gardi, A. Jeanjean (2012).
Optimization of advertisement revenue for the French TV group TF1.
In EURO 2012, the 25th European Conference of Operational Research.
Vilnius, Lithuania. [pdf]

F. Gardi (2012).
High-performance local search for TV media planning on TF1.
In EURO 2012, the 25th European Conference of Operational Research.
Vilnius, Lithuania. [pdf]

T. Benoist, B. Estellon, F. Gardi, A. Jeanjean, K. Nouioua (2011).
Local search for mixed-integer nonlinear optimization: methodology and applications.
In EDF Workshop on Advanced Optimisation Methods and their Applications to Unit Commitment in Energy Management.
Clamart, France. [pdf] [pdf]

T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2010).
Recherche locale pour un problème d'optimisation de tournées de véhicules avec gestion des stocks.
In Proceedings of MOSIM 2010, the 8th International Conference of Modeling and Simulation
(A. Hadj-Alouane, H. Pierreval, eds.). Hammamet, Tunisia. [pdf]

T. Benoist, B. Estellon, F. Gardi, K. Nouioua (2010).
Toward Local Search Programming: LocalSolver 1.0.
In EURO 2010, the 24th European Conference of Operational Research.
Lisbon, Portugal. [pdf]

T. Benoist, B. Estellon, F. Gardi, K. Nouioua (2010).
Toward local search programming: LocalSolver 1.0.
In CPAIOR 2010 Workshop : Open Source Tools for Constraint Programming and Mathematical Programming.
Bologna, Italy. [pdf]

F. Gardi, K. Nouioua (2010).
High-performance local search for a large-scale energy management problem.
In EURO 2010, the 24th European Conference of Operational Research.
Lisbon, Portugal. [pdf]

T. Benoist, B. Estellon, F. Gardi, S. Jain, A. Jeanjean, E. Patay (2009).
Inventory routing optimization for bulk gas transportation.
In INFORMS 2009, Annual Meeting. San Diego, US-CA. [pdf]

T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2009).
High-performance local search for solving real-life inventory routing problems.
In Proceedings of SLS 2009, the 2th International Workshop on Engineering Stochastic Local Search Algorithms
(T. Stützle, M. Birattari, H.H. Hoos, eds.), Lecture Notes in Computer Science 5752, pp. 105-109.
Springer, Berlin, Germany. [pdf]

F. Gardi (2004).
A sufficient condition for optimality in mutual exclusion scheduling for interval graphs and related classes.
In Abstracts of PMS 2004, the 9th International Workshop on Project Management and Scheduling
(A. Oulamara, M.-C. Portmann, eds.), pp. 154-157. Nancy, France. [pdf]

National conferences

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2014).
LocalSolver 4.0 : programmation mathématique hybride.
In Journées SMAI-MODE 2014, Mathématiques de l'Optimisation de la Décision.
Rennes, France. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2014).
LocalSolver 4.0 : nouveautés et benchmarks.
In Actes de ROADEF 2014, le 15ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Bordeaux, France. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2014).
LocalSolver: a new kind of math programming solver.
In 9th Paris Machine Learning Meetup.
Paris, France. [pdf]

F. Gardi (2013).
Toward a mathematical programming solver based on neighborhood search.
In ORO 2013, Workshop on Optimization in Operations Research.
Nantes, France. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel (2013).
Vers un solveur de programmation mathématique généralisée basé sur la recherche locale.
In Actes de ROADEF 2013, le 14ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Troyes, France. [pdf] [pdf]

J.-Y. Lucas, D. Marcel, T. Benoist, F. Gardi, R. Megel (2013).
Une modélisation LocalSolver pour le placement des assemblages combustibles en piscine.
In Actes de ROADEF 2013, le 14ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Troyes, France. [pdf]

T. Benoist, J. Darlay, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2012).
LocalSolver 2.0 : premier solveur de programmation mathématique fondé sur la recherche locale.
In Actes de ROADEF 2012, le 13ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Angers, France. (semi-plenary talk) [pdf]

F. Gardi (2012).
C'est quoi la RO : des théorèmes ou des logiciels ?
In Actes de ROADEF 2012, le 13ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Angers, France. (semi-plenary talk) [pdf]

T. Benoist, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2011).
LocalSolver : un solveur boîte noire a base de recherche locale pour l'optimisation combinatoire.
In JFRO 2011, la 25ème Journée Francilienne de Recherche Opérationnelle : Recherche Opérationnelle et Intelligence Artificielle.
Paris, France. (invited talk) [pdf]

T. Benoist, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2011).
LocalSolver 1.x : un solveur boîte noire à base de recherche locale pour la programmation 0-1.
In Actes des JFPC 2011, les 7ème Journées Francophones de Programmation par Contraintes.
Lyon, France. [pdf]

T. Benoist, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2011).
Vers une programmation par recherche locale : LocalSolver 1.1.
In Actes de ROADEF 2011, le 12ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Saint-Étienne, France. [pdf] [pdf] [video] [video]

T. Benoist, B. Estellon, F. Gardi, R. Megel, K. Nouioua (2011).
Génération automatique de voisinages de grande taille pour la recherche locale autonome.
In Actes de ROADEF 2011, le 12ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Saint-Étienne, France. [pdf]

F. Gardi (2011).
Recherche locale haute performance pour la résolution d'un problème riche de tournées d'inventaires.
In 5ème Journée du GT Transport-Logistique du GdR Recherche Opérationnelle du CNRS.
Paris, France. (invited plenary talk) [pdf]

F. Gardi, K. Nouioua (2011).
Recherche locale haute performance pour la gestion moyen-terme du parc nucléaire français.
In Actes de ROADEF 2011, le 12ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Saint-Étienne, France. (1st Prize for Industrial Apllications) [pdf]

T. Benoist, B. Estellon, F. Gardi, K. Nouioua (2010).
Vers une programmation par recherche locale : LocalSolver.
In Actes de ROADEF 2010, le 11ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
Toulouse, France. [pdf]

T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2009).
Algorithme de recherche locale pour la résolution d'un problème réel de tournée d'inventaires.
In JOR 2009, la 4ème Journée de Recherche Opérationnelle et Optimisation dans les Réseaux.
Paris, France. [pdf]

T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2009).
Recherche locale haute performance pour l'optimisation des livraisons de gaz industriels par camions-citernes.
In Actes de ROADEF 2009, le 10ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 49-50. Nancy, France. [pdf]

F. Gardi (2009).
Composition optimale d'équipes d'athlétisme.
In Actes de ROADEF 2009, le 10ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 81-82. Nancy, France. [pdf]

B. Estellon, F. Gardi, K. Nouioua (2008).
Recherche locale haute performance pour la planification des interventions à France Télécom.
In Actes des JFPC 2008, les 4èmes Journées Francophones de Programmation par Contraintes,
pp. 69-78. Nantes, France. [pdf]

B. Estellon, F. Gardi, K. Nouioua (2008).
Recherche locale haute performance.
In Actes de ROADEF 2008, le 9ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 189-190. Clermond-Ferrand, France. [pdf]

F. Gardi, T. Benoist (2008).
Programmation de campagnes publicitaires sur les chaînes thématiques du groupe TF1.
In Actes de ROADEF 2008, le 9ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 203-204. Clermond-Ferrand, France. [pdf]

B. Estellon, F. Gardi, K. Nouioua (2007).
Une heuristique à base de recherche locale pour la planification de tâches avec affectation de ressources.
In ROADEF 2007, le 8ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Grenoble, France. [pdf]

F. Gardi, A. David (2006).
Optimisation de plans de financements immobiliers.
In Actes des JFPC 2006, les 2èmes Journées Francophones de Programmation par Contraintes,
pp. 167-172. Nîmes, France. [pdf]

F. Gardi, A. David (2006).
Optimisation de plans de financements immobiliers.
In Actes de ROADEF 2006, le 7ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.
Lille, France. [pdf]

B. Estellon, F. Gardi, K. Nouioua (2005).
Ordonnancement de véhicules : une approche par recherche locale à voisinage large.
In Actes des JFPC 2005, les 1ères Journées Francophones de Programmation par Contraintes,
pp. 21-28. Lens, France. [pdf]

B. Estellon, F. Gardi, K. Nouioua (2005).
Ordonnancement de véhicules dans les usines Renault : une approche par recherche locale à voisinage large.
In Actes de ROADEF 2005, le 6ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 33-34. Tours, France. [pdf]

B. Estellon, F. Gardi, K. Nouioua (2005).
Ordonnancement de véhicules dans les usines Renault : une approche par recherche locale à voisinage réduit.
In Actes de ROADEF 2005, le 6ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 35-36. Tours, France. [pdf]

F. Gardi (2003).
Planification d'horaires de travail et colorations de graphes.
In Actes de GRM 2003, les 1ères Journées Graphes, Réseaux et Modélisation.
Paris, France. [pdf]

F. Gardi (2003).
Planification d'horaires de travail et théorie des graphes.
In Actes de ROADEF 2003, le 5ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision,
pp. 99-100. Avignon, France. [pdf]

Habilitation thesis


Title: Toward a mathematical programming solver based on local search.

Date and place of defense: November 25th 2013 at Université Pierre et Marie Curie, Paris.

Jury: Keywords: combinatorial optimization, local/neighborhood search, mathematical programming.

Abstract:

This dissertation deals with local search for combinatorial optimization and its extension to mixed-variable optimization. Our goal is to present local search in a new light. Although not yet understood from the theoretical point of view, local search is the paradigm of choice to tackle large-scale real-life optimization problems. Today end-users ask for interactivity with decision support systems. For optimization software, it means obtaining good-quality solutions quickly. Fast iterative improvement methods, like local search, are suited to satisfy such needs.

When a solution space is gigantic, a complete search becomes unpractical. Given a (possibly infeasible) solution to the problem, local search consists in modifying some parts of this one - that is, some decision variables - to reach a new, hopefully better solution. Exploring a so-called neighborhood of the incumbent has a major advantage: the new solution can be evaluated quickly through incremental calculation. Then, local search can be viewed as an incomplete and nondeterministic but efficient way to explore a solution space.

First, an iconoclast methodology is presented to design and engineer local search algorithms. We show that the performance of a local search mainly relies on the richness of the neighborhoods explored, as well as on the efficiency of their exploration. Ultimately, implementing high-performance local search algorithms is a matter of expertise in incremental algorithmics and of dexterity in computer programming. Our concern to industrialize local search approaches shall be of a particular interest for practitioners. As examples, this methodology is applied to solve two industrial problems with high economic stakes.

Nevertheless, software applications based on local search induce extra costs in development and maintenance in comparison with the direct use of mixed-integer linear programming solvers. We present the LocalSolver project whose goal is to offer the power of local search through a model-and-run solver for large-scale 0-1 nonlinear programming. Having outlined its modeling formalism, the main ideas on which LocalSolver relies are described and some benchmarks are presented to assess its performance. We conclude the dissertation by presenting our ongoing and future works on LocalSolver toward a full mathematical programming solver based on neighborhood search.

The dissertation was edited as a monograph:

F. Gardi, T. Benoist, J. Darlay, B. Estellon, R. Megel (2014).
Mathematical Programming Solver based on Local Search.
FOCUS Series in Computer Engineering, ISTE Wiley, 112 pages.
ISBN 9781848216860

The slides of the presentation in French: [pdf]

PhD thesis


Title: Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms.

Date and place of defense: June 14th 2005 at the Luminy Faculty of Sciences, Marseille.

Jury: Keywords: mutual exclusion scheduling, graph coloring, workforce planning, interval graphs, classes of graphs.

Abstract:

The mutual exclusion scheduling problem can be formulated as follows in graph-theoretic terms: given an undirected graph G and an integer k, determine a minimum coloring of G such that each color is used at most k times. When the graph G is an interval graph, this problem has some applications in workforce planning. Then, the subject of this thesis is to detail the complexity of the mutual exclusion scheduling problem for interval graphs and related classes.

The first two chapters of the thesis deal with the complexity of the problem for interval graphs, as well as two extensions, circular-arc graphs and tolerance graphs. When the problem is proved to be polynomial, we propose some simple and efficient algorithms for its resolution (in particular linear time and space algorithms).

Motivated by practical aspects, we also analyse the impact of the following property on the complexity of the problem: the graph G admits a coloring such that each color appears at least k times. We show that if an interval graph satisfies this property, then it admits an optimal partition into n/k stable sets of size at most k which can be computed in linear time and space. Then, this assertion is extended to claw-free graphs, circular-arc graphs, as well as chordal graphs for k <= 4.

The last chapter is devoted to partition problems related to interval graphs. We investigate particularly the problem of partitioning interval ou circular-arc graphs into proper interval subgraphs, for which the following proposition is established: any interval graph admits a partition into less than O( log n) proper interval graphs and this one can be computed in O(n log n + m) time and linear space. This result is used in the design of polynomial approximation algorithms for a workforce planning problem related to mutual exclusion scheduling for interval or circular-arc graphs.

The manuscript in French: [pdf]
The slides of the presentation in French: [ppt] [pdf]

Publications:

The main results of my thesis have been announced in the following note:

F. Gardi (2006).
Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms.
4OR, A Quarterly Journal of Operations Research 4(1), pp. 87-90. [pdf]

From my thesis have been published the 4 following papers which contain some updated proofs:

F. Gardi (2007).
The Roberts characterization of proper and unit interval graphs.
Discrete Mathematics 307(22), pp. 2906-2908. [pdf]

F. Gardi (2008).
Mutual exclusion scheduling with interval graphs or related classes. Part II.
Discrete Applied Mathematics 156(5), pp. 794-812. [pdf]

F. Gardi (2009).
Mutual exclusion scheduling with interval graphs or related classes. Part I.
Discrete Applied Mathematics 157(1), pp. 19-35. [pdf]

F. Gardi (2011).
On partitioning interval graphs into proper interval subgraphs and related problems.
Journal of Graph Theory 68(1), pp. 38-54. [pdf]

Education


November 2013. Habilitation in Computer Science from Université Pierre et Marie Curie (Sorbonne Universités).
Thesis: "Toward a mathematical programming solver based on local search". ISBN 9781848216860
Reviewers: Prof. Michel Gendreau, Prof. Jin-Kao Hao, Dr. Geir Hasle.

June 2005. Ph.D. in Computer Science from Aix-Marseille II University.
Thesis: "Ordonnancement avec exclusion mutuelle par un graphe d'intervalles ou d'une classe apparentée : complexité et algorithmes". [pdf]
Advisor: Prof. Michel Van Caneghem. Reviewers: Prof. Dominique De Werra, Dr. Frédéric Maffray. Summa cum laude.

June 2001. M.Sc. in Computer Science from Aix-Marseille II University, major Discrete Structures and Operations Research.
Thesis: "Sur certains problèmes de planification d'horaires de travail". [pdf]
Advisor: Prof. Michel Van Caneghem. Magna cum laude.

June 2000. B.Sc. in Computer Science from Luminy Faculty of Sciences, Aix-Marseille II University.
Thesis: "Étude de la complexité de quelques variantes de l'algorithme de tri Quicksort". [pdf]
Advisor: Prof. Michel Van Caneghem. Magna cum laude.

Academic activities


I am:
I was:

I was qualified to the position of Lecturer (2006-2010) by the section 27 of CNU. I make most of my teaching activities at the Luminy Faculty of Sciences of the Aix-Marseille University. I also speak as part of operations research courses given by Frédéric Meunier at École Nationale des Ponts et Chaussées, by Marie-Christine Costa at École Nationale Supérieure des Techniques Avancées (ENSTA ParisTech), by Nadia Brauner at École Nationale Supérieure de Génie Industriel (Grenoble INP), by Sana Berraf-Belmokhtar at École d'ingénieurs de la Chambre de commerce et d'industrie de Paris (ESIEE Paris). Here is a sample of the courses that I have given: "Introduction to computer science and computer programming", "Turing: from secret codes to universal machines", "Local search: methodology and industrial applications", "Industrial applications in operations research". Overall, I have completed 300 hours of teaching for various student audiences.

Since my arrival at Bouygues e-lab in 2007, I have mentored several brilliant students during their graduation internship: Thibaud Cavin (ENSIMAG, Grenoble), Lucile Robin (École Centrale de Lyon), Saul Pedraza Morales (École des Mines de Nantes), Romain Megel (École des Mines de Nantes), Sofia Zaourar (ENSIMAG, Grenoble), Boris Prodhomme (École Polytechnique, Palaiseau), Clément Pajean (ENSTA, Palaiseau). In addition, I mentored several students for the Fondation Francis Bouygues. From 2008 to 2011, I supervised, with Philippe Baptiste (LIX, Palaiseau) and Thierry Benoist (Bouygues e-lab), the PhD thesis of Antoine Jeanjean (Bouygues e-lab & LIX) entitled "Local search for mixed-variable optimization: methodology and industrial applications" (defended the October 10th, 2011 at École Polytechnique, Palaiseau).

The manuscript of Antoine Jeanjean's thesis, in French: [pdf]
The slides of Antoine Jeanjean's presentation, in French: [pdf]

I was a member of various scientific committees: the Young Researchers Prize at ROADEF 2012 and ROADEF 2013, the stream "OR applications and software" at ROADEF 2014, the program of PGMO-COPI 2014, the program of ROADEF 2015. I was a scientific expert for the French National Research Agency (ANR) and the Fonds québécois de la recherche sur la nature et les technologies (FQRNT). I was examiner of the PhD thesis of Ariel Waserhole.

I was a reviewer for some national (JFPC, ROADEF) and international (AISC-Calculemus 2002, LAGOS 2009) conferences, for the international journals Algorithmica, Computers and Industrial Engineering, Discrete Mathematics, Discrete Applied Mathematics, European Journal of Operational Research, Information Processing Letters, Journal of Graph Theory, Journal of Mathematical Modelling and Algorithms in Operations Research, Journal of Scheduling, Journal of the Operational Research Society, OR Spectrum, as well as for the Mathematical Reviews.

I participated in the European project IST-2001-35304 AMETIST (Advanced Methods for Timed Systems), for which I have written 5 research reports. In addition to the conferences mentioned above, I was invited to present my works in several research seminars: LIF (Marseille), G-SCOP (Grenoble), Bouygues e-lab (Paris) [pdf], LIX (Palaiseau), EDF R&D/OSIRIS (Clamart) [pdf].

Contact

Innovation 24
264 rue du Faubourg Saint-Honoré
75008 Paris, France



+33 (0)9 72 31 98 43

Last update: May 2014

[css] [xhtml]