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 <gecode/int/bin-packing.hh>
00035
00036 namespace Gecode { namespace Int { namespace BinPacking {
00037
00038
00039
00040
00041
00042
00043 PropCost
00044 Pack::cost(const Space&, const ModEventDelta&) const {
00045 return PropCost::quadratic(PropCost::HI,bs.size());
00046 }
00047
00048 void
00049 Pack::reschedule(Space& home) {
00050 l.reschedule(home,*this,PC_INT_BND);
00051 bs.reschedule(home,*this,PC_INT_DOM);
00052 }
00053
00054 Actor*
00055 Pack::copy(Space& home) {
00056 return new (home) Pack(home,*this);
00057 }
00058
00060 class TellCache {
00061 protected:
00063 int* _nq;
00065 int _n_nq;
00067 int _eq;
00068 public:
00070 TellCache(Region& region, int m);
00072 void nq(int j);
00074 void eq(int j);
00076 ExecStatus tell(Space& home, IntView x);
00077 };
00078
00079 forceinline
00080 TellCache::TellCache(Region& region, int m)
00081 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
00082 forceinline void
00083 TellCache::nq(int j) {
00084 _nq[_n_nq++] = j;
00085 }
00086 forceinline void
00087 TellCache::eq(int j) {
00088
00089 if (_eq == -1)
00090 _eq = j;
00091 else
00092 _eq = -2;
00093 }
00094 ExecStatus
00095 TellCache::tell(Space& home, IntView x) {
00096 if (_eq == -2) {
00097 return ES_FAILED;
00098 } else if (_eq >= 0) {
00099 GECODE_ME_CHECK(x.eq(home,_eq));
00100 }
00101 Iter::Values::Array nqi(_nq, _n_nq);
00102 GECODE_ME_CHECK(x.minus_v(home, nqi));
00103 _n_nq=0; _eq=-1;
00104 return ES_OK;
00105 }
00106
00107
00108
00109
00110
00111
00112 ExecStatus
00113 Pack::propagate(Space& home, const ModEventDelta& med) {
00114
00115 int n = bs.size();
00116
00117 int m = l.size();
00118
00119 Region region;
00120 {
00121
00122
00123 int* s = region.alloc<int>(m);
00124
00125 for (int j=0; j<m; j++)
00126 s[j] = 0;
00127
00128
00129 if (OffsetView::me(med) == ME_INT_VAL) {
00130
00131 int k=0;
00132 for (int i=0; i<n; i++)
00133 if (bs[i].assigned()) {
00134 int j = bs[i].bin().val();
00135 l[j].offset(l[j].offset() - bs[i].size());
00136 t -= bs[i].size();
00137 } else {
00138 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00139 s[j.val()] += bs[i].size();
00140 bs[k++] = bs[i];
00141 }
00142 n=k; bs.size(n);
00143 } else {
00144 for (int i=0; i<n; i++) {
00145 assert(!bs[i].assigned());
00146 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00147 s[j.val()] += bs[i].size();
00148 }
00149 }
00150
00151
00152 int min = t, max = t;
00153 for (int j=0; j<m; j++) {
00154 GECODE_ME_CHECK(l[j].gq(home,0));
00155 GECODE_ME_CHECK(l[j].lq(home,s[j]));
00156 min -= l[j].max(); max -= l[j].min();
00157 }
00158
00159
00160 for (bool mod = true; mod; ) {
00161 mod = false; ModEvent me;
00162 for (int j=0; j<m; j++) {
00163 int lj_min = l[j].min();
00164 me = l[j].gq(home, min + l[j].max());
00165 if (me_failed(me))
00166 return ES_FAILED;
00167 if (me_modified(me)) {
00168 max += lj_min - l[j].min(); mod = true;
00169 }
00170 int lj_max = l[j].max();
00171 me = l[j].lq(home, max + l[j].min());
00172 if (me_failed(me))
00173 return ES_FAILED;
00174 if (me_modified(me)) {
00175 min += lj_max - l[j].max(); mod = true;
00176 }
00177 }
00178 }
00179
00180 if (n == 0) {
00181 assert(l.assigned());
00182 return home.ES_SUBSUMED(*this);
00183 }
00184
00185
00186 {
00187 TellCache tc(region,m);
00188
00189 int k=0;
00190 for (int i=0; i<n; i++) {
00191 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
00192 if (bs[i].size() > l[j.val()].max())
00193 tc.nq(j.val());
00194 if (s[j.val()] - bs[i].size() < l[j.val()].min())
00195 tc.eq(j.val());
00196 }
00197 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
00198
00199 if (bs[i].assigned()) {
00200 int j = bs[i].bin().val();
00201 l[j].offset(l[j].offset() - bs[i].size());
00202 t -= bs[i].size();
00203 } else {
00204 bs[k++] = bs[i];
00205 }
00206 }
00207 n=k; bs.size(n);
00208 }
00209 region.free();
00210 }
00211
00212
00213
00214 if (IntView::me(modeventdelta()) != ME_INT_NONE)
00215 return ES_NOFIX;
00216
00217
00218 {
00219
00220
00221 SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
00222
00223 for (int j=0; j<m; j++)
00224 s[j] = SizeSetMinusOne(region,n);
00225
00226
00227 for (int i=0; i<n; i++) {
00228 assert(!bs[i].assigned());
00229 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
00230 s[j.val()].add(bs[i].size());
00231 }
00232
00233 for (int j=0; j<m; j++) {
00234
00235 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
00236 return ES_FAILED;
00237 int ap, bp;
00238
00239 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(),
00240 ap, bp))
00241 GECODE_ME_CHECK(l[j].gq(home,bp));
00242
00243 if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(),
00244 ap, bp))
00245 GECODE_ME_CHECK(l[j].lq(home,ap));
00246 }
00247
00248 TellCache tc(region,m);
00249
00250 int k=0;
00251 for (int i=0; i<n; i++) {
00252 assert(!bs[i].assigned());
00253 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
00254
00255 s[j.val()].minus(bs[i].size());
00256
00257 if (nosum(s[j.val()],
00258 l[j.val()].min() - bs[i].size(),
00259 l[j.val()].max() - bs[i].size()))
00260 tc.nq(j.val());
00261
00262 if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max()))
00263 tc.eq(j.val());
00264 }
00265 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
00266 if (bs[i].assigned()) {
00267 int j = bs[i].bin().val();
00268 l[j].offset(l[j].offset() - bs[i].size());
00269 t -= bs[i].size();
00270 } else {
00271 bs[k++] = bs[i];
00272 }
00273 }
00274 n=k; bs.size(n);
00275 region.free();
00276 }
00277
00278
00279 if (n > 0) {
00280
00281
00282
00283 int c = bs[0].size();
00284 for (int j=0; j<m; j++)
00285 c = std::max(c,l[j].max());
00286
00287
00288 int* n_s = region.alloc<int>(c+1);
00289
00290 for (int i=0; i<c+1; i++)
00291 n_s[i] = 0;
00292
00293
00294 for (int i=0; i<n; i++)
00295 n_s[bs[i].size()]++;
00296
00297
00298 int nm = n;
00299
00300
00301 for (int j=0; j<m; j++)
00302 if (l[j].max() < 0) {
00303 return ES_FAILED;
00304 } else if (c > l[j].max()) {
00305 n_s[c - l[j].max()]++; nm++;
00306 }
00307
00308
00309 int* s = region.alloc<int>(nm);
00310
00311
00312 {
00313 int k=0;
00314 for (int i=c+1; i--; )
00315 for (int j=n_s[i]; j--; )
00316 s[k++]=i;
00317 assert(k == nm);
00318 }
00319
00320
00321 int n1 = 0;
00322
00323 int n12 = 0;
00324
00325 int n3 = 0;
00326
00327 int f2 = 0;
00328
00329 int s3 = 0;
00330
00331
00332 for (; (n12 < nm) && (s[n12] > c/2); n12++)
00333 f2 += c - s[n12];
00334
00335
00336 for (n3 = n12; n3 < nm; n3++)
00337 s3 += s[n3];
00338
00339
00340 for (int k=0; k<=c/2; k++) {
00341
00342 for (; (n1 < nm) && (s[n1] > c-k); n1++)
00343 f2 -= c - s[n1];
00344 assert(n1 <= n12);
00345
00346 for (; (s[n3-1] < k) && (n3 > n12); n3--)
00347 s3 -= s[n3-1];
00348
00349 int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0;
00350 if (n12 + o > m)
00351 return ES_FAILED;
00352 }
00353 region.free();
00354 }
00355
00356 return ES_NOFIX;
00357 }
00358
00359 ExecStatus
00360 Pack::post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs) {
00361
00362 Support::quicksort(&bs[0], bs.size());
00363
00364 int s = 0;
00365
00366 for (int i=0; i<bs.size(); i++) {
00367 s += bs[i].size();
00368 GECODE_ME_CHECK(bs[i].bin().gq(home,0));
00369 GECODE_ME_CHECK(bs[i].bin().le(home,l.size()));
00370 }
00371
00372 {
00373 int n = bs.size();
00374 while ((n > 0) && (bs[n-1].size() == 0))
00375 n--;
00376 bs.size(n);
00377 }
00378 if (bs.size() == 0) {
00379
00380 for (int i=0; i<l.size(); i++)
00381 GECODE_ME_CHECK(l[i].eq(home,0));
00382 return ES_OK;
00383 } else if (l.size() == 0) {
00384
00385 return ES_FAILED;
00386 } else {
00387
00388 for (int j=0; j<l.size(); j++) {
00389 GECODE_ME_CHECK(l[j].gq(home,0));
00390 GECODE_ME_CHECK(l[j].lq(home,s));
00391 }
00392 (void) new (home) Pack(home,l,bs);
00393 return ES_OK;
00394 }
00395 }
00396
00397 }}}
00398
00399
00400