00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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
00213 if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false;
00214
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
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