CDS2013

A topic in Constraint Programming Research

Steven Butter
sbutter@dundee.ac.uk

This project aims to successfully model and consequently solve the social golfer problem, specifically to find a ten-week schedule of play, using the constraint solver MINION.

The problem is as follows: “There are 32 social golfers, each of whom play golf once a week, and always in groups of four. Come up with a schedule of play for these golfers, to last as many weeks as possible, such that no golfer plays in the same group as any other golfer on more than one occasion.”

The study concludes that a ten-week schedule does exist, but is out with the grasp of conventional constraint programming techniques. It then applies a general model to solve different problems and discuss the efficiency of each.

The efficient modelling of constraint satisfaction problems can have many real-world repercussions in fields as diverse as telecommunications, electronics, group scheduling, transportation, network management and more.

A full specification of the problem, alongwith additional information, can be found on the csplib.org problem page.