float-expr.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Vincent Barichard <Vincent.Barichard@univ-angers.fr>
00005  *
00006  *  Copyright:
00007  *     Vincent Barichard, 2012
00008  *
00009  *  Last modified:
00010  *     $Date: 2016-08-08 16:24:17 +0200 (Mon, 08 Aug 2016) $ by $Author: schulte $
00011  *     $Revision: 15141 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/minimodel.hh>
00039 
00040 #ifdef GECODE_HAS_FLOAT_VARS
00041 
00042 #include <gecode/float/linear.hh>
00043 
00044 namespace Gecode {
00045 
00047   class LinFloatExpr::Node {
00048   public:
00050     unsigned int use;
00052     int n_float;
00054     NodeType t;
00056     Node *l, *r;
00058     union {
00060       Float::Linear::Term* tf;
00062       NonLinFloatExpr* ne;
00063     } sum;
00065     FloatVal a, c;
00067     FloatVar x_float;
00069     Node(void);
00071     GECODE_MINIMODEL_EXPORT
00072     void fill(Home home, Float::Linear::Term*& tf,
00073               FloatVal m, FloatVal& d) const;
00075     FloatVal fill(Home home, Float::Linear::Term* tf) const;
00077     bool decrement(void);
00079     ~Node(void);
00081     static void* operator new(size_t size);
00083     static void  operator delete(void* p,size_t size);
00084 
00085   };
00086 
00087   /*
00088    * Operations for nodes
00089    *
00090    */
00091   forceinline
00092   LinFloatExpr::Node::Node(void) : use(1) {
00093   }
00094 
00095   forceinline
00096   LinFloatExpr::Node::~Node(void) {
00097     switch (t) {
00098     case NT_SUM:
00099       if (n_float > 0)
00100         heap.free<Float::Linear::Term>(sum.tf,n_float);
00101       break;
00102     case NT_NONLIN:
00103       delete sum.ne;
00104       break;
00105     default: ;
00106     }
00107   }
00108 
00109   forceinline void*
00110   LinFloatExpr::Node::operator new(size_t size) {
00111     return heap.ralloc(size);
00112   }
00113 
00114   forceinline void
00115   LinFloatExpr::Node::operator delete(void* p, size_t) {
00116     heap.rfree(p);
00117   }
00118 
00119   bool
00120   LinFloatExpr::Node::decrement(void) {
00121     if (--use == 0) {
00122       if ((l != NULL) && l->decrement())
00123         delete l;
00124       if ((r != NULL) && r->decrement())
00125         delete r;
00126       return true;
00127     }
00128     return false;
00129   }
00130 
00131   /*
00132    * Operations for float expressions
00133    *
00134    */
00135 
00136   LinFloatExpr::LinFloatExpr(const LinFloatExpr& e)
00137     : n(e.n) {
00138     n->use++;
00139   }
00140 
00141   NonLinFloatExpr*
00142   LinFloatExpr::nlfe(void) const {
00143     return n->t == NT_NONLIN ? n->sum.ne : NULL;
00144   }
00145 
00146   FloatVal
00147   LinFloatExpr::Node::fill(Home home,
00148                            Float::Linear::Term* tf) const {
00149     FloatVal d=0;
00150     fill(home,tf,1.0,d);
00151     Float::Limits::check(d,"MiniModel::LinFloatExpr");
00152     return d;
00153   }
00154 
00155   void
00156   LinFloatExpr::post(Home home, FloatRelType frt) const {
00157     if (home.failed()) return;
00158     Region r(home);
00159     if (n->t==NT_ADD && n->l == NULL && n->r->t==NT_NONLIN) {
00160       n->r->sum.ne->post(home,frt,-n->c);
00161     } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==NULL) {
00162       switch (frt) {
00163       case FRT_LQ: frt=FRT_GQ; break;
00164       case FRT_GQ: frt=FRT_LQ; break;
00165       default: break;
00166       }
00167       n->r->sum.ne->post(home,frt,n->c);
00168     } else if (frt==FRT_EQ &&
00169                n->t==NT_SUB && n->r->t==NT_NONLIN &&
00170                n->l != NULL && n->l->t==NT_VAR
00171                && n->l->a==1) {
00172       (void) n->r->sum.ne->post(home,&n->l->x_float);
00173     } else if (frt==FRT_EQ &&
00174                n->t==NT_SUB && n->r->t==NT_VAR &&
00175                n->l != NULL && n->l->t==NT_NONLIN
00176                && n->r->a==1) {
00177       (void) n->l->sum.ne->post(home,&n->r->x_float);
00178     } else {
00179       Float::Linear::Term* fts =
00180         r.alloc<Float::Linear::Term>(n->n_float);
00181       FloatVal c = n->fill(home,fts);
00182       Float::Linear::post(home, fts, n->n_float, frt, -c);
00183     }
00184   }
00185 
00186   void
00187   LinFloatExpr::post(Home home, FloatRelType frt, const BoolVar& b) const {
00188     if (home.failed()) return;
00189     Region r(home);
00190     if (n->t==NT_ADD && n->l==NULL && n->r->t==NT_NONLIN) {
00191       n->r->sum.ne->post(home,frt,-n->c,b);
00192     } else if (n->t==NT_SUB && n->l==NULL && n->r->t==NT_NONLIN) {
00193       switch (frt) {
00194       case FRT_LQ: frt=FRT_GQ; break;
00195       case FRT_LE: frt=FRT_GR; break;
00196       case FRT_GQ: frt=FRT_LQ; break;
00197       case FRT_GR: frt=FRT_LE; break;
00198       default: break;
00199       }
00200       n->r->sum.ne->post(home,frt,n->c,b);
00201     } else {
00202       Float::Linear::Term* fts =
00203         r.alloc<Float::Linear::Term>(n->n_float);
00204       FloatVal c = n->fill(home,fts);
00205       Float::Linear::post(home, fts, n->n_float, frt, -c, b);
00206     }
00207 
00208   }
00209 
00210   FloatVar
00211   LinFloatExpr::post(Home home) const {
00212     if (home.failed()) return FloatVar(home,0,0);
00213     Region r(home);
00214     Float::Linear::Term* fts =
00215       r.alloc<Float::Linear::Term>(n->n_float+1);
00216     FloatVal c = n->fill(home,fts);
00217     if ((n->n_float == 1) && (c == 0) && (fts[0].a == 1))
00218       return fts[0].x;
00219     FloatNum min, max;
00220     Float::Linear::estimate(&fts[0],n->n_float,c,min,max);
00221     FloatVar x(home, min, max);
00222     fts[n->n_float].x = x; fts[n->n_float].a = -1;
00223     Float::Linear::post(home, fts, n->n_float+1, FRT_EQ, -c);
00224     return x;
00225 
00226   }
00227 
00228   LinFloatExpr::LinFloatExpr(void) :
00229     n(new Node) {
00230     n->n_float = 0;
00231     n->t = NT_VAR;
00232     n->l = n->r = NULL;
00233     n->a = 0;
00234   }
00235 
00236   LinFloatExpr::LinFloatExpr(const FloatVal& c) :
00237     n(new Node) {
00238     n->n_float = 0;
00239     n->t = NT_CONST;
00240     n->l = n->r = NULL;
00241     n->a = 0;
00242     Float::Limits::check(c,"MiniModel::LinFloatExpr");
00243     n->c = c;
00244   }
00245 
00246   LinFloatExpr::LinFloatExpr(const FloatVar& x) :
00247     n(new Node) {
00248     n->n_float = 1;
00249     n->t = NT_VAR;
00250     n->l = n->r = NULL;
00251     n->a = 1.0;
00252     n->x_float = x;
00253   }
00254 
00255   LinFloatExpr::LinFloatExpr(const FloatVar& x, FloatVal a) :
00256     n(new Node) {
00257     n->n_float = 1;
00258     n->t = NT_VAR;
00259     n->l = n->r = NULL;
00260     n->a = a;
00261     n->x_float = x;
00262   }
00263 
00264   LinFloatExpr::LinFloatExpr(const FloatVarArgs& x) :
00265     n(new Node) {
00266     n->n_float = x.size();
00267     n->t = NT_SUM;
00268     n->l = n->r = NULL;
00269     if (x.size() > 0) {
00270       n->sum.tf = heap.alloc<Float::Linear::Term>(x.size());
00271       for (int i=x.size(); i--; ) {
00272         n->sum.tf[i].x = x[i];
00273         n->sum.tf[i].a = 1.0;
00274       }
00275     }
00276   }
00277 
00278   LinFloatExpr::LinFloatExpr(const FloatValArgs& a, const FloatVarArgs& x) :
00279     n(new Node) {
00280     if (a.size() != x.size())
00281       throw Float::ArgumentSizeMismatch("MiniModel::LinFloatExpr");
00282     n->n_float = x.size();
00283     n->t = NT_SUM;
00284     n->l = n->r = NULL;
00285     if (x.size() > 0) {
00286       n->sum.tf = heap.alloc<Float::Linear::Term>(x.size());
00287       for (int i=x.size(); i--; ) {
00288         n->sum.tf[i].x = x[i];
00289         n->sum.tf[i].a = a[i];
00290       }
00291     }
00292   }
00293 
00294   LinFloatExpr::LinFloatExpr(const LinFloatExpr& e0, NodeType t, const LinFloatExpr& e1) :
00295     n(new Node) {
00296     n->n_float = e0.n->n_float + e1.n->n_float;
00297     n->t = t;
00298     n->l = e0.n; n->l->use++;
00299     n->r = e1.n; n->r->use++;
00300   }
00301 
00302   LinFloatExpr::LinFloatExpr(const LinFloatExpr& e, NodeType t, const FloatVal& c) :
00303     n(new Node) {
00304     n->n_float = e.n->n_float;
00305     n->t = t;
00306     n->l = NULL;
00307     n->r = e.n; n->r->use++;
00308     n->c = c;
00309   }
00310 
00311   LinFloatExpr::LinFloatExpr(FloatVal a, const LinFloatExpr& e) :
00312     n(new Node) {
00313     n->n_float = e.n->n_float;
00314     n->t = NT_MUL;
00315     n->l = e.n; n->l->use++;
00316     n->r = NULL;
00317     n->a = a;
00318   }
00319 
00320   LinFloatExpr::LinFloatExpr(NonLinFloatExpr* e) :
00321     n(new Node) {
00322     n->n_float = 1;
00323     n->t = NT_NONLIN;
00324     n->l = n->r = NULL;
00325     n->a = 0;
00326     n->sum.ne = e;
00327   }
00328 
00329   const LinFloatExpr&
00330   LinFloatExpr::operator =(const LinFloatExpr& e) {
00331     if (this != &e) {
00332       if (n->decrement())
00333         delete n;
00334       n = e.n; n->use++;
00335     }
00336     return *this;
00337   }
00338 
00339   LinFloatExpr::~LinFloatExpr(void) {
00340     if (n->decrement())
00341       delete n;
00342   }
00343 
00344 
00345   void
00346   LinFloatExpr::Node::fill(Home home,
00347                            Float::Linear::Term*& tf,
00348                            FloatVal m, FloatVal& d) const {
00349     switch (this->t) {
00350     case NT_CONST:
00351       Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
00352       d += m*c;
00353       break;
00354     case NT_VAR:
00355       Float::Limits::check(m*a,"MiniModel::LinFloatExpr");
00356       tf->a=m*a; tf->x=x_float; tf++;
00357       break;
00358     case NT_NONLIN:
00359       tf->a=m; tf->x=sum.ne->post(home, NULL); tf++;
00360       break;
00361     case NT_SUM:
00362       for (int i=n_float; i--; ) {
00363         Float::Limits::check(m*sum.tf[i].a,"MiniModel::LinFloatExpr");
00364         tf[i].x = sum.tf[i].x; tf[i].a = m*sum.tf[i].a;
00365       }
00366       tf += n_float;
00367       break;
00368     case NT_ADD:
00369       if (l == NULL) {
00370         Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
00371         d += m*c;
00372       } else {
00373         l->fill(home,tf,m,d);
00374       }
00375       r->fill(home,tf,m,d);
00376       break;
00377     case NT_SUB:
00378       if (l == NULL) {
00379         Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
00380         d += m*c;
00381       } else {
00382         l->fill(home,tf,m,d);
00383       }
00384       r->fill(home,tf,-m,d);
00385       break;
00386     case NT_MUL:
00387       Float::Limits::check(m*a,"MiniModel::LinFloatExpr");
00388       l->fill(home,tf,m*a,d);
00389       break;
00390     default:
00391       GECODE_NEVER;
00392     }
00393   }
00394 
00395 
00396   /*
00397    * Operators
00398    *
00399    */
00400   LinFloatExpr
00401   operator +(const FloatVal& c, const FloatVar& x) {
00402     if (x.assigned() && Float::Limits::valid(c+x.val()))
00403       return LinFloatExpr(c+x.val());
00404     else
00405       return LinFloatExpr(x,LinFloatExpr::NT_ADD,c);
00406   }
00407   LinFloatExpr
00408   operator +(const FloatVal& c, const LinFloatExpr& e) {
00409     return LinFloatExpr(e,LinFloatExpr::NT_ADD,c);
00410   }
00411   LinFloatExpr
00412   operator +(const FloatVar& x, const FloatVal& c) {
00413     if (x.assigned() && Float::Limits::valid(c+x.val()))
00414       return LinFloatExpr(c+x.val());
00415     else
00416       return LinFloatExpr(x,LinFloatExpr::NT_ADD,c);
00417   }
00418   LinFloatExpr
00419   operator +(const LinFloatExpr& e, const FloatVal& c) {
00420     return LinFloatExpr(e,LinFloatExpr::NT_ADD,c);
00421   }
00422   LinFloatExpr
00423   operator +(const FloatVar& x, const FloatVar& y) {
00424     if (x.assigned())
00425       return x.val() + y;
00426     else if (y.assigned())
00427       return x + y.val();
00428     else
00429       return LinFloatExpr(x,LinFloatExpr::NT_ADD,(const LinFloatExpr&)y);
00430   }
00431   LinFloatExpr
00432   operator +(const FloatVar& x, const LinFloatExpr& e) {
00433     if (x.assigned())
00434       return x.val() + e;
00435     else
00436       return LinFloatExpr(x,LinFloatExpr::NT_ADD,e);
00437   }
00438   LinFloatExpr
00439   operator +(const LinFloatExpr& e, const FloatVar& x) {
00440     if (x.assigned())
00441       return e + x.val();
00442     else
00443       return LinFloatExpr(e,LinFloatExpr::NT_ADD,(const LinFloatExpr&)x);
00444   }
00445   LinFloatExpr
00446   operator +(const LinFloatExpr& e1, const LinFloatExpr& e2) {
00447     return LinFloatExpr(e1,LinFloatExpr::NT_ADD,e2);
00448   }
00449 
00450   LinFloatExpr
00451   operator -(const FloatVal& c, const FloatVar& x) {
00452     if (x.assigned() && Float::Limits::valid(c-x.val()))
00453       return LinFloatExpr(c-x.val());
00454     else
00455       return LinFloatExpr(x,LinFloatExpr::NT_SUB,c);
00456   }
00457   LinFloatExpr
00458   operator -(const FloatVal& c, const LinFloatExpr& e) {
00459     return LinFloatExpr(e,LinFloatExpr::NT_SUB,c);
00460   }
00461   LinFloatExpr
00462   operator -(const FloatVar& x, const FloatVal& c) {
00463     if (x.assigned() && Float::Limits::valid(x.val()-c))
00464       return LinFloatExpr(x.val()-c);
00465     else
00466       return LinFloatExpr(x,LinFloatExpr::NT_ADD,-c);
00467   }
00468   LinFloatExpr
00469   operator -(const LinFloatExpr& e, const FloatVal& c) {
00470     return LinFloatExpr(e,LinFloatExpr::NT_ADD,-c);
00471   }
00472   LinFloatExpr
00473   operator -(const FloatVar& x, const FloatVar& y) {
00474     if (x.assigned())
00475       return x.val() - y;
00476     else if (y.assigned())
00477       return x - y.val();
00478     else
00479       return LinFloatExpr(x,LinFloatExpr::NT_SUB,(const LinFloatExpr&)y);
00480   }
00481   LinFloatExpr
00482   operator -(const FloatVar& x, const LinFloatExpr& e) {
00483     if (x.assigned())
00484       return x.val() - e;
00485     else
00486       return LinFloatExpr(x,LinFloatExpr::NT_SUB,e);
00487   }
00488   LinFloatExpr
00489   operator -(const LinFloatExpr& e, const FloatVar& x) {
00490     if (x.assigned())
00491       return e - x.val();
00492     else
00493       return LinFloatExpr(e,LinFloatExpr::NT_SUB,(const LinFloatExpr&)x);
00494   }
00495   LinFloatExpr
00496   operator -(const LinFloatExpr& e1, const LinFloatExpr& e2) {
00497     return LinFloatExpr(e1,LinFloatExpr::NT_SUB,e2);
00498   }
00499 
00500   LinFloatExpr
00501   operator -(const FloatVar& x) {
00502     if (x.assigned())
00503       return LinFloatExpr(-x.val());
00504     else
00505       return LinFloatExpr(x,LinFloatExpr::NT_SUB,0);
00506   }
00507   LinFloatExpr
00508   operator -(const LinFloatExpr& e) {
00509     return LinFloatExpr(e,LinFloatExpr::NT_SUB,0);
00510   }
00511 
00512   LinFloatExpr
00513   operator *(const FloatVal& a, const FloatVar& x) {
00514     if (a == 0)
00515       return LinFloatExpr(0.0);
00516     else if (x.assigned() &&
00517              Float::Limits::valid(a*x.val()))
00518       return LinFloatExpr(a*x.val());
00519     else
00520       return LinFloatExpr(x,a);
00521   }
00522   LinFloatExpr
00523   operator *(const FloatVar& x, const FloatVal& a) {
00524     if (a == 0)
00525       return LinFloatExpr(0.0);
00526     else if (x.assigned() &&
00527              Float::Limits::valid(a*x.val()))
00528       return LinFloatExpr(a*x.val());
00529     else
00530       return LinFloatExpr(x,a);
00531   }
00532   LinFloatExpr
00533   operator *(const LinFloatExpr& e, const FloatVal& a) {
00534     if (a == 0)
00535       return LinFloatExpr(0.0);
00536     else
00537       return LinFloatExpr(a,e);
00538   }
00539   LinFloatExpr
00540   operator *(const FloatVal& a, const LinFloatExpr& e) {
00541     if (a == 0)
00542       return LinFloatExpr(0.0);
00543     else
00544       return LinFloatExpr(a,e);
00545   }
00546 
00547   LinFloatExpr
00548   sum(const FloatVarArgs& x) {
00549     return LinFloatExpr(x);
00550   }
00551 
00552   LinFloatExpr
00553   sum(const FloatValArgs& a, const FloatVarArgs& x) {
00554     return LinFloatExpr(a,x);
00555   }
00556 
00557   FloatVar
00558   expr(Home home, const LinFloatExpr& e) {
00559     PostInfo pi(home);
00560     if (!home.failed())
00561       return e.post(home);
00562     FloatVar x(home,Float::Limits::min,Float::Limits::max);
00563     return x;
00564   }
00565 
00566 }
00567 
00568 #endif
00569 
00570 // STATISTICS: minimodel-any