Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
38namespace Gecode {
39
40 void
42 const IntVarArgs& l,
43 const IntVarArgs& b, const IntArgs& s,
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
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,
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
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
void fail(void)
Mark space as failed.
Definition core.hpp:4046
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4055
Passing integer arguments.
Definition int.hh:634
static const IntSet empty
Empty set.
Definition int.hh:283
Passing integer variables.
Definition int.hh:662
Value iterator for integer variables.
Definition int.hh:493
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Exception: Arguments are of different size
Definition exception.hpp:73
Graph containing conflict information.
ExecStatus post(void)
Post additional constraints.
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)
IntSet maxclique(void) const
Return maximal clique found.
Item combining bin and size information.
static ExecStatus post(Home home, ViewArray< OffsetView > &l, ViewArray< Item > &bs)
Post propagator for loads l and items bs.
Integer view for integer variables.
Definition view.hpp:129
Offset integer view.
Definition view.hpp:443
int val(void) const
Return current value.
Class to set group information when a post function is executed.
Definition core.hpp:950
Handle to region.
Definition region.hpp:55
View arrays.
Definition array.hpp:253
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1162
const int * pi[]
Definition photo.cpp:14262
#define GECODE_POST
Check for failure in a constraint post function.
Definition macros.hpp:40
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
void binpacking(Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel ipl=IPL_DEF)
Post propagator for bin packing.
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:989
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
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1943
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474