this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2010
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 <climits>
38
39namespace Test { namespace Int {
40
41 /// %Tests for bin-packing constraint
42 namespace BinPacking {
43
44 /**
45 * \defgroup TaskTestIntBinPacking Bin-packing constraints
46 * \ingroup TaskTestInt
47 */
48 //@{
49 /// Generate load and bin assignments
50 class LoadBinAssignment : public Assignment {
51 protected:
52 /// Number of bins
53 int n_bins;
54 /// Number of items
55 int n_items;
56 /// Domain for load variables
57 Gecode::IntSet d_load;
58 /// Domain for bin variables
59 Gecode::IntSet d_bin;
60 /// Load to generate (unless -1)
61 int load;
62 /// Iterator for each variable
63 Gecode::IntSetValues* dsv;
64 public:
65 /// Initialize assignments for load and bin variables
66 LoadBinAssignment(int m, const Gecode::IntSet& d_m,
67 int n, const Gecode::IntSet& d_n,
68 int l)
69 : Assignment(m+n,d_m),
70 n_bins(m), n_items(n), d_load(d_m), d_bin(d_n), load(l),
71 dsv(new Gecode::IntSetValues[static_cast<unsigned int>(m+n)]) {
72 for (int i=n_bins; i--; )
73 dsv[i].init(d_load);
74 for (int i=n_items; i--; )
75 dsv[n_bins+i].init(d_bin);
76 }
77 /// Test whether all assignments have been iterated
78 virtual bool has_more(void) const {
79 return dsv[0]();
80 }
81 /// Move to next assignment
82 virtual void next(Gecode::Support::RandomGenerator&) {
83 // Try to generate next bin assignment
84 {
85 int i = n_items-1;
86 while (i >= 0) {
87 ++dsv[n_bins+i];
88 if (dsv[n_bins+i]())
89 return;
90 dsv[n_bins+(i--)].init(d_bin);
91 }
92 }
93 // Try to generate next load assignment
94 {
95 retry:
96 int i = n_bins-1;
97 while (true) {
98 ++dsv[i];
99 if (dsv[i]() || (i == 0)) {
100 if (dsv[i]() && (load >= 0)) {
101 int l = 0;
102 for (int k=0;k<n_bins; k++)
103 l += dsv[k].val();
104 if (load != l)
105 goto retry;
106 }
107 return;
108 }
109 dsv[i--].init(d_load);
110 }
111 }
112 }
113 /// Return value for variable \a i
114 virtual int operator[](int i) const {
115 assert((i>=0) && (i<n_bins+n_items));
116 return dsv[i].val();
117 }
118 /// Destructor
119 virtual ~LoadBinAssignment(void) {
120 delete [] dsv;
121 }
122 };
123
124 /// %Test with different bin loads and items
125 class BPT : public Test {
126 protected:
127 /// Number of bins
128 int m;
129 /// Item sizes
130 Gecode::IntArgs s;
131 /// Whether to generate only valid loads
132 bool valid;
133 /// Total item sizes
134 int t;
135 /// Array of sufficient size for computing item loads
136 mutable int il[8];
137 /// Compute total size
138 static int total(const Gecode::IntArgs& s) {
139 int t = 0;
140 for (int i=s.size(); i--; )
141 t += s[i];
142 return t;
143 }
144 public:
145 /// Create and register test for \a m bins and item sizes \a s
146 BPT(int m0, const Gecode::IntArgs& s0, bool v=true)
147 : Test("BinPacking::"+str(m0)+"::"+str(s0)+"::"+(v ? "+" : "-"),
148 m0+s0.size(), 0, 100),
149 m(m0), s(s0), valid(v), t(total(s)) {
150 testsearch = false;
151 }
152 /// Create assignment
153 virtual Assignment* assignment(void) const {
154 // Compute plausible bin sizes
155 int a = t / m;
156 return new LoadBinAssignment(m,Gecode::IntSet(a-1,a+2),
157 s.size(),Gecode::IntSet(0,m-1),
158 valid ? t : -1);
159 }
160 /// %Test whether \a x is solution
161 virtual bool solution(const Assignment& x) const {
162 // Loads are from 0 to m-1, after that are items
163 // Check whether loads sum up to total size
164 int l=0;
165 for (int j=m; j--; )
166 l += x[j];
167 if (l != t)
168 return false;
169 // Check whether items are at possible bins
170 for (int j=m; j--; )
171 if ((x[m+j] < 0) || (x[m+j] >= m))
172 return false;
173 // Compute whether items add up
174 for (int j=m; j--; )
175 il[j] = 0;
176 for (int i=s.size(); i--; )
177 il[x[m+i]] += s[i];
178 for (int j=m; j--; )
179 if (il[j] != x[j])
180 return false;
181 return true;
182 }
183 /// Post constraint on \a x
184 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
185 using namespace Gecode;
186 IntVarArgs l(m);
187 IntVarArgs b(s.size());
188 for (int j=m; j--; )
189 l[j]=x[j];
190 for (int i=s.size(); i--; )
191 b[i]=x[m+i];
192 binpacking(home, l, b, s);
193 }
194 };
195
196 /// %Test with different bin loads and items
197 class MBPT : public Test {
198 protected:
199 /// Dimension
200 int d;
201 /// Number of bins
202 int m;
203 /// Item sizes
204 Gecode::IntArgs s;
205 /// Bin capacities
206 Gecode::IntArgs c;
207 /// Array of sufficient size for computing item loads
208 mutable int il[4][8];
209 public:
210 /// Create and register test for \a d0 dimensions, \a m0 bins, item sizes \a s0, and capacities \a c0
211 MBPT(int d0, int m0,
212 const Gecode::IntArgs& s0, const Gecode::IntArgs& c0)
213 : Test("MultiBinPacking::"+str(d0)+"::"+str(m0)+"::"+
214 str(s0)+"::"+str(c0), s0.size() / d0, 0, m0-1),
215 d(d0), m(m0), s(s0), c(c0) {
216 testsearch = false;
217 testfix = false;
218 }
219 /// %Test whether \a x is solution
220 virtual bool solution(const Assignment& x) const {
221 // x are the bin variables
222 for (int k=d; k--; )
223 for (int j=m; j--; )
224 il[k][j] = 0;
225 for (int k=d; k--; )
226 for (int i=x.size(); i--; )
227 il[k][x[i]] += s[i*d+k];
228 for (int k=d; k--; )
229 for (int j=m; j--; )
230 if (il[k][j] > c[k])
231 return false;
232 return true;
233 }
234 /// Post constraint on \a x
235 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
236 using namespace Gecode;
237 IntVarArgs l(d*m);
238 for (int j=m*d; j--; )
239 l[j]=IntVar(home, 0, Gecode::Int::Limits::max);
240 binpacking(home, d, l, x, s, c);
241 }
242 };
243
244 /// Test for testing the max-clique finding for multi bin-packing
245 class CliqueMBPT : public Base {
246 protected:
247 /// Number of items
248 int n_items;
249 /// Expected clique
250 Gecode::IntArgs clique;
251 /// Simple test space class
252 class TestSpace : public Gecode::Space {
253 public:
254 // Constructor
255 TestSpace(void) {}
256 // Copy function
257 virtual Gecode::Space* copy(void) {
258 return nullptr;
259 }
260 };
261 public:
262 /// Test for number of items \a n expected clique \a c
263 CliqueMBPT(const Gecode::IntArgs& c)
264 : Base("Int::MultiBinPacking::Clique::"+Test::str(c)), clique(c) {}
265 /// Run the actual test
266 virtual bool run(void) {
267 using namespace Gecode;
268 TestSpace* home = new TestSpace;
269 /*
270 * Set up a multi-dimensional bin packing problems of dimension 2
271 * where the item sizes in one dimension are all one but for some
272 * random items and two in the other dimension if the item is
273 * included in the clique and where the capacity in both dimensions
274 * is 3.
275 */
276 // Number of items
277 int n_items = clique[clique.size()-1] + 1;
278 // Capacity
279 IntArgs c({3,3});
280 // Item sizes
281 IntArgs s(2*n_items);
282 for (int i=2*n_items; i--; )
283 s[i]=1;
284 // Create some random conflicts
285 for (int i=clique.size()-1; i--; )
286 s[_rand(n_items)*2+0]=2;
287 // Create conflicts corresponding to the clique
288 for (int i=clique.size(); i--; )
289 s[clique[i]*2+1]=2;
290 // Load and bin variables
291 IntVarArgs b(*home, n_items, 0, n_items-1);
292 IntVarArgs l(*home, 2*n_items, 0, 3);
293 IntSet mc = binpacking(*home, 2, l, b, s, c);
294 if (home->status() == SS_FAILED) {
295 delete home;
296 return false;
297 }
298 if (static_cast<unsigned int>(clique.size()) != mc.size()) {
299 delete home;
300 return false;
301 }
302 for (int i=clique.size(); i--; )
303 if (!mc.in(clique[i])) {
304 delete home;
305 return false;
306 }
307 delete home;
308 return true;
309 }
310 };
311
312 /// Help class to create and register tests
313 class Create {
314 public:
315 /// Perform creation and registration
316 Create(void) {
317 using namespace Gecode;
318
319 {
320 IntArgs s0({0,0,0,0});
321 IntArgs s1({2,1,1});
322 IntArgs s2({1,2,3,4});
323 IntArgs s3({4,3,2,1});
324 IntArgs s4({1,2,4,8});
325 IntArgs s5({1,1,1,1});
326 IntArgs s6({1,1,2,2});
327 IntArgs s7({1,3,3,4});
328 IntArgs s8({1,3,3,0,4,0});
329 IntArgs s9({1,2,4,8,16,32});
330
331 for (int m=1; m<4; m++) {
332 (void) new BPT(m, s0);
333 (void) new BPT(m, s1);
334 (void) new BPT(m, s2);
335 (void) new BPT(m, s3);
336 (void) new BPT(m, s4);
337 (void) new BPT(m, s5);
338 (void) new BPT(m, s6);
339 (void) new BPT(m, s7);
340 (void) new BPT(m, s8);
341 (void) new BPT(m, s9);
342 (void) new BPT(m, s1, false);
343 }
344 }
345
346 {
347 IntArgs s1({1,2, 2,1, 1,2, 2,1});
348 IntArgs c1({3,3});
349 (void) new MBPT(2, 4, s1, c1);
350 (void) new MBPT(2, 6, s1, c1);
351 IntArgs s2({1,1, 1,1, 1,1});
352 IntArgs c21({1,1});
353 IntArgs c22({2,2});
354 (void) new MBPT(2, 6, s2, c21);
355 (void) new MBPT(2, 6, s2, c22);
356 IntArgs s3({1,2,3, 3,2,1, 2,1,3, 1,3,2});
357 IntArgs c31({3,3,3});
358 IntArgs c32({4,4,4});
359 IntArgs c33({6,6,6});
360 (void) new MBPT(3, 4, s3, c31);
361 (void) new MBPT(3, 4, s3, c32);
362 (void) new MBPT(3, 4, s3, c33);
363 (void) new MBPT(3, 5, s3, c31);
364 (void) new MBPT(3, 5, s3, c32);
365 (void) new MBPT(3, 5, s3, c33);
366 }
367
368 {
369 IntArgs c1({0,2,4,6});
370 IntArgs c2({1,2,3,4,5,6,7,8});
371 IntArgs c3({1,3,7,10,15,22,27,97});
372 IntArgs c41({1,2,3,4,5,6,7,14});
373 IntArgs c42({1,2,3,4,5,6,7,15});
374 IntArgs c43({1,2,3,4,5,6,7,16});
375 IntArgs c44({1,2,3,4,5,6,7,30});
376 IntArgs c45({1,2,3,4,5,6,7,31});
377 IntArgs c46({1,2,3,4,5,6,7,32});
378 IntArgs c47({1,2,3,4,5,6,7,62});
379 IntArgs c48({1,2,3,4,5,6,7,63});
380 IntArgs c49({1,2,3,4,5,6,7,64});
381
382 (void) new CliqueMBPT(c1);
383 (void) new CliqueMBPT(c2);
384 (void) new CliqueMBPT(c3);
385 (void) new CliqueMBPT(c41);
386 (void) new CliqueMBPT(c42);
387 (void) new CliqueMBPT(c43);
388 (void) new CliqueMBPT(c44);
389 (void) new CliqueMBPT(c45);
390 (void) new CliqueMBPT(c46);
391 (void) new CliqueMBPT(c47);
392 (void) new CliqueMBPT(c48);
393 (void) new CliqueMBPT(c49);
394 }
395 }
396 };
397
398 Create c;
399
400 //@}
401
402 }
403
404}}
405
406
407// STATISTICS: test-int
408