Domaine de recherche
Mes travaux de recherche se rattachent à la recherche
opérationnelle, l'optimisation combinatoire, la
programmation
mathématique, la théorie des graphes et la
complexité des algorithmes. Ces branches de l'optimisation
ont
eu un développement considérable dans les trois
dernières décennies. Plusieurs
méthodes qui y ont
été développées, se sont
révélées efficaces pour
modéliser, analyser
et approcher des problèmes combinatoires (dont la structure
sous-jacente est généralement un graphe) issus de
différents domaines comme par exemple le transport, la
production, les télécommunications, la biologie,
etc. En
particulier les techniques polyèdrales en optimisation
combinatoire ont été utilisées avec
succés
pour résoudre des problèmes difficiles (NP-durs).
Elles
constituent maintenant l'outil de base de la résolution
pratique
de ces problèmes. Ces méthodes permettent en
effet de
ramener un problème d'optimisation combinatoire à
la
résolution d'un programme linéaire par la
description
complète du polyèdre de solutions par un
système
d'inégalités linéaires. Une telle
description est
généralement difficile à obtenir.
Cependant, une
caractérisation partielle du polyèdre,
utilisée
dans le cadre d'une méthode de Branch & Cut (Branch
&
Bound), peut être parfois suffisante pour résoude
le
problème à l'optimum. En effet, ces approches a
permis de
résoudre ces dernières années des
problèmes
de grandes tailles jusque-là insolubles, comme par exemple
le
problème célèbre du voyageur de
commerce. Elles
ont été aussi appliquées efficacement
pour
résoudre des problèmes pratiques de recherche
opérationnelle comme les problèmes de
tournées et
les problèmes de conception de réseaux de
télécommunications.
Mes travaux s'inscrivent dans cette ligne de recherche. Ils concernent
la modélisation et l'étude polyèdrale
et
algorithmique de problèmes de recherche
opérationnelle et
d'optimisation combinatoire, le développement de
méthodes
de résolution de type Branch & Cut pour ces
problèmes
et l'implémentation de ces méthodes.
Mots clés
Optimisation combinatoire,
Programmation mathématique,
Approche polyèdrale,
Graphes et applications,
Conception de réseaux,
Complexité des algorithmes.