Generated on Sat Feb 7 2015 02:01:16 for Gecode by doxygen 1.8.9.1
post.cpp
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, 2002
9  * Vincent Barichard, 2012
10  *
11  * Last modified:
12  * $Date: 2013-01-24 19:28:06 +0100 (Thu, 24 Jan 2013) $ by $Author: schulte $
13  * $Revision: 13235 $
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 #include <algorithm>
41 #include <climits>
42 
43 #include <gecode/float/linear.hh>
44 #include <gecode/float/rel.hh>
45 
46 namespace Gecode { namespace Float { namespace Linear {
47 
48  void
50  FloatVal est = c;
51  for (int i=n; i--; )
52  est += t[i].a * t[i].x.domain();
53  FloatNum min = est.min();
54  FloatNum max = est.max();
55  if (min < Limits::min)
56  min = Limits::min;
57  if (min > Limits::max)
58  min = Limits::max;
59  l = min;
60  if (max < Limits::min)
61  max = Limits::min;
62  if (max > Limits::max)
63  max = Limits::max;
64  u = max;
65  }
66 
68  class TermLess {
69  public:
70  forceinline bool
71  operator ()(const Term& a, const Term& b) {
72  return before(a.x,b.x);
73  }
74  };
75 
77  FloatView
78  extend(Home home, Region& r, Term*& t, int& n) {
79  FloatNum min, max;
80  estimate(t,n,0.0,min,max);
81  FloatVar x(home,min,max);
82  Term* et = r.alloc<Term>(n+1);
83  for (int i=n; i--; )
84  et[i] = t[i];
85  et[n].a=-1.0; et[n].x=x;
86  t=et; n++;
87  return x;
88  }
89 
90 
95  template<class View>
96  forceinline void
99  FloatVal c) {
100  switch (frt) {
101  case FRT_EQ:
102  GECODE_ES_FAIL((Eq<View,View >::post(home,x,y,c)));
103  break;
104  case FRT_LQ:
105  GECODE_ES_FAIL((Lq<View,View >::post(home,x,y,c)));
106  break;
107  default: GECODE_NEVER;
108  }
109  }
110 
111  void
112  dopost(Home home, Term* t, int n, FloatRelType frt, FloatVal c) {
113  Limits::check(c,"Float::linear");
114 
115  for (int i=n; i--; )
116  if (t[i].x.assigned()) {
117  c -= t[i].a * t[i].x.val();
118  t[i]=t[--n];
119  }
120 
121  if ((c < Limits::min) || (c > Limits::max))
122  throw OutOfLimits("Float::linear");
123 
124  /*
125  * Join coefficients for aliased variables:
126  *
127  */
128  {
129  // Group same variables
130  TermLess tl;
131  Support::quicksort<Term,TermLess>(t,n,tl);
132 
133  // Join adjacent variables
134  int i = 0;
135  int j = 0;
136  while (i < n) {
137  Limits::check(t[i].a,"Float::linear");
138  FloatVal a = t[i].a;
139  FloatView x = t[i].x;
140  while ((++i < n) && same(t[i].x,x)) {
141  a += t[i].a;
142  Limits::check(a,"Float::linear");
143  }
144  if (a != 0.0) {
145  t[j].a = a; t[j].x = x; j++;
146  }
147  }
148  n = j;
149  }
150 
151  Term *t_p, *t_n;
152  int n_p, n_n;
153 
154  /*
155  * Partition into positive/negative coefficents
156  *
157  */
158  if (n > 0) {
159  int i = 0;
160  int j = n-1;
161  while (true) {
162  while ((t[j].a < 0) && (--j >= 0)) ;
163  while ((t[i].a > 0) && (++i < n)) ;
164  if (j <= i) break;
165  std::swap(t[i],t[j]);
166  }
167  t_p = t; n_p = i;
168  t_n = t+n_p; n_n = n-n_p;
169  } else {
170  t_p = t; n_p = 0;
171  t_n = t; n_n = 0;
172  }
173 
174  /*
175  * Make all coefficients positive
176  *
177  */
178  for (int i=n_n; i--; )
179  t_n[i].a = -t_n[i].a;
180 
181  if (frt == FRT_GQ) {
182  frt = FRT_LQ;
183  std::swap(n_p,n_n); std::swap(t_p,t_n); c = -c;
184  }
185 
186  if (n == 0) {
187  switch (frt) {
188  case FRT_EQ: if (!c.in(0.0)) home.fail(); break;
189  case FRT_LQ: if (c.max() < 0.0) home.fail(); break;
190  default: GECODE_NEVER;
191  }
192  return;
193  }
194 
195  /*
196  * Test for unit coefficients only
197  *
198  */
199  bool is_unit = true;
200  for (int i=n; i--; )
201  if (t[i].a != 1.0) {
202  is_unit = false;
203  break;
204  }
205 
206  if (is_unit) {
207  // Unit coefficients
208  ViewArray<FloatView> x(home,n_p);
209  for (int i = n_p; i--; )
210  x[i] = t_p[i].x;
211  ViewArray<FloatView> y(home,n_n);
212  for (int i = n_n; i--; )
213  y[i] = t_n[i].x;
214  post_nary<FloatView>(home,x,y,frt,c);
215  } else {
216  // Arbitrary coefficients
217  ViewArray<ScaleView> x(home,n_p);
218  for (int i = n_p; i--; )
219  x[i] = ScaleView(t_p[i].a,t_p[i].x);
220  ViewArray<ScaleView> y(home,n_n);
221  for (int i = n_n; i--; )
222  y[i] = ScaleView(t_n[i].a,t_n[i].x);
223  post_nary<ScaleView>(home,x,y,frt,c);
224  }
225  }
226 
227  void
228  post(Home home, Term* t, int n, FloatRelType frt, FloatVal c) {
229  Region re(home);
230  switch (frt) {
231  case FRT_EQ: case FRT_LQ: case FRT_GQ:
232  break;
233  case FRT_NQ: case FRT_LE: case FRT_GR:
234  rel(home, extend(home,re,t,n), frt, c);
235  frt=FRT_EQ; c=0.0;
236  break;
237  default:
238  throw UnknownRelation("Float::linear");
239  }
240  dopost(home, t, n, frt, c);
241  }
242 
243  void
244  post(Home home, Term* t, int n, FloatRelType frt, FloatVal c, Reify r) {
245  Region re(home);
246  rel(home, extend(home,re,t,n), frt, c, r);
247  dopost(home, t, n, FRT_EQ, 0.0);
248  }
249 
250 }}}
251 
252 // STATISTICS: float-post
253 
Propagator for bounds consistent n-ary linear equality
Definition: linear.hh:108
NodeType t
Type of node.
Definition: bool-expr.cpp:234
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
FloatVal val(void) const
Return assigned value.
Definition: float.hpp:76
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
Exception: Value out of limits
Definition: exception.hpp:50
Disequality ( )
Definition: float.hh:1056
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
FloatVal a
Coefficient.
Definition: linear.hh:171
Less or equal ( )
Definition: float.hh:1057
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
void post_nary(Home home, ViewArray< View > &x, ViewArray< View > &y, FloatRelType frt, FloatVal c)
Posting n-ary propagators.
Definition: post.cpp:97
Sort linear terms by view.
Definition: post.cpp:68
Less ( )
Definition: float.hh:1058
Handle to region.
Definition: region.hpp:61
Gecode::FloatVal c(-8, 8)
Greater or equal ( )
Definition: float.hh:1059
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:603
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
FloatRelType
Relation types for floats.
Definition: float.hh:1054
bool before(const ViewA &x, const ViewB &y)
Definition: view.hpp:650
Reification specification.
Definition: int.hh:854
View arrays.
Definition: array.hpp:234
bool operator()(const Term &a, const Term &b)
Definition: post.cpp:71
Equality ( )
Definition: float.hh:1055
Exception: Unknown relation passed as argument
Definition: exception.hpp:85
Float view for float variables.
Definition: view.hpp:56
Greater ( )
Definition: float.hh:1060
void check(const FloatVal &n, const char *l)
Check whether float n is a valid number, otherwise throw out of limits exception with information l...
Definition: limits.hpp:48
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Float value type.
Definition: float.hh:321
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
bool in(FloatNum n) const
Test whether n is included.
Definition: val.hpp:100
#define forceinline
Definition: config.hpp:132
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
void estimate(Term *t, int n, FloatVal c, FloatNum &l, FloatNum &u)
Estimate lower and upper bounds.
Definition: post.cpp:49
Class for describing linear term .
Definition: linear.hh:168
FloatView x
View.
Definition: linear.hh:173
void fail(void)
Mark space as failed.
Definition: core.hpp:3437
Float variables.
Definition: float.hh:857
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
FloatView extend(Home home, Region &r, Term *&t, int &n)
Extend terms by adding view for result.
Definition: post.cpp:78
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Home class for posting propagators
Definition: core.hpp:717
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:96
void dopost(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Definition: post.cpp:112
double FloatNum
Floating point number base type.
Definition: float.hh:108
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Scale float view.
Definition: view.hpp:373