The Social Golfer Problem

Run LPL Code  ,  PDF Document

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 = {1…n}, the set of golfers i,j ∈ I = {1…nm}, and the set of weeks w ∈ W = {1…k}.

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

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 “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):

   

6. 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)];

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. One is given in Table 1.

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.

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

Further Comments

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. Note this version can only be solved by Hexaly or another non-linear solver.

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.

Answers

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 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;

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