Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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, 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 
34 
36 
37 namespace Gecode { namespace FlatZinc {
38 
39  void
41  Choice::archive(e);
42  e << _pos;
43  e << _val;
44  }
45 
46 
47  bool
49  if (start < x.size()) {
50  for (int i=start; i < x.size(); i++)
51  if (!x[i].assigned()) {
52  start = i;
53  return true;
54  }
55  start = x.size();
56  }
57  for (int i=start-x.size(); i < y.size(); i++)
58  if (!y[i].assigned()) {
59  start = x.size() + i;
60  return true;
61  }
62  return false;
63  }
64 
67  unsigned int b) {
68  const PosIntChoice& c
69  = static_cast<const PosIntChoice&>(_c);
70  int p=c.pos(); int n=c.val();
71  if (p < x.size()) {
72  return me_failed(xvsc->commit(home,b,x[p],p,n)) ?
73  ES_FAILED : ES_OK;
74  } else {
75  p -= x.size();
76  return me_failed(yvsc->commit(home,b,y[p],p,n)) ?
77  ES_FAILED : ES_OK;
78  }
79  }
80 
81  NGL*
83  unsigned int b) const {
84  const PosIntChoice& c
85  = static_cast<const PosIntChoice&>(_c);
86  int p=c.pos(); int n=c.val();
87  if (p < x.size()) {
88  return xvsc->ngl(home,b,x[p],n);
89  } else {
90  p -= x.size();
91  return yvsc->ngl(home,b,y[p],n);
92  }
93  }
94 
95  void
97  unsigned int b,
98  std::ostream& o) const {
99  const PosIntChoice& c
100  = static_cast<const PosIntChoice&>(_c);
101  int p=c.pos(); int n=c.val();
102  if (p < x.size()) {
103  xvsc->print(home,b,x[p],p,n,o);
104  } else {
105  p -= x.size();
106  yvsc->print(home,b,y[p],p,n,o);
107  }
108  }
109 
110  const Choice*
112  (void) home;
113  int p; e >> p;
114  int v; e >> v;
115  return new PosIntChoice(*this,2,p,v);
116  }
117 
118 
119  void
120  branch(Home home, const IntVarArgs& x, const BoolVarArgs& y,
121  IntBoolVarBranch vars, IntValBranch vals) {
122  if (home.failed()) return;
123  vars.expand(home,x,y);
124  ViewArray<Int::IntView> xv(home,x);
125  ViewArray<Int::BoolView> yv(home,y);
127  Int::Branch::valselcommit(home,vals);
129  Int::Branch::valselcommit(home,i2b(vals));
130  switch (vars.select()) {
132  {
133  MeritMaxAFC m(home,vars);
134  IntBoolBrancher<MeritMaxAFC>::post(home,xv,yv,m,xvsc,yvsc);
135  }
136  break;
138  {
139  MeritMaxAction m(home,vars);
140  IntBoolBrancher<MeritMaxAction>::post(home,xv,yv,m,xvsc,yvsc);
141  }
142  break;
144  {
145  MeritMaxCHB m(home,vars);
146  IntBoolBrancher<MeritMaxCHB>::post(home,xv,yv,m,xvsc,yvsc);
147  }
148  break;
150  {
151  MeritMaxAFCSize m(home,vars);
152  IntBoolBrancher<MeritMaxAFCSize>::post(home,xv,yv,m,xvsc,yvsc);
153  }
154  break;
156  {
157  MeritMaxActionSize m(home,vars);
158  IntBoolBrancher<MeritMaxActionSize>::post(home,xv,yv,m,xvsc,yvsc);
159  }
160  break;
162  {
163  MeritMaxCHBSize m(home,vars);
164  IntBoolBrancher<MeritMaxCHBSize>::post(home,xv,yv,m,xvsc,yvsc);
165  }
166  break;
167  default:
168  GECODE_NEVER;
169  }
170  }
171 
172 }}
173 
174 // STATISTICS: flatzinc-branch
175 
struct Gecode::@602::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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Archive representation
Definition: archive.hpp:42
Passing Boolean variables.
Definition: int.hh:712
Choice for performing commit
Definition: core.hpp:1412
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:891
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
virtual const Choice * choice(Space &home)=0
Return choice.
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
Definition: branch.cpp:48
ValSelCommitBase< Int::BoolView, int > * yvsc
Boolean value selection and commit object.
Definition: branch.hh:275
virtual void print(const Space &home, const Choice &c, unsigned int b, std::ostream &o) const
Print branch for choice c and alternative b.
Definition: branch.cpp:96
virtual NGL * ngl(Space &home, const Choice &c, unsigned int b) const
Create no-good literal for choice c and alternative b.
Definition: branch.cpp:82
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int b)
Perform commit for choice c and alternative b.
Definition: branch.cpp:66
ValSelCommitBase< Int::IntView, int > * xvsc
Integer value selection and commit object.
Definition: branch.hh:273
int start
Unassigned views start here (might be in x or y)
Definition: branch.hh:271
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
void expand(Home home, const IntVarArgs &x, const BoolVarArgs &y)
Expand AFC, action, and CHB.
Definition: branch.hpp:84
Select select(void) const
Return selection strategy.
Definition: branch.hpp:53
@ 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
Select by maximal AFC.
Definition: branch.hh:126
Select by maximal Action over size.
Definition: branch.hh:186
Select by maximal Action.
Definition: branch.hh:166
Select by maximal CHB over size.
Definition: branch.hh:226
Select by maximal CHB.
Definition: branch.hh:206
Choice storing position and value
Definition: branch.hh:246
virtual void archive(Archive &e) const
Archive into e.
Definition: branch.cpp:40
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 branching first.
Definition: int.hh:4854
Passing integer variables.
Definition: int.hh:656
No-good literal recorded during search.
Definition: core.hpp:1340
Computation spaces.
Definition: core.hpp:1742
Base class for value selection and commit.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1156
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
BoolValBranch i2b(const IntValBranch &ivb)
Map respective integer value selection to Boolean value selection.
Definition: branch.hpp:421
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
void branch(Home home, SetVar x, SetValBranch vals, SetVarValPrint vvp)
Branch over x with value selection vals.
Definition: branch.cpp:101
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259
Multi _c(Gecode::IntArgs({1, 2, 3}))
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56