Generated on Tue Jan 19 2021 06:15:49 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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 namespace Gecode { namespace Float { namespace Linear {
37 
38  /*
39  * Linear propagators
40  *
41  */
42  template<class P, class N, PropCond pc>
45  : Propagator(home), x(x0), y(y0), c(c0) {
46  x.subscribe(home,*this,pc);
47  y.subscribe(home,*this,pc);
48  }
49 
50  template<class P, class N, PropCond pc>
53  : Propagator(home,p), c(p.c) {
54  x.update(home,p.x);
55  y.update(home,p.y);
56  }
57 
58  template<class P, class N, PropCond pc>
59  PropCost
60  Lin<P,N,pc>::cost(const Space&, const ModEventDelta&) const {
61  return PropCost::linear(PropCost::LO, x.size()+y.size());
62  }
63 
64  template<class P, class N, PropCond pc>
65  void
67  x.reschedule(home,*this,pc);
68  y.reschedule(home,*this,pc);
69  }
70 
71  template<class P, class N, PropCond pc>
72  forceinline size_t
74  x.cancel(home,*this,pc);
75  y.cancel(home,*this,pc);
76  (void) Propagator::dispose(home);
77  return sizeof(*this);
78  }
79 
80 
81  template<class View>
82  void
84  int n = x.size();
85 
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  }
91  }
92  x.size(n);
93  }
94  }
95 
96  template<class View>
97  void
99  int n = y.size();
100  if (FloatView::me(med) == ME_FLOAT_VAL) {
101  for (int i = n; i--; ) {
102  if (y[i].assigned()) {
103  c += y[i].val(); y[i] = y[--n];
104  }
105  }
106  y.size(n);
107  }
108  }
109 
110  forceinline bool
111  infty(const FloatNum& n) {
112  return ((n == std::numeric_limits<FloatNum>::infinity()) ||
114  }
115 
116  /*
117  * Bound consistent linear equation
118  *
119  */
120 
121  template<class P, class N>
124  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
125 
126  template<class P, class N>
127  ExecStatus
129  (void) new (home) Eq<P,N>(home,x,y,c);
130  return ES_OK;
131  }
132 
133 
134  template<class P, class N>
137  : Lin<P,N,PC_FLOAT_BND>(home,p) {}
138 
139  template<class P, class N>
140  Actor*
142  return new (home) Eq<P,N>(home,*this);
143  }
144 
145  template<class P, class N>
146  ExecStatus
148  // Eliminate singletons
149  Rounding r;
150  eliminate_p<P>(med, x, c);
151  eliminate_n<N>(med, y, c);
152 
153  if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
154  if (x.size() == 1) {
155  GECODE_ME_CHECK(x[0].eq(home,c));
156  return home.ES_SUBSUMED(*this);
157  }
158  if (y.size() == 1) {
159  GECODE_ME_CHECK(y[0].eq(home,-c));
160  return home.ES_SUBSUMED(*this);
161  }
162  return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
163  }
164 
165  ExecStatus es = ES_FIX;
166  bool assigned = true;
167 
168  // Propagate max bound for positive variables
169  for (int i = x.size(); i--; ) {
170  // Compute bound
171  FloatNum sl = c.max();
172  for (int j = x.size(); j--; ) {
173  if (i == j) continue;
174  sl = r.sub_up(sl,x[j].min());
175  }
176  for (int j = y.size(); j--; )
177  sl = r.add_up(sl,y[j].max());
178  ModEvent me = x[i].lq(home,sl);
179  if (me_failed(me))
180  return ES_FAILED;
181  if (me != ME_FLOAT_VAL)
182  assigned = false;
183  if (me_modified(me))
184  es = ES_NOFIX;
185  }
186  // Propagate min bound for negative variables
187  for (int i = y.size(); i--; ) {
188  // Compute bound
189  FloatNum sl = -c.max();
190  for (int j = x.size(); j--; )
191  sl = r.add_down(sl,x[j].min());
192  for (int j = y.size(); j--; ) {
193  if (i == j) continue;
194  sl = r.sub_down(sl,y[j].max());
195  }
196  ModEvent me = y[i].gq(home,sl);
197  if (me_failed(me))
198  return ES_FAILED;
199  if (me != ME_FLOAT_VAL)
200  assigned = false;
201  if (me_modified(me))
202  es = ES_NOFIX;
203  }
204 
205  // Propagate min bound for positive variables
206  for (int i = x.size(); i--; ) {
207  // Compute bound
208  FloatNum su = c.min();
209  for (int j = x.size(); j--; ) {
210  if (i == j) continue;
211  su = r.sub_down(su,x[j].max());
212  }
213  for (int j = y.size(); j--; )
214  su = r.add_down(su,y[j].min());
215  ModEvent me = x[i].gq(home,su);
216  if (me_failed(me))
217  return ES_FAILED;
218  if (me != ME_FLOAT_VAL)
219  assigned = false;
220  if (me_modified(me))
221  es = ES_NOFIX;
222  }
223  // Propagate max bound for negative variables
224  for (int i = y.size(); i--; ) {
225  // Compute bound
226  FloatNum su = -c.min();
227  for (int j = x.size(); j--; )
228  su = r.add_up(su,x[j].max());
229  for (int j = y.size(); j--; ) {
230  if (i == j) continue;
231  su = r.sub_up(su,y[j].min());
232  }
233  ModEvent me = y[i].lq(home,su);
234  if (me_failed(me))
235  return ES_FAILED;
236  if (me != ME_FLOAT_VAL)
237  assigned = false;
238  if (me_modified(me))
239  es = ES_NOFIX;
240  }
241 
242  return assigned ? home.ES_SUBSUMED(*this) : es;
243  }
244 
245 
246  /*
247  * Bound consistent linear inequation
248  *
249  */
250 
251  template<class P, class N>
254  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
255 
256  template<class P, class N>
257  ExecStatus
259  (void) new (home) Lq<P,N>(home,x,y,c);
260  return ES_OK;
261  }
262 
263  template<class P, class N>
266  : Lin<P,N,PC_FLOAT_BND>(home,p) {}
267 
268  template<class P, class N>
269  Actor*
271  return new (home) Lq<P,N>(home,*this);
272  }
273 
274  template<class P, class N>
275  ExecStatus
277  // Eliminate singletons
278  FloatNum sl = 0.0;
279 
280  Rounding r;
281 
282  if (FloatView::me(med) == ME_FLOAT_VAL) {
283  for (int i = x.size(); i--; ) {
284  if (x[i].assigned()) {
285  c -= x[i].val(); x.move_lst(i);
286  } else {
287  sl = r.sub_up(sl,x[i].min());
288  }
289  }
290  for (int i = y.size(); i--; ) {
291  if (y[i].assigned()) {
292  c += y[i].val(); y.move_lst(i);
293  } else {
294  sl = r.add_up(sl,y[i].max());
295  }
296  }
297  if ((x.size() + y.size()) <= 1) {
298  if (x.size() == 1) {
299  GECODE_ME_CHECK(x[0].lq(home,c.max()));
300  return home.ES_SUBSUMED(*this);
301  }
302  if (y.size() == 1) {
303  GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
304  return home.ES_SUBSUMED(*this);
305  }
306  return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
307  }
308  } else {
309  for (int i = x.size(); i--; )
310  sl = r.sub_up(sl,x[i].min());
311  for (int i = y.size(); i--; )
312  sl = r.add_up(sl,y[i].max());
313  }
314 
315  sl = r.add_up(sl,c.max());
316 
317  ExecStatus es = ES_FIX;
318  bool assigned = true;
319  for (int i = x.size(); i--; ) {
320  assert(!x[i].assigned());
321  FloatNum slx = r.add_up(sl,x[i].min());
322  ModEvent me = x[i].lq(home,slx);
323  if (me == ME_FLOAT_FAILED)
324  return ES_FAILED;
325  if (me != ME_FLOAT_VAL)
326  assigned = false;
327  if (me_modified(me))
328  es = ES_NOFIX;
329  }
330 
331  for (int i = y.size(); i--; ) {
332  assert(!y[i].assigned());
333  FloatNum sly = r.sub_up(y[i].max(),sl);
334  ModEvent me = y[i].gq(home,sly);
335  if (me == ME_FLOAT_FAILED)
336  return ES_FAILED;
337  if (me != ME_FLOAT_VAL)
338  assigned = false;
339  if (me_modified(me))
340  es = ES_NOFIX;
341  }
342 
343  return assigned ? home.ES_SUBSUMED(*this) : es;
344  }
345 
346 }}}
347 
348 // STATISTICS: float-prop
349 
Propagator for bounds consistent n-ary linear equality
Definition: linear.hh:106
FloatNum add_down(FloatNum x, FloatNum y)
Return lower bound of x plus y (domain: )
Lq(Space &home, Lq &p)
Constructor for cloning p.
Definition: nary.hpp:265
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1569
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Propagator for bounds consistent n-ary linear less or equal
Definition: linear.hh:136
int ModEvent
Type for modification events.
Definition: core.hpp:62
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:41
Base-class for n-ary linear propagators.
Definition: linear.hh:57
Lin(Space &home, Lin< P, N, pc > &p)
Constructor for cloning p.
Definition: nary.hpp:52
Base-class for propagators.
Definition: core.hpp:1023
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:111
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nary.hpp:147
ViewArray< N > y
Array of negative views.
Definition: linear.hh:62
const Gecode::ModEvent ME_FLOAT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:264
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
bool in(FloatNum n) const
Test whether n is included.
Definition: val.hpp:96
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
Gecode::FloatVal c(-8, 8)
ViewArray< P > x
Array of positive views.
Definition: linear.hh:60
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nary.hpp:276
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition: nary.hpp:128
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Definition: core.hpp:473
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1034
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: nary.hpp:141
Floating point rounding policy.
Definition: float.hh:154
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1218
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
const int infinity
Infinity for integers.
Definition: int.hh:120
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
Float value type.
Definition: float.hh:334
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
FloatNum sub_down(FloatNum x, FloatNum y)
Return lower bound of x minus y (domain: )
virtual Actor * copy(Space &home)
Create copy during cloning.
Definition: nary.hpp:270
Propagation cost.
Definition: core.hpp:485
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
Post propagator for SetVar x
Definition: set.hh:767
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
void eliminate_p(ModEventDelta med, ViewArray< View > &x, FloatVal &c)
Definition: nary.hpp:83
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:98
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:258
Eq(Space &home, Eq &p)
Constructor for cloning p.
Definition: nary.hpp:136
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:92
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:386
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1138
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:398
Home class for posting propagators
Definition: core.hpp:853
double FloatNum
Floating point number base type.
Definition: float.hh:106
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54