An effective greedy heuristic for the Social Golfer Problem

An effective greedy heuristic for the Social Golfer Problem

0.00 Avg rating0 Votes
Article ID: iaor2012882
Volume: 194
Issue: 1
Start Page Number: 413
End Page Number: 425
Publication Date: Apr 2012
Journal: Annals of Operations Research
Authors: ,
Keywords: combinatorial optimization, heuristics: local search
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.

Reviews

Required fields are marked *. Your email address will not be published.