The Social Golfer Problem (SGP) is a combinatorial optimisation
problem. The task is to schedule g × p golfers
in g groups of p players
for w weeks such that no two golfers play in the same
group more than once. An instance of the SGP is
denoted by the triple g-p-w. The original problem asks
for the maximal w such that the
instance 8-4-w can be solved.
After the original SGP instance was first posted to the discussion
group sci.op-research in 1998, a solution for
9 weeks was soon found. It was also clear that no solution
for 11 weeks exists.
Proof: Suppose w ≥ 11, and observe the
schedule of an arbitrary but fixed player α. Each week,
α plays in a group with 3 distinct other players.
To play for 11 weeks, α would have to partner 3 × 11
> 31 other players.
Whether there exists a solution for 10 weeks was an open
question for several years,
until Alejandro
Aguado constructed an explicit solution for the 8-4-10
instance in 2004 (aguado.txt):
Solution methods for the SGP are the subject of my Master's
thesis. See mst.pdf for more information.
The thesis explains the following approaches for solving the SGP:
