propagate.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 * Last modified: 00010 * $Date: 2010-10-06 23:20:35 +0200 (Wed, 06 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11468 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/int/bin-packing.hh> 00039 00040 namespace Gecode { namespace Int { namespace BinPacking { 00041 00042 /* 00043 * Packing propagator 00044 * 00045 */ 00046 00047 PropCost 00048 Pack::cost(const Space&, const ModEventDelta&) const { 00049 return PropCost::quadratic(PropCost::HI,bs.size()); 00050 } 00051 00052 Actor* 00053 Pack::copy(Space& home, bool share) { 00054 return new (home) Pack(home,share,*this); 00055 } 00056 00058 class TellCache { 00059 protected: 00061 int* _nq; 00063 int _n_nq; 00065 int _eq; 00066 public: 00068 TellCache(Region& region, int m); 00070 void nq(int j); 00072 void eq(int j); 00074 ExecStatus tell(Space& home, IntView x); 00075 }; 00076 00077 forceinline 00078 TellCache::TellCache(Region& region, int m) 00079 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {} 00080 forceinline void 00081 TellCache::nq(int j) { 00082 _nq[_n_nq++] = j; 00083 } 00084 forceinline void 00085 TellCache::eq(int j) { 00086 // For eq: -1 mean not yet assigned, -2 means failure, positive means value 00087 if (_eq == -1) 00088 _eq = j; 00089 else 00090 _eq = -2; 00091 } 00092 ExecStatus 00093 TellCache::tell(Space& home, IntView x) { 00094 if (_eq == -2) { 00095 return ES_FAILED; 00096 } else if (_eq >= 0) { 00097 GECODE_ME_CHECK(x.eq(home,_eq)); 00098 } 00099 Iter::Values::Array nqi(_nq, _n_nq); 00100 GECODE_ME_CHECK(x.minus_v(home, nqi)); 00101 _n_nq=0; _eq=-1; 00102 return ES_OK; 00103 } 00104 00105 00106 /* 00107 * Propagation proper 00108 * 00109 */ 00110 ExecStatus 00111 Pack::propagate(Space& home, const ModEventDelta& med) { 00112 // Number of items 00113 int n = bs.size(); 00114 // Number of bins 00115 int m = l.size(); 00116 00117 { 00118 Region region(home); 00119 00120 // Possible sizes for bins 00121 int* s = region.alloc<int>(m); 00122 00123 for (int j=m; j--; ) 00124 s[j] = 0; 00125 00126 // Compute sizes for bins 00127 if (OffsetView::me(med) == ME_INT_VAL) { 00128 // Also eliminate assigned items 00129 int k=0; 00130 for (int i=0; i<n; i++) 00131 if (bs[i].assigned()) { 00132 int j = bs[i].bin().val(); 00133 l[j].offset(l[j].offset() - bs[i].size()); 00134 t -= bs[i].size(); 00135 } else { 00136 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) 00137 s[j.val()] += bs[i].size(); 00138 bs[k++] = bs[i]; 00139 } 00140 n=k; bs.size(n); 00141 } else { 00142 for (int i=n; i--; ) { 00143 assert(!bs[i].assigned()); 00144 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) 00145 s[j.val()] += bs[i].size(); 00146 } 00147 } 00148 00149 // Propagate bin loads and compute lower and upper bound 00150 int min = t, max = t; 00151 for (int j=m; j--; ) { 00152 GECODE_ME_CHECK(l[j].gq(home,0)); 00153 GECODE_ME_CHECK(l[j].lq(home,s[j])); 00154 min -= l[j].max(); max -= l[j].min(); 00155 } 00156 00157 // Propagate that load must be equal to total size 00158 for (bool mod = true; mod; ) { 00159 mod = false; ModEvent me; 00160 for (int j=m; j--; ) { 00161 int lj_min = l[j].min(); 00162 me = l[j].gq(home, min + l[j].max()); 00163 if (me_failed(me)) 00164 return ES_FAILED; 00165 if (me_modified(me)) { 00166 max += lj_min - l[j].min(); mod = true; 00167 } 00168 int lj_max = l[j].max(); 00169 me = l[j].lq(home, max + l[j].min()); 00170 if (me_failed(me)) 00171 return ES_FAILED; 00172 if (me_modified(me)) { 00173 min += lj_max - l[j].max(); mod = true; 00174 } 00175 } 00176 } 00177 00178 if (n == 0) { 00179 assert(l.assigned()); 00180 return home.ES_SUBSUMED(*this); 00181 } 00182 00183 00184 { 00185 TellCache tc(region,m); 00186 00187 int k=0; 00188 for (int i=0; i<n; i++) { 00189 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) { 00190 if (bs[i].size() > l[j.val()].max()) 00191 tc.nq(j.val()); 00192 if (s[j.val()] - bs[i].size() < l[j.val()].min()) 00193 tc.eq(j.val()); 00194 } 00195 GECODE_ES_CHECK(tc.tell(home,bs[i].bin())); 00196 // Eliminate assigned bin 00197 if (bs[i].assigned()) { 00198 int j = bs[i].bin().val(); 00199 l[j].offset(l[j].offset() - bs[i].size()); 00200 t -= bs[i].size(); 00201 } else { 00202 bs[k++] = bs[i]; 00203 } 00204 } 00205 n=k; bs.size(n); 00206 } 00207 00208 } 00209 00210 // Now the invariant holds that no more assigned bins exist! 00211 { 00212 Region region(home); 00213 00214 // Size of items 00215 SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m); 00216 00217 for (int j=m; j--; ) 00218 s[j] = SizeSetMinusOne(region,n); 00219 00220 // Set up size information 00221 for (int i=0; i<n; i++) { 00222 assert(!bs[i].assigned()); 00223 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) 00224 s[j.val()].add(bs[i].size()); 00225 } 00226 00227 for (int j=m; j--; ) { 00228 // Can items still be packed into bin? 00229 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max())) 00230 return ES_FAILED; 00231 int ap, bp; 00232 // Must there be packed more items into bin? 00233 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(), 00234 ap, bp)) 00235 GECODE_ME_CHECK(l[j].gq(home,bp)); 00236 // Must there be packed less items into bin? 00237 if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(), 00238 ap, bp)) 00239 GECODE_ME_CHECK(l[j].lq(home,ap)); 00240 } 00241 00242 TellCache tc(region,m); 00243 00244 int k=0; 00245 for (int i=0; i<n; i++) { 00246 assert(!bs[i].assigned()); 00247 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) { 00248 // Items must be removed in decreasing size! 00249 s[j.val()].minus(bs[i].size()); 00250 // Can item i still be packed into bin j? 00251 if (nosum(s[j.val()], 00252 l[j.val()].min() - bs[i].size(), 00253 l[j.val()].max() - bs[i].size())) 00254 tc.nq(j.val()); 00255 // Must item i be packed into bin j? 00256 if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max())) 00257 tc.eq(j.val()); 00258 } 00259 GECODE_ES_CHECK(tc.tell(home,bs[i].bin())); 00260 if (bs[i].assigned()) { 00261 int j = bs[i].bin().val(); 00262 l[j].offset(l[j].offset() - bs[i].size()); 00263 t -= bs[i].size(); 00264 } else { 00265 bs[k++] = bs[i]; 00266 } 00267 } 00268 n=k; bs.size(n); 00269 } 00270 00271 // Perform lower bound checking 00272 if (n > 0) { 00273 Region region(home); 00274 00275 // Find capacity estimate (we start from bs[0] as it might be 00276 // not packable, actually (will be detected later anyway)! 00277 int c = bs[0].size(); 00278 for (int j=m; j--; ) 00279 c = std::max(c,l[j].max()); 00280 00281 // Count how many items have a certain size (bucket sort) 00282 int* n_s = region.alloc<int>(c+1); 00283 00284 for (int i=c+1; i--; ) 00285 n_s[i] = 0; 00286 00287 // Count unpacked items 00288 for (int i=n; i--; ) 00289 n_s[bs[i].size()]++; 00290 00291 // Number of items and remaining bin load 00292 int nm = n; 00293 00294 // Only count positive remaining bin loads 00295 for (int j=m; j--; ) 00296 if (l[j].max() < 0) { 00297 return ES_FAILED; 00298 } else if (c > l[j].max()) { 00299 n_s[c - l[j].max()]++; nm++; 00300 } 00301 00302 // Sizes of items and remaining bin loads 00303 int* s = region.alloc<int>(nm); 00304 00305 // Setup sorted sizes 00306 { 00307 int k=0; 00308 for (int i=c+1; i--; ) 00309 for (int n=n_s[i]; n--; ) 00310 s[k++]=i; 00311 assert(k == nm); 00312 } 00313 00314 // Items in N1 are from 0 ... n1 - 1 00315 int n1 = 0; 00316 // Items in N2 are from n1 ... n12 - 1, we count elements in N1 and N2 00317 int n12 = 0; 00318 // Items in N3 are from n12 ... n3 - 1 00319 int n3 = 0; 00320 // Free space in N2 00321 int f2 = 0; 00322 // Total size of items in N3 00323 int s3 = 0; 00324 00325 // Initialize n12 and f2 00326 for (; (n12 < nm) && (s[n12] > c/2); n12++) 00327 f2 += c - s[n12]; 00328 00329 // Initialize n3 and s3 00330 for (n3 = n12; n3 < nm; n3++) 00331 s3 += s[n3]; 00332 00333 // Compute lower bounds 00334 for (int k=0; k<=c/2; k++) { 00335 // Make N1 larger by adding elements and N2 smaller 00336 for (; (n1 < nm) && (s[n1] > c-k); n1++) 00337 f2 -= c - s[n1]; 00338 assert(n1 <= n12); 00339 // Make N3 smaller by removing elements 00340 for (; (s[n3-1] < k) && (n3 > n12); n3--) 00341 s3 -= s[n3-1]; 00342 // Overspill 00343 int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0; 00344 if (n12 + o > m) 00345 return ES_FAILED; 00346 } 00347 } 00348 00349 return ES_NOFIX; 00350 } 00351 00352 ExecStatus 00353 Pack::post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs) { 00354 if (bs.size() == 0) { 00355 // No items to be packed 00356 for (int i=l.size(); i--; ) 00357 GECODE_ME_CHECK(l[i].eq(home,0)); 00358 return ES_OK; 00359 } else if (l.size() == 0) { 00360 // No bins available 00361 return ES_FAILED; 00362 } else { 00363 int s = 0; 00364 // Constrain bins 00365 for (int i=bs.size(); i--; ) { 00366 s += bs[i].size(); 00367 GECODE_ME_CHECK(bs[i].bin().gq(home,0)); 00368 GECODE_ME_CHECK(bs[i].bin().le(home,l.size())); 00369 } 00370 // Constrain load 00371 for (int j=l.size(); j--; ) { 00372 GECODE_ME_CHECK(l[j].gq(home,0)); 00373 GECODE_ME_CHECK(l[j].lq(home,s)); 00374 } 00375 (void) new (home) Pack(home,l,bs); 00376 return ES_OK; 00377 } 00378 } 00379 00380 }}} 00381 00382 // STATISTICS: int-prop 00383