Generated on for Gecode by doxygen 1.17.0
val.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2005
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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>
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>
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>
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
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>
108 return PropCost::quadratic(PropCost::LO, s.size());
109 }
110
111 template<class ViewM, class ViewP, class ViewU, class View>
112 void
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*
124 return new (home) Val<ViewM,ViewP,ViewU,View>(home,*this);
125 }
126
130 class Event
131 {
132 public:
136 int task;
138 int date;
140 int inc;
142 Event(ev_t _e, int _task, int _date, int _inc = 0)
143 : e(_e), task(_task), date(_date), inc(_inc)
144 {}
145
146 // Default constructor for region-allocated memory
147 Event(void) {}
148
150 bool operator <(const Event& ev) const {
151 if (date == ev.date) {
152 if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
153 if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
154 return false;
155 }
156 return date < ev.date;
157 }
158 };
159
160 template<class ViewM, class ViewP, class ViewU, class View>
162 Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
163 int ntask, int su,
164 int* contribution,
165 int* prune_tasks, int& prune_tasks_size) {
166
167 if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
168 return ES_FAILED;
169 }
170
171 int pti = 0;
172 while (pti != prune_tasks_size) {
173 int t = prune_tasks[pti];
174
175 // Algorithm 2.
176 // Prune the machine, start, and end for required
177 // tasks for machine r that have heights possibly greater than 0.
178 if (ntask != 0 &&
179 (at_most ? u[t].min() < 0
180 : u[t].max() > 0) &&
181 (at_most ? su-contribution[t] > c[r]
182 : su-contribution[t] < c[r])) {
183 if (me_failed(m[t].eq(home, r))||
184 me_failed(s[t].gq(home, up-p[t].max()+1))||
185 me_failed(s[t].lq(home, low))||
186 me_failed(e[t].lq(home,low+p[t].max()))||
187 me_failed(e[t].gq(home, up+1))||
188 me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
189 ) {
190 return ES_FAILED;
191 }
192 }
193
194 // Algorithm 3.
195 // Remove values that prevent us from reaching the limit
196 if (at_most ? u[t].min() > std::min(0, c[r])
197 : u[t].max() < std::max(0, c[r])) {
198 if (at_most ? su-contribution[t]+u[t].min() > c[r]
199 : su-contribution[t]+u[t].max() < c[r]) {
200 if (e[t].min() > low &&
201 s[t].max() <= up &&
202 p[t].min() > 0) {
203 if (me_failed(m[t].nq(home, r))) {
204 return ES_FAILED;
205 }
206 } else if (m[t].assigned()) {
207 int ptmin = p[t].min();
208 if (ptmin > 0) {
210 a(low-ptmin+1, up), b(low+1, up+ptmin);
211 if (me_failed(s[t].minus_r(home,a,false)) ||
212 me_failed(e[t].minus_r(home, b,false)))
213 return ES_FAILED;
214 }
215 if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
216 e[t].max()-up-1),
217 0)))) {
218 return ES_FAILED;
219 }
220 }
221 }
222 }
223
224 // Algorithm 4.
225 // Remove bad negative values from for-sure heights.
226 /* \note "It is not sufficient to only test for assignment of machine[t]
227 * since Algorithm 3 can remove the value." Check this against
228 * the conditions for Alg3.
229 */
230 if (m[t].assigned() &&
231 m[t].val() == r &&
232 e[t].min() > low &&
233 s[t].max() <= up &&
234 p[t].min() > 0 ) {
236 ? u[t].lq(home, c[r]-su+contribution[t])
237 : u[t].gq(home, c[r]-su+contribution[t]))) {
238 return ES_FAILED;
239 }
240 }
241
242 // Remove tasks that are no longer relevant.
243 if (!m[t].in(r) || (e[t].max() <= up+1)) {
244 prune_tasks[pti] = prune_tasks[--prune_tasks_size];
245 } else {
246 ++pti;
247 }
248 }
249
250 return ES_OK;
251 }
252
253 namespace {
254 template<class C>
255 class Less {
256 public:
257 bool operator ()(const C& lhs, const C& rhs) {
258 return lhs < rhs;
259 }
260 };
261 }
262
263 template<class ViewM, class ViewP, class ViewU, class View>
266 // Check for subsumption
267 bool subsumed = true;
268 for (int t=0; t<s.size(); t++)
269 if (!(p[t].assigned() && e[t].assigned() &&
270 m[t].assigned() && s[t].assigned() &&
271 u[t].assigned())) {
272 subsumed = false;
273 break;
274 }
275 // Propagate information for machine r
276 Region region;
277 Event *events = region.alloc<Event>(s.size()*8);
278 int events_size;
279 int *prune_tasks = region.alloc<int>(s.size());
280 int prune_tasks_size;
281 int *contribution = region.alloc<int>(s.size());
282 for (int r = c.size(); r--; ) {
283 events_size = 0;
284#define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
285 events[events_size++] = E
286
287 // Find events for sweep-line
288 for (int t = s.size(); t--; ) {
289 if (m[t].assigned() &&
290 m[t].val() == r &&
291 s[t].max() < e[t].min()) {
292 if (at_most
293 ? u[t].min() > std::min(0, c[r])
294 : u[t].max() < std::max(0, c[r])) {
296 GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, e[t].min(), -1));
297 }
298 if (at_most
299 ? u[t].min() > 0
300 : u[t].max() < 0) {
302 at_most ? u[t].min() : u[t].max()));
304 at_most ? -u[t].min() : -u[t].max()));
305 }
306 }
307
308 if (m[t].in(r)) {
309 if (at_most
310 ? u[t].min() < 0
311 : u[t].max() > 0) {
313 at_most ? u[t].min() : u[t].max()));
315 at_most ? -u[t].min() : -u[t].max()));
316 }
317 if (!(m[t].assigned() &&
318 u[t].assigned() &&
319 s[t].assigned() &&
320 e[t].assigned())) {
322 }
323 }
324 }
325#undef GECODE_PUSH_EVENTS
326
327 // If there are no events, continue with next machine
328 if (events_size == 0) {
329 continue;
330 }
331
332 // Sort the events according to date
333 Less<Event> less;
334 Support::insertion(&events[0], events_size, less);
335
336 // Sweep line along d, starting at 0
337 int d = 0;
338 int ntask = 0;
339 int su = 0;
340 int ei = 0;
341
342 prune_tasks_size = 0;
343 for (int i = s.size(); i--; ) contribution[i] = 0;
344
345 d = events[ei].date;
346 while (ei < events_size) {
347 if (events[ei].e != EVENT_PRUN) {
348 if (d != events[ei].date) {
349 GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
350 ntask, su,
351 contribution, prune_tasks, prune_tasks_size));
352 d = events[ei].date;
353 }
354 if (events[ei].e == EVENT_CHCK) {
355 ntask += events[ei].inc;
356 } else /* if (events[ei].e == EVENT_PROF) */ {
357 su += events[ei].inc;
358 contribution[events[ei].task] += events[ei].inc;
359 }
360 } else /* if (events[ei].e == EVENT_PRUN) */ {
361 assert(prune_tasks_size<s.size());
362 prune_tasks[prune_tasks_size++] = events[ei].task;
363 }
364 ei++;
365 }
366
367 GECODE_ES_CHECK(prune(home, d, d, r,
368 ntask, su,
369 contribution, prune_tasks, prune_tasks_size));
370 }
371 return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
372 }
373
374}}}
375
376// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
An event collects the information for one event for the sweep-line.
Definition val.hpp:131
int date
The date of this event.
Definition val.hpp:138
int task
The task this event refers to.
Definition val.hpp:136
Event(ev_t _e, int _task, int _date, int _inc=0)
Simple constructor.
Definition val.hpp:142
ev_t e
The type of the event.
Definition val.hpp:134
bool operator<(const Event &ev) const
Order events based on date.
Definition val.hpp:150
int inc
The quantity changed by this event (if any).
Definition val.hpp:140
Propagator for the cumulatives constraint
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition val.hpp:265
ExecStatus prune(Space &home, int low, int up, int r, int ntask, int su, int *contribution, int *prune_tasks, int &prune_tasks_size)
Definition val.hpp:162
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition val.hpp:123
virtual void reschedule(Space &home)
Schedule function.
Definition val.hpp:113
Val(Space &home, Val< ViewM, ViewP, ViewU, View > &p)
Definition val.hpp:79
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low quadratic).
Definition val.hpp:107
virtual size_t dispose(Space &home)
Dispose propagator.
Definition val.hpp:91
Range iterator for singleton range.
Propagation cost.
Definition core.hpp:493
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:5071
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Shared array with arbitrary number of elements.
View arrays.
Definition array.hpp:255
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
#define GECODE_PUSH_EVENTS(E)
Cumulatives propagators
ev_t
Types of events for the sweep-line.
Definition val.hpp:128
ModEvent prune(Space &home, View x, int v)
Exclude value v from variable view x.
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:108
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition sort.hpp:97
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
#define forceinline
Definition config.hpp:144