Generated on Sat Feb 7 2015 02:01:16 for Gecode by doxygen 1.8.9.1
nary.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
6  *
7  * Copyright:
8  * Christian Schulte, 2003
9  * Vincent Barichard, 2012
10  *
11  * Last modified:
12  * $Date: 2013-02-13 16:01:33 +0100 (Wed, 13 Feb 2013) $ by $Author: vbarichard $
13  * $Revision: 13289 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Float { namespace Linear {
41 
42  /*
43  * Linear propagators
44  *
45  */
46  template<class P, class N, PropCond pc>
49  : Propagator(home), x(x0), y(y0), c(c0) {
50  x.subscribe(home,*this,pc);
51  y.subscribe(home,*this,pc);
52  }
53 
54  template<class P, class N, PropCond pc>
56  Lin<P,N,pc>::Lin(Space& home, bool share, Lin<P,N,pc>& p)
57  : Propagator(home,share,p), c(p.c) {
58  x.update(home,share,p.x);
59  y.update(home,share,p.y);
60  }
61 
62  template<class P, class N, PropCond pc>
63  PropCost
64  Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
65  return PropCost::linear(PropCost::LO, x.size()+y.size());
66  }
67 
68  template<class P, class N, PropCond pc>
69  forceinline size_t
71  x.cancel(home,*this,pc);
72  y.cancel(home,*this,pc);
73  (void) Propagator::dispose(home);
74  return sizeof(*this);
75  }
76 
77 
78  /*
79  * Computing bounds
80  *
81  */
82 // template<class View>
83 // void
84 // bounds_p(Rounding& r, ModEventDelta med, ViewArray<View>& x, FloatVal& c, FloatNum& sl, FloatNum& su) {
85 // int n = x.size();
86 // if (FloatView::me(med) == ME_FLOAT_VAL) {
87 // for (int i = n; i--; ) {
88 // if (x[i].assigned()) {
89 // c -= x[i].val(); x[i] = x[--n];
90 // } else {
91 // sl = r.sub_up(sl,x[i].min()); su = r.sub_down(su,x[i].max());
92 // }
93 // }
94 // x.size(n);
95 // } else {
96 // for (int i = n; i--; ) {
97 // sl = r.sub_up(sl,x[i].min()); su = r.sub_down(su,x[i].max());
98 // }
99 // }
100 // }
101 //
102 // template<class View>
103 // void
104 // bounds_n(Rounding& r, ModEventDelta med, ViewArray<View>& y, FloatVal& c, FloatNum& sl, FloatNum& su) {
105 // int n = y.size();
106 // if (FloatView::me(med) == ME_FLOAT_VAL) {
107 // for (int i = n; i--; ) {
108 // if (y[i].assigned()) {
109 // c += y[i].val(); y[i] = y[--n];
110 // } else {
111 // sl = r.add_up(sl,y[i].max()); su = r.add_down(su,y[i].min());
112 // }
113 // }
114 // y.size(n);
115 // } else {
116 // for (int i = n; i--; ) {
117 // sl = r.add_up(sl,y[i].max()); su = r.add_down(su,y[i].min());
118 // }
119 // }
120 // }
121 
122  template<class View>
123  void
125  int n = x.size();
126 
127  if (FloatView::me(med) == ME_FLOAT_VAL) {
128  for (int i = n; i--; ) {
129  if (x[i].assigned()) {
130  c -= x[i].val(); x[i] = x[--n];
131  }
132  }
133  x.size(n);
134  }
135  }
136 
137  template<class View>
138  void
140  int n = y.size();
141  if (FloatView::me(med) == ME_FLOAT_VAL) {
142  for (int i = n; i--; ) {
143  if (y[i].assigned()) {
144  c += y[i].val(); y[i] = y[--n];
145  }
146  }
147  y.size(n);
148  }
149  }
150 
151  forceinline bool
152  infty(const FloatNum& n) {
153  return ((n == std::numeric_limits<FloatNum>::infinity()) ||
155  }
156 
157  /*
158  * Bound consistent linear equation
159  *
160  */
161 
162  template<class P, class N>
165  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
166 
167  template<class P, class N>
168  ExecStatus
170  (void) new (home) Eq<P,N>(home,x,y,c);
171  return ES_OK;
172  }
173 
174 
175  template<class P, class N>
177  Eq<P,N>::Eq(Space& home, bool share, Eq<P,N>& p)
178  : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
179 
180  template<class P, class N>
181  Actor*
182  Eq<P,N>::copy(Space& home, bool share) {
183  return new (home) Eq<P,N>(home,share,*this);
184  }
185 
186  template<class P, class N>
187  ExecStatus
189  // Eliminate singletons
190  Rounding r;
191  eliminate_p<P>(med, x, c);
192  eliminate_n<N>(med, y, c);
193 
194  if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
195  if (x.size() == 1) {
196  GECODE_ME_CHECK(x[0].eq(home,c));
197  return home.ES_SUBSUMED(*this);
198  }
199  if (y.size() == 1) {
200  GECODE_ME_CHECK(y[0].eq(home,-c));
201  return home.ES_SUBSUMED(*this);
202  }
203  return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
204  }
205 
206  ExecStatus es = ES_FIX;
207  bool assigned = true;
208 
209  // Propagate max bound for positive variables
210  for (int i = x.size(); i--; ) {
211  // Compute bound
212  FloatNum sl = c.max();
213  for (int j = x.size(); j--; ) {
214  if (i == j) continue;
215  sl = r.sub_up(sl,x[j].min());
216  }
217  for (int j = y.size(); j--; )
218  sl = r.add_up(sl,y[j].max());
219  ModEvent me = x[i].lq(home,sl);
220  if (me_failed(me))
221  return ES_FAILED;
222  if (me != ME_FLOAT_VAL)
223  assigned = false;
224  if (me_modified(me))
225  es = ES_NOFIX;
226  }
227  // Propagate min bound for negative variables
228  for (int i = y.size(); i--; ) {
229  // Compute bound
230  FloatNum sl = -c.max();
231  for (int j = x.size(); j--; )
232  sl = r.add_down(sl,x[j].min());
233  for (int j = y.size(); j--; ) {
234  if (i == j) continue;
235  sl = r.sub_down(sl,y[j].max());
236  }
237  ModEvent me = y[i].gq(home,sl);
238  if (me_failed(me))
239  return ES_FAILED;
240  if (me != ME_FLOAT_VAL)
241  assigned = false;
242  if (me_modified(me))
243  es = ES_NOFIX;
244  }
245 
246  // Propagate min bound for positive variables
247  for (int i = x.size(); i--; ) {
248  // Compute bound
249  FloatNum su = c.min();
250  for (int j = x.size(); j--; ) {
251  if (i == j) continue;
252  su = r.sub_down(su,x[j].max());
253  }
254  for (int j = y.size(); j--; )
255  su = r.add_down(su,y[j].min());
256  ModEvent me = x[i].gq(home,su);
257  if (me_failed(me))
258  return ES_FAILED;
259  if (me != ME_FLOAT_VAL)
260  assigned = false;
261  if (me_modified(me))
262  es = ES_NOFIX;
263  }
264  // Propagate max bound for negative variables
265  for (int i = y.size(); i--; ) {
266  // Compute bound
267  FloatNum su = -c.min();
268  for (int j = x.size(); j--; )
269  su = r.add_up(su,x[j].max());
270  for (int j = y.size(); j--; ) {
271  if (i == j) continue;
272  su = r.sub_up(su,y[j].min());
273  }
274  ModEvent me = y[i].lq(home,su);
275  if (me_failed(me))
276  return ES_FAILED;
277  if (me != ME_FLOAT_VAL)
278  assigned = false;
279  if (me_modified(me))
280  es = ES_NOFIX;
281  }
282 
283  return assigned ? home.ES_SUBSUMED(*this) : es;
284  }
285 
286 
287  /*
288  * Bound consistent linear inequation
289  *
290  */
291 
292  template<class P, class N>
295  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
296 
297  template<class P, class N>
298  ExecStatus
300  (void) new (home) Lq<P,N>(home,x,y,c);
301  return ES_OK;
302  }
303 
304  template<class P, class N>
306  Lq<P,N>::Lq(Space& home, bool share, Lq<P,N>& p)
307  : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
308 
309  template<class P, class N>
310  Actor*
311  Lq<P,N>::copy(Space& home, bool share) {
312  return new (home) Lq<P,N>(home,share,*this);
313  }
314 
315  template<class P, class N>
316  ExecStatus
318  // Eliminate singletons
319  FloatNum sl = 0.0;
320 
321  Rounding r;
322 
323  if (FloatView::me(med) == ME_FLOAT_VAL) {
324  for (int i = x.size(); i--; ) {
325  if (x[i].assigned()) {
326  c -= x[i].val(); x.move_lst(i);
327  } else {
328  sl = r.sub_up(sl,x[i].min());
329  }
330  }
331  for (int i = y.size(); i--; ) {
332  if (y[i].assigned()) {
333  c += y[i].val(); y.move_lst(i);
334  } else {
335  sl = r.add_up(sl,y[i].max());
336  }
337  }
338  if ((x.size() + y.size()) <= 1) {
339  if (x.size() == 1) {
340  GECODE_ME_CHECK(x[0].lq(home,c.max()));
341  return home.ES_SUBSUMED(*this);
342  }
343  if (y.size() == 1) {
344  GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
345  return home.ES_SUBSUMED(*this);
346  }
347  return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
348  }
349  } else {
350  for (int i = x.size(); i--; )
351  sl = r.sub_up(sl,x[i].min());
352  for (int i = y.size(); i--; )
353  sl = r.add_up(sl,y[i].max());
354  }
355 
356  sl = r.add_up(sl,c.max());
357 
358  ExecStatus es = ES_FIX;
359  bool assigned = true;
360  for (int i = x.size(); i--; ) {
361  assert(!x[i].assigned());
362  FloatNum slx = r.add_up(sl,x[i].min());
363  ModEvent me = x[i].lq(home,slx);
364  if (me == ME_FLOAT_FAILED)
365  return ES_FAILED;
366  if (me != ME_FLOAT_VAL)
367  assigned = false;
368  if (me_modified(me))
369  es = ES_NOFIX;
370  }
371 
372  for (int i = y.size(); i--; ) {
373  assert(!y[i].assigned());
374  FloatNum sly = r.sub_up(y[i].max(),sl);
375  ModEvent me = y[i].gq(home,sly);
376  if (me == ME_FLOAT_FAILED)
377  return ES_FAILED;
378  if (me != ME_FLOAT_VAL)
379  assigned = false;
380  if (me_modified(me))
381  es = ES_NOFIX;
382  }
383 
384  return assigned ? home.ES_SUBSUMED(*this) : es;
385  }
386 
387 }}}
388 
389 // STATISTICS: float-prop
390 
Propagator for bounds consistent n-ary linear equality
Definition: linear.hh:108
Lq(Space &home, bool share, Lq &p)
Constructor for cloning p.
Definition: nary.hpp:306
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
FloatNum add_down(FloatNum x, FloatNum y)
Return lower bound of x plus y (domain: )
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Propagator for bounds consistent n-ary linear less or equal
Definition: linear.hh:138
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: nary.hpp:70
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for n-ary linear propagators.
Definition: linear.hh:61
Base-class for propagators.
Definition: core.hpp:755
const Gecode::ModEvent ME_FLOAT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:260
bool infty(const FloatNum &n)
Definition: nary.hpp:152
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nary.hpp:188
ViewArray< N > y
Array of negative views.
Definition: linear.hh:66
const Gecode::ModEvent ME_FLOAT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:264
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Gecode::FloatVal c(-8, 8)
ViewArray< P > x
Array of positive views.
Definition: linear.hh:64
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nary.hpp:317
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition: nary.hpp:169
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
Eq(Space &home, bool share, Eq &p)
Constructor for cloning p.
Definition: nary.hpp:177
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: nary.hpp:311
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low linear)
Definition: nary.hpp:64
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
Floating point rounding policy.
Definition: float.hh:137
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
const int infinity
Infinity for integers.
Definition: int.hh:117
Float value type.
Definition: float.hh:321
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
FloatNum sub_down(FloatNum x, FloatNum y)
Return lower bound of x minus y (domain: )
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: nary.hpp:182
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
bool in(FloatNum n) const
Test whether n is included.
Definition: val.hpp:100
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
#define forceinline
Definition: config.hpp:132
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
Lin(Space &home, bool share, Lin< P, N, pc > &p)
Constructor for cloning p.
Definition: nary.hpp:56
void eliminate_p(ModEventDelta med, ViewArray< View > &x, FloatVal &c)
Definition: nary.hpp:124
const Gecode::PropCond PC_FLOAT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:292
void eliminate_n(ModEventDelta med, ViewArray< View > &y, FloatVal &c)
Definition: nary.hpp:139
FloatNum sub_up(FloatNum x, FloatNum y)
Return upper bound of x minus y (domain: )
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
FloatNum add_up(FloatNum x, FloatNum y)
Return upper bound of x plus y (domain: )
Gecode toplevel namespace
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition: nary.hpp:299
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Home class for posting propagators
Definition: core.hpp:717
double FloatNum
Floating point number base type.
Definition: float.hh:108
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58