Scheduling a Golf Tournament


On May 1998, a post on the sci.opresearch newsgroup
posed the following problem: suppose you have 32 golfers who organize
each week into groups of four. The original post said that the goal is
to select the foursomes so that each person only golfs with the same
person once. How many weeks before all of the options are exhausted?
This problem has since become a famous combinatorial problem and is
usually called the social golfer problem. It is a
generalization of a
roundrobin
tournament. It helps to bound the problem. You can easily show that there is
no solution for a number of weeks strictly greater than ten. This
follows from the fact that each player plays with three other players
each week, and since there is a total of 31 other players, this means
a player runs out of opponents after (31)/3 weeks. In this article, we
will see how to construct a nineweek schedule. Constructing a tenweek schedule or proving that none exists remains an open problem!
To solve the nineweek schedule problem, we will use
href="http://www.koalog.com/php/jcs.php">Koalog Constraint Solver,
a Java library for constraint programming, to write the code.
Information about Koalog Constraint Solver (including its JavaDoc) is
available at
href="http://www.koalog.com/php/jcs.php">www.koalog.com/php/jcs.php. All
of the techniques presented in this article do not depend on the choice
of the solver, but could be implemented using many commercial or
open source solvers.
Constraint Programming
Constraint programming (CP) is a technique for solving
combinatorial problems such as the social golfer problem.
It consists of modelling the problem using mathematical relations or
constraints (precisely, the term constraint denotes the implementation
of the mathematical relation).
Hence, a constraint satisfaction problem (CSP) is defined by:
 A set of variables.
 A set of domains (possible values) for the variables.
 A set of constraints/relations on the variables.
One has to define a strategy for enumerating the
different solutions. CP differs from naive enumeration methods by the
fact that constraints contain powerful filtering algorithms (usually
inspired by operational research techniques) that will
drastically reduce the search space by dynamically reducing the
domains of the variables during the enumeration.
Modeling the Golfers Problem
Let's first create a problem object that will be the placeholder for the
problem modelization. Using Koalog Constraint Solver, this can be done by
subclassing a BaseProblem
:
[prettify]
public class GolfersProblem extends BaseProblem {
public static final int GROUP_NB = 8;
public static final int GROUP_CARD = 4;
public static final int GOLFERS_NB =
GROUP_NB*GROUP_CARD;
// the forthcoming model will come here
}
</pre>
<p>We have defined some constants to make the code more readable, but
also because the problem can be generalized to various group numbers
and sizes. In the following, the number of weeks (<code>n
) will
be a parameter of the problem.
An important step in constraint programming is defining the problem variables. In our case, we want to find, for each week, the set of golfers playing in each group. Fortunately, Koalog Constraint Solver comes with set variables (in addition to Boolean and integer variables). Thus, it is possible to write:
SetVariable[ ][ ] group; [/prettify]where the instance variable
group
will be indexed by weeks
(from 1 ton
) and then by groups
(from 1 toGROUP_NB
).Note that it would also be possible to model the problem using integers
(defining, each week, for each golfer, the number of its group) or Booleans
(deciding, each week, whether a golfer belongs to a given group or not).
But a setbased representation is much more compact and powerful, since it
eliminates most of the problem symmetries.We can now model our problem and define a
GolfersProblem
constructor:public GolfersProblem(int n) {
super();
group = new SetVariable[n][GROUP_NB];
Collection golfers = new ArrayList();
for (int i=1; i<=GOLFERS_NB; i++) {
golfers.add(new Integer(i));
}
List vars = new ArrayList();
// to be continued
}The collection
golfers
is the collection of all golfers
(identified here by a number from 1 toGOLFERS_NB
).
The listvars
will contain all
problem variables.Each group variable is a set of four golfers:
[prettify] for (int i=0; i<n; i++) { for (int j=0; j<GROUP_NB; j++) { group[i][j] = new SetVariable(new SetDomain(Collections .EMPTY_SET, golfers)); add(new ConstantCard(GROUP_CARD, group[i][j])); vars.add(group[i][j]); } } </pre> <p>The domain <code>new SetDomain(Collections.EMPTY_SET, golfers)
states that the group is a set containing at least the empty set and at most the set of all golfers (previously defined). More generally, set domains are defined by two sets:
 A set of values that will be contained in the set; this set increases with time and it is the lower bound (LB) of the domain.
 A set of values containing the set, this set decreases with time and it is the upper bound (UB) of the domain.
For example, the set domain {1, 2, 3} denotes the sets containing at least 1 and at most 1, 2, and 3: these are {1}, {1,2}, {1,3}, {1, 2, 3}. A set domain is instantiated when the upper bound is equal to the lower bound.
The constraint ConstantCard
states that the cardinality of the group
should be constant (here equal to GROUP_CARD
).
Each week the groups of golfers form a partition of the set of all golfers:
for (int i=0; i<n; i++) { add(new Partition(group[i], golfers)); } </pre> <p>We want the golfers to be social. The intersection of two groups should have at most one golfer in common:</p> <pre> <code> for (int i=0; i<n1; i++) { for (int l=i+1; l<n; l++) { for (int j=0; j<GROUP_NB; j++) { for (int k=0; k<GROUP_NB; k++) { add(new IntersectionMaxSize(1, group[i][j], group[l][k])); } } } } </pre> <p>Finally, we define the array of variables to be displayed:</p> <pre> <code> setVariables((SetVariable[])vars .toArray(new SetVariable[0])); </pre> <p>We are done with the modelling; the complete model can be found at <a href="http://www.koalog.com/resources/samples/GolfersProblem.java">www.koalog.com/resources/samples/GolfersProblem.java</a>.</p> <h2 id="solving">Solving the Golfers Problem</h2> <p>Let's first create a solver object that will be the placeholder for the strategy. Using Koalog Constraint Solver, this can be done by subclassing a <code>BacktrackSolver
:public class GolfersSolver extends BacktrackSolver { SetVariable[][] group; public GolfersSolver(GolfersProblem p) { super(p); this.group = p.group; } public boolean choice() { // to be continued } } [/prettify]The
choice
method will be responsible for making choices and thus build
a search tree, the nodes of which are called choice points. This method
will be called successively until all of the group variables are instantiated.We add the golfers by numbers to the groups:
for (int i=1;
i<=GolfersProblem.GOLFERS_NB;
i++) {
Integer j = new Integer(i);
for (int d=0; d<group.length; d++) {
for (int g=0;
g<GolfersProblem.GROUP_NB;
g++) {
if (((SetDomain) group[d][g].getDomain())
.isPossibleElement(j)) {
choicePoints.push();
group[d][g]
.chooseMinByAdding(choicePoints,
constraintScheduler,
j);
return true;
}
}
}
}
return false;If a golfer can be added to a group, a new node (choice point) is created
in the search tree and the method returns true. When no more golfers can be added, the method returns false.The test
((SetDomain) group[d][g].getDomain()).isPossibleElement(j)
returns true if golferj
can be added to the groupgroup[d][g]
.
Precisely,isPossibleElement
returns true if the element is contained
in the UB of the domain, but not in the LB. The methodchooseMinByAdding
adds a new element to the set (increasing
its LB).We are done with the strategy; the complete solver can be found at
www.koalog.com/resources/samples/GolfersSolver.java.Results
This strategy performs very well. Koalog Constraint Solver is able to find a
solution to the nineweek problem in 440ms (on a 1600Mhz PC with J2SE
1.4):
 Week 1: {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15,
16}, {17, 18, 19, 20}, {21, 22, 23, 24}, {25, 26, 27, 28}, {29, 30, 31, 32}  Week 2: {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}, {4, 8, 12, 16}, {17,
21, 25, 29}, {18, 22, 26, 30}, {19, 23, 27, 31}, {20, 24, 28, 32}  Week 3: {1, 6, 11, 16}, {2, 5, 12, 15}, {3, 8, 9, 14}, {4, 7, 10, 13}, {17,
22, 27, 32}, {18, 21, 28, 31}, {19, 24, 25, 30}, {20, 23, 26, 29}  Week 4: {1, 7, 17, 23}, {2, 8, 18, 24}, {3, 5, 19, 21}, {4, 6, 20, 22},
{9, 15, 25, 31}, {10, 16, 26, 32}, {11, 13, 27, 29}, {12, 14, 28, 30}  Week 5: {1, 8, 19, 22}, {2, 7, 20, 21}, {3, 6, 17, 24}, {4, 5, 18, 23},
{9, 16, 27, 30}, {10, 15, 28, 29}, {11, 14, 25, 32}, {12, 13, 26, 31}  Week 6: {1, 10, 18, 25}, {2, 9, 17, 26}, {3, 12, 20, 27}, {4, 11, 19, 28},
{5, 14, 22, 29}, {6, 13, 21, 30}, {7, 16, 24, 31}, {8, 15, 23, 32}  Week 7: {1, 12, 21, 32}, {2, 11, 22, 31}, {3, 10, 23, 30}, {4, 9, 24, 29},
{5, 16, 17, 28}, {6, 15, 18, 27}, {7, 14, 19, 26}, {8, 13, 20, 25}  Week 8: {1, 14, 20, 31}, {2, 13, 19, 32}, {3, 16, 18, 29}, {4, 15, 17, 30},
{5, 10, 24, 27}, {6, 9, 23, 28}, {7, 12, 22, 25}, {8, 11, 21, 26}  Week 9: {1, 15, 24, 26}, {2, 16, 23, 25}, {3, 13, 22, 28}, {4, 14, 21, 27},
{5, 11, 20, 30}, {6, 12, 19, 29}, {7, 9, 18, 32}, {8, 10, 17, 31}
Precisely, only 32 nodes are explored in the search tree. This is to compare
with the huge size of the search tree (32!^9).
It is also interesting to notice that local search methods perform poorly on
this problem.
Of course, this model can be generalized to arbitrary numbers of groups and
golfers, and it is also possible to add side constraints such as Golfer 1
and Golfer 2 would like to golf together on week 1.
width="1" height="1" border="0" alt=" " /> 
 Login or register to post comments
 Printerfriendly version
 4159 reads