00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include "test/int.hh"
00035
00036 #include <gecode/minimodel.hh>
00037 #include <climits>
00038
00039 namespace Test { namespace Int {
00040
00042 namespace BinPacking {
00043
00049
00050 class LoadBinAssignment : public Assignment {
00051 protected:
00053 int n_bins;
00055 int n_items;
00057 Gecode::IntSet d_load;
00059 Gecode::IntSet d_bin;
00061 int load;
00063 Gecode::IntSetValues* dsv;
00064 public:
00066 LoadBinAssignment(int m, const Gecode::IntSet& d_m,
00067 int n, const Gecode::IntSet& d_n,
00068 int l)
00069 : Assignment(m+n,d_m),
00070 n_bins(m), n_items(n), d_load(d_m), d_bin(d_n), load(l),
00071 dsv(new Gecode::IntSetValues[static_cast<unsigned int>(m+n)]) {
00072 for (int i=n_bins; i--; )
00073 dsv[i].init(d_load);
00074 for (int i=n_items; i--; )
00075 dsv[n_bins+i].init(d_bin);
00076 }
00078 virtual bool operator()(void) const {
00079 return dsv[0]();
00080 }
00082 virtual void operator++(void) {
00083
00084 {
00085 int i = n_items-1;
00086 while (i >= 0) {
00087 ++dsv[n_bins+i];
00088 if (dsv[n_bins+i]())
00089 return;
00090 dsv[n_bins+(i--)].init(d_bin);
00091 }
00092 }
00093
00094 {
00095 retry:
00096 int i = n_bins-1;
00097 while (true) {
00098 ++dsv[i];
00099 if (dsv[i]() || (i == 0)) {
00100 if (dsv[i]() && (load >= 0)) {
00101 int l = 0;
00102 for (int k=0;k<n_bins; k++)
00103 l += dsv[k].val();
00104 if (load != l)
00105 goto retry;
00106 }
00107 return;
00108 }
00109 dsv[i--].init(d_load);
00110 }
00111 }
00112 }
00114 virtual int operator[](int i) const {
00115 assert((i>=0) && (i<n_bins+n_items));
00116 return dsv[i].val();
00117 }
00119 virtual ~LoadBinAssignment(void) {
00120 delete [] dsv;
00121 }
00122 };
00123
00125 class BPT : public Test {
00126 protected:
00128 int m;
00130 Gecode::IntArgs s;
00132 bool valid;
00134 int t;
00136 mutable int il[8];
00138 static int total(const Gecode::IntArgs& s) {
00139 int t = 0;
00140 for (int i=s.size(); i--; )
00141 t += s[i];
00142 return t;
00143 }
00144 public:
00146 BPT(int m0, const Gecode::IntArgs& s0, bool v=true)
00147 : Test("BinPacking::"+str(m0)+"::"+str(s0)+"::"+(v ? "+" : "-"),
00148 m0+s0.size(), 0, 100),
00149 m(m0), s(s0), valid(v), t(total(s)) {
00150 testsearch = false;
00151 }
00153 virtual Assignment* assignment(void) const {
00154
00155 int a = t / m;
00156 return new LoadBinAssignment(m,Gecode::IntSet(a-1,a+2),
00157 s.size(),Gecode::IntSet(0,m-1),
00158 valid ? t : -1);
00159 }
00161 virtual bool solution(const Assignment& x) const {
00162
00163
00164 int l=0;
00165 for (int j=m; j--; )
00166 l += x[j];
00167 if (l != t)
00168 return false;
00169
00170 for (int j=m; j--; )
00171 if ((x[m+j] < 0) || (x[m+j] >= m))
00172 return false;
00173
00174 for (int j=m; j--; )
00175 il[j] = 0;
00176 for (int i=s.size(); i--; )
00177 il[x[m+i]] += s[i];
00178 for (int j=m; j--; )
00179 if (il[j] != x[j])
00180 return false;
00181 return true;
00182 }
00184 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00185 using namespace Gecode;
00186 IntVarArgs l(m);
00187 IntVarArgs b(s.size());
00188 for (int j=m; j--; )
00189 l[j]=x[j];
00190 for (int i=s.size(); i--; )
00191 b[i]=x[m+i];
00192 binpacking(home, l, b, s);
00193 }
00194 };
00195
00197 class MBPT : public Test {
00198 protected:
00200 int d;
00202 int m;
00204 Gecode::IntArgs s;
00206 Gecode::IntArgs c;
00208 mutable int il[4][8];
00209 public:
00211 MBPT(int d0, int m0,
00212 const Gecode::IntArgs& s0, const Gecode::IntArgs& c0)
00213 : Test("MultiBinPacking::"+str(d0)+"::"+str(m0)+"::"+
00214 str(s0)+"::"+str(c0), s0.size() / d0, 0, m0-1),
00215 d(d0), m(m0), s(s0), c(c0) {
00216 testsearch = false;
00217 testfix = false;
00218 }
00220 virtual bool solution(const Assignment& x) const {
00221
00222 for (int k=d; k--; )
00223 for (int j=m; j--; )
00224 il[k][j] = 0;
00225 for (int k=d; k--; )
00226 for (int i=x.size(); i--; )
00227 il[k][x[i]] += s[i*d+k];
00228 for (int k=d; k--; )
00229 for (int j=m; j--; )
00230 if (il[k][j] > c[k])
00231 return false;
00232 return true;
00233 }
00235 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00236 using namespace Gecode;
00237 IntVarArgs l(d*m);
00238 for (int j=m*d; j--; )
00239 l[j]=IntVar(home, 0, Gecode::Int::Limits::max);
00240 binpacking(home, d, l, x, s, c);
00241 }
00242 };
00243
00245 class CliqueMBPT : public Base {
00246 protected:
00248 int n_items;
00250 Gecode::IntArgs clique;
00252 class TestSpace : public Gecode::Space {
00253 public:
00254
00255 TestSpace(void) {}
00256
00257 virtual Gecode::Space* copy(void) {
00258 return NULL;
00259 }
00260 };
00261 public:
00263 CliqueMBPT(const Gecode::IntArgs& c)
00264 : Base("Int::MultiBinPacking::Clique::"+Test::str(c)), clique(c) {}
00266 virtual bool run(void) {
00267 using namespace Gecode;
00268 TestSpace* home = new TestSpace;
00269
00270
00271
00272
00273
00274
00275
00276
00277 int n_items = clique[clique.size()-1] + 1;
00278
00279 IntArgs c(2, 3,3);
00280
00281 IntArgs s(2*n_items);
00282 for (int i=2*n_items; i--; )
00283 s[i]=1;
00284
00285 for (int i=clique.size()-1; i--; )
00286 s[rand(n_items)*2+0]=2;
00287
00288 for (int i=clique.size(); i--; )
00289 s[clique[i]*2+1]=2;
00290
00291 IntVarArgs b(*home, n_items, 0, n_items-1);
00292 IntVarArgs l(*home, 2*n_items, 0, 3);
00293 IntSet mc = binpacking(*home, 2, l, b, s, c);
00294 if (home->status() == SS_FAILED) {
00295 delete home;
00296 return false;
00297 }
00298 if (static_cast<unsigned int>(clique.size()) != mc.size()) {
00299 delete home;
00300 return false;
00301 }
00302 for (int i=clique.size(); i--; )
00303 if (!mc.in(clique[i])) {
00304 delete home;
00305 return false;
00306 }
00307 delete home;
00308 return true;
00309 }
00310 };
00311
00313 class Create {
00314 public:
00316 Create(void) {
00317 using namespace Gecode;
00318
00319 {
00320 IntArgs s0(4, 0,0,0,0);
00321 IntArgs s1(3, 2,1,1);
00322 IntArgs s2(4, 1,2,3,4);
00323 IntArgs s3(4, 4,3,2,1);
00324 IntArgs s4(4, 1,2,4,8);
00325 IntArgs s5(4, 1,1,1,1);
00326 IntArgs s6(4, 1,1,2,2);
00327 IntArgs s7(4, 1,3,3,4);
00328 IntArgs s8(6, 1,3,3,0,4,0);
00329 IntArgs s9(6, 1,2,4,8,16,32);
00330
00331 for (int m=1; m<4; m++) {
00332 (void) new BPT(m, s0);
00333 (void) new BPT(m, s1);
00334 (void) new BPT(m, s2);
00335 (void) new BPT(m, s3);
00336 (void) new BPT(m, s4);
00337 (void) new BPT(m, s5);
00338 (void) new BPT(m, s6);
00339 (void) new BPT(m, s7);
00340 (void) new BPT(m, s8);
00341 (void) new BPT(m, s9);
00342 (void) new BPT(m, s1, false);
00343 }
00344 }
00345
00346 {
00347 IntArgs s1(2*4, 1,2, 2,1, 1,2, 2,1);
00348 IntArgs c1(2, 3,3);
00349 (void) new MBPT(2, 4, s1, c1);
00350 (void) new MBPT(2, 6, s1, c1);
00351 IntArgs s2(2*3, 1,1, 1,1, 1,1);
00352 IntArgs c21(2, 1,1);
00353 IntArgs c22(2, 2,2);
00354 (void) new MBPT(2, 6, s2, c21);
00355 (void) new MBPT(2, 6, s2, c22);
00356 IntArgs s3(3*4, 1,2,3, 3,2,1, 2,1,3, 1,3,2);
00357 IntArgs c31(3, 3,3,3);
00358 IntArgs c32(3, 4,4,4);
00359 IntArgs c33(3, 6,6,6);
00360 (void) new MBPT(3, 4, s3, c31);
00361 (void) new MBPT(3, 4, s3, c32);
00362 (void) new MBPT(3, 4, s3, c33);
00363 (void) new MBPT(3, 5, s3, c31);
00364 (void) new MBPT(3, 5, s3, c32);
00365 (void) new MBPT(3, 5, s3, c33);
00366 }
00367
00368 {
00369 IntArgs c1(4, 0,2,4,6);
00370 IntArgs c2(8, 1,2,3,4,5,6,7,8);
00371 IntArgs c3(8, 1,3,7,10,15,22,27,97);
00372 IntArgs c41(8, 1,2,3,4,5,6,7,14);
00373 IntArgs c42(8, 1,2,3,4,5,6,7,15);
00374 IntArgs c43(8, 1,2,3,4,5,6,7,16);
00375 IntArgs c44(8, 1,2,3,4,5,6,7,30);
00376 IntArgs c45(8, 1,2,3,4,5,6,7,31);
00377 IntArgs c46(8, 1,2,3,4,5,6,7,32);
00378 IntArgs c47(8, 1,2,3,4,5,6,7,62);
00379 IntArgs c48(8, 1,2,3,4,5,6,7,63);
00380 IntArgs c49(8, 1,2,3,4,5,6,7,64);
00381
00382 (void) new CliqueMBPT(c1);
00383 (void) new CliqueMBPT(c2);
00384 (void) new CliqueMBPT(c3);
00385 (void) new CliqueMBPT(c41);
00386 (void) new CliqueMBPT(c42);
00387 (void) new CliqueMBPT(c43);
00388 (void) new CliqueMBPT(c44);
00389 (void) new CliqueMBPT(c45);
00390 (void) new CliqueMBPT(c46);
00391 (void) new CliqueMBPT(c47);
00392 (void) new CliqueMBPT(c48);
00393 (void) new CliqueMBPT(c49);
00394 }
00395 }
00396 };
00397
00398 Create c;
00399
00401
00402 }
00403
00404 }}
00405
00406
00407
00408