Generated on Fri Oct 19 11:25:01 2018 for Gecode by doxygen 1.6.3

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  *  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 <gecode/int/bin-packing.hh>
00035 
00036 namespace Gecode { namespace Int { namespace BinPacking {
00037 
00038   /*
00039    * Packing propagator
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     // For eq: -1 mean not yet assigned, -2 means failure, positive means value
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    * Propagation proper
00110    *
00111    */
00112   ExecStatus
00113   Pack::propagate(Space& home, const ModEventDelta& med) {
00114     // Number of items
00115     int n = bs.size();
00116     // Number of bins
00117     int m = l.size();
00118 
00119     Region region;
00120     {
00121 
00122       // Possible sizes for bins
00123       int* s = region.alloc<int>(m);
00124 
00125       for (int j=0; j<m; j++)
00126         s[j] = 0;
00127 
00128       // Compute sizes for bins
00129       if (OffsetView::me(med) == ME_INT_VAL) {
00130         // Also eliminate assigned items
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       // Propagate bin loads and compute lower and upper bound
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       // Propagate that load must be equal to total size
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           // Eliminate assigned bin
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     // Only if the propagator is at fixpoint here, continue with the more
00213     // expensive stage for propagation.
00214     if (IntView::me(modeventdelta()) != ME_INT_NONE)
00215       return ES_NOFIX;
00216 
00217     // Now the invariant holds that no more assigned bins exist!
00218     {
00219 
00220       // Size of items
00221       SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
00222 
00223       for (int j=0; j<m; j++)
00224         s[j] = SizeSetMinusOne(region,n);
00225 
00226       // Set up size information
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         // Can items still be packed into bin?
00235         if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
00236           return ES_FAILED;
00237         int ap, bp;
00238         // Must there be packed more items into bin?
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         // Must there be packed less items into bin?
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           // Items must be removed in decreasing size!
00255           s[j.val()].minus(bs[i].size());
00256           // Can item i still be packed into bin j?
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           // Must item i be packed into bin j?
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     // Perform lower bound checking
00279     if (n > 0) {
00280 
00281       // Find capacity estimate (we start from bs[0] as it might be
00282       // not packable, actually (will be detected later anyway)!
00283       int c = bs[0].size();
00284       for (int j=0; j<m; j++)
00285         c = std::max(c,l[j].max());
00286 
00287       // Count how many items have a certain size (bucket sort)
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       // Count unpacked items
00294       for (int i=0; i<n; i++)
00295         n_s[bs[i].size()]++;
00296 
00297       // Number of items and remaining bin load
00298       int nm = n;
00299 
00300       // Only count positive remaining bin loads
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       // Sizes of items and remaining bin loads
00309       int* s = region.alloc<int>(nm);
00310 
00311       // Setup sorted sizes
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       // Items in N1 are from 0 ... n1 - 1
00321       int n1 = 0;
00322       // Items in N2 are from n1 ... n12 - 1, we count elements in N1 and N2
00323       int n12 = 0;
00324       // Items in N3 are from n12 ... n3 - 1
00325       int n3 = 0;
00326       // Free space in N2
00327       int f2 = 0;
00328       // Total size of items in N3
00329       int s3 = 0;
00330 
00331       // Initialize n12 and f2
00332       for (; (n12 < nm) && (s[n12] > c/2); n12++)
00333         f2 += c - s[n12];
00334 
00335       // Initialize n3 and s3
00336       for (n3 = n12; n3 < nm; n3++)
00337         s3 += s[n3];
00338 
00339       // Compute lower bounds
00340       for (int k=0; k<=c/2; k++) {
00341         // Make N1 larger by adding elements and N2 smaller
00342         for (; (n1 < nm) && (s[n1] > c-k); n1++)
00343           f2 -= c - s[n1];
00344         assert(n1 <= n12);
00345         // Make N3 smaller by removing elements
00346         for (; (s[n3-1] < k) && (n3 > n12); n3--)
00347           s3 -= s[n3-1];
00348         // Overspill
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     // Sort according to size
00362     Support::quicksort(&bs[0], bs.size());
00363     // Total size of items
00364     int s = 0;
00365     // Constrain bins
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     // Eliminate zero sized items (which are at the end as the size are sorted)
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       // No items to be packed
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       // No bins available
00385       return ES_FAILED;
00386     } else {
00387       // Constrain load
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 // STATISTICS: int-prop
00400