Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
cbs.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Samuel Gagnon <samuel.gagnon92@gmail.com>
5  *
6  * Copyright:
7  * Samuel Gagnon, 2018
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 #ifdef GECODE_HAS_CBS
35 
36 namespace Gecode { namespace Int { namespace Branch {
37 
38  template<class View>
39  forceinline void
40  CBSBrancher<View>::VarIdToPos::init() {
41  assert(object() == nullptr);
42  object(new VarIdToPosO());
43  }
44 
45  template<class View>
46  forceinline bool
47  CBSBrancher<View>::VarIdToPos::isIn(unsigned int var_id) const {
48  auto *hm = &static_cast<VarIdToPosO*>(object())->_varIdToPos;
49  return hm->find(var_id) != hm->end();
50  }
51 
52  template<class View>
53  forceinline int
54  CBSBrancher<View>::VarIdToPos::operator[](unsigned int i) const {
55  return static_cast<VarIdToPosO*>(object())->_varIdToPos.at(i);
56  }
57 
58  template<class View>
59  forceinline void
60  CBSBrancher<View>::VarIdToPos::insert(unsigned int var_id,
61  unsigned int pos) {
62  static_cast<VarIdToPosO*>(object())
63  ->_varIdToPos.insert(std::make_pair(var_id, pos));
64  }
65 
66  template<class View>
67  CBSBrancher<View>::CBSBrancher(Home home, ViewArray<View>& x0)
68  : Brancher(home), x(x0),
69  logProp(typename decltype(logProp)::size_type(),
70  typename decltype(logProp)::hasher(),
71  typename decltype(logProp)::key_equal(),
72  typename decltype(logProp)::allocator_type(home)) {
73  varIdToPos.init();
74  for (int i=0; i<x.size(); i++)
75  varIdToPos.insert(x[i].id(), i);
76  }
77 
78  template<class View>
79  forceinline void
80  CBSBrancher<View>::post(Home home, ViewArray<View>& x) {
81  (void) new (home) CBSBrancher(home,x);
82  }
83 
84  template<class View>
85  Actor* CBSBrancher<View>::copy(Space& home) {
86  return new (home) CBSBrancher(home,*this);
87  }
88 
89  template<class View>
90  forceinline size_t
91  CBSBrancher<View>::dispose(Space& home) {
92  home.ignore(*this, AP_DISPOSE);
93  (void) Brancher::dispose(home);
94  return sizeof(*this);
95  }
96 
97  template<class View>
98  CBSBrancher<View>::CBSBrancher(Space& home, CBSBrancher& b)
99  : Brancher(home,b),
100  varIdToPos(b.varIdToPos),
101  logProp(b.logProp.begin(), b.logProp.end(),
102  typename decltype(logProp)::size_type(),
103  typename decltype(logProp)::hasher(),
104  typename decltype(logProp)::key_equal(),
105  typename decltype(logProp)::allocator_type(home)) {
106  x.update(home,b.x);
107  }
108 
109  template<class View>
110  bool CBSBrancher<View>::status(const Space& home) const {
111  for (Propagators p(home, PropagatorGroup::all); p(); ++p) {
112  // Sum of domains of all variable in propagator
113  unsigned int domsum;
114  // Same, but for variables that are also in this brancher.
115  unsigned int domsum_b;
116 
117  // If the propagator doesn't support counting-based search, domsum and
118  // domsum_b are going to be equal to 0.
119  p.propagator().domainsizesum([this](unsigned int var_id)
120  { return inbrancher(var_id); },
121  domsum, domsum_b);
122 
123  if (domsum_b > 0)
124  return true;
125  }
126 
127  return false;
128  }
129 
130  template<class View>
131  forceinline bool
132  CBSBrancher<View>::inbrancher(unsigned int varId) const {
133  return varIdToPos.isIn(varId);
134  }
135 
136  template<class View>
137  const Choice* CBSBrancher<View>::choice(Space& home) {
138  // Structure for keeping the maximum solution density assignment
139  struct {
140  unsigned int var_id;
141  int val;
142  double dens;
143  } maxSD{0, 0, -1};
144 
145  // Lambda we pass to propagators via solndistrib to query solution densities
146  auto SendMarginal = [this](unsigned int prop_id, unsigned int var_id,
147  int val, double dens) {
148  if (logProp[prop_id].dens < dens) {
149  logProp[prop_id].var_id = var_id;
150  logProp[prop_id].val = val;
151  logProp[prop_id].dens = dens;
152  }
153  };
154 
155  for (auto& kv : logProp)
156  kv.second.visited = false;
157 
158  for (Propagators p(home, PropagatorGroup::all); p(); ++p) {
159  unsigned int prop_id = p.propagator().id();
160  unsigned int domsum;
161  unsigned int domsum_b;
162 
163  p.propagator().domainsizesum([this](unsigned int var_id)
164  { return inbrancher(var_id); },
165  domsum, domsum_b);
166 
167  // If the propagator doesn't share any unasigned variables with this
168  // brancher, we continue and it will be deleted from the log afterwards.
169  if (domsum_b == 0)
170  continue;
171 
172  // New propagators can be created as we solve the problem. If this is the
173  // case we create a new entry in the log.
174  if (logProp.find(prop_id) == logProp.end())
175  logProp.insert(std::make_pair(prop_id, PropInfo{0, 0, 0, -1, true}));
176  else
177  logProp[prop_id].visited = true;
178 
179  // If the domain size sum of all variables in the propagator has changed
180  // since the last time we called this function, we need to recompute
181  // solution densities. Otherwise, we can reuse them.
182  if (logProp[prop_id].domsum != domsum) {
183  logProp[prop_id].dens = -1;
184  // Solution density computation
185  p.propagator().solndistrib(home, SendMarginal);
186  logProp[prop_id].domsum = domsum;
187  }
188  }
189 
190  // We delete unvisited propagators from the log and look for the highest
191  // solution density across all propagators.
192  for (const auto& kv : logProp) {
193  unsigned int prop_id = kv.first;
194  const PropInfo& info = kv.second;
195  if (!info.visited)
196  logProp.erase(prop_id);
197  else if (info.dens > maxSD.dens)
198  maxSD = {info.var_id, info.val, info.dens};
199  }
200 
201  assert(maxSD.dens != -1);
202  assert(!x[varIdToPos[maxSD.var_id]].assigned());
203  return new PosValChoice<int>(*this, 2, varIdToPos[maxSD.var_id], maxSD.val);
204  }
205 
206  template<class View>
207  forceinline const Choice*
208  CBSBrancher<View>::choice(const Space&, Archive& e) {
209  int pos, val;
210  e >> pos >> val;
211  return new PosValChoice<int>(*this, 2, pos, val);
212  }
213 
214  template<class View>
216  CBSBrancher<View>::commit(Space& home, const Choice& c, unsigned int a) {
217  const auto& pvc = static_cast<const PosValChoice<int>&>(c);
218  int pos = pvc.pos().pos;
219  int val = pvc.val();
220  if (a == 0)
221  return me_failed(x[pos].eq(home, val)) ? ES_FAILED : ES_OK;
222  else
223  return me_failed(x[pos].nq(home, val)) ? ES_FAILED : ES_OK;
224  }
225 
226  template<class View>
227  forceinline void
228  CBSBrancher<View>::print(const Space&, const Choice& c, unsigned int a,
229  std::ostream& o) const {
230  const auto& pvc = static_cast<const PosValChoice<int>&>(c);
231  int pos=pvc.pos().pos, val=pvc.val();
232  if (a == 0)
233  o << "x[" << pos << "] = " << val;
234  else
235  o << "x[" << pos << "] != " << val;
236  }
237 
238 }}}
239 
240 #endif
241 
242 // STATISTICS: int-branch
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
Actor must always be disposed.
Definition: core.hpp:561
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:786
friend class Space
Definition: core.hpp:1025
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
#define forceinline
Definition: config.hpp:185
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Definition: core.hpp:473
Council< Advisor > c
The advisor council.
Definition: bool.hh:363
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
void print(std::basic_ostream< Char, Traits > &s, bool assigned, IL &lb, IU &ub, unsigned int cardMin, unsigned int cardMax)
Print set view.
Definition: print.hpp:63
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3209
ExecStatus
Definition: core.hpp:471
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Gecode toplevel namespace
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
friend class Brancher
Definition: core.hpp:632
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54