bin-packing.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #include <gecode/int/bin-packing.hh>
00041
00042 namespace Gecode {
00043
00044 void
00045 binpacking(Home home,
00046 const IntVarArgs& l,
00047 const IntVarArgs& b, const IntArgs& s,
00048 IntPropLevel) {
00049 using namespace Int;
00050 if (l.same(home,b))
00051 throw ArgumentSame("Int::binpacking");
00052 if (b.size() != s.size())
00053 throw ArgumentSizeMismatch("Int::binpacking");
00054 for (int i=s.size(); i--; )
00055 Limits::nonnegative(s[i],"Int::binpacking");
00056 GECODE_POST;
00057
00058 ViewArray<OffsetView> lv(home,l.size());
00059 for (int i=l.size(); i--; )
00060 lv[i] = OffsetView(l[i],0);
00061
00062 ViewArray<BinPacking::Item> bs(home,b.size());
00063 for (int i=bs.size(); i--; )
00064 bs[i] = BinPacking::Item(b[i],s[i]);
00065
00066 GECODE_ES_FAIL(Int::BinPacking::Pack::post(home,lv,bs));
00067 }
00068
00069 IntSet
00070 binpacking(Home home, int d,
00071 const IntVarArgs& l, const IntVarArgs& b,
00072 const IntArgs& s, const IntArgs& c,
00073 IntPropLevel) {
00074 using namespace Int;
00075
00076 if (l.same(home,b))
00077 throw ArgumentSame("Int::binpacking");
00078
00079
00080 int n = b.size();
00081
00082 int m = l.size() / d;
00083
00084
00085 if ((n*d != s.size()) || (m*d != l.size()) || (d != c.size()))
00086 throw ArgumentSizeMismatch("Int::binpacking");
00087 for (int i=s.size(); i--; )
00088 Limits::nonnegative(s[i],"Int::binpacking");
00089 for (int i=c.size(); i--; )
00090 Limits::nonnegative(c[i],"Int::binpacking");
00091
00092 if (home.failed())
00093 return IntSet::empty;
00094
00095 PostInfo pi(home);
00096
00097
00098 for (int k=d; k--; )
00099 for (int j=m; j--; ) {
00100 IntView li(l[j*d+k]);
00101 if (me_failed(li.lq(home,c[k]))) {
00102 home.fail();
00103 return IntSet::empty;
00104 }
00105 }
00106
00107
00108 for (int k=d; k--; ) {
00109 ViewArray<OffsetView> lv(home,m);
00110 for (int j=m; j--; )
00111 lv[j] = OffsetView(l[j*d+k],0);
00112
00113 ViewArray<BinPacking::Item> bv(home,n);
00114 for (int i=n; i--; )
00115 bv[i] = BinPacking::Item(b[i],s[i*d+k]);
00116
00117 if (Int::BinPacking::Pack::post(home,lv,bv) == ES_FAILED) {
00118 home.fail();
00119 return IntSet::empty;
00120 }
00121 }
00122
00123
00124
00125 {
00126
00127 Region r(home);
00128 BinPacking::ConflictGraph cg(home,r,b,m);
00129
00130 for (int i=0; i<n-1; i++) {
00131 for (int j=i+1; j<n; j++) {
00132 unsigned int nl = 0;
00133 unsigned int ds = 0;
00134 IntVarValues ii(b[i]), jj(b[j]);
00135 while (ii() && jj()) {
00136 if (ii.val() < jj.val()) {
00137 ++ii;
00138 } else if (ii.val() > jj.val()) {
00139 ++jj;
00140 } else {
00141 ds++;
00142 for (int k=d; k--; )
00143 if (s[i*d+k] + s[j*d+k] > c[k]) {
00144 nl++;
00145 break;
00146 }
00147 ++ii; ++jj;
00148 }
00149 }
00150 if (nl >= ds)
00151 cg.edge(i,j);
00152 }
00153 }
00154
00155 if (cg.post() == ES_FAILED)
00156 home.fail();
00157
00158
00159 return cg.maxclique();
00160 }
00161 }
00162
00163 }
00164
00165