Generated on Wed Mar 19 07:29:53 2008 for Gecode by doxygen 1.5.5

golf.cc

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-01-23 09:54:03 +0100 (Wed, 23 Jan 2008) $ by $Author: tack $
00011  *     $Revision: 5950 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include "gecode/set.hh"
00039 #include "examples/support.hh"
00040 
00047 
00048 struct Tournament {
00050   int groups;
00052   int playersInGroup;
00054   int weeks;
00055 };
00057 static const Tournament t[]=
00058   { {8,4,9},
00059     {5,3,7},
00060     {4,3,2}
00061   };
00063 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00065 
00074 class Golf : public Example {
00075 public:
00077   enum {
00078     MODEL_PLAIN,   
00079     MODEL_SYMMETRY 
00080   };
00081   int groups;          
00082   int playersInGroup;  
00083   int weeks;           
00084   int players;         
00085 
00087   SetVarArray groupsS;
00088 
00090   SetVar& group(int w, int g) {
00091     return groupsS[w*groups+g];
00092   }
00093 
00095   Golf(const SizeOptions& opt) :
00096     groups(t[opt.size()].groups),
00097     playersInGroup(t[opt.size()].playersInGroup),
00098     weeks(t[opt.size()].weeks),
00099     players(groups*playersInGroup),
00100     groupsS(this,groups*weeks,IntSet::empty,0,players-1,
00101             playersInGroup,playersInGroup) {
00102 
00103     SetVar allPlayers(this, 0, players-1, 0, players-1);
00104 
00105     // Groups in one week must be disjoint
00106     for (int w=0; w<weeks; w++) {
00107       SetVarArgs p(groups);
00108       for (int g=0; g < groups; g++)
00109                p[g] = group(w,g);
00110 
00111       rel(this,SOT_DUNION,p,allPlayers);
00112     }
00113 
00114     // No two golfers play in the same group more than once
00115     for (int w=0; w<weeks; w++) {
00116       for (int g=0; g<groups; g++) {
00117               SetVar v = group(w,g);
00118               for (int i=(w+1)*groups; i<weeks*groups; i++) {
00119                 SetVar atMostOne(this,IntSet::empty,0,players-1,0,1);
00120                 rel(this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00121               }
00122       }
00123     }
00124 
00125     if (opt.model() == MODEL_SYMMETRY) {
00126 
00127       /*
00128        * Redundant constraints and static symmetry breaking from
00129        * "Solving Kirkman's Schoolgirl Problem in a Few Seconds"
00130        * Nicolas Barnier, Pascal Brisset, Constraints, 10, 7-21, 2005
00131        *
00132        */
00133 
00134       // Redundant constraint:
00135       // in each week, one player plays in only one group
00136       for (int w=0; w < weeks; w++) {
00137          for (int p=0; p < players; p++) {
00138            BoolVarArgs bs(groups);
00139            for (int g=0; g<groups; g++) {
00140             BoolVar b(this,0,1);
00141             dom(this, group(w,g), SRT_SUP, p, b);
00142             bs[g] = b;
00143           }
00144            linear(this, bs, IRT_EQ, 1);
00145          }
00146        }
00147 
00148       // Redundant constraint:
00149       // any two groups has at most one player in common
00150       atmostOne(this, groupsS, playersInGroup);
00151 
00152       // Symmetry breaking: order groups
00153       for (int w=0; w<weeks; w++) {
00154         for (int g=0; g<groups-1; g++) {
00155           IntVar minG1(this, 0, players-1);
00156           IntVar minG2(this, 0, players-1);
00157           SetVar g1 = group(w,g);
00158           SetVar g2 = group(w,g+1);
00159           min(this, g1, minG1);
00160           min(this, g2, minG2);
00161           rel(this, minG1, IRT_LE, minG2);
00162         }
00163       }
00164 
00165       // Symmetry breaking: order weeks
00166       // minElem(group(w,0)\{0}) < minElem(group(w+1,0)\{0})
00167       for (int w=0; w<weeks-1; w++) {
00168         SetVar g1(this, IntSet::empty, 1, players-1);
00169         SetVar g2(this, IntSet::empty, 1, players-1);
00170         rel(this, g1, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w,0));
00171         rel(this, g2, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w+1,0));
00172         IntVar minG1(this, 0, players-1);
00173         IntVar minG2(this, 0, players-1);
00174         min(this, g1, minG1);
00175         min(this, g2, minG2);
00176         rel(this, minG1, IRT_LE, minG2);
00177       }
00178 
00179       // Initialize the dual variables:
00180       // groupsSInv[w*players+p] is player p's group in week w
00181       IntVarArray groupsSInv(this, weeks*players, 0, groups-1);
00182       for (int w=0; w<weeks; w++) {
00183         for (int p=0; p<players; p++) {
00184           SetVar thisPlayer(this, p,p, 0, players-1);
00185           SetVarArgs thisWeek(groups);
00186           for (int g=0; g<groups; g++)
00187             thisWeek[g] = group(w,g);
00188           selectSet(this, thisWeek, groupsSInv[w*players+p], thisPlayer);
00189         }
00190       }
00191 
00192       // Symmetry breaking: order players
00193       // For all p<groups : groupsSInv[w*players+p] <= p
00194       for (int w=0; w<weeks; w++) {
00195         for (int p=0; p<groups; p++) {
00196           rel(this, groupsSInv[w*players+p], IRT_LQ, p);
00197         }
00198       }
00199 
00200     }
00201 
00202     branch(this, groupsS, SET_VAR_MIN_UNKNOWN_ELEM, SET_VAL_MIN);
00203   }
00204 
00206   virtual void
00207   print(std::ostream& os) {
00208     os << "Tournament plan" << std::endl;
00209 
00210     for (int w=0; w<weeks; w++) {
00211       os << "Week " << w << ": " << std::endl << "    ";
00212       for (int g=0; g<groups; g++) {
00213         if (group(w,g).assigned()) {          
00214           bool first = true;
00215           os << "(";
00216           for (SetVarGlbValues glb(group(w,g)); glb(); ++glb) {
00217             if (first) first = false; else os << " ";
00218             os << glb.val();
00219           }
00220           os << ")";          
00221         } else {
00222           os << "(" << group(w,g) << ")";
00223         }
00224         if (g < groups-1) os << " ";
00225         if (g > 0 && g % 4 == 0) os << std::endl << "    ";
00226       }
00227       os << std::endl;
00228     }
00229   }
00230 
00232   Golf(bool share, Golf& s) : Example(share,s),
00233       groups(s.groups), playersInGroup(s.playersInGroup),
00234       weeks(s.weeks), players(s.players) {
00235     groupsS.update(this, share, s.groupsS);
00236   }
00238   virtual Space*
00239   copy(bool share) {
00240     return new Golf(share,*this);
00241   }
00242 
00244   virtual void
00245   getVars(Gecode::Reflection::VarMap& vm, bool registerOnly) {
00246     vm.putArray(this, groupsS, "groupsS", registerOnly);
00247   }
00248 };
00249 
00253 int
00254 main(int argc, char* argv[]) {
00255   SizeOptions opt("Golf");
00256   opt.model(Golf::MODEL_PLAIN);
00257   opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00258   opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00259   opt.solutions(1);
00260   opt.parse(argc,argv);
00261   if (opt.size() >= n_examples) {
00262     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00263               << std::endl;
00264     return 1;
00265   }
00266   Example::run<Golf,DFS,SizeOptions>(opt);
00267   return 0;
00268 }
00269 
00270 // STATISTICS: example-any
00271