00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <cfloat>
00039
00040 namespace Gecode {
00041
00050 class CHB {
00051 protected:
00052 template<class View>
00053 class Recorder;
00055 class Info {
00056 public:
00058 unsigned long long int lf;
00060 double qs;
00061 };
00063 class Storage : public HeapAllocated {
00064 public:
00066 Support::Mutex m;
00068 unsigned int use_cnt;
00070 int n;
00072 Info* chb;
00074 unsigned long long int nf;
00076 double alpha;
00078 template<class View>
00079 Storage(Home home, ViewArray<View>& x,
00080 typename BranchTraits<typename View::VarType>::Merit bm);
00082 ~Storage(void);
00084 void bump(void);
00086 void update(int i, bool failed);
00087 };
00089 Storage* storage;
00091 void update(int i);
00093 void acquire(void);
00095 void release(void);
00097 void bump(void);
00099 void update(int i, bool failed);
00100 public:
00102
00103
00110 CHB(void);
00112 GECODE_KERNEL_EXPORT
00113 CHB(const CHB& a);
00115 GECODE_KERNEL_EXPORT
00116 CHB& operator =(const CHB& a);
00118 template<class View>
00119 CHB(Home home, ViewArray<View>& x,
00120 typename BranchTraits<typename View::VarType>::Merit bm);
00122 template<class View>
00123 void init(Home home, ViewArray<View>& x,
00124 typename BranchTraits<typename View::VarType>::Merit bm);
00126 operator bool(void) const;
00128 GECODE_KERNEL_EXPORT static const CHB def;
00130
00132
00133
00134 GECODE_KERNEL_EXPORT
00135 void update(Space& home, bool share, CHB& a);
00137 GECODE_KERNEL_EXPORT
00138 ~CHB(void);
00140
00142
00143
00144 double operator [](int i) const;
00146 int size(void) const;
00148 };
00149
00151 template<class View>
00152 class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
00153 protected:
00154 using NaryPropagator<View,PC_GEN_NONE>::x;
00156 class Idx : public Advisor {
00157 protected:
00159 int _info;
00160 public:
00162 Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
00164 Idx(Space& home, bool share, Idx& a);
00166 void mark(void);
00168 void unmark(void);
00170 bool marked(void) const;
00172 int idx(void) const;
00173 };
00175 CHB chb;
00177 Council<Idx> c;
00179 Recorder(Space& home, bool share, Recorder<View>& p);
00180 public:
00182 Recorder(Home home, ViewArray<View>& x, CHB& chb);
00184 virtual Propagator* copy(Space& home, bool share);
00186 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00188 virtual void reschedule(Space& home);
00190 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
00192 virtual void advise(Space& home, Advisor& a);
00194 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00196 virtual size_t dispose(Space& home);
00198 static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
00199 };
00200
00205 template<class Char, class Traits>
00206 std::basic_ostream<Char,Traits>&
00207 operator <<(std::basic_ostream<Char,Traits>& os,
00208 const CHB& a);
00209
00210
00211
00212
00213
00214
00215 template<class View>
00216 forceinline
00217 CHB::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
00218 Council<Idx>& c, int i)
00219 : Advisor(home,p,c), _info(i << 1) {}
00220 template<class View>
00221 forceinline
00222 CHB::Recorder<View>::Idx::Idx(Space& home, bool share, Idx& a)
00223 : Advisor(home,share,a), _info(a._info) {
00224 }
00225 template<class View>
00226 forceinline void
00227 CHB::Recorder<View>::Idx::mark(void) {
00228 _info |= 1;
00229 }
00230 template<class View>
00231 forceinline bool
00232 CHB::Recorder<View>::Idx::marked(void) const {
00233 return (_info & 1) != 0;
00234 }
00235 template<class View>
00236 forceinline void
00237 CHB::Recorder<View>::Idx::unmark(void) {
00238 assert(marked());
00239 _info -= 1;
00240 }
00241 template<class View>
00242 forceinline int
00243 CHB::Recorder<View>::Idx::idx(void) const {
00244 return _info >> 1;
00245 }
00246
00247
00248
00249
00250
00251
00252 template<class View>
00253 forceinline
00254 CHB::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
00255 CHB& chb0)
00256 : NaryPropagator<View,PC_GEN_NONE>(home,x), chb(chb0), c(home) {
00257 home.notice(*this,AP_DISPOSE);
00258 for (int i=x.size(); i--; )
00259 if (!x[i].assigned())
00260 x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
00261 }
00262
00263 template<class View>
00264 forceinline ExecStatus
00265 CHB::Recorder<View>::post(Home home, ViewArray<View>& x, CHB& chb) {
00266 (void) new (home) Recorder<View>(home,x,chb);
00267 return ES_OK;
00268 }
00269
00270
00271
00272
00273
00274
00275 template<class View>
00276 forceinline
00277 CHB::Storage::Storage(Home home, ViewArray<View>& x,
00278 typename
00279 BranchTraits<typename View::VarType>::Merit bm)
00280 : use_cnt(1), n(x.size()), chb(heap.alloc<Info>(x.size())),
00281 nf(0U), alpha(Kernel::Config::chb_alpha_init) {
00282 if (bm) {
00283 for (int i=n; i--; ) {
00284 typename View::VarType xi(x[i].varimp());
00285 chb[i].lf = 0U;
00286 chb[i].qs = bm(home,xi,i);
00287 }
00288 } else {
00289 for (int i=n; i--; ) {
00290 chb[i].lf = 0U;
00291 chb[i].qs = Kernel::Config::chb_qscore_init;
00292 }
00293 }
00294 }
00295 forceinline void
00296 CHB::Storage::bump(void) {
00297 nf++;
00298 if (alpha > Kernel::Config::chb_alpha_limit) {
00299 alpha -= Kernel::Config::chb_alpha_decrement;
00300 }
00301 }
00302 forceinline void
00303 CHB::Storage::update(int i, bool failed) {
00304 if (failed) {
00305 chb[i].lf = nf;
00306 double reward = 1.0 / (nf - chb[i].lf + 1);
00307 chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
00308 } else {
00309 double reward = 0.9 / (nf - chb[i].lf + 1);
00310 chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
00311 }
00312 }
00313 forceinline
00314 CHB::Storage::~Storage(void) {
00315 heap.free<Info>(chb,n);
00316 }
00317
00318
00319
00320
00321
00322
00323
00324 forceinline double
00325 CHB::operator [](int i) const {
00326 assert((i >= 0) && (i < storage->n));
00327 return storage->chb[i].qs;
00328 }
00329 forceinline int
00330 CHB::size(void) const {
00331 return storage->n;
00332 }
00333 forceinline void
00334 CHB::acquire(void) {
00335 storage->m.acquire();
00336 }
00337 forceinline void
00338 CHB::release(void) {
00339 storage->m.release();
00340 }
00341 forceinline void
00342 CHB::bump(void) {
00343 storage->bump();
00344 }
00345 forceinline void
00346 CHB::update(int i, bool failed) {
00347 storage->update(i,failed);
00348 }
00349
00350 forceinline
00351 CHB::CHB(void) : storage(NULL) {}
00352
00353 forceinline
00354 CHB::operator bool(void) const {
00355 return storage != NULL;
00356 }
00357
00358 template<class View>
00359 forceinline
00360 CHB::CHB(Home home, ViewArray<View>& x,
00361 typename BranchTraits<typename View::VarType>::Merit bm) {
00362 assert(storage == NULL);
00363 storage = new Storage(home,x,bm);
00364 (void) Recorder<View>::post(home,x,*this);
00365 }
00366 template<class View>
00367 forceinline void
00368 CHB::init(Home home, ViewArray<View>& x,
00369 typename BranchTraits<typename View::VarType>::Merit bm) {
00370 assert(storage == NULL);
00371 storage = new Storage(home,x,bm);
00372 (void) Recorder<View>::post(home,x,*this);
00373 }
00374
00375 template<class Char, class Traits>
00376 std::basic_ostream<Char,Traits>&
00377 operator <<(std::basic_ostream<Char,Traits>& os,
00378 const CHB& chb) {
00379 std::basic_ostringstream<Char,Traits> s;
00380 s.copyfmt(os); s.width(0);
00381 s << '{';
00382 if (chb.size() > 0) {
00383 s << chb[0];
00384 for (int i=1; i<chb.size(); i++)
00385 s << ", " << chb[i];
00386 }
00387 s << '}';
00388 return os << s.str();
00389 }
00390
00391
00392
00393
00394
00395
00396 template<class View>
00397 forceinline
00398 CHB::Recorder<View>::Recorder(Space& home, bool share, Recorder<View>& p)
00399 : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
00400 chb.update(home, share, p.chb);
00401 c.update(home, share, p.c);
00402 }
00403
00404 template<class View>
00405 Propagator*
00406 CHB::Recorder<View>::copy(Space& home, bool share) {
00407 return new (home) Recorder<View>(home, share, *this);
00408 }
00409
00410 template<class View>
00411 inline size_t
00412 CHB::Recorder<View>::dispose(Space& home) {
00413
00414 home.ignore(*this,AP_DISPOSE);
00415 chb.~CHB();
00416
00417 for (Advisors<Idx> as(c); as(); ++as)
00418 x[as.advisor().idx()].cancel(home,as.advisor(),true);
00419 c.dispose(home);
00420 (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
00421 return sizeof(*this);
00422 }
00423
00424 template<class View>
00425 PropCost
00426 CHB::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
00427 return PropCost::record();
00428 }
00429
00430 template<class View>
00431 void
00432 CHB::Recorder<View>::reschedule(Space& home) {
00433 View::schedule(home,*this,ME_GEN_ASSIGNED);
00434 }
00435
00436 template<class View>
00437 ExecStatus
00438 CHB::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
00439 static_cast<Idx&>(a).mark();
00440 return ES_NOFIX;
00441 }
00442
00443 template<class View>
00444 void
00445 CHB::Recorder<View>::advise(Space&, Advisor& a) {
00446 static_cast<Idx&>(a).mark();
00447 }
00448
00449 template<class View>
00450 ExecStatus
00451 CHB::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
00452
00453 chb.acquire();
00454 if (home.failed()) {
00455 chb.bump();
00456 for (Advisors<Idx> as(c); as(); ++as) {
00457 int i = as.advisor().idx();
00458 if (as.advisor().marked()) {
00459 as.advisor().unmark();
00460 chb.update(i,true);
00461 if (x[i].assigned())
00462 as.advisor().dispose(home,c);
00463 }
00464 }
00465 } else {
00466 for (Advisors<Idx> as(c); as(); ++as) {
00467 int i = as.advisor().idx();
00468 if (as.advisor().marked()) {
00469 as.advisor().unmark();
00470 chb.update(i,false);
00471 if (x[i].assigned())
00472 as.advisor().dispose(home,c);
00473 }
00474 }
00475 }
00476 chb.release();
00477 return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
00478 }
00479
00480
00481 }
00482
00483