Optimisation Combinatoire et Parallélisme
Les travaux auxquels je participe concernent avant tout des problèmes d'Optimisation Combinatoire
difficiles (NP-durs) et la détermination pour ceux-ci de méthodes de résolution efficaces.
Comme pour résoudre ces problèmes difficiles le temps d'exécution devient vite considérable dès
lors que la taille de l'instance s'accroit, le parallélisme constitue alors une arme efficace pour
lutter contre cette explosion combinatoire. L'utilisation du parallélisme induit une algorithmique
spécialisée et de nouveaux problèmes naissent alors de la difficulté d'exploiter pleinement
l'accroissement de la puissance de calcul.

Applications
Nous nous sommes intéressés à la résolution de différents problèmes d'optimisation combinatoire.
Ces travaux ont été sources de nombreuses collaborations, tant universitaires que tournées vers le monde
de l'entreprise.
Nous avons ainsi beaucoup travaillé ces derniers temps sur des problèmes de tournées de véhicules ainsi
que sur des problèmes de dimensionnement de réseau pour des applications Télécom (ces derniers travaux
ont été effectués dans le cadre d'un projet RNRT intitulé ROCOCO). C'est pour un contrat Creco développé
avec l'EDF que nous nous sommes intéréssés à un problème d'affectation linéaire sous contraintes.
Mais c'est indubitablement sur la résolution du problème d'affectation quadratique que nous avons travaillé de
la manière la plus continue. Ceci nous a conduit à apporter de nombreuses solutions efficaces pour ce
problème tant exactes que m\'eta-heuristiques.

Méthodes de résolution
Les cadres méthodologiques que nous avons utilisés ont été divers et ont été employés le plus souvent pour la
résolution concrète d'un problème précis. La détermination de bornes inférieures efficaces a ainsi été étudiée
pour le problème de dimensionnement de réseau et pour le problème d'affectation quadratique.
Des algorithmes ``Branch and Bound'' ont été développés à la fois pour le problème d'affectation quadratique
et pour le problème d'affectation linéaire sous contraintes.
La méthode de génération de colonnes a été utilisée pour les problèmes de tournées. La méthode
métaheuristique ``Scatter Search'' l'a été quant à elle pour le problème d'affectation quadratique.

Mais certains travaux ont également été plus généraux et par là meme plus théoriques, les idées développées se
voulant applicables à un large champ d'applications. C'est le cas par exemple de nos travaux, dans le cadre des
métaheuristiques, sur la définition d'une nouvelle méthode appellée ``Mimausa'' et sur l'étude de nouvelles structures
de voisinage.
 

Quelques publications (liste non complète)

Thèses :
Habilitation à Diriger des Recherches,
``Méta-heuristiques et méthodes exactes pour les problèmes d'optimisation combinatoire difficiles: illustration sur
le problème d'affectation quadratique''          habil ps.gz

Thèse de Doctorat,
``Contribution à la résolution des problèmes d'implantation: algorithmes séquentiels et parallèles pour l'affectation quadratique''

Articles :
T. Mautor,  "Intensification Neighborhoods for Local Search Methods",
Essays and Surveys in Metaheuristics (C. Ribeiro et P. Hansen éditeurs),
Operations Research/Computer Science Interfaces Series, Kluwer, p 493-508, 2001.        fichier.ps.gz

V-D. Cung, S. Dowaji, B. LeCun, T. Mautor and C. Roucairol,
"Concurrent data structures and load balancing strategies for parallel Branch and Bound/A* algorithms",
DIMACS - Series in Discrete Mathematics and Theoretical Computer Science, volume 30, p 141-162, 1997.

B. Mans, T. Mautor and C. Roucairol,
"A parallel depth first search Branch and Bound algorithm for the quadratic assignment problem",
European Journal of Operational Research 81(3) p 617-628, 1995.

T. Mautor and C. Roucairol, "A new exact algorithm for the solution of quadratic assignment problems",
Discrete Applied Mathematics 55, p 281-293, 1994.

T. Mautor and C. Roucairol, "Difficulties of Exact Methods for solving the Quadratic Assignment Problem", 
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 16, p 263-274, 1994.
 

Conférences  internationales récentes :
T. Mautor and E. Naudin, "Another Dantzig-Wolfe decomposition for the Vehicle Routing Problem with capacity and time windows",
SCRO-JOPT-2001, Qu\'ebec, mai 2001.

C. Roucairol, V.D. Cung, P. Hahn, T. Mautor, M. Guignard-Spielberg,
"An Efficient Sequential an Parallel Method Based on Linear Formation: Hahn's Method for the Quadratic Assignment Problem",
17th European Conference on Operational Research (EURO XVII), Budapest, Hongrie, juillet 2000.

V.D. Cung, T. Mautor and C. Roucairol, "Hahn's Method and Lower Bounds Based Linear Formulation for the QAP",
13th Meeting of the European Chapter of Combinatorial Optimization (ECCO XIII),} Capri, Italie, mai 2000.

S. Abdoulaye, T. Mautor and P. Michelon, "Solving  the graph cardinality constrained bipartitioning problem",
IFORS'99, 15th conference of the International Federation of Operational Research Societies, P\'ekin, Chine, aout 1999.

T. Mautor, "New neighborhood structures for Tabu Search",
Third Meta-heuristics International Conference (MIC99), p 323-328, Angra dos Reis, Br\'esil, juillet 1999.

T. Mautor, "Intensification Strategies for the Local Search Methods",
12th meeting of the European Chapter on Combinatorial Optimization (ECCO XII), Ile de Bendor, France, mai 1999.

T. Mautor, P. Michelon and F. Glover, "A neglected meta-heuristic : Referent Domain Optimization",
16th European Conference on Operational Research (EURO XVI), Bruxelles, juillet 1998.

V.D. Cung, T. Mautor and P. Michelon, "Different parallelizations of the Scatter Search method",
16th European Conference on Operational Research (EURO XVI), Bruxelles, juillet 1998.

V.D. Cung, T. Mautor, P. Michelon, A. Tavares, "Improving the efficiency of Scatter Search",
2nd Metaheuristics International Conference (MIC'97), Sophia-Antipolis, France, juillet 1997.

T. Mautor, P. Michelon, "MIMAUSA: a New Local Search Method",
Tenth Meeting of the European Chapter on Combinatorial Optimization (ECCO X), Iles Canaries, Espagne, mai 1997.

V-D. Cung, T. Mautor, P. Michelon and A. Tavares, "A scatter search based approach for the quadratic assignment problem",
IEEE-ICEC'97 (IEEE-International Conference on Evolutionary Computation), p 165-170, Indianapolis, Etats-Unis, avril 1997.