Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
branch.hh
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#ifndef __GECODE_FLATZINC_BRANCH_HH__
35#define __GECODE_FLATZINC_BRANCH_HH__
36
37#include <gecode/int.hh>
38#include <gecode/int/branch.hh>
39#include <gecode/flatzinc.hh>
40
41namespace Gecode { namespace FlatZinc {
42
96
98
99
124
127 protected:
132 public:
134 MeritMaxAFC(Space& home, const IntBoolVarBranch& ibvb);
136 MeritMaxAFC(Space& home, MeritMaxAFC& m);
138 double operator()(Int::IntView x, int i) const;
140 double operator()(Int::BoolView x, int i) const;
142 void dispose(void);
143 };
144
147 protected:
152 public:
154 MeritMaxAFCSize(Space& home, const IntBoolVarBranch& ibvb);
158 double operator()(Int::IntView x, int i) const;
160 double operator()(Int::BoolView x, int i) const;
162 void dispose(void);
163 };
164
167 protected:
172 public:
174 MeritMaxAction(Space& home, const IntBoolVarBranch& ibvb);
178 double operator()(Int::IntView x, int i) const;
180 double operator()(Int::BoolView x, int i) const;
182 void dispose(void);
183 };
184
187 protected:
192 public:
194 MeritMaxActionSize(Space& home, const IntBoolVarBranch& ibvb);
198 double operator()(Int::IntView x, int i) const;
200 double operator()(Int::BoolView x, int i) const;
202 void dispose(void);
203 };
204
207 protected:
212 public:
214 MeritMaxCHB(Space& home, const IntBoolVarBranch& ibvb);
216 MeritMaxCHB(Space& home, MeritMaxCHB& m);
218 double operator()(Int::IntView x, int i) const;
220 double operator()(Int::BoolView x, int i) const;
222 void dispose(void);
223 };
224
227 protected:
232 public:
234 MeritMaxCHBSize(Space& home, const IntBoolVarBranch& ibvb);
238 double operator()(Int::IntView x, int i) const;
240 double operator()(Int::BoolView x, int i) const;
242 void dispose(void);
243 };
244
247 private:
249 int _pos;
251 int _val;
252 public:
254 PosIntChoice(const Brancher& b, unsigned int a, int p, int n);
256 int pos(void) const;
258 int val(void) const;
260 virtual void archive(Archive& e) const;
261 };
262
265 protected:
271 mutable int start;
283 public:
285 virtual bool status(const Space& home) const;
287 virtual const Choice* choice(Space& home) = 0;
289 virtual const Choice* choice(const Space& home, Archive& e);
291 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
293 virtual NGL* ngl(Space& home, const Choice& c, unsigned int b) const;
295 virtual void print(const Space& home, const Choice& c, unsigned int b,
296 std::ostream& o) const;
298 virtual size_t dispose(Space& home);
299 };
300
302 template<class Merit>
304 protected:
306 Merit merit;
312 Merit& m,
315 public:
317 virtual const Choice* choice(Space& home);
319 virtual Actor* copy(Space& home);
321 static void post(Home home,
323 Merit& m,
327 virtual size_t dispose(Space& home);
328 };
329
331 BoolValBranch i2b(const IntValBranch& ivb);
332
335 branch(Home home, const IntVarArgs& x, const BoolVarArgs& y,
336 IntBoolVarBranch vars, IntValBranch vals);
337
338}}
339
341
342#endif
343
344// STATISTICS: flatzinc-branch
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
Archive representation
Definition archive.hpp:42
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
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
virtual const Choice * choice(Space &home)=0
Return choice.
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.
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
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
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
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
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
Home class for posting propagators
Definition core.hpp:856
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
Passing integer variables.
Definition int.hh:656
Boolean view for Boolean variables.
Definition view.hpp:1380
Integer view for integer variables.
Definition view.hpp:129
No-good literal recorded during search.
Definition core.hpp:1340
Computation spaces.
Definition core.hpp:1742
Base class for value selection and commit.
Variable branching information.
Definition var.hpp:55
View arrays.
Definition array.hpp:253
#define GECODE_FLATZINC_EXPORT
Definition flatzinc.hh:75
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
void branch(Home home, const IntVarArgs &x, const BoolVarArgs &y, IntBoolVarBranch vars, IntValBranch vals)
Branch function for integer and Boolean variables.
Definition branch.cpp:120
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
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
Post propagator for SetVar x
Definition set.hh:767
#define GECODE_VTABLE_EXPORT
Definition support.hh:72