Résultats des qualifications

La table suivante présente les candidats qualifiés et donne le classement obtenu sur la base du score normalisé moyen calculé comme suit. Si z(M,I) est la valeur de l'objectif trouvee par la méthode M sur l'instance I, zb(I) et zw(I) sont respectivement les meilleures et pires valeurs trouvées sur cette instance, le score normalisé de M sur I est donné par (zw(I)-z(M,I))/(zw(I)-zb(I)). Pour la qualification, le jury a tenu compte, en plus des résultats expérimentaux, de l'originalité des méthodes proposées.

Equipe Catégorie Rang Score Moyen
Bisaillon, Cordeau, Laporte, Pasin Senior 1 98,53
Hanafi, Wilbaut, Mansi Senior 2 94,87
Acuna-Agost, Michelon, Feillet, Gueye Senior 3 85,52
Darlay, Kronek, Schrenk, Zaourar Junior 4 82,12
Jozefowiez, Mancel, Mora-Camino Senior 5 75,29
Eggermont, Firat, Hurkens, Modelski Junior 6 61,80
Demassey, Jussien, Lorca, Menana-Quillet, Richaud Senior 7 53,58
Dickson, Smith, Li Junior 8 47,82
Estellon, Gardi, Nouioua Senior 9 47,05
Eggenberg, Salani Junior 10 2,93
Peekstok, Kuipers Senior 11 5 solutions non réalisables

La table ci-dessous présente les résultats détaillés des candidats sur les instances de la base A en donnant pour chaque instance la valeur obtenue pour l'objectif. La meilleure solution est indiquée en gras. INF signifie que la solution retournée par la méthode est irréalisable.

Equipe A01 A02 A03 A04 A05 A06 A07 A08 A09 A10
Bisaillon, Cordeau, Laporte, Pasin 29891,75 116431,70 202358,10 139747,10 3717376,35 44305,05 202247,75 659572,00 215482,35 7210166,90
Hanafi, Wilbaut, Mansi 28155,60 126684,70 131694,60 523678,808092977,55 71355,25 245696,70 329521,85 1096303,85 17166321,75
Acuna-Agost, Michelon, Feillet, Gueye 44938,40 374763,75 672790,35 108081,9016134976,15 86283,00 452752,85 1065896,20 187144,40 20892659,25
Darlay, Kronek, Schrenk, Zaourar 317525,05 765351,40 438681,05 789399,058012044,00 269462,00 546110,00 799238,00 938095,80 15098771,00
Jozefowiez, Mancel, Mora-Camino 150095,70 377992,90 473992,15 2520586,0013640667,40 111540,50 623236,80 997137,80 6163295,90 23840247,85
Eggermont, Firat, Hurkens, Modelski 987236,15 770971,35 1588231,40 1573294,5023990055,70 1032790,50 834044,65 1559644,90 1478106,60 29639201,15
Demassey, Jussien, Lorca, Menana-Quillet, Richaud 158485,35 540895,65 567124,65 4842154,7041037750,05 125286,85 634489,95 1320747,05 8750676,50 58046489,60
Dickson, Smith, Li 1345066,80 986506,60 1794442,25 2406499,2536011581,05 1389306,45 883862,40 1949700,65 2529246,70 44798632,70
Estellon, Gardi, Nouioua 297019,05 928384,65 2180182,40 1733066,6042259652,80 247315,35 1031022,70 2586730,75 2205772,30 58333715,85
Eggenberg, Salani 3860511,50 721588,60 2395934,10 6161533,2043978009,85 4980974,40 1545630,05 5048257,00 10509766,30 69097236,55
Peekstok, Kuipers 23789,05 83515,00 135225,60 INFINF 3700144,95 794892,90 INF INF INF

Aperçu des méthodes proposées

Les méthodes proposées par les candidats ne seront pas dévoilées avant la fin du challenge. Néanmoins, la lecture des résumés étendus envoyés révèle sans surprise que toutes les méthodes proposées sont des méthodes heuristiques résolvant le problème en le décomposant en plusieurs étapes, avec toutefois une assez grande variété d'approches. Parmi les dénominateurs communs des outils de base utilisés, on trouve de manière assez logique des algorithmes élémentaires de flots et de chemins optimaux. Sans révéler ce qui a le mieux marché pour cette phase de qualification, les schémas généraux de résolution se répartissent en algorithmes purement gloutons, méthodes de descente avec redémarrage, recuit simulé, méthodes hybrides de programmation linéaire en nombres entiers et de recherche locale, génération de colonnes. En termes d'implémentation, les programmes ont été développés en Delphi, C, C++, Java avec ou non l'utilisation de librairie de structure de données et de solveurs de programmation linéaire.