Generated on Fri Jul 13 2018 06:08:21 for Gecode by doxygen 1.8.14
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: 2016-10-25 12:52:26 +0200 (Tue, 25 Oct 2016) $ by $Author: schulte $
13  * $Revision: 15233 $
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  IntPropLevel) {
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");
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  IntPropLevel) {
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  PostInfo pi(home);
96 
97  // Capacity constraint for each dimension
98  for (int k=d; k--; )
99  for (int j=m; j--; ) {
100  IntView li(l[j*d+k]);
101  if (me_failed(li.lq(home,c[k]))) {
102  home.fail();
103  return IntSet::empty;
104  }
105  }
106 
107  // Post a binpacking constraint for each dimension
108  for (int k=d; k--; ) {
109  ViewArray<OffsetView> lv(home,m);
110  for (int j=m; j--; )
111  lv[j] = OffsetView(l[j*d+k],0);
112 
114  for (int i=n; i--; )
115  bv[i] = BinPacking::Item(b[i],s[i*d+k]);
116 
117  if (Int::BinPacking::Pack::post(home,lv,bv) == ES_FAILED) {
118  home.fail();
119  return IntSet::empty;
120  }
121  }
122 
123 
124  // Clique Finding and distinct posting
125  {
126  // First construct the conflict graph
127  Region r(home);
128  BinPacking::ConflictGraph cg(home,r,b,m);
129 
130  for (int i=0; i<n-1; i++) {
131  for (int j=i+1; j<n; j++) {
132  unsigned int nl = 0;
133  unsigned int ds = 0;
134  IntVarValues ii(b[i]), jj(b[j]);
135  while (ii() && jj()) {
136  if (ii.val() < jj.val()) {
137  ++ii;
138  } else if (ii.val() > jj.val()) {
139  ++jj;
140  } else {
141  ds++;
142  for (int k=d; k--; )
143  if (s[i*d+k] + s[j*d+k] > c[k]) {
144  nl++;
145  break;
146  }
147  ++ii; ++jj;
148  }
149  }
150  if (nl >= ds)
151  cg.edge(i,j);
152  }
153  }
154 
155  if (cg.post() == ES_FAILED)
156  home.fail();
157 
158  // The clique can be computed even if home is failed
159  return cg.maxclique();
160  }
161  }
162 
163 }
164 
165 // STATISTICS: int-post
Value iterator for integer variables.
Definition: int.hh:472
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
Item combining bin and size information.
Definition: bin-packing.hh:57
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
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel)
Post propagator for bin packing.
Definition: bin-packing.cpp:45
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition: propagate.cpp:364
int val(void) const
Return current value.
ExecStatus post(void)
Post additional constraints.
Graph containing conflict information.
Definition: bin-packing.hh:186
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:542
Class to set group information when a post function is executed.
Definition: core.hpp:1014
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4099
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
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)
const int * pi[]
Definition: photo.cpp:14266
Offset integer view.
Definition: view.hpp:422
View arrays.
Definition: array.hpp:234
Passing integer variables.
Definition: int.hh:639
Passing integer arguments.
Definition: int.hh:610
static const IntSet empty
Empty set.
Definition: int.hh:265
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:955
const LinInstr * li[]
Definition: mm-lin.cpp:1798
IntSet maxclique(void) const
Return maximal clique found.
Integer view for integer variables.
Definition: view.hpp:129
Exception: Arguments contain same variable multiply
Definition: exception.hpp:84
void fail(void)
Mark space as failed.
Definition: core.hpp:4090
Gecode toplevel namespace
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:44
Home class for posting propagators
Definition: core.hpp:922
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:107
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58