Generated on for Gecode by doxygen 1.17.0
unary.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.dev>
5 *
6 * Copyright:
7 * Christian Schulte, 2009
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
38namespace Test { namespace Int {
40 namespace Unary {}
41}}
42
43namespace Test { namespace Int { namespace Unary {
44
50
51 class ManFixPUnary : public Test {
52 protected:
56 static int st(const Gecode::IntArgs& p) {
57 int t = 0;
58 for (int i=p.size(); i--; )
59 t += p[i];
60 return t;
61 }
62 public:
65 int o, Gecode::IntPropLevel ipl0)
66 : Test(tags,"Unary::Man::Fix::"+str(o)+"::"+str(p0)+"::"+str(ipl0),
67 p0.size(),o,o+st(p0),false,ipl0),
68 p(p0) {
69 testsearch = false;
71 }
72
73 virtual Assignment* assignment(void) const {
74 return new RandomAssignment(arity, dom, 500, _rand);
75 }
76
77 virtual bool solution(const Assignment& x) const {
78 for (int i=0; i<x.size(); i++)
79 for (int j=i+1; j<x.size(); j++)
80 if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i]))
81 return false;
82 return true;
83 }
84
85 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
86 Gecode::unary(home, x, p, ipl);
87 }
88 };
89
91 class OptFixPUnary : public Test {
92 protected:
96 int l;
98 static int st(const Gecode::IntArgs& p) {
99 int t = 0;
100 for (int i=p.size(); i--; )
101 t += p[i];
102 return t;
103 }
104 public:
107 int o, Gecode::IntPropLevel ipl0)
108 : Test(tags,"Unary::Opt::Fix::"+str(o)+"::"+str(p0)+"::"+str(ipl0),
109 2*p0.size(),o,o+st(p0),false,ipl0), p(p0), l(o+st(p)/2) {
110 testsearch = false;
112 }
113
114 virtual Assignment* assignment(void) const {
115 return new RandomAssignment(arity, dom, 500, _rand);
116 }
117
118 virtual bool solution(const Assignment& x) const {
119 int n = x.size() / 2;
120 for (int i=0; i<n; i++)
121 if (x[n+i] > l)
122 for (int j=i+1; j<n; j++)
123 if(x[n+j] > l)
124 if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i]))
125 return false;
126 return true;
127 }
128
129 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
130 int n=x.size() / 2;
133 for (int i=0; i<n; i++) {
134 s[i]=x[i];
135 m[i]=Gecode::expr(home, (x[n+i] > l));
136 }
137 Gecode::unary(home, s, p, m, ipl);
138 }
139 };
140
142 class ManFlexUnary : public Test {
143 protected:
145 int _minP;
147 int _maxP;
149 int off;
150 public:
152 ManFlexUnary(TestTags tags, int n, int minP, int maxP,
153 int o, Gecode::IntPropLevel ipl0)
154 : Test(tags,"Unary::Man::Flex::"+str(o)+"::"+str(n)+"::"
155 +str(minP)+"::"+str(maxP)+"::"+str(ipl0),
156 2*n,0,n*maxP,false,ipl0), _minP(minP), _maxP(maxP), off(o) {
157 testsearch = false;
158 testfix = false;
160 }
161
162 virtual Assignment* assignment(void) const {
163 return new RandomMixAssignment(arity / 2, dom, arity / 2,
165 }
166
167 virtual bool solution(const Assignment& x) const {
168 int n = x.size()/2;
169 for (int i=0; i<n; i++)
170 for (int j=i+1; j<n; j++)
171 if ((x[i]+x[n+i] > x[j]) && (x[j]+x[n+j] > x[i]))
172 return false;
173 return true;
174 }
175
176 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
177 Gecode::IntVarArgs s(x.size()/2);
178 Gecode::IntVarArgs px(x.slice(x.size()/2));
179 Gecode::IntVarArgs e(home,x.size()/2,
182 for (int i=s.size(); i--;) {
183 s[i] = expr(home, off+x[i]);
184 rel(home, s[i]+px[i] == e[i]);
185 rel(home, _minP <= px[i]);
186 rel(home, _maxP >= px[i]);
187 }
188 Gecode::unary(home, s, px, e, ipl);
189 }
190 };
191
193 class OptFlexUnary : public Test {
194 protected:
196 int _minP;
198 int _maxP;
200 int off;
202 int l;
204 static int st(const Gecode::IntArgs& p) {
205 int t = 0;
206 for (int i=p.size(); i--; )
207 t += p[i];
208 return t;
209 }
210 public:
212 OptFlexUnary(TestTags tags, int n, int minP, int maxP,
213 int o, Gecode::IntPropLevel ipl0)
214 : Test(tags,"Unary::Opt::Flex::"+str(o)+"::"+str(n)+"::"
215 +str(minP)+"::"+str(maxP)+"::"+str(ipl0),
216 3*n,0,n*maxP,false,ipl0), _minP(minP), _maxP(maxP), off(o),
217 l(n*maxP/2) {
218 testsearch = false;
219 testfix = false;
221 }
222
223 virtual Assignment* assignment(void) const {
224 return new RandomMixAssignment(2 * (arity / 3), dom, arity / 3,
226 }
227
228 virtual bool solution(const Assignment& x) const {
229 int n = x.size() / 3;
230 for (int i=0; i<n; i++)
231 if (x[n+i] > l)
232 for (int j=i+1; j<n; j++)
233 if(x[n+j] > l)
234 if ((x[i]+x[2*n+i] > x[j]) && (x[j]+x[2*n+j] > x[i]))
235 return false;
236 return true;
237 }
238
239 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
240 int n=x.size() / 3;
241
243 Gecode::IntVarArgs px(n);
244 Gecode::IntVarArgs e(home,n,
247 for (int i=n; i--;) {
248 s[i] = expr(home, off+x[i]);
249 px[i] = x[2*n+i];
250 rel(home, s[i]+px[i] == e[i]);
251 rel(home, _minP <= px[i]);
252 rel(home, _maxP >= px[i]);
253 }
255 for (int i=0; i<n; i++)
256 m[i]=Gecode::expr(home, (x[n+i] > l));
257 Gecode::unary(home, s, px, e, m, ipl);
258 }
259 };
260
262 class Create {
263 public:
265 Create(void) {
266 using namespace Gecode;
267 IntArgs p1({2,2,2,2});
268 IntArgs p10({2,2,0,2,2});
269 IntArgs p2({4,3,3,5});
270 IntArgs p20({4,0,3,3,0,5});
271 IntArgs p3({4,2,9,3,7,5});
272 IntArgs p30({4,0,2,9,3,7,5,0});
273
274 for (IntPropBasicAdvanced ipba; ipba(); ++ipba) {
275 TestTags representative = ipba.ipl() == Gecode::IPL_ADVANCED
277 (void) new ManFixPUnary(TestTags::sweep(),p1,0,ipba.ipl());
278 (void) new ManFixPUnary(TestTags::sweep(),p1,Gecode::Int::Limits::min,ipba.ipl());
279 (void) new OptFixPUnary(TestTags::sweep(),p1,0,ipba.ipl());
280 (void) new OptFixPUnary(TestTags::sweep(),p1,Gecode::Int::Limits::min,ipba.ipl());
281 (void) new ManFlexUnary(TestTags::sweep(),4,0,2,0,ipba.ipl());
282 (void) new ManFlexUnary(representative,4,0,2,Gecode::Int::Limits::min,ipba.ipl());
283 (void) new ManFlexUnary(TestTags::sweep(),4,1,3,0,ipba.ipl());
284 (void) new ManFlexUnary(TestTags::sweep(),4,1,3,Gecode::Int::Limits::min,ipba.ipl());
285 (void) new OptFlexUnary(TestTags::sweep(),4,0,2,0,ipba.ipl());
286 (void) new OptFlexUnary(representative,4,0,2,Gecode::Int::Limits::min,ipba.ipl());
287
288 (void) new ManFixPUnary(TestTags::sweep(),p10,0,ipba.ipl());
289 (void) new ManFixPUnary(representative,p10,Gecode::Int::Limits::min,ipba.ipl());
290 (void) new OptFixPUnary(TestTags::sweep(),p10,0,ipba.ipl());
291 (void) new OptFixPUnary(representative,p10,Gecode::Int::Limits::min,ipba.ipl());
292 (void) new ManFlexUnary(TestTags::sweep(),5,0,2,0,ipba.ipl());
293 (void) new ManFlexUnary(TestTags::sweep(),5,0,2,Gecode::Int::Limits::min,ipba.ipl());
294 (void) new OptFlexUnary(TestTags::sweep(),5,0,2,0,ipba.ipl());
295 (void) new OptFlexUnary(TestTags::sweep(),5,0,2,Gecode::Int::Limits::min,ipba.ipl());
296
297 (void) new ManFixPUnary(TestTags::sweep(),p2,0,ipba.ipl());
298 (void) new ManFixPUnary(TestTags::sweep(),p2,Gecode::Int::Limits::min,ipba.ipl());
299 (void) new OptFixPUnary(TestTags::sweep(),p2,0,ipba.ipl());
300 (void) new OptFixPUnary(TestTags::sweep(),p2,Gecode::Int::Limits::min,ipba.ipl());
301 (void) new ManFlexUnary(TestTags::sweep(),4,3,5,0,ipba.ipl());
302 (void) new ManFlexUnary(TestTags::sweep(),4,3,5,Gecode::Int::Limits::min,ipba.ipl());
303 (void) new OptFlexUnary(TestTags::sweep(),4,3,5,0,ipba.ipl());
304 (void) new OptFlexUnary(TestTags::sweep(),4,3,5,Gecode::Int::Limits::min,ipba.ipl());
305
306 (void) new ManFixPUnary(TestTags::sweep(),p20,0,ipba.ipl());
307 (void) new ManFixPUnary(TestTags::sweep(),p20,Gecode::Int::Limits::min,ipba.ipl());
308 (void) new OptFixPUnary(TestTags::sweep(),p20,0,ipba.ipl());
309 (void) new OptFixPUnary(TestTags::sweep(),p20,Gecode::Int::Limits::min,ipba.ipl());
310 (void) new ManFlexUnary(TestTags::sweep(),6,0,5,0,ipba.ipl());
311 (void) new ManFlexUnary(TestTags::sweep(),6,0,5,Gecode::Int::Limits::min,ipba.ipl());
312 (void) new OptFlexUnary(TestTags::sweep(),6,0,5,0,ipba.ipl());
313 (void) new OptFlexUnary(TestTags::sweep(),6,0,5,Gecode::Int::Limits::min,ipba.ipl());
314
315 (void) new ManFixPUnary(TestTags::sweep(),p3,0,ipba.ipl());
316 (void) new ManFixPUnary(TestTags::sweep(),p3,Gecode::Int::Limits::min,ipba.ipl());
317 (void) new OptFixPUnary(TestTags::sweep(),p3,0,ipba.ipl());
318 (void) new OptFixPUnary(TestTags::sweep(),p3,Gecode::Int::Limits::min,ipba.ipl());
319 (void) new ManFlexUnary(TestTags::sweep(),6,2,7,0,ipba.ipl());
320 (void) new ManFlexUnary(TestTags::sweep(),6,2,7,Gecode::Int::Limits::min,ipba.ipl());
321 (void) new OptFlexUnary(TestTags::sweep(),6,2,7,0,ipba.ipl());
322 (void) new OptFlexUnary(TestTags::sweep(),6,2,7,Gecode::Int::Limits::min,ipba.ipl());
323
324 (void) new ManFixPUnary(TestTags::sweep(),p30,0,ipba.ipl());
325 (void) new ManFixPUnary(TestTags::sweep(),p30,Gecode::Int::Limits::min,ipba.ipl());
326 (void) new OptFixPUnary(TestTags::sweep(),p30,0,ipba.ipl());
327 (void) new OptFixPUnary(TestTags::sweep(),p30,Gecode::Int::Limits::min,ipba.ipl());
328 (void) new ManFlexUnary(TestTags::sweep(),8,0,9,0,ipba.ipl());
329 (void) new ManFlexUnary(TestTags::sweep(),8,0,9,Gecode::Int::Limits::min,ipba.ipl());
330 (void) new OptFlexUnary(TestTags::sweep(),8,0,9,0,ipba.ipl());
331 (void) new OptFlexUnary(TestTags::sweep(),8,0,9,Gecode::Int::Limits::min,ipba.ipl());
332 }
333 }
334 };
335
338
339
340}}}
341
342// STATISTICS: test-int
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Passing Boolean variables.
Definition int.hh:739
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
Computation spaces.
Definition core.hpp:1787
ArrayTraits< VarArgArray< Var > >::ArgsType slice(int start, int inc=1, int n=-1)
Definition array.hpp:965
int size(void) const
Return size of array (number of elements).
Definition array.hpp:945
Gecode::Support::RandomGenerator _rand
Random number generator.
Definition test.hh:238
TestTags tags(void) const
Return tags for test.
Definition test.hpp:95
Base class for assignments
Definition int.hh:73
int size(void) const
Return number of variables.
Definition int.hpp:46
Iterator for basic and advanced integer propagation levels.
Definition int.hh:448
Generate random selection of assignments.
Definition int.hh:110
Generate random selection of assignments.
Definition int.hh:130
bool testsearch
Whether to perform search test.
Definition int.hh:285
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
bool testfix
Whether to perform fixpoint test.
Definition int.hh:287
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
int arity
Number of variables.
Definition int.hh:273
Gecode::IntSet dom
Domain of variables.
Definition int.hh:275
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:283
Help class to create and register tests.
Definition unary.cpp:262
Create(void)
Perform creation and registration.
Definition unary.cpp:265
Test for unary constraint
Definition unary.cpp:51
Gecode::IntArgs p
The processing times.
Definition unary.cpp:54
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition unary.cpp:73
ManFixPUnary(TestTags tags, const Gecode::IntArgs &p0, int o, Gecode::IntPropLevel ipl0)
Create and register test.
Definition unary.cpp:64
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition unary.cpp:85
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition unary.cpp:77
static int st(const Gecode::IntArgs &p)
Get a reasonable maximal start time.
Definition unary.cpp:56
Test for unary constraint
Definition unary.cpp:142
ManFlexUnary(TestTags tags, int n, int minP, int maxP, int o, Gecode::IntPropLevel ipl0)
Create and register test.
Definition unary.cpp:152
int off
Offset for start times.
Definition unary.cpp:149
int _minP
Minimum processing time.
Definition unary.cpp:145
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition unary.cpp:176
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition unary.cpp:162
int _maxP
Maximum processing time.
Definition unary.cpp:147
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition unary.cpp:167
Test for unary constraint with optional tasks
Definition unary.cpp:91
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition unary.cpp:114
Gecode::IntArgs p
The processing times.
Definition unary.cpp:94
static int st(const Gecode::IntArgs &p)
Get a reasonable maximal start time.
Definition unary.cpp:98
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition unary.cpp:118
OptFixPUnary(TestTags tags, const Gecode::IntArgs &p0, int o, Gecode::IntPropLevel ipl0)
Create and register test.
Definition unary.cpp:106
int l
Threshold for taking a task as optional.
Definition unary.cpp:96
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition unary.cpp:129
Test for unary constraint with optional tasks
Definition unary.cpp:193
int _minP
Minimum processing time.
Definition unary.cpp:196
static int st(const Gecode::IntArgs &p)
Get a reasonable maximal start time.
Definition unary.cpp:204
int off
Offset for start times.
Definition unary.cpp:200
int l
Threshold for taking a task as optional.
Definition unary.cpp:202
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition unary.cpp:239
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition unary.cpp:223
OptFlexUnary(TestTags tags, int n, int minP, int maxP, int o, Gecode::IntPropLevel ipl0)
Create and register test.
Definition unary.cpp:212
int _maxP
Maximum processing time.
Definition unary.cpp:198
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition unary.cpp:228
Set of test tags.
Definition test.hh:105
static TestTags sweep(void)
Expensive parameter sweeps.
Definition test.hpp:59
static TestTags standard(void)
Standard suite without expensive sweeps.
Definition test.hpp:55
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_ADVANCED
Use advanced propagation algorithm.
Definition int.hh:1282
const int min
Smallest allowed integer value.
Definition int.hh:123
const int max
Largest allowed integer value.
Definition int.hh:121
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
void unary(Home home, const IntVarArgs &s, const IntArgs &p, IntPropLevel ipl=IPL_DEF)
Post propagators for scheduling tasks on unary resources.
Definition unary.cpp:44
Tests for unary scheduling constraints
Definition unary.cpp:40
Testing finite domain integers.
Definition int.cpp:41
@ CTL_NONE
No consistency-test.
Definition int.hh:154
General test support.
Definition afc.cpp:41