Generated on Mon May 10 06:46:32 2010 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  *  Last modified:
00010  *     $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $
00011  *     $Revision: 10364 $
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 <algorithm>
00039 
00040 /*
00041  * This is the propagation algorithm of the cumulatives constraint as
00042  * presented in:
00043  *   Nicolas Beldiceanu and Mats Carlsson, A New Multi-resource cumulatives
00044  *   Constraint with Negative Heights. CP 2002, pages 63-79, Springer-Verlag.
00045  */
00046 
00047 namespace Gecode { namespace Scheduling { namespace Cumulatives {
00048 
00049   template<class ViewM, class ViewD, class ViewH, class View>
00050   forceinline
00051   Val<ViewM,ViewD,ViewH,View>::Val(Home home,
00052                                    const ViewArray<ViewM>& _machine,
00053                                    const ViewArray<View>& _start,
00054                                    const ViewArray<ViewD>& _duration,
00055                                    const ViewArray<View>& _end,
00056                                    const ViewArray<ViewH>& _height,
00057                                    const SharedArray<int>& _limit,
00058                                    bool _at_most) :
00059     Propagator(home),
00060     machine(_machine), start(_start), duration(_duration),
00061     end(_end), height(_height), limit(_limit), at_most(_at_most) {
00062     home.notice(*this,AP_DISPOSE);
00063 
00064     machine.subscribe(home,*this,Int::PC_INT_DOM);
00065     start.subscribe(home,*this,Int::PC_INT_BND);
00066     duration.subscribe(home,*this,Int::PC_INT_BND);
00067     end.subscribe(home,*this,Int::PC_INT_BND);
00068     height.subscribe(home,*this,Int::PC_INT_BND);
00069   }
00070 
00071   template<class ViewM, class ViewD, class ViewH, class View>
00072   ExecStatus
00073   Val<ViewM,ViewD,ViewH,View>
00074   ::post(Home home, const ViewArray<ViewM>& machine,
00075          const ViewArray<View>& start, const ViewArray<ViewD>& duration,
00076          const ViewArray<View>& end, const ViewArray<ViewH>& height,
00077          const SharedArray<int>& limit, bool at_most) {
00078     (void) new (home) Val(home, machine, start, duration,
00079                           end, height, limit, at_most);
00080 
00081     return ES_OK;
00082   }
00083 
00084   template<class ViewM, class ViewD, class ViewH, class View>
00085   forceinline
00086   Val<ViewM,ViewD,ViewH,View>::Val(Space& home, bool share,
00087                                    Val<ViewM,ViewD,ViewH,View>& p)
00088     : Propagator(home,share,p), at_most(p.at_most) {
00089     machine.update(home,share,p.machine);
00090     start.update(home, share, p.start);
00091     duration.update(home, share, p.duration);
00092     end.update(home, share, p.end);
00093     height.update(home, share, p.height);
00094     limit.update(home, share, p.limit);
00095   }
00096 
00097   template<class ViewM, class ViewD, class ViewH, class View>
00098   size_t
00099   Val<ViewM,ViewD,ViewH,View>::dispose(Space& home) {
00100     home.ignore(*this,AP_DISPOSE);
00101     if (!home.failed()) {
00102       machine.cancel(home,*this,Int::PC_INT_DOM);
00103       start.cancel(home,*this,Int::PC_INT_BND);
00104       duration.cancel(home,*this,Int::PC_INT_BND);
00105       end.cancel(home,*this,Int::PC_INT_BND);
00106       height.cancel(home,*this,Int::PC_INT_BND);
00107     }
00108     limit.~SharedArray();
00109     (void) Propagator::dispose(home);
00110     return sizeof(*this);
00111   }
00112 
00113   template<class ViewM, class ViewD, class ViewH, class View>
00114   PropCost
00115   Val<ViewM,ViewD,ViewH,View>::cost(const Space&, const ModEventDelta&) const {
00116     return PropCost::quadratic(PropCost::LO, start.size());
00117   }
00118 
00119   template<class ViewM, class ViewD, class ViewH, class View>
00120   Actor*
00121   Val<ViewM,ViewD,ViewH,View>::copy(Space& home, bool share) {
00122     return new (home) Val<ViewM,ViewD,ViewH,View>(home,share,*this);
00123   }
00124 
00126   typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
00128   class Event
00129   {
00130   public:
00132     ev_t e;
00134     int task;
00136     int date;
00138     int inc;
00143     bool first_prof;
00144 
00146     Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
00147       : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
00148     {}
00149 
00150     // Default constructor for region-allocated memory
00151     Event(void) {}
00152 
00154     bool operator <(const Event& ev) const {
00155       if (date == ev.date) {
00156         if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
00157         if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
00158         return false;
00159       }
00160       return date < ev.date;
00161     }
00162   };
00163 
00164   template<class ViewM, class ViewD, class ViewH, class View>
00165   ExecStatus
00166   Val<ViewM,ViewD,ViewH,View>::prune(Space& home, int low, int up, int r,
00167                                      int ntask, int sheight,
00168                                      int* contribution,
00169                                      int* prune_tasks, int& prune_tasks_size) {
00170 
00171     if (ntask > 0 &&
00172         (at_most ? sheight > limit[r]
00173          : sheight < limit[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 ? height[t].min() < 0
00186            : height[t].max() > 0) &&
00187           (at_most ? sheight-contribution[t] > limit[r]
00188            : sheight-contribution[t] < limit[r])) {
00189         if (me_failed(machine[t].eq(home, r))||
00190             me_failed(start[t].gq(home, up-duration[t].max()+1))||
00191             me_failed(start[t].lq(home, low))||
00192             me_failed(end[t].lq(home,low+duration[t].max()))||
00193             me_failed(end[t].gq(home, up+1))||
00194             me_failed(duration[t].gq(home,std::min(up-start[t].max()+1,
00195                                                    end[t].min()-low)))
00196             ) {
00197           return ES_FAILED;
00198         }
00199       }
00200 
00201       // Algorithm 3.
00202       // Remove values that prevent us from reaching the limit
00203       if (at_most ? height[t].min() > std::min(0, limit[r])
00204           : height[t].max() < std::max(0, limit[r])) {
00205         if (at_most ? sheight-contribution[t]+height[t].min() > limit[r]
00206             : sheight-contribution[t]+height[t].max() < limit[r]) {
00207           if (end[t].min() > low  &&
00208               start[t].max() <= up &&
00209               duration[t].min() > 0) {
00210             if (me_failed(machine[t].nq(home, r))) {
00211               return ES_FAILED;
00212             }
00213           } else if (machine[t].assigned()) {
00214             int dtmin = duration[t].min();
00215             if (dtmin > 0) {
00216               Iter::Ranges::Singleton
00217                 a(low-dtmin+1, up), b(low+1, up+dtmin);
00218               if (me_failed(start[t].minus_r(home,a,false)) ||
00219                   me_failed(end[t].minus_r(home, b,false)))
00220                 return ES_FAILED;
00221             }
00222             if (me_failed(duration[t].lq(home,
00223                                          std::max(std::max(low-start[t].min(),
00224                                                            end[t].max()-up-1),
00225                                                   0)))) {
00226               return ES_FAILED;
00227             }
00228           }
00229         }
00230       }
00231 
00232       // Algorithm 4.
00233       // Remove bad negative values from for-sure heights.
00234       /* \note "It is not sufficient to only test for assignment of machine[t]
00235        *         since Algorithm 3 can remove the value." Check this against
00236        *         the conditions for Alg3.
00237        */
00238       if (machine[t].assigned() &&
00239           machine[t].val() == r &&
00240           end[t].min() > low    &&
00241           start[t].max() <= up  &&
00242           duration[t].min() > 0 ) {
00243         if (me_failed(at_most
00244                       ? height[t].lq(home, limit[r]-sheight+contribution[t])
00245                       : height[t].gq(home, limit[r]-sheight+contribution[t]))) {
00246           return ES_FAILED;
00247         }
00248       }
00249 
00250       // Remove tasks that are no longer relevant.
00251       if (!machine[t].in(r) || (end[t].max() <= up+1)) {
00252         prune_tasks[pti] = prune_tasks[--prune_tasks_size];
00253       } else {
00254         ++pti;
00255       }
00256     }
00257 
00258     return ES_OK;
00259   }
00260 
00261   namespace {
00262     template<class C>
00263     class Less {
00264     public:
00265       bool operator ()(const C& lhs, const C& rhs) {
00266         return lhs < rhs;
00267       }
00268     };
00269   }
00270 
00271   template<class ViewM, class ViewD, class ViewH, class View>
00272   ExecStatus
00273   Val<ViewM,ViewD,ViewH,View>::propagate(Space& home, const ModEventDelta&) {
00274     // Check for subsumption
00275     bool subsumed = true;
00276     for (int t = start.size(); t--; )
00277       if (!(duration[t].assigned() && end[t].assigned()   &&
00278             machine[t].assigned()  && start[t].assigned() &&
00279             height[t].assigned())) {
00280         subsumed = false;
00281         break;
00282       }
00283     // Propagate information for machine r
00284     Region region(home);
00285     Event *events = region.alloc<Event>(start.size()*8);
00286     int  events_size;
00287     int *prune_tasks = region.alloc<int>(start.size());
00288     int  prune_tasks_size;
00289     int *contribution = region.alloc<int>(start.size());
00290     for (int r = limit.size(); r--; ) {
00291       events_size = 0;
00292 #define GECODE_PUSH_EVENTS(E) assert(events_size < start.size()*8);     \
00293         events[events_size++] = E
00294 
00295       // Find events for sweep-line
00296       for (int t = start.size(); t--; ) {
00297         if (machine[t].assigned() &&
00298             machine[t].val() == r &&
00299             start[t].max() < end[t].min()) {
00300           if (at_most
00301               ? height[t].min() > std::min(0, limit[r])
00302               : height[t].max() < std::max(0, limit[r])) {
00303             GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, start[t].max(), 1));
00304             GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, end[t].min(), -1));
00305           }
00306           if (at_most
00307               ? height[t].min() > 0
00308               : height[t].max() < 0) {
00309             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, start[t].max(),
00310                                    at_most ? height[t].min()
00311                                    : height[t].max(), true));
00312             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, end[t].min(),
00313                                    at_most ? -height[t].min()
00314                                    : -height[t].max()));
00315           }
00316         }
00317 
00318         if (machine[t].in(r)) {
00319           if (at_most
00320               ? height[t].min() < 0
00321               : height[t].max() > 0) {
00322             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, start[t].min(),
00323                                    at_most ? height[t].min()
00324                                    : height[t].max(), true));
00325             GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, end[t].max(),
00326                                    at_most ? -height[t].min()
00327                                    : -height[t].max()));
00328           }
00329           if (!(machine[t].assigned() &&
00330                  height[t].assigned() &&
00331                   start[t].assigned() &&
00332                     end[t].assigned())) {
00333             GECODE_PUSH_EVENTS(Event(EVENT_PRUN, t, start[t].min()));
00334           }
00335         }
00336       }
00337 #undef GECODE_PUSH_EVENTS
00338 
00339       // If there are no events, continue with next machine
00340       if (events_size == 0) {
00341         continue;
00342       }
00343 
00344       // Sort the events according to date
00345       Less<Event> less;
00346       Support::insertion(&events[0], events_size, less);
00347 
00348       // Sweep line along d, starting at 0
00349       int d        = 0;
00350       int ntask    = 0;
00351       int sheight  = 0;
00352       int ei = 0;
00353 
00354       prune_tasks_size = 0;
00355       for (int i = start.size(); i--; ) contribution[i] = 0;
00356 
00357       d = events[ei].date;
00358       while (ei < events_size) {
00359         if (events[ei].e != EVENT_PRUN) {
00360           if (d != events[ei].date) {
00361             GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
00362                                   ntask, sheight,
00363                                   contribution, prune_tasks, prune_tasks_size));
00364             d = events[ei].date;
00365           }
00366           if (events[ei].e == EVENT_CHCK) {
00367             ntask += events[ei].inc;
00368           } else /* if (events[ei].e == EVENT_PROF) */ {
00369             sheight += events[ei].inc;
00370             if(events[ei].first_prof)
00371               contribution[events[ei].task] = at_most
00372                 ? std::max(contribution[events[ei].task], events[ei].inc)
00373                 : std::min(contribution[events[ei].task], events[ei].inc);
00374           }
00375         } else /* if (events[ei].e == EVENT_PRUN) */ {
00376           assert(prune_tasks_size<start.size());
00377           prune_tasks[prune_tasks_size++] = events[ei].task;
00378         }
00379         ei++;
00380       }
00381 
00382       GECODE_ES_CHECK(prune(home, d, d, r,
00383                             ntask, sheight,
00384                             contribution, prune_tasks, prune_tasks_size));
00385     }
00386     return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
00387   }
00388 
00389 }}}
00390 
00391 // STATISTICS: scheduling-prop
00392