cumulatives.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Copyright: 00007 * Mikael Lagerkvist, 2005 00008 * 00009 * Last modified: 00010 * $Date: 2010-05-08 12:56:03 +0200 (Sat, 08 May 2010) $ by $Author: tack $ 00011 * $Revision: 10906 $ 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 "test/int.hh" 00039 00040 #include <gecode/minimodel.hh> 00041 #include <gecode/search.hh> 00042 #include <gecode/scheduling.hh> 00043 00044 #include <vector> 00045 #include <algorithm> 00046 #include <string> 00047 #include <sstream> 00048 00049 namespace Test { namespace Int { 00050 00052 namespace Cumulatives { 00053 00069 class Ass : public Gecode::Space { 00070 public: 00072 Gecode::IntVarArray x; 00074 Ass(int n, const Gecode::IntSet& d) : x(*this, n, d) { 00075 using namespace Gecode; 00076 for (int i = 0; i < n; i += 4) { 00077 rel(*this, x[i+0] >= 0); 00078 rel(*this, x[i+1] >= 0); 00079 rel(*this, x[i+2] >= 0); 00080 rel(*this, x[i] + x[i+1] == x[i+2]); 00081 branch(*this, x, INT_VAR_NONE, INT_VAL_MIN); 00082 } 00083 } 00085 Ass(bool share, Ass& s) : Gecode::Space(share,s) { 00086 x.update(*this, share, s.x); 00087 } 00089 virtual Gecode::Space* copy(bool share) { 00090 return new Ass(share,*this); 00091 } 00092 }; 00093 00095 class CumulativeAssignment : public Assignment { 00097 Ass* cur; 00099 Ass* nxt; 00101 Gecode::DFS<Ass>* e; 00102 public: 00104 CumulativeAssignment(int n, const Gecode::IntSet& d) : Assignment(n,d) { 00105 Ass* a = new Ass(n, d); 00106 e = new Gecode::DFS<Ass>(a); 00107 delete a; 00108 nxt = cur = e->next(); 00109 if (cur != NULL) 00110 nxt = e->next(); 00111 } 00113 virtual bool operator()(void) const { 00114 return nxt != NULL; 00115 } 00117 virtual void operator++(void) { 00118 delete cur; 00119 cur = nxt; 00120 if (cur != NULL) nxt = e->next(); 00121 } 00123 virtual int operator[](int i) const { 00124 assert((i>=0) && (i<n) && (cur != NULL)); 00125 return cur->x[i].val(); 00126 } 00128 virtual ~CumulativeAssignment(void) { 00129 delete cur; delete nxt; delete e; 00130 } 00131 }; 00132 00134 class Event { 00135 public: 00136 int p, h; 00137 bool start; 00138 00139 Event(int pos, int height, bool s) : p(pos), h(height), start(s) {} 00141 bool operator<(const Event& e) const { 00142 return p<e.p; 00143 } 00144 }; 00145 00147 class Below { 00148 public: 00149 int limit; 00150 00151 Below(int l) : limit(l) {} 00153 bool operator()(int val) { 00154 return val <= limit; 00155 } 00156 }; 00158 class Above { 00159 public: 00160 int limit; 00161 00162 Above(int l) : limit(l) {} 00164 bool operator()(int val) { 00165 return val >= limit; 00166 } 00167 }; 00168 00170 template<class C> 00171 bool valid(std::vector<Event> e, C comp) { 00172 std::sort(e.begin(), e.end()); 00173 unsigned int i = 0; 00174 int p = 0; 00175 int h = 0; 00176 int n = 0; 00177 while (i < e.size()) { 00178 p = e[i].p; 00179 while (i < e.size() && e[i].p == p) { 00180 h += e[i].h; 00181 n += (e[i].start ? +1 : -1); 00182 ++i; 00183 } 00184 if (n && !comp(h)) 00185 return false; 00186 } 00187 return true; 00188 } 00189 00191 class Cumulatives : public Test { 00192 protected: 00193 int ntasks; 00194 bool at_most; 00195 int limit; 00196 public: 00198 Cumulatives(const std::string& s, int nt, bool am, int l) 00199 : Test("Scheduling::Cumulatives::"+s,nt*4,-1,2), ntasks(nt), at_most(am), limit(l) { 00200 testsearch = false; 00201 } 00203 virtual Assignment* assignment(void) const { 00204 assert(arity == 4*ntasks); 00205 return new CumulativeAssignment(arity, dom); 00206 } 00208 virtual bool solution(const Assignment& x) const { 00209 std::vector<Event> e; 00210 for (int i = 0; i < ntasks; ++i) { 00211 int p = i*4; 00212 // Positive start, duration and end 00213 if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false; 00214 // Start + Duration == End 00215 if (x[p+0] + x[p+1] != x[p+2]) { 00216 return false; 00217 } 00218 } 00219 for (int i = 0; i < ntasks; ++i) { 00220 int p = i*4; 00221 // Up at start, down at end. 00222 e.push_back(Event(x[p+0], +x[p+3], true)); 00223 e.push_back(Event(x[p+2], -x[p+3], false)); 00224 } 00225 if (at_most) { 00226 return valid(e, Below(limit)); 00227 } else { 00228 return valid(e, Above(limit)); 00229 } 00230 } 00232 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00233 using namespace Gecode; 00234 IntArgs m(ntasks), l(1, limit); 00235 IntVarArgs s(ntasks), d(ntasks), e(ntasks), h(ntasks); 00236 for (int i = 0; i < ntasks; ++i) { 00237 int p = i*4; 00238 m[i] = 0; 00239 s[i] = x[p+0]; rel(home, x[p+0], Gecode::IRT_GQ, 0); 00240 d[i] = x[p+1]; rel(home, x[p+1], Gecode::IRT_GQ, 1); 00241 e[i] = x[p+2]; rel(home, x[p+2], Gecode::IRT_GQ, 1); 00242 h[i] = x[p+3]; 00243 } 00244 cumulatives(home, m, s, d, e, h, l, at_most); 00245 } 00246 }; 00247 00248 Cumulatives c1t1("1t1", 1, true, 1); 00249 Cumulatives c1f1("1f1", 1, false, 1); 00250 Cumulatives c1t2("1t2", 1, true, 2); 00251 Cumulatives c1f2("1f2", 1, false, 2); 00252 Cumulatives c1t3("1t3", 1, true, 3); 00253 Cumulatives c1f3("1f3", 1, false, 3); 00254 Cumulatives c2t1("2t1", 2, true, 1); 00255 Cumulatives c2f1("2f1", 2, false, 1); 00256 Cumulatives c2t2("2t2", 2, true, 2); 00257 Cumulatives c2f2("2f2", 2, false, 2); 00258 Cumulatives c2t3("2t3", 2, true, 3); 00259 Cumulatives c2f3("2f3", 2, false, 3); 00260 Cumulatives c3t1("3t1", 3, true, 1); 00261 Cumulatives c3f1("3f1", 3, false, 1); 00262 Cumulatives c3t2("3t2", 3, true, 2); 00263 Cumulatives c3f2("3f2", 3, false, 2); 00264 Cumulatives c3t3("3t3", 3, true, 3); 00265 Cumulatives c3f3("3f3", 3, false, 3); 00266 Cumulatives c3t_1("3t-1", 3, true, -1); 00267 Cumulatives c3f_1("3f-1", 3, false, -1); 00268 Cumulatives c3t_2("3t-2", 3, true, -2); 00269 Cumulatives c3f_2("3f-2", 3, false, -2); 00270 Cumulatives c3t_3("3t-3", 3, true, -3); 00271 Cumulatives c3f_3("3f-3", 3, false, -3); 00273 00274 } 00275 }} 00276 00277 // STATISTICS: test-int