Cette page n'est pas disponible en français.

ROADEF'2005: Results of the qualification stage and lists of the qualified teams

New rankings:

New rankings of the qualified teams with the new weights and modified formulas taking better into account the gaps between solutions. But this is still NOT THE FINAL EVALUATION FUNCTION though it is closed to (see comments (6) below).

Old rankings:

ATTENTION: Important comments to the qualified teams (updated on May 31st, 2004)

Junior category  (13 qualified teams)

  • Bin HU, Gunnar W. KLAU
    Institute of Computer Graphics and Algorithms, Vienna University of Technology, AUSTRIA.

  • Daniel ALOISE (2) , Thiago NORONHA (2), Caroline ROCHA (1), Sebastián URRUTIA (2), Celso RIBEIRO (1,2)
    (1) Universidade Federal Fluminense, Departamento de Ciéncia da Computação, Niteroi, BRAZIL.
    (2) Pontificia Universidade Catolica do Rio de Janeiro, BRAZIL.

  • Flavio RIBEIRO (1), Renata WASSERMANN (2)
    (1) Dept. of Electronic Engineering of the University of São Paulo, BRAZIL.
    (2) Dept. of Computer Science, Institue of Mathematics and Statistics, University of São Paulo, BRAZIL.

  • Elmir CATRNJA (1), Dean CUPOVIC (1), Emir GANIC (4), Olana HODZIC (1), Adnan KURTOVIC (1),
    Dzenan ZUKIC (1), Tarik HADZIC (3), Vedad LETIC (1), Douglas M. VAN WIEREN (1,3)
    (1) University of Sarajevo, BOSNIA-HEZEGOVIA.
    (2) Sarajevo School of Science and Technology, BOSNIA-HEZEGOVIA.
    (3) IT University of Copenhagen, DENMARK.
    (4) University of Durham, UK.

  • Mathieu NAULT (1), Yannick SOLARI (1), Brigitte JAUMARD (2)
    (1) École Polytechnique de Montréal, CANADA.
    (2) Département d'Informatique et de recherche opérationnelle, Université de Montréal, CANADA.

  • Nicolas ZUFFEREY (1),  Martin STUDER (2)
    (1) University of Calgary, CANADA.
    (2) EPFL, SWITZERLAND.

  • Jeanne DOUCHE (1), Jean-Baptiste FERRAUD(2), Franck TAVERRITI (3), Alain HERTZ (4)
    (1) École Polytechnique de Montréal, Département de génie électrique, CANADA, and Institut National Polytechnique de Grenoble, Département Télécommunications, FRANCE.
    (2) École Polytechnique de Montréal, Département de génie électrique, CANADA, and École Supérieure d'Ingénieurs en Génie Électrique, Rouen, FRANCE.
    (3) École Polytechnique de Montréal, Département de génie électrique, CANADA, and  École des Mines D'Alès, FRANCE.
    (4) École Polytechnique de Montréal, Département de Mathématiques et Génie Industriel, and GERAD, CANADA.

  • Laetitia JOURDAN (2), Margaux ROUSSEL (1), Clarisse DHAENENS (2)
    (1) Génie Informatique et Statistique, Polytech'Lille, FRANCE.
    (2) LIFL, Université de Lille 1, FRANCE.

  • Bertrand ESTELLON, Frédéric GARDI, Karim NOUIOUA
    Laboratoire d'Informatique Fondamentale de Marseille, Université de Marseille, FRANCE.

  • Pierre-François DUTOT, Georges DA COSTA, Lionel EYRAUD
    ID-IMAG, Institut National Polytechnique de Grenoble, FRANCE.

  • Max RISLER, Luis PAQUETE, Tommaso SCHIAVINOTTO, Marco CHIARANDINI, Thomas STUETZLE
    Intellectics Group, Department of Computer Science, Darmstadt University of Technology, GERMANY.

  • Devis Giacomo BONIZZONI, Andrea PINCIROLI
    University of Milano, ITALY.

  • Grzegorz PAWLAK
    Maciej PLAZA, Przemyslaw PIECHOWIAK, Marek RUCINSKI  (G5)
    Institute of Computing Science, Poznan University of Technology, POLAND.

Senior category (11 qualified teams)

  • Haris GAVRANOVIC
    Department of Mathematics, Faculty of Sciences, University of Sarajevo, BOSNIA-HERZEGOVINA.

  • Caroline GAGNE' (1), Marc GRAVEL (1), Christophe JAILLET (2), Michael KRAJECKI (2), Wilson L. PRICE (3)
    (1) Université du Québec à Chicoutimi, CANADA.
    (2) LERI, Université de Reims, FRANCE.
    (3) Faculté des Sciences de l'Administration, Université Laval, Québec, CANADA.

  • Jean-François CORDEAU, Gilbert LAPORTE, Federico PASIN
    HEC Montréal, CANADA.

  • Olivier BRIANT (1), Grégory MOUNIE (2), Denis NADDEF (2)
    (1) Laboratoire MAB, Université Bordeaux 1, FRANCE.
    (2) ENSIMAG-INPG, ID-IMAG, FRANCE.

  • Thierry BENOIST, Eric BOURREAU, Etienne GAUDIN
    e-lab., Bouygues, FRANCE.

  • Yves CASEAU
    Membre honoraire de e-Lab Bouygues, FRANCE.

  • Axel BLOEMEN, THE NETHERLANDS.

  • Eelco KUIPERS, THE NETHERLANDS.
  • Andrzej JASZKIEWICZ, Pawel KOMINEK, Marek KUBIAK
    Institute of Computing Science, Poznan University of Technology, POLAND.

  • Roberto MONTEMANNI
    Instituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), SWITZERLAND.

  • Michel GENDREAU (1,2) Jean-Yves POTVIN (2) et al.
    (1) Centre de Recherche sur les Transports, Montréal, CANADA.
    (2) Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, CANADA.

Important comments to the qualified teams

(1) The evaluation formula presently used reduces the gaps between the candidates' ratings though these gaps exist.
Thus, for the final stage, we will use another evaluation formula in order to better reflect these gaps.

As soon as the new formula is defined by the organizing committee, we will provide the new rankings of all the qualified teams on the data set A allowing the qualified teams to appreciate the new formula's ranking.

(2) For the final stage, we will provide soon (mid-June) the data set B allowing the qualified teams to better tune their programs.

The data sets B and X will be harder than the data Set A "pushing the programs to the limits".
The number of instances in the data sets B and X will be increased in order to represent all the factories of RENAULT.

(3) The weights (coefficents) of the objectives are presently (10000, 100 and 1), but they can not completely guarantee the non balance between the objectives. This did not change the rankings of the qualification stage.
For the final stage, the weights will be respectively 1000000, 1000 and 1.

(4) Several programs had some weird behaviors (runtime errors, no respect to the maximal paint batch length) on a new and unknown data instance we used to test the programs.

  • Bloemen the program does not stop
  • Dutot solution invalid: paint color batch too long
  • Gavranovic the program crashes
  • Gravel the program crashes
  • Jourdan the program does not stop
  • Klau solution invalid: paint color batch too long
  • Naddef the program does not generate a solution (log : "Meilleure solution trouvee : aucune.")
  • Nault the program crashes
  • Pawlak solution invalid: paint color batch too long
  • Ribeiro solution invalid: paint color batch too long

This unknown data instance could be found here DOU_EP_RAF_ENP_chA.zip (for Windows) and DOU_EP_RAF_ENP_chA.tar.gz (for Linux).
This unknown data instance has the following characteristics: the cars of the day D-1 have the same color and they are not subject to any ratio constraints.

After checking with a candidate the reason why their program has this behavior, it comes out that their program uses the solution provided by RENAULT as initial solution. Since the unknown data instance is not a solution, their program generated a unexpected error.
Thus, please to note the data set X will have instances like this unknown one since the data set X will contain instances coming from RENAULT's factories and these instances will not be solutions.

(5) On student travel expense supports and the following sentence on this challenge home page:

  • "French OR society ROADEF would support part of the travel expenses to the conference ROADEF'2005 for the students who reach the final stage".

The junior teams should read:

  • "French OR society ROADEF would support part of the travel expenses to the conference ROADEF'2005 for the students who reach the final stage and finish this challenge as winner or 2nd or 3rd".

These student supports, which are not part of the prizes, are given on motivated requests (e.g. from a remote country).
This was the case for the previous challenges. Thank you for understanding that since the French OR society is a nonlucractive association, so these supports are generally low, around 450 euros maximum per junior team.

(6) Comparison between the old and the new evaluation functions:

The old evaluation:

  • For each instance and each candidate, compute the mark with the weights of the objectives (the best candidates have the lower marks):
    mark=objective_1_value*10000 + objective_2_value*100 + objective_3_value
  • For each candidate and each data series, compute the average of the candidate's marks on different instances.
  • For each candidate and each data series, compute the candidate's weighted mark according to the following formula:
    (candidate_mark- worst_candidate_mark_on_the_series) / (best_candidate_mark_on_the_series - worst_candidate_mark_on_the_series)
  • The global mark of the candidate is the average of the weighted marks obtained over the three data series.
  • Ranking on the global marks.

Drawbacks of this evaluation: the objectives are not completely without compensation due to the weights. The averages reduce the gaps and give favor to the instances with high objective values. The high 1st objective value reduces the gap between candidates having the same 1st objective value.

The improved evaluation:

weights over the objectives : 1000000, 1000 and 1 =;> the objectives are guaranteed to be without compensation.

  • For each instance and each candidate,compute the mark with the weights of the objectives (the best candidates have the lower marks):
    mark=objective_1_value*1000000 + objective_2_value*1000 + objective_3_value
  • For each candidate and each instance, compute the corrected mark of the candidate: corrected_mark=mark - best_candidate_objective_1_value_on_the_instance*1000000
  • For each candidate and each instance,  compute the candidate's weighted mark according to the following formula:
    (corrected_mark - worst_candidate_corrected_mark) / (best_candidate_corrected_mark - worst_candidate_corrected_mark)
  • Compute the candidate's global mark as the average of the candidate's weighted marks of the instances.
  • Ranking on the global marks.

We computed as well, for indication only, the rankings for each series of instances.

The main idea of this improved evaluation is to compute a gap for each instance, and then the average of the gaps. The advantages of this improved evaluation are the guarantee of the non compensation between objectives, same importance for each instance, and the gaps between candidates better presented.

Though this improved evaluation function is better and fairer, IT IS NOT THE FINAL ONE, we can still improve it a little bit.

The final evulation function will be detailed with its related rankings soon.