Generated on Thu Apr 5 2018 19:44:19 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$ by $Author$
11  * $Revision$
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,vp), c(vp.c), at_most(vp.at_most) {
86  m.update(home,vp.m);
87  s.update(home, vp.s);
88  p.update(home, vp.p);
89  e.update(home, vp.e);
90  u.update(home, vp.u);
91  }
92 
93  template<class ViewM, class ViewP, class ViewU, class View>
94  size_t
96  home.ignore(*this,AP_DISPOSE);
97  if (!home.failed()) {
98  m.cancel(home,*this,Int::PC_INT_DOM);
99  s.cancel(home,*this,Int::PC_INT_BND);
100  p.cancel(home,*this,Int::PC_INT_BND);
101  e.cancel(home,*this,Int::PC_INT_BND);
102  u.cancel(home,*this,Int::PC_INT_BND);
103  }
104  c.~SharedArray();
105  (void) Propagator::dispose(home);
106  return sizeof(*this);
107  }
108 
109  template<class ViewM, class ViewP, class ViewU, class View>
110  PropCost
112  return PropCost::quadratic(PropCost::LO, s.size());
113  }
114 
115  template<class ViewM, class ViewP, class ViewU, class View>
116  void
118  m.reschedule(home,*this,Int::PC_INT_DOM);
119  s.reschedule(home,*this,Int::PC_INT_BND);
120  p.reschedule(home,*this,Int::PC_INT_BND);
121  e.reschedule(home,*this,Int::PC_INT_BND);
122  u.reschedule(home,*this,Int::PC_INT_BND);
123  }
124 
125  template<class ViewM, class ViewP, class ViewU, class View>
126  Actor*
128  return new (home) Val<ViewM,ViewP,ViewU,View>(home,*this);
129  }
130 
134  class Event
135  {
136  public:
138  ev_t e;
140  int task;
142  int date;
144  int inc;
150 
152  Event(ev_t _e, int _task, int _date, int _inc = 0, bool _first_prof = false)
153  : e(_e), task(_task), date(_date), inc(_inc), first_prof(_first_prof)
154  {}
155 
156  // Default constructor for region-allocated memory
157  Event(void) {}
158 
160  bool operator <(const Event& ev) const {
161  if (date == ev.date) {
162  if (e == EVENT_PROF && ev.e != EVENT_PROF) return true;
163  if (e == EVENT_CHCK && ev.e == EVENT_PRUN) return true;
164  return false;
165  }
166  return date < ev.date;
167  }
168  };
169 
170  template<class ViewM, class ViewP, class ViewU, class View>
171  ExecStatus
172  Val<ViewM,ViewP,ViewU,View>::prune(Space& home, int low, int up, int r,
173  int ntask, int su,
174  int* contribution,
175  int* prune_tasks, int& prune_tasks_size) {
176 
177  if (ntask > 0 && (at_most ? su > c[r] : su < c[r])) {
178  return ES_FAILED;
179  }
180 
181  int pti = 0;
182  while (pti != prune_tasks_size) {
183  int t = prune_tasks[pti];
184 
185  // Algorithm 2.
186  // Prune the machine, start, and end for required
187  // tasks for machine r that have heights possibly greater than 0.
188  if (ntask != 0 &&
189  (at_most ? u[t].min() < 0
190  : u[t].max() > 0) &&
191  (at_most ? su-contribution[t] > c[r]
192  : su-contribution[t] < c[r])) {
193  if (me_failed(m[t].eq(home, r))||
194  me_failed(s[t].gq(home, up-p[t].max()+1))||
195  me_failed(s[t].lq(home, low))||
196  me_failed(e[t].lq(home,low+p[t].max()))||
197  me_failed(e[t].gq(home, up+1))||
198  me_failed(p[t].gq(home,std::min(up-s[t].max()+1,e[t].min()-low)))
199  ) {
200  return ES_FAILED;
201  }
202  }
203 
204  // Algorithm 3.
205  // Remove values that prevent us from reaching the limit
206  if (at_most ? u[t].min() > std::min(0, c[r])
207  : u[t].max() < std::max(0, c[r])) {
208  if (at_most ? su-contribution[t]+u[t].min() > c[r]
209  : su-contribution[t]+u[t].max() < c[r]) {
210  if (e[t].min() > low &&
211  s[t].max() <= up &&
212  p[t].min() > 0) {
213  if (me_failed(m[t].nq(home, r))) {
214  return ES_FAILED;
215  }
216  } else if (m[t].assigned()) {
217  int ptmin = p[t].min();
218  if (ptmin > 0) {
220  a(low-ptmin+1, up), b(low+1, up+ptmin);
221  if (me_failed(s[t].minus_r(home,a,false)) ||
222  me_failed(e[t].minus_r(home, b,false)))
223  return ES_FAILED;
224  }
225  if (me_failed(p[t].lq(home,std::max(std::max(low-s[t].min(),
226  e[t].max()-up-1),
227  0)))) {
228  return ES_FAILED;
229  }
230  }
231  }
232  }
233 
234  // Algorithm 4.
235  // Remove bad negative values from for-sure heights.
236  /* \note "It is not sufficient to only test for assignment of machine[t]
237  * since Algorithm 3 can remove the value." Check this against
238  * the conditions for Alg3.
239  */
240  if (m[t].assigned() &&
241  m[t].val() == r &&
242  e[t].min() > low &&
243  s[t].max() <= up &&
244  p[t].min() > 0 ) {
245  if (me_failed(at_most
246  ? u[t].lq(home, c[r]-su+contribution[t])
247  : u[t].gq(home, c[r]-su+contribution[t]))) {
248  return ES_FAILED;
249  }
250  }
251 
252  // Remove tasks that are no longer relevant.
253  if (!m[t].in(r) || (e[t].max() <= up+1)) {
254  prune_tasks[pti] = prune_tasks[--prune_tasks_size];
255  } else {
256  ++pti;
257  }
258  }
259 
260  return ES_OK;
261  }
262 
263  namespace {
264  template<class C>
265  class Less {
266  public:
267  bool operator ()(const C& lhs, const C& rhs) {
268  return lhs < rhs;
269  }
270  };
271  }
272 
273  template<class ViewM, class ViewP, class ViewU, class View>
274  ExecStatus
276  // Check for subsumption
277  bool subsumed = true;
278  for (int t = s.size(); t--; )
279  if (!(p[t].assigned() && e[t].assigned() &&
280  m[t].assigned() && s[t].assigned() &&
281  u[t].assigned())) {
282  subsumed = false;
283  break;
284  }
285  // Propagate information for machine r
286  Region region;
287  Event *events = region.alloc<Event>(s.size()*8);
288  int events_size;
289  int *prune_tasks = region.alloc<int>(s.size());
290  int prune_tasks_size;
291  int *contribution = region.alloc<int>(s.size());
292  for (int r = c.size(); r--; ) {
293  events_size = 0;
294 #define GECODE_PUSH_EVENTS(E) assert(events_size < s.size()*8); \
295  events[events_size++] = E
296 
297  // Find events for sweep-line
298  for (int t = s.size(); t--; ) {
299  if (m[t].assigned() &&
300  m[t].val() == r &&
301  s[t].max() < e[t].min()) {
302  if (at_most
303  ? u[t].min() > std::min(0, c[r])
304  : u[t].max() < std::max(0, c[r])) {
307  }
308  if (at_most
309  ? u[t].min() > 0
310  : u[t].max() < 0) {
312  at_most ? u[t].min() : u[t].max(), true));
314  at_most ? -u[t].min() : -u[t].max()));
315  }
316  }
317 
318  if (m[t].in(r)) {
319  if (at_most
320  ? u[t].min() < 0
321  : u[t].max() > 0) {
323  at_most ? u[t].min() : u[t].max(), true));
325  at_most ? -u[t].min() : -u[t].max()));
326  }
327  if (!(m[t].assigned() &&
328  u[t].assigned() &&
329  s[t].assigned() &&
330  e[t].assigned())) {
332  }
333  }
334  }
335 #undef GECODE_PUSH_EVENTS
336 
337  // If there are no events, continue with next machine
338  if (events_size == 0) {
339  continue;
340  }
341 
342  // Sort the events according to date
343  Less<Event> less;
344  Support::insertion(&events[0], events_size, less);
345 
346  // Sweep line along d, starting at 0
347  int d = 0;
348  int ntask = 0;
349  int su = 0;
350  int ei = 0;
351 
352  prune_tasks_size = 0;
353  for (int i = s.size(); i--; ) contribution[i] = 0;
354 
355  d = events[ei].date;
356  while (ei < events_size) {
357  if (events[ei].e != EVENT_PRUN) {
358  if (d != events[ei].date) {
359  GECODE_ES_CHECK(prune(home, d, events[ei].date-1, r,
360  ntask, su,
361  contribution, prune_tasks, prune_tasks_size));
362  d = events[ei].date;
363  }
364  if (events[ei].e == EVENT_CHCK) {
365  ntask += events[ei].inc;
366  } else /* if (events[ei].e == EVENT_PROF) */ {
367  su += events[ei].inc;
368  if(events[ei].first_prof)
369  contribution[events[ei].task] = at_most
370  ? std::max(contribution[events[ei].task], events[ei].inc)
371  : std::min(contribution[events[ei].task], events[ei].inc);
372  }
373  } else /* if (events[ei].e == EVENT_PRUN) */ {
374  assert(prune_tasks_size<s.size());
375  prune_tasks[prune_tasks_size++] = events[ei].task;
376  }
377  ei++;
378  }
379 
380  GECODE_ES_CHECK(prune(home, d, d, r,
381  ntask, su,
382  contribution, prune_tasks, prune_tasks_size));
383  }
384  return subsumed ? home.ES_SUBSUMED(*this): ES_NOFIX;
385  }
386 
387 }}}
388 
389 // 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:172
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1417
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:4634
Range iterator for singleton range.
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1375
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
ev_t e
The type of the event.
Definition: val.hpp:138
Actor must always be disposed.
Definition: core.hpp:554
int date
The date of this event.
Definition: val.hpp:142
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:384
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:132
Base-class for propagators.
Definition: core.hpp:1016
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1388
Multi _c(Gecode::IntArgs(3, 1, 2, 3))
Handle to region.
Definition: region.hpp:57
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
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
Base-class for both propagators and branchers.
Definition: core.hpp:620
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
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:140
Execution has resulted in failure.
Definition: core.hpp:466
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:3914
virtual size_t dispose(Space &home)
Dispose propagator.
Definition: val.hpp:95
Val(Space &home, Val< ViewM, ViewP, ViewU, View > &p)
Definition: val.hpp:83
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:275
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
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:1396
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.hpp:3139
An event collects the information for one evnet for the sweep-line.
Definition: val.hpp:134
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Event(ev_t _e, int _task, int _date, int _inc=0, bool _first_prof=false)
Simple constructor.
Definition: val.hpp:152
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low quadratic)
Definition: val.hpp:111
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.hpp:3944
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3172
Propagation cost.
Definition: core.hpp:478
ExecStatus
Definition: core.hpp:464
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
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:117
Execution is okay.
Definition: core.hpp:468
Propagation has not computed fixpoint.
Definition: core.hpp:467
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:144
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:91
Home class for posting propagators
Definition: core.hpp:846
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: val.hpp:127
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58