The Social Golfer Problem (golfers)

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

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