this repo has no description
dekker.one
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
46 /// %Tests for scheduling constraints
47 namespace Cumulatives {
48
49 /**
50 * \defgroup TaskTestIntCumulatives Cumnulatives scheduling constraint
51 * \ingroup TaskTestInt
52 */
53 //@{
54 /**
55 * \brief Script for generating assignments.
56 *
57 * We are only interested in assignments that represent tasks (s_i,
58 * d_i, e_i, h_i) such that the following hold:
59 * - The task starts at a positive time and has some extension.
60 * - The equation s_i + d_i = e_i holds.
61 * - The tasks are ordered to remove some symmetries, i.e.,
62 * s_i <= s_{i+1}
63 */
64 class Ass : public Gecode::Space {
65 public:
66 /// Store task information
67 Gecode::IntVarArray x;
68 /// Initialize model for assignments
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 /// Constructor for cloning \a s
80 Ass(Ass& s) : Gecode::Space(s) {
81 x.update(*this, s.x);
82 }
83 /// Create copy during cloning
84 virtual Gecode::Space* copy(void) {
85 return new Ass(*this);
86 }
87 };
88
89 /// Class for generating reasonable assignments
90 class CumulativeAssignment : public Assignment {
91 /// Current assignment
92 Ass* cur;
93 /// Next assignment
94 Ass* nxt;
95 /// Search engine to find assignments
96 Gecode::DFS<Ass>* e;
97 public:
98 /// Initialize assignments for \a n0 variables and values \a d0
99 CumulativeAssignment(int n, const Gecode::IntSet& d) : Assignment(n,d) {
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 /// %Test whether all assignments have been iterated
108 virtual bool has_more(void) const {
109 return nxt != nullptr;
110 }
111 /// Move to next assignment
112 virtual void next(Gecode::Support::RandomGenerator&) {
113 delete cur;
114 cur = nxt;
115 if (cur != nullptr) nxt = e->next();
116 }
117 /// Return value for variable \a i
118 virtual int operator[](int i) const {
119 assert((i>=0) && (i<n) && (cur != nullptr));
120 return cur->x[i].val();
121 }
122 /// Destructor
123 virtual ~CumulativeAssignment(void) {
124 delete cur; delete nxt; delete e;
125 }
126 };
127
128 /// %Event to be scheduled
129 class Event {
130 public:
131 int p, h; ///< Position and height of event
132 bool start; ///< Whether event has just started
133 /// Initialize event
134 Event(int pos, int height, bool s) : p(pos), h(height), start(s) {}
135 /// %Test whether this event is before event \a e
136 bool operator<(const Event& e) const {
137 return p<e.p;
138 }
139 };
140
141 /// Describe that event is below a certain limit
142 class Below {
143 public:
144 int limit; ///< limit
145 /// Initialize
146 Below(int l) : limit(l) {}
147 /// %Test whether \a val is below limit
148 bool operator()(int val) {
149 return val <= limit;
150 }
151 };
152 /// Describe that event is above a certain limit
153 class Above {
154 public:
155 int limit; ///< limit
156 /// Initialize
157 Above(int l) : limit(l) {}
158 /// %Test whether \a val is above limit
159 bool operator()(int val) {
160 return val >= limit;
161 }
162 };
163
164 /// Check whether event \a e is valid
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
185 /// %Test for cumulatives constraint
186 class Cumulatives : public Test {
187 protected:
188 int ntasks; ///< Number of tasks
189 bool at_most; ///< Whether to use atmost reasoning
190 int limit; ///< Limit
191 public:
192 /// Create and register test
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 /// Create first assignment
198 virtual Assignment* assignment(void) const {
199 assert(arity == 4*ntasks);
200 return new CumulativeAssignment(arity, dom);
201 }
202 /// %Test whether \a x is solution
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 /// Post constraint on \a x
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);
267 //@}
268
269 }
270}}
271
272// STATISTICS: test-int