In a local golf club, there are 16 social golfers, each of whom plays golf once a week, and always in groups of 4. Find a schedule of 5 weeks, such that no golfer plays in the same group as any other golfer on more than one occasion, if it exists. If it does not exist, then find a schedule of “maximal socialisation”, that is, as few repeated pairs as possible. (Found at: http://www.csplib.org/Problems/prob010/).
We use three positive numbers to specify a problem instance: The size of each groups is m, the number of groups per week is n, and the number of weeks is k. We denote it the (m-n-k) instance. The instance described above is the (4-4-5) problem, since m = 4, n = 4, and k = 5. Note that the number of golfer is n ⋅ m.
To model the problem, we introduce three sets: the set of a group given as g ∈ G = {1…n}, the set of golfers i,j ∈ I = {1…nm}, and the set of weeks w ∈ W = {1…k}.
A binary variable x_{w,i,g} is introduced which is 1 if golfer i plays in group g in a certain week w, otherwise it is 0.
Each golfer has to play in exactly one group in each week. That is:
Furthermore, each week, each group contains exactly n golfers. Hence,
Finally, the same pair of golfers should not be in the same group more than once. Let (i,j) be a pair of golfers then “x_{w,i,g} ∧ x_{w,j,g} is true (or =1)” for a given group g and a given week w which means that i and j play together in the same group. If this occurs in more then one (w,g) week-group then the condition is violated. That is, it should only occur at most one. A concise formulation is as follows:
Another and equivalent formulation would be (note that, x_{w,i,g}∧x_{w,j,g} returns 0 or 1, depending of whether it is false or true, therefore adding them using a ∑ -operator is perfectly correct):
We only need a feasible solution. This is a very concise formulation!
model golfers "The Social Golfer Problem";
parameter m:=4; n:=4; k:=5;
-- parameter m:=8; n:=4; k:=7;
-- parameter m:=5; n:=3; k:=8;
set w := 1..k "weeks";
i,j := 1..m*n "golfers";
g := 1..m "groups (per week)";
binary variable x{w,i,g};
constraint
A{w,i}: sum{g} x = 1;
B{w,g}: sum{i} x = n;
C{i,j|i<j}: atmost(1){g,w} (x[w,i,g] and x[w,j,g]);
--C{i,j|i<j}: sum{g,w} (x[w,i,g] and x[w,j,g]) = 1;
D{i}: x[1,i,i%m];
E{i}: x[2,i,Ceil(i/n)];
solve;
Write('The group of players is as follows:' n' n');
Write(' %-14s' n',{w}('Week '&w));
Write{g}('Group %s %-14s' n',g,
{w}Strreplace(Format('(%s)',{i|x}(i&',')),',)',')'));
end
To speed up the solution, it is a trivial task to fix all variables for the first and the second week. The constraints are as follows:
In LPL the constraint are as follows:
D{i}: x[1,i,i%m];
E{i}: x[2,i,Ceil(i/n)];
With 16 golfers, we can create (16 4 ) = 1820 different groups of four. For the (4-4-5) problem it is easy to find a solution for Gurobi 6.0. One is given in Table 1.
Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | |
Group 1 | (1,5,9,13) | (1,2,3,4) | (4,7,10,13) | (4,6,9,15) | (4,5,11,14) |
Group 2 | (2,6,10,14) | (5,6,7,8) | (3,8,9,14) | (3,5,10,16) | (3,6,12,13) |
Group 3 | (3,7,11,15) | (9,10,11,12) | (2,5,12,15) | (2,8,11,13) | (2,7,9,16) |
Group 4 | (4,8,12,16) | (13,14,15,16) | (1,6,11,16) | (1,7,12,14) | (1,8,10,15) |
The problem has a long history. “Euler’s officer problem” (1782) is the (6-6-4) instance which is impossible to be solved. Kirkman’s schoolgirl problem (1850), which ask to schedule for a school walk of 15 girls in groups of 3 for 7 days in succession, such that no day the same pair of girl is in the same group. It is the (5-3-7) instance. A solution is given in Table 2. It is more difficult to find a solution.
Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | |
Group 1 | (1,6,11) | (1,2,3) | (3,9,10) | (5,9,11) | (9,12,15) | (2,4,10) | (2,6,9) |
Group 2 | (2,7,12) | (4,5,6) | (2,5,13) | (3,6,14) | (2,11,14) | (1,9,13) | (3,5,12) |
Group 3 | (3,8,13) | (7,8,9) | (4,8,11) | (4,12,13) | (1,5,8) | (3,11,15) | (8,10,14) |
Group 4 | (4,9,14) | (10,11,12) | (1,12,14) | (2,8,15) | (3,4,7) | (5,7,14) | (1,4,15) |
Group 5 | (5,10,15) | (13,14,15) | (6,7,15) | (1,7,10) | (6,10,13) | (6,8,12) | (7,11,13) |
The original social golfer problem instance was first posted to the discussion group sci.op-research in 1998. The problem was stated as follows: “32 golfers play golf once a week, and always in groups of 4. For how many weeks can they do this such that no two golfers play in the same group more than once?”
A solution for 7 weeks is quickly found using the approach above. However, for 8 weeks it is already difficult. A solution for 9 weeks was found soon after the post. It was also clear that no solution for 11 weeks could exist. Today we know that a solution exists for 10 weeks. This is the (8-4-10) instance problem. It is very difficult to solve. The social golfer problem has many interesting applications. A good reference is [1].
The forumation is very elegant and short, but the resulting MIP model is not as efficient as it could be. A somewhat more efficient formulation is found at csplib.org. A different formulation is socialGolfer1. This last version has the advantage that multiple meetings of two players does not make the model infeasible.
Solve the (8-4-7) problem instance then a (8-4-8) problem. What do you observe?
Specify the constraint that certain golfers may not play against each other. Consider, for example, in the (5-3-5) instance golfer 1 refuses to play against 3, and 5.
Model the constraints that (A1) golfer 1 and 7 want to play in the fourth week in the same group, (A2) golfer 3 and 4 do want to be in the same group before week 3, (A3) golfer 1, 2, and 9 should never be together in the same group.
While it is easy to find a solution with 7 weeks, it is much harder to find a solution for 8 weeks.
Add a new parameter M_{i,j} for each pair of golfers which specifies the number of game they play against each other. In our case:
parameter M{i,j} := if(i=1 and (j=3 or j=5),0,1);
Then modify the constraint C to :
C{i,j|i<j}: sum{g,w} (x[w,i,g] and x[w,j,g]) = M;
The three constraints are:
A1: or{g} (x[4,1,g] and x[4,7,g]);
A2: nor{g,w|w<3} (x[w,3,g] and x[w,4,g]);
A3: nor{g,w} (x[w,1,g] and x[w,2,g] and x[w,9,g]);
Make sure that constraints D and E which fix the two first weeks are removed eventually to avoid infeasibilities.
[1] Triska M. Solution Methods for the Social Golfer Problem. Master Thesis, Technische Univerität Wien, 2008.
[2] MatMod. Homepage for Learning Mathematical Modeling : https://matmod.ch.
[3] Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.