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[4];
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 Create {
00198 public:
00200 Create(void) {
00201 using namespace Gecode;
00202
00203 IntArgs s1(3, 2,1,1);
00204 IntArgs s2(4, 1,2,3,4);
00205 IntArgs s3(4, 4,3,2,1);
00206 IntArgs s4(4, 1,2,4,8);
00207 IntArgs s5(4, 1,1,1,1);
00208 IntArgs s6(4, 1,1,2,2);
00209 IntArgs s7(4, 1,3,3,4);
00210 IntArgs s8(6, 1,2,4,8,16,32);
00211
00212 for (int m=1; m<4; m++) {
00213 (void) new BPT(m, s1);
00214 (void) new BPT(m, s2);
00215 (void) new BPT(m, s3);
00216 (void) new BPT(m, s4);
00217 (void) new BPT(m, s5);
00218 (void) new BPT(m, s6);
00219 (void) new BPT(m, s7);
00220 (void) new BPT(m, s8);
00221 (void) new BPT(m, s1, false);
00222 }
00223
00224 }
00225 };
00226
00227 Create c;
00228
00230
00231 }
00232
00233 }}
00234
00235
00236
00237