Generated on Mon May 10 06:46:29 2010 for Gecode by doxygen 1.6.3

golf.cpp

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: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
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/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/set.hh>
00041 
00042 using namespace Gecode;
00043 
00050 
00051 struct Tournament {
00053   int groups;
00055   int playersInGroup;
00057   int weeks;
00058 };
00060 static const Tournament t[]=
00061   { {8,4,9},
00062     {5,3,7},
00063     {4,3,2}
00064   };
00066 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00068 
00077 class Golf : public Script {
00078 public:
00080   enum {
00081     MODEL_PLAIN,   
00082     MODEL_SYMMETRY 
00083   };
00084   enum {
00085     PROP_PLAIN,    
00086     PROP_DECOMPOSE 
00087   };
00088   int groups;          
00089   int playersInGroup;  
00090   int weeks;           
00091   int players;         
00092 
00094   SetVarArray groupsS;
00095 
00097   SetVar& group(int w, int g) {
00098     return groupsS[w*groups+g];
00099   }
00101   const SetVar& group(int w, int g) const {
00102     return groupsS[w*groups+g];
00103   }
00104 
00106   Golf(const SizeOptions& opt) :
00107     groups(t[opt.size()].groups),
00108     playersInGroup(t[opt.size()].playersInGroup),
00109     weeks(t[opt.size()].weeks),
00110     players(groups*playersInGroup),
00111     groupsS(*this,groups*weeks,IntSet::empty,0,players-1,
00112             playersInGroup,playersInGroup) {
00113 
00114     SetVar allPlayers(*this, 0, players-1, 0, players-1);
00115 
00116     // Groups in one week must be disjoint
00117     for (int w=0; w<weeks; w++) {
00118       SetVarArgs p(groups);
00119       for (int g=0; g < groups; g++)
00120                p[g] = group(w,g);
00121 
00122       rel(*this,SOT_DUNION,p,allPlayers);
00123     }
00124 
00125     // No two golfers play in the same group more than once
00126     for (int w=0; w<weeks; w++) {
00127       for (int g=0; g<groups; g++) {
00128         SetVar v = group(w,g);
00129         SetVar vcompl;
00130         if (opt.propagation() == PROP_DECOMPOSE) {
00131           vcompl = SetVar(*this,IntSet::empty,
00132                           Set::Limits::min,Set::Limits::max);
00133           rel(*this, v, SRT_CMPL, vcompl);
00134         }
00135         for (int i=(w+1)*groups; i<weeks*groups; i++) {
00136           if (opt.propagation() == PROP_PLAIN) {
00137             SetVar atMostOne(*this,IntSet::empty,0,players-1,0,1);
00138             rel(*this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00139           } else {
00140             SetVar atMostOneC(*this,IntSet::empty,
00141                               Set::Limits::min,
00142                               Set::Limits::max,
00143                               Set::Limits::card-1,
00144                               Set::Limits::card);
00145             SetVar groupsSiC(*this,IntSet::empty,
00146                              Set::Limits::min,Set::Limits::max);
00147             rel(*this, groupsS[i], SRT_CMPL, groupsSiC);
00148             rel(*this, vcompl, SOT_UNION, groupsSiC, SRT_EQ, atMostOneC);
00149           }
00150         }
00151       }
00152     }
00153 
00154     if (opt.model() == MODEL_SYMMETRY) {
00155 
00156       /*
00157        * Redundant constraints and static symmetry breaking from
00158        * "Solving Kirkman's Schoolgirl Problem in a Few Seconds"
00159        * Nicolas Barnier, Pascal Brisset, Constraints, 10, 7-21, 2005
00160        *
00161        */
00162 
00163       // Redundant constraint:
00164       // in each week, one player plays in only one group
00165       for (int w=0; w < weeks; w++) {
00166          for (int p=0; p < players; p++) {
00167            BoolVarArgs bs(groups);
00168            for (int g=0; g<groups; g++) {
00169             BoolVar b(*this,0,1);
00170             dom(*this, group(w,g), SRT_SUP, p, b);
00171             bs[g] = b;
00172           }
00173            linear(*this, bs, IRT_EQ, 1);
00174          }
00175        }
00176 
00177       // Redundant constraint:
00178       // any two groups has at most one player in common
00179       atmostOne(*this, groupsS, playersInGroup);
00180 
00181       // Symmetry breaking: order groups
00182       for (int w=0; w<weeks; w++) {
00183         for (int g=0; g<groups-1; g++) {
00184           IntVar minG1(*this, 0, players-1);
00185           IntVar minG2(*this, 0, players-1);
00186           SetVar g1 = group(w,g);
00187           SetVar g2 = group(w,g+1);
00188           min(*this, g1, minG1);
00189           min(*this, g2, minG2);
00190           rel(*this, minG1, IRT_LE, minG2);
00191         }
00192       }
00193 
00194       // Symmetry breaking: order weeks
00195       // minElem(group(w,0)\{0}) < minElem(group(w+1,0)\{0})
00196       for (int w=0; w<weeks-1; w++) {
00197         SetVar g1(*this, IntSet::empty, 1, players-1);
00198         SetVar g2(*this, IntSet::empty, 1, players-1);
00199         rel(*this, g1, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w,0));
00200         rel(*this, g2, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w+1,0));
00201         IntVar minG1(*this, 0, players-1);
00202         IntVar minG2(*this, 0, players-1);
00203         min(*this, g1, minG1);
00204         min(*this, g2, minG2);
00205         rel(*this, minG1, IRT_LE, minG2);
00206       }
00207 
00208       // Initialize the dual variables:
00209       // groupsSInv[w*players+p] is player p's group in week w
00210       IntVarArray groupsSInv(*this, weeks*players, 0, groups-1);
00211       for (int w=0; w<weeks; w++) {
00212         for (int p=0; p<players; p++) {
00213           SetVar thisPlayer(*this, p,p, 0, players-1);
00214           SetVarArgs thisWeek(groups);
00215           for (int g=0; g<groups; g++)
00216             thisWeek[g] = group(w,g);
00217           element(*this, thisWeek, groupsSInv[w*players+p], thisPlayer);
00218         }
00219       }
00220 
00221       // Symmetry breaking: order players
00222       // For all p<groups : groupsSInv[w*players+p] <= p
00223       for (int w=0; w<weeks; w++)
00224         for (int p=0; p<groups; p++)
00225           rel(*this, groupsSInv[w*players+p], IRT_LQ, p);
00226     }
00227 
00228     branch(*this, groupsS, SET_VAR_MIN_MIN, SET_VAL_MIN_INC);
00229   }
00230 
00232   virtual void
00233   print(std::ostream& os) const {
00234     os << "Tournament plan" << std::endl;
00235 
00236     for (int w=0; w<weeks; w++) {
00237       os << "Week " << w << ": " << std::endl << "    ";
00238       for (int g=0; g<groups; g++) {
00239         if (group(w,g).assigned()) {
00240           bool first = true;
00241           os << "(";
00242           for (SetVarGlbValues glb(group(w,g)); glb(); ++glb) {
00243             if (first) first = false; else os << " ";
00244             os << glb.val();
00245           }
00246           os << ")";
00247         } else {
00248           os << "(" << group(w,g) << ")";
00249         }
00250         if (g < groups-1) os << " ";
00251         if (g > 0 && g % 4 == 0) os << std::endl << "    ";
00252       }
00253       os << std::endl;
00254     }
00255   }
00256 
00258   Golf(bool share, Golf& s) : Script(share,s),
00259       groups(s.groups), playersInGroup(s.playersInGroup),
00260       weeks(s.weeks), players(s.players) {
00261     groupsS.update(*this, share, s.groupsS);
00262   }
00264   virtual Space*
00265   copy(bool share) {
00266     return new Golf(share,*this);
00267   }
00268 };
00269 
00273 int
00274 main(int argc, char* argv[]) {
00275   SizeOptions opt("Golf");
00276   opt.model(Golf::MODEL_PLAIN);
00277   opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00278   opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00279   opt.propagation(Golf::PROP_PLAIN);
00280   opt.propagation(Golf::PROP_PLAIN, "plain", "intersection constraints");
00281   opt.propagation(Golf::PROP_DECOMPOSE, "decompose",
00282                   "union and complement constraints");
00283   opt.solutions(1);
00284   opt.parse(argc,argv);
00285   if (opt.size() >= n_examples) {
00286     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00287               << std::endl;
00288     return 1;
00289   }
00290   Script::run<Golf,DFS,SizeOptions>(opt);
00291   return 0;
00292 }
00293 
00294 // STATISTICS: example-any
00295