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 * Guido Tack <tack@gecode.org>
6 *
7 * Contributing authors:
8 * Gabor Szokoli <szokoli@gecode.org>
9 *
10 * Copyright:
11 * Christian Schulte, 2002
12 * Guido Tack, 2004
13 * Gabor Szokoli, 2003
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#ifndef GECODE_INT_DISTINCT_HH
41#define GECODE_INT_DISTINCT_HH
42
43#include <gecode/int.hh>
44
45#include <gecode/int/view-val-graph.hh>
46#include <gecode/int/rel.hh>
47
48/**
49 * \namespace Gecode::Int::Distinct
50 * \brief %Distinct propagators
51 */
52
53namespace Gecode { namespace Int { namespace Distinct {
54
55 /**
56 * \brief Naive value distinct propagator
57 *
58 * Eliminates values of assigned views of type \a View.
59 *
60 * Requires \code #include <gecode/int/distinct.hh> \endcode
61 * \ingroup FuncIntProp
62 */
63 template<class View>
64 class Val : public NaryPropagator<View,PC_INT_VAL> {
65 protected:
66 using NaryPropagator<View,PC_INT_VAL>::x;
67
68 /// Constructor for posting
69 Val(Home home, ViewArray<View>& x);
70 /// Constructor for cloning \a p
71 Val(Space& home, Val<View>& p);
72 public:
73#ifdef GECODE_HAS_CBS
74 /// Solution distribution computation for branching
75 virtual void solndistrib(Space& home, Propagator::SendMarginal send) const;
76 /// Sum of variables cardinalities
77 virtual void domainsizesum(Propagator::InDecision in,
78 unsigned int& size, unsigned int& size_b) const;
79#endif
80 /// Copy propagator during cloning
81 virtual Actor* copy(Space& home);
82 /// Perform propagation
83 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
84 /// Post propagator for view array \a x
85 static ExecStatus post(Home home, ViewArray<View>& x);
86 };
87
88#ifdef GECODE_HAS_CBS
89 /**
90 * \brief Solution distribution computation for the AllDifferent constraint
91 *
92 * The algorithm is taken from:
93 * Gagnon, Samuel & Pesant, Gilles. (2018).
94 * Accelerating Counting-Based Search.
95 * In book: Integration of Constraint Programming,
96 * Artificial Intelligence, and Operations Research, pp.245-253
97 * Available at http://www.polymtl.ca/labo-quosseca/en/publications
98 */
99 template<class View>
100 void cbsdistinct(Space& home, unsigned int prop_id, const ViewArray<View>& x,
101 Propagator::SendMarginal send);
102
103 template<class View>
104 void cbssize(const ViewArray<View>& x, Propagator::InDecision in,
105 unsigned int& size, unsigned int& size_b);
106#endif
107
108 /**
109 * \brief Eliminate singletons by naive value propagation
110 *
111 * This is actually the propagation algorithm for Distinct::Val.
112 * It is available as separate function as it is reused for
113 * both bounds consistent and domain consistent distinct
114 * propagators.
115 *
116 * If \a complete is true, computes fixpoint, otherwise might not
117 * compute fixpoint. This can be helpful when used together with
118 * bounds or domain propagation to protect from pathological cases
119 * which can be handled more efficiently with bounds propagation.
120 */
121 template<class View, bool complete>
122 ExecStatus prop_val(Space& home, ViewArray<View>&);
123
124
125
126 /**
127 * \brief Bounds consistent distinct propagator
128 *
129 * The propagator uses staging: first it uses naive value-based
130 * propagation and only then uses bounds consistent propagation.
131 * Due to using naive value-based propagation, the propagator
132 * might actually achieve stronger consistency than just
133 * bounds consistency.
134 *
135 * The algorithm is taken from:
136 * A. Lopez-Ortiz, C.-G. Quimper, J. Tromp, and P. van Beek.
137 * A fast and simple algorithm for bounds consistency of the
138 * alldifferent constraint. IJCAI-2003.
139 *
140 * This implementation uses the code that is provided by
141 * Peter Van Beek:
142 * http://ai.uwaterloo.ca/~vanbeek/software/software.html
143 * The code (originally by John Tromp) here has only been slightly modified
144 * to fit %Gecode (taking idempotent/non-idempotent propagation into account)
145 * and uses a more efficient layout of datastructures (keeping the number
146 * of different arrays small).
147 *
148 * Requires \code #include <gecode/int/distinct.hh> \endcode
149 * \ingroup FuncIntProp
150 */
151 template<class View>
152 class Bnd : public Propagator {
153 protected:
154 /// Views on which to perform bounds-propagation
155 ViewArray<View> x;
156 /// Views on which to perform value-propagation (subset of \c x)
157 ViewArray<View> y;
158 /// Minimum (approximation) of view in \a x
159 int min_x;
160 /// Maximum (approximation) of view in \a x
161 int max_x;
162 /// Constructor for posting
163 Bnd(Home home, ViewArray<View>& x);
164 /// Constructor for cloning \a p
165 Bnd(Space& home, Bnd<View>& p);
166 public:
167#ifdef GECODE_HAS_CBS
168 /// Solution distribution computation for branching
169 virtual void solndistrib(Space& home, Propagator::SendMarginal send) const;
170 /// Sum of variables cardinalities
171 virtual void domainsizesum(Propagator::InDecision in,
172 unsigned int& size, unsigned int& size_b) const;
173#endif
174 /// Post propagator for view array \a x
175 static ExecStatus post(Home home, ViewArray<View>& x);
176 /// Perform propagation
177 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
178 /**
179 * \brief Cost function
180 *
181 * If in stage for naive value propagation, the cost is
182 * low linear. Otherwise it is low quadratic.
183 */
184 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
185 /// Schedule function
186 virtual void reschedule(Space& home);
187 /// Copy propagator during cloning
188 virtual Actor* copy(Space& home);
189 /// Destructor
190 virtual size_t dispose(Space& home);
191 };
192
193 /**
194 * \brief Perform bounds consistent distinct propagation
195 *
196 * This is actually the propagation algorithm for Distinct::Bnd.
197 * It is available as separate function as it is reused for
198 * both bounds consistent and domain consistent distinct
199 * propagators.
200 */
201 template<class View>
202 ExecStatus prop_bnd(Space& home, ViewArray<View>& x, int& min_x, int& max_x);
203
204 /**
205 * \brief Perform bounds consistent distinct propagation
206 *
207 * This is actually the propagation algorithm for Distinct::Bnd.
208 * It is available as separate function as it is reused for
209 * both bounds consistent and domain consistent distinct
210 * propagators.
211 */
212 template<class View>
213 ExecStatus prop_bnd(Space& home, ViewArray<View>& x);
214
215
216 /// View-value graph for propagation
217 template<class View>
218 class Graph : public ViewValGraph::Graph<View> {
219 public:
220 using ViewValGraph::Graph<View>::view;
221 using ViewValGraph::Graph<View>::n_view;
222 using ViewValGraph::Graph<View>::val;
223 using ViewValGraph::Graph<View>::n_val;
224 using ViewValGraph::Graph<View>::count;
225 using ViewValGraph::Graph<View>::scc;
226 using ViewValGraph::Graph<View>::match;
227 /// Construct graph as not yet initialized
228 Graph(void);
229 /// Initialize graph
230 ExecStatus init(Space& home, ViewArray<View>& x);
231 /// Mark edges in graph, return true if pruning is at all possible
232 bool mark(void);
233 /// Prune unmarked edges, \a assigned is true if a view got assigned
234 ExecStatus prune(Space& home, bool& assigned);
235 /// Synchronize graph with new view domains
236 bool sync(void);
237 };
238
239 /**
240 * \brief Propagation controller for domain consistent distinct
241 *
242 * The propagation controller provides convenient access to
243 * performing incremental domain consistent distinct propagation
244 * so that the routines can be reused easily.
245 *
246 * Requires \code #include <gecode/int/distinct.hh> \endcode
247 * \ingroup FuncIntProp
248 */
249 template<class View>
250 class DomCtrl {
251 protected:
252 /// Propagation is performed on a view-value graph
253 Graph<View> g;
254 public:
255 /// Initialize with non-initialized view-value graph
256 DomCtrl(void);
257 /// Check whether a view-value graph is available
258 bool available(void);
259 /// Initialize view-value graph for views \a x
260 ExecStatus init(Space& home, ViewArray<View>& x);
261 /// Synchronize available view-value graph
262 ExecStatus sync(void);
263 /// Perform propagation, \a assigned is true if a view gets assigned
264 ExecStatus propagate(Space& home, bool& assigned);
265 };
266
267 /**
268 * \brief Domain consistent distinct propagator
269 *
270 * The propagator uses staging: first it uses naive value-based
271 * propagation and only then uses domain consistent propagation.
272 *
273 * The algorithm is taken from:
274 * Jean-Charles Régin, A filtering algorithm for constraints
275 * of difference in CSPs, Proceedings of the Twelfth National
276 * Conference on Artificial Intelligence, pages 362--367.
277 * Seattle, WA, USA, 1994.
278 *
279 * Requires \code #include <gecode/int/distinct.hh> \endcode
280 * \ingroup FuncIntProp
281 */
282 template<class View>
283 class Dom : public NaryPropagator<View,PC_INT_DOM> {
284 protected:
285 using NaryPropagator<View,PC_INT_DOM>::x;
286 /// Propagation controller
287 DomCtrl<View> dc;
288 /// Constructor for cloning \a p
289 Dom(Space& home, Dom<View>& p);
290 /// Constructor for posting
291 Dom(Home home, ViewArray<View>& x);
292 public:
293#ifdef GECODE_HAS_CBS
294 /// Solution distribution computation for branching
295 virtual void solndistrib(Space& home, Propagator::SendMarginal send) const;
296 /// Sum of variables cardinalities
297 virtual void domainsizesum(Propagator::InDecision in,
298 unsigned int& size, unsigned int& size_b) const;
299#endif
300 /// Perform propagation
301 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
302 /**
303 * \brief Cost function
304 *
305 * If in stage for naive value propagation, the cost is
306 * low linear. Otherwise it is high quadratic.
307 */
308 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
309 /// Copy propagator during cloning
310 virtual Actor* copy(Space& home);
311 /// Post propagator for views \a x
312 static ExecStatus post(Home home, ViewArray<View>& x);
313 };
314
315 /**
316 * \brief Ternary domain consistent distinct propagator
317 *
318 * Requires \code #include <gecode/int/distinct.hh> \endcode
319 * \ingroup FuncIntProp
320 */
321 template<class View>
322 class TerDom : public TernaryPropagator<View,PC_INT_DOM> {
323 protected:
324 using TernaryPropagator<View,PC_INT_DOM>::x0;
325 using TernaryPropagator<View,PC_INT_DOM>::x1;
326 using TernaryPropagator<View,PC_INT_DOM>::x2;
327
328 /// Constructor for cloning \a p
329 TerDom(Space& home, TerDom<View>& p);
330 /// Constructor for posting
331 TerDom(Home home, View x0, View x1, View x2);
332 public:
333 /// Perform propagation
334 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
335 /// Copy propagator during cloning
336 virtual Actor* copy(Space& home);
337 /// Post propagator for views \a x
338 static ExecStatus post(Home home, View x0, View x1, View x2);
339 };
340
341 /**
342 * \brief Equal-if-then-else domain-consistent propagator
343 *
344 * Implements the propagator \f$x_1=(x_0 = c_0) ? c_1 : x_0\f$.
345 *
346 * Requires \code #include <gecode/int/distinct.hh> \endcode
347 * \ingroup FuncIntProp
348 */
349 class EqIte : public BinaryPropagator<IntView,PC_INT_DOM> {
350 protected:
351 using BinaryPropagator<IntView,PC_INT_DOM>::x0;
352 using BinaryPropagator<IntView,PC_INT_DOM>::x1;
353 /// The integer constant
354 int c0, c1;
355 /// Constructor for cloning \a p
356 EqIte(Space& home, EqIte& p);
357 /// Constructor for creation
358 EqIte(Home home, IntView x0, IntView x1, int c0, int c1);
359 public:
360 /// Copy propagator during cloning
361 GECODE_INT_EXPORT
362 virtual Actor* copy(Space& home);
363 /// Cost function (defined as high ternary)
364 GECODE_INT_EXPORT
365 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
366 /// Perform propagation
367 GECODE_INT_EXPORT
368 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
369 /// Post if-then-else propagator
370 static ExecStatus post(Home home, IntView x0, IntView x1, int c0, int c1);
371 };
372
373}}}
374
375#include <gecode/int/distinct/cbs.hpp>
376#include <gecode/int/distinct/val.hpp>
377#include <gecode/int/distinct/bnd.hpp>
378#include <gecode/int/distinct/ter-dom.hpp>
379#include <gecode/int/distinct/graph.hpp>
380#include <gecode/int/distinct/dom-ctrl.hpp>
381#include <gecode/int/distinct/dom.hpp>
382#include <gecode/int/distinct/eqite.hpp>
383
384#endif
385
386// STATISTICS: int-prop
387