Generated on Sat Jan 20 2018 22:21:11 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15137 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <algorithm>
39 
40 /*
41  * This is the propagation algorithm of the cumulatives constraint as
42  * presented in:
43  * Nicolas Beldiceanu and Mats Carlsson, A New Multi-resource cumulatives
44  * Constraint with Negative Heights. CP 2002, pages 63-79, Springer-Verlag.
45  */
46 
47 namespace Gecode { namespace Int { namespace Cumulatives {
48 
49  template<class ViewM, class ViewP, class ViewU, class View>
52  const ViewArray<ViewM>& _m,
53  const ViewArray<View>& _s,
54  const ViewArray<ViewP>& _p,
55  const ViewArray<View>& _e,
56  const ViewArray<ViewU>& _u,
57  const SharedArray<int>& _c,
58  bool _at_most) :
59  Propagator(home),
60  m(_m), s(_s), p(_p), e(_e), u(_u), c(_c), at_most(_at_most) {
61  home.notice(*this,AP_DISPOSE);
62 
63  m.subscribe(home,*this,Int::PC_INT_DOM);
64  s.subscribe(home,*this,Int::PC_INT_BND);
65  p.subscribe(home,*this,Int::PC_INT_BND);
66  e.subscribe(home,*this,Int::PC_INT_BND);
67  u.subscribe(home,*this,Int::PC_INT_BND);
68  }
69 
70  template<class ViewM, class ViewP, class ViewU, class View>
74  const ViewArray<View>& s, const ViewArray<ViewP>& p,
75  const ViewArray<View>& e, const ViewArray<ViewU>& u,
76  const SharedArray<int>& c, bool at_most) {
77  (void) new (home) Val(home, m,s,p,e,u,c,at_most);
78  return ES_OK;
79  }
80 
81  template<class ViewM, class ViewP, class ViewU, class View>
85  : Propagator(home,share,vp), at_most(vp.at_most) {
86  m.update(home,share,vp.m);
87  s.update(home, share, vp.s);
88  p.update(home, share, vp.p);
89  e.update(home, share, vp.e);
90  u.update(home, share, vp.u);
91  c.update(home, share, vp.c);
92  }
93 
94  template<class ViewM, class ViewP, class ViewU, class View>
95  size_t
97  home.ignore(*this,AP_DISPOSE);
98  if (!home.failed()) {
99  m.cancel(home,*this,Int::PC_INT_DOM);
100  s.cancel(home,*this,Int::PC_INT_BND);
101  p.cancel(home,*this,Int::PC_INT_BND);
102  e.cancel(home,*this,Int::PC_INT_BND);
103  u.cancel(home,*this,Int::PC_INT_BND);
104  }
105  c.~SharedArray();
106  (void) Propagator::dispose(home);
107  return sizeof(*this);
108  }
109 
110  template<class ViewM, class ViewP, class ViewU, class View>
111  PropCost
113  return PropCost::quadratic(PropCost::LO, s.size());
114  }
115 
116  template<class ViewM, class ViewP, class ViewU, class View>
117  void
119  m.reschedule(home,*this,Int::PC_INT_DOM);
120  s.reschedule(home,*this,Int::PC_INT_BND);
121  p.reschedule(home,*this,Int::PC_INT_BND);
122  e.reschedule(home,*this,Int::PC_INT_BND);
123  u.reschedule(home,*this,Int::PC_INT_BND);
124  }
125 
126  template<class ViewM, class ViewP, class ViewU, class View>
127  Actor*
129  return new (home) Val<ViewM,ViewP,ViewU,View>(home,share,*this);
130  }
131 
135  class Event
136  {
137  public:
139  ev_t e;
141  int task;
143  int date;
145  int inc;
151 
153  Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
154  : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
155  {}
156 
157  // Default constructor for region-allocated memory
158  Event(void) {}
159 
161  bool operator <(const Event& ev) const {
162  if (date == ev.date) {
163  if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
164  if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
165  return false;
166  }
167  return date < ev.date;
168  }
169  };
170 
171  template<class ViewM, class ViewP, class ViewU, class View>
172  ExecStatus
173  Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
174  int ntask, int su,
175  int* contribution,
176  int* prune_tasks, int& prune_tasks_size) {
177 
178  if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
179  return ES_FAILED;
180  }
181 
182  int pti = 0;
183  while (pti != prune_tasks_size) {
184  int t = prune_tasks[pti];
185 
186  // Algorithm 2.
187  // Prune the machine, start, and end for required
188  // tasks for machine r that have heights possibly greater than 0.
189  if (ntask != 0 &&
190  (at_most ? u[t].min() < 0
191  : u[t].max() > 0) &&
192  (at_most ? su-contribution[t] > c[r]
193  : su-contribution[t] < c[r])) {
194  if (me_failed(m[t].eq(home, r))||
195  me_failed(s[t].gq(home, up-p[t].max()+1))||
196  me_failed(s[t].lq(home, low))||
197  me_failed(e[t].lq(home,low+p[t].max()))||
198  me_failed(e[t].gq(home, up+1))||
199  me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
200  ) {
201  return ES_FAILED;
202  }
203  }
204 
205  // Algorithm 3.
206  // Remove values that prevent us from reaching the limit
207  if (at_most ? u[t].min() > std::min(0, c[r])
208  : u[t].max() < std::max(0, c[r])) {
209  if (at_most ? su-contribution[t]+u[t].min() > c[r]
210  : su-contribution[t]+u[t].max() < c[r]) {
211  if (e[t].min() > low &&
212  s[t].max() <= up &&
213  p[t].min() > 0) {
214  if (me_failed(m[t].nq(home, r))) {
215  return ES_FAILED;
216  }
217  } else if (m[t].assigned()) {
218  int ptmin = p[t].min();
219  if (ptmin > 0) {
221  a(low-ptmin+1, up), b(low+1, up+ptmin);
222  if (me_failed(s[t].minus_r(home,a,false)) ||
223  me_failed(e[t].minus_r(home, b,false)))
224  return ES_FAILED;
225  }
226  if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
227  e[t].max()-up-1),
228  0)))) {
229  return ES_FAILED;
230  }
231  }
232  }
233  }
234 
235  // Algorithm 4.
236  // Remove bad negative values from for-sure heights.
237  /* \note "It is not sufficient to only test for assignment of machine[t]
238  * since Algorithm 3 can remove the value." Check this against
239  * the conditions for Alg3.
240  */
241  if (m[t].assigned() &&
242  m[t].val() == r &&
243  e[t].min() > low &&
244  s[t].max() <= up &&
245  p[t].min() > 0 ) {
246  if (me_failed(at_most
247  ? u[t].lq(home, c[r]-su+contribution[t])
248  : u[t].gq(home, c[r]-su+contribution[t]))) {
249  return ES_FAILED;
250  }
251  }
252 
253  // Remove tasks that are no longer relevant.
254  if (!m[t].in(r) || (e[t].max() <= up+1)) {
255  prune_tasks[pti] = prune_tasks[--prune_tasks_size];
256  } else {
257  ++pti;
258  }
259  }
260 
261  return ES_OK;
262  }
263 
264  namespace {
265  template<class C>
266  class Less {
267  public:
268  bool operator ()(const C& lhs, const C& rhs) {
269  return lhs < rhs;
270  }
271  };
272  }
273 
274  template<class ViewM, class ViewP, class ViewU, class View>
275  ExecStatus
277  // Check for subsumption
278  bool subsumed = true;
279  for (int t = s.size(); t--; )
280  if (!(p[t].assigned() && e[t].assigned() &&
281  m[t].assigned() && s[t].assigned() &&
282  u[t].assigned())) {
283  subsumed = false;
284  break;
285  }
286  // Propagate information for machine r
287  Region region(home);
288  Event *events = region.alloc<Event>(s.size()*8);
289  int events_size;
290  int *prune_tasks = region.alloc<int>(s.size());
291  int prune_tasks_size;
292  int *contribution = region.alloc<int>(s.size());
293  for (int r = c.size(); r--; ) {
294  events_size = 0;
295 #define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
296  events[events_size++] = E
297 
298  // Find events for sweep-line
299  for (int t = s.size(); t--; ) {
300  if (m[t].assigned() &&
301  m[t].val() == r &&
302  s[t].max() < e[t].min()) {
303  if (at_most
304  ? u[t].min() > std::min(0, c[r])
305  : u[t].max() < std::max(0, c[r])) {
308  }
309  if (at_most
310  ? u[t].min() > 0
311  : u[t].max() < 0) {
313  at_most ? u[t].min() : u[t].max(), true));
315  at_most ? -u[t].min() : -u[t].max()));
316  }
317  }
318 
319  if (m[t].in(r)) {
320  if (at_most
321  ? u[t].min() < 0
322  : u[t].max() > 0) {
324  at_most ? u[t].min() : u[t].max(), true));
326  at_most ? -u[t].min() : -u[t].max()));
327  }
328  if (!(m[t].assigned() &&
329  u[t].assigned() &&
330  s[t].assigned() &&
331  e[t].assigned())) {
333  }
334  }
335  }
336 #undef GECODE_PUSH_EVENTS
337 
338  // If there are no events, continue with next machine
339  if (events_size == 0) {
340  continue;
341  }
342 
343  // Sort the events according to date
344  Less<Event> less;
345  Support::insertion(&events[0], events_size, less);
346 
347  // Sweep line along d, starting at 0
348  int d = 0;
349  int ntask = 0;
350  int su = 0;
351  int ei = 0;
352 
353  prune_tasks_size = 0;
354  for (int i = s.size(); i--; ) contribution[i] = 0;
355 
356  d = events[ei].date;
357  while (ei < events_size) {
358  if (events[ei].e != EVENT_PRUN) {
359  if (d != events[ei].date) {
360  GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
361  ntask, su,
362  contribution, prune_tasks, prune_tasks_size));
363  d = events[ei].date;
364  }
365  if (events[ei].e == EVENT_CHCK) {
366  ntask += events[ei].inc;
367  } else /* if (events[ei].e == EVENT_PROF) */ {
368  su += events[ei].inc;
369  if(events[ei].first_prof)
370  contribution[events[ei].task] = at_most
371  ? std::max(contribution[events[ei].task], events[ei].inc)
372  : std::min(contribution[events[ei].task], events[ei].inc);
373  }
374  } else /* if (events[ei].e == EVENT_PRUN) */ {
375  assert(prune_tasks_size<s.size());
376  prune_tasks[prune_tasks_size++] = events[ei].task;
377  }
378  ei++;
379  }
380 
381  GECODE_ES_CHECK(prune(home, d, d, r,
382  ntask, su,
383  contribution, prune_tasks, prune_tasks_size));
384  }
385  return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
386  }
387 
388 }}}
389 
390 // STATISTICS: int-prop
FloatVal max(const FloatNum &x, const FloatVal &y)
Definition: val.hpp:398
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:173
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1429
NodeType t
Type of node.
Definition: bool-expr.cpp:234
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition: core.hpp:4832
union Gecode::@579::NNF::@61 u
Union depending on nodetype t.
Range iterator for singleton range.
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
ev_t e
The type of the event.
Definition: val.hpp:139
Actor must always be disposed.
Definition: core.hpp:630
int date
The date of this event.
Definition: val.hpp:143
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:42
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
ev_t
Types of events for the sweep-line.
Definition: val.hpp:133
Base-class for propagators.
Definition: core.hpp:1092
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
Multi _c(Gecode::IntArgs(3, 1, 2, 3))
Handle to region.
Definition: region.hpp:61
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:73
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
Gecode::IntSet d(v, 7)
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int task
The task this event refers to.
Definition: val.hpp:141
Execution has resulted in failure.
Definition: core.hpp:542
FloatVal min(const FloatNum &x, const FloatVal &y)
Definition: val.hpp:410
int size(void) const
Return number of elements.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:4095
virtual size_t dispose(Space &home)
Dispose propagator.
Definition: val.hpp:96
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: val.hpp:276
Val(Space &home, bool share, Val< ViewM, ViewP, ViewU, View > &p)
Definition: val.hpp:83
Propagator for the cumulatives constraint
Definition: cumulatives.hh:90
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1408
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3321
An event collects the information for one evnet for the sweep-line.
Definition: val.hpp:135
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:3127
Event(ev_t _e, int _task, int _date, int _inc=0, bool _first_prof=false)
Simple constructor.
Definition: val.hpp:153
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low quadratic)
Definition: val.hpp:112
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:4141
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:173
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition: sort.hpp:101
virtual void reschedule(Space &home)
Schedule function.
Definition: val.hpp:118
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
bool operator<(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:230
int inc
The quantity changed by this event (if any)
Definition: val.hpp:145
Gecode toplevel namespace
#define GECODE_PUSH_EVENTS(E)
Multi _e(Gecode::IntArgs(4, 4, 2, 3, 1))
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: val.hpp:128
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58