this repo has no description
dekker.one
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
43 /// Which integer or Boolean variable to select for branching
44 class IntBoolVarBranch : public VarBranch<IntVar> {
45 public:
46 /// Which variable selection
47 enum Select {
48 SEL_AFC_MAX, ///< With largest accumulated failure count
49 SEL_ACTION_MAX, ///< With highest action
50 SEL_CHB_MAX, ///< With highest CHB Q-score
51 SEL_AFC_SIZE_MAX, ///< With largest accumulated failure count divided by domain size
52 SEL_ACTION_SIZE_MAX, ///< With largest action divided by domain size
53 SEL_CHB_SIZE_MAX ///< With largest CHB Q-score divided by domain size
54 };
55 protected:
56 /// Which variable to select
57 Select s;
58 /// Integer AFC
59 IntAFC iafc;
60 /// Boolean AFC
61 BoolAFC bafc;
62 /// Integer action
63 IntAction iaction;
64 /// Boolean action
65 BoolAction baction;
66 /// Integer CHB
67 IntCHB ichb;
68 /// Boolean CHB
69 BoolCHB bchb;
70 public:
71 /// Initialize with selection strategy \a s and decay factor \a d
72 IntBoolVarBranch(Select s, double d);
73 /// Initialize with selection strategy \a s and AFC \a i and \a b
74 IntBoolVarBranch(Select s, IntAFC i, BoolAFC b);
75 /// Initialize with selection strategy \a s and action \a i and \a b
76 IntBoolVarBranch(Select s, IntAction i, BoolAction b);
77 /// Initialize with selection strategy \a s and CHB \a i and \a b
78 IntBoolVarBranch(Select s, IntCHB i, BoolCHB b);
79 /// Return selection strategy
80 Select select(void) const;
81 /// Return integer AFC
82 IntAFC intafc(void) const;
83 /// Return Boolean AFC
84 BoolAFC boolafc(void) const;
85 /// Return integer action
86 IntAction intaction(void) const;
87 /// Return Boolean action
88 BoolAction boolaction(void) const;
89 /// Return integer CHB
90 IntCHB intchb(void) const;
91 /// Return Boolean AFC
92 BoolCHB boolchb(void) const;
93 /// Expand AFC, action, and CHB
94 void expand(Home home, const IntVarArgs& x, const BoolVarArgs& y);
95 };
96
97 /// Variable selection for both integer and Boolean variables
98 //@{
99 /// Select variable with largest accumulated failure count
100 IntBoolVarBranch INTBOOL_VAR_AFC_MAX(double d=1.0);
101 /// Select variable with largest accumulated failure count
102 IntBoolVarBranch INTBOOL_VAR_AFC_MAX(IntAFC ia, BoolAFC ba);
103 /// Select variable with highest action
104 IntBoolVarBranch INTBOOL_VAR_ACTION_MAX(double d=1.0);
105 /// Select variable with highest action
106 IntBoolVarBranch INTBOOL_VAR_ACTION_MAX(IntAction ia, BoolAction ba);
107 /// Select variable with largest CHB Q-score
108 IntBoolVarBranch INTBOOL_VAR_CHB_MAX(double d=1.0);
109 /// Select variable with largest CHB Q-score
110 IntBoolVarBranch INTBOOL_VAR_CHB_MAX(IntCHB ic, BoolCHB bc);
111 /// Select variable with largest accumulated failure count divided by domain size
112 IntBoolVarBranch INTBOOL_VAR_AFC_SIZE_MAX(double d=1.0);
113 /// Select variable with largest accumulated failure count divided by domain size
114 IntBoolVarBranch INTBOOL_VAR_AFC_SIZE_MAX(IntAFC ia, BoolAFC ba);
115 /// Select variable with largest action divided by domain size
116 IntBoolVarBranch INTBOOL_VAR_ACTION_SIZE_MAX(double d=1.0);
117 /// Select variable with largest action divided by domain size
118 IntBoolVarBranch INTBOOL_VAR_ACTION_SIZE_MAX(IntAction ia, BoolAction ba);
119 /// Select variable with largest CHB Q-score divided by domain size
120 IntBoolVarBranch INTBOOL_VAR_CHB_SIZE_MAX(double d=1.0);
121 /// Select variable with largest CHB Q-score divided by domain size
122 IntBoolVarBranch INTBOOL_VAR_CHB_SIZE_MAX(IntCHB ic, BoolCHB bc);
123 //@}
124
125 /// Select by maximal AFC
126 class MeritMaxAFC {
127 protected:
128 /// Integer AFC information
129 IntAFC iafc;
130 /// Boolean AFC information
131 BoolAFC bafc;
132 public:
133 /// Constructor for initialization
134 MeritMaxAFC(Space& home, const IntBoolVarBranch& ibvb);
135 /// Constructor for cloning
136 MeritMaxAFC(Space& home, MeritMaxAFC& m);
137 /// Return merit
138 double operator()(Int::IntView x, int i) const;
139 /// Return merit
140 double operator()(Int::BoolView x, int i) const;
141 /// Dispose
142 void dispose(void);
143 };
144
145 /// Select by maximal AFC over size
146 class MeritMaxAFCSize {
147 protected:
148 /// Integer AFC information
149 IntAFC iafc;
150 /// Boolean AFC information
151 BoolAFC bafc;
152 public:
153 /// Constructor for initialization
154 MeritMaxAFCSize(Space& home, const IntBoolVarBranch& ibvb);
155 /// Constructor for cloning
156 MeritMaxAFCSize(Space& home, MeritMaxAFCSize& m);
157 /// Return merit
158 double operator()(Int::IntView x, int i) const;
159 /// Return merit
160 double operator()(Int::BoolView x, int i) const;
161 /// Dispose
162 void dispose(void);
163 };
164
165 /// Select by maximal Action
166 class MeritMaxAction {
167 protected:
168 /// Integer Action information
169 IntAction iaction;
170 /// Boolean Action information
171 BoolAction baction;
172 public:
173 /// Constructor for initialization
174 MeritMaxAction(Space& home, const IntBoolVarBranch& ibvb);
175 /// Constructor for cloning
176 MeritMaxAction(Space& home, MeritMaxAction& m);
177 /// Return merit
178 double operator()(Int::IntView x, int i) const;
179 /// Return merit
180 double operator()(Int::BoolView x, int i) const;
181 /// Dispose
182 void dispose(void);
183 };
184
185 /// Select by maximal Action over size
186 class MeritMaxActionSize {
187 protected:
188 /// Integer Action information
189 IntAction iaction;
190 /// Boolean Action information
191 BoolAction baction;
192 public:
193 /// Constructor for initialization
194 MeritMaxActionSize(Space& home, const IntBoolVarBranch& ibvb);
195 /// Constructor for cloning
196 MeritMaxActionSize(Space& home, MeritMaxActionSize& m);
197 /// Return merit
198 double operator()(Int::IntView x, int i) const;
199 /// Return merit
200 double operator()(Int::BoolView x, int i) const;
201 /// Dispose
202 void dispose(void);
203 };
204
205 /// Select by maximal CHB
206 class MeritMaxCHB {
207 protected:
208 /// Integer CHB information
209 IntCHB ichb;
210 /// Boolean CHB information
211 BoolCHB bchb;
212 public:
213 /// Constructor for initialization
214 MeritMaxCHB(Space& home, const IntBoolVarBranch& ibvb);
215 /// Constructor for cloning
216 MeritMaxCHB(Space& home, MeritMaxCHB& m);
217 /// Return merit
218 double operator()(Int::IntView x, int i) const;
219 /// Return merit
220 double operator()(Int::BoolView x, int i) const;
221 /// Dispose
222 void dispose(void);
223 };
224
225 /// Select by maximal CHB over size
226 class MeritMaxCHBSize {
227 protected:
228 /// Integer CHB information
229 IntCHB ichb;
230 /// Boolean CHB information
231 BoolCHB bchb;
232 public:
233 /// Constructor for initialization
234 MeritMaxCHBSize(Space& home, const IntBoolVarBranch& ibvb);
235 /// Constructor for cloning
236 MeritMaxCHBSize(Space& home, MeritMaxCHBSize& m);
237 /// Return merit
238 double operator()(Int::IntView x, int i) const;
239 /// Return merit
240 double operator()(Int::BoolView x, int i) const;
241 /// Dispose
242 void dispose(void);
243 };
244
245 /// %Choice storing position and value
246 class GECODE_VTABLE_EXPORT PosIntChoice : public Choice {
247 private:
248 /// Position of view to assign
249 int _pos;
250 /// Value to assign to
251 int _val;
252 public:
253 /// Initialize choice for brancher \a b, number of alternatives \a a, position \a p, and value \a n
254 PosIntChoice(const Brancher& b, unsigned int a, int p, int n);
255 /// Return position of view to assign
256 int pos(void) const;
257 /// Return value to assign to
258 int val(void) const;
259 /// Archive into \a e
260 virtual void archive(Archive& e) const;
261 };
262
263 /// Base-class for brancher for integer and Boolean views
264 class IntBoolBrancherBase : public Brancher {
265 protected:
266 /// Integer views to branch on
267 ViewArray<Int::IntView> x;
268 /// Boolean views to branch on
269 ViewArray<Int::BoolView> y;
270 /// Unassigned views start here (might be in \a x or \a y)
271 mutable int start;
272 /// Integer value selection and commit object
273 ValSelCommitBase<Int::IntView,int>* xvsc;
274 /// Boolean value selection and commit object
275 ValSelCommitBase<Int::BoolView,int>* yvsc;
276 /// Constructor for cloning \a b
277 IntBoolBrancherBase(Space& home, IntBoolBrancherBase& b);
278 /// Constructor for creation
279 IntBoolBrancherBase(Home home,
280 ViewArray<Int::IntView> x, ViewArray<Int::BoolView> y,
281 ValSelCommitBase<Int::IntView,int>* xvsc,
282 ValSelCommitBase<Int::BoolView,int>* yvsc);
283 public:
284 /// Check status of brancher, return true if alternatives left
285 virtual bool status(const Space& home) const;
286 /// Return choice
287 virtual const Choice* choice(Space& home) = 0;
288 /// Return choice
289 virtual const Choice* choice(const Space& home, Archive& e);
290 /// Perform commit for choice \a c and alternative \a b
291 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
292 /// Create no-good literal for choice \a c and alternative \a b
293 virtual NGL* ngl(Space& home, const Choice& c, unsigned int b) const;
294 /// Print branch for choice \a c and alternative \a b
295 virtual void print(const Space& home, const Choice& c, unsigned int b,
296 std::ostream& o) const;
297 /// Delete brancher and return its size
298 virtual size_t dispose(Space& home);
299 };
300
301 /// Brancher for integer and Boolean views
302 template<class Merit>
303 class IntBoolBrancher : public IntBoolBrancherBase {
304 protected:
305 /// Selection by maximal merit
306 Merit merit;
307 /// Constructor for cloning \a b
308 IntBoolBrancher(Space& home, IntBoolBrancher& b);
309 /// Constructor for creation
310 IntBoolBrancher(Home home,
311 ViewArray<Int::IntView> x, ViewArray<Int::BoolView> y,
312 Merit& m,
313 ValSelCommitBase<Int::IntView,int>* xvsc,
314 ValSelCommitBase<Int::BoolView,int>* yvsc);
315 public:
316 /// Return choice
317 virtual const Choice* choice(Space& home);
318 /// Perform cloning
319 virtual Actor* copy(Space& home);
320 /// Post brancher
321 static void post(Home home,
322 ViewArray<Int::IntView> x, ViewArray<Int::BoolView> y,
323 Merit& m,
324 ValSelCommitBase<Int::IntView,int>* xvsc,
325 ValSelCommitBase<Int::BoolView,int>* yvsc);
326 /// Delete brancher and return its size
327 virtual size_t dispose(Space& home);
328 };
329
330 /// Map respective integer value selection to Boolean value selection
331 BoolValBranch i2b(const IntValBranch& ivb);
332
333 /// Branch function for integer and Boolean variables
334 GECODE_FLATZINC_EXPORT void
335 branch(Home home, const IntVarArgs& x, const BoolVarArgs& y,
336 IntBoolVarBranch vars, IntValBranch vals);
337
338}}
339
340#include <gecode/flatzinc/branch.hpp>
341
342#endif
343
344// STATISTICS: flatzinc-branch