constraint satisfaction problem missing one constraint

Question

I'm a lab practises tutor at the university, based on last year student comments, we wanted, my boss and I, to address them. My boss chose to go with writing a C script and I pick python (python-constraint) to try to resolve our problem.

Informations

There are 6 sessions
There are 4 roles
There are 6 practices
There are 32 students
There are 4 students per team

Problem :

Assign each student to 4 roles, in 4 practices in 4 different sessions.

Constraints :

Students should do a role once
Students should do 4 different practices out of 6
Students should do only one practice per session
Student should meet the same mate only once

Templates :

Here is the template that I feel with students, where each team is composed of 4 students, positions [0, 1, 2 or 3] are roles assigned to them. Each available position is numbering from 1 to 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]]]

In other words :

This is a 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]],

Those team do the same practice:

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

Those position do the same role :

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

What I have so far :

Using python-constraint I was able to validate the first three constraints :

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]

For those that may interesting I simply do like this :

For each condition I use AllDifferentConstraint. For example, for one session I do:

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

I'm not able to find a way to constraint team, my last attempt on the entire semester was this :

    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

Questions :

Is it possible to do what I want for the team conditions ? What I mean is I have no idea if it is possible to assign 12 mates to each student and each of them meet the same mate only once.
For the team constraint, did I miss a more performant algorithm ?
Any pist that I can follow ?

Why are the last two sets of sessions a shape of `(4, 4)` instead of `(4, 6)` like the others? — r.ook, Dec 04 '19 at 20:06
It's to match the fact that this course is only one credit and require a lot of job, so my boss deside that students should only do 4 practices. So we came up with this, we have 32 students, that should do 4 practices (128 positions). — Florian Bernard, Dec 04 '19 at 23:48
I would try random and brute force approach. Just do like a permutation where you pick Session 1: Role 1 Student 1 Practice 1... same with 2 to 4. Then increment for each 6 sessions, discard already met students. Same with random. Why 128 positions and not use per Session 32 number of students as max in different permutations? Maybe in stackMath they can tell you if this is possible combination/permutation — Cristo, Dec 06 '19 at 21:37
Currently the brute force method work, my boss came back to me with its script and its work really well. But I still want t use python. — Florian Bernard, Dec 07 '19 at 04:41

Konchog · Accepted Answer · 2019-12-11T18:45:14.013

The main question would be answered with something like...

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

Added Edit

I had another look at your problem yesterday - (admittedly not long, as I have a lot of work on at the moment), and...

First of all, I see that your 'team' entity, is pretty much what I called an 'action' entity, and in retrospect I think 'team' (or 'group') was a better word for it.

If you are still finding the constraints hard, I suggest you break them out, and work on them individually - particularly the team/person/session constraints, followed by the role/task constraints.

/Added Edit

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

I had a similar problem recently, and in the end turned to OR-tools. https://developers.google.com/optimization/cp/cp_solver

Particularly, have a look at the nurse scheduling problem: https://developers.google.com/optimization/scheduling/employee_scheduling#nurse_scheduling

Anyhow, the problem is not too complex, so maybe using a solver would be overkill for you.

Likewise, for this sort of problem it may be better to use a tuple-keyed dict to hold your variables, rather than nested lists:

{ Team, Session, Person: BoolVar }

The main reason is that you can then apply constraints via filters, which is much easier than having to do nested list manipulations, for instance, to apply a constraint across persons/teams, you can do (where person is index 2 and team is 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

Thanks, for the for loop did you mean `p for p in all_people` ? — Florian Bernard, Dec 10 '19 at 20:31
Yeah - sorry! I ‘translated’ my names to your model, but was at work so was a bit quick. — Konchog, Dec 10 '19 at 21:20
Also, the mailing list is really supportive at OR-tools. If you need help with modelling your problem they will point you to example code or give you a great idea about how to set group/dependency constraints — Konchog, Dec 10 '19 at 21:22
I'm sorry but your head solution is difficulte to follow, where do come from the self ? And what P, S and G variables are ? What is pv ? Thanks for your help. — Florian Bernard, Dec 13 '19 at 17:06

score 0 · Answer 2 · answered Dec 06 '19 at 21:57

Just a permutation algorithm idea, for each iteration could be focused on one of each students or in one of each 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

Here student 2 takes place of student 1 in session 1 and goes on like this

Roles 1234
St 2,5,6,7

Continue with student 1 S3 R 1234 St 10,9,1,8

S4
R 1234
St 11,12,13,1

On the end you remove interactions for student 1, like on permutations for the next iteration you remove current.

It's like a rubiks cube.

If you get to code this or know some code with this algo let me know.

Maybe with the itertools permutations

Sessions being > than practices I believe is not that relevant its number. Just some pool to take more when you run out or more room for the rotation. Maybe could simplify the problem first aiming for 4 sessions = practices?