Constraint Programming




Social Golfer Problem Solutions


1. The first approach I take to modelling the social golfer problem is to keep the schedule into a matrix that maps each pair of (Week, Golfer) to a group (1..8).  This approach is easy enough to implement and all the constraints are straightforward.  The main disadvantage is that, giving a number to each week, golfer and group, the modelling does not allow for easy recognition of simmetric sollutions.

To break some of the symmetry, the groups in each week will be ordered in the order of the smallest index player.  For example, group {3, 6, 24, 30} will always have a smaller index than group {4, 5, 7, 8}.

Here is a 6 week schedule and the BProlog solution.

2. The second approach is to keep each week's schedule as a 32 x 32 binary matrice in which:
S[i,j] = 1 <=> player i and j have been in the same group in the respective week.

This modelling has been described by John Fabricius in A Constraint Programming Approach to the Social Golfer Problem.

The advantage of this implementation is that the group symmetry is broken without any effort.  Groups are not identified by numbers as in 1), but by the players that belong to it.  The downside to this modeling is that it is more difficult to formulate the constraints for two golfers to meet at most once.

The solution implementing this model is implemented into two files: social_golfer2.pl and utils.pl




Hosted by www.Geocities.ws

1