Premium
Applying combinatorial optimization metaheuristics to the golf scramble problem
Author(s) -
Dear R.G.,
Drezner Z.
Publication year - 2000
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2000.tb00203.x
Subject(s) - tabu search , heuristics , tournament , simulated annealing , metaheuristic , mathematical optimization , tournament selection , genetic algorithm , computer science , combinatorial optimization , travelling salesman problem , rank (graph theory) , descent (aeronautics) , operations research , mathematics , combinatorics , engineering , aerospace engineering
One typical golf tournament format is termed a ‘Scramble,’ comprised of four‐person teams. The participants are rank‐ordered into four equally sized ‘flights’ based on integer‐valued handicaps determined by skill level. One participant from each flight is selected to make up a team. Of interest is the assignment of teams in an ‘equitable’ fashion, where equitable is defined as minimizing the difference between the largest and smallest sum of the handicaps. For a typical tournament of 36 teams there are over 10 124 unique assignments. Since in general there are duplicate handicap values, the number of ‘equivalent’ assignments is reduced (but still very large). Various heuristics are explored for efficiently identifying an optimal or near optimal solution. These include descent heuristics, simulated annealing, tabu search, and genetic algorithms. Genetic algorithms outperform other heuristics by taking advantage of the problem structure.