# The Social Golfer Problem (golfers)

### Problem

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/).

### Modeling Steps

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.

1. To model the problem, we introduce three sets: the set of a group given as g G = {1n}, the set of golfers i,j I = {1nm}, and the set of weeks w W = {1k}.

2. A binary variable xw,i,g is introduced which is 1 if golfer i plays in group g in a certain week w, otherwise it is 0.

3. Each golfer has to play in exactly one group in each week. That is: 4. Furthermore, each week, each group contains exactly n golfers. Hence, 5. 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 “xw,i,g xw,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, xw,i,gxw,j,g returns 0 or 1, depending of whether it is false or true, therefore adding them using a -operator is perfectly correct): 6. We only need a feasible solution. This is a very concise formulation!

Listing 1: The Complete Model implemented in LPL 
```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)];```

### Solution

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)

Table 1: A Solution to the (4-4-5) Social-Golfer Problem

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)

Table 2: A Solution to the (5-3-7) Social-Golfer Problem

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 .

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.

### Questions

1. Solve the (8-4-7) problem instance then a (8-4-8) problem. What do you observe?

2. 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.

3. 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.

1. While it is easy to find a solution with 7 weeks, it is much harder to find a solution for 8 weeks.

2. Add a new parameter Mi,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;`
3. 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.

### References

   Triska M. Solution Methods for the Social Golfer Problem. Master Thesis, Technische Univerität Wien, 2008.

   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.