Generated on Tue Jul 27 2010 21:59:17 for Gecode by doxygen 1.7.1

lin-expr.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Guido Tack <tack@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2010
00011  *     Guido Tack, 2004
00012  *
00013  *  Last modified:
00014  *     $Date: 2010-07-14 20:32:01 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $
00015  *     $Revision: 11195 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 namespace Gecode {
00043 
00044   /*
00045    * Operations for nodes
00046    *
00047    */
00048   forceinline
00049   LinExpr::Node::Node(void) : use(1) {
00050   }
00051 
00052   forceinline
00053   LinExpr::Node::~Node(void) {
00054     switch (t) {
00055     case NT_SUM_INT:
00056       if (n_int > 0)
00057         heap.free<Int::Linear::Term<Int::IntView> >(sum.ti,n_int);
00058       break;
00059     case NT_SUM_BOOL:
00060       if (n_bool > 0)
00061         heap.free<Int::Linear::Term<Int::BoolView> >(sum.tb,n_bool);
00062       break;
00063     case NT_NONLIN:
00064       delete sum.ne;
00065       break;
00066     default: ;
00067     }
00068   }
00069 
00070   forceinline void*
00071   LinExpr::Node::operator new(size_t size) {
00072     return heap.ralloc(size);
00073   }
00074 
00075   forceinline void
00076   LinExpr::Node::operator delete(void* p, size_t) {
00077     heap.rfree(p);
00078   }
00079 
00080 
00081   /*
00082    * Operations for expressions
00083    *
00084    */
00085   forceinline
00086   LinExpr::LinExpr(void) :
00087     n(new Node) {
00088     n->n_int = n->n_bool = 0;
00089     n->t = NT_VAR_INT;
00090     n->l = n->r = NULL;
00091     n->a = 0;
00092   }
00093 
00094   forceinline
00095   LinExpr::LinExpr(double c) :
00096     n(new Node) {
00097     n->n_int = n->n_bool = 0;
00098     n->t = NT_CONST;
00099     n->l = n->r = NULL;
00100     n->a = 0;
00101     Int::Limits::check(c,"MiniModel::LinExpr");
00102     n->c = static_cast<int>(c);
00103   }
00104 
00105   forceinline
00106   LinExpr::LinExpr(const LinExpr& e)
00107     : n(e.n) {
00108     n->use++;
00109   }
00110 
00111   forceinline
00112   LinExpr::LinExpr(const IntVar& x, int a) :
00113     n(new Node) {
00114     n->n_int = 1;
00115     n->n_bool = 0;
00116     n->t = NT_VAR_INT;
00117     n->l = n->r = NULL;
00118     n->a = a;
00119     n->x_int = x;
00120   }
00121 
00122   forceinline
00123   LinExpr::LinExpr(const BoolVar& x, int a) :
00124     n(new Node) {
00125     n->n_int = 0;
00126     n->n_bool = 1;
00127     n->t = NT_VAR_BOOL;
00128     n->l = n->r = NULL;
00129     n->a = a;
00130     n->x_bool = x;
00131   }
00132 
00133   forceinline
00134   LinExpr::LinExpr(const IntVarArgs& x) :
00135     n(new Node) {
00136     n->n_int = x.size();
00137     n->n_bool = 0;
00138     n->t = NT_SUM_INT;
00139     n->l = n->r = NULL;
00140     if (x.size() > 0) {
00141       n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
00142       for (int i=x.size(); i--; ) {
00143         n->sum.ti[i].x = x[i];
00144         n->sum.ti[i].a = 1;
00145       }
00146     }
00147   }
00148 
00149   forceinline
00150   LinExpr::LinExpr(const IntArgs& a, const IntVarArgs& x) :
00151     n(new Node) {
00152     if (a.size() != x.size())
00153       throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
00154     n->n_int = x.size();
00155     n->n_bool = 0;
00156     n->t = NT_SUM_INT;
00157     n->l = n->r = NULL;
00158     if (x.size() > 0) {
00159       n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
00160       for (int i=x.size(); i--; ) {
00161         n->sum.ti[i].x = x[i];
00162         n->sum.ti[i].a = a[i];
00163       }
00164     }
00165   }
00166 
00167   forceinline
00168   LinExpr::LinExpr(const BoolVarArgs& x) :
00169     n(new Node) {
00170     n->n_int = 0;
00171     n->n_bool = x.size();
00172     n->t = NT_SUM_BOOL;
00173     n->l = n->r = NULL;
00174     if (x.size() > 0) {
00175       n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
00176       for (int i=x.size(); i--; ) {
00177         n->sum.tb[i].x = x[i];
00178         n->sum.tb[i].a = 1;
00179       }
00180     }
00181   }
00182 
00183   forceinline
00184   LinExpr::LinExpr(const IntArgs& a, const BoolVarArgs& x) :
00185     n(new Node) {
00186     if (a.size() != x.size())
00187       throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
00188     n->n_int = 0;
00189     n->n_bool = x.size();
00190     n->t = NT_SUM_BOOL;
00191     n->l = n->r = NULL;
00192     if (x.size() > 0) {
00193       n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
00194       for (int i=x.size(); i--; ) {
00195         n->sum.tb[i].x = x[i];
00196         n->sum.tb[i].a = a[i];
00197       }
00198     }
00199   }
00200 
00201   forceinline
00202   LinExpr::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) :
00203     n(new Node) {
00204     n->n_int = e0.n->n_int + e1.n->n_int;
00205     n->n_bool = e0.n->n_bool + e1.n->n_bool;
00206     n->t = t;
00207     n->l = e0.n; n->l->use++;
00208     n->r = e1.n; n->r->use++;
00209   }
00210 
00211   forceinline
00212   LinExpr::LinExpr(const LinExpr& e, NodeType t, int c) :
00213     n(new Node) {
00214     n->n_int = e.n->n_int;
00215     n->n_bool = e.n->n_bool;
00216     n->t = t;
00217     n->l = NULL;
00218     n->r = e.n; n->r->use++;
00219     n->c = c;
00220   }
00221 
00222   forceinline
00223   LinExpr::LinExpr(int a, const LinExpr& e) :
00224     n(new Node) {
00225     n->n_int = e.n->n_int;
00226     n->n_bool = e.n->n_bool;
00227     n->t = NT_MUL;
00228     n->l = e.n; n->l->use++;
00229     n->r = NULL;
00230     n->a = a;
00231   }
00232 
00233   forceinline
00234   LinExpr::LinExpr(NonLinExpr* e) :
00235     n(new Node) {
00236     n->n_int = 1;
00237     n->n_bool = 0;
00238     n->t = NT_NONLIN;
00239     n->l = n->r = NULL;
00240     n->a = 0;
00241     n->sum.ne = e;
00242   }
00243 
00244   forceinline int
00245   LinExpr::Node::fill(Home home, IntConLevel icl,
00246                       Int::Linear::Term<Int::IntView>* ti, 
00247                       Int::Linear::Term<Int::BoolView>* tb) const {
00248     double d=0;
00249     fill(home,icl,ti,tb,1.0,d);
00250     Int::Limits::check(d,"MiniModel::LinExpr");
00251     return static_cast<int>(d);
00252   }
00253 
00254   inline void
00255   LinExpr::post(Home home, IntRelType irt, IntConLevel icl) const {
00256     if (home.failed()) return;
00257     Region r(home);
00258     if (n->n_bool == 0) {
00259       // Only integer variables
00260       if (n->t==NT_ADD && n->l == NULL && n->r->t==NT_NONLIN) {
00261         n->r->sum.ne->post(home,irt,-n->c,icl);
00262       } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==NULL) {
00263         switch (irt) {
00264         case IRT_LQ: irt=IRT_GQ; break;
00265         case IRT_LE: irt=IRT_GR; break;
00266         case IRT_GQ: irt=IRT_LQ; break;
00267         case IRT_GR: irt=IRT_LE; break;
00268         default: break;
00269         }
00270         n->r->sum.ne->post(home,irt,n->c,icl);
00271       } else if (irt==IRT_EQ &&
00272                  n->t==NT_SUB && n->r->t==NT_NONLIN &&
00273                  n->l != NULL && n->l->t==NT_VAR_INT
00274                  && n->l->a==1) {
00275         (void) n->r->sum.ne->post(home,&n->l->x_int,icl);
00276       } else if (irt==IRT_EQ &&
00277                  n->t==NT_SUB && n->r->t==NT_VAR_INT &&
00278                  n->l != NULL && n->l->t==NT_NONLIN
00279                  && n->r->a==1) {
00280         (void) n->l->sum.ne->post(home,&n->r->x_int,icl);
00281       } else {
00282         Int::Linear::Term<Int::IntView>* its =
00283           r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
00284         int c = n->fill(home,icl,its,NULL);
00285         Int::Linear::post(home, its, n->n_int, irt, -c, icl);
00286       }
00287     } else if (n->n_int == 0) {
00288       // Only Boolean variables
00289       Int::Linear::Term<Int::BoolView>* bts =
00290         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00291       int c = n->fill(home,icl,NULL,bts);
00292       Int::Linear::post(home, bts, n->n_bool, irt, -c, icl);
00293     } else if (n->n_bool == 1) {
00294       // Integer variables and only one Boolean variable
00295       Int::Linear::Term<Int::IntView>* its =
00296         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00297       Int::Linear::Term<Int::BoolView>* bts =
00298         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00299       int c = n->fill(home,icl,its,bts);
00300       IntVar x(home,0,1);
00301       channel(home,bts[0].x,x);
00302       its[n->n_int].x = x;
00303       its[n->n_int].a = bts[0].a;
00304       Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
00305     } else {
00306       // Both integer and Boolean variables
00307       Int::Linear::Term<Int::IntView>* its =
00308         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00309       Int::Linear::Term<Int::BoolView>* bts =
00310         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00311       int c = n->fill(home,icl,its,bts);
00312       int min, max;
00313       Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
00314       IntVar x(home,min,max);
00315       its[n->n_int].x = x; its[n->n_int].a = 1;
00316       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00317       Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
00318     }
00319   }
00320 
00321   inline void
00322   LinExpr::post(Home home, IntRelType irt, const BoolVar& b,
00323                 IntConLevel icl) const {
00324     if (home.failed()) return;
00325     Region r(home);
00326     if (n->n_bool == 0) {
00327       // Only integer variables
00328       if (n->t==NT_ADD && n->l==NULL && n->r->t==NT_NONLIN) {
00329         n->r->sum.ne->post(home,irt,-n->c,b,icl);
00330       } else if (n->t==NT_SUB && n->l==NULL && n->r->t==NT_NONLIN) {
00331         switch (irt) {
00332         case IRT_LQ: irt=IRT_GQ; break;
00333         case IRT_LE: irt=IRT_GR; break;
00334         case IRT_GQ: irt=IRT_LQ; break;
00335         case IRT_GR: irt=IRT_LE; break;
00336         default: break;
00337         }
00338         n->r->sum.ne->post(home,irt,n->c,b,icl);
00339       } else {
00340         Int::Linear::Term<Int::IntView>* its =
00341           r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
00342         int c = n->fill(home,icl,its,NULL);
00343         Int::Linear::post(home, its, n->n_int, irt, -c, b, icl);
00344       }
00345     } else if (n->n_int == 0) {
00346       // Only Boolean variables
00347       Int::Linear::Term<Int::BoolView>* bts =
00348         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00349       int c = n->fill(home,icl,NULL,bts);
00350       Int::Linear::post(home, bts, n->n_bool, irt, -c, b, icl);
00351     } else if (n->n_bool == 1) {
00352       // Integer variables and only one Boolean variable
00353       Int::Linear::Term<Int::IntView>* its =
00354         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00355       Int::Linear::Term<Int::BoolView>* bts =
00356         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00357       int c = n->fill(home,icl,its,bts);
00358       IntVar x(home,0,1);
00359       channel(home,bts[0].x,x);
00360       its[n->n_int].x = x;
00361       its[n->n_int].a = bts[0].a;
00362       Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
00363     } else {
00364       // Both integer and Boolean variables
00365       Int::Linear::Term<Int::IntView>* its =
00366         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00367       Int::Linear::Term<Int::BoolView>* bts =
00368         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00369       int c = n->fill(home,icl,its,bts);
00370       int min, max;
00371       Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
00372       IntVar x(home,min,max);
00373       its[n->n_int].x = x; its[n->n_int].a = 1;
00374       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00375       Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
00376     }
00377   }
00378 
00379   inline IntVar
00380   LinExpr::post(Home home, IntConLevel icl) const {
00381     if (home.failed()) return IntVar(home,0,0);
00382     Region r(home);
00383     if (n->n_bool == 0) {
00384       // Only integer variables
00385       Int::Linear::Term<Int::IntView>* its =
00386         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00387       int c = n->fill(home,icl,its,NULL);
00388       if ((n->n_int == 1) && (c == 0) && (its[0].a == 1))
00389         return its[0].x;
00390       int min, max;
00391       Int::Linear::estimate(&its[0],n->n_int,c,min,max);
00392       IntVar x(home, min, max);
00393       its[n->n_int].x = x; its[n->n_int].a = -1;
00394       Int::Linear::post(home, its, n->n_int+1, IRT_EQ, -c, icl);
00395       return x;
00396     } else if (n->n_int == 0) {
00397       // Only Boolean variables
00398       Int::Linear::Term<Int::BoolView>* bts =
00399         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00400       int c = n->fill(home,icl,NULL,bts);
00401       int min, max;
00402       Int::Linear::estimate(&bts[0],n->n_bool,c,min,max);
00403       IntVar x(home, min, max);
00404       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, -c, icl);
00405       return x;
00406     } else if (n->n_bool == 1) {
00407       // Integer variables and single Boolean variable
00408       Int::Linear::Term<Int::IntView>* its =
00409         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
00410       Int::Linear::Term<Int::BoolView>* bts =
00411         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00412       int c = n->fill(home,icl,its,bts);
00413       IntVar x(home, 0, 1);
00414       channel(home, x, bts[0].x);
00415       its[n->n_int].x = x; its[n->n_int].a = bts[0].a;
00416       int y_min, y_max;
00417       Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
00418       IntVar y(home, y_min, y_max);
00419       its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
00420       Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
00421       return y;
00422     } else {
00423       // Both integer and Boolean variables
00424       Int::Linear::Term<Int::IntView>* its =
00425         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
00426       Int::Linear::Term<Int::BoolView>* bts =
00427         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00428       int c = n->fill(home,icl,its,bts);
00429       int x_min, x_max;
00430       Int::Linear::estimate(&bts[0],n->n_bool,0,x_min,x_max);
00431       IntVar x(home, x_min, x_max);
00432       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00433       its[n->n_int].x = x; its[n->n_int].a = 1;
00434       int y_min, y_max;
00435       Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
00436       IntVar y(home, y_min, y_max);
00437       its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
00438       Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
00439       return y;
00440     }
00441   }
00442 
00443   forceinline NonLinExpr*
00444   LinExpr::nle(void) const {
00445     return n->t == NT_NONLIN ? n->sum.ne : NULL;
00446   }
00447 
00448 }
00449 
00450 // STATISTICS: minimodel-any