Skip to main content

Scheduling a Golf Tournament

January 19, 2005

{cs.r.title}









Contents
Constraint Programming
Modeling the Golfers Problem
Solving the Golfers Problem
Results

On May 1998, a post on the sci.op-research 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
round-robin
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 nine-week schedule. Constructing a ten-week schedule or proving that none exists remains an open problem!

To solve the nine-week 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 to n) and then by groups
(from 1 to GROUP_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 set-based 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 to GOLFERS_NB).
The list vars will contain all
problem variables.

Each group variable is a set of four golfers:

[prettify] for (int i=0; i&lt;n; i++) {    for (int j=0; j&lt;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&lt;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&lt;n-1; i++) {
  for (int l=i+1; l&lt;n; l++) {
    for (int j=0; j&lt;GROUP_NB; j++) {
      for (int k=0; k&lt;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 golfer j can be added to the group group[d][g].
Precisely, isPossibleElement returns true if the element is contained
in the UB of the domain, but not in the LB. The method chooseMinByAdding 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 nine-week 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=" " />
Yan Georget has a degree from Paris-based Ecole Polytechnique and a Ph.D. in computer science from INRIA.