Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
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) {
60  return new (home) Pack(home,*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  Region region;
124  {
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  region.free();
214  }
215 
216  // Only if the propagator is at fixpoint here, continue with the more
217  // expensive stage for propagation.
218  if (IntView::me(modeventdelta()) != ME_INT_NONE)
219  return ES_NOFIX;
220 
221  // Now the invariant holds that no more assigned bins exist!
222  {
223 
224  // Size of items
225  SizeSetMinusOne* s = region.alloc<SizeSetMinusOne>(m);
226 
227  for (int j=m; j--; )
228  s[j] = SizeSetMinusOne(region,n);
229 
230  // Set up size information
231  for (int i=0; i<n; i++) {
232  assert(!bs[i].assigned());
233  for (ViewValues<IntView> j(bs[i].bin()); j(); ++j)
234  s[j.val()].add(bs[i].size());
235  }
236 
237  for (int j=m; j--; ) {
238  // Can items still be packed into bin?
239  if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].max()))
240  return ES_FAILED;
241  int ap, bp;
242  // Must there be packed more items into bin?
243  if (nosum(static_cast<SizeSet&>(s[j]), l[j].min(), l[j].min(),
244  ap, bp))
245  GECODE_ME_CHECK(l[j].gq(home,bp));
246  // Must there be packed less items into bin?
247  if (nosum(static_cast<SizeSet&>(s[j]), l[j].max(), l[j].max(),
248  ap, bp))
249  GECODE_ME_CHECK(l[j].lq(home,ap));
250  }
251 
252  TellCache tc(region,m);
253 
254  int k=0;
255  for (int i=0; i<n; i++) {
256  assert(!bs[i].assigned());
257  for (ViewValues<IntView> j(bs[i].bin()); j(); ++j) {
258  // Items must be removed in decreasing size!
259  s[j.val()].minus(bs[i].size());
260  // Can item i still be packed into bin j?
261  if (nosum(s[j.val()],
262  l[j.val()].min() - bs[i].size(),
263  l[j.val()].max() - bs[i].size()))
264  tc.nq(j.val());
265  // Must item i be packed into bin j?
266  if (nosum(s[j.val()], l[j.val()].min(), l[j.val()].max()))
267  tc.eq(j.val());
268  }
269  GECODE_ES_CHECK(tc.tell(home,bs[i].bin()));
270  if (bs[i].assigned()) {
271  int j = bs[i].bin().val();
272  l[j].offset(l[j].offset() - bs[i].size());
273  t -= bs[i].size();
274  } else {
275  bs[k++] = bs[i];
276  }
277  }
278  n=k; bs.size(n);
279  region.free();
280  }
281 
282  // Perform lower bound checking
283  if (n > 0) {
284 
285  // Find capacity estimate (we start from bs[0] as it might be
286  // not packable, actually (will be detected later anyway)!
287  int c = bs[0].size();
288  for (int j=m; j--; )
289  c = std::max(c,l[j].max());
290 
291  // Count how many items have a certain size (bucket sort)
292  int* n_s = region.alloc<int>(c+1);
293 
294  for (int i=c+1; i--; )
295  n_s[i] = 0;
296 
297  // Count unpacked items
298  for (int i=n; i--; )
299  n_s[bs[i].size()]++;
300 
301  // Number of items and remaining bin load
302  int nm = n;
303 
304  // Only count positive remaining bin loads
305  for (int j=m; j--; )
306  if (l[j].max() < 0) {
307  return ES_FAILED;
308  } else if (c > l[j].max()) {
309  n_s[c - l[j].max()]++; nm++;
310  }
311 
312  // Sizes of items and remaining bin loads
313  int* s = region.alloc<int>(nm);
314 
315  // Setup sorted sizes
316  {
317  int k=0;
318  for (int i=c+1; i--; )
319  for (int j=n_s[i]; j--; )
320  s[k++]=i;
321  assert(k == nm);
322  }
323 
324  // Items in N1 are from 0 ... n1 - 1
325  int n1 = 0;
326  // Items in N2 are from n1 ... n12 - 1, we count elements in N1 and N2
327  int n12 = 0;
328  // Items in N3 are from n12 ... n3 - 1
329  int n3 = 0;
330  // Free space in N2
331  int f2 = 0;
332  // Total size of items in N3
333  int s3 = 0;
334 
335  // Initialize n12 and f2
336  for (; (n12 < nm) && (s[n12] > c/2); n12++)
337  f2 += c - s[n12];
338 
339  // Initialize n3 and s3
340  for (n3 = n12; n3 < nm; n3++)
341  s3 += s[n3];
342 
343  // Compute lower bounds
344  for (int k=0; k<=c/2; k++) {
345  // Make N1 larger by adding elements and N2 smaller
346  for (; (n1 < nm) && (s[n1] > c-k); n1++)
347  f2 -= c - s[n1];
348  assert(n1 <= n12);
349  // Make N3 smaller by removing elements
350  for (; (s[n3-1] < k) && (n3 > n12); n3--)
351  s3 -= s[n3-1];
352  // Overspill
353  int o = (s3 > f2) ? ((s3 - f2 + c - 1) / c) : 0;
354  if (n12 + o > m)
355  return ES_FAILED;
356  }
357  region.free();
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 
void free(void)
Free allocate memory.
Definition: region.hpp:354
void mod(Home home, IntVar x0, IntVar x1, IntVar x2, IntPropLevel ipl)
Post propagator for .
Definition: arithmetic.cpp:267
NodeType t
Type of node.
Definition: bool-expr.cpp:234
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4634
TellCache(Region &region, int m)
Initialize cache for at most m values.
Definition: propagate.cpp:84
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
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:384
Value iterator for array of integers
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: propagate.cpp:48
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
int ModEvent
Type for modification events.
Definition: core.hpp:64
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:57
#define forceinline
Definition: config.hpp:182
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: propagate.cpp:59
Computation spaces.
Definition: core.hpp:1668
void nq(int j)
Record that view must be different from j.
Definition: propagate.cpp:87
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:620
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:69
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
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:466
ExecStatus tell(Space &home, IntView x)
Perform tell to view x and reset cache.
Definition: propagate.cpp:99
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:506
View arrays.
Definition: array.hpp:228
void add(int s)
Add new size s.
Definition: propagate.hpp:102
void eq(int j)
Record that view must be equal to j, return false if not possible.
Definition: propagate.cpp:91
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Record tell information.
Definition: propagate.cpp:64
int _eq
Value to which view should be assigned.
Definition: propagate.cpp:71
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Bin-packing propagator.
Definition: bin-packing.hh:145
Example: Bin packing
Integer view for integer variables.
Definition: view.hpp:129
ExecStatus
Definition: core.hpp:464
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.
Definition: view.hpp:514
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
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:588
void minus(int s)
Discard size s.
Definition: propagate.hpp:124
Propagation has not computed fixpoint.
Definition: core.hpp:467
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: propagate.cpp:117
Gecode toplevel namespace
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition: val.hpp:82
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1203
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
Home class for posting propagators
Definition: core.hpp:846
virtual void reschedule(Space &home)
Schedule function.
Definition: propagate.cpp:53
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:67
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58