problème de satisfaction de contrainte manquant une contrainte

13

Je suis un professeur de pratiques de laboratoire à l'université, sur la base des commentaires des étudiants de l'année dernière, nous voulions, mon patron et moi, y répondre. Mon patron a choisi d'aller avec l'écriture d'un script C et je choisis python (python-constraint) pour essayer de résoudre notre problème.

Les informations

  • Il y a 6 séances
  • Il y a 4 rôles
  • Il y a 6 pratiques
  • Il y a 32 étudiants
  • Il y a 4 étudiants par équipe

Problème:

Attribuez à chaque élève 4 rôles, dans 4 pratiques en 4 sessions différentes.

Contraintes :

  1. Les étudiants devraient jouer un rôle une fois
  2. Les étudiants doivent faire 4 pratiques différentes sur 6
  3. Les étudiants ne doivent faire qu'une seule pratique par session
  4. L'élève ne doit rencontrer le même compagnon qu'une seule fois

Modèles:

Voici le modèle que je ressens avec les étudiants, où chaque équipe est composée de 4 étudiants, les postes [0, 1, 2 ou 3] sont des rôles qui leur sont assignés. Chaque poste disponible est numéroté de 1 à 128

[# Semester
   [ # Session
     [ # Practice/Team
1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],
 [[25, 26, 27, 28],
  [29, 30, 31, 32],
  [33, 34, 35, 36],
  [37, 38, 39, 40],
  [41, 42, 43, 44],
  [45, 46, 47, 48]],
 [[49, 50, 51, 52],
  [53, 54, 55, 56],
  [57, 58, 59, 60],
  [61, 62, 63, 64],
  [65, 66, 67, 68],
  [69, 70, 71, 72]],
 [[73, 74, 75, 76],
  [77, 78, 79, 80],
  [81, 82, 83, 84],
  [85, 86, 87, 88],
  [89, 90, 91, 92],
  [93, 94, 95, 96]],
 [[97, 98, 99, 100],
  [101, 102, 103, 104],
  [105, 106, 107, 108],
  [109, 110, 111, 112]],
 [[113, 114, 115, 116],
  [117, 118, 119, 120],
  [121, 122, 123, 124],
  [125, 126, 127, 128]]]

En d'autres termes :

Ceci est une session: 

 [[1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],

Ces équipes font la même pratique: 

[
    [1, 2, 3, 4],
    [25, 26, 27, 28],
    [49, 50, 51, 52],
    [73, 74, 75, 76],
    [97, 98, 99, 100],
    [113, 114, 115, 116]
]

Ces positions jouent le même rôle: 

[
   1,
   5,
   9,
   13,
   17,
   21,
   25,
   ...
]

Ce que j'ai jusqu'à présent:

En utilisant python-constraint, j'ai pu valider les trois premières contraintes:

Valid solution : False
            - sessions  : [True, True, True, True, True, True]
            - practices : [True, True, True, True, True, True]
            - roles     : [True, True, True, True]
            - teams     : [False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False]

Pour ceux qui peuvent être intéressants, je fais simplement ceci:

Pour chaque condition, j'utilise AllDifferentConstraint . Par exemple, pour une session, je fais:

problem.addConstraint(AllDifferentConstraint(), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24])

Je ne suis pas en mesure de trouver un moyen de contraindre l'équipe, ma dernière tentative dans l'ensemble a semesterété la suivante:

    def team_constraint(self, *semester):
        students = defaultdict(list)

        # get back each teams based on the format [# Semester [ #Session [# Practice/Team ... 
        teams = [list(semester[i:i+4]) for i in range(0, len(semester), 4)]

        # Update Students dict with all mate they work with
        for team in teams:
            for student in team:
                students[student] += [s for s in team if s != student]

        # Compute for each student if they meet someone more than once 
        dupli = []
        for student, mate in students.items():
            dupli.append(len(mate) - len(set(mate)))

        # Loosly constraint, if a student meet somone 0 or one time it's find
        if max(dupli) >= 2:
            print("Mate encounter more than one time", dupli, min(dupli) ,max(dupli))
            return False
        pprint(students)
        return True

Des questions :

  1. Est-il possible de faire ce que je veux pour les conditions de l'équipe? Ce que je veux dire, c'est que je n'ai aucune idée s'il est possible d'affecter 12 camarades à chaque élève et que chacun d'eux ne rencontre le même compagnon qu'une seule fois.
  2. Pour la contrainte d'équipe, ai-je manqué un algorithme plus performant?
  3. Des pistons que je peux suivre?
python algorithm python-constraint Florian Bernard
la source
1
Pourquoi les deux dernières séries de sessions ont-elles une forme (4, 4)plutôt (4, 6)que les autres?
r.ook
C'est pour correspondre au fait que ce cours n'est qu'un seul crédit et nécessite beaucoup de travail, donc mon patron souhaite que les étudiants ne fassent que 4 pratiques. Nous avons donc trouvé cela, nous avons 32 étudiants, qui devraient faire 4 pratiques (128 postes).
Florian Bernard
1
J'essaierais l'approche par force aléatoire et brutale. Faites comme une permutation où vous choisissez Session 1: Rôle 1 Étudiant 1 Entraînez-vous 1 ... même avec 2 à 4. Ensuite, incrémentez pour chaque 6 sessions, jetez les étudiants déjà rencontrés. Même chose avec le hasard. Pourquoi 128 postes et ne pas utiliser par session 32 d'étudiants au maximum dans différentes permutations? Peut-être que dans stackMath, ils peuvent vous dire si c'est une combinaison / permutation possible
Cristo
Actuellement, la méthode de la force brute fonctionne, mon patron est revenu vers moi avec son script et son travail vraiment bien. Mais je veux toujours utiliser python.
Florian Bernard

Réponses:

2

On répondrait à la question principale par quelque chose comme ...

   def person_works_with_different():
        # over all the sessions, each person works with each other person no more than once.
        # 'works with' means in 'same session team'
        for p in all_people:
            buddy_constraint = []
            for s in all_sessions:
                for g in all_teams:
                    p_list = [pv[k] for k in filter(lambda i: i[P] == p and i[S] == s and i[G] == g, pv)]
                    for o in all_people:
                        if o != p:  # other is not person
                            o_list = [self.pv[k] for k in filter(lambda i: i[self.P] == o and i[self.S] == s and i[self.G] == g, self.pv)]
                            tmp = model.NewBoolVar('')
                            buddy_constraint.append(tmp)
                            model.Add(sum(o_list) == sum(p_list)).OnlyEnforceIf(tmp)
                            # tmp is set only if o and p are in the same session/team
            # The number of times a student gets to take part is the number of roles.
            # The size of the group controlled by the number of roles
            model.Add(sum(buddy_constraint) = all_roles * (all_roles - 1))

Ajouté Modifier

J'ai revu votre problème hier - (certes pas longtemps, car j'ai beaucoup de travail en ce moment), et ...

Tout d'abord, je vois que votre entité «équipe» est à peu près ce que j'ai appelé une entité «action» et, rétrospectivement, je pense que «équipe» (ou «groupe») était un meilleur mot pour cela.

Si vous trouvez toujours les contraintes difficiles, je vous suggère de les décomposer et de les travailler individuellement - en particulier les contraintes équipe / personne / session, suivies des contraintes rôle / tâche.

/ Modification ajoutée 

team: a gathering of 4 persons during a session
person (32): a participant of a team
session (6): time: eg, 8am -10am
role (4): what responsibility a person has in an action
task (6): type of action

A person does:
 0..1 action per session-group
 1 role per action
 1 task per action
 0..1 of each task
 1 of each role in an action
 4 persons in an action

A person meets each other person 0..1 times
An action requires exactly 4 people

J'ai eu un problème similaire récemment et je me suis finalement tourné vers les outils OR. https://developers.google.com/optimization/cp/cp_solver

En particulier, jetez un œil au problème de planification des infirmières: https://developers.google.com/optimization/scheduling/employee_scheduling#nurse_scheduling

Quoi qu'il en soit, le problème n'est pas trop complexe, alors peut-être que l'utilisation d'un solveur serait exagéré pour vous.

De même, pour ce type de problème, il peut être préférable d'utiliser un dict à clé double pour contenir vos variables, plutôt que des listes imbriquées:

{Équipe, session, personne: BoolVar}

La raison principale est que vous pouvez ensuite appliquer des contraintes via des filtres, ce qui est beaucoup plus facile que d'avoir à manipuler des listes imbriquées, par exemple, pour appliquer une contrainte à travers des personnes / équipes, vous pouvez le faire (où personne est l'index 2 et l'équipe est l'index 0):

for p in all_persons:
    for t in all_teams:
        stuff = [b_vars[k] for k in filter(lambda i: i[2] == p and i[0] == t, b_vars)]
        model.Add(sum(stuff) == 4)  # persons per team == 4
Konchog
la source
1
Merci, pour la boucle for vouliez-vous dire p for p in all_people?
Florian Bernard
1
Ouais désolé! J'ai «traduit» mes noms sur votre modèle, mais j'étais au travail, donc j'ai été un peu rapide.
Konchog
1
De plus, la liste de diffusion est vraiment favorable aux outils OR. Si vous avez besoin d'aide pour modéliser votre problème, ils vous indiqueront un exemple de code ou vous donneront une excellente idée de la façon de définir les contraintes de groupe / de dépendance
Konchog
Je suis désolé mais votre solution principale est difficile à suivre, d'où vient le moi? Et quelles sont les variables P, S et G? Qu'est-ce que le PV? Merci de votre aide.
Florian Bernard
0

Juste une idée d'algorithme de permutation, pour chaque itération pourrait être concentrée sur un de chaque étudiant ou dans une de chaque session:

Session 1:
Roles
1,2,3,4
Students
1,2,3,4

(Note is 1st permutation 1234)

Sess 2 for student 1
Roles 1234
Students 5,1,7,6

Ici, l'étudiant 2 prend la place de l'étudiant 1 dans la session 1 et continue comme ça

Roles 1234
St 2,5,6,7

Continuer avec l'élève 1 S3 R 1234 St 10,9,1,8

S4
R 1234
St 11,12,13,1

À la fin, vous supprimez les interactions pour l'étudiant 1, comme sur les permutations pour la prochaine itération que vous supprimez en cours.

C'est comme un cube rubiks.

Si vous arrivez à coder ceci ou connaissez du code avec cet algo, faites le moi savoir.

Peut-être avec les permutations d' itertools

Les sessions étant> que des pratiques, je crois que ce n'est pas pertinent son nombre. Juste un peu de piscine pour en prendre plus quand vous manquez ou plus de place pour la rotation. Peut-être pourrait simplifier le problème en visant d'abord 4 séances = pratiques?

Cristo
la source