/usr/share/mozart/doc/fst/node6.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>6 Scheduling a Golf Tournament</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node5.html#fset.examples.crew"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="bib.html#label5">Next >></A></TD></TR></TABLE><DIV id="fset.examples.golf"><H1><A name="fset.examples.golf">6 Scheduling a Golf Tournament</A></H1><P class="margin">Problem Specification</P><P> There are 32 individually playing golfers who play in groups of 4, so-called <EM>foursomes</EM>. 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. </P><P class="margin">Maximal Number of Weeks</P><P> The upper bound for the number of weeks is 10 weeks due to the following argument. There are <IMG alt="{32 \choose 2}= 496" src="latex54.png"> 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 <IMG alt="\lfloor496/48\rfloor=10" src="latex55.png"> 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. </P><P class="margin">Model</P><P> 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 intersection of a foursome with any other foursome of the other weeks has to be either 0 or 1. </P><P class="margin">Distribution Strategy</P><P> The distribution strategy is crucial for this problem.<A href="node6.html#label2"><SUP>1</SUP></A> 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 9 weeks. The approach, coming usually into mind first, to distribute a foursome completely, fails even for smaller instances of the problem. </P><P class="margin">Solver</P><P> The function <CODE>Golf</CODE> returns a solver to find an assignment for <CODE>NbOfFourSomes</CODE> foursomes per week and <CODE>NbOfWeeks</CODE> weeks duration. The number of players is computed from <CODE>NbOfFourSomes</CODE> and stored in <CODE>NbOfPlayers</CODE>. The auxiliary function <CODE>Flatten</CODE> 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><P> The procedure <CODE>DistrPlayers</CODE> 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><P> The variable <CODE>Weeks</CODE> holds <CODE>NbOfWeeks</CODE> weeks. A week is a list of foursomes. A foursome is modeled as a set. All sets are subsets of <IMG alt="\{1,\ldots,\mbox{NbOfPlayers}\}" src="latex56.png"> and have exactly 4 elements. Further, the sets modeling the foursomes of a week form a partition of the set <IMG alt="\{1,\ldots,\mbox{NbOfPlayers}\}" src="latex56.png">. These constraints are imposed by the first <CODE>ForAll</CODE> loop. </P><P> The following nested loops (<CODE>ForAllTail</CODE> and <CODE>ForAll</CODE>) 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 <CODE>Weeks</CODE>, i. e., a list of all foursomes. </P><P></P><BLOCKQUOTE class="linenumbers"><PRE><SPAN class="keyword">declare</SPAN> <BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Golf</SPAN> NbOfWeeks NbOfFourSomes}<BR> NbOfPlayers = 4<SPAN class="keyword">*</SPAN>NbOfFourSomes<BR> <BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Flatten</SPAN> Ls}<BR> {FoldL Ls <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> L R}<BR> <SPAN class="keyword">if</SPAN> R<SPAN class="keyword">==</SPAN>nil <SPAN class="keyword">then</SPAN> L<BR> <SPAN class="keyword">else</SPAN> {Append L R} <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> nil}<BR> <SPAN class="keyword">end</SPAN> <BR> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">DistrPlayers</SPAN> AllWeeks Player Weeks}<BR> <SPAN class="keyword">choice</SPAN> <BR> <SPAN class="keyword">case</SPAN> Weeks<BR> <SPAN class="keyword">of</SPAN> FourSome<SPAN class="keyword">|</SPAN>Rest <SPAN class="keyword">then</SPAN> <BR> <SPAN class="keyword">dis</SPAN> {FS<SPAN class="keyword">.</SPAN>include Player FourSome} <SPAN class="keyword">then</SPAN> <BR> {DistrPlayers AllWeeks Player Rest}<BR> <SPAN class="keyword">[]</SPAN> {FS<SPAN class="keyword">.</SPAN>exclude Player FourSome} <SPAN class="keyword">then</SPAN> <BR> {DistrPlayers AllWeeks Player Rest}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">else</SPAN> <BR> <SPAN class="keyword">if</SPAN> Player <SPAN class="keyword"><</SPAN> NbOfPlayers <SPAN class="keyword">then</SPAN> <BR> {DistrPlayers AllWeeks Player<SPAN class="keyword">+</SPAN>1 AllWeeks}<BR> <SPAN class="keyword">else</SPAN> <SPAN class="keyword">skip</SPAN> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Weeks}<BR> FlattenedWeeks<BR> <SPAN class="keyword">in</SPAN> <BR> Weeks = {MakeList NbOfWeeks}<BR> <BR> {ForAll Weeks<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Week}<BR> Week =<BR> {FS<SPAN class="keyword">.</SPAN>var<SPAN class="keyword">.</SPAN>list<SPAN class="keyword">.</SPAN>upperBound<BR> NbOfFourSomes [1<SPAN class="keyword">#</SPAN>NbOfPlayers]}<BR> {ForAll Week <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> FourSome}<BR> {FS<SPAN class="keyword">.</SPAN>card FourSome 4}<BR> <SPAN class="keyword">end</SPAN>}<BR> {FS<SPAN class="keyword">.</SPAN>partition Week<BR> {FS<SPAN class="keyword">.</SPAN>value<SPAN class="keyword">.</SPAN>make [1<SPAN class="keyword">#</SPAN>NbOfPlayers]}}<BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> {ForAllTail Weeks<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> WTails}<BR> <SPAN class="keyword">case</SPAN> WTails<BR> <SPAN class="keyword">of</SPAN> Week<SPAN class="keyword">|</SPAN>RestWeeks <SPAN class="keyword">then</SPAN> <BR> {ForAll Week<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> FourSome}<BR> {ForAll {Flatten RestWeeks}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> RestFourSome}<BR> {FS<SPAN class="keyword">.</SPAN>cardRange 0 1<BR> {FS<SPAN class="keyword">.</SPAN>intersect<BR> FourSome RestFourSome}}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">end</SPAN>}<BR> <SPAN class="keyword">else</SPAN> <SPAN class="keyword">skip</SPAN> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">end</SPAN>}<BR> <BR> FlattenedWeeks = {Flatten Weeks}<BR> {DistrPlayers FlattenedWeeks 1 FlattenedWeeks}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR> <BR></PRE></BLOCKQUOTE><P> Invoking the solver by <CODE>{ExploreOne {Golf 9 8}}</CODE> produces the following search tree. </P><DIV align="center"><IMG alt="" src="golf_explorer.gif" id="golf_explorer.pic"></DIV><P> </P><P> The search tree has a depth of 200 which makes the problem a good candidate for recomputation. Invoking the search engine with a computation depth of one <A href="node6.html#label3"><SUP>2</SUP></A> requires 64.1 MB of heap memory. On the other hand an recomputation depth of 10 <A href="node6.html#label4"><SUP>3</SUP></A> decreases the required heap memory to 19.3 MB. </P></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node5.html#fset.examples.crew"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="bib.html#label5">Next >></A></TD></TR></TABLE><HR align="left" width="30%"><DIV class="footnote"><A name="label2">1. </A>The distribution strategy was proposed by Stefano Novello from IC-PARC on the newsgroup comp.constraints.</DIV><DIV class="footnote"><A name="label3">2. </A><CODE><SPAN class="keyword">declare</SPAN> S = {Search<SPAN class="keyword">.</SPAN>one<SPAN class="keyword">.</SPAN>depth {Golf 9 8} 1 _}</CODE></DIV><DIV class="footnote"><A name="label4">3. </A><CODE><SPAN class="keyword">declare</SPAN> S = {Search<SPAN class="keyword">.</SPAN>one<SPAN class="keyword">.</SPAN>depth {Golf 9 8} 10 _}</CODE></DIV><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~tmueller/">Tobias Müller</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|