Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
36namespace 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
133 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:
143 using NaryPropagator<View,PC_GEN_NONE>::x;
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 };
169 public:
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++;
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
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
330 object().m.acquire();
331 }
332 forceinline 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>
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>
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>
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>
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
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
Base-class for advisors.
Definition core.hpp:1292
Class to iterate over advisors of a council.
Definition core.hpp:1266
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Traits for branching.
Definition traits.hpp:55
View information.
Definition chb.hpp:51
unsigned long long int lf
Last failure.
Definition chb.hpp:54
double qs
Q-score.
Definition chb.hpp:56
Advisor with index and change information.
Definition chb.hpp:145
void unmark(void)
Mark advisor as unmodified.
Definition chb.hpp:226
bool marked(void) const
Whether advisor's view has been marked.
Definition chb.hpp:221
int idx(void) const
Get index of view.
Definition chb.hpp:232
void mark(void)
Mark advisor as modified.
Definition chb.hpp:216
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition chb.hpp:206
int _info
Index and mark information.
Definition chb.hpp:148
Propagator for recording chb information.
Definition chb.hpp:141
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition chb.hpp:415
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition chb.hpp:388
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition chb.hpp:401
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition chb.hpp:395
Council< Idx > c
The advisor council.
Definition chb.hpp:166
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition chb.hpp:440
virtual void reschedule(Space &home)
Schedule function.
Definition chb.hpp:421
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition chb.hpp:427
static ExecStatus post(Home home, ViewArray< View > &x, CHB &chb)
Post chb recorder propagator.
Definition chb.hpp:254
CHB chb
Access to chb information.
Definition chb.hpp:164
Object for storing chb information.
Definition chb.hpp:59
int n
Number of chb values.
Definition chb.hpp:64
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition chb.hpp:62
void bump(void)
Bump failure count and alpha.
Definition chb.hpp:285
void update(int i, bool failed)
Update chb information at position i.
Definition chb.hpp:292
Info * chb
CHB information.
Definition chb.hpp:70
Storage(Home home, ViewArray< View > &x, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize CHB info.
Definition chb.hpp:266
double alpha
Alpha value.
Definition chb.hpp:68
unsigned long int nf
Number of failures.
Definition chb.hpp:66
Class for CHB management.
Definition chb.hpp:46
void update(int i)
Update chb value at position i.
CHB(void)
Construct as not yet intialized.
Definition chb.hpp:346
~CHB(void)
Destructor.
Definition chb.cpp:55
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
int size(void) const
Return number of chb values.
Definition chb.hpp:325
Storage & object(void) const
Return object of correct type.
Definition chb.hpp:310
CHB & operator=(const CHB &a)
Assignment operator.
Definition chb.cpp:50
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
void bump(void)
Bump failure count and alpha.
Definition chb.hpp:337
void release(void)
Release mutex.
Definition chb.hpp:333
double operator[](int i) const
Return chb value at position i.
Definition chb.hpp:320
static const CHB def
Default (empty) chb information.
Definition chb.hpp:123
void acquire(void)
Acquire mutex.
Definition chb.hpp:329
Council of advisors
Definition core.hpp:1241
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
n-ary propagator
Definition pattern.hpp:142
Propagation cost.
Definition core.hpp:486
static PropCost record(void)
For recording information (no propagation allowed)
Definition core.hpp:4765
Base-class for propagators.
Definition core.hpp:1064
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
The shared handle.
SharedHandle::Object * object(void) const
Access to the shared object.
Computation spaces.
Definition core.hpp:1742
struct Gecode::Space::@61::@63 c
Data available only during copying.
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
void release(void)
Release the mutex.
Definition none.hpp:48
void acquire(void)
Acquire the mutex and possibly block.
Definition none.hpp:42
View arrays.
Definition array.hpp:253
Heap heap
The single global heap.
Definition heap.cpp:44
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
const double chb_alpha_decrement
Alpha decrement in CHB.
Definition kernel.hh:108
const double chb_qscore_init
Initial value for Q-score in CHB.
Definition kernel.hh:110
const double chb_alpha_limit
Limit for decreasing alpha in CHB.
Definition kernel.hh:106
Gecode toplevel namespace
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition val-sel.hpp:39
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
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
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience)
Definition core.hpp:74
#define forceinline
Definition config.hpp:187
#define GECODE_VTABLE_EXPORT
Definition support.hh:72