Generated on Sat Feb 7 2015 02:01:28 for Gecode by doxygen 1.8.9.1
float-expr.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
5  *
6  * Copyright:
7  * Vincent Barichard, 2012
8  *
9  * Last modified:
10  * $Date: 2013-03-11 14:47:11 +0100 (Mon, 11 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13490 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/minimodel.hh>
39 
40 #ifdef GECODE_HAS_FLOAT_VARS
41 
42 #include <gecode/float/linear.hh>
43 
44 namespace Gecode {
45 
48  public:
50  unsigned int use;
52  int n_float;
56  Node *l, *r;
58  union {
63  } sum;
69  Node(void);
72  void fill(Home home, Float::Linear::Term*& tf,
73  FloatVal m, FloatVal& d) const;
75  FloatVal fill(Home home, Float::Linear::Term* tf) const;
77  bool decrement(void);
79  ~Node(void);
81  static void* operator new(size_t size);
83  static void operator delete(void* p,size_t size);
84 
85  };
86 
87  /*
88  * Operations for nodes
89  *
90  */
92  LinFloatExpr::Node::Node(void) : use(1) {
93  }
94 
97  switch (t) {
98  case NT_SUM:
99  if (n_float > 0)
100  heap.free<Float::Linear::Term>(sum.tf,n_float);
101  break;
102  case NT_NONLIN:
103  delete sum.ne;
104  break;
105  default: ;
106  }
107  }
108 
109  forceinline void*
110  LinFloatExpr::Node::operator new(size_t size) {
111  return heap.ralloc(size);
112  }
113 
114  forceinline void
115  LinFloatExpr::Node::operator delete(void* p, size_t) {
116  heap.rfree(p);
117  }
118 
119  bool
121  if (--use == 0) {
122  if ((l != NULL) && l->decrement())
123  delete l;
124  if ((r != NULL) && r->decrement())
125  delete r;
126  return true;
127  }
128  return false;
129  }
130 
131  /*
132  * Operations for float expressions
133  *
134  */
135 
137  : n(e.n) {
138  n->use++;
139  }
140 
142  LinFloatExpr::nlfe(void) const {
143  return n->t == NT_NONLIN ? n->sum.ne : NULL;
144  }
145 
146  FloatVal
148  Float::Linear::Term* tf) const {
149  FloatVal d=0;
150  fill(home,tf,1.0,d);
151  Float::Limits::check(d,"MiniModel::LinFloatExpr");
152  return d;
153  }
154 
155  void
157  if (home.failed()) return;
158  Region r(home);
159  if (n->t==NT_ADD && n->l == NULL && n->r->t==NT_NONLIN) {
160  n->r->sum.ne->post(home,frt,-n->c);
161  } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==NULL) {
162  switch (frt) {
163  case FRT_LQ: frt=FRT_GQ; break;
164  case FRT_GQ: frt=FRT_LQ; break;
165  default: break;
166  }
167  n->r->sum.ne->post(home,frt,n->c);
168  } else if (frt==FRT_EQ &&
169  n->t==NT_SUB && n->r->t==NT_NONLIN &&
170  n->l != NULL && n->l->t==NT_VAR
171  && n->l->a==1) {
172  (void) n->r->sum.ne->post(home,&n->l->x_float);
173  } else if (frt==FRT_EQ &&
174  n->t==NT_SUB && n->r->t==NT_VAR &&
175  n->l != NULL && n->l->t==NT_NONLIN
176  && n->r->a==1) {
177  (void) n->l->sum.ne->post(home,&n->r->x_float);
178  } else {
179  Float::Linear::Term* fts =
181  FloatVal c = n->fill(home,fts);
182  Float::Linear::post(home, fts, n->n_float, frt, -c);
183  }
184  }
185 
186  void
187  LinFloatExpr::post(Home home, FloatRelType frt, const BoolVar& b) const {
188  if (home.failed()) return;
189  Region r(home);
190  if (n->t==NT_ADD && n->l==NULL && n->r->t==NT_NONLIN) {
191  n->r->sum.ne->post(home,frt,-n->c,b);
192  } else if (n->t==NT_SUB && n->l==NULL && n->r->t==NT_NONLIN) {
193  switch (frt) {
194  case FRT_LQ: frt=FRT_GQ; break;
195  case FRT_LE: frt=FRT_GR; break;
196  case FRT_GQ: frt=FRT_LQ; break;
197  case FRT_GR: frt=FRT_LE; break;
198  default: break;
199  }
200  n->r->sum.ne->post(home,frt,n->c,b);
201  } else {
202  Float::Linear::Term* fts =
204  FloatVal c = n->fill(home,fts);
205  Float::Linear::post(home, fts, n->n_float, frt, -c, b);
206  }
207 
208  }
209 
210  FloatVar
211  LinFloatExpr::post(Home home) const {
212  if (home.failed()) return FloatVar(home,0,0);
213  Region r(home);
214  Float::Linear::Term* fts =
216  FloatVal c = n->fill(home,fts);
217  if ((n->n_float == 1) && (c == 0) && (fts[0].a == 1))
218  return fts[0].x;
219  FloatNum min, max;
220  Float::Linear::estimate(&fts[0],n->n_float,c,min,max);
221  FloatVar x(home, min, max);
222  fts[n->n_float].x = x; fts[n->n_float].a = -1;
223  Float::Linear::post(home, fts, n->n_float+1, FRT_EQ, -c);
224  return x;
225 
226  }
227 
229  n(new Node) {
230  n->n_float = 0;
231  n->t = NT_VAR;
232  n->l = n->r = NULL;
233  n->a = 0;
234  }
235 
237  n(new Node) {
238  n->n_float = 0;
239  n->t = NT_CONST;
240  n->l = n->r = NULL;
241  n->a = 0;
242  Float::Limits::check(c,"MiniModel::LinFloatExpr");
243  n->c = c;
244  }
245 
247  n(new Node) {
248  n->n_float = 1;
249  n->t = NT_VAR;
250  n->l = n->r = NULL;
251  n->a = 1.0;
252  n->x_float = x;
253  }
254 
256  n(new Node) {
257  n->n_float = 1;
258  n->t = NT_VAR;
259  n->l = n->r = NULL;
260  n->a = a;
261  n->x_float = x;
262  }
263 
265  n(new Node) {
266  n->n_float = x.size();
267  n->t = NT_SUM;
268  n->l = n->r = NULL;
269  if (x.size() > 0) {
271  for (int i=x.size(); i--; ) {
272  n->sum.tf[i].x = x[i];
273  n->sum.tf[i].a = 1.0;
274  }
275  }
276  }
277 
279  n(new Node) {
280  if (a.size() != x.size())
281  throw Float::ArgumentSizeMismatch("MiniModel::LinFloatExpr");
282  n->n_float = x.size();
283  n->t = NT_SUM;
284  n->l = n->r = NULL;
285  if (x.size() > 0) {
287  for (int i=x.size(); i--; ) {
288  n->sum.tf[i].x = x[i];
289  n->sum.tf[i].a = a[i];
290  }
291  }
292  }
293 
295  n(new Node) {
296  n->n_float = e0.n->n_float + e1.n->n_float;
297  n->t = t;
298  n->l = e0.n; n->l->use++;
299  n->r = e1.n; n->r->use++;
300  }
301 
303  n(new Node) {
304  n->n_float = e.n->n_float;
305  n->t = t;
306  n->l = NULL;
307  n->r = e.n; n->r->use++;
308  n->c = c;
309  }
310 
312  n(new Node) {
313  n->n_float = e.n->n_float;
314  n->t = NT_MUL;
315  n->l = e.n; n->l->use++;
316  n->r = NULL;
317  n->a = a;
318  }
319 
321  n(new Node) {
322  n->n_float = 1;
323  n->t = NT_NONLIN;
324  n->l = n->r = NULL;
325  n->a = 0;
326  n->sum.ne = e;
327  }
328 
329  const LinFloatExpr&
331  if (this != &e) {
332  if (n->decrement())
333  delete n;
334  n = e.n; n->use++;
335  }
336  return *this;
337  }
338 
340  if (n->decrement())
341  delete n;
342  }
343 
344 
345  void
347  Float::Linear::Term*& tf,
348  FloatVal m, FloatVal& d) const {
349  switch (this->t) {
350  case NT_CONST:
351  Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
352  d += m*c;
353  break;
354  case NT_VAR:
355  Float::Limits::check(m*a,"MiniModel::LinFloatExpr");
356  tf->a=m*a; tf->x=x_float; tf++;
357  break;
358  case NT_NONLIN:
359  tf->a=m; tf->x=sum.ne->post(home, NULL); tf++;
360  break;
361  case NT_SUM:
362  for (int i=n_float; i--; ) {
363  Float::Limits::check(m*sum.tf[i].a,"MiniModel::LinFloatExpr");
364  tf[i].x = sum.tf[i].x; tf[i].a = m*sum.tf[i].a;
365  }
366  tf += n_float;
367  break;
368  case NT_ADD:
369  if (l == NULL) {
370  Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
371  d += m*c;
372  } else {
373  l->fill(home,tf,m,d);
374  }
375  r->fill(home,tf,m,d);
376  break;
377  case NT_SUB:
378  if (l == NULL) {
379  Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
380  d += m*c;
381  } else {
382  l->fill(home,tf,m,d);
383  }
384  r->fill(home,tf,-m,d);
385  break;
386  case NT_MUL:
387  Float::Limits::check(m*a,"MiniModel::LinFloatExpr");
388  l->fill(home,tf,m*a,d);
389  break;
390  default:
391  GECODE_NEVER;
392  }
393  }
394 
395 
396  /*
397  * Operators
398  *
399  */
401  operator +(const FloatVal& c, const FloatVar& x) {
402  if (x.assigned() && Float::Limits::valid(c+x.val()))
403  return LinFloatExpr(c+x.val());
404  else
406  }
408  operator +(const FloatVal& c, const LinFloatExpr& e) {
410  }
412  operator +(const FloatVar& x, const FloatVal& c) {
413  if (x.assigned() && Float::Limits::valid(c+x.val()))
414  return LinFloatExpr(c+x.val());
415  else
417  }
419  operator +(const LinFloatExpr& e, const FloatVal& c) {
421  }
423  operator +(const FloatVar& x, const FloatVar& y) {
424  if (x.assigned())
425  return x.val() + y;
426  else if (y.assigned())
427  return x + y.val();
428  else
429  return LinFloatExpr(x,LinFloatExpr::NT_ADD,(const LinFloatExpr&)y);
430  }
432  operator +(const FloatVar& x, const LinFloatExpr& e) {
433  if (x.assigned())
434  return x.val() + e;
435  else
437  }
439  operator +(const LinFloatExpr& e, const FloatVar& x) {
440  if (x.assigned())
441  return e + x.val();
442  else
443  return LinFloatExpr(e,LinFloatExpr::NT_ADD,(const LinFloatExpr&)x);
444  }
446  operator +(const LinFloatExpr& e1, const LinFloatExpr& e2) {
447  return LinFloatExpr(e1,LinFloatExpr::NT_ADD,e2);
448  }
449 
451  operator -(const FloatVal& c, const FloatVar& x) {
452  if (x.assigned() && Float::Limits::valid(c-x.val()))
453  return LinFloatExpr(c-x.val());
454  else
456  }
458  operator -(const FloatVal& c, const LinFloatExpr& e) {
460  }
462  operator -(const FloatVar& x, const FloatVal& c) {
463  if (x.assigned() && Float::Limits::valid(x.val()-c))
464  return LinFloatExpr(x.val()-c);
465  else
466  return LinFloatExpr(x,LinFloatExpr::NT_ADD,-c);
467  }
469  operator -(const LinFloatExpr& e, const FloatVal& c) {
470  return LinFloatExpr(e,LinFloatExpr::NT_ADD,-c);
471  }
473  operator -(const FloatVar& x, const FloatVar& y) {
474  if (x.assigned())
475  return x.val() - y;
476  else if (y.assigned())
477  return x - y.val();
478  else
479  return LinFloatExpr(x,LinFloatExpr::NT_SUB,(const LinFloatExpr&)y);
480  }
482  operator -(const FloatVar& x, const LinFloatExpr& e) {
483  if (x.assigned())
484  return x.val() - e;
485  else
487  }
489  operator -(const LinFloatExpr& e, const FloatVar& x) {
490  if (x.assigned())
491  return e - x.val();
492  else
493  return LinFloatExpr(e,LinFloatExpr::NT_SUB,(const LinFloatExpr&)x);
494  }
496  operator -(const LinFloatExpr& e1, const LinFloatExpr& e2) {
497  return LinFloatExpr(e1,LinFloatExpr::NT_SUB,e2);
498  }
499 
502  if (x.assigned())
503  return LinFloatExpr(-x.val());
504  else
506  }
510  }
511 
513  operator *(const FloatVal& a, const FloatVar& x) {
514  if (a == 0)
515  return LinFloatExpr(0.0);
516  else if (x.assigned() &&
517  Float::Limits::valid(a*x.val()))
518  return LinFloatExpr(a*x.val());
519  else
520  return LinFloatExpr(x,a);
521  }
523  operator *(const FloatVar& x, const FloatVal& a) {
524  if (a == 0)
525  return LinFloatExpr(0.0);
526  else if (x.assigned() &&
527  Float::Limits::valid(a*x.val()))
528  return LinFloatExpr(a*x.val());
529  else
530  return LinFloatExpr(x,a);
531  }
533  operator *(const LinFloatExpr& e, const FloatVal& a) {
534  if (a == 0)
535  return LinFloatExpr(0.0);
536  else
537  return LinFloatExpr(a,e);
538  }
540  operator *(const FloatVal& a, const LinFloatExpr& e) {
541  if (a == 0)
542  return LinFloatExpr(0.0);
543  else
544  return LinFloatExpr(a,e);
545  }
546 
548  sum(const FloatVarArgs& x) {
549  return LinFloatExpr(x);
550  }
552  sum(const FloatValArgs& a, const FloatVarArgs& x) {
553  return LinFloatExpr(a,x);
554  }
555 
556  FloatVar
557  expr(Home home, const LinFloatExpr& e) {
558  if (!home.failed())
559  return e.post(home);
561  return x;
562  }
563 
564 }
565 
566 #endif
567 
568 // STATISTICS: minimodel-any
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
FloatVal operator-(const FloatVal &x)
Definition: val.hpp:172
FloatVar x_float
Float variable (potentially)
Definition: float-expr.cpp:67
void fill(Home home, Float::Linear::Term *&tf, FloatVal m, FloatVal &d) const
Generate linear terms from expression.
Definition: float-expr.cpp:346
Passing float arguments.
Definition: float.hh:937
void post(Home home, FloatRelType frt) const
Post propagator.
Definition: float-expr.cpp:156
NodeType t
Type of node.
Definition: bool-expr.cpp:234
int n_float
Float variables in tree.
Definition: float-expr.cpp:52
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition: limits.hpp:43
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
NodeType t
Type of expression.
Definition: float-expr.cpp:54
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
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
unsigned int use
Nodes are reference counted.
Definition: float-expr.cpp:50
Passing float variables.
Definition: float.hh:966
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
Less ( )
Definition: float.hh:1058
Handle to region.
Definition: region.hpp:61
Linear term with variable.
Definition: minimodel.hh:721
virtual FloatVar post(Home home, FloatVar *ret) const =0
Return variable constrained to be equal to the expression.
bool decrement(void)
Decrement reference count and possibly free memory.
Definition: float-expr.cpp:120
FloatVal a
Coefficient and offset.
Definition: float-expr.cpp:65
Nodes for linear expressions.
Definition: float-expr.cpp:47
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
Greater or equal ( )
Definition: float.hh:1059
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:400
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
Base class for non-linear float expressions.
Definition: minimodel.hh:685
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:168
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
FloatRelType
Relation types for floats.
Definition: float.hh:1054
unsigned int size(I &i)
Size of all ranges of range iterator i.
Subtraction of linear terms.
Definition: minimodel.hh:725
Float expressions
Definition: minimodel.hh:715
Float::Linear::Term * tf
Integer views and coefficients.
Definition: float-expr.cpp:60
LinFloatExpr(void)
Default constructor.
Definition: float-expr.cpp:228
~LinFloatExpr(void)
Destructor.
Definition: float-expr.cpp:339
NodeType
Type of linear expression.
Definition: minimodel.hh:719
Equality ( )
Definition: float.hh:1055
Multiplication by coefficient.
Definition: minimodel.hh:726
Greater ( )
Definition: float.hh:1060
Boolean integer variables.
Definition: int.hh:491
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:75
const LinFloatExpr & operator=(const LinFloatExpr &e)
Assignment operator.
Definition: float-expr.cpp:330
Sum of float variables.
Definition: minimodel.hh:723
Non-linear expression.
Definition: minimodel.hh:722
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
Float value type.
Definition: float.hh:321
FloatVal operator*(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:204
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
NonLinFloatExpr * ne
Non-linear expression.
Definition: float-expr.cpp:62
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Node(void)
Default constructor.
Definition: float-expr.cpp:92
NonLinFloatExpr * nlfe(void) const
Return non-linear expression inside, or NULL if not non-linear.
Definition: float-expr.cpp:142
FloatVal val(void) const
Return assigned value.
Definition: float.hpp:57
#define forceinline
Definition: config.hpp:132
void estimate(Term *t, int n, FloatVal c, FloatNum &l, FloatNum &u)
Estimate lower and upper bounds.
Definition: post.cpp:49
Exception: Arguments are of different size
Definition: exception.hpp:71
Node * l
Subexpressions.
Definition: float-expr.cpp:56
Class for describing linear term .
Definition: linear.hh:168
#define GECODE_MINIMODEL_EXPORT
Definition: minimodel.hh:82
FloatView x
View.
Definition: linear.hh:173
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
Float variables.
Definition: float.hh:857
Addition of linear terms.
Definition: minimodel.hh:724
Float value constant.
Definition: minimodel.hh:720
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:548
union Gecode::LinFloatExpr::Node::@60 sum
Sum of integer or Boolean variables, or non-linear expression.
~Node(void)
Destructor.
Definition: float-expr.cpp:96
Home class for posting propagators
Definition: core.hpp:717
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.