this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 * Guido Tack <tack@gecode.org>
9 *
10 * Copyright:
11 * Patrick Pekczynski, 2004/2005
12 * Christian Schulte, 2009
13 * Guido Tack, 2009
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_GCC_HH
41#define GECODE_INT_GCC_HH
42
43#include <gecode/int.hh>
44
45/**
46 * \namespace Gecode::Int::GCC
47 * \brief Global cardinality propagators (Counting)
48 */
49
50#include <gecode/int/gcc/view.hpp>
51#include <gecode/int/gcc/bnd-sup.hpp>
52#include <gecode/int/gcc/dom-sup.hpp>
53
54namespace Gecode { namespace Int { namespace GCC {
55
56 /**
57 * \brief Value consistent global cardinality propagator
58 *
59 * Requires \code #include <gecode/int/gcc.hh> \endcode
60 * \ingroup FuncIntProp
61 */
62 template<class Card>
63 class Val : public Propagator {
64 protected:
65 /// Views on which to perform value-propagation
66 ViewArray<IntView> x;
67 /// Array containing either fixed cardinalities or CardViews
68 ViewArray<Card> k;
69 /// Constructor for posting
70 Val(Home home, ViewArray<IntView>& x, ViewArray<Card>& k);
71 /// Constructor for cloning \a p
72 Val(Space& home, Val<Card>& p);
73 public:
74 /// Copy propagator during cloning
75 virtual Actor* copy(Space& home);
76 /// Cost funtion returning high linear
77 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
78 /// Schedule function
79 virtual void reschedule(Space& home);
80 /// Perform propagation
81 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
82 /// Destructor
83 virtual size_t dispose(Space& home);
84 /// Post propagator for views \a x and cardinalities \a k
85 static ExecStatus post(Home home,
86 ViewArray<IntView>& x, ViewArray<Card>& k);
87 };
88
89 /**
90 * \brief Bounds consistent global cardinality propagator
91 *
92 * The algorithm is taken from:
93 * Claude-Guy Quimper, Peter van Beek, Alejandro López-Ortiz,
94 * Alexander Golynski, and Sayyed Bashir Sadjad. An Efficient
95 * Bounds Consistency Algorithm for the Global Cardinality
96 * Constraint, CP 2003, pages 600-614.
97 *
98 * This implementation uses the code that is provided
99 * by Peter Van Beek:
100 * http://ai.uwaterloo.ca/~vanbeek/software/software.html
101 * The code here has only been slightly modified to fit Gecode
102 * (taking idempotent/non-idempotent propagation into account)
103 * and uses a more efficient layout of datastructures (keeping the
104 * number of different arrays small).
105 *
106 * The Bnd class is used to post the propagator and BndImp
107 * is the actual implementation taking shared variables into account.
108 *
109 * Requires \code #include <gecode/int/gcc.hh> \endcode
110 * \ingroup FuncIntProp
111 */
112 template<class Card>
113 class Bnd : public Propagator {
114 protected:
115 /// Views on which to perform bounds-propagation
116 ViewArray<IntView> x;
117 /// Views on which to perform value-propagation (subset of \c x)
118 ViewArray<IntView> y;
119 /// Array containing either fixed cardinalities or CardViews
120 ViewArray<Card> k;
121 /**
122 * \brief Data structure storing the sum of the views lower bounds
123 * Necessary for reasoning about the interval capacities in the
124 * propagation algorithm.
125 */
126 PartialSum<Card> lps;
127 /// Data structure storing the sum of the views upper bounds
128 PartialSum<Card> ups;
129 /**
130 * \brief Stores whether cardinalities are all assigned
131 *
132 * If all cardinalities are assigned the propagation algorithm
133 * only has to perform propagation for the upper bounds.
134 */
135 bool card_fixed;
136 /**
137 * \brief Stores whether the minium required occurences of
138 * the cardinalities are all zero. If so, we do not need
139 * to perform lower bounds propagation.
140 */
141 bool skip_lbc;
142 /// Constructor for cloning \a p
143 Bnd(Space& home, Bnd<Card>& p);
144
145 /// Prune cardinality variables with 0 maximum occurrence
146 ExecStatus pruneCards(Space& home);
147
148 /**
149 * \brief Lower Bounds constraint (LBC) stating
150 * \f$ \forall j \in \{0, \dots, |k|-1\}:
151 * \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \geq min(k_j)\f$
152 * Hence the lbc constraints the variables such that every value occurs
153 * at least as often as specified by its lower cardinality bound.
154 * \param home current space
155 * \param nb denotes number of unique bounds
156 * \param hall contains information about the hall structure of the problem
157 * (cf. HallInfo)
158 * \param rank ranking information about the variable bounds (cf. Rank)
159 * \param mu permutation \f$ \mu \f$ such that
160 * \f$ \forall i\in \{0, \dots, |x|-2\}:
161 * max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})\f$
162 * \param nu permutation \f$ \nu \f$ such that
163 * \f$ \forall i\in \{0, \dots, |x|-2\}:
164 * min(x_{\mu(i)}) \leq min(x_{\mu(i+1)})\f$
165 */
166 ExecStatus lbc(Space& home, int& nb, HallInfo hall[], Rank rank[],
167 int mu[], int nu[]);
168
169 /**
170 * \brief Upper Bounds constraint (UBC) stating
171 * \f$ \forall j \in \{0, \dots, |k|-1\}:
172 * \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \leq max(k_j)\f$
173 * Hence the ubc constraints the variables such that no value occurs
174 * more often than specified by its upper cardinality bound.
175 * \param home current space
176 * \param nb denotes number of unique bounds
177 * \param hall contains information about the hall structure of the problem
178 * (cf. HallInfo)
179 * \param rank ranking information about the variable bounds (cf. Rank)
180 * \param mu permutation \f$ \mu \f$ such that
181 * \f$ \forall i\in \{0, \dots, |x|-2\}:
182 * max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})\f$
183 * \param nu permutation \f$ \nu \f$ such that
184 * \f$ \forall i\in \{0, \dots, |x|-2\}:
185 * min(x_{\mu(i)}) \leq min(x_{\mu(i+1)})\f$
186 */
187 ExecStatus ubc(Space& home, int& nb, HallInfo hall[], Rank rank[],
188 int mu[], int nu[]);
189 /// Constructor for posting
190 Bnd(Home home, ViewArray<IntView>&, ViewArray<Card>&, bool, bool);
191 public:
192 /// Copy propagator during cloning
193 virtual Actor* copy(Space& home);
194 /// Cost funtion
195 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
196 /// Schedule function
197 virtual void reschedule(Space& home);
198 /// Perform propagation
199 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
200 /// Destructor
201 virtual size_t dispose(Space& home);
202 /// Post propagator for views \a x and cardinalities \a k
203 static ExecStatus post(Home home,
204 ViewArray<IntView>& x, ViewArray<Card>& k);
205 };
206
207 /**
208 * \brief Domain consistent global cardinality propagator
209 *
210 * The algorithm is taken from:
211 * Claude-Guy Quimper, Peter van Beek, Alejandro López-Ortiz,
212 * and Alexander Golynski. Improved Algorithms for the
213 * Global Cardinality Constraint, CP 2004, pages 542-556.
214 *
215 * Requires \code #include <gecode/int/gcc.hh> \endcode
216 * \ingroup FuncIntProp
217 */
218 template<class Card>
219 class Dom : public Propagator {
220 protected:
221 /// Views on which to perform domain-propagation
222 ViewArray<IntView> x;
223 /**
224 * \brief Views used to channel information between \c x and \c k
225 * (\f$ x \subseteq y \f$).
226 */
227 ViewArray<IntView> y;
228 /// Array containing either fixed cardinalities or CardViews
229 ViewArray<Card> k;
230 /// Propagation is performed on a variable-value graph (used as cache)
231 VarValGraph<Card>* vvg;
232 /**
233 * \brief Stores whether cardinalities are all assigned
234 *
235 * If all cardinalities are assigned the propagation algorithm
236 * only has to perform propagation for the upper bounds.
237 */
238 bool card_fixed;
239 /// Constructor for cloning \a p
240 Dom(Space& home, Dom<Card>& p);
241 /// Constructor for posting
242 Dom(Home home, ViewArray<IntView>&, ViewArray<Card>&, bool);
243 public:
244 /// Copy propagator during cloning
245 virtual Actor* copy(Space& home);
246 /// Cost function
247 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
248 /// Schedule function
249 virtual void reschedule(Space& home);
250 /// Perform propagation
251 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
252 /// Destructor
253 virtual size_t dispose(Space& home);
254 /// Post propagator for views \a x and cardinalities \a k
255 static ExecStatus post(Home home,
256 ViewArray<IntView>& x, ViewArray<Card>& k);
257 };
258
259}}}
260
261#include <gecode/int/gcc/post.hpp>
262#include <gecode/int/gcc/val.hpp>
263#include <gecode/int/gcc/bnd.hpp>
264#include <gecode/int/gcc/dom.hpp>
265
266#endif
267
268
269// STATISTICS: int-prop
270