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 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(bool share) {
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 (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 s1(3, 2,1,1);
00321 IntArgs s2(4, 1,2,3,4);
00322 IntArgs s3(4, 4,3,2,1);
00323 IntArgs s4(4, 1,2,4,8);
00324 IntArgs s5(4, 1,1,1,1);
00325 IntArgs s6(4, 1,1,2,2);
00326 IntArgs s7(4, 1,3,3,4);
00327 IntArgs s8(6, 1,3,3,0,4,0);
00328 IntArgs s9(6, 1,2,4,8,16,32);
00329
00330 for (int m=1; m<4; m++) {
00331 (void) new BPT(m, s1);
00332 (void) new BPT(m, s2);
00333 (void) new BPT(m, s3);
00334 (void) new BPT(m, s4);
00335 (void) new BPT(m, s5);
00336 (void) new BPT(m, s6);
00337 (void) new BPT(m, s7);
00338 (void) new BPT(m, s8);
00339 (void) new BPT(m, s9);
00340 (void) new BPT(m, s1, false);
00341 }
00342 }
00343
00344 {
00345 IntArgs s1(2*4, 1,2, 2,1, 1,2, 2,1);
00346 IntArgs c1(2, 3,3);
00347 (void) new MBPT(2, 4, s1, c1);
00348 (void) new MBPT(2, 6, s1, c1);
00349 IntArgs s2(2*3, 1,1, 1,1, 1,1);
00350 IntArgs c21(2, 1,1);
00351 IntArgs c22(2, 2,2);
00352 (void) new MBPT(2, 6, s2, c21);
00353 (void) new MBPT(2, 6, s2, c22);
00354 IntArgs s3(3*4, 1,2,3, 3,2,1, 2,1,3, 1,3,2);
00355 IntArgs c31(3, 3,3,3);
00356 IntArgs c32(3, 4,4,4);
00357 IntArgs c33(3, 6,6,6);
00358 (void) new MBPT(3, 4, s3, c31);
00359 (void) new MBPT(3, 4, s3, c32);
00360 (void) new MBPT(3, 4, s3, c33);
00361 (void) new MBPT(3, 5, s3, c31);
00362 (void) new MBPT(3, 5, s3, c32);
00363 (void) new MBPT(3, 5, s3, c33);
00364 }
00365
00366 {
00367 IntArgs c1(4, 0,2,4,6);
00368 IntArgs c2(8, 1,2,3,4,5,6,7,8);
00369 IntArgs c3(8, 1,3,7,10,15,22,27,97);
00370 IntArgs c41(8, 1,2,3,4,5,6,7,14);
00371 IntArgs c42(8, 1,2,3,4,5,6,7,15);
00372 IntArgs c43(8, 1,2,3,4,5,6,7,16);
00373 IntArgs c44(8, 1,2,3,4,5,6,7,30);
00374 IntArgs c45(8, 1,2,3,4,5,6,7,31);
00375 IntArgs c46(8, 1,2,3,4,5,6,7,32);
00376 IntArgs c47(8, 1,2,3,4,5,6,7,62);
00377 IntArgs c48(8, 1,2,3,4,5,6,7,63);
00378 IntArgs c49(8, 1,2,3,4,5,6,7,64);
00379
00380 (void) new CliqueMBPT(c1);
00381 (void) new CliqueMBPT(c2);
00382 (void) new CliqueMBPT(c3);
00383 (void) new CliqueMBPT(c41);
00384 (void) new CliqueMBPT(c42);
00385 (void) new CliqueMBPT(c43);
00386 (void) new CliqueMBPT(c44);
00387 (void) new CliqueMBPT(c45);
00388 (void) new CliqueMBPT(c46);
00389 (void) new CliqueMBPT(c47);
00390 (void) new CliqueMBPT(c48);
00391 (void) new CliqueMBPT(c49);
00392 }
00393 }
00394 };
00395
00396 Create c;
00397
00399
00400 }
00401
00402 }}
00403
00404
00405
00406