Generated on Thu Jul 6 07:06:40 2006 for Gecode by doxygen 1.4.7

golf.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *     Guido Tack, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2006-04-25 17:01:15 +0200 (Tue, 25 Apr 2006) $ by $Author: tack $
00012  *     $Revision: 3215 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 #include "gecode/set.hh"
00025 #include "examples/support.hh"
00026 
00033 
00034 struct Tournament {
00036   int groups;
00038   int playersInGroup;
00040   int weeks;
00041 };
00043 static const Tournament t[]=
00044   { {8,4,9},
00045     {5,3,7}
00046   };
00048 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00050 
00059 class Golf : public Example {
00060 public:
00061   int groups;
00062   int playersInGroup;
00063   int weeks;
00064   int players;
00065 
00066   SetVarArray groupsS;
00067   IntVarArray groupsSInv;
00068 
00069   SetVar& group(int w, int g) {
00070     return groupsS[w*groups+g];
00071   }
00072   IntVar& groupInv(int w, int p) {
00073     return groupsSInv[w*players+p];
00074   }
00075 
00076   Golf(const Options& o) :
00077     groups(t[o.size].groups),
00078     playersInGroup(t[o.size].playersInGroup),
00079     weeks(t[o.size].weeks),
00080     players(groups*playersInGroup),
00081     groupsS(this,groups*weeks,IntSet::empty,0,players-1,
00082             playersInGroup,playersInGroup),
00083     groupsSInv(this, weeks*players, 0, groups-1) {
00084 
00085     SetVar allPlayers(this, 0, players-1, 0, players-1);
00086 
00087     // Groups in one week must be disjoint
00088     for (int w=0; w<weeks; w++) {
00089       SetVarArgs p(groups);
00090       for (int g=0; g < groups; g++)
00091         p[g] = group(w,g);
00092       
00093       rel(this,SOT_DUNION,p,allPlayers);
00094     }
00095 
00096     // No two golfers play in the same group more than once
00097     for (int w=0; w<weeks; w++) {
00098       for (int g=0; g<groups; g++) {
00099         SetVar v = group(w,g);
00100         for (int i=(w+1)*groups; i<weeks*groups; i++) {
00101           SetVar atMostOne(this,IntSet::empty,0,players-1,0,1);
00102           rel(this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00103         }
00104       }
00105     }
00106 
00107     if (!o.naive) {
00108 
00109       //      atmostOne(this, groupsS, playersInGroup);
00110       
00111       /*
00112        * Redundant constraints and static symmetry breaking from
00113        * "Solving Kirkman's Schoolgirl Problem in a Few Seconds"
00114        * Nicolas Barnier, Pascal Brisset, Constraints, 10, 7-21, 2005
00115        *
00116        */
00117 
00118       // Redundant constraint:
00119       // in each week, one player plays in only one group
00120       for (int w=0; w < weeks; w++) {
00121         for (int p=0; p < players; p++) {
00122           BoolVarArgs bs(groups);
00123           for (int g=0; g<groups; g++) {
00124             BoolVar b(this,0,1);
00125             dom(this, group(w,g), SRT_SUP, p, b);
00126             bs[g] = b;
00127           }
00128           linear(this, bs, IRT_EQ, 1);
00129         }
00130        }
00131 
00132       // Redundant constraint:
00133       // any two groups has at most one player in common
00134       atmostOne(this, groupsS, playersInGroup);
00135       
00136       // Symmetry breaking: order groups
00137       for (int w=0; w<weeks; w++) {
00138         for (int g=0; g<groups-1; g++) {
00139           IntVar minG1(this, 0, players-1);
00140           IntVar minG2(this, 0, players-1);
00141           SetVar g1 = group(w,g);
00142           SetVar g2 = group(w,g+1);
00143           min(this, g1, minG1);
00144           min(this, g2, minG2);
00145           rel(this, minG1, IRT_LE, minG2);
00146         }
00147       }
00148 
00149       // Symmetry breaking: order weeks
00150       // minElem(group(w,0)\{0}) < minElem(group(w+1,0)\{0})
00151       for (int w=0; w<weeks-1; w++) {
00152         SetVar g1(this, IntSet::empty, 1, players-1);
00153         SetVar g2(this, IntSet::empty, 1, players-1);
00154         SetVar zero1(this, IntSet::empty,0,0);
00155         SetVar zero2(this, IntSet::empty,0,0);
00156         rel(this, g1, SOT_DUNION, zero1, SRT_EQ, group(w,0));
00157         rel(this, g2, SOT_DUNION, zero2, SRT_EQ, group(w+1,0));
00158         IntVar minG1(this, 0, players-1);
00159         IntVar minG2(this, 0, players-1);
00160         min(this, g1, minG1);
00161         min(this, g2, minG2);
00162         rel(this, minG1, IRT_LE, minG2);
00163       }
00164       
00165       // Initialize the dual variables:
00166       // groupInv(w,p) is player p's group in week w
00167       for (int w=0; w<weeks; w++) {
00168         for (int p=0; p<players; p++) {
00169           SetVar thisPlayer(this, p,p, 0, players-1);
00170           SetVarArgs thisWeek(groups);
00171           for (int g=0; g<groups; g++)
00172             thisWeek[g] = group(w,g);
00173           selectSet(this, thisWeek, groupInv(w,p), thisPlayer);
00174         }
00175       }
00176 
00177       // Symmetry breaking: order players
00178       // For all p<groups : groupInv(w,p) <= p
00179       for (int w=0; w<weeks; w++) {
00180         for (int p=0; p<groups; p++) {
00181           rel(this, groupInv(w,p), IRT_LQ, p);
00182         }
00183       }
00184 
00185     }
00186 
00187     branch(this, groupsS, SETBVAR_MIN_UNKNOWN_ELEM, SETBVAL_MIN);
00188   }
00189 
00190   Golf(bool share, Golf& s) : Example(share,s),
00191       groups(s.groups), playersInGroup(s.playersInGroup),
00192       weeks(s.weeks), players(s.players) {
00193     groupsS.update(this, share, s.groupsS);
00194   }
00195 
00196   virtual Space*
00197   copy(bool share) {
00198     return new Golf(share,*this);
00199   }
00200 
00201   virtual void
00202   print(void) {
00203 
00204     std::cout << "Tournament plan" << std::endl;
00205 
00206     for (int w=0; w<weeks; w++) {
00207       std::cout << "Week " << w << ": " << std::endl << "    ";
00208       for (int g=0; g<groups; g++) {
00209         SetVarGlbValues glb(group(w,g));
00210         std::cout << "(" << glb.val();
00211         ++glb;
00212         while(glb()) {
00213           std::cout << " " << glb.val();
00214           ++glb;
00215         }
00216         std::cout << ")";
00217         if (g < groups-1) std::cout << " ";
00218         if (g > 0 && g % 4 == 0) std::cout << std::endl << "    ";
00219       }
00220       std::cout << std::endl;
00221     }
00222 
00223   }
00224 };
00225 
00226 int
00227 main(int argc, char** argv) {
00228   Options o("Golf");
00229   o.parse(argc,argv);
00230   o.solutions  = 1;
00231   if (o.size >= n_examples) {
00232     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00233               << std::endl;
00234     return 1;
00235   }
00236   Example::run<Golf,DFS>(o);
00237   return 0;
00238 }
00239 
00240 // STATISTICS: example-any
00241