Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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 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
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 != NULL)
105 nxt = e->next();
106 }
107
108 virtual bool operator()(void) const {
109 return nxt != NULL;
110 }
111
112 virtual void operator++(void) {
113 delete cur;
114 cur = nxt;
115 if (cur != NULL) nxt = e->next();
116 }
117
118 virtual int operator[](int i) const {
119 assert((i>=0) && (i<n) && (cur != NULL));
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
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
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
Depth-first search engine.
Definition search.hh:1036
Passing integer arguments.
Definition int.hh:634
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Computation spaces.
Definition core.hpp:1744
Base class for assignments
Definition int.hh:59
Gecode::IntSet d
Domain for each variable.
Definition int.hh:62
int n
Number of variables.
Definition int.hh:61
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 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.
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.
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:238
int arity
Number of variables.
Definition int.hh:226
Gecode::IntSet dom
Domain of variables.
Definition int.hh:228
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:945
Space(void)
Default constructor.
Definition core.cpp:115
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
Post propagator for SetVar x
Definition set.hh:773
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)
Testing finite domain integers.
Definition int.cpp:40
General test support.
Definition afc.cpp:39