Scheduling a Golf Tournament Blog

Version 2

    {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 Koalog Constraint Solver, a Java library for constraint programming, to write the code. Information about Koalog Constraint Solver (including its JavaDoc) is available at 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 constraintdenotes 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:

     
     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 } 
    

    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 (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;
    

    where the instance variable group will be indexed by weeks (from 1 to n) 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 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 aGolfersProblem 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 list vars will contain all problem variables.

    Each group variable is a set of four golfers:

     
     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]); } } 
    

    The domain 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 toGROUP_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)); } 
    

    We want the golfers to be social. The intersection of two groups should have at most one golfer in common:

    
     
     for (int i=0; i<n-1; 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])); } } } } 
    

    Finally, we define the array of variables to be displayed:

    
     
     setVariables((SetVariable[])vars .toArray(new SetVariable[0])); 
    

    We are done with the modelling; the complete model can be found at www.koalog.com/resources/samples/GolfersProblem.java.

    Solving the Golfers Problem

    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 BacktrackSolver:

     public class GolfersSolver extends BacktrackSolver { SetVariable[][] group; public GolfersSolver(GolfersProblem p) { super(p); this.group = p.group; } public boolean choice() { // to be continued } }
    

    The choice method will be responsible for making choices and thus build a search tree, the nodes of which are calledchoice 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 groupgroup[d][g]. Precisely, isPossibleElementreturns 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.

      
    http://today.java.net/im/a.gif