Grouping of people multiple times, where all the members meet each other in the same group at least once

Question

I want to group people into smaller subgroups, and after shuffling groups multiple times for successive sessions, make all the people meet each other at least once.

1. In every session, people are divided into a constant number of groups. Everyone has to join one group in every session.
2. The group size should be closest to (the number of people)/(# of groups). There should not be a groups of too few people or too many people.
3. The sessions are continued until every pair of people meets each other at least once.
4. Preferably, the number of times the same pair meet each other should be minimized.

The following is the answer for this problem for 11 people (numbered 0-10) and 3 groups (3 columns). It requires 5 sessions.

Session 1: 3,6,8,10     0,1,7,9     2,4,5
Session 2: 3,5,7,8      0,1,2,10    4,6,9
Session 3: 0,1,6,8      2,3,4,9     5,7,10
Session 4: 0,3,5,9      1,4,8,10    2,6,7
Session 5: 1,3,5,6      2,8,9,10    0,4,7

Members of two groups of different size must meet each other (1v1, once)

The question above is similar, but I want rather make the people meet just in a group of a larger group, not 1-on-1.

The following is my approach that uses Alloy. This works for a small number of people (~15) and groups (~2), but it quickly causes computation time explosion when the size is increased. I need to calculate it for ~25 people and ~5 groups.

module Teaming

sig Person { groups: some Group }

sig Group { people: some Person }

sig Session { groups: some Group }

one sig Sessions { sessions: some Session }

sig GroupPerSession {}

-- Tree structures
fact {
    all s: Session | s in Sessions.sessions
    all g: Group | g in Session.groups
    all s: Session | all p:Person | p in s.groups.people
    people =~ groups
}

-- The total number of people
fact {
    all s: Session | #s.groups.people = #Person
}

-- The number of groups per session
fact {
    all s: Session | #s.groups = #GroupPerSession
}

-- The number of people in a group
fact {
    all g: Group | (#g.people) >= div[#(Person), #(GroupPerSession)] and (#g.people) <= add[div[#Person,#GroupPerSession],1]
}

-- Mutually exclusive grouping in a session
fact separate {
    all s: Session | all disj a,b: s.groups | no p: Person | p in a.people and p in b.people
}

-- Every pair of people meets somewhere
pred sameGroup {
    all disj a,b: Person | some g: Group | a in g.people and b in g.people
}

-- The same people should not meet too many times
fact sameGroupNotTooMuch {
    all disj a,b: Person | #{a.groups & b.groups} <= 3
}

run sameGroup for 6 Int, 5 Session, 15 Group, exactly 3 GroupPerSession, exactly 16 Person
run sameGroup for 6 Int, 6 Session, 24 Group, exactly 4 GroupPerSession, exactly 18 Person
run sameGroup for 6 Int, 7 Session, 35 Group, exactly 5 GroupPerSession, exactly 18 Person

I guess dynamic programming should work, though I cannot find anything specific. Any pointer for the improvement in Alloy code or other algorithms would be great.

Answer 1

I do not think Alloy is the right tool for optimisation. It is a specification tool that focuses on finding counter examples. However, it can of course be found to find solutions to puzzles like this. (I think there is a group that developed an extension to Alloy that minimises the found solutions.)

I took a stab though I am a beginner. Surprisingly I found a solution with 4 sessions 11 people and 3 groups.

  s0   {2,9,10},  {5,6,7,8},  {0,1,3,4}, 
  s1   {2,4,7,8}, {1,3,6,10}, {0,5,9}, 
  s2   {1,2,3,5}, {0,7,8,10}, {4,6,9}, 
  s3   {0,2,6},   {4,5,10},   {1,3,7,8,9} 

Since Alloy is not an optimiser I used the binary way to find the minimum number of sessions, I found that you needed at least 7 sessions for 25/5.

This is my full model:

sig P, Group {}
sig Session {
  participants : Group -> P
}

fact {
  // tuning goes here (max sure <= scope )
  # Group = 5
  # P = 25
  # Session = 7

  // In every session, people are divided into a constant number 
  // of groups.
  all s : Session | s.participants.P = Group

  // The sessions are continued until every pair of people 
  // meets each other at least once.
  // Preferably, the number of times the same pair meet 
  // each other should be minimized.
  all disj a,b : P | some participants.a & participants.b

  // Everyone has to join one group in every session.
  all p : P, s : Session | one s.participants.p

  // The group size should be closest to (the number 
  // of people)/(# of groups).
  // There should not be a 
  // groups of too few people or too many people.
  all g : Group, s : Session | (# s.participants[g]) >= 3
}

run {} for 5 Group, 25 P, 24 Session, 6 int

Specifying the int width for these number is crucial.

Finding a series of 8 sessions took 5 seconds, finding the 7 sessions took much longer, 34 seconds. Forcing a more equal group size by increasing the minimum is still running :-)

I think the tool does exactly what it is supposed to do: finding a solution. It is not that good in finding an optimal solution.

Answer 2

Here's my quick shot at solving this problem. Overall, the generation of instance seems faster, but still have difficulty to complete when trying to assign >20 people into >4 groups.

module Teaming

one sig Settings{
    maxEncounter:Int,
    minGroupSize:Int,
    maxGroupSize:Int
}{
// Manually filling values there helps (1)reducing the integer bit-width needed (2) decrease the complexity (in terms of clauses)
  maxEncounter=4
 //minGroupSize=5
 //maxGroupSize=5
  minGroupSize=div[#Person, #Group]
  maxGroupSize=add[minGroupSize,1]
}

sig Session{}{
    Group.people[this]=Person // all person are assigned in group during a session
    no disj g1,g2 :Group| g1.people[this]  & g2.people [this] !=none // a person can't be in two disjoint groups of a same session

}

sig Group { 
    people: Session some -> some Person 
}{
   all s:Session|  #people[s]<= Settings.maxGroupSize and   #people[s]>=Settings.minGroupSize 
}

sig Person {}


pred allMeet {
    all disj a,b: Person | people. a & people.b != none->none
}

pred allMeetAndMinEncounter {
    all disj a,b: Person | let x= (people. a & people.b) {
        #x <=Settings.maxEncounter
        x != none ->none
   }
}


run allMeet for 6 Int, 9 Session, exactly 4 Group, exactly 20 Person

Highlight of the changes brought:

• Removed quantifications when possible
• Removed redundant constraints
• Replaced the two binary relations groups and people by a ternary relation. This comes with several advantages:
  • It reduces the number of group atoms present in an instance to the total of group per session.
  • It enables the use of instance projection in the instance viewer. You'll now be able e.g. to view group assignment for each session separately.