Generated on Thu Jul 25 2019 00:00:00 for Gecode by doxygen 1.8.15
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: 2017-04-04 16:15:44 +0200 (Tue, 04 Apr 2017) $ by $Author: schulte $
13  * $Revision: 15627 $
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  template<class View>
86  void
88  int n = x.size();
89 
90  if (FloatView::me(med) == ME_FLOAT_VAL) {
91  for (int i = n; i--; ) {
92  if (x[i].assigned()) {
93  c -= x[i].val(); x[i] = x[--n];
94  }
95  }
96  x.size(n);
97  }
98  }
99 
100  template<class View>
101  void
103  int n = y.size();
104  if (FloatView::me(med) == ME_FLOAT_VAL) {
105  for (int i = n; i--; ) {
106  if (y[i].assigned()) {
107  c += y[i].val(); y[i] = y[--n];
108  }
109  }
110  y.size(n);
111  }
112  }
113 
114  forceinline bool
115  infty(const FloatNum& n) {
118  }
119 
120  /*
121  * Bound consistent linear equation
122  *
123  */
124 
125  template<class P, class N>
128  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
129 
130  template<class P, class N>
131  ExecStatus
133  (void) new (home) Eq<P,N>(home,x,y,c);
134  return ES_OK;
135  }
136 
137 
138  template<class P, class N>
140  Eq<P,N>::Eq(Space& home, bool share, Eq<P,N>& p)
141  : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
142 
143  template<class P, class N>
144  Actor*
145  Eq<P,N>::copy(Space& home, bool share) {
146  return new (home) Eq<P,N>(home,share,*this);
147  }
148 
149  template<class P, class N>
150  ExecStatus
152  // Eliminate singletons
153  Rounding r;
154  eliminate_p<P>(med, x, c);
155  eliminate_n<N>(med, y, c);
156 
157  if ((FloatView::me(med) == ME_FLOAT_VAL) && ((x.size() + y.size()) <= 1)) {
158  if (x.size() == 1) {
159  GECODE_ME_CHECK(x[0].eq(home,c));
160  return home.ES_SUBSUMED(*this);
161  }
162  if (y.size() == 1) {
163  GECODE_ME_CHECK(y[0].eq(home,-c));
164  return home.ES_SUBSUMED(*this);
165  }
166  return (c.in(0.0)) ? home.ES_SUBSUMED(*this) : ES_FAILED;
167  }
168 
169  ExecStatus es = ES_FIX;
170  bool assigned = true;
171 
172  // Propagate max bound for positive variables
173  for (int i = x.size(); i--; ) {
174  // Compute bound
175  FloatNum sl = c.max();
176  for (int j = x.size(); j--; ) {
177  if (i == j) continue;
178  sl = r.sub_up(sl,x[j].min());
179  }
180  for (int j = y.size(); j--; )
181  sl = r.add_up(sl,y[j].max());
182  ModEvent me = x[i].lq(home,sl);
183  if (me_failed(me))
184  return ES_FAILED;
185  if (me != ME_FLOAT_VAL)
186  assigned = false;
187  if (me_modified(me))
188  es = ES_NOFIX;
189  }
190  // Propagate min bound for negative variables
191  for (int i = y.size(); i--; ) {
192  // Compute bound
193  FloatNum sl = -c.max();
194  for (int j = x.size(); j--; )
195  sl = r.add_down(sl,x[j].min());
196  for (int j = y.size(); j--; ) {
197  if (i == j) continue;
198  sl = r.sub_down(sl,y[j].max());
199  }
200  ModEvent me = y[i].gq(home,sl);
201  if (me_failed(me))
202  return ES_FAILED;
203  if (me != ME_FLOAT_VAL)
204  assigned = false;
205  if (me_modified(me))
206  es = ES_NOFIX;
207  }
208 
209  // Propagate min bound for positive variables
210  for (int i = x.size(); i--; ) {
211  // Compute bound
212  FloatNum su = c.min();
213  for (int j = x.size(); j--; ) {
214  if (i == j) continue;
215  su = r.sub_down(su,x[j].max());
216  }
217  for (int j = y.size(); j--; )
218  su = r.add_down(su,y[j].min());
219  ModEvent me = x[i].gq(home,su);
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 max bound for negative variables
228  for (int i = y.size(); i--; ) {
229  // Compute bound
230  FloatNum su = -c.min();
231  for (int j = x.size(); j--; )
232  su = r.add_up(su,x[j].max());
233  for (int j = y.size(); j--; ) {
234  if (i == j) continue;
235  su = r.sub_up(su,y[j].min());
236  }
237  ModEvent me = y[i].lq(home,su);
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  return assigned ? home.ES_SUBSUMED(*this) : es;
247  }
248 
249 
250  /*
251  * Bound consistent linear inequation
252  *
253  */
254 
255  template<class P, class N>
258  : Lin<P,N,PC_FLOAT_BND>(home,x,y,c) {}
259 
260  template<class P, class N>
261  ExecStatus
263  (void) new (home) Lq<P,N>(home,x,y,c);
264  return ES_OK;
265  }
266 
267  template<class P, class N>
269  Lq<P,N>::Lq(Space& home, bool share, Lq<P,N>& p)
270  : Lin<P,N,PC_FLOAT_BND>(home,share,p) {}
271 
272  template<class P, class N>
273  Actor*
274  Lq<P,N>::copy(Space& home, bool share) {
275  return new (home) Lq<P,N>(home,share,*this);
276  }
277 
278  template<class P, class N>
279  ExecStatus
281  // Eliminate singletons
282  FloatNum sl = 0.0;
283 
284  Rounding r;
285 
286  if (FloatView::me(med) == ME_FLOAT_VAL) {
287  for (int i = x.size(); i--; ) {
288  if (x[i].assigned()) {
289  c -= x[i].val(); x.move_lst(i);
290  } else {
291  sl = r.sub_up(sl,x[i].min());
292  }
293  }
294  for (int i = y.size(); i--; ) {
295  if (y[i].assigned()) {
296  c += y[i].val(); y.move_lst(i);
297  } else {
298  sl = r.add_up(sl,y[i].max());
299  }
300  }
301  if ((x.size() + y.size()) <= 1) {
302  if (x.size() == 1) {
303  GECODE_ME_CHECK(x[0].lq(home,c.max()));
304  return home.ES_SUBSUMED(*this);
305  }
306  if (y.size() == 1) {
307  GECODE_ME_CHECK(y[0].gq(home,(-c).min()));
308  return home.ES_SUBSUMED(*this);
309  }
310  return (c.max() >= 0) ? home.ES_SUBSUMED(*this) : ES_FAILED;
311  }
312  } else {
313  for (int i = x.size(); i--; )
314  sl = r.sub_up(sl,x[i].min());
315  for (int i = y.size(); i--; )
316  sl = r.add_up(sl,y[i].max());
317  }
318 
319  sl = r.add_up(sl,c.max());
320 
321  ExecStatus es = ES_FIX;
322  bool assigned = true;
323  for (int i = x.size(); i--; ) {
324  assert(!x[i].assigned());
325  FloatNum slx = r.add_up(sl,x[i].min());
326  ModEvent me = x[i].lq(home,slx);
327  if (me == ME_FLOAT_FAILED)
328  return ES_FAILED;
329  if (me != ME_FLOAT_VAL)
330  assigned = false;
331  if (me_modified(me))
332  es = ES_NOFIX;
333  }
334 
335  for (int i = y.size(); i--; ) {
336  assert(!y[i].assigned());
337  FloatNum sly = r.sub_up(y[i].max(),sl);
338  ModEvent me = y[i].gq(home,sly);
339  if (me == ME_FLOAT_FAILED)
340  return ES_FAILED;
341  if (me != ME_FLOAT_VAL)
342  assigned = false;
343  if (me_modified(me))
344  es = ES_NOFIX;
345  }
346 
347  return assigned ? home.ES_SUBSUMED(*this) : es;
348  }
349 
350 }}}
351 
352 // STATISTICS: float-prop
353 
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:269
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
Propagator for bounds consistent n-ary linear less or equal
Definition: linear.hh:140
int ModEvent
Type for modification events.
Definition: core.hpp:142
void linear(Home home, const FloatVarArgs &x, FloatRelType frt, FloatVal c)
Post propagator for .
Definition: linear.cpp:45
Base-class for n-ary linear propagators.
Definition: linear.hh:61
Base-class for propagators.
Definition: core.hpp:1092
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:115
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: nary.hpp:151
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:545
bool in(FloatNum n) const
Test whether n is included.
Definition: val.hpp:100
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
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 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:280
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition: nary.hpp:132
Execution has resulted in failure.
Definition: core.hpp:542
Eq(Space &home, bool share, Eq &p)
Constructor for cloning p.
Definition: nary.hpp:140
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: nary.hpp:274
#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:158
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
const int infinity
Infinity for integers.
Definition: int.hh:120
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Float value type.
Definition: float.hh:338
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
virtual Actor * copy(Space &home, bool share)
Create copy during cloning.
Definition: nary.hpp:145
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
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:514
#define forceinline
Definition: config.hpp:173
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
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:87
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:102
Gecode toplevel namespace
static ExecStatus post(Home home, ViewArray< P > &x, ViewArray< N > &y, FloatVal c)
Post propagator for .
Definition: nary.hpp:262
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 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:922
double FloatNum
Floating point number base type.
Definition: float.hh:110
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58