| Abstract: | The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted
significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint
solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial
configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone.
In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We
show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark
instances from the literature. |
