this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Copyright:
7 * Mikael Lagerkvist, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <algorithm>
35
36/*
37 * This is the propagation algorithm of the cumulatives constraint as
38 * presented in:
39 * Nicolas Beldiceanu and Mats Carlsson, A New Multi-resource cumulatives
40 * Constraint with Negative Heights. CP 2002, pages 63-79, Springer-Verlag.
41 */
42
43namespace Gecode { namespace Int { namespace Cumulatives {
44
45 template<class ViewM, class ViewP, class ViewU, class View>
46 forceinline
47 Val<ViewM,ViewP,ViewU,View>::Val(Home home,
48 const ViewArray<ViewM>& _m,
49 const ViewArray<View>& _s,
50 const ViewArray<ViewP>& _p,
51 const ViewArray<View>& _e,
52 const ViewArray<ViewU>& _u,
53 const SharedArray<int>& _c,
54 bool _at_most) :
55 Propagator(home),
56 m(_m), s(_s), p(_p), e(_e), u(_u), c(_c), at_most(_at_most) {
57 home.notice(*this,AP_DISPOSE);
58
59 m.subscribe(home,*this,Int::PC_INT_DOM);
60 s.subscribe(home,*this,Int::PC_INT_BND);
61 p.subscribe(home,*this,Int::PC_INT_BND);
62 e.subscribe(home,*this,Int::PC_INT_BND);
63 u.subscribe(home,*this,Int::PC_INT_BND);
64 }
65
66 template<class ViewM, class ViewP, class ViewU, class View>
67 ExecStatus
68 Val<ViewM,ViewP,ViewU,View>
69 ::post(Home home, const ViewArray<ViewM>& m,
70 const ViewArray<View>& s, const ViewArray<ViewP>& p,
71 const ViewArray<View>& e, const ViewArray<ViewU>& u,
72 const SharedArray<int>& c, bool at_most) {
73 (void) new (home) Val(home, m,s,p,e,u,c,at_most);
74 return ES_OK;
75 }
76
77 template<class ViewM, class ViewP, class ViewU, class View>
78 forceinline
79 Val<ViewM,ViewP,ViewU,View>::Val(Space& home,
80 Val<ViewM,ViewP,ViewU,View>& vp)
81 : Propagator(home,vp), c(vp.c), at_most(vp.at_most) {
82 m.update(home,vp.m);
83 s.update(home, vp.s);
84 p.update(home, vp.p);
85 e.update(home, vp.e);
86 u.update(home, vp.u);
87 }
88
89 template<class ViewM, class ViewP, class ViewU, class View>
90 size_t
91 Val<ViewM,ViewP,ViewU,View>::dispose(Space& home) {
92 home.ignore(*this,AP_DISPOSE);
93 if (!home.failed()) {
94 m.cancel(home,*this,Int::PC_INT_DOM);
95 s.cancel(home,*this,Int::PC_INT_BND);
96 p.cancel(home,*this,Int::PC_INT_BND);
97 e.cancel(home,*this,Int::PC_INT_BND);
98 u.cancel(home,*this,Int::PC_INT_BND);
99 }
100 c.~SharedArray();
101 (void) Propagator::dispose(home);
102 return sizeof(*this);
103 }
104
105 template<class ViewM, class ViewP, class ViewU, class View>
106 PropCost
107 Val<ViewM,ViewP,ViewU,View>::cost(const Space&, const ModEventDelta&) const {
108 return PropCost::quadratic(PropCost::LO, s.size());
109 }
110
111 template<class ViewM, class ViewP, class ViewU, class View>
112 void
113 Val<ViewM,ViewP,ViewU,View>::reschedule(Space& home) {
114 m.reschedule(home,*this,Int::PC_INT_DOM);
115 s.reschedule(home,*this,Int::PC_INT_BND);
116 p.reschedule(home,*this,Int::PC_INT_BND);
117 e.reschedule(home,*this,Int::PC_INT_BND);
118 u.reschedule(home,*this,Int::PC_INT_BND);
119 }
120
121 template<class ViewM, class ViewP, class ViewU, class View>
122 Actor*
123 Val<ViewM,ViewP,ViewU,View>::copy(Space& home) {
124 return new (home) Val<ViewM,ViewP,ViewU,View>(home,*this);
125 }
126
127 /// Types of events for the sweep-line
128 typedef enum {EVENT_CHCK, EVENT_PROF, EVENT_PRUN} ev_t;
129 /// An event collects the information for one evnet for the sweep-line
130 class Event
131 {
132 public:
133 /// The type of the event
134 ev_t e;
135 /// The task this event refers to
136 int task;
137 /// The date of this event
138 int date;
139 /// The quantity changed by this event (if any)
140 int inc;
141 /** If the type is EVENT_PROF and it is the first of the pair,
142 * this value is true. Added to handle contribution-values
143 * correctly for both at_most and at_least.
144 */
145 bool first_prof;
146
147 /// Simple constructor
148 Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
149 : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
150 {}
151
152 // Default constructor for region-allocated memory
153 Event(void) {}
154
155 /// Order events based on date.
156 bool operator <(const Event& ev) const {
157 if (date == ev.date) {
158 if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
159 if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
160 return false;
161 }
162 return date < ev.date;
163 }
164 };
165
166 template<class ViewM, class ViewP, class ViewU, class View>
167 ExecStatus
168 Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
169 int ntask, int su,
170 int* contribution,
171 int* prune_tasks, int& prune_tasks_size) {
172
173 if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
174 return ES_FAILED;
175 }
176
177 int pti = 0;
178 while (pti != prune_tasks_size) {
179 int t = prune_tasks[pti];
180
181 // Algorithm 2.
182 // Prune the machine, start, and end for required
183 // tasks for machine r that have heights possibly greater than 0.
184 if (ntask != 0 &&
185 (at_most ? u[t].min() < 0
186 : u[t].max() > 0) &&
187 (at_most ? su-contribution[t] > c[r]
188 : su-contribution[t] < c[r])) {
189 if (me_failed(m[t].eq(home, r))||
190 me_failed(s[t].gq(home, up-p[t].max()+1))||
191 me_failed(s[t].lq(home, low))||
192 me_failed(e[t].lq(home,low+p[t].max()))||
193 me_failed(e[t].gq(home, up+1))||
194 me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
195 ) {
196 return ES_FAILED;
197 }
198 }
199
200 // Algorithm 3.
201 // Remove values that prevent us from reaching the limit
202 if (at_most ? u[t].min() > std::min(0, c[r])
203 : u[t].max() < std::max(0, c[r])) {
204 if (at_most ? su-contribution[t]+u[t].min() > c[r]
205 : su-contribution[t]+u[t].max() < c[r]) {
206 if (e[t].min() > low &&
207 s[t].max() <= up &&
208 p[t].min() > 0) {
209 if (me_failed(m[t].nq(home, r))) {
210 return ES_FAILED;
211 }
212 } else if (m[t].assigned()) {
213 int ptmin = p[t].min();
214 if (ptmin > 0) {
215 Iter::Ranges::Singleton
216 a(low-ptmin+1, up), b(low+1, up+ptmin);
217 if (me_failed(s[t].minus_r(home,a,false)) ||
218 me_failed(e[t].minus_r(home, b,false)))
219 return ES_FAILED;
220 }
221 if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
222 e[t].max()-up-1),
223 0)))) {
224 return ES_FAILED;
225 }
226 }
227 }
228 }
229
230 // Algorithm 4.
231 // Remove bad negative values from for-sure heights.
232 /* \note "It is not sufficient to only test for assignment of machine[t]
233 * since Algorithm 3 can remove the value." Check this against
234 * the conditions for Alg3.
235 */
236 if (m[t].assigned() &&
237 m[t].val() == r &&
238 e[t].min() > low &&
239 s[t].max() <= up &&
240 p[t].min() > 0 ) {
241 if (me_failed(at_most
242 ? u[t].lq(home, c[r]-su+contribution[t])
243 : u[t].gq(home, c[r]-su+contribution[t]))) {
244 return ES_FAILED;
245 }
246 }
247
248 // Remove tasks that are no longer relevant.
249 if (!m[t].in(r) || (e[t].max() <= up+1)) {
250 prune_tasks[pti] = prune_tasks[--prune_tasks_size];
251 } else {
252 ++pti;
253 }
254 }
255
256 return ES_OK;
257 }
258
259 namespace {
260 template<class C>
261 class Less {
262 public:
263 bool operator ()(const C& lhs, const C& rhs) {
264 return lhs < rhs;
265 }
266 };
267 }
268
269 template<class ViewM, class ViewP, class ViewU, class View>
270 ExecStatus
271 Val<ViewM,ViewP,ViewU,View>::propagate(Space& home, const ModEventDelta&) {
272 // Check for subsumption
273 bool subsumed = true;
274 for (int t=0; t<s.size(); t++)
275 if (!(p[t].assigned() && e[t].assigned() &&
276 m[t].assigned() && s[t].assigned() &&
277 u[t].assigned())) {
278 subsumed = false;
279 break;
280 }
281 // Propagate information for machine r
282 Region region;
283 Event *events = region.alloc<Event>(s.size()*8);
284 int events_size;
285 int *prune_tasks = region.alloc<int>(s.size());
286 int prune_tasks_size;
287 int *contribution = region.alloc<int>(s.size());
288 for (int r = c.size(); r--; ) {
289 events_size = 0;
290#define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
291 events[events_size++] = E
292
293 // Find events for sweep-line
294 for (int t = s.size(); t--; ) {
295 if (m[t].assigned() &&
296 m[t].val() == r &&
297 s[t].max() < e[t].min()) {
298 if (at_most
299 ? u[t].min() > std::min(0, c[r])
300 : u[t].max() < std::max(0, c[r])) {
301 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, s[t].max(), 1));
302 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, e[t].min(), -1));
303 }
304 if (at_most
305 ? u[t].min() > 0
306 : u[t].max() < 0) {
307 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].max(),
308 at_most ? u[t].min() : u[t].max(), true));
309 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].min(),
310 at_most ? -u[t].min() : -u[t].max()));
311 }
312 }
313
314 if (m[t].in(r)) {
315 if (at_most
316 ? u[t].min() < 0
317 : u[t].max() > 0) {
318 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, s[t].min(),
319 at_most ? u[t].min() : u[t].max(), true));
320 GECODE_PUSH_EVENTS(Event(EVENT_PROF, t, e[t].max(),
321 at_most ? -u[t].min() : -u[t].max()));
322 }
323 if (!(m[t].assigned() &&
324 u[t].assigned() &&
325 s[t].assigned() &&
326 e[t].assigned())) {
327 GECODE_PUSH_EVENTS(Event(EVENT_PRUN, t, s[t].min()));
328 }
329 }
330 }
331#undef GECODE_PUSH_EVENTS
332
333 // If there are no events, continue with next machine
334 if (events_size == 0) {
335 continue;
336 }
337
338 // Sort the events according to date
339 Less<Event> less;
340 Support::insertion(&events[0], events_size, less);
341
342 // Sweep line along d, starting at 0
343 int d = 0;
344 int ntask = 0;
345 int su = 0;
346 int ei = 0;
347
348 prune_tasks_size = 0;
349 for (int i = s.size(); i--; ) contribution[i] = 0;
350
351 d = events[ei].date;
352 while (ei < events_size) {
353 if (events[ei].e != EVENT_PRUN) {
354 if (d != events[ei].date) {
355 GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
356 ntask, su,
357 contribution, prune_tasks, prune_tasks_size));
358 d = events[ei].date;
359 }
360 if (events[ei].e == EVENT_CHCK) {
361 ntask += events[ei].inc;
362 } else /* if (events[ei].e == EVENT_PROF) */ {
363 su += events[ei].inc;
364 if(events[ei].first_prof)
365 contribution[events[ei].task] = at_most
366 ? std::max(contribution[events[ei].task], events[ei].inc)
367 : std::min(contribution[events[ei].task], events[ei].inc);
368 }
369 } else /* if (events[ei].e == EVENT_PRUN) */ {
370 assert(prune_tasks_size<s.size());
371 prune_tasks[prune_tasks_size++] = events[ei].task;
372 }
373 ei++;
374 }
375
376 GECODE_ES_CHECK(prune(home, d, d, r,
377 ntask, su,
378 contribution, prune_tasks, prune_tasks_size));
379 }
380 return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
381 }
382
383}}}
384
385// STATISTICS: int-prop