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

nary.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-01 16:35:02 +0100 (Tue, 01 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2467 $
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 #include "int/linear/noview.icc"
00023 
00024 namespace Gecode { namespace Int { namespace Linear {
00025 
00026   /*
00027    * Linear propagators
00028    *
00029    */
00030   template <class Val, class P, class N, PropCond pc>
00031   forceinline
00032   Lin<Val,P,N,pc>::Lin(Space* home, ViewArray<P>& x0, ViewArray<N>& y0, Val c0)
00033     : Propagator(home), x(x0), y(y0), c(c0) {
00034     x.subscribe(home,this,pc);
00035     y.subscribe(home,this,pc);
00036   }
00037 
00038   template <class Val, class P, class N, PropCond pc>
00039   forceinline
00040   Lin<Val,P,N,pc>::Lin(Space* home, bool share, Lin<Val,P,N,pc>& p)
00041     : Propagator(home,share,p), c(p.c) {
00042     x.update(home,share,p.x);
00043     y.update(home,share,p.y);
00044   }
00045 
00046   template <class Val, class P, class N, PropCond pc>
00047   PropCost
00048   Lin<Val,P,N,pc>::cost(void) const {
00049     return cost_lo(x.size() + y.size(), PC_LINEAR_LO);
00050   }
00051 
00052   template <class Val, class P, class N, PropCond pc>
00053   inline
00054   Lin<Val,P,N,pc>::~Lin(void) {
00055     x.cancel(this,pc);
00056     y.cancel(this,pc);
00057   }
00058 
00059 
00060   /*
00061    * Reified linear propagators
00062    *
00063    */
00064   template <class Val, class P, class N, PropCond pc, class Ctrl>
00065   forceinline
00066   ReLin<Val,P,N,pc,Ctrl>::ReLin
00067   (Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b0)
00068     : Lin<Val,P,N,pc>(home,x,y,c), b(b0) {
00069     b.subscribe(home,this,PC_INT_VAL);
00070   }
00071 
00072   template <class Val, class P, class N, PropCond pc, class Ctrl>
00073   forceinline
00074   ReLin<Val,P,N,pc,Ctrl>::ReLin
00075   (Space* home, bool share, ReLin<Val,P,N,pc,Ctrl>& p)
00076     : Lin<Val,P,N,pc>(home,share,p) {
00077     b.update(home,share,p.b);
00078   }
00079 
00080   template <class Val, class P, class N, PropCond pc, class Ctrl>
00081   inline
00082   ReLin<Val,P,N,pc,Ctrl>::~ReLin(void) {
00083     b.cancel(this,PC_INT_VAL);
00084   }
00085 
00086 
00087   /*
00088    * Computing bounds
00089    *
00090    */
00091 
00092   template <class Val, class View>
00093   void
00094   bounds_p(const Propagator* p, ViewArray<View>& x, 
00095            Val& c, Val& sl, Val& su) {
00096     int n = x.size();
00097     if (IntView::pme(p) == ME_INT_VAL) {
00098       for (int i = n; i--; ) {
00099         Val m = x[i].min();
00100         if (x[i].assigned()) {
00101           c -= m; x[i] = x[--n];
00102         } else {
00103           sl -= m; su -= x[i].max();
00104         }
00105       }
00106       x.size(n);
00107     } else {
00108       for (int i = n; i--; ) {
00109         sl -= x[i].min(); su -= x[i].max();
00110       }
00111     }
00112   }
00113 
00114   template <class Val, class View>
00115   void
00116   bounds_n(const Propagator* p, ViewArray<View>& y, 
00117            Val& c, Val& sl, Val& su) {
00118     int n = y.size();
00119     if (IntView::pme(p) == ME_INT_VAL) {
00120       for (int i = n; i--; ) {
00121         Val m = y[i].max();
00122         if (y[i].assigned()) {
00123           c += m; y[i] = y[--n];
00124         } else {
00125           sl += m; su += y[i].min();
00126         }
00127       }
00128       y.size(n);
00129     } else {
00130       for (int i = n; i--; ) {
00131         sl += y[i].max(); su += y[i].min();
00132       }
00133     }
00134   }
00135 
00136 
00137   /*
00138    * Bound consistent linear equation
00139    *
00140    */
00141 
00142   template <class Val, class P, class N>
00143   forceinline
00144   Eq<Val,P,N>::Eq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00145     : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00146 
00147   template <class Val, class P, class N>
00148   ExecStatus
00149   Eq<Val,P,N>::post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00150     ViewArray<NoView> nva;
00151     if (y.size() == 0) {
00152       (void) new (home) Eq<Val,P,NoView>(home,x,nva,c);
00153     } else if (x.size() == 0) {
00154       (void) new (home) Eq<Val,N,NoView>(home,y,nva,-c);
00155     } else {
00156       (void) new (home) Eq<Val,P,N>(home,x,y,c);
00157     }
00158     return ES_OK;
00159   }
00160 
00161 
00162   template <class Val, class P, class N>
00163   forceinline
00164   Eq<Val,P,N>::Eq(Space* home, bool share, Eq<Val,P,N>& p)
00165     : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
00166 
00167   template <class Val, class P, class N>
00168   Actor*
00169   Eq<Val,P,N>::copy(Space* home, bool share) {
00170     return new (home) Eq<Val,P,N>(home,share,*this);
00171   }
00172 
00173 
00174   template <class Val, class P, class N>
00175   ExecStatus
00176   Eq<Val,P,N>::propagate(Space* home) {
00177     // Eliminate singletons
00178     Val sl = 0;
00179     Val su = 0;
00180 
00181     bounds_p<Val,P>(this, x, c, sl, su);
00182     bounds_n<Val,N>(this, y, c, sl, su);
00183 
00184     if ((IntView::pme(this) == ME_INT_VAL) && ((x.size() + y.size()) <= 1)) {
00185       if (x.size() == 1) {
00186         GECODE_ME_CHECK(x[0].eq(home,c)); return ES_SUBSUMED;
00187       }
00188       if (y.size() == 1) {
00189         GECODE_ME_CHECK(y[0].eq(home,-c)); return ES_SUBSUMED;
00190       }
00191       return (c == static_cast<Val>(0)) ? ES_SUBSUMED : ES_FAILED;
00192     }
00193 
00194     sl += c; su += c;
00195 
00196     const int mod_sl = 1;
00197     const int mod_su = 2;
00198 
00199     int mod = mod_sl | mod_su;
00200 
00201     do {
00202       if (mod & mod_sl) {
00203         mod -= mod_sl;
00204         // Propagate upper bound for positive variables
00205         for (int i = x.size(); i--; ) {
00206           const Val xi_max = x[i].max();
00207           ModEvent me = x[i].lq(home,sl + x[i].min());
00208           if (me_failed(me))
00209             return ES_FAILED;
00210           if (me_modified(me)) {
00211             su += xi_max - x[i].max();
00212             mod |= mod_su;
00213           }
00214         }
00215         // Propagate lower bound for negative variables
00216         for (int i = y.size(); i--; ) {
00217           const Val yi_min = y[i].min();
00218           ModEvent me = y[i].gq(home,y[i].max() - sl);
00219           if (me_failed(me))
00220             return ES_FAILED;
00221           if (me_modified(me)) {
00222             su += y[i].min() - yi_min;
00223             mod |= mod_su;
00224           }
00225         }
00226       }
00227       if (mod & mod_su) {
00228         mod -= mod_su;
00229         // Propagate lower bound for positive variables
00230         for (int i = x.size(); i--; ) {
00231           const Val xi_min = x[i].min();
00232           ModEvent me = x[i].gq(home,su + x[i].max());
00233           if (me_failed(me))
00234             return ES_FAILED;
00235           if (me_modified(me)) {
00236             sl += xi_min - x[i].min();
00237             mod |= mod_sl;
00238           }
00239         }
00240         // Propagate upper bound for negative variables
00241         for (int i = y.size(); i--; ) {
00242           const Val yi_max = y[i].max();
00243           ModEvent me = y[i].lq(home,y[i].min() - su);
00244           if (me_failed(me))
00245             return ES_FAILED;
00246           if (me_modified(me)) {
00247             sl += y[i].max() - yi_max;
00248             mod |= mod_sl;
00249           }
00250         }
00251       }
00252     } while (mod);
00253 
00254     return (sl == su) ? ES_SUBSUMED : ES_FIX;
00255   }
00256 
00257   /*
00258    * Reified bound consistent linear equation
00259    *
00260    */
00261 
00262   template <class Val, class P, class N, class Ctrl>
00263   forceinline
00264   ReEq<Val,P,N,Ctrl>::ReEq(Space* home, 
00265                            ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b)
00266     : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,x,y,c,b) {}
00267 
00268   template <class Val, class P, class N, class Ctrl>
00269   ExecStatus
00270   ReEq<Val,P,N,Ctrl>::post(Space* home, 
00271                            ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) {
00272     ViewArray<NoView> nva;
00273     if (y.size() == 0) {
00274       (void) new (home) ReEq<Val,P,NoView,Ctrl>(home,x,nva,c,b);
00275     } else if (x.size() == 0) {
00276       (void) new (home) ReEq<Val,N,NoView,Ctrl>(home,y,nva,-c,b);
00277     } else {
00278       (void) new (home) ReEq<Val,P,N,Ctrl>(home,x,y,c,b);
00279     }
00280     return ES_OK;
00281   }
00282 
00283 
00284   template <class Val, class P, class N, class Ctrl>
00285   forceinline
00286   ReEq<Val,P,N,Ctrl>::ReEq(Space* home, bool share, ReEq<Val,P,N,Ctrl>& p)
00287     : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,share,p) {}
00288 
00289   template <class Val, class P, class N, class Ctrl>
00290   Actor*
00291   ReEq<Val,P,N,Ctrl>::copy(Space* home, bool share) {
00292     return new (home) ReEq<Val,P,N,Ctrl>(home,share,*this);
00293   }
00294 
00295   template <class Val, class P, class N, class Ctrl>
00296   ExecStatus
00297   ReEq<Val,P,N,Ctrl>::propagate(Space* home) {
00298     if (b.zero())
00299       return (Nq<Val,P,N>::post(home,x,y,c) == ES_FAILED)
00300         ? ES_FAILED : ES_SUBSUMED;
00301     if (b.one())
00302       return (Eq<Val,P,N>::post(home,x,y,c) == ES_FAILED)
00303         ? ES_FAILED : ES_SUBSUMED;
00304 
00305     Val sl = 0;
00306     Val su = 0;
00307 
00308     bounds_p<Val,P>(this, x, c, sl, su);
00309     bounds_n<Val,N>(this, y, c, sl, su);
00310 
00311     if ((-sl == c) && (-su == c)) {
00312       b.t_one_none(home); return ES_SUBSUMED;
00313     }
00314     if ((-sl > c) || (-su < c)) {
00315       b.t_zero_none(home); return ES_SUBSUMED;
00316     }
00317     return ES_FIX;
00318   }
00319 
00320 
00321   /*
00322    * Domain consistent linear disequation
00323    *
00324    */
00325 
00326   template <class Val, class P, class N>
00327   forceinline
00328   Nq<Val,P,N>::Nq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00329     : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {}
00330 
00331   template <class Val, class P, class N>
00332   ExecStatus
00333   Nq<Val,P,N>::post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00334     ViewArray<NoView> nva;
00335     if (y.size() == 0) {
00336       (void) new (home) Nq<Val,P,NoView>(home,x,nva,c);
00337     } else if (x.size() == 0) {
00338       (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c);
00339     } else {
00340       (void) new (home) Nq<Val,P,N>(home,x,y,c);
00341     }
00342     return ES_OK;
00343   }
00344 
00345 
00346   template <class Val, class P, class N>
00347   forceinline
00348   Nq<Val,P,N>::Nq(Space* home, bool share, Nq<Val,P,N>& p)
00349     : Lin<Val,P,N,PC_INT_VAL>(home,share,p) {}
00350 
00351   template <class Val, class P, class N>
00352   Actor*
00353   Nq<Val,P,N>::copy(Space* home, bool share) {
00354     return new (home) Nq<Val,P,N>(home,share,*this);
00355   }
00356 
00357 
00358   template <class Val, class P, class N>
00359   ExecStatus
00360   Nq<Val,P,N>::propagate(Space* home) {
00361     for (int i = x.size(); i--; )
00362       if (x[i].assigned()) {
00363         c -= x[i].val();  x.move_lst(i);
00364       }
00365     for (int i = y.size(); i--; )
00366       if (y[i].assigned()) {
00367         c += y[i].val();  y.move_lst(i);
00368       }
00369     if (x.size() + y.size() <= 1) {
00370       if (x.size() == 1) {
00371         GECODE_ME_CHECK(x[0].nq(home,c)); return ES_SUBSUMED;
00372       }
00373       if (y.size() == 1) {
00374         GECODE_ME_CHECK(y[0].nq(home,-c)); return ES_SUBSUMED;
00375       }
00376       return (c == static_cast<Val>(0)) ? ES_FAILED : ES_SUBSUMED;
00377     }
00378     return ES_FIX;
00379   }
00380 
00381 
00382   /*
00383    * Bound consistent linear inequation
00384    *
00385    */
00386 
00387   template <class Val, class P, class N>
00388   forceinline
00389   Lq<Val,P,N>::Lq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00390     : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00391 
00392   template <class Val, class P, class N>
00393   ExecStatus
00394   Lq<Val,P,N>::post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00395     ViewArray<NoView> nva;
00396     if (y.size() == 0) {
00397       (void) new (home) Lq<Val,P,NoView>(home,x,nva,c);
00398     } else if (x.size() == 0) {
00399       (void) new (home) Lq<Val,NoView,N>(home,nva,y,c);
00400     } else {
00401       (void) new (home) Lq<Val,P,N>(home,x,y,c);
00402     }
00403     return ES_OK;
00404   }
00405 
00406 
00407   template <class Val, class P, class N>
00408   forceinline
00409   Lq<Val,P,N>::Lq(Space* home, bool share, Lq<Val,P,N>& p)
00410     : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
00411 
00412   template <class Val, class P, class N>
00413   Actor*
00414   Lq<Val,P,N>::copy(Space* home, bool share) {
00415     return new (home) Lq<Val,P,N>(home,share,*this);
00416   }
00417 
00418 
00419   template <class Val, class P, class N>
00420   ExecStatus
00421   Lq<Val,P,N>::propagate(Space* home) {
00422     // Eliminate singletons
00423     Val sl = 0;
00424 
00425     if (IntView::pme(this) == ME_INT_VAL) {
00426       for (int i = x.size(); i--; ) {
00427         Val m = x[i].min();
00428         if (x[i].assigned()) {
00429           c  -= m;  x.move_lst(i);
00430         } else {
00431           sl -= m;
00432         }
00433       }
00434       for (int i = y.size(); i--; ) {
00435         Val m = y[i].max();
00436         if (y[i].assigned()) {
00437           c  += m;  y.move_lst(i);
00438         } else {
00439           sl += m;
00440         }
00441       }
00442       if ((x.size() + y.size()) <= 1) {
00443         if (x.size() == 1) {
00444           GECODE_ME_CHECK(x[0].lq(home,c));
00445           return ES_SUBSUMED;
00446         }
00447         if (y.size() == 1) {
00448           GECODE_ME_CHECK(y[0].gq(home,-c));
00449           return ES_SUBSUMED;
00450         }
00451         return (c >= static_cast<Val>(0)) ? ES_SUBSUMED : ES_FAILED;
00452       }
00453     } else {
00454       for (int i = x.size(); i--; )
00455         sl -= x[i].min();
00456       for (int i = y.size(); i--; )
00457         sl += y[i].max();
00458     }
00459 
00460     sl += c;
00461 
00462     ExecStatus es = ES_FIX;
00463     bool assigned = true;
00464     for (int i = x.size(); i--; ) {
00465       assert(!x[i].assigned());
00466       Val slx = sl + x[i].min();
00467       ModEvent me = x[i].lq(home,slx);
00468       if (me == ME_INT_FAILED)
00469         return ES_FAILED;
00470       if (me != ME_INT_VAL)
00471         assigned = false;
00472       if (me_modified(me) && (slx != x[i].max()))
00473         es = ES_NOFIX;
00474     }
00475 
00476     for (int i = y.size(); i--; ) {
00477       assert(!y[i].assigned());
00478       Val sly = y[i].max() - sl;
00479       ModEvent me = y[i].gq(home,sly);
00480       if (me == ME_INT_FAILED)
00481         return ES_FAILED;
00482       if (me != ME_INT_VAL)
00483         assigned = false;
00484       if (me_modified(me) && (sly != y[i].min()))
00485         es = ES_NOFIX;
00486     }
00487     return assigned ? ES_SUBSUMED : es;
00488   }
00489 
00490   /*
00491    * Reified bound consistent linear inequation
00492    *
00493    */
00494 
00495   template <class Val, class P, class N>
00496   forceinline
00497   ReLq<Val,P,N>::ReLq
00498   (Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b)
00499     : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {}
00500 
00501   template <class Val, class P, class N>
00502   ExecStatus
00503   ReLq<Val,P,N>::post
00504   (Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) {
00505     ViewArray<NoView> nva;
00506     if (y.size() == 0) {
00507       (void) new (home) ReLq<Val,P,NoView>(home,x,nva,c,b);
00508     } else if (x.size() == 0) {
00509       (void) new (home) ReLq<Val,NoView,N>(home,nva,y,c,b);
00510     } else {
00511       (void) new (home) ReLq<Val,P,N>(home,x,y,c,b);
00512     }
00513     return ES_OK;
00514   }
00515 
00516 
00517   template <class Val, class P, class N>
00518   forceinline
00519   ReLq<Val,P,N>::ReLq(Space* home, bool share, ReLq<Val,P,N>& p)
00520     : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,share,p) {}
00521 
00522   template <class Val, class P, class N>
00523   Actor*
00524   ReLq<Val,P,N>::copy(Space* home, bool share) {
00525     return new (home) ReLq<Val,P,N>(home,share,*this);
00526   }
00527 
00528 
00529   template <class Val, class P, class N>
00530   ExecStatus
00531   ReLq<Val,P,N>::propagate(Space* home) {
00532     if (b.zero())
00533       return (Lq<Val,N,P>::post(home,y,x,-c+1) == ES_FAILED)
00534         ? ES_FAILED : ES_SUBSUMED;
00535     if (b.one())
00536       return (Lq<Val,P,N>::post(home,x,y,c) == ES_FAILED)
00537         ? ES_FAILED : ES_SUBSUMED;
00538 
00539     // Eliminate singletons
00540     Val sl = 0;
00541     Val su = 0;
00542 
00543     bounds_p<Val,P>(this,x,c,sl,su);
00544     bounds_n<Val,N>(this,y,c,sl,su);
00545 
00546     if (-sl > c) {
00547       b.t_zero_none(home); return ES_SUBSUMED;
00548     }
00549     if (-su <= c) {
00550       b.t_one_none(home); return ES_SUBSUMED;
00551     }
00552 
00553     return ES_FIX;
00554   }
00555 
00556 }}}
00557 
00558 // STATISTICS: int-prop
00559