Generated on Wed Jan 4 17:49:10 2006 for Gecode by doxygen 1.4.6

lbc.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2696 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Int { namespace GCC {
00023 
00024   template <class View, class Card, bool shared>
00025   forceinline ExecStatus 
00026   lbc(Space* home, ViewArray<View>& x, int& nb,
00027       HallInfo hall[],
00028       Rank rank[],
00029       PartialSum<Card>* lps,
00030       int mu[], int nu[]){
00031     
00032     ExecStatus es = ES_FIX;
00033     int n = x.size();
00034 
00035     /*
00036      *  Let I(S) denote the number of variables whose domain intersects
00037      *  the set S and C(S) the number of variables whose domain is containded
00038      *  in S. Let further  min_cap(S) be the minimal number of variables
00039      *  that must be assigned to values, that is
00040      *  min_cap(S) is the sum over all l[i] for a value v_i that is an
00041      *  element of S.
00042      *
00043      *  A failure set is a set F if
00044      *       I(F) < min_cap(F)
00045      *  An unstable set is a set U if
00046      *       I(U) = min_cap(U)
00047      *  A stable set is a set S if
00048      *      C(S) > min_cap(S) and S intersetcs nor
00049      *      any failure set nor any unstable set
00050      *      forall unstable and failure sets
00051      *
00052      *  failure sets determine the satisfiability of the LBC
00053      *  unstable sets have to be pruned
00054      *  stable set do not have to be pruned
00055      *
00056      * hall[].ps ~ stores the unstable
00057      *             sets that have to be pruned
00058      * hall[].s  ~ stores sets that must not be pruned
00059      * hall[].h  ~ contains stable and unstable sets
00060      * hall[].d  ~ contains the difference between interval bounds, i.e.
00061      *             the minimal capacity of the interval
00062      * hall[].t  ~ contains the critical capacity pointer, pointing to the
00063      *             values
00064      */
00065 
00066     // LBC lower bounds
00067 
00068     int i = 0;
00069     int j = 0;
00070     int w = 0;
00071     int z = 0;
00072     int v = 0;
00073 
00074     //initialization of the tree structure
00075     int rightmost = nb + 1; // rightmost accesible value in bounds
00076     int bsize     = nb + 2;
00077     w = rightmost;
00078 
00079     // test
00080     // unused but uninitialized
00081     hall[0].d = 0;
00082     hall[0].s = 0;
00083     hall[0].ps = 0;
00084 
00085     for (i = bsize; --i; ) { // i must not be zero
00086       int pred   = i - 1;
00087       hall[i].s  = pred;
00088       hall[i].ps = pred;
00089       hall[i].d  = lps->sumup(hall[pred].bounds, hall[i].bounds - 1);
00090 
00091       /* Let [hall[i].bounds,hall[i-1].bounds]=:I
00092        * If the capacity is zero => min_cap(I) = 0
00093        * => I cannot be a failure set
00094        * => I is an unstable set
00095        */
00096       if (hall[i].d == 0) {
00097         hall[pred].h = w;
00098       } else {
00099         hall[w].h = pred;
00100         w         = pred;
00101       }
00102     }
00103 
00104     w = rightmost;
00105     for (i = bsize; i--; ) { // i can be zero
00106       if (hall[i].d == 0) {
00107         hall[i].t = w;
00108       } else {
00109         hall[w].t = i;
00110         w         = i;
00111       }
00112     }
00113 
00114     /*
00115      * The algorithm assigns to each value v in bounds
00116      * empty buckets corresponding to the minimal capacity l[i] to be
00117      * filled for v. (the buckets correspond to hall[].d containing the
00118      * difference between the interval bounds) Processing it
00119      * searches for the smallest value v in dom(x_i) that has an
00120      * empty bucket, i.e. if all buckets are filled it is guaranteed
00121      * that there are at least l[i] variables that will be
00122      * instantiated to v. Since the buckets are initially empty,
00123      * they are considered as FAILURE SETS
00124      */
00125 
00126 //     TESTOUT
00127 //         for (int c = 0; c < bsize; c++)
00128 //           std::cout << hall[c].bounds << " ";
00129 //         std::cout << "<<---bounds\n";
00130 //         for (int c = 1; c < bsize; c++)
00131 //           std::cout << hall[c].t << " ";
00132 //         std::cout << "<<---t\n";
00133 //         for (int c = 1; c < bsize; c++)
00134 //           std::cout << hall[c].h << " ";
00135 //         std::cout << "<<---h\n";
00136 //         for (int c = 1; c < bsize; c++)
00137 //           std::cout << hall[c].d << " ";
00138 //         std::cout << "<<---d\n";
00139 
00140     for (i = 0; i < n; i++) {
00141       // visit intervals in increasing max order
00142       int x0   = rank[mu[i]].min;
00143       int y    = rank[mu[i]].max;
00144       int succ = x0 + 1;  
00145       z        = pathmax_t(hall, succ);
00146       j        = hall[z].t;
00147 
00148       /*
00149        * POTENTIALLY STABLE SET:
00150        *  z \neq succ \Leftrigharrow z>succ, i.e. 
00151        *  min(D_{\mu(i)}) is guaranteed to occur min(K_i) times 
00152        *  \Rightarrow [x0, min(y,z)] is potentially stable 
00153        */
00154 
00155       if (z != succ) {
00156         w = pathmax_ps(hall, succ);
00157         v = hall[w].ps; 
00158         pathset_ps(hall, succ, w, w); 
00159         w = std::min(y, z); 
00160         pathset_ps(hall, hall[w].ps, v, w);
00161         hall[w].ps = v;
00162       }
00163 
00164       /*
00165        * STABLE SET:
00166        *   being stable implies being potentially stable, i.e. 
00167        *   [hall[y].ps, hall[y].bounds-1] is the largest stable subset of 
00168        *   [hall[j].bounds, hall[y].bounds-1]. 
00169        */
00170 
00171       if (hall[z].d <= lps->sumup(hall[y].bounds, hall[z].bounds - 1)) {
00172         w = pathmax_s(hall, hall[y].ps);
00173         pathset_s(hall, hall[y].ps, w, w);
00174         // Path compression
00175         v = hall[w].s;
00176         pathset_s(hall, hall[y].s, v, y);
00177         hall[y].s = v;
00178       } else {
00179         /*
00180          * FAILURE SET:
00181          * If the considered interval [x0,y] is neither POTENTIALLY STABLE
00182          * nor STABLE there are still buckets that can be filled,
00183          * therefore d can be decreased. If d equals zero the intervals
00184          * minimum capacity is met and thepath can be compressed to the
00185          * next value having an empty bucket.
00186          * see DOMINATION in "gcc/ubc.icc"
00187          */
00188         if (--hall[z].d == 0) {
00189           hall[z].t = z + 1;
00190           z         = pathmax_t(hall, hall[z].t);
00191           hall[z].t = j;
00192         }
00193 
00194         /*
00195          * FINDING NEW LOWER BOUND:
00196          * If the lower bound belongs to an unstable or a stable set,
00197          * remind the new value we might assigned to the lower bound
00198          * in case the variable doesn't belong to a stable set.
00199          */
00200         if (hall[x0].h > x0) {
00201           hall[i].newBound = pathmax_h(hall, x0);
00202           w                = hall[i].newBound;
00203           pathset_h(hall, x0, w, w); // path compression
00204         } else {
00205           // Do not shrink the variable: take old min as new min
00206           hall[i].newBound = x0;
00207         }
00208 
00209         /* UNSTABLE SET
00210          * If an unstable set is discovered
00211          * the difference between the interval bounds is equal to the
00212          * number of variables whose domain intersect the interval
00213          * (see ZEROTEST in "gcc/ubc.icc")
00214          */
00215         // CLEARLY THIS WAS NOT STABLE == UNSTABLE 
00216         if (hall[z].d == lps->sumup(hall[y].bounds, hall[z].bounds - 1)) {
00217           if (hall[y].h > y)
00218             /* y is not the end of the potentially stable set
00219              * thus ensure that the potentially stable superset is marked
00220              */
00221             y = hall[y].h;
00222           // Equivalent to pathmax since the path is fully compressed
00223           int predj = j - 1;
00224           pathset_h(hall, hall[y].h, predj, y);
00225           // mark the new unstable set [j,y]
00226           hall[y].h = predj;
00227         }
00228       }
00229       pathset_t(hall, succ, z, z); // path compression
00230     }
00231 
00232     /* If there is a FAILURE SET left the minimum occurences of the values
00233      * are not guaranteed. In order to satisfy the LBC the last value
00234      * in the stable and unstable datastructure hall[].h must point to
00235      * the sentinel at the beginning of bounds.
00236      */
00237     if (hall[nb].h != 0) {
00238       return ES_FAILED; // no solution
00239     }
00240 
00241     // Perform path compression over all elements in
00242     // the stable interval data structure. This data
00243     // structure will no longer be modified and will be
00244     // accessed n or 2n times. Therefore, we can afford
00245     // a linear time compression.
00246     for (i = bsize; --i;) {
00247       if (hall[i].s > i) {
00248         hall[i].s = w;
00249       } else {
00250         w = i;
00251       }
00252     }
00253 
00254     /*
00255      * UPDATING LOWER BOUND:
00256      * For all variables that are not a subset of a stable set,
00257      * shrink the lower bound, i.e. forall stable sets S we have:
00258      * x0 < S_min <= y <=S_max  or S_min <= x0 <= S_max < y
00259      * that is [x0,y] is NOT a proper subset of any stable set S
00260      */
00261     for (i = n; i--; ) {
00262       int x0 = rank[mu[i]].min;
00263       int y  = rank[mu[i]].max;
00264       // update only those variables that are not contained in a stable set
00265       if ((hall[x0].s <= x0) || (y > hall[x0].s)) {
00266         //still have to check this out, how skipping works (consider dominated indices)
00267         int m = lps->skipNonNullElementsRight(hall[hall[i].newBound].bounds);
00268         if (shared && x[mu[i]].modified()) {
00269           es = ES_NOFIX;
00270         }
00271         ModEvent me = x[mu[i]].gq(home, m);
00272         GECODE_ME_CHECK(me);
00273         if (me_modified(me) && m != x[mu[i]].min()) {
00274           es = ES_NOFIX;
00275         }
00276       }
00277     }
00278 
00279 
00280     // FORCE resorting
00281     MinInc<View> min_inc(x);
00282     Support::quicksort<int, MinInc<View> >(nu, n, min_inc);
00283 
00284     //LBC narrow upper bounds
00285     
00286     w = 0;
00287     for (i = 0; i <= nb; i++) {
00288       hall[i].d = lps->sumup(hall[i].bounds, hall[i + 1].bounds - 1);
00289       if (hall[i].d == 0) {
00290         hall[i].t = w;
00291       } else {
00292         hall[w].t = i;
00293         w         = i;
00294       }
00295     }
00296     hall[w].t = i;
00297 
00298     w         = 0;
00299     for (i = 1; i <= nb; i++) {
00300       if (hall[i - 1].d == 0) {
00301         hall[i].h = w;
00302       } else {
00303          hall[w].h = i;
00304          w         = i;
00305       }
00306     }
00307     hall[w].h = i;
00308 
00309     for (i = n; i--; ) {
00310       // visit intervals in decreasing min order
00311       // i.e. minsorted from right to left
00312       int x0   = rank[nu[i]].max;
00313       int y    = rank[nu[i]].min;
00314       int pred = x0 - 1; // predecessor of x0 in the indices
00315       z        = pathmin_t(hall, pred);
00316       j        = hall[z].t;
00317 
00318       /* If the variable is not in a discovered stable set
00319        * (see above condition for STABLE SET)
00320        */
00321       if (hall[z].d > lps->sumup(hall[z].bounds, hall[y].bounds - 1)) {
00322         //FAILURE SET
00323         if (--hall[z].d == 0) {
00324           hall[z].t = z - 1;
00325           z         = pathmin_t(hall, hall[z].t);
00326           hall[z].t = j;
00327         }
00328         //FINDING NEW UPPER BOUND
00329         if (hall[x0].h < x0) {
00330           w                = pathmin_h(hall, hall[x0].h);
00331           hall[i].newBound = w;
00332           pathset_h(hall, x0, w, w); // path compression
00333         } else {
00334           hall[i].newBound = x0;
00335         }
00336         //UNSTABLE SET
00337         if (hall[z].d == lps->sumup(hall[z].bounds, hall[y].bounds - 1)) {
00338           if (hall[y].h < y) {
00339             y = hall[y].h;
00340           }
00341           int succj = j + 1;
00342           //mark new unstable set [y,j]
00343           pathset_h(hall, hall[y].h, succj, y);
00344           hall[y].h = succj;
00345         }
00346       }
00347       pathset_t(hall, pred, z, z);
00348     }
00349 
00350     // UPDATING UPPER BOUND
00351     for (i = n; i--; ) {
00352       int x0 =  rank[nu[i]].min;
00353       int y  =  rank[nu[i]].max;
00354       if ((hall[x0].s <= x0) || (y > hall[x0].s)){
00355         int m = lps->skipNonNullElementsLeft(hall[hall[i].newBound].bounds - 1);
00356         if (shared && x[nu[i]].modified()) {
00357           es = ES_NOFIX;
00358         }
00359         ModEvent me = x[nu[i]].lq(home, m);
00360         GECODE_ME_CHECK(me);
00361         if (me_modified(me) && m != x[nu[i]].max()) {
00362           es = ES_NOFIX;
00363         }
00364       }
00365     }
00366     return es;
00367   }
00368 
00369 }}}
00370 
00371 // STATISTICS: int-prop
00372