Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace FlatZinc {
39 
42  : VarBranch<IntVar>(d), s(s0) {}
43 
46  : s(s0), iafc(i), bafc(b) {}
47 
50  : s(s0), iaction(i), baction(b) {}
51 
54  : s(s0), ichb(i), bchb(b) {}
55 
58  return s;
59  }
60 
63  return iafc;
64  }
67  return bafc;
68  }
69 
72  return iaction;
73  }
76  return baction;
77  }
78 
81  return ichb;
82  }
85  return bchb;
86  }
87  forceinline void
89  switch (select()) {
92  if (!iafc)
93  iafc = IntAFC(home,x,decay());
94  if (!bafc)
95  bafc = BoolAFC(home,y,decay());
96  break;
99  if (!iaction)
100  iaction = IntAction(home,x,decay());
101  if (!baction)
102  baction = BoolAction(home,y,decay());
103  break;
106  if (!ichb)
107  ichb = IntCHB(home,x);
108  if (!bchb)
109  bchb = BoolCHB(home,y);
110  break;
111  default: ;
112  }
113  }
114 
115 
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  inline IntBoolVarBranch
164  }
165 
166 
167 
170  : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
173  : iafc(m.iafc), bafc(m.bafc) {}
174  forceinline double
176  return x.afc();
177  }
178  forceinline double
180  return x.afc();
181  }
182  forceinline void
184  iafc.~IntAFC();
185  bafc.~BoolAFC();
186  }
187 
188 
191  : iafc(ibvb.intafc()), bafc(ibvb.boolafc()) {}
194  : iafc(m.iafc), bafc(m.bafc) {}
195  forceinline double
197  return x.afc() / x.size();
198  }
199  forceinline double
201  return x.afc() / 2.0;
202  }
203  forceinline void
205  iafc.~IntAFC();
206  bafc.~BoolAFC();
207  }
208 
209 
212  : iaction(ibvb.intaction()), baction(ibvb.boolaction()) {}
215  : iaction(m.iaction), baction(m.baction) {}
216  forceinline double
218  return iaction[i];
219  }
220  forceinline double
222  return baction[i];
223  }
224  forceinline void
226  iaction.~IntAction();
227  baction.~BoolAction();
228  }
229 
230 
233  : iaction(ibvb.intaction()), baction(ibvb.boolaction()) {}
236  : iaction(m.iaction), baction(m.baction) {}
237  forceinline double
239  return iaction[i] / x.size();
240  }
241  forceinline double
243  return baction[i] / 2.0;
244  }
245  forceinline void
247  iaction.~IntAction();
248  baction.~BoolAction();
249  }
250 
251 
254  : ichb(ibvb.intchb()), bchb(ibvb.boolchb()) {}
257  : ichb(m.ichb), bchb(m.bchb) {}
258  forceinline double
260  return ichb[i];
261  }
262  forceinline double
264  return bchb[i];
265  }
266  forceinline void
268  ichb.~IntCHB();
269  bchb.~BoolCHB();
270  }
271 
272 
275  : ichb(ibvb.intchb()), bchb(ibvb.boolchb()) {}
278  : ichb(m.ichb), bchb(m.bchb) {}
279  forceinline double
281  return ichb[i] / x.size();
282  }
283  forceinline double
285  return bchb[i] / 2.0;
286  }
287  forceinline void
289  ichb.~IntCHB();
290  bchb.~BoolCHB();
291  }
292 
293 
295  PosIntChoice::PosIntChoice(const Brancher& b, unsigned int a, int p, int n)
296  : Choice(b,a), _pos(p), _val(n) {}
297  forceinline int
298  PosIntChoice::pos(void) const {
299  return _pos;
300  }
301  forceinline int
302  PosIntChoice::val(void) const {
303  return _val;
304  }
305 
306 
314  : Brancher(home), x(x0), y(y0), start(0), xvsc(xvsc0), yvsc(yvsc0) {
315  home.notice(*this,AP_DISPOSE,true);
316  }
317 
321  : Brancher(home,b), start(b.start),
322  xvsc(b.xvsc->copy(home)), yvsc(b.yvsc->copy(home)) {
323  x.update(home,b.x);
324  y.update(home,b.y);
325  }
326 
327  forceinline size_t
329  home.ignore(*this,AP_DISPOSE,true);
330  xvsc->dispose(home);
331  yvsc->dispose(home);
332  (void) Brancher::dispose(home);
333  return sizeof(IntBoolBrancherBase);
334  }
335 
336 
337  template<class Merit>
343  Merit& m,
346  : IntBoolBrancherBase(home,x,y,xvsc,yvsc), merit(m) {}
347 
348  template<class Merit>
349  forceinline void
351  post(Home home,
354  Merit& m,
357  (void) new (home) IntBoolBrancher<Merit>(home, x, y, m, xvsc, yvsc);
358  }
359 
360  template<class Merit>
364  : IntBoolBrancherBase(home,b), merit(home, b.merit) {
365  }
366 
367  template<class Merit>
368  Actor*
370  return new (home) IntBoolBrancher<Merit>(home,*this);
371  }
372 
373  template<class Merit>
374  const Choice*
376  int p = start;
377  double m;
378  if (p < x.size()) {
379  assert(!x[p].assigned());
380  m=merit(x[p],p);
381  for (int i=p+1; i<x.size(); i++)
382  if (!x[i].assigned()) {
383  double mi = merit(x[i],i);
384  if (mi > m) {
385  m=mi; p=i;
386  }
387  }
388  for (int i=0; i<y.size(); i++)
389  if (!y[i].assigned()) {
390  double mi = merit(y[i],i);
391  if (mi > m) {
392  m=mi; p=i+x.size();
393  }
394  }
395  } else {
396  assert(!y[p-x.size()].assigned());
397  m=merit(y[p-x.size()],p-x.size());
398  for (int i=p-x.size()+1; i<y.size(); i++)
399  if (!y[i].assigned()) {
400  double mi = merit(y[i],i);
401  if (mi > m) {
402  m=mi; p=i+x.size();
403  }
404  }
405  }
406  int v;
407  if (p < x.size()) {
408  v=xvsc->val(home,x[p],p);
409  } else {
410  v=yvsc->val(home,y[p-x.size()],p-x.size());
411  }
412  return new PosIntChoice(*this,2,p,v);
413  }
414 
415  template<class Merit>
416  size_t
418  merit.dispose();
419  (void) IntBoolBrancherBase::dispose(home);
420  return sizeof(IntBoolBrancher<Merit>);
421  }
422 
423 
425  i2b(const IntValBranch& ivb) {
426  switch (ivb.select()) {
431  return BOOL_VAL_MIN();
435  return BOOL_VAL_MAX();
437  return BOOL_VAL_RND(ivb.rnd());
439  default:
440  GECODE_NEVER;
441  }
442  GECODE_NEVER;
443  return BOOL_VAL_MIN();
444  }
445 
446 }}
447 
448 // STATISTICS: flatzinc-branch
449 
BoolCHB boolchb(void) const
Return Boolean AFC.
Definition: branch.hpp:84
BoolValBranch BOOL_VAL_RND(Rnd r)
Select random value.
Definition: val.hpp:144
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:238
BoolAction baction
Boolean action.
Definition: branch.hh:69
IntBoolVarBranch(Select s, double d)
Initialize with selection strategy s and decay factor d.
Definition: branch.hpp:41
ValSelCommitBase< Int::IntView, int > * xvsc
Integer value selection and commit object.
Definition: branch.hh:277
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:351
Merit merit
Selection by maximal merit.
Definition: branch.hh:310
With largest accumulated failure count.
Definition: branch.hh:52
IntBoolVarBranch INTBOOL_VAR_ACTION_SIZE_MAX(double d=1.0)
Select variable with largest action divided by domain size.
Definition: branch.hpp:150
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1375
IntCHB ichb
Integer CHB information.
Definition: branch.hh:233
Which values to select for branching first.
Definition: int.hh:4686
Actor must always be disposed.
Definition: core.hpp:554
IntCHB intchb(void) const
Return integer CHB.
Definition: branch.hpp:80
Which values to select for branching first.
Definition: int.hh:4651
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:295
void dispose(void)
Dispose.
Definition: branch.hpp:183
IntAFC iafc
Integer AFC information.
Definition: branch.hh:153
Select smallest value.
Definition: int.hh:4655
Rnd rnd(void) const
Return random number generator.
Definition: val.hpp:94
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:280
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:75
virtual Actor * copy(Space &home)
Perform cloning.
Definition: branch.hpp:369
Select the smallest range of the variable domain if it has several ranges, otherwise select values no...
Definition: int.hh:4661
IntAction iaction
Integer action.
Definition: branch.hh:67
int start
Unassigned views start here (might be in x or y)
Definition: branch.hh:275
void dispose(void)
Dispose.
Definition: branch.hpp:288
Select by maximal Action over size.
Definition: branch.hh:190
#define forceinline
Definition: config.hpp:182
Choice storing position and value
Definition: branch.hh:250
Computation spaces.
Definition: core.hpp:1668
Base class for value selection and commit.
Base-class for both propagators and branchers.
Definition: core.hpp:620
BoolAFC bafc
Boolean AFC information.
Definition: branch.hh:135
void expand(Home home, const IntVarArgs &x, const BoolVarArgs &y)
Expand AFC, action, and CHB.
Definition: branch.hpp:88
Select
Which variable selection.
Definition: branch.hh:51
Select by maximal AFC.
Definition: branch.hh:130
Gecode::IntSet d(v, 7)
void dispose(void)
Dispose.
Definition: branch.hpp:267
BoolCHB bchb
Boolean CHB information.
Definition: branch.hh:235
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
BoolCHB bchb
Boolean CHB information.
Definition: branch.hh:215
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:134
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1368
With largest CHB Q-score divided by domain size.
Definition: branch.hh:57
BoolAction baction
Boolean Action information.
Definition: branch.hh:175
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:139
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Base-class for brancher for integer and Boolean views.
Definition: branch.hh:268
Select by maximal CHB.
Definition: branch.hh:210
With largest accumulated failure count divided by domain size.
Definition: branch.hh:55
MeritMaxCHB(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:253
IntBoolVarBranch INTBOOL_VAR_AFC_MAX(double d=1.0)
Variable selection for both integer and Boolean variables.
Definition: branch.hpp:118
double decay(void) const
Return decay factor.
Definition: var.hpp:184
Select greatest value not greater than the median.
Definition: int.hh:4656
ViewArray< Int::BoolView > y
Boolean views to branch on.
Definition: branch.hh:273
Which integer or Boolean variable to select for branching.
Definition: branch.hh:48
Select select(void) const
Return selection strategy.
Definition: val.hpp:53
ViewArray< Int::IntView > x
Integer views to branch on.
Definition: branch.hh:271
Recording AFC information for integer variables.
Definition: int.hh:4073
MeritMaxCHBSize(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:274
Select select(void) const
Return selection strategy.
Definition: branch.hpp:57
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:175
Recording AFC information for Boolean variables.
Definition: int.hh:4113
BoolValBranch i2b(const IntValBranch &ivb)
Map respective integer value selection to Boolean value selection.
Definition: branch.hpp:425
Recording actions for Boolean variables.
Definition: int.hh:4204
IntAFC iafc
Integer AFC information.
Definition: branch.hh:133
IntCHB ichb
Integer CHB information.
Definition: branch.hh:213
Recording CHB for integer variables.
Definition: int.hh:4255
BoolAFC bafc
Boolean AFC information.
Definition: branch.hh:155
void dispose(void)
Dispose.
Definition: branch.hpp:225
Passing integer variables.
Definition: int.hh:637
IntBoolBrancher(Space &home, IntBoolBrancher &b)
Constructor for cloning b.
Definition: branch.hpp:363
Select by maximal AFC over size.
Definition: branch.hh:150
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3139
virtual const Choice * choice(Space &home)
Return choice.
Definition: branch.hpp:375
Passing Boolean variables.
Definition: int.hh:691
MeritMaxAction(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:211
Brancher for integer and Boolean views.
Definition: branch.hh:307
Select values greater than mean of smallest and largest value.
Definition: int.hh:4660
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition: branch.hpp:417
IntBoolBrancherBase(Space &home, IntBoolBrancherBase &b)
Constructor for cloning b.
Definition: branch.hpp:320
Select by maximal CHB over size.
Definition: branch.hh:230
IntAFC iafc
Integer AFC.
Definition: branch.hh:63
MeritMaxAFCSize(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:190
const int v[7]
Definition: distinct.cpp:263
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition: ipl.hpp:47
IntAction iaction
Integer Action information.
Definition: branch.hh:173
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Integer view for integer variables.
Definition: view.hpp:129
Select the largest range of the variable domain if it has several ranges, otherwise select values gre...
Definition: int.hh:4662
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:259
IntAction intaction(void) const
Return integer action.
Definition: branch.hpp:71
Variable branching information.
Definition: var.hpp:59
Select values not greater than mean of smallest and largest value.
Definition: int.hh:4659
With largest action divided by domain size.
Definition: branch.hh:56
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:3944
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3172
int val(void) const
Return value to assign to.
Definition: branch.hpp:302
Select by maximal Action.
Definition: branch.hh:170
IntBoolVarBranch INTBOOL_VAR_AFC_SIZE_MAX(double d=1.0)
Select variable with largest accumulated failure count divided by domain size.
Definition: branch.hpp:142
IntCHB ichb
Integer CHB.
Definition: branch.hh:71
IntBoolVarBranch INTBOOL_VAR_CHB_MAX(double d=1.0)
Select variable with largest CHB Q-score.
Definition: branch.hpp:134
Integer variables.
Definition: int.hh:351
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Select random value.
Definition: int.hh:4658
IntAFC intafc(void) const
Return integer AFC.
Definition: branch.hpp:62
ValSelCommitBase< Int::BoolView, int > * yvsc
Boolean value selection and commit object.
Definition: branch.hh:279
IntAction iaction
Integer Action information.
Definition: branch.hh:193
BoolAction baction
Boolean Action information.
Definition: branch.hh:195
Post propagator for SetVar x
Definition: set.hh:769
BoolCHB bchb
Boolean CHB.
Definition: branch.hh:73
MeritMaxActionSize(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:232
Recording CHB for Boolean variables.
Definition: int.hh:4299
void dispose(void)
Dispose.
Definition: branch.hpp:204
MeritMaxAFC(Space &home, const IntBoolVarBranch &ibvb)
Constructor for initialization.
Definition: branch.hpp:169
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:196
IntBoolVarBranch INTBOOL_VAR_ACTION_MAX(double d=1.0)
Select variable with highest action.
Definition: branch.hpp:126
Gecode toplevel namespace
double operator()(Int::IntView x, int i) const
Return merit.
Definition: branch.hpp:217
BoolAction boolaction(void) const
Return Boolean action.
Definition: branch.hpp:75
Select largest value.
Definition: int.hh:4657
BoolAFC boolafc(void) const
Return Boolean AFC.
Definition: branch.hpp:66
BoolAFC bafc
Boolean AFC.
Definition: branch.hh:65
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1203
Home class for posting propagators
Definition: core.hpp:846
Select value according to user-defined functions.
Definition: int.hh:4663
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
virtual Actor * copy(Space &home)=0
Create copy.
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition: branch.hpp:328
IntBoolVarBranch INTBOOL_VAR_CHB_SIZE_MAX(double d=1.0)
Select variable with largest CHB Q-score divided by domain size.
Definition: branch.hpp:158
int pos(void) const
Return position of view to assign.
Definition: branch.hpp:298
Recording actions for integer variables.
Definition: int.hh:4159
double afc(void) const
Return accumulated failure count.
Definition: view.hpp:473
Select s
Which variable to select.
Definition: branch.hh:61
Boolean view for Boolean variables.
Definition: view.hpp:1329