Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
8.2 kB · 244 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245/* -*- 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