Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
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 
36 namespace Gecode {
37 
38  void
39  branch(Home home, const IntVarArgs& x,
40  IntVarBranch vars, IntValBranch vals,
41  IntBranchFilter bf,
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()) {
52  Branch::postviewvaluesbrancher<1,true>(home,xv,vs,bf,vvp);
53  break;
55  Branch::postviewvaluesbrancher<1,false>(home,xv,vs,bf,vvp);
56  break;
57  default:
58  postviewvalbrancher<IntView,1,int,2>
59  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
60  break;
61  }
62  }
63 
64  void
65  branch(Home home, const IntVarArgs& x,
67  IntBranchFilter bf,
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()) {
94  Branch::postviewvaluesbrancher<2,true>(home,xv,vs,bf,vvp);
95  break;
97  Branch::postviewvaluesbrancher<2,false>(home,xv,vs,bf,vvp);
98  break;
99  default:
100  postviewvalbrancher<IntView,2,int,2>
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()) {
110  Branch::postviewvaluesbrancher<3,true>(home,xv,vs,bf,vvp);
111  break;
113  Branch::postviewvaluesbrancher<3,false>(home,xv,vs,bf,vvp);
114  break;
115  default:
116  postviewvalbrancher<IntView,3,int,2>
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()) {
126  Branch::postviewvaluesbrancher<4,true>(home,xv,vs,bf,vvp);
127  break;
129  Branch::postviewvaluesbrancher<4,false>(home,xv,vs,bf,vvp);
130  break;
131  default:
132  postviewvalbrancher<IntView,4,int,2>
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,
149  IntBranchFilter bf,
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  };
157  postviewvalbrancher<IntView,1,int,1>
158  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
159  }
160 
161  void
162  branch(Home home, const IntVarArgs& x,
164  IntBranchFilter bf,
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  };
189  postviewvalbrancher<IntView,2,int,1>
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  };
196  postviewvalbrancher<IntView,3,int,1>
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  };
203  postviewvalbrancher<IntView,4,int,1>
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,
219  BoolBranchFilter bf,
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  };
228  postviewvalbrancher<BoolView,1,int,2>
229  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
230  }
231 
232  void
233  branch(Home home, const BoolVarArgs& x,
235  BoolBranchFilter bf,
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,
288  BoolBranchFilter bf,
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  };
296  postviewvalbrancher<BoolView,1,int,1>
297  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
298  }
299 
300  void
301  assign(Home home, const BoolVarArgs& x,
303  BoolBranchFilter bf,
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);
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);
369  }
370 
371 #endif
372 
373 }
374 
375 // STATISTICS: int-post
Post propagator for SetVar x
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
VarBranch b
Definition: tiebreak.hpp:41
Select the first unassigned view.
Definition: view-sel.hpp:109
Combine variable selection criteria for tie-breaking.
Definition: tiebreak.hpp:38
Random (uniform, for tie breaking)
Definition: int.hh:4575
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
Passing integer variables.
Definition: int.hh:656
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition: view-sel.cpp:39
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
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
Random (uniform, for tie breaking)
Definition: int.hh:4661
Which values to select for branching first.
Definition: int.hh:4854
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
Which integer variable to select for branching.
Definition: int.hh:4570
Gecode toplevel namespace
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition: ipl.hpp:43
Which Boolean variable to select for branching.
Definition: int.hh:4656
Which values to select for assignment.
Definition: int.hh:4971
Passing Boolean variables.
Definition: int.hh:712
Home class for posting propagators
Definition: core.hpp:856
VarBranch d
Definition: tiebreak.hpp:41
Select select(void) const
Return selection strategy.
Definition: val.hpp:49
Boolean integer variables.
Definition: int.hh:512
VarBranch c
Definition: tiebreak.hpp:41
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with variable selection vars and value selection vals.
Definition: branch.cpp:111
Select all values starting from smallest.
Definition: int.hh:4867
Integer variables.
Definition: int.hh:371
First unassigned.
Definition: int.hh:4574
Base class for value selection and commit.
void expand(Home home, const IntVarArgs &x)
Expand AFC, action, and CHB.
Definition: var.hpp:74
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4048
void expand(Home home, const BoolVarArgs &x)
Expand decay factor into AFC or action.
Definition: var.hpp:345
std::function< bool(const Space &home, IntVar x, int i)> IntBranchFilter
Branch filter function type for integer variables.
Definition: int.hh:4176
Select all values starting from largest.
Definition: int.hh:4868
Which values to select for assignment.
Definition: int.hh:5000
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
std::function< bool(const Space &home, BoolVar x, int i)> BoolBranchFilter
Branch filter function type for Boolean variables.
Definition: int.hh:4186
First unassigned.
Definition: int.hh:4660
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:364
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
VarBranch a
Branching criteria to try in order.
Definition: tiebreak.hpp:41
Which values to select for branching first.
Definition: int.hh:4889