this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <chris.mears@monash.edu>
5 *
6 * Copyright:
7 * Christopher Mears, 2012
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_INT_LDSB_HH
35#define GECODE_INT_LDSB_HH
36
37#include <gecode/int.hh>
38
39/**
40 * \namespace Gecode::Int::LDSB
41 * \brief Symmetry breaking for integer variables
42 */
43namespace Gecode { namespace Int { namespace LDSB {
44
45 /// A Literal is a pair of variable index and value.
46 class Literal {
47 public:
48 /// Constructor for an empty literal
49 Literal(void);
50 /// Constructor
51 Literal(int _var, int _val);
52
53 /// Variable index. The ViewArray that the index is meant
54 /// for is assumed to be known by context.
55 int _variable;
56 /// The value of the literal. For int and bool variables,
57 /// this is the value itself; for set variables, this is
58 /// one of the possible elements of the set.
59 int _value;
60
61 /// Less than. The ordering is the lexicographical order
62 /// on the (variable,value) pair.
63 bool operator <(const Literal &rhs) const;
64 };
65
66 /**
67 * \brief Find the location of an integer in a collection of
68 * sequences.
69 *
70 *
71 * Given an array \a indices of integers (of length \a n_values),
72 * which represents a collection of sequences each of size \a
73 * seq_size, find the location of the first occurrence of the value
74 * \a index. Returns a pair of sequence number and position within
75 * that sequence (both zero-based).
76 */
77 GECODE_INT_EXPORT
78 std::pair<int,int>
79 findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index);
80}}}
81
82namespace Gecode {
83 /// Traits of %ArgArray<VarImpBase*>
84 template<>
85 class ArrayTraits<ArgArray<VarImpBase*> > {
86 public:
87 typedef ArgArray<VarImpBase*> StorageType;
88 typedef VarImpBase* ValueType;
89 typedef ArgArray<VarImpBase*> ArgsType;
90 };
91
92 /// An array of literals
93 typedef ArgArray<Int::LDSB::Literal> LiteralArgs;
94 /// Traits of %LiteralArgs
95 template<>
96 class ArrayTraits<LiteralArgs> {
97 public:
98 typedef LiteralArgs StorageType;
99 typedef Int::LDSB::Literal ValueType;
100 typedef LiteralArgs ArgsType;
101 };
102}
103
104namespace Gecode { namespace Int { namespace LDSB {
105 /// Implementation of a symmetry at the modelling level
106 class GECODE_INT_EXPORT SymmetryObject {
107 public:
108 /// Number of references that point to this symmetry object.
109 int nrefs;
110 /// Default constructor
111 SymmetryObject(void);
112 /// Destructor
113 virtual ~SymmetryObject(void);
114 };
115 /// Implementation of a variable symmetry at the modelling level
116 class GECODE_INT_EXPORT VariableSymmetryObject : public SymmetryObject {
117 public:
118 /// Array of variables in symmetry
119 VarImpBase** xs;
120 /// Number of variables in symmetry
121 int nxs;
122 /// Constructor for creation
123 VariableSymmetryObject(ArgArray<VarImpBase*> vars);
124 /// Destructor
125 ~VariableSymmetryObject(void);
126 };
127 /// Implementation of a value symmetry at the modelling level
128 class GECODE_INT_EXPORT ValueSymmetryObject : public SymmetryObject {
129 public:
130 /// Set of symmetric values
131 IntSet values;
132 /// Constructor for creation
133 ValueSymmetryObject(IntSet vs);
134 };
135 /// Implementation of a variable sequence symmetry at the modelling level
136 class GECODE_INT_EXPORT VariableSequenceSymmetryObject : public SymmetryObject {
137 public:
138 /// Array of variables in symmetry
139 VarImpBase** xs;
140 /// Number of variables in symmetry
141 int nxs;
142 /// Size of each sequence in symmetry
143 int seq_size;
144 /// Constructor for creation
145 VariableSequenceSymmetryObject(ArgArray<VarImpBase*> vars, int ss);
146 /// Destructor
147 ~VariableSequenceSymmetryObject();
148 };
149 /// Implementation of a value sequence symmetry at the modelling level
150 class GECODE_INT_EXPORT ValueSequenceSymmetryObject : public SymmetryObject {
151 public:
152 /// Array of values in symmetry
153 IntArgs values;
154 /// Size of each sequence in symmetry
155 int seq_size;
156 /// Constructor for creation
157 ValueSequenceSymmetryObject(IntArgs vs, int ss);
158 };
159
160 /// Implementation of a single symmetry.
161 template<class View>
162 class SymmetryImp {
163 public:
164 /// Compute symmetric literals
165 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const = 0;
166 /// Left-branch update
167 virtual void update(Literal) = 0;
168 /// Copy function
169 virtual SymmetryImp<View>* copy(Space& home) const = 0;
170 /// Disposal
171 virtual size_t dispose(Space& home) = 0;
172 /// Unused destructor
173 virtual ~SymmetryImp(void);
174 /// Placement new operator
175 static void* operator new(size_t s, Space& home);
176 /// Return memory to space
177 static void operator delete(void*,Space&);
178 /// Needed for exceptions
179 static void operator delete(void*);
180 };
181 /// Implementation of a variable symmetry.
182 template <class View>
183 class VariableSymmetryImp : public SymmetryImp<View> {
184 protected:
185 /// Symmetric variable indices
186 Support::BitSetOffset<Space> indices;
187 public:
188 /// Constructor for creation
189 VariableSymmetryImp<View>(Space& home, int* vs, unsigned int n);
190 /// Copy constructor
191 VariableSymmetryImp<View>(Space& home, const VariableSymmetryImp<View>& other);
192 /// Disposal
193 virtual size_t dispose(Space& home);
194 /// Left-branch update
195 void update(Literal);
196 /// Compute symmetric literals
197 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
198 /// Copy function
199 SymmetryImp<View>* copy(Space& home) const;
200 };
201 /// Implementation of a value symmetry.
202 template <class View>
203 class ValueSymmetryImp : public SymmetryImp<View>
204 {
205 public:
206 /// Symmetric values
207 Support::BitSetOffset<Space> values;
208 /// Constructor for creation
209 ValueSymmetryImp<View>(Space& home, int* vs, unsigned int n);
210 /// Copy constructor
211 ValueSymmetryImp<View>(Space& home, const ValueSymmetryImp<View>& other);
212 /// Disposal
213 virtual size_t dispose(Space& home);
214 /// Left-branch update
215 void update(Literal);
216 /// Compute symmetric literals
217 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
218 /// Copy function
219 SymmetryImp<View>* copy(Space& home) const;
220 };
221 /// Implementation of a variable sequence symmetry.
222 template <class View>
223 class VariableSequenceSymmetryImp : public SymmetryImp<View>
224 {
225 protected:
226 /// Array of variable indices
227 unsigned int *indices;
228 /// Total number of indices (n_seqs * seq_size)
229 unsigned int n_indices;
230 /// Size of each sequence in symmetry
231 unsigned int seq_size;
232 /// Number of sequences in symmetry
233 unsigned int n_seqs;
234
235 /// Map from variable's index to its sequence and position.
236 // e.g. lookup[2] == 10 indicates that the variable with index 2
237 // occurs at position 10 in the "indices" array.
238 // If a variable occurs more than once, only the first occurrence
239 // is recorded.
240 // A value of -1 indicates that the variable does not occur in
241 // "indices".
242 int *lookup;
243 /// Size of lookup
244 unsigned int lookup_size;
245
246 /// Get the value in the specified sequence at the specified
247 /// position. (Both are zero-based.)
248 int getVal(unsigned int sequence, unsigned int position) const;
249 public:
250 /// Constructor for creation
251 VariableSequenceSymmetryImp<View>(Space& home, int *_indices, unsigned int n, unsigned int seqsize);
252 /// Copy constructor
253 VariableSequenceSymmetryImp<View>(Space& home, const VariableSequenceSymmetryImp<View>& s);
254 /// Disposal
255 virtual size_t dispose(Space& home);
256 /// Search left-branch update
257 void update(Literal);
258 /// Compute symmetric literals
259 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
260 /// Copy function
261 SymmetryImp<View>* copy(Space& home) const;
262 };
263 /// Implementation of a value sequence symmetry.
264 template <class View>
265 class ValueSequenceSymmetryImp : public SymmetryImp<View>
266 {
267 protected:
268 /// Set of sequences
269 int *values;
270 /// Total number of values (n_seqs * seq_size)
271 unsigned int n_values;
272 /// Size of each sequence in symmetry
273 unsigned int seq_size;
274 /// Number of sequences in symmetry
275 unsigned int n_seqs;
276 /// Which sequences are dead
277 Support::BitSet<Space> dead_sequences;
278 /// Get the value in the specified sequence at the specified
279 /// position. (Both are zero-based.)
280 int getVal(unsigned int sequence, unsigned int position) const;
281 private:
282 ValueSequenceSymmetryImp<View>(const ValueSequenceSymmetryImp<View>&);
283 public:
284 /// Constructor for creation
285 ValueSequenceSymmetryImp<View>(Space& home, int* _values, unsigned int n, unsigned int seqsize);
286 /// Copy constructor
287 ValueSequenceSymmetryImp<View>(Space& home, const ValueSequenceSymmetryImp<View>& vss);
288 /// Disposal
289 virtual size_t dispose(Space& home);
290 /// Left-branch update
291 void update(Literal);
292 /// Compute symmetric literals
293 virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
294 /// Copy function
295 SymmetryImp<View>* copy(Space& home) const;
296 };
297
298 /// %Choice storing position and value, and symmetric literals to be
299 /// excluded on the right branch.
300 template<class Val>
301 class GECODE_VTABLE_EXPORT LDSBChoice : public PosValChoice<Val> {
302 private:
303 /// Set of literals to be excluded
304 const Literal * const _literals;
305 /// Number of literals
306 const int _nliterals;
307 public:
308 /// Initialize choice for brancher \a b, position \a p, value \a
309 /// n, and set of literals \a literals (of size \a nliterals)
310 LDSBChoice(const Brancher& b, unsigned int a, const Pos& p, const Val& n,
311 const Literal* literals, int nliterals);
312 /// Destructor
313 ~LDSBChoice(void);
314 /// Return literals
315 const Literal* literals(void) const;
316 /// Return number of literals
317 int nliterals(void) const;
318 /// Archive into \a e
319 virtual void archive(Archive& e) const;
320 };
321
322 /**
323 * \brief Symmetry-breaking brancher with generic view and value
324 * selection
325 *
326 * Implements view-based branching for an array of views (of type
327 * \a View) and value (of type \a Val).
328 *
329 */
330 template<class View, int n, class Val, unsigned int a,
331 class Filter, class Print>
332 class LDSBBrancher : public ViewValBrancher<View,n,Val,a,Filter,Print> {
333 public:
334 using typename ViewValBrancher<View,n,Val,a,Filter,Print>::Var;
335 /// Array of symmetry implementations
336 SymmetryImp<View>** _syms;
337 /// Number of symmetry implementations
338 int _nsyms;
339 // Position of variable that last choice was created for
340 int _prevPos;
341 protected:
342 /// Constructor for cloning \a b
343 LDSBBrancher(Space& home, LDSBBrancher& b);
344 /// Constructor for creation
345 LDSBBrancher(Home home,
346 ViewArray<View>& x,
347 ViewSel<View>* vs[n],
348 ValSelCommitBase<View,Val>* vsc,
349 SymmetryImp<View>** syms, int nsyms,
350 BranchFilter<Var> bf,
351 VarValPrint<Var,Val> vvp);
352 public:
353 /// Return choice
354 virtual const Choice* choice(Space& home);
355 /// Return choice
356 virtual const Choice* choice(const Space& home, Archive& e);
357 /// Perform commit for choice \a c and alternative \a b
358 virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
359 /// Perform cloning
360 virtual Actor* copy(Space& home);
361 /// Delete brancher and return its size
362 virtual size_t dispose(Space& home);
363 /// Brancher post function
364 static void post(Home home,
365 ViewArray<View>& x,
366 ViewSel<View>* vs[n],
367 ValSelCommitBase<View,Val>* vsc,
368 SymmetryImp<View>** syms,
369 int nsyms,
370 BranchFilter<Var> bf,
371 VarValPrint<Var,Val> vvp);
372 };
373
374 /// Post LDSB brancher
375 template<class View, int n, class Val, unsigned int a>
376 void postldsbbrancher(Home home,
377 ViewArray<View>& x,
378 ViewSel<View>* vs[n],
379 ValSelCommitBase<View,Val>* vsc,
380 SymmetryImp<View>** syms, int nsyms,
381 BranchFilter<typename View::VarType> bf,
382 VarValPrint<typename View::VarType,Val> vvp);
383
384 /// Exclude value \v from variable view \x
385 template<class View>
386 ModEvent prune(Space& home, View x, int v);
387
388}}}
389
390#include <gecode/int/ldsb/brancher.hpp>
391#include <gecode/int/ldsb/sym-imp.hpp>
392
393#endif
394
395// STATISTICS: int-branch
396