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 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2010 00008 * 00009 * Last modified: 00010 * $Date: 2010-10-06 23:20:35 +0200 (Wed, 06 Oct 2010) $ by $Author: schulte $ 00011 * $Revision: 11468 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include "test/int.hh" 00039 00040 #include <gecode/minimodel.hh> 00041 #include <climits> 00042 00043 namespace Test { namespace Int { 00044 00046 namespace BinPacking { 00047 00053 00054 class LoadBinAssignment : public Assignment { 00055 protected: 00057 int n_bins; 00059 int n_items; 00061 Gecode::IntSet d_load; 00063 Gecode::IntSet d_bin; 00065 int load; 00067 Gecode::IntSetValues* dsv; 00068 public: 00070 LoadBinAssignment(int m, const Gecode::IntSet& d_m, 00071 int n, const Gecode::IntSet& d_n, 00072 int l) 00073 : Assignment(m+n,d_m), 00074 n_bins(m), n_items(n), d_load(d_m), d_bin(d_n), load(l), 00075 dsv(new Gecode::IntSetValues[static_cast<unsigned int>(m+n)]) { 00076 for (int i=n_bins; i--; ) 00077 dsv[i].init(d_load); 00078 for (int i=n_items; i--; ) 00079 dsv[n_bins+i].init(d_bin); 00080 } 00082 virtual bool operator()(void) const { 00083 return dsv[0](); 00084 } 00086 virtual void operator++(void) { 00087 // Try to generate next bin assignment 00088 { 00089 int i = n_items-1; 00090 while (i >= 0) { 00091 ++dsv[n_bins+i]; 00092 if (dsv[n_bins+i]()) 00093 return; 00094 dsv[n_bins+(i--)].init(d_bin); 00095 } 00096 } 00097 // Try to generate next load assignment 00098 { 00099 retry: 00100 int i = n_bins-1; 00101 while (true) { 00102 ++dsv[i]; 00103 if (dsv[i]() || (i == 0)) { 00104 if (dsv[i]() && (load >= 0)) { 00105 int l = 0; 00106 for (int k=0;k<n_bins; k++) 00107 l += dsv[k].val(); 00108 if (load != l) 00109 goto retry; 00110 } 00111 return; 00112 } 00113 dsv[i--].init(d_load); 00114 } 00115 } 00116 } 00118 virtual int operator[](int i) const { 00119 assert((i>=0) && (i<n_bins+n_items)); 00120 return dsv[i].val(); 00121 } 00123 virtual ~LoadBinAssignment(void) { 00124 delete [] dsv; 00125 } 00126 }; 00127 00129 class BPT : public Test { 00130 protected: 00132 int m; 00134 Gecode::IntArgs s; 00136 bool valid; 00138 int t; 00140 mutable int il[4]; 00142 static int total(const Gecode::IntArgs& s) { 00143 int t = 0; 00144 for (int i=s.size(); i--; ) 00145 t += s[i]; 00146 return t; 00147 } 00148 public: 00150 BPT(int m0, const Gecode::IntArgs& s0, bool v=true) 00151 : Test("BinPacking::"+str(m0)+"::"+str(s0)+"::"+(v ? "+" : "-"), 00152 m0+s0.size(), 0, 100), 00153 m(m0), s(s0), valid(v), t(total(s)) { 00154 testsearch = false; 00155 } 00157 virtual Assignment* assignment(void) const { 00158 // Compute plausible bin sizes 00159 int a = t / m; 00160 return new LoadBinAssignment(m,Gecode::IntSet(a-1,a+2), 00161 s.size(),Gecode::IntSet(0,m-1), 00162 valid ? t : -1); 00163 } 00165 virtual bool solution(const Assignment& x) const { 00166 // Loads are from 0 to m-1, after that are items 00167 // Check whether loads sum up to total size 00168 int l=0; 00169 for (int j=m; j--; ) 00170 l += x[j]; 00171 if (l != t) 00172 return false; 00173 // Compute whether items add up 00174 for (int j=m; j--; ) 00175 il[j] = 0; 00176 for (int i=s.size(); i--; ) 00177 il[x[m+i]] += s[i]; 00178 for (int j=m; j--; ) 00179 if (il[j] != x[j]) 00180 return false; 00181 return true; 00182 } 00184 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00185 using namespace Gecode; 00186 IntVarArgs l(m); 00187 IntVarArgs b(s.size()); 00188 for (int j=m; j--; ) 00189 l[j]=x[j]; 00190 for (int i=s.size(); i--; ) 00191 b[i]=x[m+i]; 00192 binpacking(home, l, b, s); 00193 } 00194 }; 00195 00197 class Create { 00198 public: 00200 Create(void) { 00201 using namespace Gecode; 00202 00203 IntArgs s1(3, 2,1,1); 00204 IntArgs s2(4, 1,2,3,4); 00205 IntArgs s3(4, 4,3,2,1); 00206 IntArgs s4(4, 1,2,4,8); 00207 IntArgs s5(4, 1,1,1,1); 00208 IntArgs s6(4, 1,1,2,2); 00209 IntArgs s7(4, 1,3,3,4); 00210 IntArgs s8(6, 1,2,4,8,16,32); 00211 00212 for (int m=1; m<4; m++) { 00213 (void) new BPT(m, s1); 00214 (void) new BPT(m, s2); 00215 (void) new BPT(m, s3); 00216 (void) new BPT(m, s4); 00217 (void) new BPT(m, s5); 00218 (void) new BPT(m, s6); 00219 (void) new BPT(m, s7); 00220 (void) new BPT(m, s8); 00221 (void) new BPT(m, s1, false); 00222 } 00223 00224 } 00225 }; 00226 00227 Create c; 00228 00230 00231 } 00232 00233 }} 00234 00235 00236 // STATISTICS: test-int 00237