this repo has no description
dekker.one
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
36#include <gecode/int/bin-packing.hh>
37
38namespace Gecode {
39
40 void
41 binpacking(Home home,
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");
52 GECODE_POST;
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
62 GECODE_ES_FAIL(Int::BinPacking::Pack::post(home,lv,bs));
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
109 ViewArray<BinPacking::Item> bv(home,n);
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