Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include "test/int.hh"
35 
36 #include <gecode/minimodel.hh>
37 #include <gecode/search.hh>
38 
39 #include <vector>
40 #include <algorithm>
41 #include <string>
42 #include <sstream>
43 
44 namespace Test { namespace Int {
45 
47  namespace Cumulatives {
48 
64  class Ass : public Gecode::Space {
65  public:
69  Ass(int n, const Gecode::IntSet& d) : x(*this, n, d) {
70  using namespace Gecode;
71  for (int i = 0; i < n; i += 4) {
72  rel(*this, x[i+0] >= 0);
73  rel(*this, x[i+1] >= 0);
74  rel(*this, x[i+2] >= 0);
75  rel(*this, x[i] + x[i+1] == x[i+2]);
76  branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
77  }
78  }
80  Ass(Ass& s) : Gecode::Space(s) {
81  x.update(*this, s.x);
82  }
84  virtual Gecode::Space* copy(void) {
85  return new Ass(*this);
86  }
87  };
88 
92  Ass* cur;
94  Ass* nxt;
97  public:
100  Ass* a = new Ass(n, d);
101  e = new Gecode::DFS<Ass>(a);
102  delete a;
103  nxt = cur = e->next();
104  if (cur != NULL)
105  nxt = e->next();
106  }
108  virtual bool operator()(void) const {
109  return nxt != NULL;
110  }
112  virtual void operator++(void) {
113  delete cur;
114  cur = nxt;
115  if (cur != NULL) nxt = e->next();
116  }
118  virtual int operator[](int i) const {
119  assert((i>=0) && (i<n) && (cur != NULL));
120  return cur->x[i].val();
121  }
123  virtual ~CumulativeAssignment(void) {
124  delete cur; delete nxt; delete e;
125  }
126  };
127 
129  class Event {
130  public:
131  int p, h;
132  bool start;
133  Event(int pos, int height, bool s) : p(pos), h(height), start(s) {}
136  bool operator<(const Event& e) const {
137  return p<e.p;
138  }
139  };
140 
142  class Below {
143  public:
144  int limit;
145  Below(int l) : limit(l) {}
148  bool operator()(int val) {
149  return val <= limit;
150  }
151  };
153  class Above {
154  public:
155  int limit;
156  Above(int l) : limit(l) {}
159  bool operator()(int val) {
160  return val >= limit;
161  }
162  };
163 
165  template<class C>
166  bool valid(std::vector<Event> e, C comp) {
167  std::sort(e.begin(), e.end());
168  unsigned int i = 0;
169  int p = 0;
170  int h = 0;
171  int n = 0;
172  while (i < e.size()) {
173  p = e[i].p;
174  while (i < e.size() && e[i].p == p) {
175  h += e[i].h;
176  n += (e[i].start ? +1 : -1);
177  ++i;
178  }
179  if (n && !comp(h))
180  return false;
181  }
182  return true;
183  }
184 
186  class Cumulatives : public Test {
187  protected:
188  int ntasks;
189  bool at_most;
190  int limit;
191  public:
193  Cumulatives(const std::string& s, int nt, bool am, int l)
194  : Test("Cumulatives::"+s,nt*4,-1,2), ntasks(nt), at_most(am), limit(l) {
195  testsearch = false;
196  }
198  virtual Assignment* assignment(void) const {
199  assert(arity == 4*ntasks);
200  return new CumulativeAssignment(arity, dom);
201  }
203  virtual bool solution(const Assignment& x) const {
204  std::vector<Event> e;
205  for (int i = 0; i < ntasks; ++i) {
206  int p = i*4;
207  // Positive start, duration and end
208  if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false;
209  // Start + Duration == End
210  if (x[p+0] + x[p+1] != x[p+2]) {
211  return false;
212  }
213  }
214  for (int i = 0; i < ntasks; ++i) {
215  int p = i*4;
216  // Up at start, down at end.
217  e.push_back(Event(x[p+0], +x[p+3], true));
218  e.push_back(Event(x[p+2], -x[p+3], false));
219  }
220  if (at_most) {
221  return valid(e, Below(limit));
222  } else {
223  return valid(e, Above(limit));
224  }
225  }
227  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
228  using namespace Gecode;
229  IntArgs m(ntasks), l({limit});
230  IntVarArgs s(ntasks), d(ntasks), e(ntasks), h(ntasks);
231  for (int i = 0; i < ntasks; ++i) {
232  int p = i*4;
233  m[i] = 0;
234  s[i] = x[p+0]; rel(home, x[p+0], Gecode::IRT_GQ, 0);
235  d[i] = x[p+1]; rel(home, x[p+1], Gecode::IRT_GQ, 1);
236  e[i] = x[p+2]; rel(home, x[p+2], Gecode::IRT_GQ, 1);
237  h[i] = x[p+3];
238  }
239  cumulatives(home, m, s, d, e, h, l, at_most);
240  }
241  };
242 
243  Cumulatives c1t1("1t1", 1, true, 1);
244  Cumulatives c1f1("1f1", 1, false, 1);
245  Cumulatives c1t2("1t2", 1, true, 2);
246  Cumulatives c1f2("1f2", 1, false, 2);
247  Cumulatives c1t3("1t3", 1, true, 3);
248  Cumulatives c1f3("1f3", 1, false, 3);
249  Cumulatives c2t1("2t1", 2, true, 1);
250  Cumulatives c2f1("2f1", 2, false, 1);
251  Cumulatives c2t2("2t2", 2, true, 2);
252  Cumulatives c2f2("2f2", 2, false, 2);
253  Cumulatives c2t3("2t3", 2, true, 3);
254  Cumulatives c2f3("2f3", 2, false, 3);
255  Cumulatives c3t1("3t1", 3, true, 1);
256  Cumulatives c3f1("3f1", 3, false, 1);
257  Cumulatives c3t2("3t2", 3, true, 2);
258  Cumulatives c3f2("3f2", 3, false, 2);
259  Cumulatives c3t3("3t3", 3, true, 3);
260  Cumulatives c3f3("3f3", 3, false, 3);
261  Cumulatives c3t_1("3t-1", 3, true, -1);
262  Cumulatives c3f_1("3f-1", 3, false, -1);
263  Cumulatives c3t_2("3t-2", 3, true, -2);
264  Cumulatives c3f_2("3f-2", 3, false, -2);
265  Cumulatives c3t_3("3t-3", 3, true, -3);
266  Cumulatives c3f_3("3f-3", 3, false, -3);
268 
269  }
270 }}
271 
272 // STATISTICS: test-int
Cumulatives c2f1("2f1", 2, false, 1)
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
int limit
Limit.
Greater or equal ( )
Definition: int.hh:930
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
bool at_most
Whether to use atmost reasoning.
Cumulatives c3f_3("3f-3", 3, false, -3)
Cumulatives c3f_1("3f-1", 3, false, -1)
Cumulatives c2f3("2f3", 2, false, 3)
Passing integer variables.
Definition: int.hh:656
Cumulatives(const std::string &s, int nt, bool am, int l)
Create and register test.
bool start
Whether event has just started Initialize event.
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition: branch.cpp:120
double am(double t[], unsigned int n)
Compute arithmetic mean of n elements in t.
Definition: script.cpp:74
Cumulatives c3f3("3f3", 3, false, 3)
Computation spaces.
Definition: core.hpp:1742
virtual Assignment * assignment(void) const
Create first assignment.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
Depth-first search engine.
Definition: search.hh:1036
Describe that event is below a certain limit.
Cumulatives c3t_3("3t-3", 3, true, -3)
Integer variable array.
Definition: int.hh:763
Cumulatives c1t1("1t1", 1, true, 1)
Event to be scheduled
Cumulatives c1f1("1f1", 1, false, 1)
Cumulatives c3t1("3t1", 3, true, 1)
int limit
limit Initialize
Gecode toplevel namespace
Integer sets.
Definition: int.hh:174
Class for generating reasonable assignments.
Definition: cumulatives.cpp:90
Cumulatives c1f2("1f2", 1, false, 2)
bool operator()(int val)
Test whether val is above limit
int p
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Test for cumulatives constraint
struct Gecode::Space::@61::@62 p
Data only available during propagation or branching.
Cumulatives c3t3("3t3", 3, true, 3)
Cumulatives c3t_1("3t-1", 3, true, -1)
CumulativeAssignment(int n, const Gecode::IntSet &d)
Initialize assignments for n0 variables and values d0.
Definition: cumulatives.cpp:99
Cumulatives c1t3("1t3", 1, true, 3)
bool valid(std::vector< Event > e, C comp)
Check whether event e is valid.
Cumulatives c2f2("2f2", 2, false, 2)
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
virtual int operator[](int i) const
Return value for variable i.
Ass(Ass &s)
Constructor for cloning s.
Definition: cumulatives.cpp:80
Describe that event is above a certain limit.
Script for generating assignments.
Definition: cumulatives.cpp:64
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:133
virtual void operator++(void)
Move to next assignment.
Cumulatives c2t3("2t3", 2, true, 3)
Cumulatives c3f2("3f2", 3, false, 2)
Ass(int n, const Gecode::IntSet &d)
Initialize model for assignments.
Definition: cumulatives.cpp:69
int ntasks
Number of tasks.
Cumulatives c3t2("3t2", 3, true, 2)
Base class for assignments
Definition: int.hh:59
int limit
limit Initialize
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
virtual ~CumulativeAssignment(void)
Destructor.
Gecode::IntSet d(v, 7)
bool operator()(int val)
Test whether val is below limit
Cumulatives c3f_2("3f-2", 3, false, -2)
bool operator<(const Event &e) const
Test whether this event is before event e
Cumulatives c1f3("1f3", 1, false, 3)
General test support.
Definition: afc.cpp:39
Cumulatives c1t2("1t2", 1, true, 2)
Cumulatives c2t2("2t2", 2, true, 2)
Cumulatives c3f1("3f1", 3, false, 1)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
virtual Gecode::Space * copy(void)
Create copy during cloning.
Definition: cumulatives.cpp:84
Passing integer arguments.
Definition: int.hh:628
virtual bool solution(const Assignment &x) const
Test whether x is solution
Gecode::IntArgs i({1, 2, 3, 4})
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
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, IntPropLevel cl)
Post propagators for the cumulatives constraint.
Cumulatives c3t_2("3t-2", 3, true, -2)
Gecode::IntVarArray x
Store task information.
Definition: cumulatives.cpp:67
Cumulatives c2t1("2t1", 2, true, 1)
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1013
virtual bool operator()(void) const
Test whether all assignments have been iterated