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

ubc.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 
00045   template <class View, class Card, bool shared>
00046   forceinline ExecStatus 
00047   ubc(Space* home, ViewArray<View>& x, int& nb,
00048       HallInfo hall[], Rank rank[],
00049       PartialSum<Card>* ups,
00050       int mu[], int nu[]){
00051 
00052     ExecStatus es = ES_FIX;
00053 
00054     int rightmost = nb + 1; // rightmost accesible value in bounds
00055     int bsize     = nb + 2; // number of unique bounds including sentinels
00056 
00057     //Narrow lower bounds (UBC)
00058 
00059     /* Initializing tree structure with the values from bounds
00060      * and the interval capacities of neighboured values
00061      * from left to right
00062      */
00063 
00064     // test
00065     // unused but unitialized
00066     hall[0].h = 0;
00067     hall[0].t = 0;
00068     hall[0].d = 0;
00069 
00070     for (int i = 1; i < bsize; i++) {
00071       int pred  = i - 1;
00072       hall[i].h = pred;
00073       hall[i].t = pred;
00074       hall[i].d = ups->sumup(hall[pred].bounds, hall[i].bounds - 1);
00075     }
00076 
00077     //TESTOUT
00078 //         for (int c = 0; c < bsize; c++)
00079 //           std::cout << hall[c].bounds << " ";
00080 //         std::cout << "<<---bounds\n";
00081 //         for (int c = 1; c < bsize; c++)
00082 //           std::cout << hall[c].t << " ";
00083 //         std::cout << "<<---t\n";
00084 //         for (int c = 1; c < bsize; c++)
00085 //           std::cout << hall[c].h << " ";
00086 //         std::cout << "<<---h\n";
00087 //         for (int c = 1; c < bsize; c++)
00088 //           std::cout << hall[c].d << " ";
00089 //         std::cout << "<<---d\n";
00090     int n          = x.size();
00091     for (int i = 0; i < n; i++) {
00092       // visit intervals in increasing max order
00093       int x0   = rank[mu[i]].min;
00094       int succ = x0 + 1;
00095       int y    = rank[mu[i]].max;
00096       int z    = pathmax_t(hall, succ);
00097       int j    = hall[z].t;
00098 
00099       /* DOMINATION:
00100        *     v^i_j denotes
00101        *     unused values in the current interval. If the difference d
00102        *     between to critical capacities v^i_j and v^i_z 
00103        *     is equal to zero, j dominates z
00104        *
00105        *     i.e. [hall[l].bounds, hall[nb+1].bounds] is not left-maximal and
00106        *     [hall[j].bounds, hall[l].bounds] is a Hall set iff 
00107        *     [hall[j].bounds, hall[l].bounds] processing a variable x_i uses up a value in the interval
00108        *     [hall[z].bounds,hall[z+1].bounds] according to the intervals
00109        *     capacity. Therefore, if d = 0
00110        *     the considered value has already been used by processed variables
00111        *     m-times, where m = u[i] for value v_i. Since this value must not
00112        *     be reconsidered the path can be compressed
00113        */
00114       if (--hall[z].d == 0){
00115         hall[z].t = z + 1;
00116         z         = pathmax_t(hall, hall[z].t);
00117         hall[z].t = j;
00118       }
00119       pathset_t(hall, succ, z, z); // path compression
00120 
00121       /* NEGATIVE CAPACITY:
00122        *     A negative capacity results in a failure.Since a
00123        *     negative capacity signals that the number of variables
00124        *     whose domain is contained in the set S is larger than
00125        *     the maximum capacity of S => UBC is not satisfiable,
00126        *     i.e. there are more variables than values to instantiate them
00127        */
00128       if (hall[z].d < ups->sumup(hall[y].bounds, hall[z].bounds - 1)){
00129         return ES_FAILED;
00130       }
00131 
00132       /* UPDATING LOWER BOUND:
00133        *   If the lower bound min_i lies inside a Hall interval [a,b]
00134        *   i.e. a <= min_i <=b <= max_i
00135        *   min_i is set to  min_i := b+1
00136        */
00137       if (hall[x0].h > x0) {
00138         int w       = pathmax_h(hall, hall[x0].h);
00139         int m       = hall[w].bounds;
00140 
00141         // check for tells to shared variables
00142         if (shared && x[mu[i]].modified()) {
00143           es = ES_NOFIX;
00144         }
00145         ModEvent me = x[mu[i]].gq(home, m);
00146         GECODE_ME_CHECK(me);
00147         if (me_modified(me) && (m != x[mu[i]].min())) {
00148           es = ES_NOFIX;
00149         }
00150         pathset_h(hall, x0, w, w); // path compression
00151       }
00152       /* ZEROTEST:
00153        *     (using the difference between capacity pointers)
00154        *     zero capacity => the difference between critical capacity
00155        *     pointers is equal to the maximum capacity of the interval,i.e.
00156        *     the number of variables whose domain is contained in the
00157        *     interval is equal to the sum over all u[i] for a value v_i that
00158        *     lies in the Hall-Intervall which can also be thought of as a
00159        *     Hall-Set
00160        *
00161        *    ZeroTestLemma: Let k and l be succesive critical indices.
00162        *          v^i_k=0  =>  v^i_k = max_i+1-l+d
00163        *                   <=> v^i_k = y + 1 - z + d
00164        *                   <=> d = z-1-y
00165        *    if this equation holds the interval [j,z-1] is a hall intervall
00166        */
00167       if (hall[z].d == ups->sumup(hall[y].bounds, hall[z].bounds - 1)) {
00168         /* mark hall interval [j,z-1]
00169          * hall pointers form a path to the upper bound of the interval
00170          */
00171         int predj = j - 1;
00172         pathset_h(hall, hall[y].h, predj, y);
00173         hall[y].h = predj;
00174       }
00175     }
00176 
00177 
00178     // FORCE resorting the lower bound permutation
00179     // Create sorting permutation nu according to the variables lower bounds
00180     MinInc<View> min_inc(x);
00181     Support::quicksort<int, MinInc<View> >(nu, n, min_inc);
00182 
00183 
00184     /* Narrow upper bounds (UBC)
00185      * symmetric to the narrowing of the lower bounds
00186      */
00187 
00188     for (int i = 0; i < rightmost; i++) {
00189       int succ  = i + 1;
00190       hall[i].h = succ;
00191       hall[i].t = succ;
00192       hall[i].d = ups->sumup(hall[i].bounds, hall[succ].bounds - 1);
00193     }
00194     for (int i = n; i--; ) {
00195       // visit intervals in decreasing min order
00196       int x0   = rank[nu[i]].max;
00197       int pred = x0 - 1;
00198       int y    = rank[nu[i]].min;
00199       int z    = pathmin_t(hall, pred);
00200       int j    = hall[z].t;
00201 
00202       // DOMINATION:
00203       if (--hall[z].d == 0){
00204         hall[z].t = z - 1;
00205         z         = pathmin_t(hall, hall[z].t);
00206         hall[z].t = j;
00207       }
00208       pathset_t(hall, pred, z, z);
00209 
00210       // NEGATIVE CAPACITY:
00211       if (hall[z].d < ups->sumup(hall[z].bounds,hall[y].bounds-1)){
00212         return ES_FAILED;
00213       }
00214 
00215       /* UPDATING UPPER BOUND:
00216        *   If the upper bound max_i lies inside a Hall interval [a,b]
00217        *   i.e. min_i <= a <= max_i < b
00218        *   max_i is set to  max_i := a-1
00219        */
00220       if (hall[x0].h < x0) {
00221         int w       = pathmin_h(hall, hall[x0].h);
00222         int m       = hall[w].bounds - 1;
00223         if (shared && x[nu[i]].modified()) {
00224           es = ES_NOFIX;
00225         }
00226         ModEvent me = x[nu[i]].lq(home, m);
00227         GECODE_ME_CHECK(me);
00228         if (me_modified(me) && (m != x[nu[i]].max())) {
00229           es = ES_NOFIX;
00230         }
00231         pathset_h(hall, x0, w, w);
00232       }
00233       // ZEROTEST
00234       if (hall[z].d == ups->sumup(hall[z].bounds, hall[y].bounds - 1)) {
00235         //mark hall interval [y,j]
00236         int succj = j + 1;
00237         pathset_h(hall, hall[y].h, succj, y);
00238         hall[y].h = succj;
00239       }
00240     }
00241     return es;
00242   }
00243 
00244 }}}
00245 
00246 
00247 
00248 
00249 
00250 // STATISTICS: int-prop
00251