Finale du Challenge ROADEF'2001 à Québec
Van-Dat CUNG (PRiSM-UVSQ) et Thierry DEFAIX (CELAR-DGA)
Si le 10 mai 2001 est une date remarquée dans l'histoire contemporaine
française, depuis, elle est devenue certainement aussi une date
mémorable pour l'ensemble des participants de la phase finale du
Challenge ROADEF'2001 ! Pour cette édition, le sujet proposé
par le CELAR de la Délégation Générale pour
l'Armement (DGA) est intitulé " Affectation de Fréquences
avec Polarisations ".
Presque jour pour jour depuis le lancement du challenge, et après un an de travaux de recherche et trois phases de tests, six équipes ont été sélectionnées parmi les 27 initialement déclarées (2 brésiliennes, 2 canadiennes, 17 françaises, 1 espagnole, 1 indienne, 1 polonaise, 1 suisse, 1 turque, 1 américaine) et ces six finalistes ont été invités à présenter (enfin !) leurs travaux dans deux sessions dédiées (JE-A7 et JE-B7) de la conférence FRANCORO III. Cette manifestation a lieu cette année à la ville de Québec de "la Belle Province" canadienne. La session JE-A7 du matin était consacrée aux exposés des équipes Senior, alors que la session JE-B7 de l'après-midi l'était à ceux des équipes Junior. L'ensemble des six équipes - trois en catégorie Junior et trois en catégorie Senior - ont répondu à cette invitation. Une équipe Junior non finaliste a également été conviée à cette présentation. La liste des équipes se trouve ci-après avec les classements finaux.
Le jury composé de Maurice Diamantini (ENSTA), François Fages (INRIA), Benoît Rottembourg (Bouygues), Fédéric Roupin (IIE-CNAM), Thierry Defaix (CELAR-DGA) et Van-Dat Cung (PRiSM-UVSQ) est représenté par ces trois derniers cités pendant les présentations. Les autres membres n'ont malheureusement pas pu être présents pour des raisons professionnelles. Les équipes présentes ainsi que le jury ont énormément regretté le retour anticipé du représentant de l'équipe canadienne du GERAD/CRT, Michel Gendreau, pour raison familiale.
Le ton scientifique et convivial de la journée est donné dès le premier exposé de la session Senior. Des échanges d'idées très fructueux entre les finalistes et le jury ont eu lieu pendant et après les exposés des intervenants. L'ordre des présentations des Seniors est Michel Vasquez (LGI2P, Ecole des Mines d'Alès), puis Yves Caseau (e-Lab, Bouygues SA). En raison de l'absence de l'équipe canadienne, Benjamin Weinberg (équipe Junior non finaliste, LIFL, Univ. de Lille 1) a accepté de présenter dans cette session. Les membres du Jury ont été impressionnés par la simplicité et surtout l'efficacité de la méthode de M. Vasquez, et ils ont énormément apprécié les nombreuses expériences positives et négatives qu'Y. Caseau a pu tester avec le " peu " de temps qu'il a consacré à ce Challenge.
Thierry Defaix a exposé
à la fin de cette séance l'ensemble des critères d'évaluation
et la méthode que le Jury a pris en compte pour établir un
classement le plus impartial que possible. Suivant ces critères
(valeur de la solution trouvée, nombre de contraintes non satisfaites,
etc.), chaque équipe obtient une note sur 10, moyennée sur
les 44 instances proposées successivement dans les 3 phases du Challenge
(cf. tableau récapitulatif ci-après).
Pour la session des équipes Junior, les membres du Jury ont beaucoup apprécié le caractère " professionnel " des présentations malgré la jeunesse des participants. De plus, on a pu noter des idées inattendues et " rafraîchissantes " émergeant des présentations. Dans l'ordre de passage, on peut citer Haris Gavranovic (Doctorant IMAG et Université de Sarajevo), Nicolas Zufferey (Doctorant EPFL) et F. Buscaylet, P. Dru, F. Faure, F. Pernias (Etudiants en fin de cycle d'IUP d'Avignon).
Les méthodes de résolution utilisées peuvent se résumer à une dominance quasi totale de la Recherche Tabou (RT) hybridée avec la Programmation Par Contrainte (PPC). La raison principale invoquée par les équipes est la durée du calcul limitée à une heure sur une machine de référence (Pentium III, 500Mhz, 128Mo). Le Jury regrette qu'il n'y ait pas eu de méthodes à base de " population " comme par exemple des Algorithmes Génétiques ou des Systèmes de Fourmis.
Le classement " brut " établi par le Jury du Challenge est donc le suivant :
Nous devons mentionner que ces résultats sont obtenus sur
une seule et même machine de référence au CELAR.
Dans la catégorie Junior, le Jury a deux prix à distribuer : le 1er prix parrainé par le CELAR-DGA et le second parrainé par la société EuroDécision. Si H. Gavranovic est le vainqueur incontestable du 1er prix de cette catégorie, le second prix est plus disputé entre les équipes de Lausanne et d'Avignon et discuté au sein même du Jury. La moyenne sur 10 (note entre parenthèses) et le total des places donnent un avantage à l'équipe de Lausanne, mais les résultats de la phase 3 qui ont été menés sur des instances tenues secrètes aux équipes ont montré la robustesse du code de l'équipe d'Avignon vis à vis de celui de l'équipe de Lausanne. De plus, le Jury a apprécié les preuves plus importantes sur des bornes inférieures apportées par l'équipe avignonaise. Comme l'un des buts de ce challenge est d'encourager un nombre toujours croissant de chercheurs " débutants " de travailler dans ce domaine et sur des applications industrielles en particulier, le Jury a décidé de décerner un second prix ex æquo pour les équipes de Lausanne et d'Avignon.
Le 1er prix dans la catégorie Senior, parrainé par le CELAR-DGA, est aussi très disputé entre les équipes Senior d'une part, mais aussi avec le Junior H. Gavranovic. D'après les conditions de ce Challenge, une équipe Junior pouvait gagner les deux prix s'il s'avère que ses résultats sont les meilleurs toutes catégories confondues. Cela ne fut pas le cas, mais on peut noter l'excellente moyenne de H. Gavranovic ainsi que ses deux deuxièmes places pendant les phases 2 et 3 du Challenge. Il mérite de préciser que la moyenne finale n'est pas la moyenne des 3 notes des phases, mais de toutes les instances de données. Les 3 notes n'ont donc pas les mêmes coefficients. Le 1er prix de la catégorie Senior est finalement revenu à M. Vasquez de l'Ecole des Mines d'Alès. Il n'y a pas de second prix dans cette catégorie.
Classements finaux
Premier prix
Au vu des résultats obtenus et l'enthousiasme des équipes finalistes, nous pouvons raisonnablement penser que le Challenge ROADEF'2001, deuxième édition du nom après celui de 1999 à Autrans (Grenoble), a encore une fois atteint les deux objectifs visés :
Nos remerciements vont d'abord à T. Defaix pour le travail formidable qu'il a mené sur la rédaction du sujet ainsi que pour le suivi et les tests (44 heures par finaliste rien que sur la phase 3) qu'il a réalisés pendant cette année du Challenge. Que soient remerciés les membres du Jury pour avoir été particulièrement actifs pendant les différentes phases du Challenge et nous espérons avoir été aussi objectif que possible.
Nous sommes également très reconnaissants aux différents parrains - le CELAR-DGA, la société EuroDécision et la ROADEF - d'avoir accepté de financer les prix décernés aux vainqueurs ainsi que certains frais de déplacement des équipes finalistes Junior.
Que soient associées à ces remerciements toutes les personnes ayant encouragé et soutenu de près ou de loin cette initiative et sans qui ce Challenge n'aurait pas lieu. En particulier nous pouvons citer les membres du comité international et les organisateurs locaux de FRANCORO III (messieurs Jean-Marc Martel et Adel Guitouni) ainsi que le bureau de la ROADEF.
Enfin, en vous donnant Rendez-Vous pour le prochain Challenge ROADEF'2003, encore un grand Merci et Bravo aux équipes participantes !
NB : des informations complémentaires peuvent être trouvées sur les sites du Challenge (PRiSM, ENSTA) via le site de la ROADEF (www.roadef.org).