Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.9.4
branch.hpp
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, 2017
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
34namespace Gecode { namespace FlatZinc {
35
38 : VarBranch<IntVar>(d), s(s0) {}
39
42 : s(s0), iafc(i), bafc(b) {}
43
46 : s(s0), iaction(i), baction(b) {}
47
50 : s(s0), ichb(i), bchb(b) {}
51
54 return s;
55 }
56
59 return iafc;
60 }
63 return bafc;
64 }
65
68 return iaction;
69 }
72 return baction;
73 }
74
77 return ichb;
78 }
81 return bchb;
82 }
83 forceinline void
85 switch (select()) {
88 if (!iafc)
89 iafc = IntAFC(home,x,decay());
90 if (!bafc)
91 bafc = BoolAFC(home,y,decay());
92 break;
95 if (!iaction)
96 iaction = IntAction(home,x,decay());
97 if (!baction)
98 baction = BoolAction(home,y,decay());
99 break;
102 if (!ichb)
103 ichb = IntCHB(home,x);
104 if (!bchb)
105 bchb = BoolCHB(home,y);
106 break;
107 default: ;
108 }
109 }
110
111
112
113 inline IntBoolVarBranch
116 }
117 inline IntBoolVarBranch
120 }
121 inline IntBoolVarBranch
124 }
125 inline IntBoolVarBranch
128 }
129 inline IntBoolVarBranch
132 }
133 inline IntBoolVarBranch
136 }
137 inline IntBoolVarBranch
140 }
141 inline IntBoolVarBranch
144 }
145 inline IntBoolVarBranch
148 }
149 inline IntBoolVarBranch
152 }
153 inline IntBoolVarBranch
156 }
157 inline IntBoolVarBranch
160 }
161
162
163
166 : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
169 : iafc(m.iafc), bafc(m.bafc) {}
170 forceinline double
172 return x.afc();
173 }
174 forceinline double
176 return x.afc();
177 }
178 forceinline void
180 iafc.~IntAFC();
181 bafc.~BoolAFC();
182 }
183
184
187 : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
190 : iafc(m.iafc), bafc(m.bafc) {}
191 forceinline double
193 return x.afc() / x.size();
194 }
195 forceinline double
197 return x.afc() / 2.0;
198 }
199 forceinline void
201 iafc.~IntAFC();
202 bafc.~BoolAFC();
203 }
204
205
208 : iaction(ibvb.intaction()), baction(ibvb.boolaction()) {}
211 : iaction(m.iaction), baction(m.baction) {}
212 forceinline double
214 return iaction[i];
215 }
216 forceinline double
218 return baction[i];
219 }
220 forceinline void
222 iaction.~IntAction();
223 baction.~BoolAction();
224 }
225
226
229 : iaction(ibvb.intaction()), baction(ibvb.boolaction()) {}
232 : iaction(m.iaction), baction(m.baction) {}
233 forceinline double
235 return iaction[i] / x.size();
236 }
237 forceinline double
239 return baction[i] / 2.0;
240 }
241 forceinline void
243 iaction.~IntAction();
244 baction.~BoolAction();
245 }
246
247
250 : ichb(ibvb.intchb()), bchb(ibvb.boolchb()) {}
253 : ichb(m.ichb), bchb(m.bchb) {}
254 forceinline double
256 return ichb[i];
257 }
258 forceinline double
260 return bchb[i];
261 }
262 forceinline void
264 ichb.~IntCHB();
265 bchb.~BoolCHB();
266 }
267
268
271 : ichb(ibvb.intchb()), bchb(ibvb.boolchb()) {}
274 : ichb(m.ichb), bchb(m.bchb) {}
275 forceinline double
277 return ichb[i] / x.size();
278 }
279 forceinline double
281 return bchb[i] / 2.0;
282 }
283 forceinline void
285 ichb.~IntCHB();
286 bchb.~BoolCHB();
287 }
288
289
291 PosIntChoice::PosIntChoice(const Brancher& b, unsigned int a, int p, int n)
292 : Choice(b,a), _pos(p), _val(n) {}
293 forceinline int
294 PosIntChoice::pos(void) const {
295 return _pos;
296 }
297 forceinline int
298 PosIntChoice::val(void) const {
299 return _val;
300 }
301
302
310 : Brancher(home), x(x0), y(y0), start(0), xvsc(xvsc0), yvsc(yvsc0) {
311 home.notice(*this,AP_DISPOSE,true);
312 }
313
317 : Brancher(home,b), start(b.start),
318 xvsc(b.xvsc->copy(home)), yvsc(b.yvsc->copy(home)) {
319 x.update(home,b.x);
320 y.update(home,b.y);
321 }
322
323 forceinline size_t
325 home.ignore(*this,AP_DISPOSE,true);
326 xvsc->dispose(home);
327 yvsc->dispose(home);
328 (void) Brancher::dispose(home);
329 return sizeof(IntBoolBrancherBase);
330 }
331
332
333 template<class Merit>
339 Merit& m,
342 : IntBoolBrancherBase(home,x,y,xvsc,yvsc), merit(m) {}
343
344 template<class Merit>
345 forceinline void
347 post(Home home,
350 Merit& m,
353 (void) new (home) IntBoolBrancher<Merit>(home, x, y, m, xvsc, yvsc);
354 }
355
356 template<class Merit>
360 : IntBoolBrancherBase(home,b), merit(home, b.merit) {
361 }
362
363 template<class Merit>
364 Actor*
366 return new (home) IntBoolBrancher<Merit>(home,*this);
367 }
368
369 template<class Merit>
370 const Choice*
372 int p = start;
373 double m;
374 if (p < x.size()) {
375 assert(!x[p].assigned());
376 m=merit(x[p],p);
377 for (int i=p+1; i<x.size(); i++)
378 if (!x[i].assigned()) {
379 double mi = merit(x[i],i);
380 if (mi > m) {
381 m=mi; p=i;
382 }
383 }
384 for (int i=0; i<y.size(); i++)
385 if (!y[i].assigned()) {
386 double mi = merit(y[i],i);
387 if (mi > m) {
388 m=mi; p=i+x.size();
389 }
390 }
391 } else {
392 assert(!y[p-x.size()].assigned());
393 m=merit(y[p-x.size()],p-x.size());
394 for (int i=p-x.size()+1; i<y.size(); i++)
395 if (!y[i].assigned()) {
396 double mi = merit(y[i],i);
397 if (mi > m) {
398 m=mi; p=i+x.size();
399 }
400 }
401 }
402 int v;
403 if (p < x.size()) {
404 v=xvsc->val(home,x[p],p);
405 } else {
406 v=yvsc->val(home,y[p-x.size()],p-x.size());
407 }
408 return new PosIntChoice(*this,2,p,v);
409 }
410
411 template<class Merit>
412 size_t
414 merit.dispose();
415 (void) IntBoolBrancherBase::dispose(home);
416 return sizeof(IntBoolBrancher<Merit>);
417 }
418
419
421 i2b(const IntValBranch& ivb) {
422 switch (ivb.select()) {
427 return BOOL_VAL_MIN();
431 return BOOL_VAL_MAX();
433 return BOOL_VAL_RND(ivb.rnd());
435 default:
437 }
439 return BOOL_VAL_MIN();
440 }
441
442}}
443
444// STATISTICS: flatzinc-branch
445
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
Recording AFC information for Boolean variables.
Definition: int.hh:4316
Recording actions for Boolean variables.
Definition: int.hh:4407
Recording CHB for Boolean variables.
Definition: int.hh:4502
Which values to select for branching first.
Definition: int.hh:4889
Passing Boolean variables.
Definition: int.hh:712
Base-class for branchers.
Definition: core.hpp:1442
Choice for performing commit
Definition: core.hpp:1412
Base-class for brancher for integer and Boolean views.
Definition: branch.hh:264
ViewArray< Int::BoolView > y
Boolean views to branch on.
Definition: branch.hh:269
ViewArray< Int::IntView > x
Integer views to branch on.
Definition: branch.hh:267
IntBoolBrancherBase(Space &home, IntBoolBrancherBase &b)
Constructor for cloning b.
Definition: branch.hpp:316
ValSelCommitBase< Int::BoolView, int > * yvsc
Boolean value selection and commit object.
Definition: branch.hh:275
ValSelCommitBase< Int::IntView, int > * xvsc
Integer value selection and commit object.
Definition: branch.hh:273
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition: branch.hpp:324
Brancher for integer and Boolean views.
Definition: branch.hh:303
virtual const Choice * choice(Space &home)
Return choice.
Definition: branch.hpp:371
virtual Actor * copy(Space &home)
Perform cloning.
Definition: branch.hpp:365
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition: branch.hpp:413
IntBoolBrancher(Space &home, IntBoolBrancher &b)
Constructor for cloning b.
Definition: branch.hpp:359
static void post(Home home, ViewArray< Int::IntView > x, ViewArray< Int::BoolView > y, Merit &m, ValSelCommitBase< Int::IntView, int > *xvsc, ValSelCommitBase< Int::BoolView, int > *yvsc)
Post brancher.
Definition: branch.hpp:347
Which integer or Boolean variable to select for branching.
Definition: branch.hh:44
BoolCHB boolchb(void) const
Return Boolean AFC.
Definition: branch.hpp:80
IntAFC iafc
Integer AFC.
Definition: branch.hh:59
IntCHB intchb(void) const
Return integer CHB.
Definition: branch.hpp:76
BoolCHB bchb
Boolean CHB.
Definition: branch.hh:69
void expand(Home home, const IntVarArgs &x, const BoolVarArgs &y)
Expand AFC, action, and CHB.
Definition: branch.hpp:84
Select s
Which variable to select.
Definition: branch.hh:57
IntBoolVarBranch(Select s, double d)
Initialize with selection strategy s and decay factor d.
Definition: branch.hpp:37
BoolAFC bafc
Boolean AFC.
Definition: branch.hh:61
IntAction intaction(void) const
Return integer action.
Definition: branch.hpp:67
IntAFC intafc(void) const
Return integer AFC.
Definition: branch.hpp:58
BoolAFC boolafc(void) const
Return Boolean AFC.
Definition: branch.hpp:62
BoolAction boolaction(void) const
Return Boolean action.
Definition: branch.hpp:71
Select select(void) const
Return selection strategy.
Definition: branch.hpp:53
IntCHB ichb
Integer CHB.
Definition: branch.hh:67
BoolAction baction
Boolean action.
Definition: branch.hh:65
IntAction iaction
Integer action.
Definition: branch.hh:63
Select
Which variable selection.
Definition: branch.hh:47
@ SEL_ACTION_SIZE_MAX
With largest action divided by domain size.
Definition: branch.hh:52
@ SEL_CHB_SIZE_MAX
With largest CHB Q-score divided by domain size.
Definition: branch.hh:53
@ SEL_ACTION_MAX
With highest action.
Definition: branch.hh:49
@ SEL_AFC_MAX
With largest accumulated failure count.
Definition: branch.hh:48
@ SEL_CHB_MAX
With highest CHB Q-score.
Definition: branch.hh:50
@ SEL_AFC_SIZE_MAX
With largest accumulated failure count divided by domain size.
Definition: branch.hh:51
Select by maximal AFC over size.
Definition: branch.hh:146
IntAFC iafc
Integer AFC information.
Definition: branch.hh:149
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:192
BoolAFC bafc
Boolean AFC information.
Definition: branch.hh:151
MeritMaxAFCSize(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:186
void dispose(void)
Dispose.
Definition: branch.hpp:200
Select by maximal AFC.
Definition: branch.hh:126
MeritMaxAFC(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:165
void dispose(void)
Dispose.
Definition: branch.hpp:179
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:171
BoolAFC bafc
Boolean AFC information.
Definition: branch.hh:131
IntAFC iafc
Integer AFC information.
Definition: branch.hh:129
Select by maximal Action over size.
Definition: branch.hh:186
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:234
BoolAction baction
Boolean Action information.
Definition: branch.hh:191
MeritMaxActionSize(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:228
IntAction iaction
Integer Action information.
Definition: branch.hh:189
Select by maximal Action.
Definition: branch.hh:166
void dispose(void)
Dispose.
Definition: branch.hpp:221
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:213
BoolAction baction
Boolean Action information.
Definition: branch.hh:171
MeritMaxAction(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:207
IntAction iaction
Integer Action information.
Definition: branch.hh:169
Select by maximal CHB over size.
Definition: branch.hh:226
BoolCHB bchb
Boolean CHB information.
Definition: branch.hh:231
void dispose(void)
Dispose.
Definition: branch.hpp:284
IntCHB ichb
Integer CHB information.
Definition: branch.hh:229
MeritMaxCHBSize(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:270
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:276
Select by maximal CHB.
Definition: branch.hh:206
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:255
void dispose(void)
Dispose.
Definition: branch.hpp:263
MeritMaxCHB(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:249
BoolCHB bchb
Boolean CHB information.
Definition: branch.hh:211
IntCHB ichb
Integer CHB information.
Definition: branch.hh:209
Choice storing position and value
Definition: branch.hh:246
int pos(void) const
Return position of view to assign.
Definition: branch.hpp:294
int val(void) const
Return value to assign to.
Definition: branch.hpp:298
PosIntChoice(const Brancher &b, unsigned int a, int p, int n)
Initialize choice for brancher b, number of alternatives a, position p, and value n.
Definition: branch.hpp:291
Home class for posting propagators
Definition: core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
Recording AFC information for integer variables.
Definition: int.hh:4276
Recording actions for integer variables.
Definition: int.hh:4362
Recording CHB for integer variables.
Definition: int.hh:4458
Which values to select for branching first.
Definition: int.hh:4854
@ SEL_RND
Select random value.
Definition: int.hh:4861
@ SEL_SPLIT_MAX
Select values greater than mean of smallest and largest value.
Definition: int.hh:4863
@ SEL_MIN
Select smallest value.
Definition: int.hh:4858
@ SEL_MAX
Select largest value.
Definition: int.hh:4860
@ SEL_RANGE_MAX
Select the largest range of the variable domain if it has several ranges, otherwise select values gre...
Definition: int.hh:4865
@ SEL_RANGE_MIN
Select the smallest range of the variable domain if it has several ranges, otherwise select values no...
Definition: int.hh:4864
@ SEL_VAL_COMMIT
Select value according to user-defined functions.
Definition: int.hh:4866
@ SEL_MED
Select greatest value not greater than the median.
Definition: int.hh:4859
@ SEL_SPLIT_MIN
Select values not greater than mean of smallest and largest value.
Definition: int.hh:4862
Select select(void) const
Return selection strategy.
Definition: val.hpp:49
Passing integer variables.
Definition: int.hh:656
Integer variables.
Definition: int.hh:371
Boolean view for Boolean variables.
Definition: view.hpp:1380
Integer view for integer variables.
Definition: view.hpp:129
Computation spaces.
Definition: core.hpp:1742
Rnd rnd(void) const
Return random number generator.
Definition: val.hpp:90
Base class for value selection and commit.
Variable branching information.
Definition: var.hpp:55
double decay(void) const
Return decay factor.
Definition: var.hpp:180
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
double afc(void) const
Return accumulated failure count.
Definition: var.hpp:106
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1328
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
IntBoolVarBranch INTBOOL_VAR_CHB_SIZE_MAX(double d=1.0)
Select variable with largest CHB Q-score divided by domain size.
Definition: branch.hpp:154
IntBoolVarBranch INTBOOL_VAR_CHB_MAX(double d=1.0)
Select variable with largest CHB Q-score.
Definition: branch.hpp:130
IntBoolVarBranch INTBOOL_VAR_ACTION_MAX(double d=1.0)
Select variable with highest action.
Definition: branch.hpp:122
BoolValBranch i2b(const IntValBranch &ivb)
Map respective integer value selection to Boolean value selection.
Definition: branch.hpp:421
IntBoolVarBranch INTBOOL_VAR_AFC_SIZE_MAX(double d=1.0)
Select variable with largest accumulated failure count divided by domain size.
Definition: branch.hpp:138
IntBoolVarBranch INTBOOL_VAR_ACTION_SIZE_MAX(double d=1.0)
Select variable with largest action divided by domain size.
Definition: branch.hpp:146
IntBoolVarBranch INTBOOL_VAR_AFC_MAX(double d=1.0)
Variable selection for both integer and Boolean variables.
Definition: branch.hpp:114
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Gecode toplevel namespace
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition: ipl.hpp:43
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:130
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:135
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
BoolValBranch BOOL_VAL_RND(Rnd r)
Select random value.
Definition: val.hpp:140
Post propagator for SetVar x
Definition: set.hh:767
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const int v[7]
Definition: distinct.cpp:259
#define forceinline
Definition: config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56