Discussion :

[Laugilus]

Bonjour,

Dans le cadre d'un projet, je dois résoudre un problème d'affectation (des étudiants doivent choisir des cours dans une liste, puis seront repartis (affectes) au cours. Par exemple, chaque étudiant a un crédit de 500 points, et il distribue les points sur chacun des cours, en mettant davantage de points sur les cours qu'il veut suivre (Un étudiant peut mettre 0 point sur un cours s'il ne veut pas suivre par exemple)).

Je n'ai jamais traite de tels problèmes avant : mes recherches m'ont conduit sur la méthode hongroise ou sur l'algorithme de Ford Fulkerson.

Dans les deux cas, je me suis rendu compte qu'il faut "autant d’étudiant que de cours" (pour avoir une matrice de coût carrée (pour la méthode Hongroise en tout cas)). Ce problème est résolu en ne considérant non pas les cours mais les places disponibles dans ces derniers.

Pour la méthode Hongroise, je n'ai pas de problèmes : j'arrive a faire une matrice carrée de coût.
Mon soucis se situe au niveau de l'algorithme de Ford Fulkerson, qui est plus intéressant pour moi car a un temps d’exécution réduit. J'ai du mal a comprendre exactement l'algorithme. (Et a trouver de la doc dessus qui traite du problème d'affectation)
Je tiens a préciser que je n'ai jamais eu l'occasion de suivre un cours sur les graphes, et que ces notions sont assez nouvelles pour moi^^.

D’après ce que j'ai compris :
Il s'agit de faire un graphe biparti, avec une source et un puits, de pondérer chaque arc reliant un sommet "étudiant" a un sommet "cours" (Ceci se fait grâce a la liste que les étudiants ont rempli). Il faut aussi donner a chaque arc une capacité de 1. Et pondérer les arcs partant de la source et les arcs arrivant au puits avec un poids unitaire.

Ensuite il faut utiliser un algo du chemin le plus court (Dijkstra par exemple) pour relier la source au puits, et regarder par quel chemin l'algo est passe. Le couple (étudiant, cours) traverse est mémorisé (et est définitif ?)
Il faut alors supprimer du graphe les arcs qui ont été traversés par l'algo du chemin le plus court (4 arcs en tout donc, et réduire leur capacité a 0), et recommencer.

Est-ce que c'est ca ?

J'ai vu une autre implémentation qui en plus de supprimer les arcs traverses (a la fin de chaque étape), il ajoute ces mêmes arcs mais dans le sens oppose, avec un poids oppose. (par exemple s'il y avait un arc reliant l’étudiant a au cours b, avec un poids p, l'algo détruit cet arc (met un poids infini), et crée un arc qui relie b a a avec un poids de -p)

J'ai l'impression que cette implémentation n'apporte rien de plus, que l'algo du chemin le plus court (un autre que dijkstra donc car poids négatif) ne retournera jamais un chemin qui passe par ces arcs négatifs. Est-ce que je me trompe ?

Bref, toutes ces notions sont assez nouvelles pour moi, donc je suis peut-être complètement a cote de la plaque^^.

Autre question : pour ce problème, vaut mieux utiliser l'algo hongrois au Ford Fulkerson ? (le temps d’exécution n'est pas tres important, tant que l'algo répond dans l'heure. Si je fais des matrices carrées, elles seront de la taille 1500*1500...)

Merci d'avance^^.

PS : Désole pour certains accents, j'ai un clavier qwerty.

[zamato]

Ensuite il faut utiliser un algo du chemin le plus court (Dijkstra par exemple) pour relier la source au puits, et regarder par quel chemin l'algo est passe. Le couple (étudiant, cours) traverse est mémorisé (et est définitif ?)
Il faut alors supprimer du graphe les arcs qui ont été traversés par l'algo du chemin le plus court (4 arcs en tout donc, et réduire leur capacité a 0), et recommencer.

Est-ce que c'est ca ?

J'ai vu une autre implémentation qui en plus de supprimer les arcs traverses (a la fin de chaque étape), il ajoute ces mêmes arcs mais dans le sens oppose, avec un poids oppose. (par exemple s'il y avait un arc reliant l’étudiant a au cours b, avec un poids p, l'algo détruit cet arc (met un poids infini), et crée un arc qui relie b a a avec un poids de -p)

Cet algorithme répond au problème du maximum matching.

En fait à chaque chemin que tu trouves, tu mets à 0 la capacité des arcs qui les composent et tu mets à 1 la capacité des arcs opposés. Dans ce cas les arcs opposés crées seront succeptibles d'être utilisés dans des chemins ultérieurs. (Il ne faut pas mettre la capacité à infini par contre...ça c'est quand on travaille avec des distances...).

Par ailleurs je te conseille de ne pas utiliser djisktra pour trouver un chemin, c'est assez lourd (par exemple un simple dfs sera plus efficace). Pour faire une implémentation rapide, tu peux utiliser deux fonctions qui s'appellent récursivement. Enfin vu que ta matrice n'est pas très grosse, ce n'est peut-être pas la peine d'optimiser.

[Franck Dernoncourt]

Je n'ai pas le temps de te répondre en détail mais peut-être que la PJ t'aidera.

[Alexis.M]

Y a-t-il des contraintes supplémentaires dans le problème ? Nombre minimum de cours à suivre, nombre maximum d'étudiant par cours ?

Tel que tu le présente il suffit d'attribuer à chaque étudiant les cours qu'il demande et c'est terminé.

Formellement si tu as N étudiants et C cours. Tu appelles xij l'affectation de l'étudiant i au cours j et pij le poids attribué par l'étudiant i au cours j

tu veux donc maximiser:

sum_i sum_j p_ij x_ij

avec les contraintes (je suppose)
sum_i xij > s (nombre minimal de cours par étudiant)
sum_j xij < t (nombre maximal d'étudiant par court)

C'est un problème de programmation linéaire discrète. Je ne connait pas assez bien le domaine pour en être sûr mais typiquement tu auras soit des résolution exacte longues à trouver soit des solutions approchées (recuit simulé, algorithmes génétiques).

Dans tous les cas je ne pense pas que le hongrois soit le bon algo pour ton problème.

Il me semble qu'une approche pratique consiste a suprimer la contrainte "entière" sur les xij (éventuellement rajouter la contrainte 0<=xij<=1) à résoudre le problème de programmation linéaire et ensuite à seuiller pour retrouver des valeurs binaires

[Laugilus]

Merci de vos réponses et merci pour le pdf (je comprends mieux le principe du Hongrois).

J'aurais aussi aimé trouver un document pour expliquer plus en détails l'algorithme de Fulkerson appliqué au problème d'affectation.
Parce qu'il y a toujours un point que je comprends pas. Par exemple si le chemin trouve est du type (source, élève, cours, puits), alors on peut affecter l’élève au cours.
Cependant, si le chemin trouve passe par des arcs de poids négatifs (donc par des élèves qui sont déjà affectes, comment interpréter le résultat ?)

Par exemple est-ce qu'un chemin obtenu pourrait être (source, élève 1, cours 1, puits, cours 2, élève 2, cours 3, puits), sachant que (puits, cours 2) et (cours 2, élèves 2) sont des arcs de poids négatifs ? Si oui, comment interpréter le résultat ? (Je n'arrive pas a trouver de doc la dessus)
Faut-il désaffecter l’élève 2 et le cours 2 ? Que faut-il faire des arcs ? A quoi affecter l’élève 1 ?

Merci encore de vos réponses^^.

[GPPro]

Ca remonte à loin pour moi, mais le puits est terminal, tu n'as pas d'arc sortant il me semble.

[Laugilus]

Alexis.M Je n'avais pas vu ton message.

Mon contient beaucoup de contraintes administratives. Il y a en fait 2 types de cours (transversal et disciplinaire). On a les combinaisons possibles pour chaque étudiant :
- 6 disciplinaires
- 3 disciplinaires, 1 transversal
- 2 transversaux

D'autres contraintes imposes que certains étudiants sont obliges d’être affectés à un cours donne (disciplinaire ou transversal).

Et enfin chaque cours peut contenir un nombre d’élève maximal (qui varie selon le cours).

Voila plus ou moins toutes les contraintes qu'il y a. Cependant, j'arrive toujours à me ramener au cas du problème d'affectation basique : n élèves à repartir dans n cours. (Parfois en rajoutant des élèves, parfois en rajoutant des cours. Enfin bref, je ne veux pas vous ennuyer avec ça)

Toujours est-il que je suis donc ramené au problème d'affectation. Au tout début je préférais l'algorithme de Fulkerson plutôt que l'algorithme Hongrois pour avoir un meilleur contrôle (étape par étape) des contraintes administratives, mais maintenant que j'ai trouve des astuces pour les traiter en amonts, ça n'a plus trop d'importance.

Il me semble qu'une approche pratique consiste a suprimer la contrainte "entière" sur les xij (éventuellement rajouter la contrainte 0<=xij<=1) à résoudre le problème de programmation linéaire et ensuite à seuiller pour retrouver des valeurs binaires

Oui, ça à l'air possible. Mais je n'ai jamais eu à faire à des algos résolvant ce genre de problèmes non plus^^.

Ca remonte à loin pour moi, mais le puits est terminal, tu n'as pas d'arc sortant il me semble.

Dans l’implémentation que j'ai vu (http://www.yoan-chabot.fr/EspacePers...algorithme.pdf page 25), il y a bien un arc sortant du puits de poids négatif. Cependant je ne sais pas comment juger ce document, s'il est sur ou non^^.
Mais ma question est surtout comment interpréter les chemins qui passent par des arrêtes de poids négatif ?

Merci d'avance.