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