<!-- ********************************************************************** -->

<Chapter id="fset.examples.golf"> <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
size.

<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.

<P>
<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 = {Search.one.depth {Golf 9 8} 1 _}>>/ 
requires <Math>64.1</Math> MB of
heap memory. On the other hand an recomputation depth of
<Math>10</Math> 
<Note foot/<<declare S = {Search.one.depth {Golf 9 8} 10 _}>>/ 
decreases the required heap memory to <Math>19.3</Math> MB.

</Chapter>
