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-05-11 10:12:13 +0200 (Tue, 11 May 2010) $ by $Author: tack $ 00011 * $Revision: 10933 $ 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