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