cbs.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Samuel Gagnon <samuel.gagnon92@gmail.com>
*
* Copyright:
* Samuel Gagnon, 2018
*
* 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.
*
*/
#ifdef GECODE_HAS_CBS
namespace Gecode { namespace Int { namespace Branch {
template<class View>
forceinline void
CBSBrancher<View>::VarIdToPos::init() {
assert(object() == nullptr);
object(new VarIdToPosO());
}
template<class View>
forceinline bool
CBSBrancher<View>::VarIdToPos::isIn(unsigned int var_id) const {
auto *hm = &static_cast<VarIdToPosO*>(object())->_varIdToPos;
return hm->find(var_id) != hm->end();
}
template<class View>
forceinline int
CBSBrancher<View>::VarIdToPos::operator[](unsigned int i) const {
return static_cast<VarIdToPosO*>(object())->_varIdToPos.at(i);
}
template<class View>
forceinline void
CBSBrancher<View>::VarIdToPos::insert(unsigned int var_id,
unsigned int pos) {
static_cast<VarIdToPosO*>(object())
->_varIdToPos.insert(std::make_pair(var_id, pos));
}
template<class View>
CBSBrancher<View>::CBSBrancher(Home home, ViewArray<View>& x0)
: Brancher(home), x(x0),
logProp(typename decltype(logProp)::size_type(),
typename decltype(logProp)::hasher(),
typename decltype(logProp)::key_equal(),
typename decltype(logProp)::allocator_type(home)) {
home.notice(*this, AP_DISPOSE);
varIdToPos.init();
for (int i=0; i<x.size(); i++)
varIdToPos.insert(x[i].id(), i);
}
template<class View>
forceinline void
CBSBrancher<View>::post(Home home, ViewArray<View>& x) {
(void) new (home) CBSBrancher(home,x);
}
template<class View>
Actor* CBSBrancher<View>::copy(Space& home) {
return new (home) CBSBrancher(home,*this);
}
template<class View>
forceinline size_t
CBSBrancher<View>::dispose(Space& home) {
home.ignore(*this, AP_DISPOSE);
varIdToPos.~VarIdToPos();
(void) Brancher::dispose(home);
return sizeof(*this);
}
template<class View>
CBSBrancher<View>::CBSBrancher(Space& home, CBSBrancher& b)
: Brancher(home,b),
varIdToPos(b.varIdToPos),
logProp(b.logProp.begin(), b.logProp.end(),
typename decltype(logProp)::size_type(),
typename decltype(logProp)::hasher(),
typename decltype(logProp)::key_equal(),
typename decltype(logProp)::allocator_type(home)) {
x.update(home,b.x);
}
template<class View>
bool CBSBrancher<View>::status(const Space& home) const {
for (Propagators p(home, PropagatorGroup::all); p(); ++p) {
// Sum of domains of all variable in propagator
unsigned int domsum;
// Same, but for variables that are also in this brancher.
unsigned int domsum_b;
// If the propagator doesn't support counting-based search, domsum and
// domsum_b are going to be equal to 0.
p.propagator().domainsizesum([this](unsigned int var_id)
{ return inbrancher(var_id); },
domsum, domsum_b);
if (domsum_b > 0)
return true;
}
return false;
}
template<class View>
forceinline bool
CBSBrancher<View>::inbrancher(unsigned int varId) const {
return varIdToPos.isIn(varId);
}
template<class View>
const Choice* CBSBrancher<View>::choice(Space& home) {
// Structure for keeping the maximum solution density assignment
struct {
unsigned int var_id;
int val;
double dens;
} maxSD{0, 0, -1};
// Lambda we pass to propagators via solndistrib to query solution densities
auto SendMarginal = [this](unsigned int prop_id, unsigned int var_id,
int val, double dens) {
if (logProp[prop_id].dens < dens) {
logProp[prop_id].var_id = var_id;
logProp[prop_id].val = val;
logProp[prop_id].dens = dens;
}
};
for (auto& kv : logProp)
kv.second.visited = false;
for (Propagators p(home, PropagatorGroup::all); p(); ++p) {
unsigned int prop_id = p.propagator().id();
unsigned int domsum;
unsigned int domsum_b;
p.propagator().domainsizesum([this](unsigned int var_id)
{ return inbrancher(var_id); },
domsum, domsum_b);
// If the propagator doesn't share any unasigned variables with this
// brancher, we continue and it will be deleted from the log afterwards.
if (domsum_b == 0)
continue;
// New propagators can be created as we solve the problem. If this is the
// case we create a new entry in the log.
if (logProp.find(prop_id) == logProp.end())
logProp.insert(std::make_pair(prop_id, PropInfo{0, 0, 0, -1, true}));
else
logProp[prop_id].visited = true;
// If the domain size sum of all variables in the propagator has changed
// since the last time we called this function, we need to recompute
// solution densities. Otherwise, we can reuse them.
if (logProp[prop_id].domsum != domsum) {
logProp[prop_id].dens = -1;
// Solution density computation
p.propagator().solndistrib(home, SendMarginal);
logProp[prop_id].domsum = domsum;
}
}
// We delete unvisited propagators from the log and look for the highest
// solution density across all propagators.
for (const auto& kv : logProp) {
unsigned int prop_id = kv.first;
const PropInfo& info = kv.second;
if (!info.visited)
logProp.erase(prop_id);
else if (info.dens > maxSD.dens)
maxSD = {info.var_id, info.val, info.dens};
}
assert(maxSD.dens != -1);
assert(!x[varIdToPos[maxSD.var_id]].assigned());
return new PosValChoice<int>(*this, 2, varIdToPos[maxSD.var_id], maxSD.val);
}
template<class View>
forceinline const Choice*
CBSBrancher<View>::choice(const Space&, Archive& e) {
int pos, val;
e >> pos >> val;
return new PosValChoice<int>(*this, 2, pos, val);
}
template<class View>
forceinline ExecStatus
CBSBrancher<View>::commit(Space& home, const Choice& c, unsigned int a) {
const auto& pvc = static_cast<const PosValChoice<int>&>(c);
int pos = pvc.pos().pos;
int val = pvc.val();
if (a == 0)
return me_failed(x[pos].eq(home, val)) ? ES_FAILED : ES_OK;
else
return me_failed(x[pos].nq(home, val)) ? ES_FAILED : ES_OK;
}
template<class View>
forceinline void
CBSBrancher<View>::print(const Space&, const Choice& c, unsigned int a,
std::ostream& o) const {
const auto& pvc = static_cast<const PosValChoice<int>&>(c);
int pos=pvc.pos().pos, val=pvc.val();
if (a == 0)
o << "x[" << pos << "] = " << val;
else
o << "x[" << pos << "] != " << val;
}
}}}
#endif
// STATISTICS: int-branch
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::FloatVal::x
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Gecode::me_failed
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
Gecode::Float::Arithmetic::pos
bool pos(const View &x)
Test whether x is postive.
Definition mult.hpp:41
Gecode::Int::Branch
Integer branchers.
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Test::Float::Arithmetic::b
Gecode::FloatVal b(9, 12)
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
forceinline
#define forceinline
Definition config.hpp:187