Maître de Conférences Département d'Informatique de Luminy DIL Laboratoire d'Informatique Fondamentale de Marseille LIF Equipe Combinatoire et Recherche Opérationnelle CRO Faculté des Sciences de Luminy Université de la Méditerranée - Aix-Marseille II

Thèse de Doctorat en Informatique

Mots-clés : géométrie algorithmique, optimisation combinatoire, algorithme d'approximation, distance, programmation linéaire, optimalité de Pareto, réseau rectilinéaire.

Soutenue le 12 décembre 2005 à Marseille.

Titre : Enveloppes de Pareto et Réseaux de Manhattan : Caractérisations et Algorithmes.

Jury :

• M. Jean-Daniel Boissonnat (rapporteur), Directeur de recherche INRIA
• M. Andras Sebö (rapporteur), Directeur de recherche CNRS
• M. Gérard Cornuéjols (examinateur), Professeur
• M. Jean-François Maurras (examinateur), Professeur
• M. Victor Chepoi (directeur de thèse), Professeur
• M. Yann Vaxès (co-directeur), Maître de conférences Habilité

Résumé : Dans un espace métrique (R^m,d), l'enveloppe de Pareto d'un nuage de points T est constituée des points de R^m non dominés (un point q de R^m domine un point p de R^m si d(q,t) <= d(p,t) pour tout terminal t de T et si d(q,t') < d(p,t') pour un terminal t' de T ). Les enveloppes de Pareto peuvent être vues comme une extension des enveloppes convexes usuelles dans le sens où ces deux objets géométriques coïncident lorsque d est la distance euclidienne. Elles ont la particularité d'accueillir les solutions optimales d'un grand nombre de problèmes d'optimisation. Dans la première partie de cette thèse, nous caractérisons ces enveloppes dans (R³,d₁) et dans (R^m,d_inf). Nous décrivons également un algorithme de construction optimal dans (R³,d₁) et un algorithme générique permettant de les construire dans R^m pour toute distance issue d'une norme polyédrale. Dans la deuxième partie, nous nous intéressons au problème du réseaux de Manhattan minimal, dont certaines solutions optimales sont contenues dans les enveloppes de Pareto de (R²,d₁). Pour un ensemble de terminaux T de R², un réseau de Manhattan est un réseau dans lequel il existe un plus court chemin rectilinéaire entre chaque paires de terminaux. Un réseau de Manhattan minimal est un réseau de Manhattan de longueur minimale. Ce problème a été formulé en 1999 par Gudmundsson, Levcopoulos et Narasimhan qui ont proposé deux algorithmes d'approximation avec des facteurs 4 et 8. Nous répondons à une de leurs conjectures en proposant deux algorithmes d'approximation avec un facteur 2. Ces deux algorithmes utilisent une formulation en programmation linéaire en nombres entiers du problème.

La document de thèse : THESE_NOUIOUA.pdf

Les transparents de soutenance : SOUTENANCE_NOUIOUA.ppt

Sélection de publications

N. Catusse, V. Chepoi, K. Nouioua et Y. Vaxès (2011).
Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
Algorithmica [pdf].

F. Gardi et K. Nouioua (2011).
Local Search for Mixed-Integer Nonlinear Optimization: A Methodology and an Application.
EvoCOP 2011, European Conference on Evolutionary Computation in Combinatorial Optimisation [pdf].

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

V. Chepoi, K. Nouioua, E. Thiel et Y. Vaxès (2010).
Pareto Envelopes in Simple Polygons.
International Journal of Computational Geometry and Applications [pdf].

B. Estellon, F. Gardi et K. Nouioua (2009).
High-Performance Local Search for Task Scheduling with Human Resource Allocation.
SLS 2009, International Workshop on Engineering Stochastic Local Search Algorithms [pdf].

B. Estellon, F. Gardi et K. Nouioua (2008).
Two local search approaches for solving real-life car sequencing problems.
EJOR, European Journal of Operational Research [pdf].

V. Chepoi, K. Nouioua et Y. Vaxès (2008).
A rounding algorithm for approximating minimum Manhattan networks.
Theoretical Computer Science [pdf].

V. Chepoi et K. Nouioua (2007).
Pareto envelopes in R³ under l₁ and l_inf distance functions.
SoCG 2007, Symposium on Computational Geometry 2007 [pdf].

V. Chepoi, B. Estellon, K. Nouioua et Y. Vaxès (2006).
Mixed covering of trees and the augmentation problem with odd diameter constraints.
Algorithmica [pdf].

B. Estellon, F. Gardi et K. Nouioua (2006).
Large neighborhood improvements for solving car sequencing problems.
RAIRO Operations Research [pdf].

V. Chepoi, K. Nouioua et Y. Vaxès (2005).
A rounding algorithm for approximating minimum Manhattan networks.
APPROX 2005, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems [pdf].

Autres publications et communications

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

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

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

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

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

F. Gardi et K. Nouioua (2011).
Recherche locale haute performance pour la gestion moyen-terme du parc nucléaire français.
ROADEF 2011, Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision [pdf].

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

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

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

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

B. Estellon, F. Gardi et K. Nouioua (2008).
Recherche locale haute performance pour la planification des interventions à France Télécom.
JFPC 2008, Journées Francophones de Programmation par Contraintes [pdf].

B. Estellon, F. Gardi et K. Nouioua (2008).
Recherche locale haute performance.
ROADEF 2008, Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision [pdf].

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

K. Nouioua (2006).
Un algorithme d'approximation de facteur 2 efficace pour le problème du réseau de Manhattan minimal.
ROADEF 2006, Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.

B. Estellon, F. Gardi et K. Nouioua (2005).
Ordonnancement de véhicules : une approche par recherche locale à voisinage large.
JFPC 2005, Journées Francophones de Programmation par Contraintes [pdf].

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

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

V. Chepoi, B. Estellon, K. Nouioua et Y. Vaxès (2005).
Mixed Covering of Trees and the Augmentation Problem with Odd Diameter Constraints.
ICGT'05, International Colloquium on Graph Theory [pdf].

K. Nouioua (2003).
Enveloppes de Pareto en normes l₁ et l_inf : caractérisations, constructions et applications.
ROADEF 2003, Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision.

Distinctions

Premier Prix Application Industrielle de la ROADEF'2011 [site] [résumé] [article]
Prix remis aux meilleures communications présentant des applications industrielles.
F. Gardi et K. Nouioua, Recherche locale haute performance pour la gestion moyen-terme du parc nucléaire français.

Finaliste du Challenge ROADEF'2010 [site]
Problème de gestion d'énergie de grande taille -- EDF
Premier de la phase de qualification

Deuxième Prix du Challenge ROADEF'2007 [site]
Planification d'interventions -- France Télécom

Prix de thèse 2005 de l'Université de la Méditerranée
Enveloppes de Pareto et Réseaux de Manhattan : Caractérisations et Algorithmes

Premier Prix du Challenge ROADEF'2005 [site] [photo] [OR/MS Today]
Catégories Junior et Senior
Ordonnancement de véhicules -- Renault

Téléchargement Licence 3 et Master 1

Programme à compléter pour les TP's (tgz):

Enveloppe convexe Arbre de Steiner Voyageur de commerce ...

Ce programme permet de saisir des points et d'afficher les segments calculés par l'un des algorithmes. Pour cela, il suffit de modifier la méthode static Vector<Segment> algorithme(Vector<Point> points) située dans le fichier Algorithmes.java.

Programme à compléter pour le TP flot max (tgz).

Ce programme permet de saisir des sommets et des arêtes avec capacité puis d'afficher le flot max. Pour cela, il suffit de modifier la méthode static void algorithme(Vector<Sommet> sommets, Vector<Arete> aretes) située dans le fichier Algorithmes.java.

Exemple d'utilisation de GLPK pour le TP sur la couverture d'ensembles :

• Le fichier d'exemple exemple_glpk.tgz
• La librairie GLPK (GNU Linear Programming Kit) glpk-4.11.tar.gz
• Comment exécuter l'exemple ? README_GLPK.txt
• En savoir plus sur GLPK

Coordonnées

LIF - UFR Sciences Luminy,
163 avenue de Luminy,
13288 Marseille Cedex 9, France.

Bureau 611 (TPR2, Entrée G, 6ème étage)
Tél. (+33) 4 91 82 90 76
Fax. (+33) 4 91 82 92 75
Mél. Karim.Nouioua[at]lif.univ-mrs.fr