Generated on Tue Mar 24 2020 14:04:04 for Gecode by doxygen 1.8.17
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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
37 
38 namespace Gecode {
39 
40  void
42  const IntVarArgs& l,
43  const IntVarArgs& b, const IntArgs& s,
44  IntPropLevel) {
45  using namespace Int;
46  if (same(l,b))
47  throw ArgumentSame("Int::binpacking");
48  if (b.size() != s.size())
49  throw ArgumentSizeMismatch("Int::binpacking");
50  for (int i=0; i<s.size(); i++)
51  Limits::nonnegative(s[i],"Int::binpacking");
53 
54  ViewArray<OffsetView> lv(home,l.size());
55  for (int i=0; i<l.size(); i++)
56  lv[i] = OffsetView(l[i],0);
57 
58  ViewArray<BinPacking::Item> bs(home,b.size());
59  for (int i=0; i<bs.size(); i++)
60  bs[i] = BinPacking::Item(b[i],s[i]);
61 
63  }
64 
65  IntSet
66  binpacking(Home home, int d,
67  const IntVarArgs& l, const IntVarArgs& b,
68  const IntArgs& s, const IntArgs& c,
69  IntPropLevel) {
70  using namespace Int;
71 
72  if (same(l,b))
73  throw ArgumentSame("Int::binpacking");
74 
75  // The number of items
76  int n = b.size();
77  // The number of bins
78  int m = l.size() / d;
79 
80  // Check input sizes
81  if ((n*d != s.size()) || (m*d != l.size()) || (d != c.size()))
82  throw ArgumentSizeMismatch("Int::binpacking");
83  for (int i=0; i<s.size(); i++)
84  Limits::nonnegative(s[i],"Int::binpacking");
85  for (int i=0; i<c.size(); i++)
86  Limits::nonnegative(c[i],"Int::binpacking");
87 
88  if (home.failed())
89  return IntSet::empty;
90 
91  PostInfo pi(home);
92 
93  // Capacity constraint for each dimension
94  for (int k=0; k<d; k++)
95  for (int j=0; j<m; j++) {
96  IntView li(l[j*d+k]);
97  if (me_failed(li.lq(home,c[k]))) {
98  home.fail();
99  return IntSet::empty;
100  }
101  }
102 
103  // Post a binpacking constraint for each dimension
104  for (int k=0; k<d; k++) {
105  ViewArray<OffsetView> lv(home,m);
106  for (int j=0; j<m; j++)
107  lv[j] = OffsetView(l[j*d+k],0);
108 
110  for (int i=0; i<n; i++)
111  bv[i] = BinPacking::Item(b[i],s[i*d+k]);
112 
113  if (Int::BinPacking::Pack::post(home,lv,bv) == ES_FAILED) {
114  home.fail();
115  return IntSet::empty;
116  }
117  }
118 
119 
120  // Clique Finding and distinct posting
121  {
122  // First construct the conflict graph
123  Region r;
124  BinPacking::ConflictGraph cg(home,r,b,m);
125 
126  for (int i=0; i<n-1; i++) {
127  for (int j=i+1; j<n; j++) {
128  unsigned int nl = 0;
129  unsigned int ds = 0;
130  IntVarValues ii(b[i]), jj(b[j]);
131  while (ii() && jj()) {
132  if (ii.val() < jj.val()) {
133  ++ii;
134  } else if (ii.val() > jj.val()) {
135  ++jj;
136  } else {
137  ds++;
138  for (int k=0; k<d; k++)
139  if (s[i*d+k] + s[j*d+k] > c[k]) {
140  nl++;
141  break;
142  }
143  ++ii; ++jj;
144  }
145  }
146  if (nl >= ds)
147  cg.edge(i,j);
148  }
149  }
150 
151  if (cg.post() == ES_FAILED)
152  home.fail();
153 
154  // The clique can be computed even if home is failed
155  return cg.maxclique();
156  }
157  }
158 
159 }
160 
161 // STATISTICS: int-post
Exception: Arguments are of different size
Definition: exception.hpp:73
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel)
Post propagator for bin packing.
Definition: bin-packing.cpp:41
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
const int * pi[]
Definition: photo.cpp:14262
Passing integer variables.
Definition: int.hh:656
IntSet maxclique(void) const
Return maximal clique found.
static const IntSet empty
Empty set.
Definition: int.hh:283
Value iterator for integer variables.
Definition: int.hh:490
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Definition: propagate.cpp:360
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)
int val(void) const
Return current value.
Gecode toplevel namespace
const LinInstr * li[]
Definition: mm-lin.cpp:1794
Exception: Arguments contain same variable multiply
Definition: exception.hpp:80
Home class for posting propagators
Definition: core.hpp:856
Handle to region.
Definition: region.hpp:55
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
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:68
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Class to set group information when a post function is executed.
Definition: core.hpp:948
ExecStatus post(void)
Post additional constraints.
Offset integer view.
Definition: view.hpp:443
Create c
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4048
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void fail(void)
Mark space as failed.
Definition: core.hpp:4039
Gecode::IntSet d(v, 7)
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
Integer view for integer variables.
Definition: view.hpp:129
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1156
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition: array.hpp:1937
View arrays.
Definition: array.hpp:253
Graph containing conflict information.
Definition: bin-packing.hh:182
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
Passing integer arguments.
Definition: int.hh:628
Gecode::IntArgs i({1, 2, 3, 4})
Item combining bin and size information.
Definition: bin-packing.hh:53