Generated on Sun Aug 26 2012 08:42:51 for Gecode by doxygen 1.8.1.1
cumulatives.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Copyright:
7  * Mikael Lagerkvist, 2005
8  *
9  * Last modified:
10  * $Date: 2011-05-26 00:56:41 +1000 (Thu, 26 May 2011) $ by $Author: schulte $
11  * $Revision: 12022 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/int.hh"
39 
40 #include <gecode/minimodel.hh>
41 #include <gecode/search.hh>
42 
43 #include <vector>
44 #include <algorithm>
45 #include <string>
46 #include <sstream>
47 
48 namespace Test { namespace Int {
49 
51  namespace Cumulatives {
52 
68  class Ass : public Gecode::Space {
69  public:
73  Ass(int n, const Gecode::IntSet& d) : x(*this, n, d) {
74  using namespace Gecode;
75  for (int i = 0; i < n; i += 4) {
76  rel(*this, x[i+0] >= 0);
77  rel(*this, x[i+1] >= 0);
78  rel(*this, x[i+2] >= 0);
79  rel(*this, x[i] + x[i+1] == x[i+2]);
80  branch(*this, x, INT_VAR_NONE, INT_VAL_MIN);
81  }
82  }
84  Ass(bool share, Ass& s) : Gecode::Space(share,s) {
85  x.update(*this, share, s.x);
86  }
88  virtual Gecode::Space* copy(bool share) {
89  return new Ass(share,*this);
90  }
91  };
92 
96  Ass* cur;
98  Ass* nxt;
100  Gecode::DFS<Ass>* e;
101  public:
104  Ass* a = new Ass(n, d);
105  e = new Gecode::DFS<Ass>(a);
106  delete a;
107  nxt = cur = e->next();
108  if (cur != NULL)
109  nxt = e->next();
110  }
112  virtual bool operator()(void) const {
113  return nxt != NULL;
114  }
116  virtual void operator++(void) {
117  delete cur;
118  cur = nxt;
119  if (cur != NULL) nxt = e->next();
120  }
122  virtual int operator[](int i) const {
123  assert((i>=0) && (i<n) && (cur != NULL));
124  return cur->x[i].val();
125  }
127  virtual ~CumulativeAssignment(void) {
128  delete cur; delete nxt; delete e;
129  }
130  };
131 
133  class Event {
134  public:
135  int p, h;
136  bool start;
137 
138  Event(int pos, int height, bool s) : p(pos), h(height), start(s) {}
140  bool operator<(const Event& e) const {
141  return p<e.p;
142  }
143  };
144 
146  class Below {
147  public:
148  int limit;
149 
150  Below(int l) : limit(l) {}
152  bool operator()(int val) {
153  return val <= limit;
154  }
155  };
157  class Above {
158  public:
159  int limit;
160 
161  Above(int l) : limit(l) {}
163  bool operator()(int val) {
164  return val >= limit;
165  }
166  };
167 
169  template<class C>
170  bool valid(std::vector<Event> e, C comp) {
171  std::sort(e.begin(), e.end());
172  unsigned int i = 0;
173  int p = 0;
174  int h = 0;
175  int n = 0;
176  while (i < e.size()) {
177  p = e[i].p;
178  while (i < e.size() && e[i].p == p) {
179  h += e[i].h;
180  n += (e[i].start ? +1 : -1);
181  ++i;
182  }
183  if (n && !comp(h))
184  return false;
185  }
186  return true;
187  }
188 
190  class Cumulatives : public Test {
191  protected:
192  int ntasks;
193  bool at_most;
194  int limit;
195  public:
197  Cumulatives(const std::string& s, int nt, bool am, int l)
198  : Test("Cumulatives::"+s,nt*4,-1,2), ntasks(nt), at_most(am), limit(l) {
199  testsearch = false;
200  }
202  virtual Assignment* assignment(void) const {
203  assert(arity == 4*ntasks);
204  return new CumulativeAssignment(arity, dom);
205  }
207  virtual bool solution(const Assignment& x) const {
208  std::vector<Event> e;
209  for (int i = 0; i < ntasks; ++i) {
210  int p = i*4;
211  // Positive start, duration and end
212  if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false;
213  // Start + Duration == End
214  if (x[p+0] + x[p+1] != x[p+2]) {
215  return false;
216  }
217  }
218  for (int i = 0; i < ntasks; ++i) {
219  int p = i*4;
220  // Up at start, down at end.
221  e.push_back(Event(x[p+0], +x[p+3], true));
222  e.push_back(Event(x[p+2], -x[p+3], false));
223  }
224  if (at_most) {
225  return valid(e, Below(limit));
226  } else {
227  return valid(e, Above(limit));
228  }
229  }
231  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
232  using namespace Gecode;
233  IntArgs m(ntasks), l(1, limit);
234  IntVarArgs s(ntasks), d(ntasks), e(ntasks), h(ntasks);
235  for (int i = 0; i < ntasks; ++i) {
236  int p = i*4;
237  m[i] = 0;
238  s[i] = x[p+0]; rel(home, x[p+0], Gecode::IRT_GQ, 0);
239  d[i] = x[p+1]; rel(home, x[p+1], Gecode::IRT_GQ, 1);
240  e[i] = x[p+2]; rel(home, x[p+2], Gecode::IRT_GQ, 1);
241  h[i] = x[p+3];
242  }
243  cumulatives(home, m, s, d, e, h, l, at_most);
244  }
245  };
246 
247  Cumulatives c1t1("1t1", 1, true, 1);
248  Cumulatives c1f1("1f1", 1, false, 1);
249  Cumulatives c1t2("1t2", 1, true, 2);
250  Cumulatives c1f2("1f2", 1, false, 2);
251  Cumulatives c1t3("1t3", 1, true, 3);
252  Cumulatives c1f3("1f3", 1, false, 3);
253  Cumulatives c2t1("2t1", 2, true, 1);
254  Cumulatives c2f1("2f1", 2, false, 1);
255  Cumulatives c2t2("2t2", 2, true, 2);
256  Cumulatives c2f2("2f2", 2, false, 2);
257  Cumulatives c2t3("2t3", 2, true, 3);
258  Cumulatives c2f3("2f3", 2, false, 3);
259  Cumulatives c3t1("3t1", 3, true, 1);
260  Cumulatives c3f1("3f1", 3, false, 1);
261  Cumulatives c3t2("3t2", 3, true, 2);
262  Cumulatives c3f2("3f2", 3, false, 2);
263  Cumulatives c3t3("3t3", 3, true, 3);
264  Cumulatives c3f3("3f3", 3, false, 3);
265  Cumulatives c3t_1("3t-1", 3, true, -1);
266  Cumulatives c3f_1("3f-1", 3, false, -1);
267  Cumulatives c3t_2("3t-2", 3, true, -2);
268  Cumulatives c3f_2("3f-2", 3, false, -2);
269  Cumulatives c3t_3("3t-3", 3, true, -3);
270  Cumulatives c3f_3("3f-3", 3, false, -3);
272 
273  }
274 }}
275 
276 // STATISTICS: test-int