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