Generated on Tue Mar 5 2013 22:37:12 for Gecode by doxygen 1.8.3.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  * Last modified:
10  * $Date: 2010-10-07 08:20:35 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
11  * $Revision: 11468 $
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 
54  class LoadBinAssignment : public Assignment {
55  protected:
57  int n_bins;
59  int n_items;
65  int load;
68  public:
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[4];
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  // 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 Create {
198  public:
200  Create(void) {
201  using namespace Gecode;
202 
203  IntArgs s1(3, 2,1,1);
204  IntArgs s2(4, 1,2,3,4);
205  IntArgs s3(4, 4,3,2,1);
206  IntArgs s4(4, 1,2,4,8);
207  IntArgs s5(4, 1,1,1,1);
208  IntArgs s6(4, 1,1,2,2);
209  IntArgs s7(4, 1,3,3,4);
210  IntArgs s8(6, 1,2,4,8,16,32);
211 
212  for (int m=1; m<4; m++) {
213  (void) new BPT(m, s1);
214  (void) new BPT(m, s2);
215  (void) new BPT(m, s3);
216  (void) new BPT(m, s4);
217  (void) new BPT(m, s5);
218  (void) new BPT(m, s6);
219  (void) new BPT(m, s7);
220  (void) new BPT(m, s8);
221  (void) new BPT(m, s1, false);
222  }
223 
224  }
225  };
226 
228 
230 
231  }
232 
233 }}
234 
235 
236 // STATISTICS: test-int
237