unary.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, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-08 13:04:57 +0200 (Tue, 08 Jun 2010) $ by $Author: tack $ 00011 * $Revision: 11058 $ 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 <gecode/scheduling.hh> 00042 00043 namespace Test { namespace Int { 00044 00046 namespace Unary { 00047 00053 00054 class ManFixPUnary : public Test { 00055 protected: 00057 Gecode::IntArgs p; 00059 static int st(const Gecode::IntArgs& p) { 00060 int t = 0; 00061 for (int i=p.size(); i--; ) 00062 t += p[i]; 00063 return t; 00064 } 00065 public: 00067 ManFixPUnary(const Gecode::IntArgs& p0, int o) 00068 : Test("Scheduling::Unary::Man::Fix::"+str(o)+"::"+str(p0), 00069 p0.size(),o,o+st(p0)), 00070 p(p0) { 00071 testsearch = false; 00072 contest = CTL_NONE; 00073 } 00075 virtual Assignment* assignment(void) const { 00076 return new RandomAssignment(arity,dom,500); 00077 } 00079 virtual bool solution(const Assignment& x) const { 00080 for (int i=0; i<x.size(); i++) 00081 for (int j=i+1; j<x.size(); j++) 00082 if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i])) 00083 return false; 00084 return true; 00085 } 00087 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00088 Gecode::unary(home, x, p); 00089 } 00090 }; 00091 00093 class OptFixPUnary : public Test { 00094 protected: 00096 Gecode::IntArgs p; 00098 int l; 00100 static int st(const Gecode::IntArgs& p) { 00101 int t = 0; 00102 for (int i=p.size(); i--; ) 00103 t += p[i]; 00104 return t; 00105 } 00106 public: 00108 OptFixPUnary(const Gecode::IntArgs& p0, int o) 00109 : Test("Scheduling::Unary::Opt::Fix::"+str(o)+"::"+str(p0), 00110 2*p0.size(),o,o+st(p0)), p(p0), l(o+st(p)/2) { 00111 testsearch = false; 00112 contest = CTL_NONE; 00113 } 00115 virtual Assignment* assignment(void) const { 00116 return new RandomAssignment(arity,dom,500); 00117 } 00119 virtual bool solution(const Assignment& x) const { 00120 int n = x.size() / 2; 00121 for (int i=0; i<n; i++) 00122 if (x[n+i] > l) 00123 for (int j=i+1; j<n; j++) 00124 if(x[n+j] > l) 00125 if ((x[i]+p[i] > x[j]) && (x[j]+p[j] > x[i])) 00126 return false; 00127 return true; 00128 } 00130 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00131 int n=x.size() / 2; 00132 Gecode::IntVarArgs s(n); 00133 Gecode::BoolVarArgs m(n); 00134 for (int i=0; i<n; i++) { 00135 s[i]=x[i]; 00136 m[i]=Gecode::expr(home, (x[n+i] > l)); 00137 } 00138 Gecode::unary(home, s, p, m); 00139 } 00140 }; 00141 00142 00144 class ManFlexUnary : public Test { 00145 protected: 00147 int _minP; 00149 int _maxP; 00151 int off; 00152 public: 00154 ManFlexUnary(int n, int minP, int maxP, int o) 00155 : Test("Scheduling::Unary::Man::Flex::"+str(o)+"::"+str(n)+"::" 00156 +str(minP)+"::"+str(maxP), 00157 2*n,0,n*maxP), _minP(minP), _maxP(maxP), off(o) { 00158 testsearch = false; 00159 testfix = false; 00160 contest = CTL_NONE; 00161 } 00163 virtual Assignment* assignment(void) const { 00164 return new RandomMixAssignment(arity/2,dom,arity/2, 00165 Gecode::IntSet(_minP,_maxP),500); 00166 } 00168 virtual bool solution(const Assignment& x) const { 00169 int n = x.size()/2; 00170 for (int i=0; i<n; i++) 00171 for (int j=i+1; j<n; j++) 00172 if ((x[i]+x[n+i] > x[j]) && (x[j]+x[n+j] > x[i])) 00173 return false; 00174 return true; 00175 } 00177 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00178 Gecode::IntVarArgs s(x.size()/2); 00179 Gecode::IntVarArgs px(x.slice(x.size()/2)); 00180 Gecode::IntVarArgs e(home,x.size()/2, 00181 Gecode::Int::Limits::min, 00182 Gecode::Int::Limits::max); 00183 for (int i=s.size(); i--;) { 00184 s[i] = expr(home, off+x[i]); 00185 rel(home, s[i]+px[i] == e[i]); 00186 rel(home, _minP <= px[i]); 00187 rel(home, _maxP >= px[i]); 00188 } 00189 Gecode::unary(home, s, px, e); 00190 } 00191 }; 00192 00194 class OptFlexUnary : public Test { 00195 protected: 00197 int _minP; 00199 int _maxP; 00201 int off; 00203 int l; 00205 static int st(const Gecode::IntArgs& p) { 00206 int t = 0; 00207 for (int i=p.size(); i--; ) 00208 t += p[i]; 00209 return t; 00210 } 00211 public: 00213 OptFlexUnary(int n, int minP, int maxP, int o) 00214 : Test("Scheduling::Unary::Opt::Flex::"+str(o)+"::"+str(n)+"::" 00215 +str(minP)+"::"+str(maxP), 00216 3*n,0,n*maxP), _minP(minP), _maxP(maxP), off(o), 00217 l(n*maxP/2) { 00218 testsearch = false; 00219 testfix = false; 00220 contest = CTL_NONE; 00221 } 00223 virtual Assignment* assignment(void) const { 00224 return new RandomMixAssignment(2*(arity/3),dom,arity/3, 00225 Gecode::IntSet(_minP,_maxP),500); 00226 } 00228 virtual bool solution(const Assignment& x) const { 00229 int n = x.size() / 3; 00230 for (int i=0; i<n; i++) 00231 if (x[n+i] > l) 00232 for (int j=i+1; j<n; j++) 00233 if(x[n+j] > l) 00234 if ((x[i]+x[2*n+i] > x[j]) && (x[j]+x[2*n+j] > x[i])) 00235 return false; 00236 return true; 00237 } 00239 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) { 00240 int n=x.size() / 3; 00241 00242 Gecode::IntVarArgs s(n); 00243 Gecode::IntVarArgs px(n); 00244 Gecode::IntVarArgs e(home,n, 00245 Gecode::Int::Limits::min, 00246 Gecode::Int::Limits::max); 00247 for (int i=n; i--;) { 00248 s[i] = expr(home, off+x[i]); 00249 px[i] = x[2*n+i]; 00250 rel(home, s[i]+px[i] == e[i]); 00251 rel(home, _minP <= px[i]); 00252 rel(home, _maxP >= px[i]); 00253 } 00254 Gecode::BoolVarArgs m(n); 00255 for (int i=0; i<n; i++) 00256 m[i]=Gecode::expr(home, (x[n+i] > l)); 00257 Gecode::unary(home, s, px, e, m); 00258 } 00259 }; 00260 00261 Gecode::IntArgs p1(4, 2,2,2,2); 00262 ManFixPUnary mfu10(p1,0); 00263 ManFixPUnary mfu1i(p1,Gecode::Int::Limits::min); 00264 OptFixPUnary ofu10(p1,0); 00265 OptFixPUnary ofu1i(p1,Gecode::Int::Limits::min); 00266 ManFlexUnary mflu10(4,0,2,0); 00267 ManFlexUnary mflu1i(4,0,2,Gecode::Int::Limits::min); 00268 ManFlexUnary mflu101(4,1,3,0); 00269 ManFlexUnary mflu1i1(4,1,3,Gecode::Int::Limits::min); 00270 OptFlexUnary oflu10(4,0,2,0); 00271 OptFlexUnary oflu1i(4,0,2,Gecode::Int::Limits::min); 00272 00273 Gecode::IntArgs p10(5, 2,2,0,2,2); 00274 ManFixPUnary mfu010(p10,0); 00275 ManFixPUnary mfu01i(p10,Gecode::Int::Limits::min); 00276 OptFixPUnary ofu010(p10,0); 00277 OptFixPUnary ofu01i(p10,Gecode::Int::Limits::min); 00278 ManFlexUnary mflu010(5,0,2,0); 00279 ManFlexUnary mflu01i(5,0,2,Gecode::Int::Limits::min); 00280 OptFlexUnary oflu010(5,0,2,0); 00281 OptFlexUnary oflu01i(5,0,2,Gecode::Int::Limits::min); 00282 00283 Gecode::IntArgs p2(4, 4,3,3,5); 00284 ManFixPUnary mfu20(p2,0); 00285 ManFixPUnary mfu2i(p2,Gecode::Int::Limits::min); 00286 OptFixPUnary ofu20(p2,0); 00287 OptFixPUnary ofu2i(p2,Gecode::Int::Limits::min); 00288 ManFlexUnary mflu20(4,3,5,0); 00289 ManFlexUnary mflu2i(4,3,5,Gecode::Int::Limits::min); 00290 OptFlexUnary oflu20(4,3,5,0); 00291 OptFlexUnary oflu2i(4,3,5,Gecode::Int::Limits::min); 00292 00293 Gecode::IntArgs p20(6, 4,0,3,3,0,5); 00294 ManFixPUnary mfu020(p20,0); 00295 ManFixPUnary mfu02i(p20,Gecode::Int::Limits::min); 00296 OptFixPUnary ofu020(p20,0); 00297 OptFixPUnary ofu02i(p20,Gecode::Int::Limits::min); 00298 ManFlexUnary mflu020(6,0,5,0); 00299 ManFlexUnary mflu02i(6,0,5,Gecode::Int::Limits::min); 00300 OptFlexUnary oflu020(6,0,5,0); 00301 OptFlexUnary oflu02i(6,0,5,Gecode::Int::Limits::min); 00302 00303 Gecode::IntArgs p3(6, 4,2,9,3,7,5); 00304 ManFixPUnary mfu30(p3,0); 00305 ManFixPUnary mfu3i(p3,Gecode::Int::Limits::min); 00306 OptFixPUnary ofu30(p3,0); 00307 OptFixPUnary ofu3i(p3,Gecode::Int::Limits::min); 00308 ManFlexUnary mflu30(6,2,7,0); 00309 ManFlexUnary mflu3i(6,2,7,Gecode::Int::Limits::min); 00310 OptFlexUnary oflu30(6,2,7,0); 00311 OptFlexUnary oflu3i(6,2,7,Gecode::Int::Limits::min); 00312 00313 Gecode::IntArgs p30(8, 4,0,2,9,3,7,5,0); 00314 ManFixPUnary mfu030(p30,0); 00315 ManFixPUnary mfu03i(p30,Gecode::Int::Limits::min); 00316 OptFixPUnary ofu030(p30,0); 00317 OptFixPUnary ofu03i(p30,Gecode::Int::Limits::min); 00318 ManFlexUnary mflu030(8,0,9,0); 00319 ManFlexUnary mflu03i(8,0,9,Gecode::Int::Limits::min); 00320 OptFlexUnary oflu030(8,0,9,0); 00321 OptFlexUnary oflu03i(8,0,9,Gecode::Int::Limits::min); 00322 00324 00325 } 00326 }} 00327 00328 // STATISTICS: test-int