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 IntConLevel) {
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 if (home.failed()) return;
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 IntConLevel) {
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
00096 for (int k=d; k--; )
00097 for (int j=m; j--; ) {
00098 IntView li(l[j*d+k]);
00099 if (me_failed(li.lq(home,c[k]))) {
00100 home.fail();
00101 return IntSet::empty;
00102 }
00103 }
00104
00105
00106 for (int k=d; k--; ) {
00107 ViewArray<OffsetView> lv(home,m);
00108 for (int j=m; j--; )
00109 lv[j] = OffsetView(l[j*d+k],0);
00110
00111 ViewArray<BinPacking::Item> bv(home,n);
00112 for (int i=n; i--; )
00113 bv[i] = BinPacking::Item(b[i],s[i*d+k]);
00114
00115 if (Int::BinPacking::Pack::post(home,lv,bv) == ES_FAILED) {
00116 home.fail();
00117 return IntSet::empty;
00118 }
00119 }
00120
00121
00122
00123 {
00124
00125 Region r(home);
00126 BinPacking::ConflictGraph cg(home,r,b,m);
00127
00128 for (int i=0; i<n-1; i++) {
00129 for (int j=i+1; j<n; j++) {
00130 unsigned int nl = 0;
00131 unsigned int ds = 0;
00132 IntVarValues ii(b[i]), jj(b[j]);
00133 while (ii() && jj()) {
00134 if (ii.val() < jj.val()) {
00135 ++ii;
00136 } else if (ii.val() > jj.val()) {
00137 ++jj;
00138 } else {
00139 ds++;
00140 for (int k=d; k--; )
00141 if (s[i*d+k] + s[j*d+k] > c[k]) {
00142 nl++;
00143 break;
00144 }
00145 ++ii; ++jj;
00146 }
00147 }
00148 if (nl >= ds)
00149 cg.edge(i,j);
00150 }
00151 }
00152
00153 if (cg.post() == ES_FAILED)
00154 home.fail();
00155
00156
00157 return cg.maxclique();
00158 }
00159 }
00160
00161 }
00162
00163