Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date: 2017-03-09 09:51:58 +0100 (Thu, 09 Mar 2017) $ by $Author: schulte $
11  * $Revision: 15565 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <cfloat>
39 
40 namespace Gecode {
41 
50  class CHB {
51  protected:
52  template<class View>
53  class Recorder;
55  class Info {
56  public:
58  unsigned long long int lf;
60  double qs;
61  };
63  class Storage : public HeapAllocated {
64  public:
68  unsigned int use_cnt;
70  int n;
74  unsigned long long int nf;
76  double alpha;
78  template<class View>
82  ~Storage(void);
84  void bump(void);
86  void update(int i, bool failed);
87  };
91  void update(int i);
93  void acquire(void);
95  void release(void);
97  void bump(void);
99  void update(int i, bool failed);
100  public:
102 
103 
110  CHB(void);
113  CHB(const CHB& a);
116  CHB& operator =(const CHB& a);
118  template<class View>
119  CHB(Home home, ViewArray<View>& x,
122  template<class View>
123  void init(Home home, ViewArray<View>& x,
126  operator bool(void) const;
130 
132 
135  void update(Space& home, bool share, CHB& a);
138  ~CHB(void);
140 
142 
143  double operator [](int i) const;
146  int size(void) const;
148  };
149 
151  template<class View>
152  class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
153  protected:
156  class Idx : public Advisor {
157  protected:
159  int _info;
160  public:
162  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
164  Idx(Space& home, bool share, Idx& a);
166  void mark(void);
168  void unmark(void);
170  bool marked(void) const;
172  int idx(void) const;
173  };
179  Recorder(Space& home, bool share, Recorder<View>& p);
180  public:
182  Recorder(Home home, ViewArray<View>& x, CHB& chb);
184  virtual Propagator* copy(Space& home, bool share);
186  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
188  virtual void reschedule(Space& home);
190  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
192  virtual void advise(Space& home, Advisor& a);
194  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
196  virtual size_t dispose(Space& home);
198  static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
199  };
200 
205  template<class Char, class Traits>
206  std::basic_ostream<Char,Traits>&
207  operator <<(std::basic_ostream<Char,Traits>& os,
208  const CHB& a);
209 
210 
211  /*
212  * Advisor for chb recorder
213  *
214  */
215  template<class View>
218  Council<Idx>& c, int i)
219  : Advisor(home,p,c), _info(i << 1) {}
220  template<class View>
223  : Advisor(home,share,a), _info(a._info) {
224  }
225  template<class View>
226  forceinline void
228  _info |= 1;
229  }
230  template<class View>
231  forceinline bool
233  return (_info & 1) != 0;
234  }
235  template<class View>
236  forceinline void
238  assert(marked());
239  _info -= 1;
240  }
241  template<class View>
242  forceinline int
244  return _info >> 1;
245  }
246 
247 
248  /*
249  * Posting of chb recorder propagator
250  *
251  */
252  template<class View>
255  CHB& chb0)
256  : NaryPropagator<View,PC_GEN_NONE>(home,x), chb(chb0), c(home) {
257  home.notice(*this,AP_DISPOSE);
258  for (int i=x.size(); i--; )
259  if (!x[i].assigned())
260  x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
261  }
262 
263  template<class View>
266  (void) new (home) Recorder<View>(home,x,chb);
267  return ES_OK;
268  }
269 
270 
271  /*
272  * CHB value storage
273  *
274  */
275  template<class View>
278  typename
280  : use_cnt(1), n(x.size()), chb(heap.alloc<Info>(x.size())),
281  nf(0U), alpha(Kernel::Config::chb_alpha_init) {
282  if (bm) {
283  for (int i=n; i--; ) {
284  typename View::VarType xi(x[i].varimp());
285  chb[i].lf = 0U;
286  chb[i].qs = bm(home,xi,i);
287  }
288  } else {
289  for (int i=n; i--; ) {
290  chb[i].lf = 0U;
292  }
293  }
294  }
295  forceinline void
297  nf++;
300  }
301  }
302  forceinline void
303  CHB::Storage::update(int i, bool failed) {
304  if (failed) {
305  chb[i].lf = nf;
306  double reward = 1.0 / (nf - chb[i].lf + 1);
307  chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
308  } else {
309  double reward = 0.9 / (nf - chb[i].lf + 1);
310  chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
311  }
312  }
315  heap.free<Info>(chb,n);
316  }
317 
318 
319  /*
320  * CHB
321  *
322  */
323 
324  forceinline double
325  CHB::operator [](int i) const {
326  assert((i >= 0) && (i < storage->n));
327  return storage->chb[i].qs;
328  }
329  forceinline int
330  CHB::size(void) const {
331  return storage->n;
332  }
333  forceinline void
334  CHB::acquire(void) {
335  storage->m.acquire();
336  }
337  forceinline void
338  CHB::release(void) {
339  storage->m.release();
340  }
341  forceinline void
342  CHB::bump(void) {
343  storage->bump();
344  }
345  forceinline void
346  CHB::update(int i, bool failed) {
347  storage->update(i,failed);
348  }
349 
351  CHB::CHB(void) : storage(NULL) {}
352 
354  CHB::operator bool(void) const {
355  return storage != NULL;
356  }
357 
358  template<class View>
362  assert(storage == NULL);
363  storage = new Storage(home,x,bm);
364  (void) Recorder<View>::post(home,x,*this);
365  }
366  template<class View>
367  forceinline void
370  assert(storage == NULL);
371  storage = new Storage(home,x,bm);
372  (void) Recorder<View>::post(home,x,*this);
373  }
374 
375  template<class Char, class Traits>
376  std::basic_ostream<Char,Traits>&
377  operator <<(std::basic_ostream<Char,Traits>& os,
378  const CHB& chb) {
379  std::basic_ostringstream<Char,Traits> s;
380  s.copyfmt(os); s.width(0);
381  s << '{';
382  if (chb.size() > 0) {
383  s << chb[0];
384  for (int i=1; i<chb.size(); i++)
385  s << ", " << chb[i];
386  }
387  s << '}';
388  return os << s.str();
389  }
390 
391 
392  /*
393  * Propagation for chb recorder
394  *
395  */
396  template<class View>
399  : NaryPropagator<View,PC_GEN_NONE>(home,share,p) {
400  chb.update(home, share, p.chb);
401  c.update(home, share, p.c);
402  }
403 
404  template<class View>
405  Propagator*
406  CHB::Recorder<View>::copy(Space& home, bool share) {
407  return new (home) Recorder<View>(home, share, *this);
408  }
409 
410  template<class View>
411  inline size_t
413  // Delete access to chb information
414  home.ignore(*this,AP_DISPOSE);
415  chb.~CHB();
416  // Cancel remaining advisors
417  for (Advisors<Idx> as(c); as(); ++as)
418  x[as.advisor().idx()].cancel(home,as.advisor(),true);
419  c.dispose(home);
421  return sizeof(*this);
422  }
423 
424  template<class View>
425  PropCost
427  return PropCost::record();
428  }
429 
430  template<class View>
431  void
433  View::schedule(home,*this,ME_GEN_ASSIGNED);
434  }
435 
436  template<class View>
437  ExecStatus
439  static_cast<Idx&>(a).mark();
440  return ES_NOFIX;
441  }
442 
443  template<class View>
444  void
446  static_cast<Idx&>(a).mark();
447  }
448 
449  template<class View>
450  ExecStatus
452  // Lock chb information
453  chb.acquire();
454  if (home.failed()) {
455  chb.bump();
456  for (Advisors<Idx> as(c); as(); ++as) {
457  int i = as.advisor().idx();
458  if (as.advisor().marked()) {
459  as.advisor().unmark();
460  chb.update(i,true);
461  if (x[i].assigned())
462  as.advisor().dispose(home,c);
463  }
464  }
465  } else {
466  for (Advisors<Idx> as(c); as(); ++as) {
467  int i = as.advisor().idx();
468  if (as.advisor().marked()) {
469  as.advisor().unmark();
470  chb.update(i,false);
471  if (x[i].assigned())
472  as.advisor().dispose(home,c);
473  }
474  }
475  }
476  chb.release();
477  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
478  }
479 
480 
481 }
482 
483 // STATISTICS: kernel-branch
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:154
bool marked(void *p)
Check whether p is marked.
CHB & operator=(const CHB &a)
Assignment operator.
Definition: chb.cpp:54
Council of advisors
Definition: core.hpp:232
unsigned int use_cnt
How many references exist for this object.
Definition: chb.hpp:68
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
int n
Number of chb values.
Definition: chb.hpp:70
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
void bump(void)
Bump failure count and alpha.
Definition: chb.hpp:296
Actor must always be disposed.
Definition: core.hpp:630
Info * chb
CHB information.
Definition: chb.hpp:72
Object for storing chb information.
Definition: chb.hpp:63
Advisor with index and change information.
Definition: chb.hpp:156
static ExecStatus post(Home home, ViewArray< View > &x, CHB &chb)
Post chb recorder propagator.
Definition: chb.hpp:265
int idx(void) const
Get index of view.
Definition: chb.hpp:243
void bump(void)
Bump failure count and alpha.
Definition: chb.hpp:342
void update(int i)
Update chb value at position i.
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition: core.hpp:149
double alpha
Alpha value.
Definition: chb.hpp:76
ViewArray< View > x
Array of views.
Definition: propagator.hpp:152
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
Propagator for recording chb information.
Definition: chb.hpp:53
Base-class for propagators.
Definition: core.hpp:1092
virtual void reschedule(Space &home)
Schedule function.
Definition: chb.hpp:432
Base-class for advisors.
Definition: core.hpp:1294
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4810
Class to iterate over advisors of a council.
Definition: core.hpp:233
void * mark(void *p)
Return marked pointer for unmarked pointer p.
int size(void) const
Return number of chb values.
Definition: chb.hpp:330
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: chb.hpp:451
Propagation has computed fixpoint.
Definition: core.hpp:545
~Storage(void)
Delete object.
Definition: chb.hpp:314
Computation spaces.
Definition: core.hpp:1748
void acquire(void)
Acquire mutex.
Definition: chb.hpp:334
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
Gecode::IntSet d(v, 7)
void release(void)
Release the mutex.
Definition: none.hpp:52
CHB(void)
Construct as not yet intialized.
Definition: chb.hpp:351
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
void update(int i, bool failed)
Update chb information at position i.
Definition: chb.hpp:303
unsigned long long int nf
Number of failures.
Definition: chb.hpp:74
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
void mark(void)
Mark advisor as modified.
Definition: chb.hpp:227
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: chb.hpp:217
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4095
Class for CHB management.
Definition: chb.hpp:50
Recorder(Space &home, bool share, Recorder< View > &p)
Constructor for cloning p.
Definition: chb.hpp:398
View information.
Definition: chb.hpp:55
const double chb_alpha_init
Initial value for alpha in CHB.
Definition: kernel.hh:108
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:368
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1105
n-ary propagator
Definition: propagator.hpp:149
~CHB(void)
Destructor.
Definition: chb.cpp:74
double operator[](int i) const
Return chb value at position i.
Definition: chb.hpp:325
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: chb.hpp:438
#define GECODE_KERNEL_EXPORT
Definition: kernel.hh:74
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
View arrays.
Definition: array.hpp:234
CHB chb
Access to chb information.
Definition: chb.hpp:175
Council< Idx > c
The advisor council.
Definition: chb.hpp:177
void release(void)
Release mutex.
Definition: chb.hpp:338
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
static const CHB def
Default (empty) chb information.
Definition: chb.hpp:128
double qs
Q-score.
Definition: chb.hpp:60
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
bool marked(void) const
Whether advisor&#39;s view has been marked.
Definition: chb.hpp:232
Generic domain change information to be supplied to advisors.
Definition: core.hpp:281
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
Propagation cost.
Definition: core.hpp:554
Storage(Home home, ViewArray< View > &x, typename BranchTraits< typename View::VarType >::Merit bm)
Allocate CHB info.
Definition: chb.hpp:277
unsigned long long int lf
Last failure.
Definition: chb.hpp:58
ExecStatus
Definition: core.hpp:540
Heap heap
The single global heap.
Definition: heap.cpp:48
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:173
const double chb_alpha_limit
Limit for decreasing alpha in CHB.
Definition: kernel.hh:110
Storage * storage
Pointer to storage object.
Definition: chb.hpp:89
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
int _info
Index and mark information.
Definition: chb.hpp:159
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: chb.hpp:412
const double chb_alpha_decrement
Alpha decrement in CHB.
Definition: kernel.hh:112
Gecode toplevel namespace
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition: chb.hpp:426
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
Base class for heap allocated objects.
Definition: heap.hpp:344
const double chb_qscore_init
Initial value for Q-score in CHB.
Definition: kernel.hh:114
Traits for branching.
Support::Mutex m
Mutex to synchronize globally shared access.
Definition: chb.hpp:66
void unmark(void)
Mark advisor as unmodified.
Definition: chb.hpp:237
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
virtual Propagator * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: chb.hpp:406