Generated on Sat Feb 12 2011 17:40:45 for Gecode by doxygen 1.7.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-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $
00011  *     $Revision: 11473 $
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 
00045 class GolfOptions : public Options {
00046 protected:
00047   Driver::IntOption _w; //< Number of weeks
00048   Driver::IntOption _g; //< Number of groups
00049   Driver::IntOption _s; //< Number of players per group
00050 public:
00052   GolfOptions(void)
00053     : Options("Golf"),
00054       _w("-w","number of weeks",9),
00055       _g("-g","number of groups",8),
00056       _s("-s","number of players per group",4) {
00057     add(_w);
00058     add(_g);
00059     add(_s);
00060   }
00062   int w(void) const { return _w.value(); }
00064   int g(void) const { return _g.value(); }
00066   int s(void) const { return _s.value(); }
00067 };
00068 
00080 class Golf : public Script {
00081 public:
00083   enum {
00084     MODEL_PLAIN,   
00085     MODEL_SYMMETRY 
00086   };
00087   int g; 
00088   int s; 
00089   int w; 
00090 
00092   SetVarArray groups;
00093 
00095   Golf(const GolfOptions& opt) : g(opt.g()), s(opt.s()), w(opt.w()),
00096     groups(*this,g*w,IntSet::empty,0,g*s-1,s,s) {
00097     Matrix<SetVarArray> schedule(groups,g,w);
00098 
00099     // Groups in one week must be disjoint
00100     SetVar allPlayers(*this, 0,g*s-1, 0,g*s-1);
00101     for (int i=0; i<w; i++)
00102       rel(*this, setdunion(schedule.row(i)) == allPlayers);
00103 
00104     // No two golfers play in the same group more than once
00105     for (int i=0; i<groups.size()-1; i++)
00106       for (int j=i+1; j<groups.size(); j++)
00107         rel(*this, cardinality(groups[i] & groups[j]) <= 1);
00108 
00109     if (opt.model() == MODEL_SYMMETRY) {
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 j=0; j<w; j++) {
00121          for (int p=0; p < g*s; p++) {
00122            BoolVarArgs b(g);
00123            for (int i=0; i<g; i++)
00124              b[i] = expr(*this, (singleton(p) <= schedule(i,j)));
00125            linear(*this, b, IRT_EQ, 1);
00126          }
00127        }
00128 
00129       // Symmetry breaking: order groups
00130       for (int j=0; j<w; j++) {
00131         for (int i=0; i<g-1; i++) {
00132           rel(*this, min(schedule(i,j)) < min(schedule(i+1,j)));
00133         }
00134       }
00135 
00136       // Symmetry breaking: order weeks
00137       // minElem(group(w,0)\{0}) < minElem(group(w+1,0)\{0})
00138       for (int i=0; i<w-1; i++) {
00139         rel(*this, min(schedule(0,i)-IntSet(0,0)) <
00140                    min(schedule(0,i+1)-IntSet(0,0)));
00141         
00142       }
00143 
00144       // Initialize the dual variables:
00145       // gInv(i,p) is player p's group in week i
00146       Matrix<IntVarArgs> gInv(IntVarArgs(*this, w*g*s, 0, g-1),w,g*s);
00147      
00148       for (int i=0; i<w; i++)
00149         for (int p=0; p<g*s; p++) {
00150           SetVar player(*this, p,p, 0, g*s-1);
00151           element(*this, schedule.row(i), gInv(i,p),player);
00152         }
00153       
00154       // Symmetry breaking: order players
00155       for (int i=0; i<w; i++)
00156         for (int p=0; p<g; p++)
00157           rel(*this, gInv(i,p), IRT_LQ, p);
00158     }
00159 
00160     branch(*this, groups, SET_VAR_MIN_MIN, SET_VAL_MIN_INC);
00161   }
00162 
00164   virtual void
00165   print(std::ostream& os) const {
00166     os << "Tournament plan" << std::endl;
00167     Matrix<SetVarArray> schedule(groups,g,w);
00168     for (int j=0; j<w; j++) {
00169       os << "Week " << j << ": " << std::endl << "    ";
00170       os << schedule.row(j) << std::endl;
00171     }
00172   }
00173 
00175   Golf(bool share, Golf& s) : Script(share,s), g(s.g), s(s.s), w(s.w) {
00176     groups.update(*this, share, s.groups);
00177   }
00179   virtual Space*
00180   copy(bool share) {
00181     return new Golf(share,*this);
00182   }
00183 };
00184 
00188 int
00189 main(int argc, char* argv[]) {
00190   GolfOptions opt;
00191   opt.model(Golf::MODEL_PLAIN);
00192   opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00193   opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00194   opt.solutions(1);
00195   opt.parse(argc,argv);
00196   Script::run<Golf,DFS,GolfOptions>(opt);
00197   return 0;
00198 }
00199 
00200 // STATISTICS: example-any