Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.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: 2012-09-07 11:29:57 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13061 $
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  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  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  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
Cumulatives c2t2("2t2", 2, true, 2)
Event to be scheduled
Describe that event is above a certain limit.
double am(double t[], int n)
Compute arithmetic mean of n elements in t.
Definition: script.cpp:78
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Ass(bool share, Ass &s)
Constructor for cloning s.
Definition: cumulatives.cpp:84
bool start
Whether event has just started Initialize event.
Test for cumulatives constraint
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
Cumulatives c3f_2("3f-2", 3, false,-2)
Cumulatives c3t_2("3t-2", 3, true,-2)
Cumulatives c1f1("1f1", 1, false, 1)
Integer variable array.
Definition: int.hh:741
bool operator()(int val)
Test whether val is above limit
CumulativeAssignment(int n, const Gecode::IntSet &d)
Initialize assignments for n0 variables and values d0.
Computation spaces.
Definition: core.hpp:1362
Greater or equal ( )
Definition: int.hh:908
Cumulatives c3t2("3t2", 3, true, 2)
virtual void operator++(void)
Move to next assignment.
Gecode::IntVarArray x
Store task information.
Definition: cumulatives.cpp:71
Gecode::IntSet d(v, 7)
Cumulatives(const std::string &s, int nt, bool am, int l)
Create and register test.
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Class for generating reasonable assignments.
Definition: cumulatives.cpp:94
virtual bool solution(const Assignment &x) const
Test whether x is solution
Cumulatives c2f3("2f3", 2, false, 3)
Script for generating assignments.
Definition: cumulatives.cpp:68
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
Cumulatives c1f2("1f2", 1, false, 2)
Cumulatives c3t_3("3t-3", 3, true,-3)
Cumulatives c3t3("3t3", 3, true, 3)
int limit
limit Initialize
void cumulatives(Home home, const IntArgs &m, const IntVarArgs &s, const IntArgs &p, const IntVarArgs &e, const IntArgs &u, const IntArgs &c, bool at_most, IntConLevel cl)
Post propagators for the cumulatives constraint.
Cumulatives c1t1("1t1", 1, true, 1)
struct Gecode::Space::@52::@53 p
Data only available during propagation.
virtual Assignment * assignment(void) const
Create first assignment.
Integer sets.
Definition: int.hh:171
Cumulatives c3f2("3f2", 3, false, 2)
Cumulatives c2f1("2f1", 2, false, 1)
Cumulatives c3f_1("3f-1", 3, false,-1)
Cumulatives c2f2("2f2", 2, false, 2)
Passing integer variables.
Definition: int.hh:636
bool operator()(int val)
Test whether val is below limit
Passing integer arguments.
Definition: int.hh:607
virtual int operator[](int i) const
Return value for variable i.
Cumulatives c3t1("3t1", 3, true, 1)
General test support.
Definition: afc.cpp:43
Cumulatives c3f3("3f3", 3, false, 3)
Cumulatives c2t3("2t3", 2, true, 3)
Base class for assignments
Definition: int.hh:63
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Cumulatives c2t1("2t1", 2, true, 1)
Cumulatives c3f_3("3f-3", 3, false,-3)
virtual ~CumulativeAssignment(void)
Destructor.
Cumulatives c1t3("1t3", 1, true, 3)
int limit
limit Initialize
Gecode toplevel namespace
virtual bool operator()(void) const
Test whether all assignments have been iterated
Cumulatives c1t2("1t2", 1, true, 2)
Ass(int n, const Gecode::IntSet &d)
Initialize model for assignments.
Definition: cumulatives.cpp:73
virtual Gecode::Space * copy(bool share)
Create copy during cloning.
Definition: cumulatives.cpp:88
bool operator<(const Event &e) const
Test whether this event is before event e
BrancherHandle branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:43
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Cumulatives c3t_1("3t-1", 3, true,-1)
Cumulatives c3f1("3f1", 3, false, 1)
bool valid(std::vector< Event > e, C comp)
Check whether event e is valid.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Depth-first search engine.
Definition: search.hh:494
Describe that event is below a certain limit.
bool at_most
Whether to use atmost reasoning.
Cumulatives c1f3("1f3", 1, false, 3)