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

val.hpp

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <algorithm>
00035 
00036 /*
00037  * This is the propagation algorithm of the cumulatives constraint as
00038  * presented in:
00039  *   Nicolas Beldiceanu and Mats Carlsson, A New Multi-resource cumulatives
00040  *   Constraint with Negative Heights. CP 2002, pages 63-79, Springer-Verlag.
00041  */
00042 
00043 namespace Gecode { namespace Int { namespace Cumulatives {
00044 
00045   template<class ViewM, class ViewP, class ViewU, class View>
00046   forceinline
00047   Val<ViewM,ViewP,ViewU,View>::Val(Home home,
00048                                    const ViewArray<ViewM>& _m,
00049                                    const ViewArray<View>& _s,
00050                                    const ViewArray<ViewP>& _p,
00051                                    const ViewArray<View>& _e,
00052                                    const ViewArray<ViewU>& _u,
00053                                    const SharedArray<int>& _c,
00054                                    bool _at_most) :
00055     Propagator(home),
00056     m(_m), s(_s), p(_p), e(_e), u(_u), c(_c), at_most(_at_most) {
00057     home.notice(*this,AP_DISPOSE);
00058 
00059     m.subscribe(home,*this,Int::PC_INT_DOM);
00060     s.subscribe(home,*this,Int::PC_INT_BND);
00061     p.subscribe(home,*this,Int::PC_INT_BND);
00062     e.subscribe(home,*this,Int::PC_INT_BND);
00063     u.subscribe(home,*this,Int::PC_INT_BND);
00064   }
00065 
00066   template<class ViewM, class ViewP, class ViewU, class View>
00067   ExecStatus
00068   Val<ViewM,ViewP,ViewU,View>
00069   ::post(Home home, const ViewArray<ViewM>& m,
00070          const ViewArray<View>& s, const ViewArray<ViewP>& p,
00071          const ViewArray<View>& e, const ViewArray<ViewU>& u,
00072          const SharedArray<int>& c, bool at_most) {
00073     (void) new (home) Val(home, m,s,p,e,u,c,at_most);
00074     return ES_OK;
00075   }
00076 
00077   template<class ViewM, class ViewP, class ViewU, class View>
00078   forceinline
00079   Val<ViewM,ViewP,ViewU,View>::Val(Space& home,
00080                                    Val<ViewM,ViewP,ViewU,View>& vp)
00081     : Propagator(home,vp), c(vp.c), at_most(vp.at_most) {
00082     m.update(home,vp.m);
00083     s.update(home, vp.s);
00084     p.update(home, vp.p);
00085     e.update(home, vp.e);
00086     u.update(home, vp.u);
00087   }
00088 
00089   template<class ViewM, class ViewP, class ViewU, class View>
00090   size_t
00091   Val<ViewM,ViewP,ViewU,View>::dispose(Space& home) {
00092     home.ignore(*this,AP_DISPOSE);
00093     if (!home.failed()) {
00094       m.cancel(home,*this,Int::PC_INT_DOM);
00095       s.cancel(home,*this,Int::PC_INT_BND);
00096       p.cancel(home,*this,Int::PC_INT_BND);
00097       e.cancel(home,*this,Int::PC_INT_BND);
00098       u.cancel(home,*this,Int::PC_INT_BND);
00099     }
00100     c.~SharedArray();
00101     (void) Propagator::dispose(home);
00102     return sizeof(*this);
00103   }
00104 
00105   template<class ViewM, class ViewP, class ViewU, class View>
00106   PropCost
00107   Val<ViewM,ViewP,ViewU,View>::cost(const Space&, const ModEventDelta&) const {
00108     return PropCost::quadratic(PropCost::LO, s.size());
00109   }
00110 
00111   template<class ViewM, class ViewP, class ViewU, class View>
00112   void
00113   Val<ViewM,ViewP,ViewU,View>::reschedule(Space& home) {
00114     m.reschedule(home,*this,Int::PC_INT_DOM);
00115     s.reschedule(home,*this,Int::PC_INT_BND);
00116     p.reschedule(home,*this,Int::PC_INT_BND);
00117     e.reschedule(home,*this,Int::PC_INT_BND);
00118     u.reschedule(home,*this,Int::PC_INT_BND);
00119   }
00120 
00121   template<class ViewM, class ViewP, class ViewU, class View>
00122   Actor*
00123   Val<ViewM,ViewP,ViewU,View>::copy(Space& home) {
00124     return new (home) Val<ViewM,ViewP,ViewU,View>(home,*this);
00125   }
00126 
00128   typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
00130   class Event
00131   {
00132   public:
00134     ev_t e;
00136     int task;
00138     int date;
00140     int inc;
00145     bool first_prof;
00146 
00148     Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
00149       : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
00150     {}
00151 
00152     // Default constructor for region-allocated memory
00153     Event(void) {}
00154 
00156     bool operator <(const Event& ev) const {
00157       if (date == ev.date) {
00158         if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
00159         if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
00160         return false;
00161       }
00162       return date < ev.date;
00163     }
00164   };
00165 
00166   template<class ViewM, class ViewP, class ViewU, class View>
00167   ExecStatus
00168   Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
00169                                      int ntask, int su,
00170                                      int* contribution,
00171                                      int* prune_tasks, int& prune_tasks_size) {
00172 
00173     if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
00174       return ES_FAILED;
00175     }
00176 
00177     int pti = 0;
00178     while (pti != prune_tasks_size) {
00179       int t = prune_tasks[pti];
00180 
00181       // Algorithm 2.
00182       // Prune the machine, start, and end for required
00183       // tasks for machine r that have heights possibly greater than 0.
00184       if (ntask != 0 &&
00185           (at_most ? u[t].min() < 0
00186            : u[t].max() > 0) &&
00187           (at_most ? su-contribution[t] > c[r]
00188            : su-contribution[t] < c[r])) {
00189         if (me_failed(m[t].eq(home, r))||
00190             me_failed(s[t].gq(home, up-p[t].max()+1))||
00191             me_failed(s[t].lq(home, low))||
00192             me_failed(e[t].lq(home,low+p[t].max()))||
00193             me_failed(e[t].gq(home, up+1))||
00194             me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
00195             ) {
00196           return ES_FAILED;
00197         }
00198       }
00199 
00200       // Algorithm 3.
00201       // Remove values that prevent us from reaching the limit
00202       if (at_most ? u[t].min() > std::min(0, c[r])
00203           : u[t].max() < std::max(0, c[r])) {
00204         if (at_most ? su-contribution[t]+u[t].min() > c[r]
00205             : su-contribution[t]+u[t].max() < c[r]) {
00206           if (e[t].min() > low  &&
00207               s[t].max() <= up &&
00208               p[t].min() > 0) {
00209             if (me_failed(m[t].nq(home, r))) {
00210               return ES_FAILED;
00211             }
00212           } else if (m[t].assigned()) {
00213             int ptmin = p[t].min();
00214             if (ptmin > 0) {
00215               Iter::Ranges::Singleton
00216                 a(low-ptmin+1, up), b(low+1, up+ptmin);
00217               if (me_failed(s[t].minus_r(home,a,false)) ||
00218                   me_failed(e[t].minus_r(home, b,false)))
00219                 return ES_FAILED;
00220             }
00221             if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
00222                                                          e[t].max()-up-1),
00223                                                 0)))) {
00224               return ES_FAILED;
00225             }
00226           }
00227         }
00228       }
00229 
00230       // Algorithm 4.
00231       // Remove bad negative values from for-sure heights.
00232       /* \note "It is not sufficient to only test for assignment of machine[t]
00233        *         since Algorithm 3 can remove the value." Check this against
00234        *         the conditions for Alg3.
00235        */
00236       if (m[t].assigned() &&
00237           m[t].val() == r &&
00238           e[t].min() > low    &&
00239           s[t].max() <= up  &&
00240           p[t].min() > 0 ) {
00241         if (me_failed(at_most
00242                       ? u[t].lq(home, c[r]-su+contribution[t])
00243                       : u[t].gq(home, c[r]-su+contribution[t]))) {
00244           return ES_FAILED;
00245         }
00246       }
00247 
00248       // Remove tasks that are no longer relevant.
00249       if (!m[t].in(r) || (e[t].max() <= up+1)) {
00250         prune_tasks[pti] = prune_tasks[--prune_tasks_size];
00251       } else {
00252         ++pti;
00253       }
00254     }
00255 
00256     return ES_OK;
00257   }
00258 
00259   namespace {
00260     template<class C>
00261     class Less {
00262     public:
00263       bool operator ()(const C& lhs, const C& rhs) {
00264         return lhs < rhs;
00265       }
00266     };
00267   }
00268 
00269   template<class ViewM, class ViewP, class ViewU, class View>
00270   ExecStatus
00271   Val<ViewM,ViewP,ViewU,View>::propagate(Space& home, const ModEventDelta&) {
00272     // Check for subsumption
00273     bool subsumed = true;
00274     for (int t=0; t<s.size(); t++)
00275       if (!(p[t].assigned() && e[t].assigned()   &&
00276             m[t].assigned()  && s[t].assigned() &&
00277             u[t].assigned())) {
00278         subsumed = false;
00279         break;
00280       }
00281     // Propagate information for machine r
00282     Region region;
00283     Event *events = region.alloc<Event>(s.size()*8);
00284     int  events_size;
00285     int *prune_tasks = region.alloc<int>(s.size());
00286     int  prune_tasks_size;
00287     int *contribution = region.alloc<int>(s.size());
00288     for (int r = c.size(); r--; ) {
00289       events_size = 0;
00290 #define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8);     \
00291         events[events_size++] = E
00292 
00293       // Find events for sweep-line
00294       for (int t = s.size(); t--; ) {
00295         if (m[t].assigned() &&
00296             m[t].val() == r &&
00297             s[t].max() < e[t].min()) {
00298           if (at_most
00299               ? u[t].min() > std::min(0, c[r])
00300               : u[t].max() < std::max(0, c[r])) {
00301             GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, s[t].max(), 1));
00302             GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, e[t].min(), -1));
00303           }
00304           if (at_most
00305               ? u[t].min() > 0
00306               : u[t].max() < 0) {
00307             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].max(),
00308                                      at_most ? u[t].min() : u[t].max(), true));
00309             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].min(),
00310                                      at_most ? -u[t].min() : -u[t].max()));
00311           }
00312         }
00313 
00314         if (m[t].in(r)) {
00315           if (at_most
00316               ? u[t].min() < 0
00317               : u[t].max() > 0) {
00318             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].min(),
00319                                      at_most ? u[t].min() : u[t].max(), true));
00320             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].max(),
00321                                      at_most ? -u[t].min() : -u[t].max()));
00322           }
00323           if (!(m[t].assigned() &&
00324                 u[t].assigned() &&
00325                 s[t].assigned() &&
00326                 e[t].assigned())) {
00327             GECODE_PUSH_EVENTS(Event(EVENT_PRUN, t, s[t].min()));
00328           }
00329         }
00330       }
00331 #undef GECODE_PUSH_EVENTS
00332 
00333       // If there are no events, continue with next machine
00334       if (events_size == 0) {
00335         continue;
00336       }
00337 
00338       // Sort the events according to date
00339       Less<Event> less;
00340       Support::insertion(&events[0], events_size, less);
00341 
00342       // Sweep line along d, starting at 0
00343       int d        = 0;
00344       int ntask    = 0;
00345       int su  = 0;
00346       int ei = 0;
00347 
00348       prune_tasks_size = 0;
00349       for (int i = s.size(); i--; ) contribution[i] = 0;
00350 
00351       d = events[ei].date;
00352       while (ei < events_size) {
00353         if (events[ei].e != EVENT_PRUN) {
00354           if (d != events[ei].date) {
00355             GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
00356                                   ntask, su,
00357                                   contribution, prune_tasks, prune_tasks_size));
00358             d = events[ei].date;
00359           }
00360           if (events[ei].e == EVENT_CHCK) {
00361             ntask += events[ei].inc;
00362           } else /* if (events[ei].e == EVENT_PROF) */ {
00363             su += events[ei].inc;
00364             if(events[ei].first_prof)
00365               contribution[events[ei].task] = at_most
00366                 ? std::max(contribution[events[ei].task], events[ei].inc)
00367                 : std::min(contribution[events[ei].task], events[ei].inc);
00368           }
00369         } else /* if (events[ei].e == EVENT_PRUN) */ {
00370           assert(prune_tasks_size<s.size());
00371           prune_tasks[prune_tasks_size++] = events[ei].task;
00372         }
00373         ei++;
00374       }
00375 
00376       GECODE_ES_CHECK(prune(home, d, d, r,
00377                             ntask, su,
00378                             contribution, prune_tasks, prune_tasks_size));
00379     }
00380     return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
00381   }
00382 
00383 }}}
00384 
00385 // STATISTICS: int-prop