Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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  home.notice(*this, AP_DISPOSE);
74  varIdToPos.init();
75  for (int i=0; i<x.size(); i++)
76  varIdToPos.insert(x[i].id(), i);
77  }
78 
79  template<class View>
80  forceinline void
81  CBSBrancher<View>::post(Home home, ViewArray<View>& x) {
82  (void) new (home) CBSBrancher(home,x);
83  }
84 
85  template<class View>
86  Actor* CBSBrancher<View>::copy(Space& home) {
87  return new (home) CBSBrancher(home,*this);
88  }
89 
90  template<class View>
91  forceinline size_t
92  CBSBrancher<View>::dispose(Space& home) {
93  home.ignore(*this, AP_DISPOSE);
94  varIdToPos.~VarIdToPos();
95  (void) Brancher::dispose(home);
96  return sizeof(*this);
97  }
98 
99  template<class View>
100  CBSBrancher<View>::CBSBrancher(Space& home, CBSBrancher& b)
101  : Brancher(home,b),
102  varIdToPos(b.varIdToPos),
103  logProp(b.logProp.begin(), b.logProp.end(),
104  typename decltype(logProp)::size_type(),
105  typename decltype(logProp)::hasher(),
106  typename decltype(logProp)::key_equal(),
107  typename decltype(logProp)::allocator_type(home)) {
108  x.update(home,b.x);
109  }
110 
111  template<class View>
112  bool CBSBrancher<View>::status(const Space& home) const {
113  for (Propagators p(home, PropagatorGroup::all); p(); ++p) {
114  // Sum of domains of all variable in propagator
115  unsigned int domsum;
116  // Same, but for variables that are also in this brancher.
117  unsigned int domsum_b;
118 
119  // If the propagator doesn't support counting-based search, domsum and
120  // domsum_b are going to be equal to 0.
121  p.propagator().domainsizesum([this](unsigned int var_id)
122  { return inbrancher(var_id); },
123  domsum, domsum_b);
124 
125  if (domsum_b > 0)
126  return true;
127  }
128 
129  return false;
130  }
131 
132  template<class View>
133  forceinline bool
134  CBSBrancher<View>::inbrancher(unsigned int varId) const {
135  return varIdToPos.isIn(varId);
136  }
137 
138  template<class View>
139  const Choice* CBSBrancher<View>::choice(Space& home) {
140  // Structure for keeping the maximum solution density assignment
141  struct {
142  unsigned int var_id;
143  int val;
144  double dens;
145  } maxSD{0, 0, -1};
146 
147  // Lambda we pass to propagators via solndistrib to query solution densities
148  auto SendMarginal = [this](unsigned int prop_id, unsigned int var_id,
149  int val, double dens) {
150  if (logProp[prop_id].dens < dens) {
151  logProp[prop_id].var_id = var_id;
152  logProp[prop_id].val = val;
153  logProp[prop_id].dens = dens;
154  }
155  };
156 
157  for (auto& kv : logProp)
158  kv.second.visited = false;
159 
160  for (Propagators p(home, PropagatorGroup::all); p(); ++p) {
161  unsigned int prop_id = p.propagator().id();
162  unsigned int domsum;
163  unsigned int domsum_b;
164 
165  p.propagator().domainsizesum([this](unsigned int var_id)
166  { return inbrancher(var_id); },
167  domsum, domsum_b);
168 
169  // If the propagator doesn't share any unasigned variables with this
170  // brancher, we continue and it will be deleted from the log afterwards.
171  if (domsum_b == 0)
172  continue;
173 
174  // New propagators can be created as we solve the problem. If this is the
175  // case we create a new entry in the log.
176  if (logProp.find(prop_id) == logProp.end())
177  logProp.insert(std::make_pair(prop_id, PropInfo{0, 0, 0, -1, true}));
178  else
179  logProp[prop_id].visited = true;
180 
181  // If the domain size sum of all variables in the propagator has changed
182  // since the last time we called this function, we need to recompute
183  // solution densities. Otherwise, we can reuse them.
184  if (logProp[prop_id].domsum != domsum) {
185  logProp[prop_id].dens = -1;
186  // Solution density computation
187  p.propagator().solndistrib(home, SendMarginal);
188  logProp[prop_id].domsum = domsum;
189  }
190  }
191 
192  // We delete unvisited propagators from the log and look for the highest
193  // solution density across all propagators.
194  for (const auto& kv : logProp) {
195  unsigned int prop_id = kv.first;
196  const PropInfo& info = kv.second;
197  if (!info.visited)
198  logProp.erase(prop_id);
199  else if (info.dens > maxSD.dens)
200  maxSD = {info.var_id, info.val, info.dens};
201  }
202 
203  assert(maxSD.dens != -1);
204  assert(!x[varIdToPos[maxSD.var_id]].assigned());
205  return new PosValChoice<int>(*this, 2, varIdToPos[maxSD.var_id], maxSD.val);
206  }
207 
208  template<class View>
209  forceinline const Choice*
210  CBSBrancher<View>::choice(const Space&, Archive& e) {
211  int pos, val;
212  e >> pos >> val;
213  return new PosValChoice<int>(*this, 2, pos, val);
214  }
215 
216  template<class View>
218  CBSBrancher<View>::commit(Space& home, const Choice& c, unsigned int a) {
219  const auto& pvc = static_cast<const PosValChoice<int>&>(c);
220  int pos = pvc.pos().pos;
221  int val = pvc.val();
222  if (a == 0)
223  return me_failed(x[pos].eq(home, val)) ? ES_FAILED : ES_OK;
224  else
225  return me_failed(x[pos].nq(home, val)) ? ES_FAILED : ES_OK;
226  }
227 
228  template<class View>
229  forceinline void
230  CBSBrancher<View>::print(const Space&, const Choice& c, unsigned int a,
231  std::ostream& o) const {
232  const auto& pvc = static_cast<const PosValChoice<int>&>(c);
233  int pos=pvc.pos().pos, val=pvc.val();
234  if (a == 0)
235  o << "x[" << pos << "] = " << val;
236  else
237  o << "x[" << pos << "] != " << val;
238  }
239 
240 }}}
241 
242 #endif
243 
244 // STATISTICS: int-branch
Post propagator for SetVar x
Definition: set.hh:767
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
ViewArray< VX > x
Array of views.
Definition: pattern.hpp:275
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
Gecode toplevel namespace
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1328
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:789
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1156
#define forceinline
Definition: config.hpp:192
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
Gecode::FloatVal c(-8, 8)
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
Gecode::IntArgs i({1, 2, 3, 4})
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
void print(const Search::Statistics &stat, bool restart)
Print statistics.
Definition: job-shop.cpp:606
ExecStatus
Definition: core.hpp:472