Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
39
43
47
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
117 inline IntBoolVarBranch
121 inline IntBoolVarBranch
125 inline IntBoolVarBranch
129 inline IntBoolVarBranch
133 inline IntBoolVarBranch
137 inline IntBoolVarBranch
141 inline IntBoolVarBranch
145 inline IntBoolVarBranch
149 inline IntBoolVarBranch
153 inline IntBoolVarBranch
157 inline IntBoolVarBranch
161
162
163
166 : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
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()) {}
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()) {}
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()) {}
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()) {}
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()) {}
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>
343
344 template<class Merit>
345 forceinline void
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
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual Actor * copy(Space &home)=0
Create copy.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
Recording AFC information for Boolean variables.
Definition int.hh:4331
Recording actions for Boolean variables.
Definition int.hh:4422
Recording CHB for Boolean variables.
Definition int.hh:4517
Which values to select for branching first.
Definition int.hh:4904
Passing Boolean variables.
Definition int.hh:721
Base-class for branchers.
Definition core.hpp:1444
friend class Space
Definition core.hpp:1446
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3612
Choice for performing commit
Definition core.hpp:1414
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition core.hpp:3773
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
int start
Unassigned views start here (might be in x or y)
Definition branch.hh:271
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
Merit merit
Selection by maximal merit.
Definition branch.hh:306
IntBoolBrancher(Space &home, IntBoolBrancher &b)
Constructor for cloning b.
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
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
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
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
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
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
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
BoolCHB bchb
Boolean CHB information.
Definition branch.hh:231
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
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
FloatValImpType x
Implementation of float value.
Definition float.hh:425
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3223
Recording AFC information for integer variables.
Definition int.hh:4291
Recording actions for integer variables.
Definition int.hh:4377
Recording CHB for integer variables.
Definition int.hh:4473
Which values to select for branching first.
Definition int.hh:4869
@ SEL_RND
Select random value.
Definition int.hh:4876
@ SEL_SPLIT_MAX
Select values greater than mean of smallest and largest value.
Definition int.hh:4878
@ SEL_MIN
Select smallest value.
Definition int.hh:4873
@ SEL_MAX
Select largest value.
Definition int.hh:4875
@ SEL_RANGE_MAX
Select the largest range of the variable domain if it has several ranges, otherwise select values gre...
Definition int.hh:4880
@ SEL_RANGE_MIN
Select the smallest range of the variable domain if it has several ranges, otherwise select values no...
Definition int.hh:4879
@ SEL_VAL_COMMIT
Select value according to user-defined functions.
Definition int.hh:4881
@ SEL_MED
Select greatest value not greater than the median.
Definition int.hh:4874
@ SEL_SPLIT_MIN
Select values not greater than mean of smallest and largest value.
Definition int.hh:4877
Select select(void) const
Return selection strategy.
Definition val.hpp:49
Passing integer variables.
Definition int.hh:662
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:1744
Rnd rnd(void) const
Return random number generator.
Definition val.hpp:90
Base class for value selection and commit.
double decay(void) const
Definition var.hpp:180
View arrays.
Definition array.hpp:253
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4081
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Interpreter for the FlatZinc language.
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
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:773
BoolValBranch BOOL_VAL_RND(Rnd r)
Select random value.
Definition val.hpp:140
Post propagator for SetVar x
Definition set.hh:773
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56