Generated on Fri May 13 2011 22:41:21 for Gecode by doxygen 1.7.1

cumulative.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 Cumulative {
00047 
00053 
00054     class ManFixPCumulative : public Test {
00055     protected:
00057       int c;
00059       Gecode::IntArgs p;
00061       Gecode::IntArgs u;
00063       static int st(int c, 
00064                     const Gecode::IntArgs& p, const Gecode::IntArgs& u) {
00065         double e = 0;
00066         for (int i=p.size(); i--; )
00067           e += static_cast<double>(p[i])*u[i];
00068         return e / c;
00069       }
00071       int o;
00072     public:
00074       ManFixPCumulative(int c0, 
00075                        const Gecode::IntArgs& p0,
00076                        const Gecode::IntArgs& u0,
00077                        int o0)
00078         : Test("Scheduling::Cumulative::Man::Fix::"+str(o0)+"::"+
00079                str(c0)+"::"+str(p0)+"::"+str(u0),
00080                p0.size(),o0,o0+st(c0,p0,u0)), 
00081           c(c0), p(p0), u(u0), o(o0) {
00082         testsearch = false;
00083         testfix = false;
00084         contest = CTL_NONE;
00085       }
00087       virtual Assignment* assignment(void) const {
00088         return new RandomAssignment(arity,dom,500);
00089       }
00091       virtual bool solution(const Assignment& x) const {
00092         // Compute maximal time
00093         int t = 0;
00094         for (int i=0; i<x.size(); i++)
00095           t = std::max(t,x[i]-o+std::max(1,p[i]));
00096         // Compute resource usage (including at start times)
00097         int* used = new int[t];
00098         for (int i=0; i<t; i++)
00099           used[i] = 0;
00100         for (int i=0; i<x.size(); i++)
00101           for (int t=0; t<p[i]; t++)
00102             used[x[i]-o+t] += u[i];
00103         // Check resource usage
00104         for (int i=0; i<t; i++)
00105           if (used[i] > c) {
00106             delete [] used;
00107             return false;
00108           }
00109         // Compute resource usage (only internal)
00110         for (int i=0; i<t; i++)
00111           used[i] = 0;
00112         for (int i=0; i<x.size(); i++) {
00113           for (int t=1; t<p[i]; t++) {
00114             used[x[i]-o+t] += u[i];
00115           }
00116         }
00117         // Check resource usage at start times
00118         for (int i=0; i<x.size(); i++)
00119           if (used[x[i]-o]+u[i] > c) {
00120             delete [] used;
00121             return false;
00122           }
00123         delete [] used;
00124         return true;
00125       }
00127       virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00128         Gecode::cumulative(home, c, x, p, u);
00129       }
00130     };
00131 
00132 
00134     class OptFixPCumulative : public Test {
00135     protected:
00137       int c;
00139       Gecode::IntArgs p;
00141       Gecode::IntArgs u;
00143       int l;
00145       int o;
00147       static int st(int c, 
00148                     const Gecode::IntArgs& p, const Gecode::IntArgs& u) {
00149         double e = 0;
00150         for (int i=p.size(); i--; )
00151           e += static_cast<double>(p[i])*u[i];
00152         return e / c;
00153       }
00154     public:
00156       OptFixPCumulative(int c0, 
00157                        const Gecode::IntArgs& p0,
00158                        const Gecode::IntArgs& u0,
00159                        int o0)
00160         : Test("Scheduling::Cumulative::Opt::Fix::"+str(o0)+"::"+
00161                str(c0)+"::"+str(p0)+"::"+str(u0),
00162                2*p0.size(),o0,o0+st(c0,p0,u0)), 
00163           c(c0), p(p0), u(u0), l(o0+st(c,p,u)/2), o(o0) {
00164         testsearch = false;
00165         testfix = false;
00166         contest = CTL_NONE;
00167       }
00169       virtual Assignment* assignment(void) const {
00170         return new RandomAssignment(arity,dom,500);
00171       }
00173       virtual bool solution(const Assignment& x) const {
00174         int n = x.size() / 2;
00175         // Compute maximal time
00176         int t = 0;
00177         for (int i=0; i<n; i++)
00178           t = std::max(t,x[i]-o+std::max(1,p[i]));
00179         // Compute resource usage (including at start times)
00180         int* used = new int[t];
00181         for (int i=0; i<t; i++)
00182           used[i] = 0;
00183         for (int i=0; i<n; i++)
00184           if (x[n+i] > l)
00185             for (int t=0; t<p[i]; t++)
00186               used[x[i]-o+t] += u[i];
00187         // Check resource usage
00188         for (int i=0; i<t; i++) {
00189           if (used[i] > c) {
00190             delete [] used;
00191             return false;
00192           }
00193         }
00194         // Compute resource usage (only internal)
00195         for (int i=0; i<t; i++)
00196           used[i] = 0;
00197         for (int i=0; i<n; i++)
00198           if (x[n+i] > l) {
00199             for (int t=1; t<p[i]; t++)
00200               used[x[i]-o+t] += u[i];
00201           }
00202         // Check resource usage at start times
00203         for (int i=0; i<n; i++)
00204           if (x[n+i] > l)
00205             if (used[x[i]-o]+u[i] > c) {
00206               delete [] used;
00207               return false;
00208             }
00209         delete [] used;
00210         return true;
00211       }
00213       virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00214         int n=x.size() / 2;
00215         Gecode::IntVarArgs s(n);
00216         Gecode::BoolVarArgs m(n);
00217         for (int i=0; i<n; i++) {
00218           s[i]=x[i];
00219           m[i]=Gecode::expr(home, x[n+i] > l);
00220         }
00221         Gecode::cumulative(home, c, s, p, u, m);
00222       }
00223     };
00224 
00226     class ManFlexCumulative : public Test {
00227     protected:
00229       int c;
00231       int _minP;
00233       int _maxP;
00235       Gecode::IntArgs u;
00237       static int st(int c, int maxP, const Gecode::IntArgs& u) {
00238         double e = 0;
00239         for (int i=u.size(); i--; )
00240           e += static_cast<double>(maxP)*u[i];
00241         return e / c;
00242       }
00244       int o;
00245     public:
00247       ManFlexCumulative(int c0, int minP, int maxP,
00248                        const Gecode::IntArgs& u0,
00249                        int o0)
00250         : Test("Scheduling::Cumulative::Man::Flex::"+str(o0)+"::"+
00251                str(c0)+"::"+str(minP)+"::"+str(maxP)+"::"+str(u0),
00252                2*u0.size(),0,std::max(maxP,st(c0,maxP,u0))), 
00253           c(c0), _minP(minP), _maxP(maxP), u(u0), o(o0) {
00254         testsearch = false;
00255         testfix = false;
00256         contest = CTL_NONE;
00257       }
00259       virtual Assignment* assignment(void) const {
00260         return new RandomMixAssignment(arity/2,dom,arity/2,
00261                                        Gecode::IntSet(_minP,_maxP),500);
00262       }
00264       virtual bool solution(const Assignment& x) const {
00265         int n = x.size()/2;
00266         // Compute maximal time
00267         int t = 0;
00268         for (int i=0; i<n; i++) {
00269           t = std::max(t,x[i]+std::max(1,x[n+i]));
00270         }
00271         // Compute resource usage (including at start times)
00272         int* used = new int[t];
00273         for (int i=0; i<t; i++)
00274           used[i] = 0;
00275         for (int i=0; i<n; i++)
00276           for (int t=0; t<x[n+i]; t++)
00277             used[x[i]+t] += u[i];
00278         // Check resource usage
00279         for (int i=0; i<t; i++)
00280           if (used[i] > c) {
00281             delete [] used;
00282             return false;
00283           }
00284         // Compute resource usage (only internal)
00285         for (int i=0; i<t; i++)
00286           used[i] = 0;
00287         for (int i=0; i<n; i++) {
00288           for (int t=1; t<x[n+i]; t++)
00289             used[x[i]+t] += u[i];
00290         }
00291         // Check resource usage at start times
00292         for (int i=0; i<n; i++)
00293           if (used[x[i]]+u[i] > c) {
00294             delete [] used;
00295             return false;
00296           }
00297         delete [] used;
00298         return true;
00299       }
00301       virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00302         Gecode::IntVarArgs s(x.size()/2);
00303         Gecode::IntVarArgs px(x.slice(x.size()/2));
00304         Gecode::IntVarArgs e(home,x.size()/2,
00305                              Gecode::Int::Limits::min,
00306                              Gecode::Int::Limits::max);
00307         for (int i=s.size(); i--;) {
00308           s[i] = expr(home, o+x[i]);
00309           rel(home, s[i]+px[i] == e[i]);
00310           rel(home, _minP <= px[i]);
00311           rel(home, _maxP >= px[i]);
00312         }
00313         Gecode::cumulative(home, c, s, px, e, u);
00314       }
00315     };
00316 
00318     class OptFlexCumulative : public Test {
00319     protected:
00321       int c;
00323       int _minP;
00325       int _maxP;
00327       Gecode::IntArgs u;
00329       int l;
00331       int o;
00333       static int st(int c, int maxP, const Gecode::IntArgs& u) {
00334         double e = 0;
00335         for (int i=u.size(); i--; )
00336           e += static_cast<double>(maxP)*u[i];
00337         return e / c;
00338       }
00339     public:
00341       OptFlexCumulative(int c0, int minP, int maxP,
00342                         const Gecode::IntArgs& u0,
00343                         int o0)
00344         : Test("Scheduling::Cumulative::Opt::Flex::"+str(o0)+"::"+
00345                str(c0)+"::"+str(minP)+"::"+str(maxP)+"::"+str(u0),
00346                3*u0.size(),0,std::max(maxP,st(c0,maxP,u0))), 
00347           c(c0), _minP(minP), _maxP(maxP), u(u0), 
00348           l(std::max(maxP,st(c0,maxP,u0))/2), o(o0) {
00349         testsearch = false;
00350         testfix = false;
00351         contest = CTL_NONE;
00352       }
00354       virtual Assignment* assignment(void) const {
00355         return new RandomMixAssignment(2*(arity/3),dom,arity/3,
00356                                        Gecode::IntSet(_minP,_maxP),500);
00357       }
00359       virtual bool solution(const Assignment& x) const {
00360         int n = x.size() / 3;
00361         // Compute maximal time
00362         int t = 0;
00363         for (int i=0; i<n; i++)
00364           t = std::max(t,x[i]+std::max(1,x[2*n+i]));
00365         // Compute resource usage (including at start times)
00366         int* used = new int[t];
00367         for (int i=0; i<t; i++)
00368           used[i] = 0;
00369         for (int i=0; i<n; i++)
00370           if (x[n+i] > l)
00371             for (int t=0; t<x[2*n+i]; t++)
00372               used[x[i]+t] += u[i];
00373         // Check resource usage
00374         for (int i=0; i<t; i++)
00375           if (used[i] > c) {
00376             delete [] used;
00377             return false;
00378           }
00379         // Compute resource usage (only internal)
00380         for (int i=0; i<t; i++)
00381           used[i] = 0;
00382         for (int i=0; i<n; i++)
00383           if (x[n+i] > l)
00384             for (int t=1; t<x[2*n+i]; t++)
00385               used[x[i]+t] += u[i];
00386         // Check resource usage at start times
00387         for (int i=0; i<n; i++)
00388           if (x[n+i] > l && used[x[i]]+u[i] > c) {
00389             delete [] used;
00390             return false;
00391           }
00392         delete [] used;
00393         return true;
00394       }
00396       virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00397         int n=x.size() / 3;
00398 
00399         Gecode::IntVarArgs s(n);
00400         Gecode::IntVarArgs px(n);
00401         Gecode::IntVarArgs e(home,n,
00402                              Gecode::Int::Limits::min,
00403                              Gecode::Int::Limits::max);
00404         for (int i=n; i--;) {
00405           s[i] = expr(home, o+x[i]);
00406           px[i] = x[2*n+i];
00407           rel(home, s[i]+px[i] == e[i]);
00408           rel(home, _minP <= px[i]);
00409           rel(home, _maxP >= px[i]);
00410         }
00411         Gecode::BoolVarArgs m(n);
00412         for (int i=0; i<n; i++)
00413           m[i]=Gecode::expr(home, (x[n+i] > l));
00414         Gecode::cumulative(home, c, s, px, e, u, m);
00415       }
00416     };
00417 
00419     class Create {
00420     public:
00422       Create(void) {
00423         using namespace Gecode;
00424         IntArgs p1(4, 1,1,1,1);
00425         IntArgs p2(4, 2,2,2,2);
00426         IntArgs p3(4, 4,3,3,5);
00427         IntArgs p4(4, 4,0,3,5);
00428 
00429         IntArgs u1(4, 1,1,1,1);
00430         IntArgs u2(4, 2,2,2,2);
00431         IntArgs u3(4, 2,3,4,5);
00432 
00433         for (int c=1; c<8; c++) {
00434           int off = 0;
00435           for (int coff=0; coff<2; coff++) {
00436             (void) new ManFixPCumulative(c,p1,u1,off);
00437             (void) new ManFixPCumulative(c,p1,u2,off);
00438             (void) new ManFixPCumulative(c,p1,u3,off);
00439             (void) new ManFixPCumulative(c,p2,u1,off);
00440             (void) new ManFixPCumulative(c,p2,u2,off);
00441             (void) new ManFixPCumulative(c,p2,u3,off);
00442             (void) new ManFixPCumulative(c,p3,u1,off);
00443             (void) new ManFixPCumulative(c,p3,u2,off);
00444             (void) new ManFixPCumulative(c,p3,u3,off);
00445             (void) new ManFixPCumulative(c,p4,u1,off);
00446             (void) new ManFixPCumulative(c,p4,u2,off);
00447             (void) new ManFixPCumulative(c,p4,u3,off);
00448 
00449             (void) new ManFlexCumulative(c,0,1,u1,off);
00450             (void) new ManFlexCumulative(c,0,1,u2,off);
00451             (void) new ManFlexCumulative(c,0,1,u3,off);
00452             (void) new ManFlexCumulative(c,0,2,u1,off);
00453             (void) new ManFlexCumulative(c,0,2,u2,off);
00454             (void) new ManFlexCumulative(c,0,2,u3,off);
00455             (void) new ManFlexCumulative(c,3,5,u1,off);
00456             (void) new ManFlexCumulative(c,3,5,u2,off);
00457             (void) new ManFlexCumulative(c,3,5,u3,off);
00458 
00459             (void) new OptFixPCumulative(c,p1,u1,off);
00460             (void) new OptFixPCumulative(c,p1,u2,off);
00461             (void) new OptFixPCumulative(c,p1,u3,off);
00462             (void) new OptFixPCumulative(c,p2,u1,off);
00463             (void) new OptFixPCumulative(c,p2,u2,off);
00464             (void) new OptFixPCumulative(c,p2,u3,off);
00465             (void) new OptFixPCumulative(c,p3,u1,off);
00466             (void) new OptFixPCumulative(c,p3,u2,off);
00467             (void) new OptFixPCumulative(c,p3,u3,off);
00468             (void) new OptFixPCumulative(c,p4,u1,off);
00469             (void) new OptFixPCumulative(c,p4,u2,off);
00470             (void) new OptFixPCumulative(c,p4,u3,off);
00471             
00472             (void) new OptFlexCumulative(c,0,1,u1,off);
00473             (void) new OptFlexCumulative(c,0,1,u2,off);
00474             (void) new OptFlexCumulative(c,0,1,u3,off);
00475             (void) new OptFlexCumulative(c,0,2,u1,off);
00476             (void) new OptFlexCumulative(c,0,2,u2,off);
00477             (void) new OptFlexCumulative(c,0,2,u3,off);
00478             (void) new OptFlexCumulative(c,3,5,u1,off);
00479             (void) new OptFlexCumulative(c,3,5,u2,off);
00480             (void) new OptFlexCumulative(c,3,5,u3,off);
00481 
00482             off = Gecode::Int::Limits::min;
00483           }
00484         }
00485       }
00486     };
00487 
00488     Create c;
00490 
00491   }
00492 }}
00493 
00494 // STATISTICS: test-int