Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
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 
36 namespace 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*
55  Pack::copy(Space& home) {
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);
76  ExecStatus tell(Space& home, IntView x);
77  };
78 
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  }
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  */
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
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 
void free(void)
Free allocate memory.
Definition: region.hpp:356
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:263
NodeType t
Type of node.
Definition: bool-expr.cpp:230
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4714
TellCache(Region &region, int m)
Initialize cache for at most m values.
Definition: propagate.cpp:80
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:166
ViewArray< Item > bs
Items with bin and size.
Definition: bin-packing.hh:146
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
Value iterator for array of integers
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: propagate.cpp:44
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
int ModEvent
Type for modification events.
Definition: core.hpp:62
Pack(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Constructor for posting.
Definition: propagate.hpp:151
ViewArray< OffsetView > l
Views for load of bins.
Definition: bin-packing.hh:144
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: propagate.cpp:55
Computation spaces.
Definition: core.hpp:1701
void nq(int j)
Record that view must be different from j.
Definition: propagate.cpp:83
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition: propagate.cpp:360
Base-class for both propagators and branchers.
Definition: core.hpp:627
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:206
int _n_nq
Number of values to be pruned.
Definition: propagate.cpp:65
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Gecode::FloatVal c(-8, 8)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Definition: core.hpp:473
ExecStatus tell(Space &home, IntView x)
Perform tell to view x and reset cache.
Definition: propagate.cpp:95
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
unsigned int size(I &i)
Size of all ranges of range iterator i.
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
Expensive.
Definition: core.hpp:513
View arrays.
Definition: array.hpp:235
void add(int s)
Add new size s.
Definition: propagate.hpp:98
void eq(int j)
Record that view must be equal to j, return false if not possible.
Definition: propagate.cpp:87
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Record tell information.
Definition: propagate.cpp:60
int _eq
Value to which view should be assigned.
Definition: propagate.cpp:67
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Bin-packing propagator.
Definition: bin-packing.hh:141
Example: Bin packing
Integer view for integer variables.
Definition: view.hpp:129
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
Size sets with one element discarded.
Definition: bin-packing.hh:111
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:639
void minus(int s)
Discard size s.
Definition: propagate.hpp:120
Propagation has not computed fixpoint.
Definition: core.hpp:474
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: propagate.cpp:113
Gecode toplevel namespace
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition: val.hpp:78
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
virtual void reschedule(Space &home)
Schedule function.
Definition: propagate.cpp:49
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:63
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54