Problem der Einschränkungszufriedenheit, bei dem eine Einschränkung fehlt

13

Ich bin ein Tutor für Laborpraktiken an der Universität, basierend auf den Kommentaren der Studenten aus dem letzten Jahr, die wir, mein Chef und ich, ansprechen wollten. Mein Chef hat sich entschieden, ein C-Skript zu schreiben, und ich habe Python (Python-Einschränkung) ausgewählt, um unser Problem zu lösen.

Informationen

  • Es gibt 6 Sitzungen
  • Es gibt 4 Rollen
  • Es gibt 6 Übungen
  • Es gibt 32 Studenten
  • Es gibt 4 Studenten pro Team

Problem :

Weisen Sie jedem Schüler 4 Rollen in 4 Übungen in 4 verschiedenen Sitzungen zu.

Einschränkungen:

  1. Die Schüler sollten einmal eine Rolle spielen
  2. Die Schüler sollten 4 von 6 verschiedenen Übungen machen
  3. Die Schüler sollten nur eine Übung pro Sitzung machen
  4. Der Schüler sollte denselben Partner nur einmal treffen

Vorlagen:

Hier ist die Vorlage, die ich für Schüler empfinde, bei der jedes Team aus 4 Schülern besteht. Den Positionen [0, 1, 2 oder 3] sind Rollen zugewiesen. Jede verfügbare Position ist von 1 bis 128 nummeriert

[# 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]]]

Mit anderen Worten :

Dies ist eine Sitzung:

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

Diese Teams machen die gleiche Übung:

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

Diese Positionen spielen die gleiche Rolle:

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

Was ich bisher habe:

Mit Python-Constraint konnte ich die ersten drei Constraints validieren:

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]

Für diejenigen, die interessant sein mögen, mag ich einfach Folgendes:

Für jede Bedingung verwende ich AllDifferentConstraint . Zum Beispiel mache ich für eine Sitzung:

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])

Ich bin nicht in der Lage, das Team einzuschränken. Mein letzter Versuch im Großen und Ganzen semesterwar folgender:

    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

Fragen :

  1. Kann ich für die Teambedingungen tun, was ich will? Ich meine, ich habe keine Ahnung, ob es möglich ist, jedem Schüler 12 Partner zuzuweisen, und jeder von ihnen trifft denselben Partner nur einmal.
  2. Habe ich für die Teambeschränkung einen performanteren Algorithmus verpasst?
  3. Irgendeine Pistole, der ich folgen kann?
Florian Bernard
quelle
1
Warum haben die letzten beiden Sitzungsgruppen eine Form von (4, 4)anstatt (4, 6)wie die anderen?
r.ook
Es ist passend zu der Tatsache, dass dieser Kurs nur eine Gutschrift ist und viel Arbeit erfordert, also mein Chef beschließt, dass die Schüler nur 4 Übungen machen sollten. Also haben wir uns das ausgedacht, wir haben 32 Studenten, die 4 Übungen machen sollten (128 Positionen).
Florian Bernard
1
Ich würde versuchen, zufällige und Brute-Force-Ansatz. Machen Sie einfach eine Permutation, bei der Sie Sitzung 1 auswählen: Rolle 1 Schüler 1 Übung 1 ... wie bei 2 bis 4. Inkrementieren Sie dann für jeweils 6 Sitzungen bereits getroffene Schüler. Gleiches gilt für zufällige. Warum 128 Positionen und nicht pro Sitzung 32 Studenten als Maximum in verschiedenen Permutationen verwenden? Vielleicht können sie Ihnen in stackMath sagen, ob dies eine mögliche Kombination / Permutation ist
Cristo
Derzeit arbeitet die Brute-Force-Methode, mein Chef kam mit seinem Skript und seiner Arbeit wirklich gut zu mir zurück. Aber ich möchte immer noch kein Python verwenden.
Florian Bernard

Antworten:

2

Die Hauptfrage würde mit so etwas wie ...

   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)) 

Bearbeiten hinzugefügt

Ich habe mir gestern Ihr Problem noch einmal angesehen - (zugegebenermaßen nicht lange, da ich gerade viel Arbeit habe) und ...

Zunächst sehe ich, dass Ihre "Team" -Entität so ziemlich das ist, was ich als "Aktions" -Entität bezeichnet habe, und im Nachhinein denke ich, dass "Team" (oder "Gruppe") ein besseres Wort dafür war.

Wenn Sie die Einschränkungen immer noch als schwierig empfinden, empfehlen wir Ihnen, sie aufzubrechen und einzeln zu bearbeiten - insbesondere die Einschränkungen für Team / Person / Sitzung, gefolgt von den Einschränkungen für Rolle / Aufgabe.

/ Bearbeiten hinzugefügt

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

Ich hatte kürzlich ein ähnliches Problem und wandte mich am Ende den OP-Werkzeugen zu. https://developers.google.com/optimization/cp/cp_solver

Sehen Sie sich insbesondere das Problem mit der Planung von Krankenschwestern an: https://developers.google.com/optimization/scheduling/employee_scheduling#nurse_scheduling

Wie auch immer, das Problem ist nicht zu komplex, daher wäre die Verwendung eines Lösers für Sie möglicherweise übertrieben.

Ebenso ist es für diese Art von Problem möglicherweise besser, ein Diktat mit Tupelschlüssel zu verwenden, um Ihre Variablen zu speichern, als verschachtelte Listen:

{Team, Sitzung, Person: BoolVar}

Der Hauptgrund ist, dass Sie dann Einschränkungen über Filter anwenden können, was viel einfacher ist, als verschachtelte Listenmanipulationen durchführen zu müssen, um beispielsweise eine Einschränkung auf Personen / Teams anzuwenden (wobei Person Index 2 und Team Index ist) 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
quelle
1
Danke, für die for-Schleife meintest du p for p in all_people?
Florian Bernard
1
Ja entschuldigung! Ich habe meine Namen in Ihr Modell 'übersetzt', war aber bei der Arbeit und war ein bisschen schnell.
Konchog
1
Auch die Mailingliste ist bei OR-Tools sehr hilfreich. Wenn Sie Hilfe bei der Modellierung Ihres Problems benötigen, werden Sie auf Beispielcode verwiesen oder erhalten eine gute Vorstellung davon, wie Sie Gruppen- / Abhängigkeitsbeschränkungen festlegen können
Konchog,
Es tut mir leid, aber es ist schwierig, Ihrer Kopflösung zu folgen. Woher kommt das Selbst? Und was sind P-, S- und G-Variablen? Was ist pv? Danke für Ihre Hilfe.
Florian Bernard
0

Nur eine Idee für einen Permutationsalgorithmus, bei der jede Iteration auf einen der Schüler oder auf eine Sitzung konzentriert werden kann:

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

Hier findet Schüler 2 in Sitzung 1 von Schüler 1 statt und geht so weiter

Roles 1234
St 2,5,6,7 

Weiter mit Schüler 1 S3 R 1234 St 10,9,1,8

S4
R 1234
St 11,12,13,1

Am Ende entfernen Sie Interaktionen für Schüler 1, wie bei Permutationen für die nächste Iteration, die Sie aktuell entfernen.

Es ist wie ein Zauberwürfel.

Wenn Sie dies codieren oder einen Code mit diesem Algo kennen, lassen Sie es mich wissen.

Vielleicht mit den itertools Permutationen

Sitzungen, die> als Praktiken sind, sind meiner Meinung nach nicht so relevant für ihre Anzahl. Nur ein Pool, um mehr zu nehmen, wenn Sie ausgehen oder mehr Platz für die Rotation. Vielleicht könnte das Problem vereinfacht werden, indem zuerst 4 Sitzungen = Übungen angestrebt werden?

Cristo
quelle