Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
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 
43 namespace 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>
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>
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>
106  PropCost
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>
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) {
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
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])) {
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) {
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
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3219
Event(void)
Definition: val.hpp:153
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: val.hpp:123
ev_t
Types of events for the sweep-line.
Definition: val.hpp:128
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1341
An event collects the information for one evnet for the sweep-line.
Definition: val.hpp:131
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
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
ViewArray< ViewU > u
Definition: cumulatives.hh:92
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
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:386
@ LO
Cheap.
Definition: core.hpp:513
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Computation spaces.
Definition: core.hpp:1742
Multi _c(Gecode::IntArgs({1, 2, 3}))
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:38
Base-class for both propagators and branchers.
Definition: core.hpp:628
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4787
FloatVal min(const FloatNum &x, const FloatVal &y)
Definition: val.hpp:406
#define GECODE_PUSH_EVENTS(E)
ViewArray< ViewM > m
Definition: cumulatives.hh:88
Val(Space &home, Val< ViewM, ViewP, ViewU, View > &p)
Definition: val.hpp:79
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition: sort.hpp:97
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1328
static ExecStatus post(Home home, const ViewArray< ViewM > &, const ViewArray< View > &, const ViewArray< ViewP > &, const ViewArray< View > &, const ViewArray< ViewU > &, const SharedArray< int > &, bool)
Post propagator.
Definition: val.hpp:69
virtual size_t dispose(Space &home)
Dispose propagator.
Definition: val.hpp:91
Home class for posting propagators
Definition: core.hpp:856
ViewArray< ViewP > p
Definition: cumulatives.hh:90
Handle to region.
Definition: region.hpp:55
@ AP_DISPOSE
Actor must always be disposed.
Definition: core.hpp:562
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
bool operator<(const Event &ev) const
Order events based on date.
Definition: val.hpp:156
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:271
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low quadratic)
Definition: val.hpp:107
virtual void reschedule(Space &home)
Schedule function.
Definition: val.hpp:113
Multi _e(Gecode::IntArgs({4, 2, 3, 1}))
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:264
ViewArray< View > s
Definition: cumulatives.hh:89
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition: val.hpp:78
@ EVENT_CHCK
Definition: val.hpp:128
@ EVENT_PROF
Definition: val.hpp:128
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4044
Propagation cost.
Definition: core.hpp:486
Propagator for the cumulatives constraint
Definition: cumulatives.hh:86
Gecode::IntSet d(v, 7)
int inc
The quantity changed by this event (if any)
Definition: val.hpp:140
#define forceinline
Definition: config.hpp:185
Range iterator for singleton range.
FloatVal max(const FloatNum &x, const FloatVal &y)
Definition: val.hpp:394
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4074
ViewArray< View > e
Definition: cumulatives.hh:91
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3252
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
int task
The task this event refers to.
Definition: val.hpp:136
Gecode::FloatVal c(-8, 8)
bool first_prof
Definition: val.hpp:145
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
Gecode::IntArgs i({1, 2, 3, 4})
@ EVENT_PRUN
Definition: val.hpp:128
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ev_t e
The type of the event.
Definition: val.hpp:134
ExecStatus
Definition: core.hpp:472