Generated on Sat Feb 7 2015 02:01:11 for Gecode by doxygen 1.8.9.1
bin-packing.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Stefano Gualandi <stefano.gualandi@gmail.com>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Stefano Gualandi, 2013
9  * Christian Schulte, 2010
10  *
11  * Last modified:
12  * $Date: 2014-07-30 14:16:57 +0200 (Wed, 30 Jul 2014) $ by $Author: schulte $
13  * $Revision: 14181 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
41 
42 namespace Gecode {
43 
44  void
46  const IntVarArgs& l,
47  const IntVarArgs& b, const IntArgs& s,
48  IntConLevel) {
49  using namespace Int;
50  if (l.same(home,b))
51  throw ArgumentSame("Int::binpacking");
52  if (b.size() != s.size())
53  throw ArgumentSizeMismatch("Int::binpacking");
54  for (int i=s.size(); i--; )
55  Limits::nonnegative(s[i],"Int::binpacking");
56  if (home.failed()) return;
57 
58  ViewArray<OffsetView> lv(home,l.size());
59  for (int i=l.size(); i--; )
60  lv[i] = OffsetView(l[i],0);
61 
62  ViewArray<BinPacking::Item> bs(home,b.size());
63  for (int i=bs.size(); i--; )
64  bs[i] = BinPacking::Item(b[i],s[i]);
65 
67  }
68 
69  IntSet
70  binpacking(Home home, int d,
71  const IntVarArgs& l, const IntVarArgs& b,
72  const IntArgs& s, const IntArgs& c,
73  IntConLevel) {
74  using namespace Int;
75 
76  if (l.same(home,b))
77  throw ArgumentSame("Int::binpacking");
78 
79  // The number of items
80  int n = b.size();
81  // The number of bins
82  int m = l.size() / d;
83 
84  // Check input sizes
85  if ((n*d != s.size()) || (m*d != l.size()) || (d != c.size()))
86  throw ArgumentSizeMismatch("Int::binpacking");
87  for (int i=s.size(); i--; )
88  Limits::nonnegative(s[i],"Int::binpacking");
89  for (int i=c.size(); i--; )
90  Limits::nonnegative(c[i],"Int::binpacking");
91 
92  if (home.failed())
93  return IntSet::empty;
94 
95  // Capacity constraint for each dimension
96  for (int k=d; k--; )
97  for (int j=m; j--; ) {
98  IntView li(l[j*d+k]);
99  if (me_failed(li.lq(home,c[k]))) {
100  home.fail();
101  return IntSet::empty;
102  }
103  }
104 
105  // Post a binpacking constraint for each dimension
106  for (int k=d; k--; ) {
107  ViewArray<OffsetView> lv(home,m);
108  for (int j=m; j--; )
109  lv[j] = OffsetView(l[j*d+k],0);
110 
111  ViewArray<BinPacking::Item> bv(home,n);
112  for (int i=n; i--; )
113  bv[i] = BinPacking::Item(b[i],s[i*d+k]);
114 
115  if (Int::BinPacking::Pack::post(home,lv,bv) == ES_FAILED) {
116  home.fail();
117  return IntSet::empty;
118  }
119  }
120 
121 
122  // Clique Finding and distinct posting
123  {
124  // First construct the conflict graph
125  Region r(home);
126  BinPacking::ConflictGraph cg(home,r,b,m);
127 
128  for (int i=0; i<n-1; i++) {
129  for (int j=i+1; j<n; j++) {
130  unsigned int nl = 0;
131  unsigned int ds = 0;
132  IntVarValues ii(b[i]), jj(b[j]);
133  while (ii() && jj()) {
134  if (ii.val() < jj.val()) {
135  ++ii;
136  } else if (ii.val() > jj.val()) {
137  ++jj;
138  } else {
139  ds++;
140  for (int k=d; k--; )
141  if (s[i*d+k] + s[j*d+k] > c[k]) {
142  nl++;
143  break;
144  }
145  ++ii; ++jj;
146  }
147  }
148  if (nl >= ds)
149  cg.edge(i,j);
150  }
151  }
152 
153  if (cg.post() == ES_FAILED)
154  home.fail();
155 
156  // The clique can be computed even if home is failed
157  return cg.maxclique();
158  }
159  }
160 
161 }
162 
163 // STATISTICS: int-post
Value iterator for integer variables.
Definition: int.hh:469
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Item combining bin and size information.
Definition: bin-packing.hh:57
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
void nonnegative(int n, const char *l)
Check whether n is in range and nonnegative, otherwise throw out of limits with information l...
Definition: limits.hpp:72
Handle to region.
Definition: region.hpp:61
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition: propagate.cpp:358
ExecStatus post(void)
Post additional constraints.
Graph containing conflict information.
Definition: bin-packing.hh:183
IntSet maxclique(void) const
Return maximal clique found.
Gecode::IntSet d(v, 7)
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:525
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:115
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
void edge(int i, int j, bool add=true)
Add or remove an edge between nodes i and j (i must be less than j)
Offset integer view.
Definition: view.hpp:422
View arrays.
Definition: array.hpp:234
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
static const IntSet empty
Empty set.
Definition: int.hh:262
const LinInstr * li[]
Definition: mm-lin.cpp:1798
Integer view for integer variables.
Definition: view.hpp:129
Exception: Arguments contain same variable multiply
Definition: exception.hpp:84
int val(void) const
Return current value.
void fail(void)
Mark space as failed.
Definition: core.hpp:3437
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntConLevel)
Post propagator for bin packing.
Definition: bin-packing.cpp:45
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Home class for posting propagators
Definition: core.hpp:717
Exception: Arguments are of different size
Definition: exception.hpp:77
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
bool same(const Space &home) const
Test whether array contains same variable multiply.
Definition: array.hpp:2085
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58