My Constraint Programming Blog

This blog post is my entry in December Blog Challenge: O.R. and the Holidays. (Note: since I'm not a INFORMS member, this entry might get disqualified.)

This week my company (the local office) is having the annually Christmas gathering and we will - after eating some good Brazilian food - go bowling.

Mixing the teams as good as possible in these kind of gatherings can be quite important and I have here created a MiniZinc model (company_competition.mzn) for this.

Problem statement

In this problem I have decided that the teams should be picked (mixed) according to the following requirements (see below for other considerations):

• We are in total 18 contestants and there should be 4 or 5 persons in each team, which gives 4 teams. (Different teams sizes are discussed below.)
• There should be as even distribution of sexes in each team as possible. There are 12 males and 6 females.
• There are 3 departments (IT, Custom relations 1, Custom relations 2) and these should be mixed as much as possible. As it happens, all 3 departments consists of 6 persons each.
• The managers for each department should be in different teams, if possible.

The number of violations of these requirements is then minimized (the variable z in the model).

MiniZinc model

The MiniZinc model used is company_competition.mzn.

This model is slightly simplified and includes our first names and departments for realism (I'm "hakan" as you may have guessed). For general use of this model - e.g. our the next Christmas competition, or by some other company - the problem instance should have been in a separate data file (this is easy to fix), but for clarity I've kept everything is the same file.

The hardest part in modeling this problem was the following which required a lot of experimenting.

• The way to measure the violations is very important to get a good (fair) mixing, and took quite a time. Some of the rejected measurements has been kept (commented) in the model. See below for a comparison of two different measurements.
• To no surprise it took quite a time to get the labeling as good as possible. It may - of course - be a better labeling, but I have not found any.
• Testing different symmetry breaking constraints.

Results

For Gecode/fz, MiniZinc/fd, and JaCoP/fz the optimal value of z (14) was found almost immediately (< 1 second). However, after that it took quite a while to prove that this was the optimal value. Here are the times (including generating the FlatZinc file) and the number of failures for each solver:

• Gecode/fz: 1:37 minutes, 6213161 failures
• JaCoP/fz : 4:02 minutes, 6591510 failures
• MiniZinc/fd: 4:30 minutes: 3726 choice points explored (it don't report # of failures)
• SMT : 11:49 minutes (no failures is reported)
• LazyFD : > 1 hour
• Choco/fz : error (the solver didn't like the way I use set variables)
• SICStus/fz: error (ibid)
• ECLiPSe/ic: error (ibid)
• ECLiPSe/fd: error (ibid)
• FzTini: error
• SCIP: error (don't handle sets)

For the presentation of the results, however, the MiniZinc helper program mzn was used since it is the only way to show the output statements. This additional constraint was also added:

/\ z = 14

Also, please note that for getting a "nice" mix of sex and departments I actually did this is two steps: 1) Running with minimize z to obtain the minimum value (as described above), and (in principle) ignored the specific mixing. 2) Before running mzn I changed the labeling somewhat by adding team_sex first in the labeling list (which was not used in the labeling for optimization) since the distribution of sexes tend to be somewhat off. This approach seemed to be easier than looking through many thousands of solutions (with optimal value of z).

One solution

Below is one solution (of many) which seems to have a quite fair mixing: the departments and sexes are mixed very good. Since the number of competitors (18) don't divide evenly with t_size (4), we allow team sizes of either t_size (4) or t_size+1 (5).

z (#violations): 14

Teams: [{1, 7, 8, 13, 17}, {2, 5, 9, 10, 18}, {3, 6, 11, 14}, {4, 12, 15, 16}]

Team Departments:
1 2 2
2 2 1
2 1 1
1 1 2

Team Sexes:
3 2
3 2
3 1
3 1

Team_size: [5, 5, 4, 4]

which_team: [1, 2, 3, 4, 2, 3, 1, 1, 2, 2, 3, 4, 1, 3, 4, 4, 1, 2]
1: hakan	1
2: andersj	2
3: robert	3
4: markus	4
5: johan	2
6: micke	3
7: alex	        1
8: andersh	1
9: jennyk	2
10: kenneth	2
11: sara	3
12: cecilia	4
13: stefan	1
14: jacob	3
15: roger	4
16: henrik	4
17: line	1
18: hanna	2

The teams:
Team 1: hakan(M,it) alex(F,cr1) andersh(M,cr1) stefan(M,cr2) line(F,cr2) 
Team 2: andersj(M,it) johan(M,it) jennyk(F,cr1) kenneth(M,cr1) hanna(F,cr2) 
Team 3: robert(M,it) micke(M,it) sara(F,cr1) jacob(M,cr2) 
Team 4: markus(M,it) cecilia(F,cr1) roger(M,cr2) henrik(M,cr2) 

Managers:
johan(it) belongs to team 2
cecilia(cr1) belongs to team 4
stefan(cr2) belongs to team 1

Some explanations

The mixing of departments ("Team Departments"):

1 2 2  (team 1)
2 2 1  (team 2)
2 1 1  (team 3)
1 1 2  (team 4)

means that the first team consists of 1 person from department 1 (it), and 2 persons from departments 2 (cr1) and 3 (cr2) respectively. And so on.

Team Sexes:
3 2
3 2
3 1
3 1

shows the number of males and females for each team.

It took Gecode/fz 6:20 minutes (and 6006337 failures) to generate all the 467424 optimal solutions (where z = 14).

Different violation measurements: departments

As stated above, the measurements of the violations was one of the hardest part. The solution I selected to be the best for measuring department mixing was the following:

sum(t in 1..num_teams, d1,d2 in 1..num_departments where d1 < d2) (abs(team_departments[t,d1] - team_departments[t,d2]))

One alternative version is to measure the department "mixedness" against some ideal value: the team size divided by the number of departments:

sum(t in 1..num_teams, d in 1..num_departments) (abs(team_departments[t,d] - (team_size[t] div num_departments)))

Using this latter version we get the following as the first solution from mzn, but it don't look as fair as the first variant shown above: both for the mixing of the departments and the sexes could be better. Note: I realize that there are many solutions with z = 12 and there may be some other optimal solution that looks more fair.

z (#violations): 12

Teams: [{1, 7, 8, 9, 13}, {2, 5, 10, 14, 17}, {3, 6, 11, 15}, {4, 12, 16, 18}]

Team Departments:
1 3 1
2 1 2
2 1 1
1 1 2

Team Sexes:
3 2
4 1
3 1
2 2

Here are the times to solve this optimization problem (to prove that z = 12 is the optimal value) for the three fastest solvers above:

• Gecode/fz: 1:30 minutes, 6502528 failures
• JaCoP/fz : 3:45 minutes, 6885666 failures
• MiniZinc/fd: 4:33 minutes, 21 choice points explored

Well, it seems that the time and the number of failures are about the same for Gecode/fz and MiniZinc/fd. For JaCoP/fz it's slightly faster.

Different team sizes

Given the same problem instance, the same constraints and search labeling, how do different team sizes change the time to solve the problem? By changing t_size we see that team size of 4 was the hardest one.

For t_size = 3 it took Gecode/fz 15 seconds (742196 failures) to realize that it is quite easy to pick mixed teams. This seems to be an optimal mixing.

team_departments:
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 1 1 

team_sex:
2 1 
2 1 
2 1 
2 1 
2 1 
2 1 

team_size: 3 3 3 3 3 3

which_team: 1 2 3 4 5 6 1 2 3 4 5 6 1 3 5 6 2 4
z = 6;

For t_size = 5 if took Gecode/fz 2.2 seconds (122300 failures) to get the following optimal solution (z = 6). However, a better mixing of sexes must be sought in another optimal solution.

team_departments:
2 2 2 
2 2 2 
2 2 2 

team_sex:
5 1 
4 2 
3 3 

z = 6;

For t_size = 6 we get the same solution as for 5 but it took Gecode/fz slightly longer, 3.5 seconds (202517 failures).

Final notes

The mixing model presented above can - of course - be used for competitions other than Christmas company competitions.

Also, other mixing requirements could have been taken into considerations, such as:

• different offices: people from different offices (say different cities) should be mixed
• ages: a fair mixing of age groups may be of some point.
• time of employment.
• experience in the target activity of competition: If some are very experienced in the target activity (e.g. former bowling pros), they should be put in different teams. Some kind of handicap system might also be used, e.g. that these pros counts as two persons etc.
• there might also be that some persons cannot stand each other. Depending on the management principle these should either be in the same team (to learn to cooperate) or in different teams (so they don't ruin a team). The opposite case, i.e. where two person are together as couple (or family, etc) may be handled in the same way.

Christmas related

Related to this (Christmas and OR) is the two Secret Santa models I wrote about a year ago: Merry Christmas: Secret Santas Problem and 1 year anniversary and Secret Santa problem II