<bgsound src ="theme8.mid" loop = "-1"> The Social Golfer Problem

# The Social Golfer Problem

The problem is derived from a question posted to sci.op-research in May 1998. It consists of trying to schedule g*s golfers into g groups of s players over w weeks, such that no golfer plays in the same group with any other golfer more than just once. The problem can be looked at as an optimization problem if for two given numbers g and s we ask for the maximum number of weeks the golfers can play together.

An instance to the problem is characterized by a triple w-g-s. The original question therefore is to find a solution to w-8-4, w -> max! The current best known solution is a w=9 week schedule. Obviously, there can be no solution to 11-8-4, because every golfer plays with three new partners each week, which requires him to have 33 fellows in 11 weeks. Therefore, the challenge is to find a solution to 10-8-4 or prove that none exists.

The instance 7-5-3 is equivalent to Thomas Kirkman's Schoolgirl Problem: If once every day for a week, 15 schoolgirls are to walk in five groups of three girls each, is it possible for each girl to be in a group with every other exactly once?

The following table gives the maximum number of weeks for which g*s golfers can play in g groups of s players. If that number is not known yet, we give upper and lower bound information. First, the observation for 11-8-4 can be generalized: w <= (g*s-1)/(s-1). Moreover, if g < s, it is clear a priori that the maximum number of weeks is 1, because it is not possible to seperate s players in the second week. For clarity reasons, we therefore leave out this trivial case in our table.

 Number of Groups Number of Golfers per Group 2 3 4 5 6 7 8 2 3 3 5 4 4 7 4 5 5 9 7 5 6 6 11 [7, 8] 7 [5, 6] 3 7 13 [7, 10] [6, 9] [5, 8] [4, 8] [7, 8] 8 15 [5, 11] [9, 10] [3, 9] [5, 9] [4, 9] 9 9 17 [10, 13] [6, 12] [3, 11] [3, 10] [4, 10] [1, 10] 10 19 [8, 15] [5, 13] [5, 12] [6, 12] [1,11] [1,11]

Obviously, there is a lot of symmetry in the golfers' problem: players can be permuted in groups, groups can be ordered arbitrarily within every week, and the weeks themselves can also be permuted. Finally, since they are indistinguishable, the players can be labeled arbitrarily. An interesting question therefore is, how many unique solutions there are to a given instance w-g-s. Using symmetry breaking by dominance detection (SBDD), we were able to answer this question for some instances. The following table gives the number of unique solutions to some instances of the social golfer problem:

 Number of Weeks Number of Groups - Number of Golfers per Group 2 - 2 3 - 2 3 - 3 4 - 2 4 - 3 4 - 4 5 - 2 5 - 3 5 - 4 5 - 5 2 1 1 1 2 1 1 2 2 1 1 3 1 2 1 8 4 2 23 251 40 2 4 0 1 1 16 3 1 310 13933 20 1 5 1 0 19 0 1 3468 9719 10 1 6 0 13 0 13277 49 0 1 7 6 14241 7 0 8 0 3192 0 9 396 10 0