Generated on Thu Apr 11 13:58:57 2019 for Gecode by doxygen 1.6.3

chb.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  *
00006  *  Copyright:
00007  *     Christian Schulte, 2017
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <cfloat>
00035 
00036 namespace Gecode {
00037 
00046   class CHB : public SharedHandle {
00047   protected:
00048     template<class View>
00049     class Recorder;
00051     class Info {
00052     public:
00054       unsigned long long int lf;
00056       double qs;
00057     };
00059     class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
00060     public:
00062       GECODE_KERNEL_EXPORT static Support::Mutex m;
00064       int n;
00066       unsigned long int nf;
00068       double alpha;
00070       Info* chb;
00072       template<class View>
00073       Storage(Home home, ViewArray<View>& x,
00074               typename BranchTraits<typename View::VarType>::Merit bm);
00076       GECODE_KERNEL_EXPORT
00077       ~Storage(void);
00079       void bump(void);
00081       void update(int i, bool failed);
00082     };
00084     Storage& object(void) const;
00086     void object(Storage& o);
00088     void update(int i);
00090     void acquire(void);
00092     void release(void);
00094     void bump(void);
00096     void update(int i, bool failed);
00097   public:
00099 
00100 
00107     CHB(void);
00109     GECODE_KERNEL_EXPORT
00110     CHB(const CHB& a);
00112     GECODE_KERNEL_EXPORT
00113     CHB& operator =(const CHB& a);
00115     template<class View>
00116     CHB(Home home, ViewArray<View>& x,
00117         typename BranchTraits<typename View::VarType>::Merit bm);
00119     template<class View>
00120     void init(Home home, ViewArray<View>& x,
00121               typename BranchTraits<typename View::VarType>::Merit bm);
00123     GECODE_KERNEL_EXPORT static const CHB def;
00125 
00127     GECODE_KERNEL_EXPORT
00128     ~CHB(void);
00129 
00131 
00132 
00133     double operator [](int i) const;
00135     int size(void) const;
00137   };
00138 
00140   template<class View>
00141   class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
00142   protected:
00143     using NaryPropagator<View,PC_GEN_NONE>::x;
00145     class Idx : public Advisor {
00146     protected:
00148       int _info;
00149     public:
00151       Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
00153       Idx(Space& home, Idx& a);
00155       void mark(void);
00157       void unmark(void);
00159       bool marked(void) const;
00161       int idx(void) const;
00162     };
00164     CHB chb;
00166     Council<Idx> c;
00168     Recorder(Space& home, Recorder<View>& p);
00169   public:
00171     Recorder(Home home, ViewArray<View>& x, CHB& chb);
00173     virtual Propagator* copy(Space& home);
00175     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00177     virtual void reschedule(Space& home);
00179     virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00181     virtual void advise(Space& home, Advisor& a);
00183     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00185     virtual size_t dispose(Space& home);
00187     static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
00188   };
00189 
00194   template<class Char, class Traits>
00195   std::basic_ostream<Char,Traits>&
00196   operator <<(std::basic_ostream<Char,Traits>& os,
00197              const CHB& a);
00198 
00199 
00200   /*
00201    * Advisor for chb recorder
00202    *
00203    */
00204   template<class View>
00205   forceinline
00206   CHB::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
00207                                 Council<Idx>& c, int i)
00208     : Advisor(home,p,c), _info(i << 1) {}
00209   template<class View>
00210   forceinline
00211   CHB::Recorder<View>::Idx::Idx(Space& home, Idx& a)
00212     : Advisor(home,a), _info(a._info) {
00213   }
00214   template<class View>
00215   forceinline void
00216   CHB::Recorder<View>::Idx::mark(void) {
00217     _info |= 1;
00218   }
00219   template<class View>
00220   forceinline bool
00221   CHB::Recorder<View>::Idx::marked(void) const {
00222     return (_info & 1) != 0;
00223   }
00224   template<class View>
00225   forceinline void
00226   CHB::Recorder<View>::Idx::unmark(void) {
00227     assert(marked());
00228     _info -= 1;
00229   }
00230   template<class View>
00231   forceinline int
00232   CHB::Recorder<View>::Idx::idx(void) const {
00233     return _info >> 1;
00234   }
00235 
00236 
00237   /*
00238    * Posting of chb recorder propagator
00239    *
00240    */
00241   template<class View>
00242   forceinline
00243   CHB::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
00244                                 CHB& chb0)
00245     : NaryPropagator<View,PC_GEN_NONE>(home,x), chb(chb0), c(home) {
00246     home.notice(*this,AP_DISPOSE);
00247     for (int i=0; i<x.size(); i++)
00248       if (!x[i].assigned())
00249         x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
00250   }
00251 
00252   template<class View>
00253   forceinline ExecStatus
00254   CHB::Recorder<View>::post(Home home, ViewArray<View>& x, CHB& chb) {
00255     (void) new (home) Recorder<View>(home,x,chb);
00256     return ES_OK;
00257   }
00258 
00259 
00260   /*
00261    * CHB value storage
00262    *
00263    */
00264   template<class View>
00265   forceinline
00266   CHB::Storage::Storage(Home home, ViewArray<View>& x,
00267                         typename 
00268                         BranchTraits<typename View::VarType>::Merit bm)
00269     : n(x.size()), nf(0U), alpha(Kernel::Config::chb_alpha_init),
00270       chb(heap.alloc<Info>(x.size())) {
00271     if (bm) {
00272       for (int i=0; i<n; i++) {
00273         typename View::VarType xi(x[i].varimp());
00274         chb[i].lf = 0U;
00275         chb[i].qs = bm(home,xi,i);
00276       }
00277     } else {
00278       for (int i=0; i<n; i++) {
00279         chb[i].lf = 0U;
00280         chb[i].qs = Kernel::Config::chb_qscore_init;
00281       }
00282     }
00283   }
00284   forceinline void
00285   CHB::Storage::bump(void) {
00286     nf++;
00287     if (alpha > Kernel::Config::chb_alpha_limit) {
00288       alpha -= Kernel::Config::chb_alpha_decrement;
00289     }
00290   }
00291   forceinline void
00292   CHB::Storage::update(int i, bool failed) {
00293     if (failed) {
00294       chb[i].lf = nf;
00295       double reward = 1.0 / (nf - chb[i].lf + 1);
00296       chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
00297     } else {
00298       double reward = 0.9 / (nf - chb[i].lf + 1);
00299       chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
00300     }
00301   }
00302 
00303 
00304   /*
00305    * CHB
00306    *
00307    */
00308 
00309   forceinline CHB::Storage&
00310   CHB::object(void) const {
00311     return static_cast<CHB::Storage&>(*SharedHandle::object());
00312   }
00313 
00314   forceinline void
00315   CHB::object(CHB::Storage& o) {
00316     SharedHandle::object(&o);
00317   }
00318 
00319   forceinline double
00320   CHB::operator [](int i) const {
00321     assert((i >= 0) && (i < object().n));
00322     return object().chb[i].qs;
00323   }
00324   forceinline int
00325   CHB::size(void) const {
00326     return object().n;
00327   }
00328   forceinline void
00329   CHB::acquire(void) {
00330     object().m.acquire();
00331   }
00332   forceinline void
00333   CHB::release(void) {
00334     object().m.release();
00335   }
00336   forceinline void
00337   CHB::bump(void) {
00338     object().bump();
00339   }
00340   forceinline void
00341   CHB::update(int i, bool failed) {
00342     object().update(i,failed);
00343   }
00344 
00345   forceinline
00346   CHB::CHB(void) {}
00347 
00348   template<class View>
00349   forceinline
00350   CHB::CHB(Home home, ViewArray<View>& x,
00351            typename BranchTraits<typename View::VarType>::Merit bm) {
00352     assert(!*this);
00353     object(*new Storage(home,x,bm));
00354     (void) Recorder<View>::post(home,x,*this);
00355   }
00356   template<class View>
00357   forceinline void
00358   CHB::init(Home home, ViewArray<View>& x,
00359             typename BranchTraits<typename View::VarType>::Merit bm) {
00360     assert(!*this);
00361     object(*new Storage(home,x,bm));
00362     (void) Recorder<View>::post(home,x,*this);
00363   }
00364 
00365   template<class Char, class Traits>
00366   std::basic_ostream<Char,Traits>&
00367   operator <<(std::basic_ostream<Char,Traits>& os,
00368               const CHB& chb) {
00369     std::basic_ostringstream<Char,Traits> s;
00370     s.copyfmt(os); s.width(0);
00371     s << '{';
00372     if (chb.size() > 0) {
00373       s << chb[0];
00374       for (int i=1; i<chb.size(); i++)
00375         s << ", " << chb[i];
00376     }
00377     s << '}';
00378     return os << s.str();
00379   }
00380 
00381 
00382   /*
00383    * Propagation for chb recorder
00384    *
00385    */
00386   template<class View>
00387   forceinline
00388   CHB::Recorder<View>::Recorder(Space& home, Recorder<View>& p)
00389     : NaryPropagator<View,PC_GEN_NONE>(home,p), chb(p.chb) {
00390     c.update(home, p.c);
00391   }
00392 
00393   template<class View>
00394   Propagator*
00395   CHB::Recorder<View>::copy(Space& home) {
00396     return new (home) Recorder<View>(home, *this);
00397   }
00398 
00399   template<class View>
00400   inline size_t
00401   CHB::Recorder<View>::dispose(Space& home) {
00402     // Delete access to chb information
00403     home.ignore(*this,AP_DISPOSE);
00404     chb.~CHB();
00405     // Cancel remaining advisors
00406     for (Advisors<Idx> as(c); as(); ++as)
00407       x[as.advisor().idx()].cancel(home,as.advisor(),true);
00408     c.dispose(home);
00409     (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
00410     return sizeof(*this);
00411   }
00412 
00413   template<class View>
00414   PropCost
00415   CHB::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
00416     return PropCost::record();
00417   }
00418 
00419   template<class View>
00420   void
00421   CHB::Recorder<View>::reschedule(Space& home) {
00422     View::schedule(home,*this,ME_GEN_ASSIGNED);
00423   }
00424 
00425   template<class View>
00426   ExecStatus
00427   CHB::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
00428     static_cast<Idx&>(a).mark();
00429     return ES_NOFIX;
00430   }
00431 
00432   template<class View>
00433   void
00434   CHB::Recorder<View>::advise(Space&, Advisor& a) {
00435     static_cast<Idx&>(a).mark();
00436   }
00437 
00438   template<class View>
00439   ExecStatus
00440   CHB::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
00441     // Lock chb information
00442     chb.acquire();
00443     if (home.failed()) {
00444       chb.bump();
00445       for (Advisors<Idx> as(c); as(); ++as) {
00446         int i = as.advisor().idx();
00447         if (as.advisor().marked()) {
00448           as.advisor().unmark();
00449           chb.update(i,true);
00450           if (x[i].assigned())
00451             as.advisor().dispose(home,c);
00452         }
00453       }
00454     } else {
00455       for (Advisors<Idx> as(c); as(); ++as) {
00456         int i = as.advisor().idx();
00457         if (as.advisor().marked()) {
00458           as.advisor().unmark();
00459           chb.update(i,false);
00460           if (x[i].assigned())
00461             as.advisor().dispose(home,c);
00462         }
00463       }
00464     }
00465     chb.release();
00466     return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
00467   }
00468 
00469 
00470 }
00471 
00472 // STATISTICS: kernel-branch