Generated on Fri Oct 19 11:24:55 2018 for Gecode by doxygen 1.6.3

nary.hpp

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  *     Vincent Barichard <Vincent.Barichard@univ-angers.fr>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2003
00009  *     Vincent Barichard, 2012
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 namespace Gecode { namespace Float { namespace Linear {
00037 
00038   /*
00039    * Linear propagators
00040    *
00041    */
00042   template<class P, class N, PropCond pc>
00043   forceinline
00044   Lin<P,N,pc>::Lin(Home home, ViewArray<P>& x0, ViewArray<N>& y0, FloatVal c0)
00045     : Propagator(home), x(x0), y(y0), c(c0) {
00046     x.subscribe(home,*this,pc);
00047     y.subscribe(home,*this,pc);
00048   }
00049 
00050   template<class P, class N, PropCond pc>
00051   forceinline
00052   Lin<P,N,pc>::Lin(Space& home, Lin<P,N,pc>& p)
00053     : Propagator(home,p), c(p.c) {
00054     x.update(home,p.x);
00055     y.update(home,p.y);
00056   }
00057 
00058   template<class P, class N, PropCond pc>
00059   PropCost
00060   Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
00061     return PropCost::linear(PropCost::LO, x.size()+y.size());
00062   }
00063 
00064   template<class P, class N, PropCond pc>
00065   void
00066   Lin<P,N,pc>::reschedule(Space& home) {
00067     x.reschedule(home,*this,pc);
00068     y.reschedule(home,*this,pc);
00069   }
00070 
00071   template<class P, class N, PropCond pc>
00072   forceinline size_t
00073   Lin<P,N,pc>::dispose(Space& home) {
00074     x.cancel(home,*this,pc);
00075     y.cancel(home,*this,pc);
00076     (void) Propagator::dispose(home);
00077     return sizeof(*this);
00078   }
00079 
00080 
00081   template<class View>
00082   void
00083   eliminate_p(ModEventDelta med, ViewArray<View>& x, FloatVal& c) {
00084     int n = x.size();
00085 
00086     if (FloatView::me(med) == ME_FLOAT_VAL) {
00087       for (int i = n; i--; ) {
00088         if (x[i].assigned()) {
00089           c -= x[i].val(); x[i] = x[--n];
00090         }
00091       }
00092       x.size(n);
00093     }
00094   }
00095 
00096   template<class View>
00097   void
00098   eliminate_n(ModEventDelta med, ViewArray<View>& y, FloatVal& c) {
00099     int n = y.size();
00100     if (FloatView::me(med) == ME_FLOAT_VAL) {
00101       for (int i = n; i--; ) {
00102         if (y[i].assigned()) {
00103           c += y[i].val(); y[i] = y[--n];
00104         }
00105       }
00106       y.size(n);
00107     }
00108   }
00109 
00110   forceinline bool
00111   infty(const FloatNum& n) {
00112     return ((n == std::numeric_limits<FloatNum>::infinity()) ||
00113             (n == -std::numeric_limits<FloatNum>::infinity()));
00114   }
00115 
00116   /*
00117    * Bound consistent linear equation
00118    *
00119    */
00120 
00121   template<class P, class N>
00122   forceinline
00123   Eq<P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
00124     : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
00125 
00126   template<class P, class N>
00127   ExecStatus
00128   Eq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
00129     (void) new (home) Eq<P,N>(home,x,y,c);
00130     return ES_OK;
00131   }
00132 
00133 
00134   template<class P, class N>
00135   forceinline
00136   Eq<P,N>::Eq(Space& home, Eq<P,N>& p)
00137     : Lin<P,N,PC_FLOAT_BND>(home,p) {}
00138 
00139   template<class P, class N>
00140   Actor*
00141   Eq<P,N>::copy(Space& home) {
00142     return new (home) Eq<P,N>(home,*this);
00143   }
00144 
00145   template<class P, class N>
00146   ExecStatus
00147   Eq<P,N>::propagate(Space& home, const ModEventDelta& med) {
00148     // Eliminate singletons
00149     Rounding r;
00150     eliminate_p<P>(med, x, c);
00151     eliminate_n<N>(med, y, c);
00152 
00153     if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
00154       if (x.size() == 1) {
00155         GECODE_ME_CHECK(x[0].eq(home,c));
00156         return home.ES_SUBSUMED(*this);
00157       }
00158       if (y.size() == 1) {
00159         GECODE_ME_CHECK(y[0].eq(home,-c));
00160         return home.ES_SUBSUMED(*this);
00161       }
00162       return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00163     }
00164 
00165     ExecStatus es = ES_FIX;
00166     bool assigned = true;
00167 
00168     // Propagate max bound for positive variables
00169     for (int i = x.size(); i--; ) {
00170       // Compute bound
00171       FloatNum sl = c.max();
00172       for (int j = x.size(); j--; ) {
00173         if (i == j) continue;
00174         sl = r.sub_up(sl,x[j].min());
00175       }
00176       for (int j = y.size(); j--; )
00177         sl = r.add_up(sl,y[j].max());
00178       ModEvent me = x[i].lq(home,sl);
00179       if (me_failed(me))
00180         return ES_FAILED;
00181       if (me != ME_FLOAT_VAL)
00182         assigned = false;
00183       if (me_modified(me))
00184         es = ES_NOFIX;
00185     }
00186     // Propagate min bound for negative variables
00187     for (int i = y.size(); i--; ) {
00188       // Compute bound
00189       FloatNum sl = -c.max();
00190       for (int j = x.size(); j--; )
00191         sl = r.add_down(sl,x[j].min());
00192       for (int j = y.size(); j--; ) {
00193         if (i == j) continue;
00194         sl = r.sub_down(sl,y[j].max());
00195       }
00196       ModEvent me = y[i].gq(home,sl);
00197       if (me_failed(me))
00198         return ES_FAILED;
00199       if (me != ME_FLOAT_VAL)
00200         assigned = false;
00201       if (me_modified(me))
00202         es = ES_NOFIX;
00203     }
00204 
00205     // Propagate min bound for positive variables
00206     for (int i = x.size(); i--; ) {
00207       // Compute bound
00208       FloatNum su = c.min();
00209       for (int j = x.size(); j--; ) {
00210         if (i == j) continue;
00211         su = r.sub_down(su,x[j].max());
00212       }
00213       for (int j = y.size(); j--; )
00214         su = r.add_down(su,y[j].min());
00215       ModEvent me = x[i].gq(home,su);
00216       if (me_failed(me))
00217         return ES_FAILED;
00218       if (me != ME_FLOAT_VAL)
00219         assigned = false;
00220       if (me_modified(me))
00221         es = ES_NOFIX;
00222     }
00223     // Propagate max bound for negative variables
00224     for (int i = y.size(); i--; ) {
00225       // Compute bound
00226       FloatNum su = -c.min();
00227       for (int j = x.size(); j--; )
00228         su = r.add_up(su,x[j].max());
00229       for (int j = y.size(); j--; ) {
00230         if (i == j) continue;
00231         su = r.sub_up(su,y[j].min());
00232       }
00233       ModEvent me = y[i].lq(home,su);
00234       if (me_failed(me))
00235         return ES_FAILED;
00236       if (me != ME_FLOAT_VAL)
00237         assigned = false;
00238       if (me_modified(me))
00239         es = ES_NOFIX;
00240     }
00241 
00242     return assigned ? home.ES_SUBSUMED(*this) : es;
00243   }
00244 
00245 
00246   /*
00247    * Bound consistent linear inequation
00248    *
00249    */
00250 
00251   template<class P, class N>
00252   forceinline
00253   Lq<P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c)
00254     : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
00255 
00256   template<class P, class N>
00257   ExecStatus
00258   Lq<P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, FloatVal c) {
00259     (void) new (home) Lq<P,N>(home,x,y,c);
00260     return ES_OK;
00261   }
00262 
00263   template<class P, class N>
00264   forceinline
00265   Lq<P,N>::Lq(Space& home, Lq<P,N>& p)
00266     : Lin<P,N,PC_FLOAT_BND>(home,p) {}
00267 
00268   template<class P, class N>
00269   Actor*
00270   Lq<P,N>::copy(Space& home) {
00271     return new (home) Lq<P,N>(home,*this);
00272   }
00273 
00274   template<class P, class N>
00275   ExecStatus
00276   Lq<P,N>::propagate(Space& home, const ModEventDelta& med) {
00277     // Eliminate singletons
00278     FloatNum sl = 0.0;
00279 
00280     Rounding r;
00281 
00282     if (FloatView::me(med) == ME_FLOAT_VAL) {
00283       for (int i = x.size(); i--; ) {
00284         if (x[i].assigned()) {
00285           c  -= x[i].val();  x.move_lst(i);
00286         } else {
00287           sl = r.sub_up(sl,x[i].min());
00288         }
00289       }
00290       for (int i = y.size(); i--; ) {
00291         if (y[i].assigned()) {
00292           c  += y[i].val();  y.move_lst(i);
00293         } else {
00294           sl = r.add_up(sl,y[i].max());
00295         }
00296       }
00297       if ((x.size() + y.size()) <= 1) {
00298         if (x.size() == 1) {
00299           GECODE_ME_CHECK(x[0].lq(home,c.max()));
00300           return home.ES_SUBSUMED(*this);
00301         }
00302         if (y.size() == 1) {
00303           GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
00304           return home.ES_SUBSUMED(*this);
00305         }
00306         return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
00307       }
00308     } else {
00309       for (int i = x.size(); i--; )
00310         sl = r.sub_up(sl,x[i].min());
00311       for (int i = y.size(); i--; )
00312         sl = r.add_up(sl,y[i].max());
00313     }
00314 
00315     sl = r.add_up(sl,c.max());
00316 
00317     ExecStatus es = ES_FIX;
00318     bool assigned = true;
00319     for (int i = x.size(); i--; ) {
00320       assert(!x[i].assigned());
00321       FloatNum slx = r.add_up(sl,x[i].min());
00322       ModEvent me = x[i].lq(home,slx);
00323       if (me == ME_FLOAT_FAILED)
00324         return ES_FAILED;
00325       if (me != ME_FLOAT_VAL)
00326         assigned = false;
00327       if (me_modified(me))
00328         es = ES_NOFIX;
00329     }
00330 
00331     for (int i = y.size(); i--; ) {
00332       assert(!y[i].assigned());
00333       FloatNum sly = r.sub_up(y[i].max(),sl);
00334       ModEvent me = y[i].gq(home,sly);
00335       if (me == ME_FLOAT_FAILED)
00336         return ES_FAILED;
00337       if (me != ME_FLOAT_VAL)
00338         assigned = false;
00339       if (me_modified(me))
00340         es = ES_NOFIX;
00341     }
00342 
00343     return assigned ? home.ES_SUBSUMED(*this) : es;
00344   }
00345 
00346 }}}
00347 
00348 // STATISTICS: float-prop
00349