Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
weights.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 * Gabor Szokoli <szokoli@gecode.org>
7 *
8 * Copyright:
9 * Guido Tack, 2004
10 * Christian Schulte, 2004
11 * Gabor Szokoli, 2004
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/set.hh>
39#include <gecode/int.hh>
40
41namespace Gecode { namespace Set { namespace Int {
42
44 template<class I>
46 private:
48 int threshold;
50 I iter;
52 SharedArray<int> elements;
54 SharedArray<int> weights;
56 int index;
58 void next(void);
59 public:
61
62
63 OverweightValues(void);
65 OverweightValues(int t,
66 SharedArray<int>& elements0,
67 SharedArray<int>& weights0,
68 I& i);
70 void init(int t,
71 SharedArray<int>& elements0,
72 SharedArray<int>& weights0,
73 I& i);
75
77
78
79 bool operator ()(void) const;
81 void operator ++(void);
83
85
86 int val(void) const;
88 };
89
90 template<class I>
91 forceinline void
92 OverweightValues<I>::next(void) {
93 while (iter()) {
94 while (elements[index]<iter.val()) index++;
95 assert(elements[index]==iter.val());
96 if (weights[index] > threshold) {
97 return;
98 }
99 ++iter;
100 }
101 }
102
103 template<class I>
106
107 template<class I>
110 SharedArray<int>& elements0,
111 SharedArray<int>& weights0,
112 I& i) : threshold(t),
113 iter(i),
114 elements(elements0),
115 weights(weights0),
116 index(0) {
117 next();
118 }
119
120 template<class I>
121 forceinline void
123 SharedArray<int>& elements0,
124 SharedArray<int>& weights0,
125 I& i) {
126 threshold = t; iter = i;
127 elements = elements0; weights = weights0;
128 index = 0;
129 next();
130 }
131
132 template<class I>
133 forceinline bool
134 OverweightValues<I>::operator ()(void) const { return iter(); }
135
136 template<class I>
137 forceinline void
138 OverweightValues<I>::operator ++(void) { ++iter; next(); }
139
140 template<class I>
141 forceinline int
142 OverweightValues<I>::val(void) const { return elements[index]; }
143
144 template<class View>
147 const SharedArray<int>& elements0,
148 const SharedArray<int>& weights0,
150 : Propagator(home), elements(elements0), weights(weights0),
151 x(x0), y(y0) {
152 home.notice(*this,AP_DISPOSE);
153 x.subscribe(home,*this, PC_SET_ANY);
154 y.subscribe(home,*this, Gecode::Int::PC_INT_BND);
155 }
156
157 template<class View>
160 : Propagator(home,p), elements(p.elements), weights(p.weights) {
161 x.update(home,p.x);
162 y.update(home,p.y);
163 }
164
165 template<class View>
166 inline ExecStatus
170 if (elements.size() != weights.size())
171 throw ArgumentSizeMismatch("Weights");
172 Region r;
173 int* els_arr = r.alloc<int>(elements.size());
174 for (int i=elements.size(); i--;)
175 els_arr[i] = elements[i];
176 IntSet els(els_arr, elements.size());
177 IntSetRanges er(els);
178 GECODE_ME_CHECK(x.intersectI(home, er));
179 (void) new (home) Weights(home,elements,weights,x,y);
180 return ES_OK;
181 }
182
183 template<class View>
186 return PropCost::linear(PropCost::LO, y.size()+1);
187 }
188
189 template<class View>
190 void
192 x.reschedule(home,*this, PC_SET_ANY);
193 y.reschedule(home,*this, Gecode::Int::PC_INT_BND);
194 }
195
196 template<class View>
197 forceinline size_t
199 home.ignore(*this,AP_DISPOSE);
200 x.cancel(home,*this, PC_SET_ANY);
201 y.cancel(home,*this, Gecode::Int::PC_INT_BND);
202 elements.~SharedArray();
203 weights.~SharedArray();
204 (void) Propagator::dispose(home);
205 return sizeof(*this);
206 }
207
208 template<class View>
209 Actor*
211 return new (home) Weights(home,*this);
212 }
213
215 template<class I>
219 I& iter) {
220 int sum = 0;
221 int i = 0;
223 for (; v(); ++v) {
224 // Skip all elements below the current
225 while (elements[i]<v.val()) i++;
226 assert(elements[i] == v.val());
227 sum += weights[i];
228 }
229 assert(!v());
230 return sum;
231 }
232
233
235 class IntLess {
236 public:
237 bool operator ()(int x, int y);
238 };
239
240 forceinline bool
242 return x < y;
243 }
244
245 template<class View>
249
250 if (!x.assigned()) {
251 // Collect the weights of the elements in the unknown set in an array
252 int size = elements.size();
253 Region r;
254 int* minWeights = r.alloc<int>(size);
255 int* maxWeights = r.alloc<int>(size);
256
259 for (int i=0; i<size; i++) {
260 if (!urv() || elements[i]<urv.val()) {
261 minWeights[i] = INT_MAX;
262 maxWeights[i] = INT_MIN;
263 } else {
264 assert(elements[i] == urv.val());
265 minWeights[i] = weights[i];
266 maxWeights[i] = weights[i];
267 ++urv;
268 }
269 }
270
271 // Sort the weights of the unknown elements
272 IntLess il;
273 Support::quicksort<int>(minWeights, size, il);
274 Support::quicksort<int>(maxWeights, size, il);
275
276 // The maximum number of elements that can still be added to x
277 int delta = static_cast<int>(std::min(x.unknownSize(), x.cardMax() - x.glbSize()));
278
279 // The weight of the elements already in x
280 GlbRanges<View> glb(x);
281 int glbWeight = weightI<GlbRanges<View> >(elements, weights, glb);
282
283 // Compute the weight of the current lower bound of x, plus at most
284 // delta-1 further elements with smallest negative weights. This weight
285 // determines which elements in the upper bound cannot possibly be
286 // added to x (those whose weight would exceed the capacity even if
287 // all other elements are minimal)
288 int lowWeight = glbWeight;
289 for (int i=0; i<delta-1; i++) {
290 if (minWeights[i] >= 0)
291 break;
292 lowWeight+=minWeights[i];
293 }
294
295 // Compute the lowest possible weight of x. If there is another element
296 // with negative weight left, then add its weight to lowWeight.
297 // Otherwise lowWeight is already the lowest possible weight.
298 int lowestWeight = lowWeight;
299 if (delta>0 && minWeights[delta-1]<0)
300 lowestWeight+=minWeights[delta-1];
301
302 // If after including the minimal number of required elements,
303 // no more element with negative weight is available, then
304 // a tighter lower bound can be computed.
305 if ( (x.cardMin() - x.glbSize() > 0 &&
306 minWeights[x.cardMin() - x.glbSize() - 1] >= 0) ||
307 minWeights[0] >= 0 ) {
308 int lowestPosWeight = glbWeight;
309 for (unsigned int i=0; i<x.cardMin() - x.glbSize(); i++) {
310 lowestPosWeight += minWeights[i];
311 }
312 lowestWeight = std::max(lowestWeight, lowestPosWeight);
313 }
314
315 // Compute the highest possible weight of x as the weight of the lower
316 // bound plus the weight of the delta heaviest elements still in the
317 // upper bound.
318 int highestWeight = glbWeight;
319 for (int i=0; i<delta; i++) {
320 if (maxWeights[size-i-1]<=0)
321 break;
322 highestWeight += maxWeights[size-i-1];
323 }
324
325 // Prune the weight using the computed bounds
326 GECODE_ME_CHECK(y.gq(home, lowestWeight));
327 GECODE_ME_CHECK(y.lq(home, highestWeight));
328
329 // Exclude all elements that are too heavy from the set x.
330 // Elements are too heavy if their weight alone already
331 // exceeds the remaining capacity
332 int remainingCapacity = y.max()-lowWeight;
333
337 ov(remainingCapacity, elements, weights, urv2);
340 me = x.excludeI(home, ovr);
341 GECODE_ME_CHECK(me);
342 }
343 if (x.assigned()) {
344 // If x is assigned, just compute its weight and assign y.
345 GlbRanges<View> glb(x);
346 int w =
348 GECODE_ME_CHECK(y.eq(home, w));
349 return home.ES_SUBSUMED(*this);
350 }
351
352 // return me_modified(me) ? ES_NOFIX : ES_FIX;
353 return ES_NOFIX;
354 }
355
356}}}
357
358// STATISTICS: set-prop
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3256
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3223
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
Exception: Arguments are of different size
Definition exception.hpp:73
Integer view for integer variables.
Definition view.hpp:129
Value iterator from range iterator.
int val(void) const
Return current value.
Range iterator from value iterator.
Propagation cost.
Definition core.hpp:486
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4803
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1079
friend class Space
Definition core.hpp:1068
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3505
Handle to region.
Definition region.hpp:55
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Sort order for integers.
Definition weights.hpp:235
bool operator()(int x, int y)
Definition weights.hpp:241
Value Iterator for values above a certain weight.
Definition weights.hpp:45
void operator++(void)
Move iterator to next value (if possible)
Definition weights.hpp:138
void init(int t, SharedArray< int > &elements0, SharedArray< int > &weights0, I &i)
Initialize with elements/weights pairs, threshold t and iterator i.
Definition weights.hpp:122
bool operator()(void) const
Test whether iterator is still at a value or done.
Definition weights.hpp:134
int val(void) const
Return current value.
Definition weights.hpp:142
OverweightValues(void)
Default constructor.
Definition weights.hpp:105
Gecode::Int::IntView y
The integer view.
Definition int.hh:267
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition weights.hpp:247
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition weights.hpp:210
SharedArray< int > weights
Weights for the elements in the upper bound.
Definition int.hh:262
View x
The set view.
Definition int.hh:265
Weights(Space &home, Weights &p)
Constructor for cloning p.
Definition weights.hpp:159
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as PC_LINEAR_LO)
Definition weights.hpp:185
static ExecStatus post(Home home, const SharedArray< int > &elements, const SharedArray< int > &weights, View x, Gecode::Int::IntView y)
Post propagator for .
Definition weights.hpp:167
SharedArray< int > elements
List of elements in the upper bound.
Definition int.hh:260
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition weights.hpp:198
virtual void reschedule(Space &home)
Schedule function.
Definition weights.hpp:191
Range iterator for the unknown set.
Definition var-imp.hpp:402
Shared array with arbitrary number of elements.
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4081
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Propagators connecting set and int variables.
Definition int.cpp:105
int weightI(SharedArray< int > &elements, SharedArray< int > &weights, I &iter)
Compute the weight of the elements in the iterator I.
Definition weights.hpp:217
Finite integer sets.
Definition var-imp.hpp:137
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition var-type.hpp:140
const Gecode::PropCond PC_SET_ANY
Propagate when any bound or the cardinality of a view changes.
Definition var-type.hpp:248
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Definition int.cpp:292
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:880
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:194