Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
39
40namespace Gecode {
41
44 public:
46 unsigned int use;
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;
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 */
88 LinFloatExpr::Node::Node(void) : use(1) {
89 }
90
93 switch (t) {
94 case NT_SUM:
95 if (n_float > 0)
96 heap.free<Float::Linear::Term>(sum.tf,n_float);
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 != nullptr) && l->decrement())
119 delete l;
120 if ((r != nullptr) && 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 : nullptr;
140 }
141
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 == nullptr && 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==nullptr) {
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 != nullptr && 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 != nullptr && n->l->t==NT_NONLIN
174 && n->r->a==1) {
175 (void) n->l->sum.ne->post(home,&n->r->x_float);
176 } else {
178 r.alloc<Float::Linear::Term>(n->n_float);
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==nullptr && 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==nullptr && 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 {
201 r.alloc<Float::Linear::Term>(n->n_float);
202 FloatVal c = n->fill(home,fts);
203 Float::Linear::post(home, fts, n->n_float, frt, -c, b);
204 }
205
206 }
207
210 if (home.failed()) return FloatVar(home,0,0);
211 Region r;
213 r.alloc<Float::Linear::Term>(n->n_float+1);
214 FloatVal c = n->fill(home,fts);
215 if ((n->n_float == 1) && (c == 0) && (fts[0].a == 1))
216 return fts[0].x;
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 = nullptr;
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 = nullptr;
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 = nullptr;
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 = nullptr;
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 = nullptr;
267 if (x.size() > 0) {
268 n->sum.tf = heap.alloc<Float::Linear::Term>(x.size());
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
276 LinFloatExpr::LinFloatExpr(const FloatValArgs& a, const FloatVarArgs& x) :
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 = nullptr;
283 if (x.size() > 0) {
284 n->sum.tf = heap.alloc<Float::Linear::Term>(x.size());
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 = nullptr;
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 = nullptr;
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 = nullptr;
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
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, nullptr); 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 == nullptr) {
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 == nullptr) {
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:
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
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
442 }
444 operator +(const LinFloatExpr& e1, const LinFloatExpr& 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
465 }
467 operator -(const LinFloatExpr& e, const FloatVal& 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
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
492 }
494 operator -(const LinFloatExpr& e1, const LinFloatExpr& 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
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
NNF * l
Left subtree.
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Node * x
Pointer to corresponding Boolean expression node.
Boolean integer variables.
Definition int.hh:512
Passing float arguments.
Definition float.hh:950
Float value type.
Definition float.hh:334
Passing float variables.
Definition float.hh:979
Float variables.
Definition float.hh:870
Exception: Arguments are of different size
Definition exception.hpp:74
Class for describing linear term .
Definition linear.hh:166
FloatVal a
Coefficient.
Definition linear.hh:169
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition heap.hpp:457
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
Home class for posting propagators
Definition core.hpp:856
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4048
Nodes for linear expressions.
union Gecode::LinFloatExpr::Node::@68 sum
Sum of integer or Boolean variables, or non-linear expression.
NonLinFloatExpr * ne
Non-linear expression.
NodeType t
Type of expression.
FloatVal a
Coefficient and offset.
FloatVar x_float
Float variable (potentially)
unsigned int use
Nodes are reference counted.
int n_float
Float variables in tree.
Node(void)
Default constructor.
Node * l
Subexpressions.
void fill(Home home, Float::Linear::Term *&tf, FloatVal m, FloatVal &d) const
Generate linear terms from expression.
bool decrement(void)
Decrement reference count and possibly free memory.
Float::Linear::Term * tf
Integer views and coefficients.
Float expressions
Definition minimodel.hh:822
NonLinFloatExpr * nlfe(void) const
Return non-linear expression inside, or null if not non-linear.
LinFloatExpr(void)
Default constructor.
const LinFloatExpr & operator=(const LinFloatExpr &e)
Assignment operator.
~LinFloatExpr(void)
Destructor.
void post(Home home, FloatRelType frt) const
Post propagator.
NodeType
Type of linear expression.
Definition minimodel.hh:826
@ NT_VAR
Linear term with variable.
Definition minimodel.hh:828
@ NT_CONST
Float value constant.
Definition minimodel.hh:827
@ NT_SUM
Sum of float variables.
Definition minimodel.hh:830
@ NT_NONLIN
Non-linear expression.
Definition minimodel.hh:829
@ NT_ADD
Addition of linear terms.
Definition minimodel.hh:831
@ NT_MUL
Multiplication by coefficient.
Definition minimodel.hh:833
@ NT_SUB
Subtraction of linear terms.
Definition minimodel.hh:832
Base class for non-linear float expressions.
Definition minimodel.hh:794
virtual FloatVar post(Home home, FloatVar *ret) const =0
Return variable constrained to be equal to the expression.
Class to set group information when a post function is executed.
Definition core.hpp:948
Handle to region.
Definition region.hpp:55
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
VarImpType * x
Pointer to variable implementation.
Definition view.hpp:141
const int * pi[]
Definition photo.cpp:14262
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition post.cpp:238
Heap heap
The single global heap.
Definition heap.cpp:44
double FloatNum
Floating point number base type.
Definition float.hh:106
FloatRelType
Relation types for floats.
Definition float.hh:1068
@ FRT_EQ
Equality ( )
Definition float.hh:1069
@ FRT_GR
Greater ( )
Definition float.hh:1074
@ FRT_LE
Less ( )
Definition float.hh:1072
@ FRT_LQ
Less or equal ( )
Definition float.hh:1071
@ FRT_GQ
Greater or equal ( )
Definition float.hh:1073
#define GECODE_MINIMODEL_EXPORT
Definition minimodel.hh:78
const FloatNum max
Largest allowed float value.
Definition float.hh:844
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition limits.hpp:39
const FloatNum min
Smallest allowed float value.
Definition float.hh:846
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 estimate(Term *t, int n, FloatVal c, FloatNum &l, FloatNum &u)
Estimate lower and upper bounds.
Definition post.cpp:45
Gecode toplevel namespace
FloatVal operator-(const FloatVal &x)
Definition val.hpp:168
FloatVal operator+(const FloatVal &x)
Definition val.hpp:164
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:880
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
FloatVal operator*(const FloatVal &x, const FloatVal &y)
Definition val.hpp:200
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56