Generated on Sat Feb 7 2015 02:01:15 for Gecode by doxygen 1.8.9.1
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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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>
73  ::post(Home home, const ViewArray<ViewM>& m,
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  Actor*
119  return new (home) Val<ViewM,ViewP,ViewU,View>(home,share,*this);
120  }
121 
125  class Event
126  {
127  public:
131  int task;
133  int date;
135  int inc;
141 
143  Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
144  : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
145  {}
146 
147  // Default constructor for region-allocated memory
148  Event(void) {}
149 
151  bool operator <(const Event& ev) const {
152  if (date == ev.date) {
153  if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
154  if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
155  return false;
156  }
157  return date < ev.date;
158  }
159  };
160 
161  template<class ViewM, class ViewP, class ViewU, class View>
162  ExecStatus
163  Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
164  int ntask, int su,
165  int* contribution,
166  int* prune_tasks, int& prune_tasks_size) {
167 
168  if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
169  return ES_FAILED;
170  }
171 
172  int pti = 0;
173  while (pti != prune_tasks_size) {
174  int t = prune_tasks[pti];
175 
176  // Algorithm 2.
177  // Prune the machine, start, and end for required
178  // tasks for machine r that have heights possibly greater than 0.
179  if (ntask != 0 &&
180  (at_most ? u[t].min() < 0
181  : u[t].max() > 0) &&
182  (at_most ? su-contribution[t] > c[r]
183  : su-contribution[t] < c[r])) {
184  if (me_failed(m[t].eq(home, r))||
185  me_failed(s[t].gq(home, up-p[t].max()+1))||
186  me_failed(s[t].lq(home, low))||
187  me_failed(e[t].lq(home,low+p[t].max()))||
188  me_failed(e[t].gq(home, up+1))||
189  me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
190  ) {
191  return ES_FAILED;
192  }
193  }
194 
195  // Algorithm 3.
196  // Remove values that prevent us from reaching the limit
197  if (at_most ? u[t].min() > std::min(0, c[r])
198  : u[t].max() < std::max(0, c[r])) {
199  if (at_most ? su-contribution[t]+u[t].min() > c[r]
200  : su-contribution[t]+u[t].max() < c[r]) {
201  if (e[t].min() > low &&
202  s[t].max() <= up &&
203  p[t].min() > 0) {
204  if (me_failed(m[t].nq(home, r))) {
205  return ES_FAILED;
206  }
207  } else if (m[t].assigned()) {
208  int ptmin = p[t].min();
209  if (ptmin > 0) {
211  a(low-ptmin+1, up), b(low+1, up+ptmin);
212  if (me_failed(s[t].minus_r(home,a,false)) ||
213  me_failed(e[t].minus_r(home, b,false)))
214  return ES_FAILED;
215  }
216  if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
217  e[t].max()-up-1),
218  0)))) {
219  return ES_FAILED;
220  }
221  }
222  }
223  }
224 
225  // Algorithm 4.
226  // Remove bad negative values from for-sure heights.
227  /* \note "It is not sufficient to only test for assignment of machine[t]
228  * since Algorithm 3 can remove the value." Check this against
229  * the conditions for Alg3.
230  */
231  if (m[t].assigned() &&
232  m[t].val() == r &&
233  e[t].min() > low &&
234  s[t].max() <= up &&
235  p[t].min() > 0 ) {
236  if (me_failed(at_most
237  ? u[t].lq(home, c[r]-su+contribution[t])
238  : u[t].gq(home, c[r]-su+contribution[t]))) {
239  return ES_FAILED;
240  }
241  }
242 
243  // Remove tasks that are no longer relevant.
244  if (!m[t].in(r) || (e[t].max() <= up+1)) {
245  prune_tasks[pti] = prune_tasks[--prune_tasks_size];
246  } else {
247  ++pti;
248  }
249  }
250 
251  return ES_OK;
252  }
253 
254  namespace {
255  template<class C>
256  class Less {
257  public:
258  bool operator ()(const C& lhs, const C& rhs) {
259  return lhs < rhs;
260  }
261  };
262  }
263 
264  template<class ViewM, class ViewP, class ViewU, class View>
265  ExecStatus
267  // Check for subsumption
268  bool subsumed = true;
269  for (int t = s.size(); t--; )
270  if (!(p[t].assigned() && e[t].assigned() &&
271  m[t].assigned() && s[t].assigned() &&
272  u[t].assigned())) {
273  subsumed = false;
274  break;
275  }
276  // Propagate information for machine r
277  Region region(home);
278  Event *events = region.alloc<Event>(s.size()*8);
279  int events_size;
280  int *prune_tasks = region.alloc<int>(s.size());
281  int prune_tasks_size;
282  int *contribution = region.alloc<int>(s.size());
283  for (int r = c.size(); r--; ) {
284  events_size = 0;
285 #define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
286  events[events_size++] = E
287 
288  // Find events for sweep-line
289  for (int t = s.size(); t--; ) {
290  if (m[t].assigned() &&
291  m[t].val() == r &&
292  s[t].max() < e[t].min()) {
293  if (at_most
294  ? u[t].min() > std::min(0, c[r])
295  : u[t].max() < std::max(0, c[r])) {
297  GECODE_PUSH_EVENTS(Event(EVENT_CHCK, t, e[t].min(), -1));
298  }
299  if (at_most
300  ? u[t].min() > 0
301  : u[t].max() < 0) {
303  at_most ? u[t].min() : u[t].max(), true));
305  at_most ? -u[t].min() : -u[t].max()));
306  }
307  }
308 
309  if (m[t].in(r)) {
310  if (at_most
311  ? u[t].min() < 0
312  : u[t].max() > 0) {
314  at_most ? u[t].min() : u[t].max(), true));
316  at_most ? -u[t].min() : -u[t].max()));
317  }
318  if (!(m[t].assigned() &&
319  u[t].assigned() &&
320  s[t].assigned() &&
321  e[t].assigned())) {
323  }
324  }
325  }
326 #undef GECODE_PUSH_EVENTS
327 
328  // If there are no events, continue with next machine
329  if (events_size == 0) {
330  continue;
331  }
332 
333  // Sort the events according to date
334  Less<Event> less;
335  Support::insertion(&events[0], events_size, less);
336 
337  // Sweep line along d, starting at 0
338  int d = 0;
339  int ntask = 0;
340  int su = 0;
341  int ei = 0;
342 
343  prune_tasks_size = 0;
344  for (int i = s.size(); i--; ) contribution[i] = 0;
345 
346  d = events[ei].date;
347  while (ei < events_size) {
348  if (events[ei].e != EVENT_PRUN) {
349  if (d != events[ei].date) {
350  GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
351  ntask, su,
352  contribution, prune_tasks, prune_tasks_size));
353  d = events[ei].date;
354  }
355  if (events[ei].e == EVENT_CHCK) {
356  ntask += events[ei].inc;
357  } else /* if (events[ei].e == EVENT_PROF) */ {
358  su += events[ei].inc;
359  if(events[ei].first_prof)
360  contribution[events[ei].task] = at_most
361  ? std::max(contribution[events[ei].task], events[ei].inc)
362  : std::min(contribution[events[ei].task], events[ei].inc);
363  }
364  } else /* if (events[ei].e == EVENT_PRUN) */ {
365  assert(prune_tasks_size<s.size());
366  prune_tasks[prune_tasks_size++] = events[ei].task;
367  }
368  ei++;
369  }
370 
371  GECODE_ES_CHECK(prune(home, d, d, r,
372  ntask, su,
373  contribution, prune_tasks, prune_tasks_size));
374  }
375  return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
376  }
377 
378 }}}
379 
380 // 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:163
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
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:4032
bool operator<(const Event &ev) const
Order events based on date.
Definition: val.hpp:151
Range iterator for singleton range.
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
ev_t e
The type of the event.
Definition: val.hpp:129
Actor must always be disposed.
Definition: core.hpp:610
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
int date
The date of this event.
Definition: val.hpp:133
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:57
ev_t
Types of events for the sweep-line.
Definition: val.hpp:123
Base-class for propagators.
Definition: core.hpp:755
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:1362
ExecStatus prune(Space &home, ViewArray< VX > &x, ConstIntView)
Definition: rel.hpp:245
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3442
Base-class for both propagators and branchers.
Definition: core.hpp:666
Gecode::IntSet d(v, 7)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low quadratic)
Definition: val.hpp:112
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
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:131
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
FloatVal min(const FloatNum &x, const FloatVal &y)
Definition: val.hpp:410
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
virtual size_t dispose(Space &home)
Dispose propagator.
Definition: val.hpp:96
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:266
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 notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:2849
An event collects the information for one evnet for the sweep-line.
Definition: val.hpp:125
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
void update(Space &home, bool share, SharedHandle &sh)
Updating during cloning.
Definition: core.hpp:2656
Event(ev_t _e, int _task, int _date, int _inc=0, bool _first_prof=false)
Simple constructor.
Definition: val.hpp:143
ExecStatus subsumed(Space &home, Propagator &p, TaskArray< Task > &t)
Check tasks t for subsumption.
Definition: subsumption.hpp:42
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:169
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
Multi _e(Gecode::IntArgs(4, 4, 2, 3, 1))
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
void insertion(Type *l, Type *r, Less &less)
Standard insertion sort.
Definition: sort.hpp:101
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition: val.hpp:82
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
int inc
The quantity changed by this event (if any)
Definition: val.hpp:135
Gecode toplevel namespace
#define GECODE_PUSH_EVENTS(E)
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: val.hpp:118
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
Multi _c(Gecode::IntArgs(3, 1, 2, 3))