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