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