Scheduling a Golf Tournament

Problem Specification

There are 32 individually playing golfers who play in groups of 4, so-called foursomes. For every week of the golf tournament new sets of foursomes are to be compiled. The task is to assign foursomes for a given number of weeks such that no player plays with another player in a foursome twice.

Maximal Number of Weeks

The upper bound for the number of weeks is 10 weeks due to the following argument. There are $\left(\vphantom{{32 \atop 2}}\right.$${32 \atop 2}$$\left.\vphantom{{32 \atop 2}}\right)$ = 496 pairing of players. Each foursome takes 6 pairings and every week consists of 8 foursomes, hence, every week occupies 48 pairings. Having only 496 pairings available, at most [496/48] = 10 weeks can be assigned without duplicating foursomes. Unfortunately, only assignments for 9 weeks could be found so far. Fortunately again, this assignment could only be found by solvers using set constraints. Other approaches, using linear integer programming, failed for this problem size.

Viewpoint and Constraints

A foursome is modeled as a set of cardinality 4. A week is a collection of foursomes and all foursomes of a week are pairwise disjoint and their union is the set of all golfers. This leads to a partition constraint. Further, each foursome shares at most one element with any other foursome, since a golfer, of course, may occur in different foursomes but only on his own. Therefore, the cardinality of the intersubsection of a foursome with any other foursome of the other weeks has to be either 0 or 1.

Branching Strategy

The branching strategy is crucial for this problem. A player is taken and assigned to all possible foursomes. Then the next player is taken and assigned and so on. The approach, coming usually into mind first, to branch a foursome completely, fails even for smaller instances of the problem. This branching strategy is called MIN UNKNOWN ELEMENT.

Script

val nbOfWeeks = 9;
val nbOfFourSomes = 8;

fun golf nbOfWeeks nbOfFourSomes space =
  let
      val nbOfPlayers = 4 * nbOfFourSomes
      val tournament = List.tabulate(nbOfWeeks,fn y => 
                       List.tabulate(nbOfFourSomes,fn x =>
                       FS.upperBound(space,#[(1,nbOfPlayers)])))
      val allPlayers = FS.Value.make(space,#[(1,nbOfPlayers)])
      fun flatten([])= []
        | flatten(x::xs)= x@flatten(xs)
      fun weeks([])= ()
        | weeks(x::xs) = (List.app(fn y => 
                            FS.cardRange(space,4,4,y))x;
                          FS.relN(space,Vector.fromList x,
                                      FS.DUNION,allPlayers);
                          List.app(fn y =>
                           List.app(fn z => 
                            List.app(fn v =>
                             let
                                val tmp = FS.setvar space
                             in
                               (FS.relOp(space,v,FS.INTER,y,
                                            FS.SEQ,tmp);
                                FS.cardRange(space,0,1,tmp))
                             end)z   
                              )xs             
                            )x;
                           weeks(xs))
   in 
      weeks(tournament);
      FS.setvarbranch(space,Vector.fromList(flatten tournament),
                           FS.FSB_MIN_UNKNOWN_ELEM,FS.FSB_MIN);
      tournament
   end

The function Golf returns a solver to find an assignment for NbOfFourSomes foursomes per week and NbOfWeeks weeks duration. The number of players is computed from NbOfFourSomes and stored in NbOfPlayers. The auxiliary function flatten is used to flatten a list of lists of variables.

The variable tournament is a list, that contains for every field (week) a list of sets (foursomes).

The procedure weeks imposes the constraint that all sets are subsets of {1,...,nbOfPlayers} and have exactly 4 elements. Further, it imposes that every foursome shares at most one element with any other foursome of other weeks.

The following let - construct can be used to test the solver:

let 
    val (s,r) = valOf(Search.searchOne
                  (golf nbOfWeeks nbOfFourSomes))
in
    List.map(fn z =>
     List.map(fn w => domainToList w)z)
         (List.map(fn x => 
             (List.map(fn y => 
               FS.Reflect.upperBound(s,y))x)
         )r)
end