Skip to content


Subversion checkout URL

You can clone with
Download ZIP
Fetching contributors…
Cannot retrieve contributors at this time
93 lines (75 sloc) 4.34 KB
<!-- ********************************************************************** -->
<Chapter id=""> <Title/Scheduling a Golf Tournament/
<Para><Title/Problem Specification/ There are <Math>32</Math>
individually playing golfers who play in groups of <Math>4</Math>,
so-called <Def/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.
<Para><Title/Maximal Number of Weeks/ The upper bound for the number
of weeks is <Math>10</Math> weeks due to the following argument. There
are <Math>{32 \choose 2}= 496</Math> pairing of players. Each foursome
takes <Math>6</Math> pairings and every week consists of
<Math>8</Math> foursomes, hence, every week occupies <Math>48</Math>
pairings. Having only <Math>496</Math> pairings available, at most
<Math>\lfloor496/48\rfloor=10</Math> weeks can be assigned without
duplicating foursomes. Unfortunately, only assignments for
<Math>9</Math> 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
<Para><Title/Model/ A foursome is modeled as a set of cardinality
<Math>4</Math>. 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 intersection of a foursome with
any other foursome of the other weeks has to be either <Math>0</Math>
or <Math>1</Math>.
<Para><Title/Distribution Strategy/ The distribution strategy is
crucial for this problem.<Note foot/The distribution strategy was
proposed by Stefano Novello from IC-PARC on the newsgroup
comp.constraints./ A player is taken and assigned to all possible
foursomes. Then the next player is taken and assigned and so on. This
player-wise distribution allows to solve instances of that problems up
to <Math>9</Math> weeks. The approach, coming usually into mind first,
to distribute a foursome completely, fails even for smaller instances
of the problem.
<Para><Title/Solver/ 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. Its definition is necessary since the library function of
the same name works only on ground terms.
<P> The procedure <<DistrPlayers>> implements the player-wise
distribution strategy. It tries to create for every player on every
foursome a choice point by simply enumerating all players and iterating
for each player over all foursomes.
<P> The variable <<Weeks>> holds <<NbOfWeeks>> weeks. A week is a list
of foursomes. A foursome is modeled as a set. All sets are subsets of
<Math>\{1,\ldots,\mbox{NbOfPlayers}\}</Math> and have exactly
<Math>4</Math> elements. Further, the sets modeling the foursomes of a
week form a partition of the set
<Math>\{1,\ldots,\mbox{NbOfPlayers}\}</Math>. These constraints are
imposed by the first <<ForAll>> loop.
<P> The following nested loops (<<ForAllTail>> and <<ForAll>>) impose
that every foursome shares at most one element with any other foursome
of other weeks. Finally, the distribution procedure is called with a
flattened copy of <<Weeks>>, &ie;, a list of all foursomes.
<Code.Extern display to="fset_golf.oz" class=linenumbers>
Invoking the solver by <<{ExploreOne {Golf 9 8}}>> produces the
following search tree.
<PICTURE.extern display to="golf_explorer.gif" id="golf_explorer.pic" type=GIF>
<P> The search tree has a depth of <Math>200</Math> which makes the
problem a good candidate for recomputation. Invoking the search engine
with a computation depth of one
<Note foot/<<declare S = { {Golf 9 8} 1 _}>>/
requires <Math>64.1</Math> MB of
heap memory. On the other hand an recomputation depth of
<Note foot/<<declare S = { {Golf 9 8} 10 _}>>/
decreases the required heap memory to <Math>19.3</Math> MB.
Jump to Line
Something went wrong with that request. Please try again.