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