# 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).**

- Junior category: global_ranking.txt (for a glance on the results), junior_rankings.zip (for the detailed results)
- Senior category: global_ranking.txt (for a glance on the results), senior_rankings.zip (for the detailed results)
- All categories of the qualified teams: global_ranking.txt (for a glance on the results), global_rankings.zip (for the detailed results)

## Old rankings:

- Junior category: global_ranking.txt (for a glance on the results), junior_rankings.zip (for the detailed results)
- Senior category: global_ranking.txt (for a glance on the results), senior_rankings.zip (for the detailed results)
- All categories of the qualified teams: global_ranking.txt (for a glance on the results), rankings.zip (for the detailed results)

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.