Generated on for Gecode by doxygen 1.17.0
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 Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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
44namespace Test { namespace Int {
45
47 namespace Cumulatives {
48
54
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 }
79
80 Ass(Ass& s) : Gecode::Space(s) {
81 x.update(*this, s.x);
82 }
83
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 != nullptr)
105 nxt = e->next();
106 }
107
108 virtual bool has_more(void) const {
109 return nxt != nullptr;
110 }
111
113 delete cur;
114 cur = nxt;
115 if (cur != nullptr) nxt = e->next();
116 }
117
118 virtual int operator[](int i) const {
119 assert((i>=0) && (i<n) && (cur != nullptr));
120 return cur->x[i].val();
121 }
122
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 };
152
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 }
197
198 virtual Assignment* assignment(void) const {
199 assert(arity == 4*ntasks);
200 return new CumulativeAssignment(arity, dom);
201 }
202
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 }
226
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
245 private:
246 class Fixture : public Gecode::Space {
247 public:
248 Gecode::IntVar producer;
249 Fixture(bool at_most)
250 : producer(*this,at_most ? -10 : 0,at_most ? 0 : 10) {
251 using namespace Gecode;
252 const int sign = at_most ? 1 : -1;
253 IntVarArgs usage({IntVar(*this,3*sign,3*sign),
254 IntVar(*this,5*sign,5*sign),producer});
255 cumulatives(*this,IntArgs({0,0,0}),
256 IntVarArgs(*this,3,0,0),IntVarArgs(*this,3,1,1),
257 IntVarArgs(*this,3,1,1),usage,IntArgs({0}),at_most);
258 }
259 Fixture(Fixture& fixture) : Gecode::Space(fixture) {
260 producer.update(*this,fixture.producer);
261 }
262 virtual Gecode::Space* copy(void) {
263 return new Fixture(*this);
264 }
265 };
266 public:
268 : Test::Base("Cumulatives::ProfileContribution",TestTags::check()) {}
269 virtual bool run(void) {
270 Fixture upper(true), lower(false);
271 return (upper.status() != Gecode::SS_FAILED) &&
272 (lower.status() != Gecode::SS_FAILED) &&
273 (upper.producer.min() == -10) && (upper.producer.max() == -8) &&
274 (lower.producer.min() == 8) && (lower.producer.max() == 10);
275 }
277
279 class EmptyProfile : public Test {
280 public:
282 : Test(TestTags::check(),"Cumulatives::EmptyProfile",1,-2,-1) {}
283 virtual bool solution(const Assignment&) const {
284 return true;
285 }
286 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
287 using namespace Gecode;
288 cumulatives(home,IntArgs({0,0}),IntVarArgs(home,2,0,0),
289 IntVarArgs({IntVar(home,1,1),IntVar(home,0,0)}),
290 IntVarArgs({IntVar(home,1,1),IntVar(home,0,0)}),
291 IntVarArgs({IntVar(home,1,1),x[0]}),IntArgs({1}),true);
292 }
294
295 Cumulatives c1t1("1t1", 1, true, 1);
296 Cumulatives c1f1("1f1", 1, false, 1);
297 Cumulatives c1t2("1t2", 1, true, 2);
298 Cumulatives c1f2("1f2", 1, false, 2);
299 Cumulatives c1t3("1t3", 1, true, 3);
300 Cumulatives c1f3("1f3", 1, false, 3);
301 Cumulatives c2t1("2t1", 2, true, 1);
302 Cumulatives c2f1("2f1", 2, false, 1);
303 Cumulatives c2t2("2t2", 2, true, 2);
304 Cumulatives c2f2("2f2", 2, false, 2);
305 Cumulatives c2t3("2t3", 2, true, 3);
306 Cumulatives c2f3("2f3", 2, false, 3);
307 Cumulatives c3t1("3t1", 3, true, 1);
308 Cumulatives c3f1("3f1", 3, false, 1);
309 Cumulatives c3t2("3t2", 3, true, 2);
310 Cumulatives c3f2("3f2", 3, false, 2);
311 Cumulatives c3t3("3t3", 3, true, 3);
312 Cumulatives c3f3("3f3", 3, false, 3);
313 Cumulatives c3t_1("3t-1", 3, true, -1);
314 Cumulatives c3f_1("3f-1", 3, false, -1);
315 Cumulatives c3t_2("3t-2", 3, true, -2);
316 Cumulatives c3f_2("3f-2", 3, false, -2);
317 Cumulatives c3t_3("3t-3", 3, true, -3);
318 Cumulatives c3f_3("3f-3", 3, false, -3);
320
321 }
322}}
323
324// STATISTICS: test-int
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Depth-first search engine.
Definition search.hh:1211
Passing integer arguments.
Definition int.hh:653
Integer sets.
Definition int.hh:179
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
int min(void) const
Return minimum of domain.
Definition int.hpp:62
int max(void) const
Return maximum of domain.
Definition int.hpp:70
Computation spaces.
Definition core.hpp:1787
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
Base class for assignments
Definition int.hh:73
Gecode::IntSet d
Domain for each variable.
Definition int.hh:76
int n
Number of variables.
Definition int.hh:75
Assignment(int n0, const Gecode::IntSet &d0)
Initialize assignments for n0 variables and values d0.
Definition int.hpp:43
Describe that event is above a certain limit.
bool operator()(int val)
Test whether val is above limit
Script for generating assignments.
Ass(Ass &s)
Constructor for cloning s.
virtual Gecode::Space * copy(void)
Create copy during cloning.
Ass(int n, const Gecode::IntSet &d)
Initialize model for assignments.
Gecode::IntVarArray x
Store task information.
Describe that event is below a certain limit.
bool operator()(int val)
Test whether val is below limit
Class for generating reasonable assignments.
virtual bool has_more(void) const
Test whether all assignments have been iterated
CumulativeAssignment(int n, const Gecode::IntSet &d)
Initialize assignments for n0 variables and values d0.
virtual void next(Gecode::Support::RandomGenerator &)
Move to next assignment.
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 void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
virtual Assignment * assignment(void) const
Create first assignment.
Cumulatives(const std::string &s, int nt, bool am, int l)
Create and register test.
virtual bool solution(const Assignment &) const
Check for solution.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
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)
bool testsearch
Whether to perform search test.
Definition int.hh:285
int arity
Number of variables.
Definition int.hh:273
Gecode::IntSet dom
Domain of variables.
Definition int.hh:275
Set of test tags.
Definition test.hh:105
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_GQ
Greater or equal ( ).
Definition int.hh:1230
Space(void)
Default constructor.
Definition core.cpp:121
virtual Space * copy(void)=0
Copying member function.
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Gecode toplevel namespace
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
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 ipl=IPL_DEF)
Post propagators for the cumulatives constraint.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
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)
Test::Int::Cumulatives::EmptyProfile empty_profile
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)
Test::Int::Cumulatives::ProfileContribution profile_contribution
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)
Testing finite domain integers.
Definition int.cpp:41
General test support.
Definition afc.cpp:41
@ check
Basic integrity tests.
Definition test.hh:99