Generated on Wed Jan 4 17:49:08 2006 for Gecode by doxygen 1.4.6

val.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Mikael Lagerkvist, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-07 17:15:40 +0100 (Mon, 07 Nov 2005) $ by $Author: zayenz $
00010  *     $Revision: 2519 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 /* This is the propagation algorithm of the cumulatives constraint as presented in
00023    @inproceedings{DBLP:conf/cp/BeldiceanuC02,
00024      author    = {Nicolas Beldiceanu and Mats Carlsson},
00025      title     = {A New Multi-resource cumulatives Constraint with Negative Heights.},
00026      booktitle = {CP},
00027      year      = {2002},
00028      pages     = {63-79},
00029      ee        = {http://link.springer.de/link/service/series/0558/bibs/2470/24700063.htm},
00030      crossref  = {DBLP:conf/cp/2002},
00031      bibsource = {DBLP, http://dblp.uni-trier.de}
00032    }
00033    @proceedings{DBLP:conf/cp/2002,
00034      editor    = {Pascal Van Hentenryck},
00035      title     = {Principles and Practice of Constraint Programming - CP 2002, 
00036                   8th International Conference, CP 2002, 
00037                   Ithaca, NY, USA, September 9-13, 2002, Proceedings},
00038      booktitle = {CP},
00039      publisher = {Springer},
00040      series    = {Lecture Notes in Computer Science},
00041      volume    = {2470},
00042      year      = {2002},
00043      isbn      = {3-540-44120-4},
00044      bibsource = {DBLP, http://dblp.uni-trier.de}
00045    }
00046 
00047  */
00048 
00049 #include <vector>
00050 #include <list>
00051 #include <algorithm>
00052 
00053 
00054 namespace Gecode { namespace Int { namespace Cumulatives {
00055 
00056   template <class ViewM, class ViewD, class ViewH, class View>
00057   forceinline
00058   Val<ViewM,ViewD,ViewH,View>::Val(Space* home, const ViewArray<ViewM>& _machine, 
00059                                    const ViewArray<View>& _start, 
00060                                    const ViewArray<ViewD>& _duration, 
00061                                    const ViewArray<View>& _end, 
00062                                    const ViewArray<ViewH>& _height, 
00063                                    const IntArgs& _limit, 
00064                                    bool _at_most) :
00065     Propagator(home), machine(_machine), start(_start), duration(_duration), 
00066     end(_end), height(_height), limit(_limit.size()), at_most(_at_most),
00067     cd_option(false) {
00068     for(int i = _limit.size(); i--; ) {
00069       limit[i] = _limit[i];
00070     }
00071 
00072     machine.subscribe(home,this,PC_INT_DOM);
00073     start.subscribe(home,this,PC_INT_BND);
00074     duration.subscribe(home,this,PC_INT_BND);
00075     end.subscribe(home,this,PC_INT_BND);
00076     height.subscribe(home,this,PC_INT_BND);
00077   }
00078 
00079   template <class ViewM, class ViewD, class ViewH, class View>
00080   ExecStatus
00081   Val<ViewM,ViewD,ViewH,View>::post(Space* home, const ViewArray<ViewM>& machine, 
00082                   const ViewArray<View>& start, const ViewArray<ViewD>& duration, 
00083                   const ViewArray<View>& end, const ViewArray<ViewH>& height, 
00084                   const IntArgs& limit, bool at_most) {
00085     (void) new (home) Val(home, machine, start, duration, 
00086                           end, height, limit, at_most);
00087 
00088     return ES_OK;
00089   }
00090 
00091   template <class ViewM, class ViewD, class ViewH, class View>
00092   forceinline
00093   Val<ViewM,ViewD,ViewH,View>::Val(Space* home, bool share, 
00094                                    Val<ViewM,ViewD,ViewH,View>& p)
00095     : Propagator(home,share,p), at_most(p.at_most), cd_option(false) {
00096     machine.update(home,share,p.machine);
00097     start.update(home, share, p.start);
00098     duration.update(home, share, p.duration);
00099     end.update(home, share, p.end);
00100     height.update(home, share, p.height);
00101     limit.update(share, p.limit);
00102   } 
00103 
00104   template <class ViewM, class ViewD, class ViewH, class View>
00105   Val<ViewM,ViewD,ViewH,View>::~Val(void) {
00106     machine.cancel(this,PC_INT_DOM);
00107     start.cancel(this,PC_INT_BND);
00108     duration.cancel(this,PC_INT_BND);
00109     end.cancel(this,PC_INT_BND);
00110     height.cancel(this,PC_INT_BND);
00111   }
00112   
00113   template <class ViewM, class ViewD, class ViewH, class View>
00114   PropCost
00115   Val<ViewM,ViewD,ViewH,View>::cost(void) const {
00116     return cost_hi(start.size(), PC_QUADRATIC_LO);
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     
00151     bool operator<(const Event& e) {
00152       return date < e.date;
00153     }
00154   };
00155   
00156 
00157   template <class ViewM, class ViewD, class ViewH, class View> 
00158   ExecStatus 
00159   Val<ViewM,ViewD,ViewH,View>::prune(Space * home, int low, int up, int r, 
00160                    int ntask, int sheight,
00161                    const std::vector<int>& contribution, 
00162                    std::list<int>& prune_tasks) {
00163 
00164     if (ntask > 0 && 
00165         (at_most ? sheight > limit[r]
00166          : sheight < limit[r])) {
00167       return ES_FAILED;
00168     }
00169 
00170     std::list<int>::iterator it = prune_tasks.begin(); 
00171     while (it != prune_tasks.end()) {
00172       int t = *it;
00173       // Algorithm 2.
00174       // Prune the machine, start, and end for required 
00175       // tasks for machine r that have heights possibly greater than 0.
00176       if (ntask != 0 && 
00177           (at_most ? height[t].min() < 0 
00178            : height[t].max() > 0) &&
00179           (at_most ? sheight-contribution[t] > limit[r]
00180            : sheight-contribution[t] < limit[r])) {
00181         if (me_failed(machine[t].eq(home, r))||
00182             me_failed(start[t].gq(home, up-duration[t].max()+1))||
00183             me_failed(start[t].lq(home, low))||
00184             me_failed(end[t].lq(home,low+duration[t].max()))||
00185             me_failed(end[t].gq(home, up+1))||
00186             me_failed(duration[t].gq(home,std::min(up-start[t].max()+1,
00187                                                    end[t].min()-low)))
00188             )
00189           return ES_FAILED;
00190       }
00191 
00192       // Algorithm 3.
00193       // Remove values that prevent us from reaching the limit
00194       if (at_most ? height[t].min() < std::min(0, limit[r])
00195           : height[t].max() < std::max(0, limit[r])) {
00196         if (at_most ? sheight-contribution[t]+height[t].min() > limit[r]
00197             : sheight-contribution[t]+height[t].max() < limit[r]) {
00198           if (end[t].min() > low  && 
00199               start[t].max() <= up && 
00200               duration[t].min() > 0) {
00201             if (me_failed(machine[t].nq(home, r)))
00202               return ES_FAILED;
00203           } else if (machine[t].assigned()) {
00204             int dtmin = duration[t].min();
00205             if (dtmin > 0) {
00206               Iter::Ranges::Singleton
00207                 a(low-dtmin+1, up), b(low+1, up+dtmin);
00208               if (me_failed(start[t].minus(home,a)) ||
00209                   me_failed(end[t].minus(home, b)))
00210                 return ES_FAILED;
00211             }
00212             if (me_failed(duration[t].lq(home, 
00213                                          std::max(std::max(low-start[t].min(), 
00214                                                            end[t].max()-up-1),
00215                                                   0))))
00216               return ES_FAILED;
00217           }
00218         }
00219       }
00220 
00221       // Algorithm 4.
00222       // Remove bad negative values from for-sure heights.
00223       /* \note "It is not sufficient to only test for assignment of machine[t]
00224        *         since Algorithm 3 can remove the value." Check this against 
00225        *         the conditions for Alg3.
00226        */
00227       if (machine[t].assigned() &&
00228           machine[t].val() == r &&
00229           end[t].min() > low    &&
00230           start[t].max() <= up  &&
00231           duration[t].min() > 0 ) {
00232         if (me_failed(at_most
00233                       ? height[t].lq(home, limit[r]-sheight+contribution[t])
00234                       : height[t].gq(home, limit[r]-sheight+contribution[t])))
00235           return ES_FAILED;
00236       }
00237 
00238       // Remove tasks that are no longer relevant.
00239       /* @todo check condition more thouroughly - is 
00240        *        \f$max(end_r)\geq up+1\f$  CORRECT?
00241        */
00242       if ((!machine[t].in(r)) ||
00243           end[t].max() <= up+1) {
00244         // @todo more than one *it (probably not) ? ==> remove(*it)
00245         std::list<int>::iterator old = it++;
00246         prune_tasks.erase(old);
00247       } else {
00248         ++it;
00249       }
00250     }
00251 
00252     // Constructive disjunction on machine-assignement.
00253     if(cd_option) {
00254       
00255     }
00256 
00257     return ES_OK;
00258   }
00259     
00260   template <class ViewM, class ViewD, class ViewH, class View> 
00261   ExecStatus 
00262   Val<ViewM,ViewD,ViewH,View>::propagate(Space* home) {
00263     ExecStatus res = ES_NOFIX;
00264     // Check for subsumption
00265     bool nnft = true; // no non-fixed tasks.
00266     for (int t = start.size(); t--; )
00267       if(!(duration[t].assigned() && end[t].assigned()   && 
00268            machine[t].assigned()  && start[t].assigned() &&
00269            height[t].assigned())) {
00270         nnft = false;
00271         break;
00272       }
00273     if(nnft) res = ES_SUBSUMED;
00274 
00275 
00276     // Propagate information for machine r
00277     for (int r = limit.size(); r--; ) {
00278       std::list<Event> events;
00279       
00280       // Find events for sweep-line 
00281       for (int t = start.size(); t--; ) {
00282         if (machine[t].assigned() && 
00283             machine[t].val() == r &&
00284             start[t].max() < end[t].min()) {
00285           if (at_most 
00286               ? height[t].min() > std::min(0, limit[r])
00287               : height[t].max() < std::max(0, limit[r])) {
00288             events.push_back(Event(EVENT_CHCK, t, start[t].max(), 1));
00289             events.push_back(Event(EVENT_CHCK, t, end[t].min(), -1));
00290           }
00291           if (at_most
00292               ? height[t].min() > 0
00293               : height[t].max() < 0) {
00294             events.push_back(Event(EVENT_PROF, t, start[t].max(), 
00295                                    at_most ? height[t].min()
00296                                    : height[t].max(), true));
00297             events.push_back(Event(EVENT_PROF, t, end[t].min(), 
00298                                    at_most ? -height[t].min()
00299                                    : -height[t].max()));
00300           }
00301         }
00302         
00303         if (machine[t].in(r)) {
00304           if (at_most
00305               ? height[t].min() < 0
00306               : height[t].max() > 0) {
00307             events.push_back(Event(EVENT_PROF, t, start[t].min(), 
00308                                    at_most ? height[t].min()
00309                                    : height[t].max(), true));
00310             events.push_back(Event(EVENT_PROF, t, end[t].max(), 
00311                                    at_most ? -height[t].min()
00312                                    : -height[t].max()));
00313           }
00314           if (!(machine[t].assigned() &&
00315                  height[t].assigned() &&
00316                   start[t].assigned() &&
00317                     end[t].assigned())) {
00318             events.push_back(Event(EVENT_PRUN, t, start[t].min()));
00319           }
00320         }
00321       }
00322 
00323       // If there are no events, continue with next machine
00324       if (events.size() == 0)
00325         continue;
00326 
00327       // Sort the events according to date
00328       events.sort();
00329 
00330       // Sweep line along d, starting at 0
00331       int d        = 0;
00332       int ntask    = 0;
00333       int sheight  = 0;
00334       std::list<Event>::iterator it = events.begin();
00335       std::list<int> prune_tasks;
00336       std::vector<int> contribution(start.size(), at_most 
00337                                     ? Limits::Int::int_max
00338                                     : Limits::Int::int_min);
00339 
00340       d = it->date;
00341       while (it != events.end()) {
00342         if (it->e != EVENT_PRUN) {
00343           if (d != it->date) {
00344             GECODE_ES_CHECK(prune(home, d, it->date-1, r, 
00345                                   ntask, sheight,
00346                                   contribution, prune_tasks));
00347             d = it->date;
00348           }
00349           if (it->e == EVENT_CHCK) {
00350             ntask += it->inc;
00351           } else /* if (it->e == EVENT_PROF) */ {
00352             sheight += it->inc;
00353             // @bug may not be correct. Check alg 3, maximum or 
00354             // recent contribution...
00355             if(it->first_prof)
00356               contribution[it->task] = at_most 
00357                 ? std::min(contribution[it->task], it->inc)
00358                 : std::max(contribution[it->task], it->inc);
00359           }
00360         } else /* if (it->e == EVENT_PRUN) */ {
00361           prune_tasks.push_back(it->task);
00362         }
00363         ++it;
00364       }
00365 
00366       GECODE_ES_CHECK(prune(home, d, d, r, 
00367                             ntask, sheight,
00368                             contribution, prune_tasks));
00369     }
00370 
00371 
00372     return res;
00373   }
00374 
00375 }}}
00376 
00377 // STATISTICS: int-prop
00378