Algorithme utilisé

L'algorithme est assez classique : en les classant, les élèves attribuent un poids à chaque projet. On calcule alors par l'algorithme de Munkres la répartition qui minimise la somme des poids. Les poids sont choisis pour correspondre à une minimisation des mécontentements : leur progression n'est pas linéaire, mais transformée en interne en grosso modo n³. Autrement dit, le système essaye vraiment fort d'éviter les gens pas contents du tout. L'algorithme de Munkres a la bonne propriété de trouver, en un temps raisonnable (O(n³)), la solution optimale. Une autre solution correspondrait donc à un mécontentement global plus grand (à bien méditer avant tout réclamation…).

Il y a quand même un problème : même si on est assuré de trouver un optimum, rien ne prouve que cet optimum est unique. Il faut donc trouver un dernier critère discriminant, pour finaliser la répartition et choisir arbitrairement entre deux optimum. Il a été décidé de ne pas prendre en compte la date de soumission des voeux, pour plusieurs raisons : vous donner le temps de réfléchir avant de voter, éviter l'absentéisme à l'ouverture des votes, ne pas discriminer ceux qui n'ont pas facilement de PC à leur disposition, et ne pas effondrer le serveur par un pic d'accès à l'ouverture ou à la clôture des votes.

Conformément aux discussions de conseil d'année le critère discriminant   choisi (utilisé en vraiment tout dernier recours, pour choisir entre deux optimum) est un ordre aléatoire, choisi une fois pour toutes à l'ouverture des votes.  De plus, le classement de tous les projets à chaque vote est maintenant obligatoire pour minimiser le risque de collisions. Il y aura donc peut-être quelques déçus.  Mais la solution trouvée étant un optimum global, c'est malgré tout celle qui en fait le moins possible.