this repo has no description
dekker.one
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
38 /**
39 * \brief Class for CHB management
40 *
41 * The idea is taken from: Exponential Recency Weighted Average
42 * Branching Heuristic for SAT Solvers, Jia Hui Liang, Vijay Ganesh,
43 * Pascal Poupart, Krzysztof Czarnecki, AAAI 2016, pages 3434-3440.
44 *
45 */
46 class CHB : public SharedHandle {
47 protected:
48 template<class View>
49 class Recorder;
50 /// View information
51 class Info {
52 public:
53 /// Last failure
54 unsigned long long int lf;
55 /// Q-score
56 double qs;
57 };
58 /// Object for storing chb information
59 class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
60 public:
61 /// Mutex to synchronize globally shared access
62 GECODE_KERNEL_EXPORT static Support::Mutex m;
63 /// Number of chb values
64 int n;
65 /// Number of failures
66 unsigned long long int nf;
67 /// Alpha value
68 double alpha;
69 /// CHB information
70 Info* chb;
71 /// Initialize CHB info
72 template<class View>
73 Storage(Home home, ViewArray<View>& x,
74 typename BranchTraits<typename View::VarType>::Merit bm);
75 /// Delete object
76 GECODE_KERNEL_EXPORT
77 ~Storage(void);
78 /// Bump failure count and alpha
79 void bump(void);
80 /// Update chb information at position \a i
81 void update(int i, bool failed);
82 };
83 /// Return object of correct type
84 Storage& object(void) const;
85 /// Set object to \a o
86 void object(Storage& o);
87 /// Update chb value at position \a i
88 void update(int i);
89 /// Acquire mutex
90 void acquire(void);
91 /// Release mutex
92 void release(void);
93 /// Bump failure count and alpha
94 void bump(void);
95 /// Update chb information at position \a i
96 void update(int i, bool failed);
97 public:
98 /// \name Constructors and initialization
99 //@{
100 /**
101 * \brief Construct as not yet intialized
102 *
103 * The only member functions that can be used on a constructed but not
104 * yet initialized chb storage is init and the assignment operator.
105 *
106 */
107 CHB(void);
108 /// Copy constructor
109 GECODE_KERNEL_EXPORT
110 CHB(const CHB& a);
111 /// Assignment operator
112 GECODE_KERNEL_EXPORT
113 CHB& operator =(const CHB& a);
114 /// Initialize for views \a x and Q-score as defined by \a bm
115 template<class View>
116 CHB(Home home, ViewArray<View>& x,
117 typename BranchTraits<typename View::VarType>::Merit bm);
118 /// Initialize for views \a x and Q-score as defined by \a bm
119 template<class View>
120 void init(Home home, ViewArray<View>& x,
121 typename BranchTraits<typename View::VarType>::Merit bm);
122 /// Default (empty) chb information
123 GECODE_KERNEL_EXPORT static const CHB def;
124 //@}
125
126 /// Destructor
127 GECODE_KERNEL_EXPORT
128 ~CHB(void);
129
130 /// \name Information access
131 //@{
132 /// Return chb value at position \a i
133 double operator [](int i) const;
134 /// Return number of chb values
135 int size(void) const;
136 //@}
137 };
138
139 /// Propagator for recording chb information
140 template<class View>
141 class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
142 protected:
143 using NaryPropagator<View,PC_GEN_NONE>::x;
144 /// Advisor with index and change information
145 class Idx : public Advisor {
146 protected:
147 /// Index and mark information
148 int _info;
149 public:
150 /// Constructor for creation
151 Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
152 /// Constructor for cloning \a a
153 Idx(Space& home, Idx& a);
154 /// Mark advisor as modified
155 void mark(void);
156 /// Mark advisor as unmodified
157 void unmark(void);
158 /// Whether advisor's view has been marked
159 bool marked(void) const;
160 /// Get index of view
161 int idx(void) const;
162 };
163 /// Access to chb information
164 CHB chb;
165 /// The advisor council
166 Council<Idx> c;
167 /// Constructor for cloning \a p
168 Recorder(Space& home, Recorder<View>& p);
169 public:
170 /// Constructor for creation
171 Recorder(Home home, ViewArray<View>& x, CHB& chb);
172 /// Copy propagator during cloning
173 virtual Propagator* copy(Space& home);
174 /// Cost function (record so that propagator runs last)
175 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
176 /// Schedule function
177 virtual void reschedule(Space& home);
178 /// Give advice to propagator
179 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
180 /// Give advice to propagator when \a home has failed
181 virtual void advise(Space& home, Advisor& a);
182 /// Perform propagation
183 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
184 /// Delete propagator and return its size
185 virtual size_t dispose(Space& home);
186 /// Post chb recorder propagator
187 static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
188 };
189
190 /**
191 * \brief Print chb values enclosed in curly brackets
192 * \relates CHB
193 */
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>
205 forceinline
206 CHB::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
207 Council<Idx>& c, int i)
208 : Advisor(home,p,c), _info(i << 1) {}
209 template<class View>
210 forceinline
211 CHB::Recorder<View>::Idx::Idx(Space& home, Idx& a)
212 : Advisor(home,a), _info(a._info) {
213 }
214 template<class View>
215 forceinline void
216 CHB::Recorder<View>::Idx::mark(void) {
217 _info |= 1;
218 }
219 template<class View>
220 forceinline bool
221 CHB::Recorder<View>::Idx::marked(void) const {
222 return (_info & 1) != 0;
223 }
224 template<class View>
225 forceinline void
226 CHB::Recorder<View>::Idx::unmark(void) {
227 assert(marked());
228 _info -= 1;
229 }
230 template<class View>
231 forceinline int
232 CHB::Recorder<View>::Idx::idx(void) const {
233 return _info >> 1;
234 }
235
236
237 /*
238 * Posting of chb recorder propagator
239 *
240 */
241 template<class View>
242 forceinline
243 CHB::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
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>
253 forceinline ExecStatus
254 CHB::Recorder<View>::post(Home home, ViewArray<View>& x, CHB& chb) {
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>
265 forceinline
266 CHB::Storage::Storage(Home home, ViewArray<View>& x,
267 typename
268 BranchTraits<typename View::VarType>::Merit bm)
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;
280 chb[i].qs = Kernel::Config::chb_qscore_init;
281 }
282 }
283 }
284 forceinline void
285 CHB::Storage::bump(void) {
286 nf++;
287 if (alpha > Kernel::Config::chb_alpha_limit) {
288 alpha -= Kernel::Config::chb_alpha_decrement;
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
309 forceinline CHB::Storage&
310 CHB::object(void) const {
311 return static_cast<CHB::Storage&>(*SharedHandle::object());
312 }
313
314 forceinline void
315 CHB::object(CHB::Storage& o) {
316 SharedHandle::object(&o);
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
345 forceinline
346 CHB::CHB(void) {}
347
348 template<class View>
349 forceinline
350 CHB::CHB(Home home, ViewArray<View>& x,
351 typename BranchTraits<typename View::VarType>::Merit bm) {
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
358 CHB::init(Home home, ViewArray<View>& x,
359 typename BranchTraits<typename View::VarType>::Merit bm) {
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>
387 forceinline
388 CHB::Recorder<View>::Recorder(Space& home, Recorder<View>& p)
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*
395 CHB::Recorder<View>::copy(Space& home) {
396 return new (home) Recorder<View>(home, *this);
397 }
398
399 template<class View>
400 inline size_t
401 CHB::Recorder<View>::dispose(Space& home) {
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);
409 (void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
410 return sizeof(*this);
411 }
412
413 template<class View>
414 PropCost
415 CHB::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
416 return PropCost::record();
417 }
418
419 template<class View>
420 void
421 CHB::Recorder<View>::reschedule(Space& home) {
422 View::schedule(home,*this,ME_GEN_ASSIGNED);
423 }
424
425 template<class View>
426 ExecStatus
427 CHB::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
428 static_cast<Idx&>(a).mark();
429 return ES_NOFIX;
430 }
431
432 template<class View>
433 void
434 CHB::Recorder<View>::advise(Space&, Advisor& a) {
435 static_cast<Idx&>(a).mark();
436 }
437
438 template<class View>
439 ExecStatus
440 CHB::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
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