Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
propagate.cpp
Go to the documentation of this file.
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, 2010
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
35
36namespace Gecode { namespace Int { namespace BinPacking {
37
38 /*
39 * Packing propagator
40 *
41 */
42
43 PropCost
44 Pack::cost(const Space&, const ModEventDelta&) const {
45 return PropCost::quadratic(PropCost::HI,bs.size());
46 }
47
48 void
50 l.reschedule(home,*this,PC_INT_BND);
51 bs.reschedule(home,*this,PC_INT_DOM);
52 }
53
54 Actor*
56 return new (home) Pack(home,*this);
57 }
58
60 class TellCache {
61 protected:
63 int* _nq;
65 int _n_nq;
67 int _eq;
68 public:
70 TellCache(Region& region, int m);
72 void nq(int j);
74 void eq(int j);
77 };
78
81 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
82 forceinline void
84 _nq[_n_nq++] = j;
85 }
86 forceinline void
88 // For eq: -1 mean not yet assigned, -2 means failure, positive means value
89 if (_eq == -1)
90 _eq = j;
91 else
92 _eq = -2;
93 }
96 if (_eq == -2) {
97 return ES_FAILED;
98 } else if (_eq >= 0) {
99 GECODE_ME_CHECK(x.eq(home,_eq));
100 }
102 GECODE_ME_CHECK(x.minus_v(home, nqi));
103 _n_nq=0; _eq=-1;
104 return ES_OK;
105 }
106
107
108 /*
109 * Propagation proper
110 *
111 */
114 // Number of items
115 int n = bs.size();
116 // Number of bins
117 int m = l.size();
118
119 Region region;
120 {
121
122 // Possible sizes for bins
123 int* s = region.alloc<int>(m);
124
125 for (int j=0; j<m; j++)
126 s[j] = 0;
127
128 // Compute sizes for bins
129 if (OffsetView::me(med) == ME_INT_VAL) {
130 // Also eliminate assigned items
131 int k=0;
132 for (int i=0; i<n; i++)
133 if (bs[i].assigned()) {
134 int j = bs[i].bin().val();
135 l[j].offset(l[j].offset() - bs[i].size());
136 t -= bs[i].size();
137 } else {
138 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
139 s[j.val()] += bs[i].size();
140 bs[k++] = bs[i];
141 }
142 n=k; bs.size(n);
143 } else {
144 for (int i=0; i<n; i++) {
145 assert(!bs[i].assigned());
146 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
147 s[j.val()] += bs[i].size();
148 }
149 }
150
151 // Propagate bin loads and compute lower and upper bound
152 int min = t, max = t;
153 for (int j=0; j<m; j++) {
154 GECODE_ME_CHECK(l[j].gq(home,0));
155 GECODE_ME_CHECK(l[j].lq(home,s[j]));
156 min -= l[j].max(); max -= l[j].min();
157 }
158
159 // Propagate that load must be equal to total size
160 for (bool mod = true; mod; ) {
161 mod = false; ModEvent me;
162 for (int j=0; j<m; j++) {
163 int lj_min = l[j].min();
164 me = l[j].gq(home, min + l[j].max());
165 if (me_failed(me))
166 return ES_FAILED;
167 if (me_modified(me)) {
168 max += lj_min - l[j].min(); mod = true;
169 }
170 int lj_max = l[j].max();
171 me = l[j].lq(home, max + l[j].min());
172 if (me_failed(me))
173 return ES_FAILED;
174 if (me_modified(me)) {
175 min += lj_max - l[j].max(); mod = true;
176 }
177 }
178 }
179
180 if (n == 0) {
181 assert(l.assigned());
182 return home.ES_SUBSUMED(*this);
183 }
184
185
186 {
187 TellCache tc(region,m);
188
189 int k=0;
190 for (int i=0; i<n; i++) {
191 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
192 if (bs[i].size() > l[j.val()].max())
193 tc.nq(j.val());
194 if (s[j.val()] - bs[i].size() < l[j.val()].min())
195 tc.eq(j.val());
196 }
197 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
198 // Eliminate assigned bin
199 if (bs[i].assigned()) {
200 int j = bs[i].bin().val();
201 l[j].offset(l[j].offset() - bs[i].size());
202 t -= bs[i].size();
203 } else {
204 bs[k++] = bs[i];
205 }
206 }
207 n=k; bs.size(n);
208 }
209 region.free();
210 }
211
212 // Only if the propagator is at fixpoint here, continue with the more
213 // expensive stage for propagation.
215 return ES_NOFIX;
216
217 // Now the invariant holds that no more assigned bins exist!
218 {
219
220 // Size of items
221 SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
222
223 for (int j=0; j<m; j++)
224 s[j] = SizeSetMinusOne(region,n);
225
226 // Set up size information
227 for (int i=0; i<n; i++) {
228 assert(!bs[i].assigned());
229 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
230 s[j.val()].add(bs[i].size());
231 }
232
233 for (int j=0; j<m; j++) {
234 // Can items still be packed into bin?
235 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
236 return ES_FAILED;
237 int ap, bp;
238 // Must there be packed more items into bin?
239 if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(),
240 ap, bp))
241 GECODE_ME_CHECK(l[j].gq(home,bp));
242 // Must there be packed less items into bin?
243 if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(),
244 ap, bp))
245 GECODE_ME_CHECK(l[j].lq(home,ap));
246 }
247
248 TellCache tc(region,m);
249
250 int k=0;
251 for (int i=0; i<n; i++) {
252 assert(!bs[i].assigned());
253 for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
254 // Items must be removed in decreasing size!
255 s[j.val()].minus(bs[i].size());
256 // Can item i still be packed into bin j?
257 if (nosum(s[j.val()],
258 l[j.val()].min() - bs[i].size(),
259 l[j.val()].max() - bs[i].size()))
260 tc.nq(j.val());
261 // Must item i be packed into bin j?
262 if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max()))
263 tc.eq(j.val());
264 }
265 GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
266 if (bs[i].assigned()) {
267 int j = bs[i].bin().val();
268 l[j].offset(l[j].offset() - bs[i].size());
269 t -= bs[i].size();
270 } else {
271 bs[k++] = bs[i];
272 }
273 }
274 n=k; bs.size(n);
275 region.free();
276 }
277
278 // Perform lower bound checking
279 if (n > 0) {
280
281 // Find capacity estimate (we start from bs[0] as it might be
282 // not packable, actually (will be detected later anyway)!
283 int c = bs[0].size();
284 for (int j=0; j<m; j++)
285 c = std::max(c,l[j].max());
286
287 // Count how many items have a certain size (bucket sort)
288 int* n_s = region.alloc<int>(c+1);
289
290 for (int i=0; i<c+1; i++)
291 n_s[i] = 0;
292
293 // Count unpacked items
294 for (int i=0; i<n; i++)
295 n_s[bs[i].size()]++;
296
297 // Number of items and remaining bin load
298 int nm = n;
299
300 // Only count positive remaining bin loads
301 for (int j=0; j<m; j++)
302 if (l[j].max() < 0) {
303 return ES_FAILED;
304 } else if (c > l[j].max()) {
305 n_s[c - l[j].max()]++; nm++;
306 }
307
308 // Sizes of items and remaining bin loads
309 int* s = region.alloc<int>(nm);
310
311 // Setup sorted sizes
312 {
313 int k=0;
314 for (int i=c+1; i--; )
315 for (int j=n_s[i]; j--; )
316 s[k++]=i;
317 assert(k == nm);
318 }
319
320 // Items in N1 are from 0 ... n1 - 1
321 int n1 = 0;
322 // Items in N2 are from n1 ... n12 - 1, we count elements in N1 and N2
323 int n12 = 0;
324 // Items in N3 are from n12 ... n3 - 1
325 int n3 = 0;
326 // Free space in N2
327 int f2 = 0;
328 // Total size of items in N3
329 int s3 = 0;
330
331 // Initialize n12 and f2
332 for (; (n12 < nm) && (s[n12] > c/2); n12++)
333 f2 += c - s[n12];
334
335 // Initialize n3 and s3
336 for (n3 = n12; n3 < nm; n3++)
337 s3 += s[n3];
338
339 // Compute lower bounds
340 for (int k=0; k<=c/2; k++) {
341 // Make N1 larger by adding elements and N2 smaller
342 for (; (n1 < nm) && (s[n1] > c-k); n1++)
343 f2 -= c - s[n1];
344 assert(n1 <= n12);
345 // Make N3 smaller by removing elements
346 for (; (s[n3-1] < k) && (n3 > n12); n3--)
347 s3 -= s[n3-1];
348 // Overspill
349 int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0;
350 if (n12 + o > m)
351 return ES_FAILED;
352 }
353 region.free();
354 }
355
356 return ES_NOFIX;
357 }
358
361 // Sort according to size
362 Support::quicksort(&bs[0], bs.size());
363 // Total size of items
364 int s = 0;
365 // Constrain bins
366 for (int i=0; i<bs.size(); i++) {
367 s += bs[i].size();
368 GECODE_ME_CHECK(bs[i].bin().gq(home,0));
369 GECODE_ME_CHECK(bs[i].bin().le(home,l.size()));
370 }
371 // Eliminate zero sized items (which are at the end as the size are sorted)
372 {
373 int n = bs.size();
374 while ((n > 0) && (bs[n-1].size() == 0))
375 n--;
376 bs.size(n);
377 }
378 if (bs.size() == 0) {
379 // No items to be packed
380 for (int i=0; i<l.size(); i++)
381 GECODE_ME_CHECK(l[i].eq(home,0));
382 return ES_OK;
383 } else if (l.size() == 0) {
384 // No bins available
385 return ES_FAILED;
386 } else {
387 // Constrain load
388 for (int j=0; j<l.size(); j++) {
389 GECODE_ME_CHECK(l[j].gq(home,0));
390 GECODE_ME_CHECK(l[j].lq(home,s));
391 }
392 (void) new (home) Pack(home,l,bs);
393 return ES_OK;
394 }
395 }
396
397}}}
398
399// STATISTICS: int-prop
400
NNF * l
Left subtree.
int n
Number of negative literals for node type.
Example: Bin packing
Base-class for both propagators and branchers.
Definition core.hpp:628
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:639
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
ViewArray< OffsetView > l
Views for load of bins.
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
ViewArray< Item > bs
Items with bin and size.
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
int t
Total size of all items.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition propagate.cpp:55
bool nosum(const SizeSet &s, int a, int b, int &ap, int &bp)
Detect non-existence of sums in a .. b.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition propagate.cpp:44
virtual void reschedule(Space &home)
Schedule function.
Definition propagate.cpp:49
Size sets with one element discarded.
void minus(int s)
Discard size s.
void add(int s)
Add new size s.
Definition propagate.hpp:97
Record tell information.
Definition propagate.cpp:60
int * _nq
Values (sorted) to be pruned from view.
Definition propagate.cpp:63
int _n_nq
Number of values to be pruned.
Definition propagate.cpp:65
TellCache(Region &region, int m)
Initialize cache for at most m values.
Definition propagate.cpp:80
ExecStatus tell(Space &home, IntView x)
Perform tell to view x and reset cache.
Definition propagate.cpp:95
void eq(int j)
Record that view must be equal to j, return false if not possible.
Definition propagate.cpp:87
int _eq
Value to which view should be assigned.
Definition propagate.cpp:67
void nq(int j)
Record that view must be different from j.
Definition propagate.cpp:83
Integer view for integer variables.
Definition view.hpp:129
Value iterator for integer views.
Definition view.hpp:94
Value iterator for array of integers
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
@ HI
Expensive.
Definition core.hpp:514
size_t size
The size of the propagator (used during subsumption)
Definition core.hpp:1077
ModEventDelta modeventdelta(void) const
Return the modification event delta.
Definition core.hpp:3520
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
Handle to region.
Definition region.hpp:55
void free(void)
Free allocate memory.
Definition region.hpp:356
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
View arrays.
Definition array.hpp:253
int offset(void) const
Integer-precision integer scale view.
Definition view.hpp:642
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
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
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition var-type.hpp:54
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl=IPL_DEF)
Post propagator for .
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:187