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 #include "test/int.hh"
00035
00036 #include <gecode/minimodel.hh>
00037 #include <gecode/search.hh>
00038
00039 #include <vector>
00040 #include <algorithm>
00041 #include <string>
00042 #include <sstream>
00043
00044 namespace Test { namespace Int {
00045
00047 namespace Cumulatives {
00048
00064 class Ass : public Gecode::Space {
00065 public:
00067 Gecode::IntVarArray x;
00069 Ass(int n, const Gecode::IntSet& d) : x(*this, n, d) {
00070 using namespace Gecode;
00071 for (int i = 0; i < n; i += 4) {
00072 rel(*this, x[i+0] >= 0);
00073 rel(*this, x[i+1] >= 0);
00074 rel(*this, x[i+2] >= 0);
00075 rel(*this, x[i] + x[i+1] == x[i+2]);
00076 branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
00077 }
00078 }
00080 Ass(Ass& s) : Gecode::Space(s) {
00081 x.update(*this, s.x);
00082 }
00084 virtual Gecode::Space* copy(void) {
00085 return new Ass(*this);
00086 }
00087 };
00088
00090 class CumulativeAssignment : public Assignment {
00092 Ass* cur;
00094 Ass* nxt;
00096 Gecode::DFS<Ass>* e;
00097 public:
00099 CumulativeAssignment(int n, const Gecode::IntSet& d) : Assignment(n,d) {
00100 Ass* a = new Ass(n, d);
00101 e = new Gecode::DFS<Ass>(a);
00102 delete a;
00103 nxt = cur = e->next();
00104 if (cur != NULL)
00105 nxt = e->next();
00106 }
00108 virtual bool operator()(void) const {
00109 return nxt != NULL;
00110 }
00112 virtual void operator++(void) {
00113 delete cur;
00114 cur = nxt;
00115 if (cur != NULL) nxt = e->next();
00116 }
00118 virtual int operator[](int i) const {
00119 assert((i>=0) && (i<n) && (cur != NULL));
00120 return cur->x[i].val();
00121 }
00123 virtual ~CumulativeAssignment(void) {
00124 delete cur; delete nxt; delete e;
00125 }
00126 };
00127
00129 class Event {
00130 public:
00131 int p, h;
00132 bool start;
00133
00134 Event(int pos, int height, bool s) : p(pos), h(height), start(s) {}
00136 bool operator<(const Event& e) const {
00137 return p<e.p;
00138 }
00139 };
00140
00142 class Below {
00143 public:
00144 int limit;
00145
00146 Below(int l) : limit(l) {}
00148 bool operator()(int val) {
00149 return val <= limit;
00150 }
00151 };
00153 class Above {
00154 public:
00155 int limit;
00156
00157 Above(int l) : limit(l) {}
00159 bool operator()(int val) {
00160 return val >= limit;
00161 }
00162 };
00163
00165 template<class C>
00166 bool valid(std::vector<Event> e, C comp) {
00167 std::sort(e.begin(), e.end());
00168 unsigned int i = 0;
00169 int p = 0;
00170 int h = 0;
00171 int n = 0;
00172 while (i < e.size()) {
00173 p = e[i].p;
00174 while (i < e.size() && e[i].p == p) {
00175 h += e[i].h;
00176 n += (e[i].start ? +1 : -1);
00177 ++i;
00178 }
00179 if (n && !comp(h))
00180 return false;
00181 }
00182 return true;
00183 }
00184
00186 class Cumulatives : public Test {
00187 protected:
00188 int ntasks;
00189 bool at_most;
00190 int limit;
00191 public:
00193 Cumulatives(const std::string& s, int nt, bool am, int l)
00194 : Test("Cumulatives::"+s,nt*4,-1,2), ntasks(nt), at_most(am), limit(l) {
00195 testsearch = false;
00196 }
00198 virtual Assignment* assignment(void) const {
00199 assert(arity == 4*ntasks);
00200 return new CumulativeAssignment(arity, dom);
00201 }
00203 virtual bool solution(const Assignment& x) const {
00204 std::vector<Event> e;
00205 for (int i = 0; i < ntasks; ++i) {
00206 int p = i*4;
00207
00208 if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false;
00209
00210 if (x[p+0] + x[p+1] != x[p+2]) {
00211 return false;
00212 }
00213 }
00214 for (int i = 0; i < ntasks; ++i) {
00215 int p = i*4;
00216
00217 e.push_back(Event(x[p+0], +x[p+3], true));
00218 e.push_back(Event(x[p+2], -x[p+3], false));
00219 }
00220 if (at_most) {
00221 return valid(e, Below(limit));
00222 } else {
00223 return valid(e, Above(limit));
00224 }
00225 }
00227 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00228 using namespace Gecode;
00229 IntArgs m(ntasks), l(1, limit);
00230 IntVarArgs s(ntasks), d(ntasks), e(ntasks), h(ntasks);
00231 for (int i = 0; i < ntasks; ++i) {
00232 int p = i*4;
00233 m[i] = 0;
00234 s[i] = x[p+0]; rel(home, x[p+0], Gecode::IRT_GQ, 0);
00235 d[i] = x[p+1]; rel(home, x[p+1], Gecode::IRT_GQ, 1);
00236 e[i] = x[p+2]; rel(home, x[p+2], Gecode::IRT_GQ, 1);
00237 h[i] = x[p+3];
00238 }
00239 cumulatives(home, m, s, d, e, h, l, at_most);
00240 }
00241 };
00242
00243 Cumulatives c1t1("1t1", 1, true, 1);
00244 Cumulatives c1f1("1f1", 1, false, 1);
00245 Cumulatives c1t2("1t2", 1, true, 2);
00246 Cumulatives c1f2("1f2", 1, false, 2);
00247 Cumulatives c1t3("1t3", 1, true, 3);
00248 Cumulatives c1f3("1f3", 1, false, 3);
00249 Cumulatives c2t1("2t1", 2, true, 1);
00250 Cumulatives c2f1("2f1", 2, false, 1);
00251 Cumulatives c2t2("2t2", 2, true, 2);
00252 Cumulatives c2f2("2f2", 2, false, 2);
00253 Cumulatives c2t3("2t3", 2, true, 3);
00254 Cumulatives c2f3("2f3", 2, false, 3);
00255 Cumulatives c3t1("3t1", 3, true, 1);
00256 Cumulatives c3f1("3f1", 3, false, 1);
00257 Cumulatives c3t2("3t2", 3, true, 2);
00258 Cumulatives c3f2("3f2", 3, false, 2);
00259 Cumulatives c3t3("3t3", 3, true, 3);
00260 Cumulatives c3f3("3f3", 3, false, 3);
00261 Cumulatives c3t_1("3t-1", 3, true, -1);
00262 Cumulatives c3f_1("3f-1", 3, false, -1);
00263 Cumulatives c3t_2("3t-2", 3, true, -2);
00264 Cumulatives c3f_2("3f-2", 3, false, -2);
00265 Cumulatives c3t_3("3t-3", 3, true, -3);
00266 Cumulatives c3f_3("3f-3", 3, false, -3);
00268
00269 }
00270 }}
00271
00272