Generated on Fri Oct 19 11:24:48 2018 for Gecode by doxygen 1.6.3

bin-packing.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Stefano Gualandi <stefano.gualandi@gmail.com>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Stefano Gualandi, 2013
00009  *     Christian Schulte, 2010
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <gecode/int/bin-packing.hh>
00037 
00038 namespace Gecode {
00039 
00040   void
00041   binpacking(Home home,
00042              const IntVarArgs& l,
00043              const IntVarArgs& b, const IntArgs& s,
00044              IntPropLevel) {
00045     using namespace Int;
00046     if (same(l,b))
00047       throw ArgumentSame("Int::binpacking");
00048     if (b.size() != s.size())
00049       throw ArgumentSizeMismatch("Int::binpacking");
00050     for (int i=0; i<s.size(); i++)
00051       Limits::nonnegative(s[i],"Int::binpacking");
00052     GECODE_POST;
00053 
00054     ViewArray<OffsetView> lv(home,l.size());
00055     for (int i=0; i<l.size(); i++)
00056       lv[i] = OffsetView(l[i],0);
00057 
00058     ViewArray<BinPacking::Item> bs(home,b.size());
00059     for (int i=0; i<bs.size(); i++)
00060       bs[i] = BinPacking::Item(b[i],s[i]);
00061 
00062     GECODE_ES_FAIL(Int::BinPacking::Pack::post(home,lv,bs));
00063   }
00064 
00065   IntSet
00066   binpacking(Home home, int d,
00067              const IntVarArgs& l, const IntVarArgs& b,
00068              const IntArgs& s, const IntArgs& c,
00069              IntPropLevel) {
00070     using namespace Int;
00071 
00072     if (same(l,b))
00073       throw ArgumentSame("Int::binpacking");
00074 
00075     // The number of items
00076     int n = b.size();
00077     // The number of bins
00078     int m = l.size() / d;
00079 
00080     // Check input sizes
00081     if ((n*d != s.size()) || (m*d != l.size()) || (d != c.size()))
00082       throw ArgumentSizeMismatch("Int::binpacking");
00083     for (int i=0; i<s.size(); i++)
00084       Limits::nonnegative(s[i],"Int::binpacking");
00085     for (int i=0; i<c.size(); i++)
00086       Limits::nonnegative(c[i],"Int::binpacking");
00087 
00088     if (home.failed())
00089       return IntSet::empty;
00090 
00091     PostInfo pi(home);
00092 
00093     // Capacity constraint for each dimension
00094     for (int k=0; k<d; k++)
00095       for (int j=0; j<m; j++) {
00096         IntView li(l[j*d+k]);
00097         if (me_failed(li.lq(home,c[k]))) {
00098           home.fail();
00099           return IntSet::empty;
00100         }
00101       }
00102 
00103     // Post a binpacking constraint for each dimension
00104     for (int k=0; k<d; k++) {
00105       ViewArray<OffsetView> lv(home,m);
00106       for (int j=0; j<m; j++)
00107         lv[j] = OffsetView(l[j*d+k],0);
00108 
00109       ViewArray<BinPacking::Item> bv(home,n);
00110       for (int i=0; i<n; i++)
00111         bv[i] = BinPacking::Item(b[i],s[i*d+k]);
00112 
00113       if (Int::BinPacking::Pack::post(home,lv,bv) == ES_FAILED) {
00114         home.fail();
00115         return IntSet::empty;
00116       }
00117     }
00118 
00119 
00120     // Clique Finding and distinct posting
00121     {
00122       // First construct the conflict graph
00123       Region r;
00124       BinPacking::ConflictGraph cg(home,r,b,m);
00125 
00126       for (int i=0; i<n-1; i++) {
00127         for (int j=i+1; j<n; j++) {
00128           unsigned int nl = 0;
00129           unsigned int ds = 0;
00130           IntVarValues ii(b[i]), jj(b[j]);
00131           while (ii() && jj()) {
00132             if (ii.val() < jj.val()) {
00133               ++ii;
00134             } else if (ii.val() > jj.val()) {
00135               ++jj;
00136             } else {
00137               ds++;
00138               for (int k=0; k<d; k++)
00139                 if (s[i*d+k] + s[j*d+k] > c[k]) {
00140                   nl++;
00141                   break;
00142                 }
00143               ++ii; ++jj;
00144             }
00145           }
00146           if (nl >= ds)
00147             cg.edge(i,j);
00148         }
00149       }
00150 
00151       if (cg.post() == ES_FAILED)
00152         home.fail();
00153 
00154       // The clique can be computed even if home is failed
00155       return cg.maxclique();
00156     }
00157   }
00158 
00159 }
00160 
00161 // STATISTICS: int-post