Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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 
39 namespace Test { namespace Int {
40 
42  namespace BinPacking {
43 
50  class LoadBinAssignment : public Assignment {
51  protected:
53  int n_bins;
55  int n_items;
61  int load;
64  public:
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  }
78  virtual bool operator()(void) const {
79  return dsv[0]();
80  }
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  }
114  virtual int operator[](int i) const {
115  assert((i>=0) && (i<n_bins+n_items));
116  return dsv[i].val();
117  }
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  }
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  }
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  }
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  }
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  }
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:
248  int n_items;
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) {}
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 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Example: Bin packing
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Passing integer arguments.
Definition: int.hh:628
Value iterator for integer sets.
Definition: int.hh:333
void init(const IntSet &s)
Initialize with values for s.
Definition: int-set-1.hpp:285
Integer sets.
Definition: int.hh:174
bool in(int n) const
Return whether n is included in the set.
Definition: int-set-1.hpp:177
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
Passing integer variables.
Definition: int.hh:656
Integer variable array.
Definition: int.hh:763
Integer variables.
Definition: int.hh:371
int val(void) const
Return current value.
Computation spaces.
Definition: core.hpp:1742
Base class for all tests to be run
Definition: test.hh:103
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition: test.hh:134
Base class for assignments
Definition: int.hh:59
int n
Number of variables.
Definition: int.hh:61
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 m
Number of bins.
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.
Definition: bin-packing.cpp:50
virtual ~LoadBinAssignment(void)
Destructor.
Gecode::IntSet d_bin
Domain for bin variables.
Definition: bin-packing.cpp:59
virtual void operator++(void)
Move to next assignment.
Definition: bin-packing.cpp:82
Gecode::IntSetValues * dsv
Iterator for each variable.
Definition: bin-packing.cpp:63
virtual bool operator()(void) const
Test whether all assignments have been iterated.
Definition: bin-packing.cpp:78
LoadBinAssignment(int m, const Gecode::IntSet &d_m, int n, const Gecode::IntSet &d_n, int l)
Initialize assignments for load and bin variables.
Definition: bin-packing.cpp:66
int load
Load to generate (unless -1)
Definition: bin-packing.cpp:61
Gecode::IntSet d_load
Domain for load variables.
Definition: bin-packing.cpp:57
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.
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)
Post propagator for bin packing.
Definition: bin-packing.cpp:41
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
const int max
Largest allowed integer value.
Definition: int.hh:116
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int v[7]
Definition: distinct.cpp:259
General test support.
Definition: afc.cpp:39