Integer Programming for Finding Good Groups in Teaching

So, in a few weeks we are offering the Extreme Programming Lab again. This time we have 20 participants. Last year, we had a few (though not huge) problems, because the groups weren't assigned very evenly. We typically work with two groups who each realize a project in XP style. I got to admit, this uneven assignment was my fault. Back then, I assigned the persons randomly and shifted them them a little according to what i thought i knew about their capabilities.

This year, i decided to go a different route. For the lab application, i specifically asked for specific capabilities and what the participants thought how good they were at them. According to their statements, i classified each statement to points between 0 and 2. With 0 meaning "little knowledge", 1 meaning "normal knowledge" and 2 meaning "good knowledge". I collected a total of 10 different capabilities. So the question now is, how do i find good groups. My optimal groups would be where every capability is covered by the same degree of points. Moving the participants around in Excel to find a good solution is obviously pretty tedious. After all there are quite a lot of different combinations for those two groups.

A few years back, i heard a lecture about traffic planning and learnt about integer programming. After some thinking, i came to the conclusion that this is pretty much the same stuff and that integer programming would be the right tool to solve this problem. Therefore, i downloaded the student version of Xpress-IVT as i remembered that i liked Mosel a lot back then. I wasn't wrong. A few hours later (geeeze, you can't write your phd thesis all the time!), i had a working Mosel integer program that in fact solved my little problem for finding optimal groups with evenly distributed knowledge. Maybe someone enjoys this as much as i did. So here it is (Names have been anonymized of course):

model "Participants Assignment to Groups"
uses "mmxprs","mmquad","mmive";

declarations
PERSONS = 1..20
GROUPS = 1..2
SKILL_DIMENSIONS = 1..10
SKILLS: ARRAY(SKILL_DIMENSIONS,PERSONS) of integer
SKILL_SUMS: ARRAY(SKILL_DIMENSIONS) of integer
PERSON_NAMES: ARRAY(PERSONS) of string
SKILL_NAMES: ARRAY(SKILL_DIMENSIONS) of string
allowed_deviation = 1

assign: ARRAY(PERSONS,GROUPS) of mpvar
end-declarations

initializations from "initdata.dat"
SKILL_NAMES
PERSON_NAMES
SKILLS
end-initializations

groupCount := getsize(GROUPS);
personCount := getsize(PERSONS);

writeln("Number of groups: ", groupCount);
writeln;

forall(d in SKILL_DIMENSIONS) do 
    SKILL_SUMS(d) := 0;
    forall(p in PERSONS) do 
        SKILL_SUMS(d) += SKILLS(d,p);
    end-do
end-do

forall(d in SKILL_DIMENSIONS) do
    writeln("Skill sum for ", SKILL_NAMES(d),": ",SKILL_SUMS(d), " - average per group: ", SKILL_SUMS(d)/groupCount)
end-do

GoodGroups := sum(d in SKILL_DIMENSIONS, p in PERSONS, g in GROUPS) SKILLS(d,p)*assign(p,g)

forall(p in PERSONS) sum(g in GROUPS) assign(p,g) = 1 ! every person is in one group only

forall(g in GROUPS) sum(p in PERSONS) assign(p,g) = personCount / groupCount !groupCount ! every group has a maximum of groupCount persons

forall(d in SKILL_DIMENSIONS) forall(g in GROUPS) sum(p in PERSONS) SKILLS(d,p)*assign(p,g) >= SKILL_SUMS(d)/groupCount - allowed_deviation

forall(d in SKILL_DIMENSIONS) forall(g in GROUPS) sum(p in PERSONS) SKILLS(d,p)*assign(p,g) <= SKILL_SUMS(d)/g

The data file looks something like this:

PERSON_NAMES: ["Person 1",
      ...
"Person 20"]

SKILL_NAMES: ["Eclipse",
"DB/SQL",
"SVN",
"UML",
"Design Patterns",
"Refactoring",
"Testing",
"GUI",
"Web",
"Java"]

SKILLS: [1,0,0,1,2,2,2,2,2,2,2,0,0,0,0,0,2,2,2,2,
   2,2,2,0,1,2,2,2,2,2,2,2,2,2,2,1,1,2,2,2,
...
   0,1,2,1,1,2,2,2,1,1,2,1,1,1,1,1,1,1,1,2]

I hope there is nothing wrong with this little Mosel program. I have to say that i really enjoy optimization every time there is reason to use it. You don't understand what i'm doing here? Just learn a little about linear optimization and integer programming. This is great fun!