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

bnd.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/2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-06 11:46:17 +0100 (Tue, 06 Dec 2005) $ by $Author: schulte $
00010  *     $Revision: 2700 $
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, bool isView>
00025   inline ExecStatus
00026   prop_bnd(Space* home, ViewArray<View>& x, Card& k, 
00027            PartialSum<Card>* lps, PartialSum<Card>* ups){               
00028   
00029     ExecStatus es_ubc = ES_FIX;
00030     ExecStatus es_lbc = ES_FIX;
00031     int n = x.size();  
00032 
00033     GECODE_AUTOARRAY(int, mu, n);
00034     GECODE_AUTOARRAY(int, nu, n);
00035 
00036     for (int i = n; i--; ) {
00037       nu[i] = i;
00038       mu[i] = i;
00039     }
00040     // Create sorting permutation mu according to the variables upper bounds
00041     MaxInc<View> max_inc(x);
00042     Support::quicksort<int, MaxInc<View> >(mu, n, max_inc);
00043 
00044     // Create sorting permutation nu according to the variables lower bounds
00045     MinInc<View> min_inc(x);
00046     Support::quicksort<int, MinInc<View> >(nu, n, min_inc);
00047 
00048 
00049     assert(lps->minValue() == ups->minValue());
00050     assert(lps->maxValue() == ups->maxValue());
00051     assert(lps->minValue() <= x[nu[0]].min());
00052     assert(x[mu[x.size() - 1]].max()>= ups->maxValue());
00053 
00054     /*  
00055      *  Setup rank and bounds info
00056      *  Since this implementation is based on the theory of Hall Intervals
00057      *  additional datastructures are needed in order to represent these
00058      *  intervals and the "partial-sum" data structure (cf."gcc/gccbndsup.icc")
00059      *
00060      */
00061     
00062     GECODE_AUTOARRAY(HallInfo, hall, (2 * n + 2));
00063     GECODE_AUTOARRAY(Rank,     rank, n);
00064 
00065     int nb = 0;
00066     // setup bounds and rank      
00067     int min        = x[nu[0]].min();
00068     int max        = x[mu[0]].max() + 1;
00069     int last       = lps->firstValue + 1; //equivalent to last = min -2
00070     hall[0].bounds = last;
00071 
00072     /* 
00073      * First the algorithm merges the arrays minsorted and maxsorted
00074      * into bounds i.e. hall[].bounds contains the ordered union
00075      * of the lower and upper domain bounds including two sentinels
00076      * at the beginning and at the end of the set
00077      * ( the upper variable bounds in this union are increased by 1 )
00078      */
00079 
00080     {
00081       int i = 0;
00082       int j = 0;
00083       while (true) {
00084         if (i < n && min < max) {
00085           if (min != last) {
00086             last = min;
00087             hall[++nb].bounds = last;
00088           }
00089           rank[nu[i]].min = nb;
00090           if (++i < n) {
00091             min = x[nu[i]].min();
00092           }
00093         } else {
00094           if (max != last) {
00095             last = max;
00096             hall[++nb].bounds = last;
00097           }
00098           rank[mu[j]].max = nb;
00099           if (++j == n) {
00100             break;
00101           }
00102           max = x[mu[j]].max() + 1;
00103         }
00104       }
00105     }
00106 
00107     int rightmost = nb + 1; // rightmost accesible value in bounds
00108     hall[rightmost].bounds = ups->lastValue + 1 ;    
00109 
00110     GECODE_ES_CHECK(es_lbc = (lbc<View, Card, shared>(home, x, nb, hall, rank,
00111                                                       lps, mu, nu)));
00112     if (es_lbc == ES_NOFIX) {
00113       return ES_NOFIX;
00114     }
00115 
00116     // FORCE resorting after possible bound modification
00117     MaxInc<View> newmax(x);
00118     Support::quicksort<int, MaxInc<View> >(mu, n, newmax);
00119 
00120     MinInc<View> newmin(x);
00121     Support::quicksort<int, MinInc<View> >(nu, n, newmin);
00122 
00123     GECODE_ES_CHECK(es_ubc = (ubc<View, Card, shared>(home, x, nb, hall, rank,
00124                                                       ups, mu, nu)));
00125 
00126     if (es_ubc == ES_NOFIX || es_lbc == ES_NOFIX) {
00127       return ES_NOFIX;
00128     } else {
00129       return ES_FIX;
00130     }
00131   }
00132 
00133   // for posting
00134   template <class View, class Card, bool isView, bool shared>
00135   forceinline
00136   BndImp<View, Card, isView, shared>::
00137   BndImp(Space* home, ViewArray<View>& x0, Card& k0)
00138     : Propagator(home, true), x(x0), y(home,x0), k(k0),
00139       lps(NULL), ups(NULL){
00140     //copy of the problem variables to perform value propagation
00141     y.subscribe(home, this, PC_INT_BND);
00142     k.subscribe(home, this, PC_INT_BND);
00143   }
00144   
00145   // for cloning
00146   template <class View, class Card, bool isView, bool shared>
00147   forceinline
00148   BndImp<View, Card, isView, shared>::
00149   BndImp(Space* home, bool share, BndImp<View, VarCard, isView, shared>& p)
00150     : Propagator(home, share, p), lps(NULL), ups(NULL)  {
00151     x.update(home, share, p.x);
00152     y.update(home, share, p.y);
00153     k.update(home, share, p.k);
00154   }
00155 
00156   template <class View, class Card, bool isView, bool shared>
00157   forceinline
00158   BndImp<View, Card, isView, shared>::
00159   BndImp(Space* home, bool share, BndImp<View, FixCard, isView, shared>& p)  
00160     : Propagator(home, share, p), k(p.k.size()), 
00161       lps(NULL), ups(NULL){ 
00162     x.update(home, share, p.x);
00163     y.update(home, share, p.y);
00164     k.update(home, share, p.k);
00165   }
00166 
00167   template <class View, class Card, bool isView, bool shared>
00168   forceinline
00169   BndImp<View, Card, isView, shared>::~BndImp(void){
00170     y.cancel(this, PC_INT_BND);
00171     k.cancel(this, PC_INT_BND);
00172     delete lps;
00173     lps = NULL;
00174     delete ups;
00175     ups = NULL;
00176   }
00177 
00178   template <class View, class Card, bool isView, bool shared>
00179   forceinline Actor* 
00180   BndImp<View, Card, isView, shared>::copy(Space* home, bool share){
00181     return new (home) BndImp<View, Card, isView, shared>(home, share, *this);
00182   }
00183 
00184   template <class View, class Card, bool isView, bool shared>
00185   forceinline PropCost
00186   BndImp<View, Card, isView, shared>::cost (void) const {
00187     /* 
00188      * The bounds consistent version of the Global Cardinality constraint
00189      * has a theoretical complexity of
00190      *   O(t + n\cdot log(n)) with
00191      *   n = number of variables
00192      *   t = time needed to sort the domain bounds of the variables
00193      */
00194     return (View::pme(this) == ME_INT_VAL)
00195       ? cost_lo(y.size(),PC_LINEAR_LO)
00196       : cost_hi(x.size(),PC_LINEAR_HI);
00197   }
00198 
00199   template <class View, class Card, bool isView, bool shared>
00200   forceinline ExecStatus 
00201   BndImp<View, Card, isView, shared>::propagate(Space* home) {  
00202 
00203     bool all_assigned = true;
00204     bool mod          = false;
00205 
00206     GECODE_AUTOARRAY(int, count, k.size());
00207     for (int i = k.size(); i--; ) {
00208       count[i] = 0;
00209     }
00210       
00211     for (int i = x.size(); i--; ) {
00212       bool b = x[i].assigned();
00213       all_assigned &= b;
00214       if (b) {
00215         int idx = k.lookup(x[i].val());
00216         // reduction is essential for order on value nodes in dom
00217         // hence introduce test for failed lookup
00218         if (idx == -1) {
00219           return ES_FAILED;
00220         }
00221         count[idx]++;
00222       }
00223     }
00224 
00225     if (all_assigned) {
00226       for (int i = k.size(); i--; ) {
00227         int ci = count[i];
00228         if (! (k[i].min() <= ci && ci <= k[i].max())) {
00229           return ES_FAILED;
00230         } else {
00231           if (isView) {
00232             ModEvent me = k[i].eq(home, ci);
00233             GECODE_ME_CHECK(me);
00234             mod |= k[i].assigned();
00235           }
00236         }
00237       }
00238       return ES_SUBSUMED;
00239     }
00240 
00241 
00242     ExecStatus es = 
00243       prop_val<View, Card, isView>(home, y, k);
00244     if (es == ES_FAILED || es == ES_SUBSUMED) {
00245       return es;
00246     }
00247 
00248     int cmin = x[x.size() - 1].min();
00249     int cmax = x[x.size() - 1].max();
00250     
00251     for (int i = x.size() - 1; i--; ) {
00252       if (x[i].min() < cmin) {
00253         cmin = x[i].min();
00254       }
00255       if (x[i].max() > cmax) {
00256         cmax = x[i].max();
00257       }
00258     }
00259 
00260     // ensure that only values are considered lying in the variable domain
00261     reduce_card(cmin, cmax, k); 
00262 
00263     if (lps == NULL) {
00264       assert (ups == NULL);
00265       lps = new PartialSum<Card>(cmin,  k.size(), k, false);
00266       ups = new PartialSum<Card>(cmin,  k.size(), k, true);
00267     } 
00268 
00269     if (isView) {
00270       // if there has been a change to the cardinality variables
00271       // reconstruction of the partial sum structure is necessary
00272       if (lps->check_update_min(k)) {
00273         delete lps;
00274         lps = new PartialSum<Card>(cmin,  k.size(), k, false);
00275       }
00276       
00277       if (ups->check_update_max(k)) {
00278         delete ups;
00279         ups = new PartialSum<Card>(cmin,  k.size(), k, true);
00280       }
00281     }
00282 
00283     bool minima_equal = lps->minValue() == ups->minValue();
00284     bool maxima_equal = lps->maxValue() == ups->maxValue();
00285     bool min_is_valid = lps->minValue() <= cmin;
00286     bool max_is_valid = cmax >= ups->maxValue();
00287 
00288     if (!minima_equal || 
00289         !maxima_equal || 
00290         !min_is_valid ||
00291         !max_is_valid) {
00292       delete lps; 
00293       lps = new PartialSum<Card>(cmin, k.size(), k, false);
00294       delete ups;
00295       ups = new PartialSum<Card>(cmin, k.size(), k, true);
00296     }
00297 
00298     assert(lps->minValue() == ups->minValue());
00299     assert(lps->maxValue() == ups->maxValue());
00300     assert(lps->minValue() <= cmin);
00301     assert(cmax>= ups->maxValue());
00302 
00303     GECODE_ES_CHECK((prop_bnd<View, Card, shared, isView>(home, x, k, lps, ups)));
00304 
00305     all_assigned = true;
00306 
00307     for (int i = k.size(); i--; ) {
00308       count[i] = 0;
00309     }
00310       
00311     for (int i = x.size(); i--; ) {
00312       bool b = x[i].assigned();
00313       all_assigned &= b;
00314       if (b) {
00315         int idx = k.lookup(x[i].val());
00316         count[idx]++;
00317       }
00318     }
00319 
00320     if (all_assigned) {
00321       for (int i = k.size(); i--; ) {
00322       int ci = count[i];
00323         if (! (k[i].min() <= ci && ci <= k[i].max())) {
00324           return ES_FAILED;
00325         } else {
00326           if (isView) {
00327             ModEvent me = k[i].eq(home, ci);
00328             GECODE_ME_CHECK(me);
00329             mod |= k[i].assigned();
00330           }
00331         }
00332       }
00333       return ES_SUBSUMED;
00334     }
00335 
00336     return (mod) ? ES_NOFIX : ES_FIX;
00337   }
00338 
00339   template <class View, class Card, bool isView>
00340   inline ExecStatus
00341   Bnd<View, Card, isView>::post(Space* home, ViewArray<View>& x0, Card& k0) {
00342     if (x0.shared()) {
00343       new (home) BndImp<View, Card, isView, true>(home, x0, k0);
00344     } else {
00345       new (home) BndImp<View, Card, isView, false>(home, x0, k0);
00346     }
00347     return ES_OK;
00348   }
00349 
00350   template <class View, class Card, bool isView, bool shared>
00351   void
00352   BndImp<View, Card, isView, shared>::flush(void){
00353     delete lps; 
00354     lps = NULL;
00355     delete ups;
00356     ups = NULL;
00357   }
00358 
00359 }}}
00360 
00361 // STATISTICS: int-prop
00362