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 *
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
34#include <gecode/int/bin-packing.hh>
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
49 Pack::reschedule(Space& home) {
50 l.reschedule(home,*this,PC_INT_BND);
51 bs.reschedule(home,*this,PC_INT_DOM);
52 }
53
54 Actor*
55 Pack::copy(Space& home) {
56 return new (home) Pack(home,*this);
57 }
58
59 /// Record tell information
60 class TellCache {
61 protected:
62 /// Values (sorted) to be pruned from view
63 int* _nq;
64 /// Number of values to be pruned
65 int _n_nq;
66 /// Value to which view should be assigned
67 int _eq;
68 public:
69 /// Initialize cache for at most \a m values
70 TellCache(Region& region, int m);
71 /// Record that view must be different from \a j
72 void nq(int j);
73 /// Record that view must be equal to \a j, return false if not possible
74 void eq(int j);
75 /// Perform tell to view \a x and reset cache
76 ExecStatus tell(Space& home, IntView x);
77 };
78
79 forceinline
80 TellCache::TellCache(Region& region, int m)
81 : _nq(region.alloc<int>(m)), _n_nq(0), _eq(-1) {}
82 forceinline void
83 TellCache::nq(int j) {
84 _nq[_n_nq++] = j;
85 }
86 forceinline void
87 TellCache::eq(int j) {
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 }
94 ExecStatus
95 TellCache::tell(Space& home, IntView x) {
96 if (_eq == -2) {
97 return ES_FAILED;
98 } else if (_eq >= 0) {
99 GECODE_ME_CHECK(x.eq(home,_eq));
100 }
101 Iter::Values::Array nqi(_nq, _n_nq);
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 */
112 ExecStatus
113 Pack::propagate(Space& home, const ModEventDelta& med) {
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.
214 if (IntView::me(modeventdelta()) != ME_INT_NONE)
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
359 ExecStatus
360 Pack::post(Home home, ViewArray<OffsetView>& l, ViewArray<Item>& bs) {
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