this repo has no description
dekker.one
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
40namespace Gecode {
41
42 /// Nodes for linear expressions
43 class LinFloatExpr::Node {
44 public:
45 /// Nodes are reference counted
46 unsigned int use;
47 /// Float variables in tree
48 int n_float;
49 /// Type of expression
50 NodeType t;
51 /// Subexpressions
52 Node *l, *r;
53 /// Sum of integer or Boolean variables, or non-linear expression
54 union {
55 /// Integer views and coefficients
56 Float::Linear::Term* tf;
57 /// Non-linear expression
58 NonLinFloatExpr* ne;
59 } sum;
60 /// Coefficient and offset
61 FloatVal a, c;
62 /// Float variable (potentially)
63 FloatVar x_float;
64 /// Default constructor
65 Node(void);
66 /// Generate linear terms from expression
67 GECODE_MINIMODEL_EXPORT
68 void fill(Home home, Float::Linear::Term*& tf,
69 FloatVal m, FloatVal& d) const;
70 /// Generate linear terms for expressions
71 FloatVal fill(Home home, Float::Linear::Term* tf) const;
72 /// Decrement reference count and possibly free memory
73 bool decrement(void);
74 /// Destructor
75 ~Node(void);
76 /// Memory management
77 static void* operator new(size_t size);
78 /// Memory management
79 static void operator delete(void* p,size_t size);
80
81 };
82
83 /*
84 * Operations for nodes
85 *
86 */
87 forceinline
88 LinFloatExpr::Node::Node(void) : use(1) {
89 }
90
91 forceinline
92 LinFloatExpr::Node::~Node(void) {
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
116 LinFloatExpr::Node::decrement(void) {
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
132 LinFloatExpr::LinFloatExpr(const LinFloatExpr& e)
133 : n(e.n) {
134 n->use++;
135 }
136
137 NonLinFloatExpr*
138 LinFloatExpr::nlfe(void) const {
139 return n->t == NT_NONLIN ? n->sum.ne : nullptr;
140 }
141
142 FloatVal
143 LinFloatExpr::Node::fill(Home home,
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
152 LinFloatExpr::post(Home home, FloatRelType frt) const {
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 {
177 Float::Linear::Term* fts =
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 {
200 Float::Linear::Term* fts =
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
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 =
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;
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
226 LinFloatExpr::LinFloatExpr(void) :
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
234 LinFloatExpr::LinFloatExpr(const FloatVal& c) :
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
244 LinFloatExpr::LinFloatExpr(const FloatVar& x) :
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
253 LinFloatExpr::LinFloatExpr(const FloatVar& x, FloatVal a) :
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
262 LinFloatExpr::LinFloatExpr(const FloatVarArgs& x) :
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
292 LinFloatExpr::LinFloatExpr(const LinFloatExpr& e0, NodeType t, const LinFloatExpr& e1) :
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
300 LinFloatExpr::LinFloatExpr(const LinFloatExpr& e, NodeType t, const FloatVal& c) :
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
309 LinFloatExpr::LinFloatExpr(FloatVal a, const LinFloatExpr& e) :
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
318 LinFloatExpr::LinFloatExpr(NonLinFloatExpr* e) :
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&
328 LinFloatExpr::operator =(const LinFloatExpr& e) {
329 if (this != &e) {
330 if (n->decrement())
331 delete n;
332 n = e.n; n->use++;
333 }
334 return *this;
335 }
336
337 LinFloatExpr::~LinFloatExpr(void) {
338 if (n->decrement())
339 delete n;
340 }
341
342
343 void
344 LinFloatExpr::Node::fill(Home home,
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, 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:
389 GECODE_NEVER;
390 }
391 }
392
393
394 /*
395 * Operators
396 *
397 */
398 LinFloatExpr
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
403 return LinFloatExpr(x,LinFloatExpr::NT_ADD,c);
404 }
405 LinFloatExpr
406 operator +(const FloatVal& c, const LinFloatExpr& e) {
407 return LinFloatExpr(e,LinFloatExpr::NT_ADD,c);
408 }
409 LinFloatExpr
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
414 return LinFloatExpr(x,LinFloatExpr::NT_ADD,c);
415 }
416 LinFloatExpr
417 operator +(const LinFloatExpr& e, const FloatVal& c) {
418 return LinFloatExpr(e,LinFloatExpr::NT_ADD,c);
419 }
420 LinFloatExpr
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 }
429 LinFloatExpr
430 operator +(const FloatVar& x, const LinFloatExpr& e) {
431 if (x.assigned())
432 return x.val() + e;
433 else
434 return LinFloatExpr(x,LinFloatExpr::NT_ADD,e);
435 }
436 LinFloatExpr
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 }
443 LinFloatExpr
444 operator +(const LinFloatExpr& e1, const LinFloatExpr& e2) {
445 return LinFloatExpr(e1,LinFloatExpr::NT_ADD,e2);
446 }
447
448 LinFloatExpr
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
453 return LinFloatExpr(x,LinFloatExpr::NT_SUB,c);
454 }
455 LinFloatExpr
456 operator -(const FloatVal& c, const LinFloatExpr& e) {
457 return LinFloatExpr(e,LinFloatExpr::NT_SUB,c);
458 }
459 LinFloatExpr
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 }
466 LinFloatExpr
467 operator -(const LinFloatExpr& e, const FloatVal& c) {
468 return LinFloatExpr(e,LinFloatExpr::NT_ADD,-c);
469 }
470 LinFloatExpr
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 }
479 LinFloatExpr
480 operator -(const FloatVar& x, const LinFloatExpr& e) {
481 if (x.assigned())
482 return x.val() - e;
483 else
484 return LinFloatExpr(x,LinFloatExpr::NT_SUB,e);
485 }
486 LinFloatExpr
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 }
493 LinFloatExpr
494 operator -(const LinFloatExpr& e1, const LinFloatExpr& e2) {
495 return LinFloatExpr(e1,LinFloatExpr::NT_SUB,e2);
496 }
497
498 LinFloatExpr
499 operator -(const FloatVar& x) {
500 if (x.assigned())
501 return LinFloatExpr(-x.val());
502 else
503 return LinFloatExpr(x,LinFloatExpr::NT_SUB,0);
504 }
505 LinFloatExpr
506 operator -(const LinFloatExpr& e) {
507 return LinFloatExpr(e,LinFloatExpr::NT_SUB,0);
508 }
509
510 LinFloatExpr
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 }
520 LinFloatExpr
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 }
530 LinFloatExpr
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 }
537 LinFloatExpr
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
545 LinFloatExpr
546 sum(const FloatVarArgs& x) {
547 return LinFloatExpr(x);
548 }
549
550 LinFloatExpr
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);
560 FloatVar x(home,Float::Limits::min,Float::Limits::max);
561 return x;
562 }
563
564}
565
566#endif
567
568// STATISTICS: minimodel-any