lipn

Laboratoire d'Informatique de Paris Nord

UMR 7030, Université Paris 13, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse

up13 cnrs

Discours de Gérard Plateau, Université Paris 13, le 13 décembre 2005

Nelson 008

Nelson 066

Nelson 057

Nelson 070

Nelson 055

Je voudrais d'abord dire quelques mots sur la discipline de recherche de prédilection du professeur Nelson Maculan : l'optimisation combinatoire. Elle aborde des problèmes consistant à optimiser un objectif (par ex., maximiser des revenus ou minimiser des coûts) en tenant compte de contraintes (souvent très nombreuses) liées à des ressources humaines et matérielles (par ex., limitation en main d'œuvre, en investissement, en espace, en temps,…). Il peut même exister des contraintes logiques (par ex., la mise en fabrication d'un nouveau produit nécessite un réglage de la machine, dans le cadre d'un problème d'ordonnancement : une tâche doit être réalisée impérativement avant une autre). Les inconnues (dites variables) à déterminer sont très souvent à valeurs entières (par ex., nombre de machines à utiliser, nombre de tâches à réaliser, nombre d'heures de travail, quantité de personnel). Les variables de décision à valeurs 0 ou 1 ont également une place importante en traduisant la réponse oui ou non vis-à-vis de projets potentiels à réaliser.

La difficulté de ces problèmes peut s'illustrer par le modèle le plus simple qui soit dans notre domaine : le problème dit du sac à dos qui consiste à remplir un sac de la meilleure manière qui soit avec des objets naturellement en surnombre (sinon il n'y aurait pas de problème). Ainsi connaissant la taille et la valeur de chaque objet et la capacité du sac, il faut déterminer le lot d'objets rentrant dans le sac et qui possède la plus grande valeur possible. On pourrait se dire qu'envisager toutes les possibilités et garder la meilleure d'entre elles est une méthode rapide. Malheureusement, pour 50 objets seulement, cette méthode consisterait à envisager plus d'un million de milliards de solutions ce qui prendrait plus de 3 ans pour un ordinateur standard.

La recherche menée par Nelson Maculan consiste donc à apporter des réponses théoriques et algorithmiques, impliquant une mise en œuvre informatique, et également des modélisations judicieuses à des problèmes dont la nature est des plus concrètes : par exemple pour cette cérémonie, les quelques problèmes que je vais citer sont du ressort de l'optimisation combinatoire :

  • Pour les organisateurs : il a fallu résoudre entre autres des problèmes de planification, d'ordonnancement et d'affectation des participants à leur place,
  • Quant aux récipiendaires, ils ont pris l'avion pour venir à Paris ; cela suppose que chaque compagnie aérienne avait résolu beaucoup de problèmes d'optimisation : combien de places dans l'avion allouées aux différentes catégories (économique, affaire, …) de façon à optimiser son chiffre d'affaires ? Par quels vols l'équipage continuera sa rotation après le vol de Paris, de manière à minimiser les temps d'attente entre les vols ? Par où et par qui faire transiter les bagages pour minimiser l'attente ?
J'arrête là cette énumération qui est loin d'être exhaustive et je reviens à notre fameux problème de sac à dos qui m'a donné la chance de rencontrer mon ami le professeur Nelson Maculan en 1981 à Hambourg au cours d'un congrès fédérant l'ensemble des sociétés nationales de recherche opérationnelle (IFORS) au sein de laquelle l'optimisation combinatoire tient une place importante. Je travaillais à cette époque sur des méthodes de résolution de ce problème de sac à dos qui intéressait Nelson dans le traitement des problèmes de découpe de câbles téléphoniques pour réaliser l'expansion du réseau de télécommunications de Rio de Janeiro. Ce furent ainsi les prémices de notre longue collaboration.

Après ce préambule, je ne vais pas trop m'étendre sur les relations de Nelson Maculan avec la France qu'il aime tant, et en particulier avec l'université Paris 13 où il a effectué de nombreux séjours depuis la création il y a 20 ans du LIPN, notre laboratoire d'informatique de Paris Nord. D'un commun accord, je lui laisserai le soin d'en parler plus longuement.

Laissez-moi vous dire simplement combien sa collaboration a été fructueuse pour les chercheurs du LIPN :
-Il a co-dirigé trois thèses de doctorat à l'université Paris 13 ;
-Il a été à de nombreuses reprises membre de jurys et président de thèses ou d'habilitations à diriger des recherches soutenues à Paris 13 ;
-Il a participé à des enseignements de troisième cycle ainsi qu'à des encadrements de stages (en DEA IA & OC et en formation d'ingénieurs de l'institut Galilée) ;
-De nombreuses publications ont été réalisées en commun dont 6 en revues ou ouvrage et plusieurs conférences nationales et internationales.

J'ajouterai que Nelson a aussi séjourné au LIPN pendant toute l'année 2001-2002 sur un poste de directeur de recherche associé au CNRS. Il a par ailleurs permis le financement de stages de longue durée pour des chercheurs brésiliens au LIPN, favorisé la venue au laboratoire de doctorants brésiliens inscrits à Paris 13 et prodigué de nombreux et précieux conseils aux membres du LIPN avec une générosité sans égal.

Je vais désormais esquisser en quelques minutes la brillante carrière universitaire de Nelson et les facettes de sa recherche qui font qu'il a été plébiscité par notre laboratoire pour recevoir cette distinction de docteur honoris causa de l'université Paris 13.

D'abord je me dois de préciser la diversité des thèmes de recherche qu'a abordés Nelson Maculan tout au long de sa carrière, dans ce domaine très vaste de la recherche opérationnelle. En voici la liste : la programmation linéaire et non linéaire ainsi que l'optimisation globale, ceci en variables continues, entières ou mixtes, l'optimisation stochastique, l'optimisation sur les graphes, les heuristiques et les méta-heuristiques.

La richesse de sa culture lui a permis d'apporter des contributions originales à la fois théoriques et algorithmiques dans chacune de ces spécialités. Nombre de ses résultats sont des références pour les chercheurs de notre communauté.

Ne pouvant tous les citer, j'en ai sélectionné trois qui parmi d'autres font la notoriété de Nelson Maculan au niveau mondial :

  • Le premier, dans le domaine de la théorie de la dualité, est la conception d'une nouvelle décomposition lagrangienne appelée aussi substitution lagrangienne, qui permet de détecter en temps raisonnable, une borne de qualité pour les problèmes d'optimisation non linéaire
  • Le deuxième, dans le domaine de l'algorithmique, est son travail novateur sur la génération de colonnes pour les problèmes linéaires en nombres entiers de grande taille qui se posent par exemple dans les problèmes de transport aériens ou ferroviaires.
  • Le troisième, dans le domaine des problèmes académiques traités dans la littérature, est la résolution des problèmes euclidiens de Steiner à plusieurs dimensions pour lesquels l'expertise de Nelson est unique. Par exemple dans le domaine de la conception de réseaux de télécommunication, ce problème consiste à placer des émetteurs (appelés points de Steiner) au milieu d'un nuage d'autres points représentant la clientèle à couvrir, de sorte que l'ensemble des liaisons de communication ait la forme d'un arbre dont la somme des longueurs des branches est minimal.

L'optimisation combinatoire étant une discipline appliquée, Nelson Maculan est également expert dans un large panel d'applications, dont le dimensionnement des réseaux de télécommunications, les problèmes de découpe et la planification sont les plus emblématiques.

Nelson Maculan a une production scientifique de tout premier ordre : 5 livres, près de 70 articles de revues parmi les plus renommées, 20 articles dans des ouvrages, près de 40 actes de congrès). Il a de surcroît une activité d'encadrement doctoral des plus importantes (45 thèses soutenues à ce jour et plus d'une centaine de mémoires de master).

Depuis sa nomination en 1971, comme professeur en optimisation à l'institut de mathématiques et à la COPPE (école d'ingénieurs en informatique) de l'université fédérale de Rio de Janeiro, il a occupé plusieurs fonctions de direction dont la responsabilité suprême de recteur (président) de cette université de 90 à 94.

En plus de sa forte implication dans le développement de la recherche brésilienne en informatique et en mathématiques appliquées depuis plus de 30 ans, il a toujours joué un rôle fédérateur au sein de la communauté scientifique latino-américaine (par des présidences de sociétés scientifiques brésiliennes et latino-américaines, par des fonctions d'éditeur ou co-éditeur de revues de recherche opérationnelle). Encore plus largement, son action s'est étendue au niveau international par de nombreuses activités éditoriales de revues, la vice-présidence de la fédération de l'ensemble des sociétés nationales de recherche opérationnelle. Enfin en 2006, il présidera à Rio de Janeiro l'organisation de la plus grande rencontre internationale triennale de programmation mathématique.

Il faut également souligner la multitude d'invitations fécondes en Europe, au Canada, aux USA, au Japon et en Amérique latine, qui est un gage supplémentaire de sa reconnaissance dans la communauté internationale.

L'ampleur de ses activités scientifiques lui a valu plusieurs distinctions dont une médaille de l'ordre national brésilien pour la recherche en 2002. En France, il a été fait chevalier de l'ordre des palmes académiques en 98. Au Pérou, il est docteur honoris causa de l'université San Marcos à Lima depuis 2004. Il est également membre de l'Académie brésilienne des sciences et de l'Académie européenne des sciences, des arts et des lettres dont le siège est à Paris. Je termine naturellement par la reconnaissance suprême, c'est-à-dire la nomination toute récente (en février 2004) au poste de secrétaire national pour l'éducation supérieure du Brésil.

Je sais que malgré ses lourdes tâches assurément exaltantes, son activité débordante lui permet de se réserver encore quelques plages de travail pour poursuivre ses travaux de recherche.

Ce diplôme de docteur honoris causa de l'université Paris 13 vient donc couronner une relation exceptionnelle de Nelson Maculan avec le LIPN et l'université Paris 13, mais surtout un grand scientifique mondialement renommé qui est aussi exceptionnel, et là je me fais l'interprète de tout le laboratoire, pour sa disponibilité, son humilité, son ouverture d'esprit et sa très grande générosité.

Je suis sincèrement très heureux et très fier d'avoir eu le privilège de rendre ce trop court hommage à Nelson Maculan avec qui les relations sont devenues depuis longtemps, le mot n'est pas trop fort, vraiment fraternelles.

pres

w3c-xhtml