Répartir une promotion : préférences, stabilité et flots

Des élèves classent leurs groupes préférés ; chaque groupe possède un nombre limité de places. Comment les affecter ? Ce projet algorithmique en Elixir compare trois garanties : l’absence de paire bloquante, le nombre maximal d’élèves placés, puis le meilleur coût total à effectif fixé.

Le projet noté commence en semi-autonomie pendant AP9 et se poursuit à la maison. Nous pouvons lire la première trace ensemble avant de compléter les algorithmes. Le socle rassemble acceptation différée et flot maximal ; le coût minimal est un prolongement guidé avec davantage de code fourni. Le périmètre attendu, le barème et l’échéance seront précisés avant le lancement ; les étapes ne sont pas un barème.

Téléchargez le squelette affectation-groupes. Le README contient le parcours autonome complet, les contrats, les indices, les commandes et les éléments à conserver. Les données sont fictives et l’affichage SVG est fourni : aucun HTML, CSS ou JavaScript n’est nécessaire.

Partir d’une affectation qui fonctionne

mix compile
mix test --only provided
mix allocation immediate replacement out/immediate

Les neuf tests de l’infrastructure passent avant de remplir les trous. La commande produit l’affectation finale, une trace et un SVG par étape dans out/immediate/. Vous pouvez les ouvrir dans votre éditeur.

Un élève fournit une liste stricte de vœux, éventuellement incomplète ; chaque groupe fournit une priorité stricte sur les élèves. Cette priorité est une donnée annoncée, par exemple un ordre issu d’un tirage au sort, et ne se déduit pas des vœux. Nos exemples ne représentent ni des notes ni le mérite des élèves. Les capacités sont des maxima : aucun minimum, bonus ou quota supplémentaire n’intervient.

Retenir une place provisoirement

L’algorithme fourni admet les élèves définitivement, par tours de vœux. Dans l’exemple replacement, Ada obtient C alors qu’elle préfère A ; A donne priorité à Ada sur Bob, déjà admis. Ada et A forment donc une paire bloquante.

Avec une place par groupe, on retrouve le problème des mariages stables. Avec plusieurs places, chaque groupe conserve ses meilleurs candidats provisoirement et peut en remplacer un lorsqu’une nouvelle proposition arrive. Un élève rejeté reprend sa liste au vœu suivant. Cette méthode, où chaque admission reste provisoire jusqu’à la fin, s’appelle l’acceptation différée : c’est l’algorithme de Gale et Shapley. Une affectation est stable lorsqu’il n’existe aucune paire bloquante.

Complétez Deferred.step/2 et Deferred.blocking_pairs/2. L’initialisation, la boucle et le classement d’un ensemble de candidats sont fournis. Votre état conserve la file des élèves qui proposent, leurs vœux restants, les candidats retenus et la trace des propositions.

mix test --only stable
mix allocation stable replacement out/stable

Prédisez un remplacement avant d’exécuter le programme. Pourquoi les vœux d’un candidat éjecté ne recommencent-ils pas au début ? Vérifiez une capacité de deux, un groupe fermé et un élève qui a épuisé ses vœux.

Affecter le plus d’élèves possible

Changeons de question : peut-on placer toute la promotion dans ses deux premiers vœux ? Dans shortage, trois élèves souhaitent A, B, C dans cet ordre, avec une place par groupe. Restreindre les choix à A et B rend la place de C inutilisable.

Un flot est une quantité qui circule d’une source vers un puits en respectant la capacité de chaque arc ; chaque unité de flot représente ici une affectation. Le réseau possède une source, un nœud par élève, un nœud par groupe et un puits. Les arcs source–élève limitent chacun à une affectation ; les arcs élève–groupe représentent ses choix acceptables ; les arcs groupe–puits portent les capacités des groupes.

Complétez Flow.network/2 puis Flow.augment/2. Le parcours en largeur et la boucle d’augmentation sont fournis. Chaque chemin de la source au puits qui n’emprunte que des arcs encore disponibles, appelé chemin augmentant, envoie une unité supplémentaire. Les arcs de retour permettent de réviser une ancienne affectation pour en rendre une nouvelle possible : l’ensemble de ces capacités encore modifiables forme le graphe résiduel.

mix test --only flow
mix allocation max reroute out/reroute
mix allocation max shortage out/top2 2

Repérez le retour A–Ada dans la trace de reroute. Lisez les images avant et après ce chemin : personne n’occupe deux places. Quand aucun chemin ne joint source et puits, l’effectif affecté est maximal, même si certains élèves restent sans place. La fonction fournie Flow.smallest_k/1 cherche le plus petit nombre de vœux à ouvrir pour affecter toute la promotion.

Le socle s’arrête ici. Pour le vérifier sans activer le prolongement :

mix test --only provided --only stable --only flow

Prolongement : minimiser la somme des rangs

La fonction Flow.with_costs/2 attribue le coût zéro à un premier vœu, un à un deuxième, deux à un troisième. Le retour prend le coût opposé : annuler un choix rembourse son coût. La recherche de plus court chemin devient Bellman–Ford, un algorithme qui accepte les coûts négatifs ; il est fourni.

mix test --only cost
mix allocation stable objectives out/objectives-stable
mix allocation min_cost objectives out/objectives-cost

Avec une place dans A, B et C et la priorité commune Ada, Bob, Chloe, comparez les deux résultats suivants :

Le résultat de coût un admet la paire bloquante Ada–A. Expliquez pourquoi cela ne contredit pas l’objectif du flot, qui ne consulte pas les priorités des groupes. Comparez les méthodes avec les mêmes capacités et les mêmes listes ; ici, tous les vœux sont ouverts.

Le solveur maximise d’abord l’effectif, puis minimise le coût à cet effectif. Une affectation vide a un coût nul : cela ne la rend pas meilleure ! L’oracle fourni énumère les possibilités sur de petits exemples pour contrôler ces deux critères. Les tests complets confrontent les méthodes à 341 profils fictifs, dont des listes incomplètes et des capacités variables.

Garder une explication avec le code

Conservez votre code, vos tests personnels, quelques SVG et un COMPTE-RENDU.md. Le README précise le contenu : commandes réellement exécutées, remplacement prédit puis observé, chemin résiduel expliqué, comparaison des garanties et limite du modèle. Le dossier out/ est ignoré par Git : copiez les traces et SVG retenus dans rendu/. Une extension possible consiste à expliquer une impossibilité à partir des nœuds encore accessibles dans le graphe résiduel.

L’article de Gale et Shapley sur les admissions et la stabilité (1962) présente l’acceptation différée. La documentation OR-Tools sur les flots de coût minimal illustre capacités, conservation et coûts ; nous n’installons pas cette bibliothèque pour ce petit solveur Elixir.

Pour toute question sur le sujet ou le point de départ, vous pouvez me contacter par email, comme pour les autres séances.