Professeur A. Ridha Mahjoub

Recherche


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.