HDR Fr
Forum 'Annonces' - Sujet créé le 2013-10-11 par Frédéric Gardi
J'ai le plaisir de vous inviter à la soutenance de mon Habilitation à diriger des recherches qui se tiendra :
le lundi 25 novembre à 14 h
à l'Université Pierre et Marie Curie (UPMC, Paris 6)
salle 211 - tour 55 - couloir 55/65 - 2ème étage
Plan d'accès
Vous êtes également invités au cocktail qui suivra. Ci-dessous vous trouverez quelques informations relatives au sujet abordé. Le manuscrit peut être téléchargé ici.
Title: Toward a mathematical programming solver based on local search.
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 softwares, 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, softwares 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 local search.
Keywords: combinatorial optimization, local search, mathematical programming.
Jury:
- Mr. Philippe Baptiste (examiner), Strategy & Innovation Director, MESR/DGRI
- Mr. Yves Caseau (examiner), Executive Vice President, Bouygues Telecom
- Mr. Philippe Chrétienne (examiner), Professor of Computer Science, Université Pierre et Marie Curie
- Mr. Gérard Cornuéjols (examiner), Professor of Operations Research, Carnegie Mellon University
- Mr. Michel Gendreau (reviewer), Professor of Operations Research, École Polytechnique de Montréal
- Mr. Jin-Kao Hao (reviewer), Professor of Computer Science, Université d'Angers
- Mr. Geir Hasle (reviewer), Chief Research Scientist, SINTEF ICT
- Mr. Marc Sevaux (examiner), Professor of Computer Science, Université de Bretagne-Sud
Vous pouvez retrouver ces informations ainsi que le manuscrit sur ma page personnelle : http://pageperso.lif.univ-mrs.fr/~frederic.gardi.
Au plaisir de vous retrouver le 25 novembre.
Cordialement,
Frédéric Gardi
Innovation 24 & LocalSolver
fgardi@innovation24.fr | fgardi@localsolver.com | +33 1 44 20 11 06 | +33 6 77 82 37 87
www.innovation24.fr | www.localsolver.com | 24 avenue Hoche 75008 Paris
le lundi 25 novembre à 14 h
à l'Université Pierre et Marie Curie (UPMC, Paris 6)
salle 211 - tour 55 - couloir 55/65 - 2ème étage
Plan d'accès
Vous êtes également invités au cocktail qui suivra. Ci-dessous vous trouverez quelques informations relatives au sujet abordé. Le manuscrit peut être téléchargé ici.
Title: Toward a mathematical programming solver based on local search.
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 softwares, 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, softwares 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 local search.
Keywords: combinatorial optimization, local search, mathematical programming.
Jury:
- Mr. Philippe Baptiste (examiner), Strategy & Innovation Director, MESR/DGRI
- Mr. Yves Caseau (examiner), Executive Vice President, Bouygues Telecom
- Mr. Philippe Chrétienne (examiner), Professor of Computer Science, Université Pierre et Marie Curie
- Mr. Gérard Cornuéjols (examiner), Professor of Operations Research, Carnegie Mellon University
- Mr. Michel Gendreau (reviewer), Professor of Operations Research, École Polytechnique de Montréal
- Mr. Jin-Kao Hao (reviewer), Professor of Computer Science, Université d'Angers
- Mr. Geir Hasle (reviewer), Chief Research Scientist, SINTEF ICT
- Mr. Marc Sevaux (examiner), Professor of Computer Science, Université de Bretagne-Sud
Vous pouvez retrouver ces informations ainsi que le manuscrit sur ma page personnelle : http://pageperso.lif.univ-mrs.fr/~frederic.gardi.
Au plaisir de vous retrouver le 25 novembre.
Cordialement,
Frédéric Gardi
Innovation 24 & LocalSolver
fgardi@innovation24.fr | fgardi@localsolver.com | +33 1 44 20 11 06 | +33 6 77 82 37 87
www.innovation24.fr | www.localsolver.com | 24 avenue Hoche 75008 Paris