this repo has no description
dekker.one
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
36namespace 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>
217 forceinline ExecStatus
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