Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
branch.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2012
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#include <gecode/int/branch.hh>
35
36namespace Gecode {
37
38 void
39 branch(Home home, const IntVarArgs& x,
40 IntVarBranch vars, IntValBranch vals,
42 IntVarValPrint vvp) {
43 using namespace Int;
44 if (home.failed()) return;
45 vars.expand(home,x);
46 ViewArray<IntView> xv(home,x);
47 ViewSel<IntView>* vs[1] = {
48 Branch::viewsel(home,vars)
49 };
50 switch (vals.select()) {
53 break;
56 break;
57 default:
59 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
60 break;
61 }
62 }
63
64 void
65 branch(Home home, const IntVarArgs& x,
68 IntVarValPrint vvp) {
69 using namespace Int;
70 if (home.failed()) return;
71 vars.a.expand(home,x);
72 if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
73 (vars.a.select() == IntVarBranch::SEL_RND))
74 vars.b = INT_VAR_NONE();
75 vars.b.expand(home,x);
76 if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
77 (vars.b.select() == IntVarBranch::SEL_RND))
78 vars.c = INT_VAR_NONE();
79 vars.c.expand(home,x);
80 if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
81 (vars.c.select() == IntVarBranch::SEL_RND))
82 vars.d = INT_VAR_NONE();
83 vars.d.expand(home,x);
84 if (vars.b.select() == IntVarBranch::SEL_NONE) {
85 branch(home,x,vars.a,vals,bf,vvp);
86 } else {
87 ViewArray<IntView> xv(home,x);
88 if (vars.c.select() == IntVarBranch::SEL_NONE) {
89 ViewSel<IntView>* vs[2] = {
90 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
91 };
92 switch (vals.select()) {
95 break;
98 break;
99 default:
101 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
102 }
103 } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
104 ViewSel<IntView>* vs[3] = {
105 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
106 Branch::viewsel(home,vars.c)
107 };
108 switch (vals.select()) {
111 break;
114 break;
115 default:
117 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
118 }
119 } else {
120 ViewSel<IntView>* vs[4] = {
121 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
122 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
123 };
124 switch (vals.select()) {
127 break;
130 break;
131 default:
133 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
134 }
135 }
136 }
137 }
138
139 void
141 IntVarArgs xv(1); xv[0]=x;
142 branch(home, xv, INT_VAR_NONE(), vals, nullptr, vvp);
143 }
144
145
146 void
147 assign(Home home, const IntVarArgs& x,
148 IntVarBranch vars, IntAssign vals,
150 IntVarValPrint vvp) {
151 using namespace Int;
152 if (home.failed()) return;
153 ViewArray<IntView> xv(home,x);
154 ViewSel<IntView>* vs[1] = {
155 new (home) ViewSelNone<IntView>(home,vars)
156 };
158 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
159 }
160
161 void
162 branch(Home home, const IntVarArgs& x,
165 IntVarValPrint vvp) {
166 using namespace Int;
167 if (home.failed()) return;
168 vars.a.expand(home,x);
169 if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
170 (vars.a.select() == IntVarBranch::SEL_RND))
171 vars.b = INT_VAR_NONE();
172 vars.b.expand(home,x);
173 if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
174 (vars.b.select() == IntVarBranch::SEL_RND))
175 vars.c = INT_VAR_NONE();
176 vars.c.expand(home,x);
177 if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
178 (vars.c.select() == IntVarBranch::SEL_RND))
179 vars.d = INT_VAR_NONE();
180 vars.d.expand(home,x);
181 if (vars.b.select() == IntVarBranch::SEL_NONE) {
182 assign(home,x,vars.a,vals,bf,vvp);
183 } else {
184 ViewArray<IntView> xv(home,x);
185 if (vars.c.select() == IntVarBranch::SEL_NONE) {
186 ViewSel<IntView>* vs[2] = {
187 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
188 };
190 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
191 } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
192 ViewSel<IntView>* vs[3] = {
193 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
194 Branch::viewsel(home,vars.c)
195 };
197 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
198 } else {
199 ViewSel<IntView>* vs[4] = {
200 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
201 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
202 };
204 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
205 }
206 }
207 }
208
209 void
211 IntVarArgs xv(1); xv[0]=x;
212 assign(home, xv, INT_VAR_NONE(), ia, nullptr, vvp);
213 }
214
215
216 void
217 branch(Home home, const BoolVarArgs& x,
218 BoolVarBranch vars, BoolValBranch vals,
220 BoolVarValPrint vvp) {
221 using namespace Int;
222 if (home.failed()) return;
223 vars.expand(home,x);
224 ViewArray<BoolView> xv(home,x);
225 ViewSel<BoolView>* vs[1] = {
226 Branch::viewsel(home,vars)
227 };
229 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
230 }
231
232 void
233 branch(Home home, const BoolVarArgs& x,
236 BoolVarValPrint vvp) {
237 using namespace Int;
238 if (home.failed()) return;
239 vars.a.expand(home,x);
240 if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
241 (vars.a.select() == BoolVarBranch::SEL_RND))
242 vars.b = BOOL_VAR_NONE();
243 vars.b.expand(home,x);
244 if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
245 (vars.b.select() == BoolVarBranch::SEL_RND))
246 vars.c = BOOL_VAR_NONE();
247 vars.c.expand(home,x);
248 if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
249 (vars.c.select() == BoolVarBranch::SEL_RND))
250 vars.d = BOOL_VAR_NONE();
251 vars.d.expand(home,x);
252 if (vars.b.select() == BoolVarBranch::SEL_NONE) {
253 branch(home,x,vars.a,vals,bf,vvp);
254 } else {
255 ViewArray<BoolView> xv(home,x);
257 vsc = Branch::valselcommit(home,vals);
258 if (vars.c.select() == BoolVarBranch::SEL_NONE) {
259 ViewSel<BoolView>* vs[2] = {
260 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
261 };
262 postviewvalbrancher<BoolView,2,int,2>(home,xv,vs,vsc,bf,vvp);
263 } else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
264 ViewSel<BoolView>* vs[3] = {
265 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
266 Branch::viewsel(home,vars.c)
267 };
268 postviewvalbrancher<BoolView,3,int,2>(home,xv,vs,vsc,bf,vvp);
269 } else {
270 ViewSel<BoolView>* vs[4] = {
271 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
272 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
273 };
274 postviewvalbrancher<BoolView,4,int,2>(home,xv,vs,vsc,bf,vvp);
275 }
276 }
277 }
278
279 void
281 BoolVarArgs xv(1); xv[0]=x;
282 branch(home, xv, BOOL_VAR_NONE(), vals, nullptr, vvp);
283 }
284
285 void
286 assign(Home home, const BoolVarArgs& x,
287 BoolVarBranch vars, BoolAssign vals,
289 BoolVarValPrint vvp) {
290 using namespace Int;
291 if (home.failed()) return;
292 ViewArray<BoolView> xv(home,x);
293 ViewSel<BoolView>* vs[1] = {
294 new (home) ViewSelNone<BoolView>(home,vars)
295 };
297 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
298 }
299
300 void
301 assign(Home home, const BoolVarArgs& x,
304 BoolVarValPrint vvp) {
305 using namespace Int;
306 if (home.failed()) return;
307 vars.a.expand(home,x);
308 if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
309 (vars.a.select() == BoolVarBranch::SEL_RND))
310 vars.b = BOOL_VAR_NONE();
311 vars.b.expand(home,x);
312 if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
313 (vars.b.select() == BoolVarBranch::SEL_RND))
314 vars.c = BOOL_VAR_NONE();
315 vars.c.expand(home,x);
316 if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
317 (vars.c.select() == BoolVarBranch::SEL_RND))
318 vars.d = BOOL_VAR_NONE();
319 vars.d.expand(home,x);
320 if (vars.b.select() == BoolVarBranch::SEL_NONE) {
321 assign(home,x,vars.a,vals,bf,vvp);
322 } else {
323 ViewArray<BoolView> xv(home,x);
325 vsc = Branch::valselcommit(home,vals);
326 if (vars.c.select() == BoolVarBranch::SEL_NONE) {
327 ViewSel<BoolView>* vs[2] = {
328 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
329 };
330 postviewvalbrancher<BoolView,2,int,1>(home,xv,vs,vsc,bf,vvp);
331 } else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
332 ViewSel<BoolView>* vs[3] = {
333 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
334 Branch::viewsel(home,vars.c)
335 };
336 postviewvalbrancher<BoolView,3,int,1>(home,xv,vs,vsc,bf,vvp);
337 } else {
338 ViewSel<BoolView>* vs[4] = {
339 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
340 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
341 };
342 postviewvalbrancher<BoolView,4,int,1>(home,xv,vs,vsc,bf,vvp);
343 }
344 }
345 }
346
347 void
349 BoolVarArgs xv(1); xv[0]=x;
350 assign(home, xv, BOOL_VAR_NONE(), ba, nullptr, vvp);
351 }
352
353#ifdef GECODE_HAS_CBS
354
355 void
356 cbsbranch(Home home, const IntVarArgs& x) {
357 using namespace Int;
358 if (home.failed()) return;
359 ViewArray<IntView> y(home,x);
360 Branch::CBSBrancher<IntView>::post(home,y);
361 }
362
363 void
364 cbsbranch(Home home, const BoolVarArgs& x) {
365 using namespace Int;
366 if (home.failed()) return;
367 ViewArray<BoolView> y(home,x);
368 Branch::CBSBrancher<BoolView>::post(home,y);
369 }
370
371#endif
372
373}
374
375// STATISTICS: int-post
Which values to select for assignment.
Definition int.hh:5000
Which values to select for branching first.
Definition int.hh:4889
Passing Boolean variables.
Definition int.hh:712
Which Boolean variable to select for branching.
Definition int.hh:4656
void expand(Home home, const BoolVarArgs &x)
Expand decay factor into AFC or action.
Definition var.hpp:345
@ SEL_RND
Random (uniform, for tie breaking)
Definition int.hh:4661
@ SEL_NONE
First unassigned.
Definition int.hh:4660
Boolean integer variables.
Definition int.hh:512
Home class for posting propagators
Definition core.hpp:856
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4048
Which values to select for assignment.
Definition int.hh:4971
Which values to select for branching first.
Definition int.hh:4854
@ SEL_VALUES_MIN
Select all values starting from smallest.
Definition int.hh:4867
@ SEL_VALUES_MAX
Select all values starting from largest.
Definition int.hh:4868
Select select(void) const
Return selection strategy.
Definition val.hpp:49
Passing integer variables.
Definition int.hh:656
Which integer variable to select for branching.
Definition int.hh:4570
void expand(Home home, const IntVarArgs &x)
Expand AFC, action, and CHB.
Definition var.hpp:74
@ SEL_RND
Random (uniform, for tie breaking)
Definition int.hh:4575
@ SEL_NONE
First unassigned.
Definition int.hh:4574
Integer variables.
Definition int.hh:371
Combine variable selection criteria for tie-breaking.
Definition tiebreak.hpp:38
VarBranch a
Branching criteria to try in order.
Definition tiebreak.hpp:41
Base class for value selection and commit.
View arrays.
Definition array.hpp:253
Select the first unassigned view.
Definition view-sel.hpp:109
Abstract class for view selection.
Definition view-sel.hpp:44
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
std::function< bool(const Space &home, IntVar x, int i)> IntBranchFilter
Branch filter function type for integer variables.
Definition int.hh:4176
std::function< bool(const Space &home, BoolVar x, int i)> BoolBranchFilter
Branch filter function type for Boolean variables.
Definition int.hh:4186
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition view-sel.cpp:39
void postviewvaluesbrancher(Home home, ViewArray< IntView > &x, ViewSel< IntView > *vs[n], IntBranchFilter bf, IntVarValPrint vvp)
Post brancher for view and values.
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Gecode toplevel namespace
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition ipl.hpp:43
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:364
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
void postviewvalbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Post view value brancher.
Definition view-val.hpp:341
std::function< void(const Space &home, const Brancher &b, unsigned int a, IntVar x, int i, const int &n, std::ostream &o)> IntVarValPrint
Function type for printing branching alternatives for integer variables.
Definition int.hh:4552
std::function< void(const Space &home, const Brancher &b, unsigned int a, BoolVar x, int i, const int &n, std::ostream &o)> BoolVarValPrint
Function type for printing branching alternatives for Boolean variables.
Definition int.hh:4559
Post propagator for SetVar x
Definition set.hh:767