Generated on Thu Mar 16 2017 03:24:13 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date: 2016-06-17 15:43:08 +0200 (Fri, 17 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15116 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/int.hh"
39 
40 #include <gecode/minimodel.hh>
41 #include <climits>
42 
43 namespace Test { namespace Int {
44 
46  namespace BinPacking {
47 
53  class LoadBinAssignment : public Assignment {
55  protected:
57  int n_bins;
59  int n_items;
65  int load;
68  public:
70  LoadBinAssignment(int m, const Gecode::IntSet& d_m,
71  int n, const Gecode::IntSet& d_n,
72  int l)
73  : Assignment(m+n,d_m),
74  n_bins(m), n_items(n), d_load(d_m), d_bin(d_n), load(l),
75  dsv(new Gecode::IntSetValues[static_cast<unsigned int>(m+n)]) {
76  for (int i=n_bins; i--; )
77  dsv[i].init(d_load);
78  for (int i=n_items; i--; )
79  dsv[n_bins+i].init(d_bin);
80  }
82  virtual bool operator()(void) const {
83  return dsv[0]();
84  }
86  virtual void operator++(void) {
87  // Try to generate next bin assignment
88  {
89  int i = n_items-1;
90  while (i >= 0) {
91  ++dsv[n_bins+i];
92  if (dsv[n_bins+i]())
93  return;
94  dsv[n_bins+(i--)].init(d_bin);
95  }
96  }
97  // Try to generate next load assignment
98  {
99  retry:
100  int i = n_bins-1;
101  while (true) {
102  ++dsv[i];
103  if (dsv[i]() || (i == 0)) {
104  if (dsv[i]() && (load >= 0)) {
105  int l = 0;
106  for (int k=0;k<n_bins; k++)
107  l += dsv[k].val();
108  if (load != l)
109  goto retry;
110  }
111  return;
112  }
113  dsv[i--].init(d_load);
114  }
115  }
116  }
118  virtual int operator[](int i) const {
119  assert((i>=0) && (i<n_bins+n_items));
120  return dsv[i].val();
121  }
123  virtual ~LoadBinAssignment(void) {
124  delete [] dsv;
125  }
126  };
127 
129  class BPT : public Test {
130  protected:
132  int m;
136  bool valid;
138  int t;
140  mutable int il[8];
142  static int total(const Gecode::IntArgs& s) {
143  int t = 0;
144  for (int i=s.size(); i--; )
145  t += s[i];
146  return t;
147  }
148  public:
150  BPT(int m0, const Gecode::IntArgs& s0, bool v=true)
151  : Test("BinPacking::"+str(m0)+"::"+str(s0)+"::"+(v ? "+" : "-"),
152  m0+s0.size(), 0, 100),
153  m(m0), s(s0), valid(v), t(total(s)) {
154  testsearch = false;
155  }
157  virtual Assignment* assignment(void) const {
158  // Compute plausible bin sizes
159  int a = t / m;
160  return new LoadBinAssignment(m,Gecode::IntSet(a-1,a+2),
161  s.size(),Gecode::IntSet(0,m-1),
162  valid ? t : -1);
163  }
165  virtual bool solution(const Assignment& x) const {
166  // Loads are from 0 to m-1, after that are items
167  // Check whether loads sum up to total size
168  int l=0;
169  for (int j=m; j--; )
170  l += x[j];
171  if (l != t)
172  return false;
173  // Check whether items are at possible bins
174  for (int j=m; j--; )
175  if ((x[m+j] < 0) || (x[m+j] >= m))
176  return false;
177  // Compute whether items add up
178  for (int j=m; j--; )
179  il[j] = 0;
180  for (int i=s.size(); i--; )
181  il[x[m+i]] += s[i];
182  for (int j=m; j--; )
183  if (il[j] != x[j])
184  return false;
185  return true;
186  }
188  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
189  using namespace Gecode;
190  IntVarArgs l(m);
191  IntVarArgs b(s.size());
192  for (int j=m; j--; )
193  l[j]=x[j];
194  for (int i=s.size(); i--; )
195  b[i]=x[m+i];
196  binpacking(home, l, b, s);
197  }
198  };
199 
201  class MBPT : public Test {
202  protected:
204  int d;
206  int m;
212  mutable int il[4][8];
213  public:
215  MBPT(int d0, int m0,
216  const Gecode::IntArgs& s0, const Gecode::IntArgs& c0)
217  : Test("MultiBinPacking::"+str(d0)+"::"+str(m0)+"::"+
218  str(s0)+"::"+str(c0), s0.size() / d0, 0, m0-1),
219  d(d0), m(m0), s(s0), c(c0) {
220  testsearch = false;
221  testfix = false;
222  }
224  virtual bool solution(const Assignment& x) const {
225  // x are the bin variables
226  for (int k=d; k--; )
227  for (int j=m; j--; )
228  il[k][j] = 0;
229  for (int k=d; k--; )
230  for (int i=x.size(); i--; )
231  il[k][x[i]] += s[i*d+k];
232  for (int k=d; k--; )
233  for (int j=m; j--; )
234  if (il[k][j] > c[k])
235  return false;
236  return true;
237  }
239  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
240  using namespace Gecode;
241  IntVarArgs l(d*m);
242  for (int j=m*d; j--; )
243  l[j]=IntVar(home, 0, Gecode::Int::Limits::max);
244  binpacking(home, d, l, x, s, c);
245  }
246  };
247 
249  class CliqueMBPT : public Base {
250  protected:
252  int n_items;
256  class TestSpace : public Gecode::Space {
257  public:
258  // Constructor
259  TestSpace(void) {}
260  // Copy function
261  virtual Gecode::Space* copy(bool) {
262  return NULL;
263  }
264  };
265  public:
268  : Base("Int::MultiBinPacking::Clique::"+Test::str(c)), clique(c) {}
270  virtual bool run(void) {
271  using namespace Gecode;
272  TestSpace* home = new TestSpace;
273  /*
274  * Set up a multi-dimensional bin packing problems of dimension 2
275  * where the item sizes in one dimension are all one but for some
276  * random items and two in the other dimension if the item is
277  * included in the clique and where the capacity in both dimensions
278  * is 3.
279  */
280  // Number of items
281  int n_items = clique[clique.size()-1] + 1;
282  // Capacity
283  IntArgs c(2, 3,3);
284  // Item sizes
285  IntArgs s(2*n_items);
286  for (int i=2*n_items; i--; )
287  s[i]=1;
288  // Create some random conflicts
289  for (int i=clique.size()-1; i--; )
290  s[rand(n_items)*2+0]=2;
291  // Create conflicts corresponding to the clique
292  for (int i=clique.size(); i--; )
293  s[clique[i]*2+1]=2;
294  // Load and bin variables
295  IntVarArgs b(*home, n_items, 0, n_items-1);
296  IntVarArgs l(*home, 2*n_items, 0, 3);
297  IntSet mc = binpacking(*home, 2, l, b, s, c);
298  if (home->status() == SS_FAILED) {
299  delete home;
300  return false;
301  }
302  if (clique.size() != mc.size()) {
303  delete home;
304  return false;
305  }
306  for (int i=clique.size(); i--; )
307  if (!mc.in(clique[i])) {
308  delete home;
309  return false;
310  }
311  delete home;
312  return true;
313  }
314  };
315 
317  class Create {
318  public:
320  Create(void) {
321  using namespace Gecode;
322 
323  {
324  IntArgs s0(4, 0,0,0,0);
325  IntArgs s1(3, 2,1,1);
326  IntArgs s2(4, 1,2,3,4);
327  IntArgs s3(4, 4,3,2,1);
328  IntArgs s4(4, 1,2,4,8);
329  IntArgs s5(4, 1,1,1,1);
330  IntArgs s6(4, 1,1,2,2);
331  IntArgs s7(4, 1,3,3,4);
332  IntArgs s8(6, 1,3,3,0,4,0);
333  IntArgs s9(6, 1,2,4,8,16,32);
334 
335  for (int m=1; m<4; m++) {
336  (void) new BPT(m, s0);
337  (void) new BPT(m, s1);
338  (void) new BPT(m, s2);
339  (void) new BPT(m, s3);
340  (void) new BPT(m, s4);
341  (void) new BPT(m, s5);
342  (void) new BPT(m, s6);
343  (void) new BPT(m, s7);
344  (void) new BPT(m, s8);
345  (void) new BPT(m, s9);
346  (void) new BPT(m, s1, false);
347  }
348  }
349 
350  {
351  IntArgs s1(2*4, 1,2, 2,1, 1,2, 2,1);
352  IntArgs c1(2, 3,3);
353  (void) new MBPT(2, 4, s1, c1);
354  (void) new MBPT(2, 6, s1, c1);
355  IntArgs s2(2*3, 1,1, 1,1, 1,1);
356  IntArgs c21(2, 1,1);
357  IntArgs c22(2, 2,2);
358  (void) new MBPT(2, 6, s2, c21);
359  (void) new MBPT(2, 6, s2, c22);
360  IntArgs s3(3*4, 1,2,3, 3,2,1, 2,1,3, 1,3,2);
361  IntArgs c31(3, 3,3,3);
362  IntArgs c32(3, 4,4,4);
363  IntArgs c33(3, 6,6,6);
364  (void) new MBPT(3, 4, s3, c31);
365  (void) new MBPT(3, 4, s3, c32);
366  (void) new MBPT(3, 4, s3, c33);
367  (void) new MBPT(3, 5, s3, c31);
368  (void) new MBPT(3, 5, s3, c32);
369  (void) new MBPT(3, 5, s3, c33);
370  }
371 
372  {
373  IntArgs c1(4, 0,2,4,6);
374  IntArgs c2(8, 1,2,3,4,5,6,7,8);
375  IntArgs c3(8, 1,3,7,10,15,22,27,97);
376  IntArgs c41(8, 1,2,3,4,5,6,7,14);
377  IntArgs c42(8, 1,2,3,4,5,6,7,15);
378  IntArgs c43(8, 1,2,3,4,5,6,7,16);
379  IntArgs c44(8, 1,2,3,4,5,6,7,30);
380  IntArgs c45(8, 1,2,3,4,5,6,7,31);
381  IntArgs c46(8, 1,2,3,4,5,6,7,32);
382  IntArgs c47(8, 1,2,3,4,5,6,7,62);
383  IntArgs c48(8, 1,2,3,4,5,6,7,63);
384  IntArgs c49(8, 1,2,3,4,5,6,7,64);
385 
386  (void) new CliqueMBPT(c1);
387  (void) new CliqueMBPT(c2);
388  (void) new CliqueMBPT(c3);
389  (void) new CliqueMBPT(c41);
390  (void) new CliqueMBPT(c42);
391  (void) new CliqueMBPT(c43);
392  (void) new CliqueMBPT(c44);
393  (void) new CliqueMBPT(c45);
394  (void) new CliqueMBPT(c46);
395  (void) new CliqueMBPT(c47);
396  (void) new CliqueMBPT(c48);
397  (void) new CliqueMBPT(c49);
398  }
399  }
400  };
401 
403 
405 
406  }
407 
408 }}
409 
410 
411 // STATISTICS: test-int
412 
int m
Number of bins.
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
NodeType t
Type of node.
Definition: bool-expr.cpp:234
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
IntSet binpacking(Home home, int d, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, const IntArgs &c, IntPropLevel)
Definition: bin-packing.cpp:70
int size(void) const
Return number of variables.
Definition: int.hpp:50
int t
Total item sizes.
Create(void)
Perform creation and registration.
int m
Number of bins.
void init(const IntSet &s)
Initialize with values for s.
Definition: int-set-1.hpp:229
Gecode::IntArgs s
Item sizes.
Gecode::IntArgs c
Bin capacities.
bool valid
Whether to generate only valid loads.
Integer variable array.
Definition: int.hh:742
virtual ~LoadBinAssignment(void)
Destructor.
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...
Gecode::IntSet d_bin
Domain for bin variables.
Definition: bin-packing.cpp:63
const int max
Largest allowed integer value.
Definition: int.hh:114
static int total(const Gecode::IntArgs &s)
Compute total size.
Computation spaces.
Definition: core.hpp:1672
virtual void operator++(void)
Move to next assignment.
Definition: bin-packing.cpp:86
int val(void) const
Return current value.
int n
Number of variables.
Definition: int.hh:65
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
Test with different bin loads and items
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::IntArgs clique
Expected clique.
Help class to create and register tests.
Gecode::IntSetValues * dsv
Iterator for each variable.
Definition: bin-packing.cpp:67
virtual int operator[](int i) const
Return value for variable i.
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
Base class for all tests to be run
Definition: test.hh:107
Integer sets.
Definition: int.hh:172
virtual Assignment * assignment(void) const
Create assignment.
virtual bool solution(const Assignment &x) const
Test whether x is solution
CliqueMBPT(const Gecode::IntArgs &c)
Test for number of items n expected clique c.
Passing integer variables.
Definition: int.hh:637
Passing integer arguments.
Definition: int.hh:608
Generate load and bin assignments.
Definition: bin-packing.cpp:54
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
const int v[7]
Definition: distinct.cpp:263
General test support.
Definition: afc.cpp:43
Example: Bin packing
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Test with different bin loads and items
Gecode::IntSet d_load
Domain for load variables.
Definition: bin-packing.cpp:61
Base class for assignments
Definition: int.hh:63
Integer variables.
Definition: int.hh:351
virtual Gecode::Space * copy(bool)
Copying member function.
Value iterator for integer sets.
Definition: int.hh:313
Test for testing the max-clique finding for multi bin-packing.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:234
Gecode toplevel namespace
BPT(int m0, const Gecode::IntArgs &s0, bool v=true)
Create and register test for m bins and item sizes s.
virtual bool run(void)
Run the actual test.
bool in(int n) const
Return whether n is included in the set.
Definition: int-set-1.hpp:140
Gecode::IntArgs s
Item sizes.
virtual bool solution(const Assignment &x) const
Test whether x is solution
Space is failed
Definition: core.hpp:1611
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
virtual bool operator()(void) const
Test whether all assignments have been iterated.
Definition: bin-packing.cpp:82
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:70
int load
Load to generate (unless -1)
Definition: bin-packing.cpp:65