Problème affectation : méthode Hongroise vs Ford Fulkerson

[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.

[Franck Dernoncourt]

Peut-être quelques informations qui t'intéresseront en cherchant Ford ou Fulkerson dans les 2 PJ.

[Alexis.M]

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)

Cela me paraît difficile. Tu dois rester général et à mon avis ce n'est pas la bonne approche car il ne s'agit plus du même type de problèmes.

Tu devrais plutôt regarder tu côté de la programmation par contrainte et les algos associés. Il existe par exemples des "solver" pour ce genre de problèmes:
http://fr.wikipedia.org/wiki/Program...ar_contraintes

Typiquement tu as deux types d'approches recherche exhaustive par arbre ("branch and bound"...) qui peuvent s'avérer longs en pratiques et recherches approchées (recuit simulé, algorithmes génétiques, relaxation continue...)

Tu dois surtout à mon avis bien poser ton problème:

valeur du cours j : vi = 1 si disciplinaire 3 si tranversal et pour chaque
élève i prends cours j : xij = 1 ou 0
préférence de l'élève i pour le cours j : pij

Tu veux maximiser l'adéquation avec les préférences des élèves:

\sum_i sum_j pij * xij

Avec les contraintes générales:
sum_i xij < cj (pas plus de cj élèves pour le cours j)
sum_j vi xij = 6 (la valeur total des cours est 6 pour tous les éléves)
puis au cas par cas :
x_ij = 1 (l'élève i doit prendre le cours j)

Les algos de types "branch and bound" ne sont pas difficiles à comprendre il pratiques un recherche exhausitve mais permettent d'éliminer des jeux complets de possibilité en calculant des limites sur les quantités à optimiser.

http://fr.wikipedia.org/wiki/S%C3%A9...C3%A9valuation

[Laugilus]

Franck Dernoncourt > Je ne peux lire les fichiers 7-zip maintenant, je regarderai la doc ce soir. Merci.

Alexis.M > Je vais regarder de plus près, mais plusieurs points me semblent obscurs. L'algorithme trouvera-t-il une configuration (matrice x_ij) optimale ?
Tu avais dis auparavant de prendre x_ij réel, éventuellement dans [0, 1], et de revenir dans {0, 1} une fois l'algorithme exécuté, via un système de seuil (je suppose que si x_ij > 0.8 par exemple, alors on considère x_ij = 1). Cependant, il ne faut pas oublier que ça doit respecter les autres inéquations. (sum_j vi xij = 6 et sum_i xij < cj). Quand bien même on arrive au final a trouver une matrice entière de x_ij vérifiant les inéquations, comment être sur que la configuration est optimale (autrement dit, il pourrait y avoir une autre matrice x_ij entière qui maximise davantage la somme) ?

C'est pour avoir une solution optimale (voire même les avoir toutes) que je voulais m'orienter vers Hongrois/Fulkerson (Et aussi parce que je n'avais aucune idée que des algorithmes de maximisation comme ceux auxquels tu me renvois existaient^^).
Apres je ne sais pas si c'est le cas avec ce que tu proposes (si j'ai la garanti que le résultat est optimal). Je lirai la doc quand j'aurais le temps ce soir, car c'est tout de même une vision du problème que j'avais pas vu et semble être une piste a explorer.

Merci de vos réponses.

[Franck Dernoncourt]

Envoyé par Laugilus

Franck Dernoncourt > Je ne peux lire les fichiers 7-zip maintenant, je regarderai la doc ce soir. Merci.

http://www.convertfiles.com/convert/...7Z-to-ZIP.html (d'habitude http://www.wobzip.org/ fait du bon travail mais en l'occurrence il ne reconnaît pas la compression que j'ai utilisée)

[Alexis.M]

Tu peux voir l'approche 'Séparation et évaluation' comme une recherche dans un arbre où chaque niveau d'embranchement correspond à une variable.

Imagine que tu as x1 et x2 comme variables binaire

Code :

1
2
3
4
5
       x1   x2
             0
         0 < 1
racine <     0
         1 < 1

Dans ton cas tu (neleves * ncours) variables. L'idée est don de parcourir l'arbre et à chaque noeuds :
- si l'exploration ne conduit qu'à des contraintes non satisfaite on arrête (élagage)
- on estime le score maximal que l'on peut obtenir en poursuivant :
-si le score maximal est plus petit qu'un score connu dans un autre chemin on arrête.
-sinon on continue en choisissant en priorité les chemin pouvant mener aux plus grands scores maximaux.

Il est important que l'estimation du score maximal soit optimiste (toujours supérieure ou égale au vrai score). Il se trouve que la relaxation continue conduit toujours à ce genre d'estimation.

Dans ce cas tu es sûr de trouver une solution optimale.

Par définition les méthodes approchées ne garantissent pas l'optimalité mais à défaut conduisent à une "bonne" solution qui vérifie les contraintes.

[Alexis.M]

Pour info, et pour faciliter tes recherches, le nom générique du problème est Programmation Linéaire en Nombres Entiers (PLNE) ou Integer Linear Programing (ILP).