Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

bin-packing.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2010
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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         // Try to generate next bin assignment
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         // Try to generate next load assignment
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         // Compute plausible bin sizes
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         // Loads are from 0 to m-1, after that are items
00163         // Check whether loads sum up to total size
00164         int l=0;
00165         for (int j=m; j--; )
00166           l += x[j];
00167         if (l != t)
00168           return false;
00169         // Check whether items are at possible bins
00170         for (int j=m; j--; )
00171           if ((x[m+j] < 0) || (x[m+j] >= m))
00172             return false;
00173         // Compute whether items add up
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         // x are the bin variables
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         // Constructor
00255         TestSpace(void) {}
00256         // Copy function
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          * Set up a multi-dimensional bin packing problems of dimension 2
00271          * where the item sizes in one dimension are all one but for some
00272          * random items and two in the other dimension if the item is
00273          * included in the clique  and where the capacity in both dimensions
00274          * is 3.
00275          */
00276         // Number of items
00277         int n_items = clique[clique.size()-1] + 1;
00278         // Capacity
00279         IntArgs c({3,3});
00280         // Item sizes
00281         IntArgs s(2*n_items);
00282         for (int i=2*n_items; i--; )
00283           s[i]=1;
00284         // Create some random conflicts
00285         for (int i=clique.size()-1; i--; )
00286           s[rand(n_items)*2+0]=2;
00287         // Create conflicts corresponding to the clique
00288         for (int i=clique.size(); i--; )
00289           s[clique[i]*2+1]=2;
00290         // Load and bin variables
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({0,0,0,0});
00321           IntArgs s1({2,1,1});
00322           IntArgs s2({1,2,3,4});
00323           IntArgs s3({4,3,2,1});
00324           IntArgs s4({1,2,4,8});
00325           IntArgs s5({1,1,1,1});
00326           IntArgs s6({1,1,2,2});
00327           IntArgs s7({1,3,3,4});
00328           IntArgs s8({1,3,3,0,4,0});
00329           IntArgs s9({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({1,2, 2,1, 1,2, 2,1});
00348           IntArgs c1({3,3});
00349           (void) new MBPT(2, 4, s1, c1);
00350           (void) new MBPT(2, 6, s1, c1);
00351           IntArgs s2({1,1, 1,1, 1,1});
00352           IntArgs c21({1,1});
00353           IntArgs c22({2,2});
00354           (void) new MBPT(2, 6, s2, c21);
00355           (void) new MBPT(2, 6, s2, c22);
00356           IntArgs s3({1,2,3, 3,2,1, 2,1,3, 1,3,2});
00357           IntArgs c31({3,3,3});
00358           IntArgs c32({4,4,4});
00359           IntArgs c33({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({0,2,4,6});
00370           IntArgs c2({1,2,3,4,5,6,7,8});
00371           IntArgs c3({1,3,7,10,15,22,27,97});
00372           IntArgs c41({1,2,3,4,5,6,7,14});
00373           IntArgs c42({1,2,3,4,5,6,7,15});
00374           IntArgs c43({1,2,3,4,5,6,7,16});
00375           IntArgs c44({1,2,3,4,5,6,7,30});
00376           IntArgs c45({1,2,3,4,5,6,7,31});
00377           IntArgs c46({1,2,3,4,5,6,7,32});
00378           IntArgs c47({1,2,3,4,5,6,7,62});
00379           IntArgs c48({1,2,3,4,5,6,7,63});
00380           IntArgs c49({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 // STATISTICS: test-int
00408