Generated on Mon May 5 05:53:54 2008 for Gecode by doxygen 1.5.5

val.icc

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: 2008-02-06 18:48:22 +0100 (Wed, 06 Feb 2008) $ by $Author: schulte $
00011  *     $Revision: 6102 $
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 /* This is the propagation algorithm of the cumulatives constraint as presented in
00039    @inproceedings{DBLP:conf/cp/BeldiceanuC02,
00040      author    = {Nicolas Beldiceanu and Mats Carlsson},
00041      title     = {A New Multi-resource cumulatives Constraint with Negative Heights.},
00042      booktitle = {CP},
00043      year      = {2002},
00044      pages     = {63-79},
00045      ee        = {http://link.springer.de/link/service/series/0558/bibs/2470/24700063.htm},
00046      crossref  = {DBLP:conf/cp/2002},
00047      bibsource = {DBLP, http://dblp.uni-trier.de}
00048    }
00049    @proceedings{DBLP:conf/cp/2002,
00050      editor    = {Pascal Van Hentenryck},
00051      title     = {Principles and Practice of Constraint Programming - CP 2002,
00052                   8th International Conference, CP 2002,
00053                   Ithaca, NY, USA, September 9-13, 2002, Proceedings},
00054      booktitle = {CP},
00055      publisher = {Springer},
00056      series    = {Lecture Notes in Computer Science},
00057      volume    = {2470},
00058      year      = {2002},
00059      isbn      = {3-540-44120-4},
00060      bibsource = {DBLP, http://dblp.uni-trier.de}
00061    }
00062 
00063  */
00064 
00065 #include <vector>
00066 #include <list>
00067 #include <algorithm>
00068 
00069 
00070 namespace Gecode { namespace Int { namespace Cumulatives {
00071 
00072   template <class ViewM, class ViewD, class ViewH, class View>
00073   forceinline
00074   Val<ViewM,ViewD,ViewH,View>::Val(Space* home, 
00075                                    const ViewArray<ViewM>& _machine,
00076                                    const ViewArray<View>& _start,
00077                                    const ViewArray<ViewD>& _duration,
00078                                    const ViewArray<View>& _end,
00079                                    const ViewArray<ViewH>& _height,
00080                                    const IntArgs& _limit,
00081                                    bool _at_most) :
00082     Propagator(home),
00083     machine(_machine), start(_start), duration(_duration),
00084     end(_end), height(_height), limit(_limit.size()), at_most(_at_most) {
00085     force(home);    
00086     for(int i = _limit.size(); i--; )
00087       limit[i] = _limit[i];
00088 
00089     machine.subscribe(home,this,PC_INT_DOM);
00090     start.subscribe(home,this,PC_INT_BND);
00091     duration.subscribe(home,this,PC_INT_BND);
00092     end.subscribe(home,this,PC_INT_BND);
00093     height.subscribe(home,this,PC_INT_BND);
00094   }
00095 
00096   template <class ViewM, class ViewD, class ViewH, class View>
00097   ExecStatus
00098   Val<ViewM,ViewD,ViewH,View>
00099   ::post(Space* home, const ViewArray<ViewM>& machine,
00100          const ViewArray<View>& start, const ViewArray<ViewD>& duration,
00101          const ViewArray<View>& end, const ViewArray<ViewH>& height,
00102          const IntArgs& limit, bool at_most) {
00103     (void) new (home) Val(home, machine, start, duration,
00104                           end, height, limit, at_most);
00105 
00106     return ES_OK;
00107   }
00108 
00109   template <class ViewM, class ViewD, class ViewH, class View>
00110   forceinline
00111   Val<ViewM,ViewD,ViewH,View>::Val(Space* home, bool share,
00112                                    Val<ViewM,ViewD,ViewH,View>& p)
00113     : Propagator(home,share,p), at_most(p.at_most) {
00114     machine.update(home,share,p.machine);
00115     start.update(home, share, p.start);
00116     duration.update(home, share, p.duration);
00117     end.update(home, share, p.end);
00118     height.update(home, share, p.height);
00119     limit.update(home, share, p.limit);
00120   }
00121 
00122   template <class ViewM, class ViewD, class ViewH, class View>
00123   size_t
00124   Val<ViewM,ViewD,ViewH,View>::dispose(Space* home) {
00125     unforce(home);
00126     if (!home->failed()) {
00127       machine.cancel(home,this,PC_INT_DOM);
00128       start.cancel(home,this,PC_INT_BND);
00129       duration.cancel(home,this,PC_INT_BND);
00130       end.cancel(home,this,PC_INT_BND);
00131       height.cancel(home,this,PC_INT_BND);
00132     }
00133     limit.~SharedArray();
00134     (void) Propagator::dispose(home);
00135     return sizeof(*this);
00136   }
00137 
00138   template <class ViewM, class ViewD, class ViewH, class View>
00139   PropCost
00140   Val<ViewM,ViewD,ViewH,View>::cost(ModEventDelta) const {
00141     return cost_hi(start.size(), PC_QUADRATIC_LO);
00142   }
00143 
00144   template <class ViewM, class ViewD, class ViewH, class View>
00145   Support::Symbol
00146   Val<ViewM,ViewD,ViewH,View>::ati(void) {
00147     return 
00148       Reflection::mangle<ViewM,ViewD,ViewH,View>("Gecode::Int::Cumulatives::Val");
00149   }
00150 
00151   template <class ViewM, class ViewD, class ViewH, class View>
00152   Reflection::ActorSpec
00153   Val<ViewM,ViewD,ViewH,View>::spec(const Space* home,
00154                                     Reflection::VarMap& m) const {
00155     Reflection::ActorSpec s(ati());
00156 
00157     return s << machine.spec(home, m)
00158              << start.spec(home, m)
00159              << duration.spec(home, m)
00160              << end.spec(home, m)
00161              << height.spec(home, m)
00162              << Reflection::Arg::newIntArray(limit)
00163              << at_most;
00164   }
00165 
00166   template <class ViewM, class ViewD, class ViewH, class View>
00167   void
00168   Val<ViewM,ViewD,ViewH,View>::post(Space* home, Reflection::VarMap& vars,
00169                                     const Reflection::ActorSpec& spec) {
00170     spec.checkArity(7);
00171     ViewArray<ViewM> machine(home, vars, spec[0]);
00172     ViewArray<View>  start(home, vars, spec[1]);
00173     ViewArray<ViewD> duration(home, vars, spec[2]);
00174     ViewArray<View>  end(home, vars, spec[3]);
00175     ViewArray<ViewH> height(home, vars, spec[4]);
00176     Reflection::IntArrayArg* limitA = spec[5]->toIntArray();
00177     IntArgs limit(limitA->size());
00178     for (int i=limitA->size(); i--; )
00179       limit[i] = (*limitA)[i];
00180     bool at_most = spec[6]->toInt();
00181     (void) new (home) Val(home,machine,start,duration,
00182                           end,height,limit,at_most);
00183   }
00184 
00185   template <class ViewM, class ViewD, class ViewH, class View>
00186   Actor*
00187   Val<ViewM,ViewD,ViewH,View>::copy(Space* home, bool share) {
00188     return new (home) Val<ViewM,ViewD,ViewH,View>(home,share,*this);
00189   }
00190 
00192   typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
00194   class Event
00195   {
00196   public:
00198     ev_t e;
00200     int task;
00202     int date;
00204     int inc;
00209     bool first_prof;
00210 
00212     Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
00213       : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
00214     {}
00215 
00217     bool operator<(const Event& e) {
00218       return date < e.date;
00219     }
00220   };
00221 
00222 
00223   template <class ViewM, class ViewD, class ViewH, class View>
00224   ExecStatus
00225   Val<ViewM,ViewD,ViewH,View>::prune(Space * home, int low, int up, int r,
00226                                      int ntask, int sheight,
00227                                      const std::vector<int>& contribution,
00228                                      std::list<int>& prune_tasks) {
00229 
00230     if (ntask > 0 &&
00231         (at_most ? sheight > limit[r]
00232          : sheight < limit[r])) {
00233       return ES_FAILED;
00234     }
00235 
00236     std::list<int>::iterator it = prune_tasks.begin();
00237     while (it != prune_tasks.end()) {
00238       int t = *it;
00239       // Algorithm 2.
00240       // Prune the machine, start, and end for required
00241       // tasks for machine r that have heights possibly greater than 0.
00242       if (ntask != 0 &&
00243           (at_most ? height[t].min() < 0
00244            : height[t].max() > 0) &&
00245           (at_most ? sheight-contribution[t] > limit[r]
00246            : sheight-contribution[t] < limit[r])) {
00247         if (me_failed(machine[t].eq(home, r))||
00248             me_failed(start[t].gq(home, up-duration[t].max()+1))||
00249             me_failed(start[t].lq(home, low))||
00250             me_failed(end[t].lq(home,low+duration[t].max()))||
00251             me_failed(end[t].gq(home, up+1))||
00252             me_failed(duration[t].gq(home,std::min(up-start[t].max()+1,
00253                                                    end[t].min()-low)))
00254             )
00255           return ES_FAILED;
00256       }
00257 
00258       // Algorithm 3.
00259       // Remove values that prevent us from reaching the limit
00260       if (at_most ? height[t].min() < std::min(0, limit[r])
00261           : height[t].max() < std::max(0, limit[r])) {
00262         if (at_most ? sheight-contribution[t]+height[t].min() > limit[r]
00263             : sheight-contribution[t]+height[t].max() < limit[r]) {
00264           if (end[t].min() > low  &&
00265               start[t].max() <= up &&
00266               duration[t].min() > 0) {
00267             if (me_failed(machine[t].nq(home, r)))
00268               return ES_FAILED;
00269           } else if (machine[t].assigned()) {
00270             int dtmin = duration[t].min();
00271             if (dtmin > 0) {
00272               Iter::Ranges::Singleton
00273                 a(low-dtmin+1, up), b(low+1, up+dtmin);
00274                 if (me_failed(start[t].minus_r(home,a,false)) ||
00275                     me_failed(end[t].minus_r(home, b,false)))
00276                   return ES_FAILED;
00277             }
00278             if (me_failed(duration[t].lq(home,
00279                                          std::max(std::max(low-start[t].min(),
00280                                                            end[t].max()-up-1),
00281                                                   0))))
00282               return ES_FAILED;
00283           }
00284         }
00285       }
00286 
00287       // Algorithm 4.
00288       // Remove bad negative values from for-sure heights.
00289       /* \note "It is not sufficient to only test for assignment of machine[t]
00290        *         since Algorithm 3 can remove the value." Check this against
00291        *         the conditions for Alg3.
00292        */
00293       if (machine[t].assigned() &&
00294           machine[t].val() == r &&
00295           end[t].min() > low    &&
00296           start[t].max() <= up  &&
00297           duration[t].min() > 0 ) {
00298         if (me_failed(at_most
00299                       ? height[t].lq(home, limit[r]-sheight+contribution[t])
00300                       : height[t].gq(home, limit[r]-sheight+contribution[t])))
00301           return ES_FAILED;
00302       }
00303 
00304       // Remove tasks that are no longer relevant.
00305       if ((!machine[t].in(r)) ||
00306           end[t].max() <= up+1) {
00307         std::list<int>::iterator old = it++;
00308         prune_tasks.erase(old);
00309       } else {
00310         ++it;
00311       }
00312     }
00313 
00314     return ES_OK;
00315   }
00316 
00317   template <class ViewM, class ViewD, class ViewH, class View>
00318   ExecStatus
00319   Val<ViewM,ViewD,ViewH,View>::propagate(Space* home, ModEventDelta) {
00320     // Check for subsumption
00321     bool subsumed = true;
00322     for (int t = start.size(); t--; )
00323       if (!(duration[t].assigned() && end[t].assigned()   &&
00324             machine[t].assigned()  && start[t].assigned() &&
00325             height[t].assigned())) {
00326         subsumed = false;
00327         break;
00328       }
00329 
00330     // Propagate information for machine r
00331     for (int r = limit.size(); r--; ) {
00332       std::list<Event> events;
00333 
00334       // Find events for sweep-line
00335       for (int t = start.size(); t--; ) {
00336         if (machine[t].assigned() &&
00337             machine[t].val() == r &&
00338             start[t].max() < end[t].min()) {
00339           if (at_most
00340               ? height[t].min() > std::min(0, limit[r])
00341               : height[t].max() < std::max(0, limit[r])) {
00342             events.push_back(Event(EVENT_CHCK, t, start[t].max(), 1));
00343             events.push_back(Event(EVENT_CHCK, t, end[t].min(), -1));
00344           }
00345           if (at_most
00346               ? height[t].min() > 0
00347               : height[t].max() < 0) {
00348             events.push_back(Event(EVENT_PROF, t, start[t].max(),
00349                                    at_most ? height[t].min()
00350                                    : height[t].max(), true));
00351             events.push_back(Event(EVENT_PROF, t, end[t].min(),
00352                                    at_most ? -height[t].min()
00353                                    : -height[t].max()));
00354           }
00355         }
00356         
00357         if (machine[t].in(r)) {
00358           if (at_most
00359               ? height[t].min() < 0
00360               : height[t].max() > 0) {
00361             events.push_back(Event(EVENT_PROF, t, start[t].min(),
00362                                    at_most ? height[t].min()
00363                                    : height[t].max(), true));
00364             events.push_back(Event(EVENT_PROF, t, end[t].max(),
00365                                    at_most ? -height[t].min()
00366                                    : -height[t].max()));
00367           }
00368           if (!(machine[t].assigned() &&
00369                  height[t].assigned() &&
00370                   start[t].assigned() &&
00371                     end[t].assigned())) {
00372             events.push_back(Event(EVENT_PRUN, t, start[t].min()));
00373           }
00374         }
00375       }
00376 
00377       // If there are no events, continue with next machine
00378       if (events.size() == 0)
00379         continue;
00380 
00381       // Sort the events according to date
00382       events.sort();
00383 
00384       // Sweep line along d, starting at 0
00385       int d        = 0;
00386       int ntask    = 0;
00387       int sheight  = 0;
00388       std::list<Event>::iterator it = events.begin();
00389       std::list<int> prune_tasks;
00390       std::vector<int> contribution(start.size(), at_most
00391                                     ? Limits::max
00392                                     : Limits::min);
00393 
00394       d = it->date;
00395       while (it != events.end()) {
00396         if (it->e != EVENT_PRUN) {
00397           if (d != it->date) {
00398             GECODE_ES_CHECK(prune(home, d, it->date-1, r,
00399                                   ntask, sheight,
00400                                   contribution, prune_tasks));
00401             d = it->date;
00402           }
00403           if (it->e == EVENT_CHCK) {
00404             ntask += it->inc;
00405           } else /* if (it->e == EVENT_PROF) */ {
00406             sheight += it->inc;
00407             if(it->first_prof)
00408               contribution[it->task] = at_most
00409                 ? std::min(contribution[it->task], it->inc)
00410                 : std::max(contribution[it->task], it->inc);
00411           }
00412         } else /* if (it->e == EVENT_PRUN) */ {
00413           prune_tasks.push_back(it->task);
00414         }
00415         ++it;
00416       }
00417 
00418       GECODE_ES_CHECK(prune(home, d, d, r,
00419                             ntask, sheight,
00420                             contribution, prune_tasks));
00421     }
00422 
00423     return subsumed ? ES_SUBSUMED(this,home): ES_NOFIX;
00424   }
00425 
00426 }}}
00427 
00428 // STATISTICS: int-prop
00429