Generated on Thu Apr 5 2018 19:44:19 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$ by $Author$
11  * $Revision$
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 : public SharedHandle {
51  protected:
52  template<class View>
53  class Recorder;
55  class Info {
56  public:
58  unsigned long long int lf;
60  double qs;
61  };
64  public:
68  int n;
70  unsigned long int nf;
72  double alpha;
76  template<class View>
81  ~Storage(void);
83  void bump(void);
85  void update(int i, bool failed);
86  };
88  Storage& object(void) const;
90  void object(Storage& o);
92  void update(int i);
94  void acquire(void);
96  void release(void);
98  void bump(void);
100  void update(int i, bool failed);
101  public:
103 
104 
111  CHB(void);
114  CHB(const CHB& a);
117  CHB& operator =(const CHB& a);
119  template<class View>
120  CHB(Home home, ViewArray<View>& x,
123  template<class View>
124  void init(Home home, ViewArray<View>& x,
129 
132  ~CHB(void);
133 
135 
136  double operator [](int i) const;
139  int size(void) const;
141  };
142 
144  template<class View>
145  class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
146  protected:
149  class Idx : public Advisor {
150  protected:
152  int _info;
153  public:
155  Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
157  Idx(Space& home, Idx& a);
159  void mark(void);
161  void unmark(void);
163  bool marked(void) const;
165  int idx(void) const;
166  };
172  Recorder(Space& home, Recorder<View>& p);
173  public:
175  Recorder(Home home, ViewArray<View>& x, CHB& chb);
177  virtual Propagator* copy(Space& home);
179  virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
181  virtual void reschedule(Space& home);
183  virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
185  virtual void advise(Space& home, Advisor& a);
187  virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
189  virtual size_t dispose(Space& home);
191  static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
192  };
193 
198  template<class Char, class Traits>
199  std::basic_ostream<Char,Traits>&
200  operator <<(std::basic_ostream<Char,Traits>& os,
201  const CHB& a);
202 
203 
204  /*
205  * Advisor for chb recorder
206  *
207  */
208  template<class View>
211  Council<Idx>& c, int i)
212  : Advisor(home,p,c), _info(i << 1) {}
213  template<class View>
216  : Advisor(home,a), _info(a._info) {
217  }
218  template<class View>
219  forceinline void
221  _info |= 1;
222  }
223  template<class View>
224  forceinline bool
226  return (_info & 1) != 0;
227  }
228  template<class View>
229  forceinline void
231  assert(marked());
232  _info -= 1;
233  }
234  template<class View>
235  forceinline int
237  return _info >> 1;
238  }
239 
240 
241  /*
242  * Posting of chb recorder propagator
243  *
244  */
245  template<class View>
248  CHB& chb0)
249  : NaryPropagator<View,PC_GEN_NONE>(home,x), chb(chb0), c(home) {
250  home.notice(*this,AP_DISPOSE);
251  for (int i=x.size(); i--; )
252  if (!x[i].assigned())
253  x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
254  }
255 
256  template<class View>
259  (void) new (home) Recorder<View>(home,x,chb);
260  return ES_OK;
261  }
262 
263 
264  /*
265  * CHB value storage
266  *
267  */
268  template<class View>
271  typename
273  : n(x.size()), nf(0U), alpha(Kernel::Config::chb_alpha_init),
274  chb(heap.alloc<Info>(x.size())) {
275  if (bm) {
276  for (int i=n; i--; ) {
277  typename View::VarType xi(x[i].varimp());
278  chb[i].lf = 0U;
279  chb[i].qs = bm(home,xi,i);
280  }
281  } else {
282  for (int i=n; i--; ) {
283  chb[i].lf = 0U;
285  }
286  }
287  }
288  forceinline void
290  nf++;
293  }
294  }
295  forceinline void
296  CHB::Storage::update(int i, bool failed) {
297  if (failed) {
298  chb[i].lf = nf;
299  double reward = 1.0 / (nf - chb[i].lf + 1);
300  chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
301  } else {
302  double reward = 0.9 / (nf - chb[i].lf + 1);
303  chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
304  }
305  }
306 
307 
308  /*
309  * CHB
310  *
311  */
312 
314  CHB::object(void) const {
315  return static_cast<CHB::Storage&>(*SharedHandle::object());
316  }
317 
318  forceinline void
321  }
322 
323  forceinline double
324  CHB::operator [](int i) const {
325  assert((i >= 0) && (i < object().n));
326  return object().chb[i].qs;
327  }
328  forceinline int
329  CHB::size(void) const {
330  return object().n;
331  }
332  forceinline void
333  CHB::acquire(void) {
334  object().m.acquire();
335  }
336  forceinline void
337  CHB::release(void) {
338  object().m.release();
339  }
340  forceinline void
341  CHB::bump(void) {
342  object().bump();
343  }
344  forceinline void
345  CHB::update(int i, bool failed) {
346  object().update(i,failed);
347  }
348 
350  CHB::CHB(void) {}
351 
352  template<class View>
356  assert(!*this);
357  object(*new Storage(home,x,bm));
358  (void) Recorder<View>::post(home,x,*this);
359  }
360  template<class View>
361  forceinline void
364  assert(!*this);
365  object(*new Storage(home,x,bm));
366  (void) Recorder<View>::post(home,x,*this);
367  }
368 
369  template<class Char, class Traits>
370  std::basic_ostream<Char,Traits>&
371  operator <<(std::basic_ostream<Char,Traits>& os,
372  const CHB& chb) {
373  std::basic_ostringstream<Char,Traits> s;
374  s.copyfmt(os); s.width(0);
375  s << '{';
376  if (chb.size() > 0) {
377  s << chb[0];
378  for (int i=1; i<chb.size(); i++)
379  s << ", " << chb[i];
380  }
381  s << '}';
382  return os << s.str();
383  }
384 
385 
386  /*
387  * Propagation for chb recorder
388  *
389  */
390  template<class View>
393  : NaryPropagator<View,PC_GEN_NONE>(home,p), chb(p.chb) {
394  c.update(home, p.c);
395  }
396 
397  template<class View>
398  Propagator*
400  return new (home) Recorder<View>(home, *this);
401  }
402 
403  template<class View>
404  inline size_t
406  // Delete access to chb information
407  home.ignore(*this,AP_DISPOSE);
408  chb.~CHB();
409  // Cancel remaining advisors
410  for (Advisors<Idx> as(c); as(); ++as)
411  x[as.advisor().idx()].cancel(home,as.advisor(),true);
412  c.dispose(home);
414  return sizeof(*this);
415  }
416 
417  template<class View>
418  PropCost
420  return PropCost::record();
421  }
422 
423  template<class View>
424  void
426  View::schedule(home,*this,ME_GEN_ASSIGNED);
427  }
428 
429  template<class View>
430  ExecStatus
432  static_cast<Idx&>(a).mark();
433  return ES_NOFIX;
434  }
435 
436  template<class View>
437  void
439  static_cast<Idx&>(a).mark();
440  }
441 
442  template<class View>
443  ExecStatus
445  // Lock chb information
446  chb.acquire();
447  if (home.failed()) {
448  chb.bump();
449  for (Advisors<Idx> as(c); as(); ++as) {
450  int i = as.advisor().idx();
451  if (as.advisor().marked()) {
452  as.advisor().unmark();
453  chb.update(i,true);
454  if (x[i].assigned())
455  as.advisor().dispose(home,c);
456  }
457  }
458  } else {
459  for (Advisors<Idx> as(c); as(); ++as) {
460  int i = as.advisor().idx();
461  if (as.advisor().marked()) {
462  as.advisor().unmark();
463  chb.update(i,false);
464  if (x[i].assigned())
465  as.advisor().dispose(home,c);
466  }
467  }
468  }
469  chb.release();
470  return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
471  }
472 
473 
474 }
475 
476 // STATISTICS: kernel-branch
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition: core.hpp:76
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:156
The shared handle.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
int n
Number of chb values.
Definition: chb.hpp:68
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
void bump(void)
Bump failure count and alpha.
Definition: chb.hpp:289
Actor must always be disposed.
Definition: core.hpp:554
Info * chb
CHB information.
Definition: chb.hpp:74
Object for storing chb information.
Definition: chb.hpp:63
Advisor with index and change information.
Definition: chb.hpp:149
static ExecStatus post(Home home, ViewArray< View > &x, CHB &chb)
Post chb recorder propagator.
Definition: chb.hpp:258
int idx(void) const
Get index of view.
Definition: chb.hpp:236
void bump(void)
Bump failure count and alpha.
Definition: chb.hpp:341
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:71
double alpha
Alpha value.
Definition: chb.hpp:72
ViewArray< View > x
Array of views.
Definition: pattern.hpp:149
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:1016
virtual void reschedule(Space &home)
Schedule function.
Definition: chb.hpp:425
Base-class for advisors.
Definition: core.hpp:1218
static PropCost record(void)
For recording information (no propagation allowed)
Definition: core.hpp:4612
Class to iterate over advisors of a council.
Definition: core.hpp:157
void * mark(void *p)
Return marked pointer for unmarked pointer p.
int size(void) const
Return number of chb values.
Definition: chb.hpp:329
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: chb.hpp:444
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
Computation spaces.
Definition: core.hpp:1668
void acquire(void)
Acquire mutex.
Definition: chb.hpp:333
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:105
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:350
Gecode::FloatVal c(-8, 8)
void update(int i, bool failed)
Update chb information at position i.
Definition: chb.hpp:296
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Storage & object(void) const
Return object of correct type.
Definition: chb.hpp:314
Gecode::IntArgs i(4, 1, 2, 3, 4)
void mark(void)
Mark advisor as modified.
Definition: chb.hpp:220
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
SharedHandle::Object * object(void) const
Access to the shared object.
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition: chb.hpp:210
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3914
Class for CHB management.
Definition: chb.hpp:50
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:362
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1029
n-ary propagator
Definition: pattern.hpp:146
~CHB(void)
Destructor.
Definition: chb.cpp:59
double operator[](int i) const
Return chb value at position i.
Definition: chb.hpp:324
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition: chb.hpp:431
#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:228
CHB chb
Access to chb information.
Definition: chb.hpp:168
Council< Idx > c
The advisor council.
Definition: chb.hpp:170
void release(void)
Release mutex.
Definition: chb.hpp:337
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3139
static const CHB def
Default (empty) chb information.
Definition: chb.hpp:127
double qs
Q-score.
Definition: chb.hpp:60
bool marked(void) const
Whether advisor&#39;s view has been marked.
Definition: chb.hpp:225
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:3944
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Propagation cost.
Definition: core.hpp:478
Storage(Home home, ViewArray< View > &x, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize CHB info.
Definition: chb.hpp:270
unsigned long long int lf
Last failure.
Definition: chb.hpp:58
ExecStatus
Definition: core.hpp:464
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
const double chb_alpha_limit
Limit for decreasing alpha in CHB.
Definition: kernel.hh:110
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
Propagation has not computed fixpoint.
Definition: core.hpp:467
int _info
Index and mark information.
Definition: chb.hpp:152
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: chb.hpp:405
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition: chb.hpp:392
const double chb_alpha_decrement
Alpha decrement in CHB.
Definition: kernel.hh:112
Gecode toplevel namespace
#define GECODE_VTABLE_EXPORT
Definition: support.hh:76
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition: chb.hpp:419
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:1203
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition: chb.hpp:399
const double chb_qscore_init
Initial value for Q-score in CHB.
Definition: kernel.hh:114
Traits for branching.
Definition: traits.hpp:59
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition: chb.hpp:66
void unmark(void)
Mark advisor as unmodified.
Definition: chb.hpp:230
unsigned long int nf
Number of failures.
Definition: chb.hpp:70
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:142