Solution methods for the social golfer problem

Abstract

Das "social golfer problem" (SGP) ist ein kombinatorisches Optimierungsproblem. Die Aufgabe besteht darin, p*g Golfer in g Gruppen zu je p Spielern für w Wochen so einzuteilen, dass sich je zwei Spieler höchstens einmal in derselben Gruppe treffen. Eine SGP-Instanz wird durch das Tripel g-p-w bezeichnet. Das ursprüngliche Problem besteht darin, das maximale w zu bestimmen sodass die Instanz 8-4-w gelöst werden kann.<br />Das SGP ist ein interessantes Puzzle und Benchmark-Problem, und tritt zudem in zahlreichen praktischen Anwendungen wie Kodierung, Verschlüsselung und Überdeckungs-Problemen auf.<br />In dieser Diplomarbeit werden vorhandene Ansätze zum Lösen von SGP-Instanzen präsentiert und verbessert. Wir zeigen, dass das zum SGP gehörige "completion problem" NP-vollständig ist, und dass die Instanz 10-10-11 nicht gelöst werden kann. Wir korrigieren mehrere Fehler in einem vorhandenen SAT Encoding für das SGP, und schlagen eine Modifikation vor, die zu einer erheblichen Senkung der Laufzeit führt, wenn man SGP-Instanzen mit gängigen SAT-Solvern löst. Wir entwickeln einen neuen und frei verfügbaren Constraint Solver über Finite Domains, um mit einer vorhandenen Constraint-basierten Formulierung für das SGP zu experimentieren. Mit dem Solver lösen wir das ursprüngliche SGP für 9 Wochen, was dem derzeit besten mit kommerziellen Solvern erzielten Ergebnis für diese Instanz entspricht. Wir stellen eine neue Greedy-Heuristik und eine neue "greedy randomised adaptive search procedure" (GRASP) für das SGP vor. Dies ist die erste metaheuristische Methode, mit der das ursprüngliche SGP optimal gelöst werden kann. Auch auf anderen Instanzen erzielen wir mit unserer Methode Ergebnisse, die existierenden Ansätzen gleichkommen oder sie übertreffen.<br />

The social golfer problem (SGP) is a combinatorial optimisation problem. The task is to schedule p*g golfers in g groups of p players for w weeks such that no two golfers play in the same group more than once. An instance of the SGP is denoted by the triple g-p-w. The original problem asks for the maximal w such that the instance 8-4-w can be solved.<br />In addition to being an interesting puzzle and hard benchmark problem, the SGP and closely related problems arise in many practical applications such as encoding, encryption and covering tasks.<br />In this thesis, we present and improve upon existing approaches towards solving SGP instances. We prove that the completion problem corresponding to the SGP is NP-complete, and that the instance 10-10-11 cannot be solved. We correct several mistakes of an existing SAT encoding for the SGP, and propose a modification that yields considerably improved running times when solving SGP instances with common SAT solvers. We develop a new and freely available finite domain constraint solver, which lets us experiment with an existing constraint-based formulation of the SGP. We use our solver to solve the original problem for 9 weeks, thus matching the best current results of commercial constraint solvers for this instance. We present a new greedy heuristic and a new greedy randomised adaptive search procedure (GRASP) for the SGP. Our method is the first metaheuristic technique that can solve the original problem optimally, and is also highly competitive with existing approaches on many other instances.<br />