Generated on Wed Jul 27 2011 15:08:51 for Gecode by doxygen 1.7.4
cumulatives.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Mikael Lagerkvist, 2005
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-05-08 12:56:03 +0200 (Sat, 08 May 2010) $ by $Author: tack $
00011  *     $Revision: 10906 $
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/search.hh>
00042 #include <gecode/scheduling.hh>
00043 
00044 #include <vector>
00045 #include <algorithm>
00046 #include <string>
00047 #include <sstream>
00048 
00049 namespace Test { namespace Int {
00050 
00052    namespace Cumulatives {
00053 
00069      class Ass : public Gecode::Space {
00070      public:
00072        Gecode::IntVarArray x;
00074        Ass(int n, const Gecode::IntSet& d) : x(*this, n, d) {
00075          using namespace Gecode;
00076          for (int i = 0; i < n; i += 4) {
00077            rel(*this, x[i+0] >= 0);
00078            rel(*this, x[i+1] >= 0);
00079            rel(*this, x[i+2] >= 0);
00080            rel(*this, x[i] + x[i+1] == x[i+2]);
00081            branch(*this, x, INT_VAR_NONE, INT_VAL_MIN);
00082          }
00083        }
00085        Ass(bool share, Ass& s) : Gecode::Space(share,s) {
00086          x.update(*this, share, s.x);
00087        }
00089        virtual Gecode::Space* copy(bool share) {
00090          return new Ass(share,*this);
00091        }
00092      };
00093 
00095      class CumulativeAssignment : public Assignment {
00097        Ass* cur;
00099        Ass* nxt;
00101        Gecode::DFS<Ass>* e;
00102      public:
00104        CumulativeAssignment(int n, const Gecode::IntSet& d) : Assignment(n,d) {
00105          Ass* a = new Ass(n, d);
00106          e = new Gecode::DFS<Ass>(a);
00107          delete a;
00108          nxt = cur = e->next();
00109          if (cur != NULL)
00110            nxt = e->next();
00111        }
00113        virtual bool operator()(void) const {
00114          return nxt != NULL;
00115        }
00117        virtual void operator++(void) {
00118          delete cur;
00119          cur = nxt;
00120          if (cur != NULL) nxt = e->next();
00121        }
00123        virtual int  operator[](int i) const {
00124          assert((i>=0) && (i<n) && (cur != NULL));
00125          return cur->x[i].val();
00126        }
00128        virtual ~CumulativeAssignment(void) {
00129          delete cur; delete nxt; delete e;
00130        }
00131      };
00132 
00134      class Event {
00135      public:
00136        int p, h; 
00137        bool start; 
00138 
00139        Event(int pos, int height, bool s) : p(pos), h(height), start(s) {}
00141        bool operator<(const Event& e) const {
00142          return p<e.p;
00143        }
00144      };
00145 
00147      class Below {
00148      public:
00149        int limit; 
00150 
00151        Below(int l) : limit(l) {}
00153        bool operator()(int val) {
00154          return val <= limit;
00155        }
00156      };
00158      class Above {
00159      public:
00160        int limit; 
00161 
00162        Above(int l) : limit(l) {}
00164        bool operator()(int val) {
00165          return val >= limit;
00166        }
00167      };
00168 
00170      template<class C>
00171      bool valid(std::vector<Event> e, C comp) {
00172        std::sort(e.begin(), e.end());
00173        unsigned int i = 0;
00174        int p = 0;
00175        int h = 0;
00176        int n = 0;
00177        while (i < e.size()) {
00178          p = e[i].p;
00179          while (i < e.size() && e[i].p == p) {
00180            h += e[i].h;
00181            n += (e[i].start ? +1 : -1);
00182            ++i;
00183          }
00184          if (n && !comp(h))
00185            return false;
00186        }
00187        return true;
00188      }
00189 
00191      class Cumulatives : public Test {
00192      protected:
00193        int ntasks;   
00194        bool at_most; 
00195        int limit;    
00196      public:
00198        Cumulatives(const std::string& s, int nt, bool am, int l)
00199          : Test("Scheduling::Cumulatives::"+s,nt*4,-1,2), ntasks(nt), at_most(am), limit(l) {
00200          testsearch = false;
00201        }
00203        virtual Assignment* assignment(void) const {
00204          assert(arity == 4*ntasks);
00205          return new CumulativeAssignment(arity, dom);
00206        }
00208        virtual bool solution(const Assignment& x) const {
00209          std::vector<Event> e;
00210          for (int i = 0; i < ntasks; ++i) {
00211            int p = i*4;
00212            // Positive start, duration and end
00213            if (x[p+0] < 0 || x[p+1] < 1 || x[p+2] < 1) return false;
00214            // Start + Duration == End
00215            if (x[p+0] + x[p+1] != x[p+2]) {
00216              return false;
00217            }
00218          }
00219          for (int i = 0; i < ntasks; ++i) {
00220            int p = i*4;
00221            // Up at start, down at end.
00222            e.push_back(Event(x[p+0], +x[p+3],  true));
00223            e.push_back(Event(x[p+2], -x[p+3], false));
00224          }
00225          if (at_most) {
00226            return valid(e, Below(limit));
00227          } else {
00228            return valid(e, Above(limit));
00229          }
00230        }
00232        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00233          using namespace Gecode;
00234          IntArgs m(ntasks), l(1, limit);
00235          IntVarArgs s(ntasks), d(ntasks), e(ntasks), h(ntasks);
00236          for (int i = 0; i < ntasks; ++i) {
00237            int p = i*4;
00238            m[i] = 0;
00239            s[i] = x[p+0]; rel(home, x[p+0], Gecode::IRT_GQ, 0);
00240            d[i] = x[p+1]; rel(home, x[p+1], Gecode::IRT_GQ, 1);
00241            e[i] = x[p+2]; rel(home, x[p+2], Gecode::IRT_GQ, 1);
00242            h[i] = x[p+3];
00243          }
00244          cumulatives(home, m, s, d, e, h, l, at_most);
00245        }
00246      };
00247 
00248      Cumulatives c1t1("1t1", 1,  true, 1);
00249      Cumulatives c1f1("1f1", 1, false, 1);
00250      Cumulatives c1t2("1t2", 1,  true, 2);
00251      Cumulatives c1f2("1f2", 1, false, 2);
00252      Cumulatives c1t3("1t3", 1,  true, 3);
00253      Cumulatives c1f3("1f3", 1, false, 3);
00254      Cumulatives c2t1("2t1", 2,  true, 1);
00255      Cumulatives c2f1("2f1", 2, false, 1);
00256      Cumulatives c2t2("2t2", 2,  true, 2);
00257      Cumulatives c2f2("2f2", 2, false, 2);
00258      Cumulatives c2t3("2t3", 2,  true, 3);
00259      Cumulatives c2f3("2f3", 2, false, 3);
00260      Cumulatives c3t1("3t1", 3,  true, 1);
00261      Cumulatives c3f1("3f1", 3, false, 1);
00262      Cumulatives c3t2("3t2", 3,  true, 2);
00263      Cumulatives c3f2("3f2", 3, false, 2);
00264      Cumulatives c3t3("3t3", 3,  true, 3);
00265      Cumulatives c3f3("3f3", 3, false, 3);
00266      Cumulatives c3t_1("3t-1", 3,  true, -1);
00267      Cumulatives c3f_1("3f-1", 3, false, -1);
00268      Cumulatives c3t_2("3t-2", 3,  true, -2);
00269      Cumulatives c3f_2("3f-2", 3, false, -2);
00270      Cumulatives c3t_3("3t-3", 3,  true, -3);
00271      Cumulatives c3f_3("3f-3", 3, false, -3);
00273 
00274    }
00275 }}
00276 
00277 // STATISTICS: test-int