Forum Programmation.python Programmation générique / programmation par contraintes. Minimisation du nombre d' "insatisfaits"

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
3
21
sept.
2013

Bonjour,

je suis enseignant et je m'occupe de projets.
je voudrais mettre en place un script (python + pandas + …) pour générer de manière la plus objective l'attribution de projet.

Voici le problème.
J'ai des étudiants qui doivent faire des projets (cette année il y en a 64 mais ça peut monter à 80-90 certaines années).
Ces projets se font majoritairement par groupe de 4 (il peut y avoir à la marge un groupe de 3 ou de 5).

J'ai des enseignants qui proposent des projets (j'en ai 19 cette année… donc à priori plus que nécessaire)

Les étudiants peuvent aussi proposer des projets (sous réserve qu'ils aient trouvé un enseignant souhaitant les encadrer)

Les étudiants peuvent choisir leur ordre de préférence des projets.

Ils ont deux stratégies pour saisir leur ordre de préférence :
- soit d'abord se mettre en groupe et donner un ordre de préférence parmi les projets (stratégie de groupe)
- soit choisir un ordre de préférence parmi les projets et le groupe se constituera (stratégie individuelle)

Je demande aux étudiants de saisir leur voeux (soit via la "stratégie de groupe" soit via la "stratégie individuelle")
J'ai ensuite les données dans un tableur
Choix_strat;Nom_indiv;Nom1;Nom2;Nom3;Nom4;Nom5;Ordre
indiv;EtuToutSeul;;;;;;1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
groupe;;Nom1;Nom2;Nom3;Nom4;;perso,19,18,17,16,15,15,13,12,11,10,9,8,7,6,5,4,3,2,1

Je voudrais faire un script qui "minimise" le nombre d'"insatisfaits" (voeu pieu)

Comment arborderiez-vous le problème ?

Je ne connais pas vraiment ni la programmation par contraintes, ni la programmation génétique,
par contre je maîtrise bien Python et Pandas.

Merci d'avance

  • # Programme Lineaire en Nombre Entier

    Posté par  . Évalué à 3.

    Moi je commencerai par un programme linéaire en nombre entier.

    Le principe, c'est de réduire ton problème à une forme du type:

    minimiser A X
tel que B X = C

    avec X un vecteur d'entier qui sont les inconnues (et qu'on peut trivialement borner si besoin), C vecteurs de réels constants et B de matrices réeles constantes. Les inconnues peuvent être trivialement bornées, la minimisation peut se transformer facilement en maximisation (suffit de prendre des nombres negatifs dans A), et on peut facilement transformer une égalité en inégalité (si a <= b, alors a = b + inconnue positive)

    Sous forme non-matricielle, et en pratique, ça donne :

    maximiser a₁x₁ + a₂x₂ + .... + aₙxₙ
avec b₁₁x₁ + b₁₂x₂ + .... + b₁ₙxₙ <= c₁
et b₂₁x₁ + b₂₂x₂ + .... + b₂ₙxₙ = c₂
et b₃₁x₁ + b₃₂x₂ + .... + b₃ₙxₙ >= c₃
et ....
et bₘ₁x₁ + bₘ₂x₂ + .... + bₘₙxₙ <= cₘ

    Après, il faut juste choisir ses inconnues et ses variables et éxprimer correctement ses contraintes.
    L'avantage de cette méthode c'est qu'elle est éxacte et même si tu ne t'en sert pas pour résoudre, elle permet de prouver que tu est bien à l'optimum. Elle est rapide pour des petits problèmes, par contre, elle peut devenir lente si le nombre de relation/variable éxplose, mais dans ce cas la elle peut proposer des solution intermédiaires.

    • [^] # Re: Programme Lineaire en Nombre Entier

      Posté par  . Évalué à 3.

      Pour ton problème, par exemple, je verrais bien déjà au moins 2 inconnues :

      xᵢⱼ : variables binaires: l'étudiant i est dans le projet j.
      pⱼ : variable binaire: le projet j est ouvert

      On peut déjà commencer à exprimer quelques relations avec ça :

      xᵢ₁ + xᵢ₂ + ... + xₙ = 1 (un étudiant est dans un et un seul projet)

      xᵢⱼ <= pⱼ (un étudiant est dans un projet seulement si il est ouvert, ça se transforme trivialement en xᵢⱼ - pⱼ <= 0)
      x₁ⱼ + x₂ⱼ + ... + xₙⱼ <= 5 (pas plus de 5 étudiant dans un projet)
      On peut déjà factoriser ces deux contraintes en une seule :
      x₁ⱼ + x₂ⱼ + ... + xₙⱼ <= 5pⱼ (si pⱼ est égal à 0, ça force tout les xᵢⱼ à 0, sinon, ils doivent être inférieur à 5)

      Pour forcer le nombre d'étudiant par groupe à être supérieur à 3, il faut une contrainte du même type:
      x₁ⱼ + x₂ⱼ + ... + xₙⱼ >= 3pⱼ (si le groupe est ouvert, il doit y avoir 3 étudiants dedans)

      (En pratique, pour transformer ces deux relations en égalités, il faudra ajouter des inconnues. On pourrai très bien utiliser ces inconnues et mettre des pénalités pour les groupes de 3 ou 5 ou limiter leur nombre)

      Il reste plus qu'a choisir l'objectif. Par exemple, tu peux donner une insatisfaction de 1 si l'étudiant est dans son 2 ième choix, 2 si il est dans son troisième choix … ect. et minimiser la somme des insatisfactions. Tu pourrai être aussi plus fin en cherchant à maximiser la satisfaction et en demandant aux étudiants de noter chaque projet, ça leur permet d'exprimer des opinions plus fines comme "je veux ce projet, tout le reste est indifféremment nul" "j'aime bien ces trois projets, au pire celui là il est bien, mais pas ceux là" "j'en ai rien à foutre".

      Pour les groupes, ou bien tu refait les contraintes pour prendre en compte les groupes, ou bien tu fait ça de manière crade, en rajoutant une contrainte "tout ces étudiants font le même projet" et en laissant le solveur simplifier le problème pour toi (ou pas). l'avantage (ou le désavantage) c'est qu'il peut aussi compléter des groupes de 2,3 ou 4 personnes.

      Après, pour utiliser ça en python, je sais pas si il existe des bonnes bibliothèques pour ça, mais au pire tu peux lancer lp_solve depuis un programme python et lui donner ton problème en entrée, et parser sa sortie.

      (un truc bien avec lp_solve, c'est que sa bibliothèque est une dépendance du solveur d'openoffice/libreoffice, donc il est déjà installé sur pas mal de systèmes)

      • [^] # Re: Programme Lineaire en Nombre Entier

        Posté par  (site web personnel) . Évalué à 1.

        c'est intéressant cette mise en forme du problème….

        par contre ça me gêne un peu que ça puisse "casser" les groupes donc ajouter la contrainte "tout ces étudiants font le même projet" me semble judicieux

  • # Notion de distance

    Posté par  (site web personnel) . Évalué à 0.

    Merci pour ce début de réponse… mais je ne vois juste pas comment mettre ça en forme !

    Ce que je comprends de mon problème c'est que pour minimiser le nombre d'"insatisfaits" il faut maximiser le nombre de premier voeux en fait il faudrait créer une "distance" ou une norme entre le projet attribué à un étudiant / groupe d'étudiant par rapport à l'ordre de ses choix

    exemple:
    un étudiant ou un groupe d'étudiant a fait le choix d'ordre
    1,3,6,4,5,2,7,8,9,10,11,12,13,14,15,16,17,18,19
    et le programme lui donne le projet 1
    alors il est totalement satisfait (distance=0)

    si le programme lui donne le projet 6
    alors il n'est plus totalement satisfait (distance=2)

    si le programme lui donne le projet 2
    alors il n'est plus totalement satisfait (distance=5)

    l'idée serait de sommer pour tous les étudiants (et tous les groupes avec un coefficient dépendant du nombre d'étudiant dans le groupe) cette distance et trouver la distance "minimale"

    Le truc que je ne vois pas c'est comment "envoyer" un choix de projet pour chaque étudiants / groupe d'étudiants sachant que lorsque j'affecte le projet à un groupe il ne pourra pas être affecté à un autre groupe mais que lorsque je l'affecte à un étudiant seul il peut être affecté à 3 autres étudiants.

    • [^] # Re: Notion de distance

      Posté par  . Évalué à 3.

      Un algorithme vite fait :
      pour i=1 jusqu'au nombre de groupe :
      pour chaque projet qui reste :
      Si il y a des personnes ou des groupes qui l'ont classé en i :
      Parmi ceux-ci, tirage au sort (avec une probabilité proportionnelle au nombre de personnes du groupe) de celui qui l'emporte. On retire le projet et le groupe vainqueur des listes.

      Si il a assez de projets, il me semble qu'il ne doit pas rester de groupe à la fin…

      Cela favorise ceux qui ont choisi la stratégie par groupe puisque je propose une probabilité variable suivant le nombre dans le groupe. C'est un choix à faire.

      Le problème c'est que, en sommant les distances, on ne fait pas trop la distinction entre les situations suivantes :
      Première situation : beaucoup de très satisfait et beaucoup de très peu satisfait

      Deuxième situations : tout le monde moyennement satisfait

      En fait c'est un problème politique ;-)

      • [^] # Re: Notion de distance

        Posté par  (site web personnel) . Évalué à 1.

        Moi ce que je n'aime pas dans ta solution c'est qu'elle n'est pas stable (si je relance le script j'ai une nouvelle attribution). Par contre on est d'accord sur l'aspect "politique" de la tâche.

        • [^] # Re: Notion de distance

          Posté par  . Évalué à 1.

          Effectivement.
          Dans ce cas, je te propose de ne pas tirer au sort mais de prendre celui qui a rendu en premier sa liste de choix.
          Ou alors, encore plus arbitraire, le premier dans l'ordre alphabétique.

          Je ne suis pas capable de formaliser le problème comme dans les messages au dessus. Il me semble "à vue de nez" que ma solution n'est pas loin de l'optimum puisqu'un maximum de personnes aura son premier choix, un maximum son second, etc… Il n'y aura pas de cas où un projet ayant été classé en 1 par quelqu'un sera donné à un autre l'ayant classé à un autre rang. Ce que je n'arrive pas à voir/imaginer c'est si toute les solutions (quand on utilise le hasard) seront équivalentes et aussi satisfaisantes.

          Mais je suis intéressé par savoir quelle procédure aura été retenue.

  • # algoritme du vrai "chef"

    Posté par  . Évalué à 3.

    "premier arrivé, premier servi, reponse demandé avant le 15 octobre."

    comme ca ils se bougeront pour te repondre et etre satisfait

    • [^] # Re: algoritme du vrai "chef"

      Posté par  (site web personnel) . Évalué à 1.

      si je n'arrive pas à mettre au point l'algo de minimisation du nombre de "clients" insatisfait ça pourrait tourner à une version proche de ça… mais bon je suis pas un vrai "chef"… je suis juste prof ;-)

  • # Mariages stables

    Posté par  . Évalué à 3.

    Ce ne serait pas équivalent au problème des mariages stables ? (il y a l'algo sur wikipedia)
    Problème_des_mariages_stables

    • [^] # Re: Mariages stables

      Posté par  . Évalué à 3.

      pas mal du tout, meme si on voit que l'algo date de quelques années (c'est l'homme qui choisit sa femme ;) )

      on voit bien que cela peut s'appliquer à l'etudiant qui choisit son projet,
      et ca leve une contrainte car il n'y pas à calculer l'affinité du projet avec l'etudiant (ce qui est le cas dans cet algo qui regarde l'affinité de la femme avec l'homme, meme si c'est l'homme qui choisit)

  • # Et de 20

    Posté par  . Évalué à 3.

    Rajoute ce problème dans la liste des projets. pour cette année c'est rapé, mais l'an prochain tu devrais avoir une solution.

    ->[]

    • [^] # Re: Et de 20

      Posté par  (site web personnel) . Évalué à 1. Dernière modification le 24 septembre 2013 à 20:24.

      on fait (presque) pas d'info… chez nous c'est plutôt plomberie, chauffage et énergies renouvelables

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.