Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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 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>
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;
146
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
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>
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) {
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>
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])) {
303 }
304 if (at_most
305 ? u[t].min() > 0
306 : u[t].max() < 0) {
308 at_most ? u[t].min() : u[t].max(), true));
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) {
319 at_most ? u[t].min() : u[t].max(), true));
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())) {
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
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
NodeType t
Type of node.
int p
Number of positive literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
An event collects the information for one evnet for the sweep-line.
Definition val.hpp:131
int date
The date of this event.
Definition val.hpp:138
Event(ev_t _e, int _task, int _date, int _inc=0, bool _first_prof=false)
Simple constructor.
Definition val.hpp:148
int task
The task this event refers to.
Definition val.hpp:136
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:156
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:271
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:168
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:486
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
Base-class for propagators.
Definition core.hpp:1064
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.
Computation spaces.
Definition core.hpp:1742
View arrays.
Definition array.hpp:253
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition array.hpp:1328
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition array.hpp:1341
View & operator()(View &x)
Integer-precision integer scale view.
Definition view.hpp:632
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
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:562
#define GECODE_PUSH_EVENTS(E)
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.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition sort.hpp:97
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
#define forceinline
Definition config.hpp:187