Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
action.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, 2012
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
42 class Action : public SharedHandle {
43 protected:
44 template<class View>
45 class Recorder;
48 public:
52 int n;
54 double invd;
56 double* a;
58 template<class View>
59 Storage(Home home, ViewArray<View>& x, double d,
62 void update(int i);
65 ~Storage(void);
66 };
68 Storage& object(void) const;
70 void object(Storage& o);
72 void update(int i);
74 void acquire(void);
76 void release(void);
77 public:
79
80
87 Action(void);
90 Action(const Action& a);
93 Action& operator =(const Action& a);
95 template<class View>
96 Action(Home home, ViewArray<View>& x, double d,
99 template<class View>
100 void init(Home home, ViewArray<View>& x, double d,
105
108 ~Action(void);
109
111
112
113 double operator [](int i) const;
115 int size(void) const;
117
119
120
122 void decay(Space& home, double d);
125 double decay(const Space& home) const;
127 };
128
130 template<class View>
131 class Action::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
132 protected:
133 using NaryPropagator<View,PC_GEN_NONE>::x;
135 class Idx : public Advisor {
136 protected:
138 int _info;
139 public:
141 Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
143 Idx(Space& home, Idx& a);
145 void mark(void);
147 void unmark(void);
149 bool marked(void) const;
151 int idx(void) const;
152 };
159 public:
163 virtual Propagator* copy(Space& home);
165 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
167 virtual void reschedule(Space& home);
169 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
171 virtual void advise(Space& home, Advisor& a);
173 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
175 virtual size_t dispose(Space& home);
177 static ExecStatus post(Home home, ViewArray<View>& x, Action& a);
178 };
179
184 template<class Char, class Traits>
185 std::basic_ostream<Char,Traits>&
186 operator <<(std::basic_ostream<Char,Traits>& os,
187 const Action& a);
188
189
190 /*
191 * Advisor for action recorder
192 *
193 */
194 template<class View>
197 Council<Idx>& c, int i)
198 : Advisor(home,p,c), _info(i << 1) {}
199 template<class View>
202 : Advisor(home,a), _info(a._info) {
203 }
204 template<class View>
205 forceinline void
207 _info |= 1;
208 }
209 template<class View>
210 forceinline bool
212 return (_info & 1) != 0;
213 }
214 template<class View>
215 forceinline void
217 assert(marked());
218 _info -= 1;
219 }
220 template<class View>
221 forceinline int
223 return _info >> 1;
224 }
225
226
227 /*
228 * Posting of action recorder propagator
229 *
230 */
231 template<class View>
234 Action& a0)
235 : NaryPropagator<View,PC_GEN_NONE>(home,x), a(a0), c(home) {
236 home.notice(*this,AP_DISPOSE);
237 for (int i=0; i<x.size(); i++)
238 if (!x[i].assigned())
239 x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
240 }
241
242 template<class View>
245 (void) new (home) Recorder<View>(home,x,a);
246 return ES_OK;
247 }
248
249
250 /*
251 * Action value storage
252 *
253 */
254
255 template<class View>
258 typename
260 : n(x.size()), invd(1.0 / d), a(heap.alloc<double>(x.size())) {
261 if (bm)
262 for (int i=0; i<n; i++) {
263 typename View::VarType xi(x[i].varimp());
264 a[i] = bm(home,xi,i);
265 }
266 else
267 for (int i=0; i<n; i++)
268 a[i] = 1.0;
269 }
270 forceinline void
272 /*
273 * The trick to inverse decay is from: An Extensible SAT-solver,
274 * Niklas Eén, Niklas Sörensson, SAT 2003.
275 */
276 assert((i >= 0) && (i < n));
277 a[i] = invd * (a[i] + 1.0);
279 for (int j=0; j<n; j++)
281 }
282
283
284 /*
285 * Action
286 *
287 */
288
290 Action::object(void) const {
291 return static_cast<Action::Storage&>(*SharedHandle::object());
292 }
293
294 forceinline void
298
299 forceinline void
301 object().update(i);
302 }
303 forceinline double
304 Action::operator [](int i) const {
305 assert((i >= 0) && (i < object().n));
306 return object().a[i];
307 }
308 forceinline int
309 Action::size(void) const {
310 return object().n;
311 }
312 forceinline void
314 object().m.acquire();
315 }
316 forceinline void
318 object().m.release();
319 }
320
321
324
325 template<class View>
329 assert(!*this);
330 object(*new Storage(home,x,d,bm));
331 (void) Recorder<View>::post(home,x,*this);
332 }
333 template<class View>
334 forceinline void
337 assert(!*this);
338 object(*new Storage(home,x,d,bm));
339 (void) Recorder<View>::post(home,x,*this);
340 }
341
342 template<class Char, class Traits>
343 std::basic_ostream<Char,Traits>&
344 operator <<(std::basic_ostream<Char,Traits>& os,
345 const Action& a) {
346 std::basic_ostringstream<Char,Traits> s;
347 s.copyfmt(os); s.width(0);
348 s << '{';
349 if (a.size() > 0) {
350 s << a[0];
351 for (int i=1; i<a.size(); i++)
352 s << ", " << a[i];
353 }
354 s << '}';
355 return os << s.str();
356 }
357
358
359 /*
360 * Propagation for action recorder
361 *
362 */
363 template<class View>
366 : NaryPropagator<View,PC_GEN_NONE>(home,p), a(p.a) {
367 c.update(home, p.c);
368 }
369
370 template<class View>
373 return new (home) Recorder<View>(home, *this);
374 }
375
376 template<class View>
377 inline size_t
379 // Delete access to action information
380 home.ignore(*this,AP_DISPOSE);
381 a.~Action();
382 // Cancel remaining advisors
383 for (Advisors<Idx> as(c); as(); ++as)
384 x[as.advisor().idx()].cancel(home,as.advisor(),true);
385 c.dispose(home);
387 return sizeof(*this);
388 }
389
390 template<class View>
393 return PropCost::record();
394 }
395
396 template<class View>
397 void
399 View::schedule(home,*this,ME_GEN_ASSIGNED);
400 }
401
402 template<class View>
405 static_cast<Idx&>(a).mark();
406 return ES_NOFIX;
407 }
408
409 template<class View>
410 void
412 static_cast<Idx&>(a).mark();
413 }
414
415 template<class View>
418 // Lock action information
419 a.acquire();
420 for (Advisors<Idx> as(c); as(); ++as) {
421 int i = as.advisor().idx();
422 if (as.advisor().marked()) {
423 as.advisor().unmark();
424 a.update(i);
425 if (x[i].assigned())
426 as.advisor().dispose(home,c);
427 }
428 }
429 a.release();
430 return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
431 }
432
433
434}
435
436// 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.
Advisor with index and change information.
Definition action.hpp:135
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition action.hpp:196
int idx(void) const
Get index of view.
Definition action.hpp:222
void unmark(void)
Mark advisor as unmodified.
Definition action.hpp:216
int _info
Index and mark information.
Definition action.hpp:138
void mark(void)
Mark advisor as modified.
Definition action.hpp:206
bool marked(void) const
Whether advisor's view has been marked.
Definition action.hpp:211
Propagator for recording action information.
Definition action.hpp:131
Action a
Access to action information.
Definition action.hpp:154
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition action.hpp:378
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition action.hpp:404
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition action.hpp:417
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition action.hpp:372
Council< Idx > c
The advisor council.
Definition action.hpp:156
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last)
Definition action.hpp:392
static ExecStatus post(Home home, ViewArray< View > &x, Action &a)
Post action recorder propagator.
Definition action.hpp:244
virtual void reschedule(Space &home)
Schedule function.
Definition action.hpp:398
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition action.hpp:365
Object for storing action values.
Definition action.hpp:47
void update(int i)
Update action value at position i.
Definition action.hpp:271
double invd
Inverse decay factor.
Definition action.hpp:54
double * a
Action values (more follow)
Definition action.hpp:56
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition action.hpp:50
Storage(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize action values.
Definition action.hpp:257
int n
Number of action values.
Definition action.hpp:52
Class for action management.
Definition action.hpp:42
Storage & object(void) const
Return object of correct type.
Definition action.hpp:290
void update(int i)
Update action value at position i.
Definition action.hpp:300
Action & operator=(const Action &a)
Assignment operator.
Definition action.cpp:50
int size(void) const
Return number of action values.
Definition action.hpp:309
double operator[](int i) const
Return action value at position i.
Definition action.hpp:304
void init(Home home, ViewArray< View > &x, double d, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize for views x and decay factor d and action as defined by bm.
Definition action.hpp:335
void acquire(void)
Acquire mutex.
Definition action.hpp:313
void release(void)
Release mutex.
Definition action.hpp:317
static const Action def
Default (empty) action information.
Definition action.hpp:103
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const Action &a)
Print action values enclosed in curly brackets.
Definition action.hpp:344
Action(void)
Construct as not yet intialized.
Definition action.hpp:323
~Action(void)
Destructor.
Definition action.cpp:55
void decay(Space &home, double d)
Set decay factor to d.
Definition action.cpp:58
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
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
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
const double rescale_limit
Rescale action and afc values when larger than this.
Definition kernel.hh:101
const double rescale
Rescale factor for action and afc values.
Definition kernel.hh:99
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