chb.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2017
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <cfloat>
namespace Gecode {
class CHB : public SharedHandle {
protected:
template<class View>
class Recorder;
class Info {
public:
unsigned long long int lf;
double qs;
};
class GECODE_VTABLE_EXPORT Storage : public SharedHandle::Object {
public:
GECODE_KERNEL_EXPORT static Support::Mutex m;
int n;
unsigned long int nf;
double alpha;
Info* chb;
template<class View>
Storage(Home home, ViewArray<View>& x,
typename BranchTraits<typename View::VarType>::Merit bm);
GECODE_KERNEL_EXPORT
~Storage(void);
void bump(void);
void update(int i, bool failed);
};
Storage& object(void) const;
void object(Storage& o);
void update(int i);
void acquire(void);
void release(void);
void bump(void);
void update(int i, bool failed);
public:
CHB(void);
GECODE_KERNEL_EXPORT
CHB(const CHB& a);
GECODE_KERNEL_EXPORT
CHB& operator =(const CHB& a);
template<class View>
CHB(Home home, ViewArray<View>& x,
typename BranchTraits<typename View::VarType>::Merit bm);
template<class View>
void init(Home home, ViewArray<View>& x,
typename BranchTraits<typename View::VarType>::Merit bm);
GECODE_KERNEL_EXPORT static const CHB def;
GECODE_KERNEL_EXPORT
~CHB(void);
double operator [](int i) const;
int size(void) const;
};
template<class View>
class CHB::Recorder : public NaryPropagator<View,PC_GEN_NONE> {
protected:
using NaryPropagator<View,PC_GEN_NONE>::x;
class Idx : public Advisor {
protected:
int _info;
public:
Idx(Space& home, Propagator& p, Council<Idx>& c, int i);
Idx(Space& home, Idx& a);
void mark(void);
void unmark(void);
bool marked(void) const;
int idx(void) const;
};
CHB chb;
Council<Idx> c;
Recorder(Space& home, Recorder<View>& p);
public:
Recorder(Home home, ViewArray<View>& x, CHB& chb);
virtual Propagator* copy(Space& home);
virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
virtual void reschedule(Space& home);
virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
virtual void advise(Space& home, Advisor& a);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
virtual size_t dispose(Space& home);
static ExecStatus post(Home home, ViewArray<View>& x, CHB& chb);
};
template<class Char, class Traits>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os,
const CHB& a);
/*
* Advisor for chb recorder
*
*/
template<class View>
forceinline
CHB::Recorder<View>::Idx::Idx(Space& home, Propagator& p,
Council<Idx>& c, int i)
: Advisor(home,p,c), _info(i << 1) {}
template<class View>
forceinline
CHB::Recorder<View>::Idx::Idx(Space& home, Idx& a)
: Advisor(home,a), _info(a._info) {
}
template<class View>
forceinline void
CHB::Recorder<View>::Idx::mark(void) {
_info |= 1;
}
template<class View>
forceinline bool
CHB::Recorder<View>::Idx::marked(void) const {
return (_info & 1) != 0;
}
template<class View>
forceinline void
CHB::Recorder<View>::Idx::unmark(void) {
assert(marked());
_info -= 1;
}
template<class View>
forceinline int
CHB::Recorder<View>::Idx::idx(void) const {
return _info >> 1;
}
/*
* Posting of chb recorder propagator
*
*/
template<class View>
forceinline
CHB::Recorder<View>::Recorder(Home home, ViewArray<View>& x,
CHB& chb0)
: NaryPropagator<View,PC_GEN_NONE>(home,x), chb(chb0), c(home) {
home.notice(*this,AP_DISPOSE);
for (int i=0; i<x.size(); i++)
if (!x[i].assigned())
x[i].subscribe(home,*new (home) Idx(home,*this,c,i), true);
}
template<class View>
forceinline ExecStatus
CHB::Recorder<View>::post(Home home, ViewArray<View>& x, CHB& chb) {
(void) new (home) Recorder<View>(home,x,chb);
return ES_OK;
}
/*
* CHB value storage
*
*/
template<class View>
forceinline
CHB::Storage::Storage(Home home, ViewArray<View>& x,
typename
BranchTraits<typename View::VarType>::Merit bm)
: n(x.size()), nf(0U), alpha(Kernel::Config::chb_alpha_init),
chb(heap.alloc<Info>(x.size())) {
if (bm) {
for (int i=0; i<n; i++) {
typename View::VarType xi(x[i].varimp());
chb[i].lf = 0U;
chb[i].qs = bm(home,xi,i);
}
} else {
for (int i=0; i<n; i++) {
chb[i].lf = 0U;
chb[i].qs = Kernel::Config::chb_qscore_init;
}
}
}
forceinline void
CHB::Storage::bump(void) {
nf++;
if (alpha > Kernel::Config::chb_alpha_limit) {
alpha -= Kernel::Config::chb_alpha_decrement;
}
}
forceinline void
CHB::Storage::update(int i, bool failed) {
if (failed) {
chb[i].lf = nf;
double reward = 1.0 / (nf - chb[i].lf + 1);
chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
} else {
double reward = 0.9 / (nf - chb[i].lf + 1);
chb[i].qs = (1.0 - alpha) * chb[i].qs + alpha * reward;
}
}
/*
* CHB
*
*/
forceinline CHB::Storage&
CHB::object(void) const {
return static_cast<CHB::Storage&>(*SharedHandle::object());
}
forceinline void
CHB::object(CHB::Storage& o) {
SharedHandle::object(&o);
}
forceinline double
CHB::operator [](int i) const {
assert((i >= 0) && (i < object().n));
return object().chb[i].qs;
}
forceinline int
CHB::size(void) const {
return object().n;
}
forceinline void
CHB::acquire(void) {
object().m.acquire();
}
forceinline void
CHB::release(void) {
object().m.release();
}
forceinline void
CHB::bump(void) {
object().bump();
}
forceinline void
CHB::update(int i, bool failed) {
object().update(i,failed);
}
forceinline
CHB::CHB(void) {}
template<class View>
forceinline
CHB::CHB(Home home, ViewArray<View>& x,
typename BranchTraits<typename View::VarType>::Merit bm) {
assert(!*this);
object(*new Storage(home,x,bm));
(void) Recorder<View>::post(home,x,*this);
}
template<class View>
forceinline void
CHB::init(Home home, ViewArray<View>& x,
typename BranchTraits<typename View::VarType>::Merit bm) {
assert(!*this);
object(*new Storage(home,x,bm));
(void) Recorder<View>::post(home,x,*this);
}
template<class Char, class Traits>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os,
const CHB& chb) {
std::basic_ostringstream<Char,Traits> s;
s.copyfmt(os); s.width(0);
s << '{';
if (chb.size() > 0) {
s << chb[0];
for (int i=1; i<chb.size(); i++)
s << ", " << chb[i];
}
s << '}';
return os << s.str();
}
/*
* Propagation for chb recorder
*
*/
template<class View>
forceinline
CHB::Recorder<View>::Recorder(Space& home, Recorder<View>& p)
: NaryPropagator<View,PC_GEN_NONE>(home,p), chb(p.chb) {
c.update(home, p.c);
}
template<class View>
Propagator*
CHB::Recorder<View>::copy(Space& home) {
return new (home) Recorder<View>(home, *this);
}
template<class View>
inline size_t
CHB::Recorder<View>::dispose(Space& home) {
// Delete access to chb information
home.ignore(*this,AP_DISPOSE);
chb.~CHB();
// Cancel remaining advisors
for (Advisors<Idx> as(c); as(); ++as)
x[as.advisor().idx()].cancel(home,as.advisor(),true);
c.dispose(home);
(void) NaryPropagator<View,PC_GEN_NONE>::dispose(home);
return sizeof(*this);
}
template<class View>
PropCost
CHB::Recorder<View>::cost(const Space&, const ModEventDelta&) const {
return PropCost::record();
}
template<class View>
void
CHB::Recorder<View>::reschedule(Space& home) {
View::schedule(home,*this,ME_GEN_ASSIGNED);
}
template<class View>
ExecStatus
CHB::Recorder<View>::advise(Space&, Advisor& a, const Delta&) {
static_cast<Idx&>(a).mark();
return ES_NOFIX;
}
template<class View>
void
CHB::Recorder<View>::advise(Space&, Advisor& a) {
static_cast<Idx&>(a).mark();
}
template<class View>
ExecStatus
CHB::Recorder<View>::propagate(Space& home, const ModEventDelta&) {
// Lock chb information
chb.acquire();
if (home.failed()) {
chb.bump();
for (Advisors<Idx> as(c); as(); ++as) {
int i = as.advisor().idx();
if (as.advisor().marked()) {
as.advisor().unmark();
chb.update(i,true);
if (x[i].assigned())
as.advisor().dispose(home,c);
}
}
} else {
for (Advisors<Idx> as(c); as(); ++as) {
int i = as.advisor().idx();
if (as.advisor().marked()) {
as.advisor().unmark();
chb.update(i,false);
if (x[i].assigned())
as.advisor().dispose(home,c);
}
}
}
chb.release();
return c.empty() ? home.ES_SUBSUMED(*this) : ES_FIX;
}
}
// STATISTICS: kernel-branch
Gecode::ActorLink::Space
friend class Space
Definition core.hpp:595
Gecode::ActorLink::Propagator
friend class Propagator
Definition core.hpp:591
Gecode::Advisor::Advisor
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:3831
Gecode::Advisor::Council
friend class Council
Definition core.hpp:1294
Gecode::Advisors
Class to iterate over advisors of a council.
Definition core.hpp:1266
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::BranchTraits
Traits for branching.
Definition traits.hpp:55
Gecode::CHB::Info
View information.
Definition chb.hpp:51
Gecode::CHB::Info::lf
unsigned long long int lf
Last failure.
Definition chb.hpp:54
Gecode::CHB::Info::qs
double qs
Q-score.
Definition chb.hpp:56
Gecode::CHB::Recorder::Idx
Advisor with index and change information.
Definition chb.hpp:145
Gecode::CHB::Recorder::Idx::unmark
void unmark(void)
Mark advisor as unmodified.
Definition chb.hpp:226
Gecode::CHB::Recorder::Idx::marked
bool marked(void) const
Whether advisor's view has been marked.
Definition chb.hpp:221
Gecode::CHB::Recorder::Idx::idx
int idx(void) const
Get index of view.
Definition chb.hpp:232
Gecode::CHB::Recorder::Idx::mark
void mark(void)
Mark advisor as modified.
Definition chb.hpp:216
Gecode::CHB::Recorder::Idx::Idx
Idx(Space &home, Propagator &p, Council< Idx > &c, int i)
Constructor for creation.
Definition chb.hpp:206
Gecode::CHB::Recorder::Idx::_info
int _info
Index and mark information.
Definition chb.hpp:148
Gecode::CHB::Recorder
Propagator for recording chb information.
Definition chb.hpp:141
Gecode::CHB::Recorder::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (record so that propagator runs last).
Definition chb.hpp:415
Gecode::CHB::Recorder::Recorder
Recorder(Space &home, Recorder< View > &p)
Constructor for cloning p.
Definition chb.hpp:388
Gecode::CHB::Recorder::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition chb.hpp:401
Gecode::CHB::Recorder::copy
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition chb.hpp:395
Gecode::CHB::Recorder::c
Council< Idx > c
The advisor council.
Definition chb.hpp:166
Gecode::CHB::Recorder::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition chb.hpp:440
Gecode::CHB::Recorder::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition chb.hpp:421
Gecode::CHB::Recorder::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition chb.hpp:427
Gecode::CHB::Recorder::post
static ExecStatus post(Home home, ViewArray< View > &x, CHB &chb)
Post chb recorder propagator.
Definition chb.hpp:254
Gecode::CHB::Recorder::chb
CHB chb
Access to chb information.
Definition chb.hpp:164
Gecode::CHB::Storage
Object for storing chb information.
Definition chb.hpp:59
Gecode::CHB::Storage::n
int n
Number of chb values.
Definition chb.hpp:64
Gecode::CHB::Storage::m
static Support::Mutex m
Mutex to synchronize globally shared access.
Definition chb.hpp:62
Gecode::CHB::Storage::bump
void bump(void)
Bump failure count and alpha.
Definition chb.hpp:285
Gecode::CHB::Storage::update
void update(int i, bool failed)
Update chb information at position i.
Definition chb.hpp:292
Gecode::CHB::Storage::chb
Info * chb
CHB information.
Definition chb.hpp:70
Gecode::CHB::Storage::Storage
Storage(Home home, ViewArray< View > &x, typename BranchTraits< typename View::VarType >::Merit bm)
Initialize CHB info.
Definition chb.hpp:266
Gecode::CHB::Storage::alpha
double alpha
Alpha value.
Definition chb.hpp:68
Gecode::CHB::Storage::nf
unsigned long int nf
Number of failures.
Definition chb.hpp:66
Gecode::CHB
Class for CHB management.
Definition chb.hpp:46
Gecode::CHB::update
void update(int i)
Update chb value at position i.
Gecode::CHB::CHB
CHB(void)
Construct as not yet intialized.
Definition chb.hpp:346
Gecode::CHB::~CHB
~CHB(void)
Destructor.
Definition chb.cpp:55
Gecode::CHB::init
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
Gecode::CHB::size
int size(void) const
Return number of chb values.
Definition chb.hpp:325
Gecode::CHB::object
Storage & object(void) const
Return object of correct type.
Definition chb.hpp:310
Gecode::CHB::operator=
CHB & operator=(const CHB &a)
Assignment operator.
Definition chb.cpp:50
Gecode::CHB::operator<<
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
Gecode::CHB::bump
void bump(void)
Bump failure count and alpha.
Definition chb.hpp:337
Gecode::CHB::release
void release(void)
Release mutex.
Definition chb.hpp:333
Gecode::CHB::operator[]
double operator[](int i) const
Return chb value at position i.
Definition chb.hpp:320
Gecode::CHB::def
static const CHB def
Default (empty) chb information.
Definition chb.hpp:123
Gecode::CHB::acquire
void acquire(void)
Acquire mutex.
Definition chb.hpp:329
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Home::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Gecode::NaryPropagator::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition pattern.hpp:513
Gecode::NaryPropagator< View, PC_GEN_NONE >::x
ViewArray< View > x
Definition pattern.hpp:145
Gecode::NaryPropagator< View, PC_GEN_NONE >::NaryPropagator
NaryPropagator(Space &home, NaryPropagator &p)
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::record
static PropCost record(void)
For recording information (no propagation allowed).
Definition core.hpp:4765
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Propagator::Council
friend class Council
Definition core.hpp:1069
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::SharedHandle::Object
The shared object.
Definition shared-object.hpp:53
Gecode::SharedHandle::SharedHandle
SharedHandle(void)
Create shared handle with no object pointing to.
Definition shared-object.hpp:122
Gecode::SharedHandle::object
SharedHandle::Object * object(void) const
Access to the shared object.
Definition shared-object.hpp:102
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Gecode::Support::Mutex::release
void release(void)
Release the mutex.
Definition none.hpp:48
Gecode::Support::Mutex::acquire
void acquire(void)
Acquire the mutex and possibly block.
Definition none.hpp:42
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Space::failed
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
GECODE_KERNEL_EXPORT
#define GECODE_KERNEL_EXPORT
Definition kernel.hh:70
Gecode::Kernel::Config::chb_alpha_decrement
const double chb_alpha_decrement
Alpha decrement in CHB.
Definition kernel.hh:108
Gecode::Kernel::Config::chb_qscore_init
const double chb_qscore_init
Initial value for Q-score in CHB.
Definition kernel.hh:110
Gecode::Kernel::Config::chb_alpha_limit
const double chb_alpha_limit
Limit for decreasing alpha in CHB.
Definition kernel.hh:106
Gecode::Kernel
Kernel functionality
Gecode
Gecode toplevel namespace
Gecode::operator<<
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition val-sel.hpp:39
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::ME_GEN_ASSIGNED
const ModEvent ME_GEN_ASSIGNED
Generic modification event: variable is assigned a value.
Definition core.hpp:69
Gecode::PC_GEN_NONE
const PropCond PC_GEN_NONE
Propagation condition to be ignored (convenience).
Definition core.hpp:74
forceinline
#define forceinline
Definition config.hpp:187
GECODE_VTABLE_EXPORT
#define GECODE_VTABLE_EXPORT
Definition support.hh:72