Contest L3 info et L3 BIM 2007 : équilibrage.

Enseignants : Karim Nouioua Stéphane Grandcolas Yann Vaxes

Transparents de la présentation


NOUS VOUS FERONS PASSER LES INFORMATIONS IMPORTANTES PAR MAIL. PENSEZ A LIRE VOS MAILS SUR LE COMPTE QUE VOUS AVEZ AU DEPARTEMENT D'INFORMATIQUE.



Résultats.

Nous avons lancé les programmes sur le jeu de problèmes trois fois (sauf le projet de l'équipe 3). Les résultats obtenus apparaissent dans la table ci-dessous : pour chaque run et pour chaque équipe nous avons indiqué le nombre de problèmes pour lesquels la solution trouvée est de meme valeur que la meilleure solution (trouvée par une des équipes en compétition).

T5 T7 T8 T1 T4 T6 T3
run 1 22 21 10 30 0 35 97
run 2 24 24 7 29 0 32 100
run 3 24 21 13 29 0 40 100

the winner : équipe 3


Florent A.
Marine B.
Sébastien B.
Sabrina B.
Thomas C.

second : équipe 6


Adrien B.
Stéphanie M.
Michael R.
Roy S.
Maxime V.

troisième : équipe 1


Lyna A.
Julien G.
Teiva H.
Joris R.
Vincent R.

Encore bravo à tous les participants. Beaucoup ont un peu manqué de rigueur dans la programmation. Des idées intéressantes n'ont pas produit les résultats escomptés du fait d'erreurs de programmation trop nombreuses. Des programmes efficaces auraient pu faire encore mieux s'ils ne s'étaient pas terminé sur des segmentation faults. Les meilleurs projets étaient aussi ceux qui étaient les mieux écrits et les mieux structurés.
Cela dit, nous n'avons pas eu de problèmes pour compiler les programmes ni pour les faire tourner, c'est une bonne surprise.



Les problèmes de l'évaluation.

Vous pouvez télécharger le jeu de problèmes sur lequel les projets des équipes en compétition seront évaluées. Vous y trouverez des problèmes avec 100, 500, 1000, 2000 et 5000 objets. Certains sont générés de façon totalement aléatoire (tailles comprises entre 10 et 100, poids compris entre 10 et 1000), d'autres sont générés avec des tailles choisies au hasard entre 10 et 100, mais leurs poids sont les premiers nombres premiers (tous les poids sont distincts et peuvent être très grands). Chaque solveur sera évalué sur tous les problèmes avec un timeout de 60 secondes au delà duquel le solveur sera stoppé et son score sera considéré comme nul sur ce problème. Nous vérifierons que les solutions trouvées correspondent bien aux problèmes donnés.
N'oubliez pas lorsque vous nous enverrez vos projets de signaler quels sont les membres ou le numéro de l'équipe. Bonne chance à toutes les équipes.

Modalités.

Durée de la compétition. Vous devez nous envoyer les sources de vos programmes au plus tard le lundi 24 septembre à 12h00 par mail.
Les sources. Ecrites en C ANSI (pas de C++), nous devons pouvoir les compiler facilement sous Linux avec gcc (commande : gcc src1.c src2.c ... srck.c -o solve). Un programme que nous ne pourrions pas compiler ne pourra pas être évalué.
L'évaluation. Nous lancerons tous les programmes sur un ensemble de problèmes de tailles et de difficultés variées. Le temps de calcul est limité à 60 secondes pour chaque problème sur une machine plutot rapide (tout dépassement annulera le résultat du solveur pour le problème). Chaque solveur sera évalué par le nombre d'instances pour lesquelles il aura trouvé le meilleur résultat (par rapport aux autres solveurs).


Le problème.

Etant donné un ensemble de n paquets cubiques et homogènes de poids et de tailles donnés, on cherche l'ordonnancement de ces paquets pour lequel le centre de gravité est le plus proche du milieu de la suite de paquets (ordonnancement : positionnement des paquets les uns à la suite des autres dans un certain ordre ; la longueur d'un ordonnancement est donc la somme des tailles des paquets ; le milieu de l'ordonnancement est situé à la moitié de la longueur). Idéalement le centre de gravité coincide avec le milieur de la suite, mais ça n'est biensur pas toujours possible.



Les données et les résultats que vous devez produire.

Vous respecterez strictement le formalisme demandé, afin que nous puissions facilement tester vos programmes.

Fichiers de données. Ce sont des fichiers texte. Ils respectent un format particulier. Sous Linux vous pourrez utiliser le programme de génération genere pour produire des instances aléatoirement (essayez d'abord ./genere -help). Ces fichiers ne contiennent que des valeurs numériques entières. La première valeur est le nombre de paquets. Le fichier contient ensuite, pour chaque paquet, sa taille et son poids.

Résultats. Les résultats produits ont le même syntaxe que les données : le nombre de paquets suivi d'une taille et d'un poids autant de fois qu'il y a de paquets. L'ordre est donné par l'ordre d'apparition des dimensions des paquets. Ces résultats seront simplement affichés par les solveurs sur la sortie standard (i.e. avec des printf("...",...)). Nous ne tiendrons pas compte des fichiers créés par les programmes.

Programmes utilitaires (pour Linux uniquement).

genere pour la génération de problèmes

# ./genere 100 6 10 112 822 1554


Génère et affiche à l'écran un problème avec 100 paquets de tailles prises au hasard entre 6 et 10 et de poids pris au hasard entre 112 et 822 en utilisant la graine de génération aléatoire 1554 (si cette graine n'est pas présente un nouveau problème sera généré chaque fois). Pour sauver le problème dans un fichier texte, modifiez la sortie standard

# ./genere 100 6 10 112 822 1554 > mon_probleme.data



eval pour l'évaluation d'un ordonnancement

# ./eval < sol.data


Evalue la solution contenue dans le fichier sol.data et affiche la distance entre le centre de gravité de cet ordonnancement et sa position idéale (au milieu de la suite). On peut par exemple combiner eval et genere afin d'évaluer l'ordre initial des paquets produit par le générateur aléatoire

# ./genere 100 6 10 112 822 1554 | ./eval
eval = 19.9492574526
#