The Social Golfer Problem (golfers)

Run LPL Code  ,  PDF Document


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:

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:

    xw,i,g = 1   forall w ∈ W, i ∈ I
  4. Furthermore, each week, each group contains exactly n golfers. Hence,

   x     = n    forall w ∈ W, g ∈ G
  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:

    atmost (1)w,g (xw,i,g ∧ xw,j,g),  forall i < j

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

   (xw,i,g ∧ xw,j,g) ≤ 1,   forall i < j
  6. We only need a feasible solution. This is a very concise formulation!

Listing 1: The Complete Model implemented in LPL [3]
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}; 
    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)]; 
  Write('The group of players is as follows:' n' n'); 
  Write(' %-14s' n',{w}('Week '&w)); 
  Write{g}('Group %s %-14s' n',g, 

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:

x1,i,i%m =  1 ,  ,  x2,i,⌈i∕n⌉ = 1 ,  forall i ∈ I

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)

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 [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 A different formulation is socialGolfer1. This last version has the advantage that multiple meetings of two players does not make the model infeasible.


  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.


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

[2]   MatMod. Homepage for Learning Mathematical Modeling :

[3]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version.