Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.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  * 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;
134  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;
146  Below(int l) : limit(l) {}
148  bool operator()(int val) {
149  return val <= limit;
150  }
151  };
153  class Above {
154  public:
155  int limit;
157  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
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Depth-first search engine.
Definition: search.hh:1036
Passing integer arguments.
Definition: int.hh:628
Integer sets.
Definition: int.hh:174
Passing integer variables.
Definition: int.hh:656
Integer variable array.
Definition: int.hh:763
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
Computation spaces.
Definition: core.hpp:1742
struct Gecode::Space::@61::@62 p
Data only available during propagation or branching.
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1013
Base class for assignments
Definition: int.hh:59
Describe that event is above a certain limit.
bool operator()(int val)
Test whether val is above limit
int limit
limit Initialize
Script for generating assignments.
Definition: cumulatives.cpp:64
Ass(Ass &s)
Constructor for cloning s.
Definition: cumulatives.cpp:80
Ass(int n, const Gecode::IntSet &d)
Initialize model for assignments.
Definition: cumulatives.cpp:69
Gecode::IntVarArray x
Store task information.
Definition: cumulatives.cpp:67
virtual Gecode::Space * copy(void)
Create copy during cloning.
Definition: cumulatives.cpp:84
Describe that event is below a certain limit.
int limit
limit Initialize
bool operator()(int val)
Test whether val is below limit
Class for generating reasonable assignments.
Definition: cumulatives.cpp:90
virtual void operator++(void)
Move to next assignment.
virtual bool operator()(void) const
Test whether all assignments have been iterated
CumulativeAssignment(int n, const Gecode::IntSet &d)
Initialize assignments for n0 variables and values d0.
Definition: cumulatives.cpp:99
virtual ~CumulativeAssignment(void)
Destructor.
virtual int operator[](int i) const
Return value for variable i.
Test for cumulatives constraint
bool at_most
Whether to use atmost reasoning.
virtual bool solution(const Assignment &x) const
Test whether x is solution
virtual Assignment * assignment(void) const
Create first assignment.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Cumulatives(const std::string &s, int nt, bool am, int l)
Create and register test.
Event to be scheduled
bool start
Whether event has just started Initialize event.
int h
Position and height of event.
bool operator<(const Event &e) const
Test whether this event is before event e
Event(int pos, int height, bool s)
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
void cumulatives(Home home, const IntVarArgs &m, const IntVarArgs &s, const IntVarArgs &p, const IntVarArgs &e, const IntVarArgs &u, const IntArgs &c, bool at_most, IntPropLevel cl)
Post propagators for the cumulatives constraint.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
@ IRT_GQ
Greater or equal ( )
Definition: int.hh:930
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
double am(double t[], unsigned int n)
Compute arithmetic mean of n elements in t.
Definition: script.cpp:74
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:133
Gecode::IntArgs i({1, 2, 3, 4})
Cumulatives c1t3("1t3", 1, true, 3)
bool valid(std::vector< Event > e, C comp)
Check whether event e is valid.
Cumulatives c3f1("3f1", 3, false, 1)
Cumulatives c3f_2("3f-2", 3, false, -2)
Cumulatives c2t2("2t2", 2, true, 2)
Cumulatives c1t1("1t1", 1, true, 1)
Cumulatives c3t_2("3t-2", 3, true, -2)
Cumulatives c3f3("3f3", 3, false, 3)
Cumulatives c2f1("2f1", 2, false, 1)
Cumulatives c1f1("1f1", 1, false, 1)
Cumulatives c2f2("2f2", 2, false, 2)
Cumulatives c2t3("2t3", 2, true, 3)
Cumulatives c1t2("1t2", 1, true, 2)
Cumulatives c2t1("2t1", 2, true, 1)
Cumulatives c3t_3("3t-3", 3, true, -3)
Cumulatives c3t2("3t2", 3, true, 2)
Cumulatives c2f3("2f3", 2, false, 3)
Cumulatives c3f2("3f2", 3, false, 2)
Cumulatives c1f2("1f2", 1, false, 2)
Cumulatives c1f3("1f3", 1, false, 3)
Cumulatives c3t1("3t1", 3, true, 1)
Cumulatives c3f_3("3f-3", 3, false, -3)
Cumulatives c3f_1("3f-1", 3, false, -1)
Cumulatives c3t_1("3t-1", 3, true, -1)
Cumulatives c3t3("3t3", 3, true, 3)
Gecode::IntSet d(v, 7)
General test support.
Definition: afc.cpp:39