Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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.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
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 operator()(void) const {
79 return dsv[0]();
80 }
81
82 virtual void operator++(void) {
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 NULL;
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 Create {
314 public:
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
399
401
402 }
403
404}}
405
406
407// STATISTICS: test-int
408
Passing integer arguments.
Definition int.hh:634
Value iterator for integer sets.
Definition int.hh:333
Integer sets.
Definition int.hh:174
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:662
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
Computation spaces.
Definition core.hpp:1744
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition test.hh:134
Base(const std::string &s)
Create and register test with name s.
Definition test.cpp:59
Base class for assignments
Definition int.hh:59
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
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.
Generate load and bin assignments.
virtual ~LoadBinAssignment(void)
Destructor.
Gecode::IntSet d_bin
Domain for bin variables.
virtual void operator++(void)
Move to next assignment.
Gecode::IntSetValues * dsv
Iterator for each variable.
virtual bool operator()(void) const
Test whether all assignments have been iterated.
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)
Gecode::IntSet d_load
Domain for load variables.
virtual int operator[](int i) const
Return value for variable i.
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.
bool testsearch
Whether to perform search test.
Definition int.hh:238
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel ipl=IPL_DEF)
Post propagator for bin packing.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
@ SS_FAILED
Space is failed
Definition core.hpp:1684
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode toplevel namespace
Post propagator for SetVar x
Definition set.hh:773
Tests for bin-packing constraint
Testing finite domain integers.
Definition int.cpp:40
General test support.
Definition afc.cpp:39