# The Social Golfer Problem

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:
• design-theoretic techniques
• SAT formulations
• constraint-based approaches
• metaheuristic methods.
Other contributions:
• the completion problem of the SGP is NP-complete in general
• corrections to an existing SAT encoding
• new greedy heuristic and new GRASP scheme
• solve 8-4-10 with a metaheuristic.

Some of these results are published in:
An Effective Greedy Heuristic for the Social Golfer Problem (pdf)
Markus Triska and Nysret Musliu
Annals of Operations Research Vol. 194(1) (2012), pp. 413-425
An Improved SAT Formulation for the Social Golfer Problem (pdf)
Markus Triska and Nysret Musliu
Annals of Operations Research Vol. 194(1) (2012), pp. 427-438
Here is a Prolog program that lets you express instances of the SGP as SAT instances in DIMACS format: satgolf.pl

You can use Scryer Prolog to generate a SAT formula for any SGP instance g-p-w, for example using:
```    ?- golf(5,3,2).
```