Group assignment problem with optimisation methods

Question

There’s a company organising a seminar, where 60 trainees will attend. The company plans to divide the participants into 10 groups, each of 6 trainees. Each of the trainees was asked beforehand to choose 5 other trainees they would like to work with. And each of the five is weighted equally. The problem is how we can assign the participants into groups so that the total satisfaction could to optimised.

Answer 1

let me give you a small example with CPO within CPLEX in OPL:

//There’s a company organising a seminar, where 60 trainees will attend. 
//The company plans to divide the participants into 10 groups, each of 6 trainees. 
//Each of the trainees was asked beforehand to choose 5 other trainees they would like to work with. 
//And each of the five is weighted equally. 
//The problem is how we can assign the participants into groups so that the total satisfaction could to optimised. 

using CP;

execute
{
cp.param.timelimit=20;
}

int nbTrainees=60;
int nbGroups=10;
int nbWishes=5;
int sizeGroup=nbTrainees div nbGroups;



range trainees=1..nbTrainees;
range groups=1..nbGroups;
range likes=1..nbWishes;

// let us start with the nbWishes next trainees
int wishes[t in trainees][w in likes]=(t+w-1) mod nbTrainees+1;

assert forall(t in trainees,w in likes) wishes[t][w] in trainees;
assert forall(t in trainees,w in likes) wishes[t][w] != t;

// a gievn trainee belongs to a given group ?
dvar boolean x[trainees][groups];

dvar int satisfaction;

maximize satisfaction;
subject to
{

// trainees belong to one and only one group
forall(t in trainees) sum(g in groups) x[t][g]==1;

// group size
forall(g in groups) sum(t in trainees) x[t][g]==sizeGroup;

// satisfaction formula
satisfaction==sum(t in trainees,w in likes,g in groups) ((x[t][g]*x[wishes[t][w]][g]));

}

{int} team[g in groups]={ i | i in trainees : x[i][g]==1};

execute
{
writeln(team);
}