Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
13  * $Revision$
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 
67  forceinline bool
68  overflow(Term* t, int n, FloatVal c) {
69  FloatVal est = c;
70  for (int i=n; i--; )
71  est += t[i].a * t[i].x.domain();
72  FloatNum min = est.min();
73  FloatNum max = est.max();
74  return ((min < Limits::min) || (min > Limits::max) ||
75  (max < Limits::min) || (max > Limits::max));
76  }
77 
79  class TermLess {
80  public:
81  forceinline bool
82  operator ()(const Term& a, const Term& b) {
83  return before(a.x,b.x);
84  }
85  };
86 
88  FloatView
89  extend(Home home, Region& r, Term*& t, int& n) {
90  FloatNum min, max;
91  estimate(t,n,0.0,min,max);
92  FloatVar x(home,min,max);
93  Term* et = r.alloc<Term>(n+1);
94  for (int i=n; i--; )
95  et[i] = t[i];
96  et[n].a=-1.0; et[n].x=x;
97  t=et; n++;
98  return x;
99  }
100 
101 
106  template<class View>
107  forceinline void
110  FloatVal c) {
111  switch (frt) {
112  case FRT_EQ:
113  GECODE_ES_FAIL((Eq<View,View >::post(home,x,y,c)));
114  break;
115  case FRT_LQ:
116  GECODE_ES_FAIL((Lq<View,View >::post(home,x,y,c)));
117  break;
118  default: GECODE_NEVER;
119  }
120  }
121 
122  void
123  dopost(Home home, Term* t, int n, FloatRelType frt, FloatVal c) {
124  Limits::check(c,"Float::linear");
125 
126  for (int i=n; i--; ) {
127  if ((t[i].a.min() < 0.0) && (t[i].a.max() > 0.0))
128  throw ValueMixedSign("Float::linear[coefficient]");
129  if (t[i].x.assigned()) {
130  c -= t[i].a * t[i].x.val();
131  t[i]=t[--n];
132  }
133  }
134 
135  if ((c < Limits::min) || (c > Limits::max) || overflow(t, n, c))
136  throw OutOfLimits("Float::linear");
137 
138  /*
139  * Join coefficients for aliased variables:
140  *
141  */
142  {
143  // Group same variables
144  TermLess tl;
145  Support::quicksort<Term,TermLess>(t,n,tl);
146 
147  // Join adjacent variables
148  int i = 0;
149  int j = 0;
150  while (i < n) {
151  Limits::check(t[i].a,"Float::linear");
152  FloatVal a = t[i].a;
153  FloatView x = t[i].x;
154  while ((++i < n) && same(t[i].x,x)) {
155  a += t[i].a;
156  Limits::check(a,"Float::linear");
157  }
158  if (a != 0.0) {
159  t[j].a = a; t[j].x = x; j++;
160  }
161  }
162  n = j;
163  }
164 
165  Term *t_p, *t_n;
166  int n_p, n_n;
167 
168  /*
169  * Partition into positive/negative coefficents
170  *
171  */
172  if (n > 0) {
173  int i = 0;
174  int j = n-1;
175  while (true) {
176  while ((t[j].a < 0) && (--j >= 0)) ;
177  while ((t[i].a > 0) && (++i < n)) ;
178  if (j <= i) break;
179  std::swap(t[i],t[j]);
180  }
181  t_p = t; n_p = i;
182  t_n = t+n_p; n_n = n-n_p;
183  } else {
184  t_p = t; n_p = 0;
185  t_n = t; n_n = 0;
186  }
187 
188  /*
189  * Make all coefficients positive
190  *
191  */
192  for (int i=n_n; i--; )
193  t_n[i].a = -t_n[i].a;
194 
195  if (frt == FRT_GQ) {
196  frt = FRT_LQ;
197  std::swap(n_p,n_n); std::swap(t_p,t_n); c = -c;
198  }
199 
200  if (n == 0) {
201  switch (frt) {
202  case FRT_EQ: if (!c.in(0.0)) home.fail(); break;
203  case FRT_LQ: if (c.max() < 0.0) home.fail(); break;
204  default: GECODE_NEVER;
205  }
206  return;
207  }
208 
209  /*
210  * Test for unit coefficients only
211  *
212  */
213  bool is_unit = true;
214  for (int i=n; i--; )
215  if (!(t[i].a == 1.0)) {
216  is_unit = false;
217  break;
218  }
219 
220  if (is_unit) {
221  // Unit coefficients
222  ViewArray<FloatView> x(home,n_p);
223  for (int i = n_p; i--; )
224  x[i] = t_p[i].x;
225  ViewArray<FloatView> y(home,n_n);
226  for (int i = n_n; i--; )
227  y[i] = t_n[i].x;
228  post_nary<FloatView>(home,x,y,frt,c);
229  } else {
230  // Arbitrary coefficients
231  ViewArray<ScaleView> x(home,n_p);
232  for (int i = n_p; i--; )
233  x[i] = ScaleView(t_p[i].a,t_p[i].x);
234  ViewArray<ScaleView> y(home,n_n);
235  for (int i = n_n; i--; )
236  y[i] = ScaleView(t_n[i].a,t_n[i].x);
237  post_nary<ScaleView>(home,x,y,frt,c);
238  }
239  }
240 
241  void
242  post(Home home, Term* t, int n, FloatRelType frt, FloatVal c) {
243  Region re;
244  switch (frt) {
245  case FRT_EQ: case FRT_LQ: case FRT_GQ:
246  break;
247  case FRT_NQ: case FRT_LE: case FRT_GR:
248  rel(home, extend(home,re,t,n), frt, c);
249  frt=FRT_EQ; c=0.0;
250  break;
251  default:
252  throw UnknownRelation("Float::linear");
253  }
254  dopost(home, t, n, frt, c);
255  }
256 
257  void
258  post(Home home, Term* t, int n, FloatRelType frt, FloatVal c, Reify r) {
259  Region re;
260  rel(home, extend(home,re,t,n), frt, c, r);
261  dopost(home, t, n, FRT_EQ, 0.0);
262  }
263 
264 }}}
265 
266 // STATISTICS: float-post
267 
Propagator for bounds consistent n-ary linear equality
Definition: linear.hh:110
NodeType t
Type of node.
Definition: bool-expr.cpp:234
FloatVal val(void) const
Return assigned value.
Definition: float.hpp:76
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:242
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Exception: Value out of limits
Definition: exception.hpp:50
Disequality ( )
Definition: float.hh:1071
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
FloatVal a
Coefficient.
Definition: linear.hh:173
Less or equal ( )
Definition: float.hh:1072
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
Propagator for bounds consistent n-ary linear less or equal
Definition: linear.hh:140
void post_nary(Home home, ViewArray< View > &x, ViewArray< View > &y, FloatRelType frt, FloatVal c)
Posting n-ary propagators.
Definition: post.cpp:108
Sort linear terms by view.
Definition: post.cpp:79
Less ( )
Definition: float.hh:1073
Handle to region.
Definition: region.hpp:57
#define forceinline
Definition: config.hpp:182
bool in(FloatNum n) const
Test whether n is included.
Definition: val.hpp:100
Gecode::FloatVal c(-8, 8)
Greater or equal ( )
Definition: float.hh:1074
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:643
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
bool overflow(Term *t, int n, FloatVal c)
Definition: post.cpp:68
FloatRelType
Relation types for floats.
Definition: float.hh:1069
VarImp * x
Pointer to variable implementation.
Definition: var.hpp:54
bool before(const ViewA &x, const ViewB &y)
Definition: view.hpp:690
Reification specification.
Definition: int.hh:855
union Gecode::@585::NNF::@62 u
Union depending on nodetype t.
View arrays.
Definition: array.hpp:228
bool operator()(const Term &a, const Term &b)
Definition: post.cpp:82
Equality ( )
Definition: float.hh:1070
Exception: Unknown relation passed as argument
Definition: exception.hpp:92
Float view for float variables.
Definition: view.hpp:56
Greater ( )
Definition: float.hh:1075
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
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
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:769
Float value type.
Definition: float.hh:338
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
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
Post propagator for SetVar x
Definition: set.hh:769
Class for describing linear term .
Definition: linear.hh:170
FloatView x
View.
Definition: linear.hh:175
void fail(void)
Mark space as failed.
Definition: core.hpp:3909
Float variables.
Definition: float.hh:874
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:89
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
Home class for posting propagators
Definition: core.hpp:846
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
Exception: Value with mixed sign
Definition: exception.hpp:57
void dopost(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Definition: post.cpp:123
double FloatNum
Floating point number base type.
Definition: float.hh:110
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Scale float view.
Definition: view.hpp:373
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:41