Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
chb.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2017
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <cfloat>
35 
36 namespace Gecode {
37 
46  class CHB : public SharedHandle {
47  protected:
48  template<class View>
49  class Recorder;
51  class Info {
52  public:
54  unsigned long long int lf;
56  double qs;
57  };
60  public:
64  int n;
66  unsigned long int nf;
68  double alpha;
72  template<class View>
77  ~Storage(void);
79  void bump(void);
81  void update(int i, bool failed);
82  };
84  Storage& object(void) const;
86  void object(Storage& o);
88  void update(int i);
90  void acquire(void);
92  void release(void);
94  void bump(void);
96  void update(int i, bool failed);
97  public:
99 
100 
107  CHB(void);
110  CHB(const CHB& a);
113  CHB& operator =(const CHB& a);
115  template<class View>
116  CHB(Home home, ViewArray<View>& x,
119  template<class View>
120  void init(Home home, ViewArray<View>& x,
125 
128  ~CHB(void);
129 
131 
132  double operator [](int i) const;
135  int size(void) const;
137  };
138 
140  template<class View>
141  class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
142  protected:
145  class Idx : public Advisor {
146  protected:
148  int _info;
149  public:
151  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
153  Idx(Space& home, Idx& a);
155  void mark(void);
157  void unmark(void);
159  bool marked(void) const;
161  int idx(void) const;
162  };
168  Recorder(Space& home, Recorder<View>& p);
169  public:
171  Recorder(Home home, ViewArray<View>& x, CHB& chb);
173  virtual Propagator* copy(Space& home);
175  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
177  virtual void reschedule(Space& home);
179  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
181  virtual void advise(Space& home, Advisor& a);
183  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
185  virtual size_t dispose(Space& home);
187  static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
188  };
189 
194  template<class Char, class Traits>
195  std::basic_ostream<Char,Traits>&
196  operator <<(std::basic_ostream<Char,Traits>& os,
197  const CHB& a);
198 
199 
200  /*
201  * Advisor for chb recorder
202  *
203  */
204  template<class View>
207  Council<Idx>& c, int i)
208  : Advisor(home,p,c), _info(i << 1) {}
209  template<class View>
212  : Advisor(home,a), _info(a._info) {
213  }
214  template<class View>
215  forceinline void
217  _info |= 1;
218  }
219  template<class View>
220  forceinline bool
222  return (_info & 1) != 0;
223  }
224  template<class View>
225  forceinline void
227  assert(marked());
228  _info -= 1;
229  }
230  template<class View>
231  forceinline int
233  return _info >> 1;
234  }
235 
236 
237  /*
238  * Posting of chb recorder propagator
239  *
240  */
241  template<class View>
244  CHB& chb0)
245  : NaryPropagator<View,PC_GEN_NONE>(home,x), chb(chb0), c(home) {
246  home.notice(*this,AP_DISPOSE);
247  for (int i=0; i<x.size(); i++)
248  if (!x[i].assigned())
249  x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
250  }
251 
252  template<class View>
255  (void) new (home) Recorder<View>(home,x,chb);
256  return ES_OK;
257  }
258 
259 
260  /*
261  * CHB value storage
262  *
263  */
264  template<class View>
267  typename
269  : n(x.size()), nf(0U), alpha(Kernel::Config::chb_alpha_init),
270  chb(heap.alloc<Info>(x.size())) {
271  if (bm) {
272  for (int i=0; i<n; i++) {
273  typename View::VarType xi(x[i].varimp());
274  chb[i].lf = 0U;
275  chb[i].qs = bm(home,xi,i);
276  }
277  } else {
278  for (int i=0; i<n; i++) {
279  chb[i].lf = 0U;
281  }
282  }
283  }
284  forceinline void
286  nf++;
287  if (alpha > Kernel::Config::chb_alpha_limit) {
289  }
290  }
291  forceinline void
292  CHB::Storage::update(int i, bool failed) {
293  if (failed) {
294  chb[i].lf = nf;
295  double reward = 1.0 / (nf - chb[i].lf + 1);
296  chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
297  } else {
298  double reward = 0.9 / (nf - chb[i].lf + 1);
299  chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
300  }
301  }
302 
303 
304  /*
305  * CHB
306  *
307  */
308 
310  CHB::object(void) const {
311  return static_cast<CHB::Storage&>(*SharedHandle::object());
312  }
313 
314  forceinline void
317  }
318 
319  forceinline double
320  CHB::operator [](int i) const {
321  assert((i >= 0) && (i < object().n));
322  return object().chb[i].qs;
323  }
324  forceinline int
325  CHB::size(void) const {
326  return object().n;
327  }
328  forceinline void
329  CHB::acquire(void) {
330  object().m.acquire();
331  }
332  forceinline void
333  CHB::release(void) {
334  object().m.release();
335  }
336  forceinline void
337  CHB::bump(void) {
338  object().bump();
339  }
340  forceinline void
341  CHB::update(int i, bool failed) {
342  object().update(i,failed);
343  }
344 
346  CHB::CHB(void) {}
347 
348  template<class View>
352  assert(!*this);
353  object(*new Storage(home,x,bm));
354  (void) Recorder<View>::post(home,x,*this);
355  }
356  template<class View>
357  forceinline void
360  assert(!*this);
361  object(*new Storage(home,x,bm));
362  (void) Recorder<View>::post(home,x,*this);
363  }
364 
365  template<class Char, class Traits>
366  std::basic_ostream<Char,Traits>&
367  operator <<(std::basic_ostream<Char,Traits>& os,
368  const CHB& chb) {
369  std::basic_ostringstream<Char,Traits> s;
370  s.copyfmt(os); s.width(0);
371  s << '{';
372  if (chb.size() > 0) {
373  s << chb[0];
374  for (int i=1; i<chb.size(); i++)
375  s << ", " << chb[i];
376  }
377  s << '}';
378  return os << s.str();
379  }
380 
381 
382  /*
383  * Propagation for chb recorder
384  *
385  */
386  template<class View>
389  : NaryPropagator<View,PC_GEN_NONE>(home,p), chb(p.chb) {
390  c.update(home, p.c);
391  }
392 
393  template<class View>
394  Propagator*
396  return new (home) Recorder<View>(home, *this);
397  }
398 
399  template<class View>
400  inline size_t
402  // Delete access to chb information
403  home.ignore(*this,AP_DISPOSE);
404  chb.~CHB();
405  // Cancel remaining advisors
406  for (Advisors<Idx> as(c); as(); ++as)
407  x[as.advisor().idx()].cancel(home,as.advisor(),true);
408  c.dispose(home);
410  return sizeof(*this);
411  }
412 
413  template<class View>
414  PropCost
416  return PropCost::record();
417  }
418 
419  template<class View>
420  void
422  View::schedule(home,*this,ME_GEN_ASSIGNED);
423  }
424 
425  template<class View>
426  ExecStatus
428  static_cast<Idx&>(a).mark();
429  return ES_NOFIX;
430  }
431 
432  template<class View>
433  void
435  static_cast<Idx&>(a).mark();
436  }
437 
438  template<class View>
439  ExecStatus
441  // Lock chb information
442  chb.acquire();
443  if (home.failed()) {
444  chb.bump();
445  for (Advisors<Idx> as(c); as(); ++as) {
446  int i = as.advisor().idx();
447  if (as.advisor().marked()) {
448  as.advisor().unmark();
449  chb.update(i,true);
450  if (x[i].assigned())
451  as.advisor().dispose(home,c);
452  }
453  }
454  } else {
455  for (Advisors<Idx> as(c); as(); ++as) {
456  int i = as.advisor().idx();
457  if (as.advisor().marked()) {
458  as.advisor().unmark();
459  chb.update(i,false);
460  if (x[i].assigned())
461  as.advisor().dispose(home,c);
462  }
463  }
464  }
465  chb.release();
466  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
467  }
468 
469 
470 }
471 
472 // STATISTICS: kernel-branch
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:69
Post propagator for SetVar x
Definition: set.hh:767
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4765
void update(int i)
Update chb value at position i.
unsigned long long int lf
Last failure.
Definition: chb.hpp:54
#define GECODE_VTABLE_EXPORT
Definition: support.hh:72
double qs
Q-score.
Definition: chb.hpp:56
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:42
int _info
Index and mark information.
Definition: chb.hpp:148
static ExecStatus post(Home home, ViewArray< View > &x, CHB &chb)
Post chb recorder propagator.
Definition: chb.hpp:254
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition: chb.hpp:415
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: chb.hpp:440
const double chb_alpha_limit
Limit for decreasing alpha in CHB.
Definition: kernel.hh:106
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Class for CHB management.
Definition: chb.hpp:46
Class to iterate over advisors of a council.
Definition: core.hpp:156
static const CHB def
Default (empty) chb information.
Definition: chb.hpp:123
SharedHandle::Object * object(void) const
Access to the shared object.
Advisor with index and change information.
Definition: chb.hpp:145
virtual void reschedule(Space &home)
Schedule function.
Definition: chb.hpp:421
int size(void) const
Return number of chb values.
Definition: chb.hpp:325
const double chb_qscore_init
Initial value for Q-score in CHB.
Definition: kernel.hh:110
The shared object.
Computation spaces.
Definition: core.hpp:1742
bool marked(void) const
Whether advisor's view has been marked.
Definition: chb.hpp:221
void release(void)
Release mutex.
Definition: chb.hpp:333
ViewArray< View > x
Array of views.
Definition: pattern.hpp:145
void unmark(void)
Mark advisor as unmodified.
Definition: chb.hpp:226
void bump(void)
Bump failure count and alpha.
Definition: chb.hpp:337
Traits for branching.
Definition: traits.hpp:55
Gecode toplevel namespace
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: chb.hpp:427
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: chb.hpp:401
Base-class for propagators.
Definition: core.hpp:1064
Object for storing chb information.
Definition: chb.hpp:59
int n
Number of chb values.
Definition: chb.hpp:64
Storage(Home home, ViewArray< View > &x, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize CHB info.
Definition: chb.hpp:266
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: chb.hpp:395
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Storage & object(void) const
Return object of correct type.
Definition: chb.hpp:310
Home class for posting propagators
Definition: core.hpp:856
Actor must always be disposed.
Definition: core.hpp:562
double alpha
Alpha value.
Definition: chb.hpp:68
CHB(void)
Construct as not yet intialized.
Definition: chb.hpp:346
n-ary propagator
Definition: pattern.hpp:142
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: chb.hpp:206
View information.
Definition: chb.hpp:51
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1075
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const CHB &a)
Print chb values enclosed in curly brackets.
Definition: chb.hpp:367
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:70
~CHB(void)
Destructor.
Definition: chb.cpp:55
const double chb_alpha_init
Initial value for alpha in CHB.
Definition: kernel.hh:104
void mark(void)
Mark advisor as modified.
Definition: chb.hpp:216
const double chb_alpha_decrement
Alpha decrement in CHB.
Definition: kernel.hh:108
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition: chb.hpp:62
Heap heap
The single global heap.
Definition: heap.cpp:44
Council< Idx > c
The advisor council.
Definition: chb.hpp:166
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
Propagation cost.
Definition: core.hpp:486
Council of advisors
Definition: core.hpp:155
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Propagator for recording chb information.
Definition: chb.hpp:49
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1292
Propagation has computed fixpoint.
Definition: core.hpp:477
int idx(void) const
Get index of view.
Definition: chb.hpp:232
CHB & operator=(const CHB &a)
Assignment operator.
Definition: chb.cpp:50
#define forceinline
Definition: config.hpp:185
Info * chb
CHB information.
Definition: chb.hpp:70
double operator[](int i) const
Return chb value at position i.
Definition: chb.hpp:320
CHB chb
Access to chb information.
Definition: chb.hpp:164
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
The shared handle.
Gecode::FloatVal c(-8, 8)
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition: chb.hpp:388
View arrays.
Definition: array.hpp:253
unsigned long int nf
Number of failures.
Definition: chb.hpp:66
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:74
void update(int i, bool failed)
Update chb information at position i.
Definition: chb.hpp:292
void release(void)
Release the mutex.
Definition: none.hpp:48
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
void acquire(void)
Acquire mutex.
Definition: chb.hpp:329
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Propagation has not computed fixpoint.
Definition: core.hpp:475
Gecode::IntArgs i({1, 2, 3, 4})
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
void init(Home home, ViewArray< View > &x, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize for views x and Q-score as defined by bm.
Definition: chb.hpp:358
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition: val-sel.hpp:39
bool marked(void *p)
Check whether p is marked.
void bump(void)
Bump failure count and alpha.
Definition: chb.hpp:285
ExecStatus
Definition: core.hpp:472