Generated on for Gecode by doxygen 1.17.0
bin-packing.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, 2010
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 <climits>
38
39namespace Test { namespace Int {
40
42 namespace BinPacking {
43
49
51 protected:
53 int n_bins;
61 int load;
64 public:
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
78 virtual bool has_more(void) const {
79 return dsv[0]();
80 }
81
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
114 virtual int operator[](int i) const {
115 assert((i>=0) && (i<n_bins+n_items));
116 return dsv[i].val();
117 }
118
119 virtual ~LoadBinAssignment(void) {
120 delete [] dsv;
121 }
122 };
123
125 class BPT : public Test {
126 protected:
128 int m;
132 bool valid;
134 int t;
136 mutable int il[8];
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:
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
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
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
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
197 class MBPT : public Test {
198 protected:
200 int d;
202 int m;
208 mutable int il[4][8];
209 public:
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
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
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
245 class CliqueMBPT : public Base {
246 protected:
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:
264 : Base("Int::MultiBinPacking::Clique::"+Test::str(c)), clique(c) {}
265
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
313 class PropagationLevels : public Base {
314 protected:
316 class TestSpace : public Gecode::Space {
317 public:
318 TestSpace(void) {}
319 virtual Gecode::Space* copy(void) {
320 return nullptr;
321 }
322 };
323
324 bool check_case(int n_bins, int capacity, const Gecode::IntArgs& sizes,
325 const bool expected_failed[4]) const {
326 using namespace Gecode;
327 IntPropLevel const levels[] =
329 for (unsigned int i = 0; i < 4; i += 1) {
330 TestSpace* home = new TestSpace;
331 IntVarArgs l(*home, n_bins, 0, capacity);
332 IntVarArgs b(*home, sizes.size(), 0, n_bins-1);
333 binpacking(*home, l, b, sizes, levels[i]);
334 bool failed = home->status() == SS_FAILED;
335 delete home;
336 if (failed != expected_failed[i])
337 return false;
338 }
339 return true;
340 }
341 public:
344 : Base("Int::BinPacking::PropagationLevels") {}
345
346 virtual bool run(void) {
347 using namespace Gecode;
348 bool const advanced_failed[] = {false, true, true, true};
349 bool const full_failed[] = {false, false, false, true};
350 return
351 check_case(3, 5, IntArgs({4,2,2,2,2,2}), advanced_failed) &&
352 check_case(5, 35,
353 IntArgs({32,30,24,21,19,11,10,9,8,5,3}),
354 full_failed);
355 }
356 };
357
359 class DFFLargeWeights : public Test {
360 int capacity;
361 int weight;
362 public:
363 DFFLargeWeights(int n, int c, int w)
364 : Test("BinPacking::DFFLargeWeights::"+str(n)+"::"+str(w),
365 n,0,1), capacity(c), weight(w) {}
366 virtual bool solution(const Assignment& x) const {
367 long long loads[2] = {0,0};
368 for (int i=0; i<x.size(); i++)
369 loads[x[i]] += weight;
370 return (loads[0] <= capacity) && (loads[1] <= capacity);
371 }
372 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
373 Gecode::IntVarArgs loads(home,2,0,capacity);
374 Gecode::IntArgs sizes(x.size());
375 for (int i=0; i<x.size(); i++)
376 sizes[i] = weight;
377 Gecode::binpacking(home,loads,x,sizes);
378 }
379 };
380
382 class Create {
383 public:
385 Create(void) {
386 using namespace Gecode;
387
388 {
389 IntArgs s0({0,0,0,0});
390 IntArgs s1({2,1,1});
391 IntArgs s2({1,2,3,4});
392 IntArgs s3({4,3,2,1});
393 IntArgs s4({1,2,4,8});
394 IntArgs s5({1,1,1,1});
395 IntArgs s6({1,1,2,2});
396 IntArgs s7({1,3,3,4});
397 IntArgs s8({1,3,3,0,4,0});
398 IntArgs s9({1,2,4,8,16,32});
399
400 for (int m=1; m<4; m++) {
401 (void) new BPT(m, s0);
402 (void) new BPT(m, s1);
403 (void) new BPT(m, s2);
404 (void) new BPT(m, s3);
405 (void) new BPT(m, s4);
406 (void) new BPT(m, s5);
407 (void) new BPT(m, s6);
408 (void) new BPT(m, s7);
409 (void) new BPT(m, s8);
410 (void) new BPT(m, s9);
411 (void) new BPT(m, s1, false);
412 }
413 }
414
415 {
416 IntArgs s1({1,2, 2,1, 1,2, 2,1});
417 IntArgs c1({3,3});
418 (void) new MBPT(2, 4, s1, c1);
419 (void) new MBPT(2, 6, s1, c1);
420 IntArgs s2({1,1, 1,1, 1,1});
421 IntArgs c21({1,1});
422 IntArgs c22({2,2});
423 (void) new MBPT(2, 6, s2, c21);
424 (void) new MBPT(2, 6, s2, c22);
425 IntArgs s3({1,2,3, 3,2,1, 2,1,3, 1,3,2});
426 IntArgs c31({3,3,3});
427 IntArgs c32({4,4,4});
428 IntArgs c33({6,6,6});
429 (void) new MBPT(3, 4, s3, c31);
430 (void) new MBPT(3, 4, s3, c32);
431 (void) new MBPT(3, 4, s3, c33);
432 (void) new MBPT(3, 5, s3, c31);
433 (void) new MBPT(3, 5, s3, c32);
434 (void) new MBPT(3, 5, s3, c33);
435 }
436
437 {
438 IntArgs c1({0,2,4,6});
439 IntArgs c2({1,2,3,4,5,6,7,8});
440 IntArgs c3({1,3,7,10,15,22,27,97});
441 IntArgs c41({1,2,3,4,5,6,7,14});
442 IntArgs c42({1,2,3,4,5,6,7,15});
443 IntArgs c43({1,2,3,4,5,6,7,16});
444 IntArgs c44({1,2,3,4,5,6,7,30});
445 IntArgs c45({1,2,3,4,5,6,7,31});
446 IntArgs c46({1,2,3,4,5,6,7,32});
447 IntArgs c47({1,2,3,4,5,6,7,62});
448 IntArgs c48({1,2,3,4,5,6,7,63});
449 IntArgs c49({1,2,3,4,5,6,7,64});
450
451 (void) new CliqueMBPT(c1);
452 (void) new CliqueMBPT(c2);
453 (void) new CliqueMBPT(c3);
454 (void) new CliqueMBPT(c41);
455 (void) new CliqueMBPT(c42);
456 (void) new CliqueMBPT(c43);
457 (void) new CliqueMBPT(c44);
458 (void) new CliqueMBPT(c45);
459 (void) new CliqueMBPT(c46);
460 (void) new CliqueMBPT(c47);
461 (void) new CliqueMBPT(c48);
462 (void) new CliqueMBPT(c49);
463 }
464
465 (void) new PropagationLevels;
470 (void) new DFFLargeWeights(2,1100000000,1000000000);
471 }
472 };
473
475
477
478 }
479
480}}
481
482
483// STATISTICS: test-int
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
Passing integer arguments.
Definition int.hh:653
Value iterator for integer sets.
Definition int.hh:352
Integer sets.
Definition int.hh:179
bool in(int n) const
Return whether n is included in the set.
unsigned int size(void) const
Return size (cardinality) of set.
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Integer variables.
Definition int.hh:390
Computation spaces.
Definition core.hpp:1787
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
Base(std::string s)
Create and register a standard test with name s.
Definition test.cpp:125
static std::string str(bool b)
Map bool to string.
Definition test.hpp:121
Base class for assignments
Definition int.hh:73
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
int size(void) const
Return number of variables.
Definition int.hpp:46
Test with different bin loads and items
static int total(const Gecode::IntArgs &s)
Compute total size.
virtual Assignment * assignment(void) const
Create assignment.
virtual bool solution(const Assignment &x) const
Test whether x is solution
BPT(int m0, const Gecode::IntArgs &s0, bool v=true)
Create and register test for m bins and item sizes s.
Gecode::IntArgs s
Item sizes.
int il[8]
Array of sufficient size for computing item loads.
bool valid
Whether to generate only valid loads.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
int t
Total item sizes.
virtual Gecode::Space * copy(void)
Copying member function.
Test for testing the max-clique finding for multi bin-packing.
CliqueMBPT(const Gecode::IntArgs &c)
Test for number of items n expected clique c.
Gecode::IntArgs clique
Expected clique.
virtual bool run(void)
Run the actual test.
Help class to create and register tests.
Create(void)
Perform creation and registration.
Large weights must preserve every feasible bin assignment.
virtual bool solution(const Assignment &x) const
Check for solution.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Generate load and bin assignments.
virtual ~LoadBinAssignment(void)
Destructor.
Gecode::IntSet d_bin
Domain for bin variables.
Gecode::IntSetValues * dsv
Iterator for each variable.
LoadBinAssignment(int m, const Gecode::IntSet &d_m, int n, const Gecode::IntSet &d_n, int l)
Initialize assignments for load and bin variables.
int load
Load to generate (unless -1).
virtual bool has_more(void) const
Test whether all assignments have been iterated.
Gecode::IntSet d_load
Domain for load variables.
virtual int operator[](int i) const
Return value for variable i.
virtual void next(Gecode::Support::RandomGenerator &)
Move to next assignment.
Test with different bin loads and items
MBPT(int d0, int m0, const Gecode::IntArgs &s0, const Gecode::IntArgs &c0)
Create and register test for d0 dimensions, m0 bins, item sizes s0, and capacities c0.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Gecode::IntArgs c
Bin capacities.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Gecode::IntArgs s
Item sizes.
int il[4][8]
Array of sufficient size for computing item loads.
virtual Gecode::Space * copy(void)
Copying member function.
Test the bin-packing propagation levels.
bool check_case(int n_bins, int capacity, const Gecode::IntArgs &sizes, const bool expected_failed[4]) const
Check one propagation-level test case.
virtual bool run(void)
Run the actual test.
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
const int capacity[n_warehouses]
Capacity of a single warehouse.
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel ipl=IPL_DEF)
Post propagator for bin packing.
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_BASIC
Use basic propagation algorithm.
Definition int.hh:1281
@ IPL_FULL
Use full propagation.
Definition int.hh:1284
@ IPL_ADVANCED
Use advanced propagation algorithm.
Definition int.hh:1282
@ IPL_DEF
Simple propagation levels.
Definition int.hh:1276
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_FAILED
Space is failed
Definition core.hpp:1727
const int max
Largest allowed integer value.
Definition int.hh:121
Gecode toplevel namespace
Tests for bin-packing constraint
Testing finite domain integers.
Definition int.cpp:41
General test support.
Definition afc.cpp:41