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