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