Generated on Thu Mar 16 2017 03:24:16 for Gecode by doxygen 1.8.13
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: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
13  * $Revision: 15137 $
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  void
71  x.reschedule(home,*this,pc);
72  y.reschedule(home,*this,pc);
73  }
74 
75  template<class P, class N, PropCond pc>
76  forceinline size_t
78  x.cancel(home,*this,pc);
79  y.cancel(home,*this,pc);
80  (void) Propagator::dispose(home);
81  return sizeof(*this);
82  }
83 
84 
85  /*
86  * Computing bounds
87  *
88  */
89 // template<class View>
90 // void
91 // bounds_p(Rounding& r, ModEventDelta med, ViewArray<View>& x, FloatVal& c, FloatNum& sl, FloatNum& su) {
92 // int n = x.size();
93 // if (FloatView::me(med) == ME_FLOAT_VAL) {
94 // for (int i = n; i--; ) {
95 // if (x[i].assigned()) {
96 // c -= x[i].val(); x[i] = x[--n];
97 // } else {
98 // sl = r.sub_up(sl,x[i].min()); su = r.sub_down(su,x[i].max());
99 // }
100 // }
101 // x.size(n);
102 // } else {
103 // for (int i = n; i--; ) {
104 // sl = r.sub_up(sl,x[i].min()); su = r.sub_down(su,x[i].max());
105 // }
106 // }
107 // }
108 //
109 // template<class View>
110 // void
111 // bounds_n(Rounding& r, ModEventDelta med, ViewArray<View>& y, FloatVal& c, FloatNum& sl, FloatNum& su) {
112 // int n = y.size();
113 // if (FloatView::me(med) == ME_FLOAT_VAL) {
114 // for (int i = n; i--; ) {
115 // if (y[i].assigned()) {
116 // c += y[i].val(); y[i] = y[--n];
117 // } else {
118 // sl = r.add_up(sl,y[i].max()); su = r.add_down(su,y[i].min());
119 // }
120 // }
121 // y.size(n);
122 // } else {
123 // for (int i = n; i--; ) {
124 // sl = r.add_up(sl,y[i].max()); su = r.add_down(su,y[i].min());
125 // }
126 // }
127 // }
128 
129  template<class View>
130  void
132  int n = x.size();
133 
134  if (FloatView::me(med) == ME_FLOAT_VAL) {
135  for (int i = n; i--; ) {
136  if (x[i].assigned()) {
137  c -= x[i].val(); x[i] = x[--n];
138  }
139  }
140  x.size(n);
141  }
142  }
143 
144  template<class View>
145  void
147  int n = y.size();
148  if (FloatView::me(med) == ME_FLOAT_VAL) {
149  for (int i = n; i--; ) {
150  if (y[i].assigned()) {
151  c += y[i].val(); y[i] = y[--n];
152  }
153  }
154  y.size(n);
155  }
156  }
157 
158  forceinline bool
159  infty(const FloatNum& n) {
160  return ((n == std::numeric_limits<FloatNum>::infinity()) ||
162  }
163 
164  /*
165  * Bound consistent linear equation
166  *
167  */
168 
169  template<class P, class N>
172  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
173 
174  template<class P, class N>
175  ExecStatus
177  (void) new (home) Eq<P,N>(home,x,y,c);
178  return ES_OK;
179  }
180 
181 
182  template<class P, class N>
184  Eq<P,N>::Eq(Space& home, bool share, Eq<P,N>& p)
185  : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
186 
187  template<class P, class N>
188  Actor*
189  Eq<P,N>::copy(Space& home, bool share) {
190  return new (home) Eq<P,N>(home,share,*this);
191  }
192 
193  template<class P, class N>
194  ExecStatus
196  // Eliminate singletons
197  Rounding r;
198  eliminate_p<P>(med, x, c);
199  eliminate_n<N>(med, y, c);
200 
201  if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
202  if (x.size() == 1) {
203  GECODE_ME_CHECK(x[0].eq(home,c));
204  return home.ES_SUBSUMED(*this);
205  }
206  if (y.size() == 1) {
207  GECODE_ME_CHECK(y[0].eq(home,-c));
208  return home.ES_SUBSUMED(*this);
209  }
210  return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
211  }
212 
213  ExecStatus es = ES_FIX;
214  bool assigned = true;
215 
216  // Propagate max bound for positive variables
217  for (int i = x.size(); i--; ) {
218  // Compute bound
219  FloatNum sl = c.max();
220  for (int j = x.size(); j--; ) {
221  if (i == j) continue;
222  sl = r.sub_up(sl,x[j].min());
223  }
224  for (int j = y.size(); j--; )
225  sl = r.add_up(sl,y[j].max());
226  ModEvent me = x[i].lq(home,sl);
227  if (me_failed(me))
228  return ES_FAILED;
229  if (me != ME_FLOAT_VAL)
230  assigned = false;
231  if (me_modified(me))
232  es = ES_NOFIX;
233  }
234  // Propagate min bound for negative variables
235  for (int i = y.size(); i--; ) {
236  // Compute bound
237  FloatNum sl = -c.max();
238  for (int j = x.size(); j--; )
239  sl = r.add_down(sl,x[j].min());
240  for (int j = y.size(); j--; ) {
241  if (i == j) continue;
242  sl = r.sub_down(sl,y[j].max());
243  }
244  ModEvent me = y[i].gq(home,sl);
245  if (me_failed(me))
246  return ES_FAILED;
247  if (me != ME_FLOAT_VAL)
248  assigned = false;
249  if (me_modified(me))
250  es = ES_NOFIX;
251  }
252 
253  // Propagate min bound for positive variables
254  for (int i = x.size(); i--; ) {
255  // Compute bound
256  FloatNum su = c.min();
257  for (int j = x.size(); j--; ) {
258  if (i == j) continue;
259  su = r.sub_down(su,x[j].max());
260  }
261  for (int j = y.size(); j--; )
262  su = r.add_down(su,y[j].min());
263  ModEvent me = x[i].gq(home,su);
264  if (me_failed(me))
265  return ES_FAILED;
266  if (me != ME_FLOAT_VAL)
267  assigned = false;
268  if (me_modified(me))
269  es = ES_NOFIX;
270  }
271  // Propagate max bound for negative variables
272  for (int i = y.size(); i--; ) {
273  // Compute bound
274  FloatNum su = -c.min();
275  for (int j = x.size(); j--; )
276  su = r.add_up(su,x[j].max());
277  for (int j = y.size(); j--; ) {
278  if (i == j) continue;
279  su = r.sub_up(su,y[j].min());
280  }
281  ModEvent me = y[i].lq(home,su);
282  if (me_failed(me))
283  return ES_FAILED;
284  if (me != ME_FLOAT_VAL)
285  assigned = false;
286  if (me_modified(me))
287  es = ES_NOFIX;
288  }
289 
290  return assigned ? home.ES_SUBSUMED(*this) : es;
291  }
292 
293 
294  /*
295  * Bound consistent linear inequation
296  *
297  */
298 
299  template<class P, class N>
302  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
303 
304  template<class P, class N>
305  ExecStatus
307  (void) new (home) Lq<P,N>(home,x,y,c);
308  return ES_OK;
309  }
310 
311  template<class P, class N>
313  Lq<P,N>::Lq(Space& home, bool share, Lq<P,N>& p)
314  : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
315 
316  template<class P, class N>
317  Actor*
318  Lq<P,N>::copy(Space& home, bool share) {
319  return new (home) Lq<P,N>(home,share,*this);
320  }
321 
322  template<class P, class N>
323  ExecStatus
325  // Eliminate singletons
326  FloatNum sl = 0.0;
327 
328  Rounding r;
329 
330  if (FloatView::me(med) == ME_FLOAT_VAL) {
331  for (int i = x.size(); i--; ) {
332  if (x[i].assigned()) {
333  c -= x[i].val(); x.move_lst(i);
334  } else {
335  sl = r.sub_up(sl,x[i].min());
336  }
337  }
338  for (int i = y.size(); i--; ) {
339  if (y[i].assigned()) {
340  c += y[i].val(); y.move_lst(i);
341  } else {
342  sl = r.add_up(sl,y[i].max());
343  }
344  }
345  if ((x.size() + y.size()) <= 1) {
346  if (x.size() == 1) {
347  GECODE_ME_CHECK(x[0].lq(home,c.max()));
348  return home.ES_SUBSUMED(*this);
349  }
350  if (y.size() == 1) {
351  GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
352  return home.ES_SUBSUMED(*this);
353  }
354  return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
355  }
356  } else {
357  for (int i = x.size(); i--; )
358  sl = r.sub_up(sl,x[i].min());
359  for (int i = y.size(); i--; )
360  sl = r.add_up(sl,y[i].max());
361  }
362 
363  sl = r.add_up(sl,c.max());
364 
365  ExecStatus es = ES_FIX;
366  bool assigned = true;
367  for (int i = x.size(); i--; ) {
368  assert(!x[i].assigned());
369  FloatNum slx = r.add_up(sl,x[i].min());
370  ModEvent me = x[i].lq(home,slx);
371  if (me == ME_FLOAT_FAILED)
372  return ES_FAILED;
373  if (me != ME_FLOAT_VAL)
374  assigned = false;
375  if (me_modified(me))
376  es = ES_NOFIX;
377  }
378 
379  for (int i = y.size(); i--; ) {
380  assert(!y[i].assigned());
381  FloatNum sly = r.sub_up(y[i].max(),sl);
382  ModEvent me = y[i].gq(home,sly);
383  if (me == ME_FLOAT_FAILED)
384  return ES_FAILED;
385  if (me != ME_FLOAT_VAL)
386  assigned = false;
387  if (me_modified(me))
388  es = ES_NOFIX;
389  }
390 
391  return assigned ? home.ES_SUBSUMED(*this) : es;
392  }
393 
394 }}}
395 
396 // STATISTICS: float-prop
397 
Propagator for bounds consistent n-ary linear equality
Definition: linear.hh:110
Lq(Space &home, bool share, Lq &p)
Constructor for cloning p.
Definition: nary.hpp:313
FloatNum add_down(FloatNum x, FloatNum y)
Return lower bound of x plus y (domain: )
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatNum c)
Post propagator for .
Definition: linear.cpp:45
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3484
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:140
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for n-ary linear propagators.
Definition: linear.hh:61
Base-class for propagators.
Definition: core.hpp:1012
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:159
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nary.hpp:195
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:541
bool in(FloatNum n) const
Test whether n is included.
Definition: val.hpp:100
Computation spaces.
Definition: core.hpp:1672
Base-class for both propagators and branchers.
Definition: core.hpp:682
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:324
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition: nary.hpp:176
Execution has resulted in failure.
Definition: core.hpp:538
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Eq(Space &home, bool share, Eq &p)
Constructor for cloning p.
Definition: nary.hpp:184
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1022
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: nary.hpp:318
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Floating point rounding policy.
Definition: float.hh:156
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1295
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:118
Float value type.
Definition: float.hh:336
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:189
Propagation cost.
Definition: core.hpp:550
ExecStatus
Definition: core.hpp:536
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.
Definition: view.hpp:502
#define forceinline
Definition: config.hpp:173
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Execution is okay.
Definition: core.hpp:540
Propagation has not computed fixpoint.
Definition: core.hpp:539
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:131
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:146
FloatNum sub_up(FloatNum x, FloatNum y)
Return upper bound of x minus y (domain: )
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:306
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Home class for posting propagators
Definition: core.hpp:905
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