Generated on Mon May 10 06:46:43 2010 for Gecode by doxygen 1.6.3

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-02-04 11:04:52 +0100 (Thu, 04 Feb 2010) $ by $Author: schulte $
00015  *     $Revision: 10263 $
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     default: ;
00064     }
00065   }
00066 
00067   forceinline void*
00068   LinExpr::Node::operator new(size_t size) {
00069     return heap.ralloc(size);
00070   }
00071 
00072   forceinline void
00073   LinExpr::Node::operator delete(void* p, size_t) {
00074     heap.rfree(p);
00075   }
00076 
00077 
00078   /*
00079    * Operations for expressions
00080    *
00081    */
00082   forceinline
00083   LinExpr::LinExpr(void) :
00084     n(new Node) {
00085     n->n_int = n->n_bool = 0;
00086     n->t = NT_VAR_INT;
00087     n->l = n->r = NULL;
00088     n->a = 0;
00089   }
00090 
00091   forceinline
00092   LinExpr::LinExpr(const LinExpr& e)
00093     : n(e.n) {
00094     n->use++;
00095   }
00096 
00097   forceinline
00098   LinExpr::LinExpr(const IntVar& x, int a) :
00099     n(new Node) {
00100     n->n_int = 1;
00101     n->n_bool = 0;
00102     n->t = NT_VAR_INT;
00103     n->l = n->r = NULL;
00104     n->a = a;
00105     n->x_int = x;
00106   }
00107 
00108   forceinline
00109   LinExpr::LinExpr(const BoolVar& x, int a) :
00110     n(new Node) {
00111     n->n_int = 0;
00112     n->n_bool = 1;
00113     n->t = NT_VAR_BOOL;
00114     n->l = n->r = NULL;
00115     n->a = a;
00116     n->x_bool = x;
00117   }
00118 
00119   forceinline
00120   LinExpr::LinExpr(const IntVarArgs& x) :
00121     n(new Node) {
00122     n->n_int = x.size();
00123     n->n_bool = 0;
00124     n->t = NT_SUM_INT;
00125     n->l = n->r = NULL;
00126     if (x.size() > 0) {
00127       n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
00128       for (int i=x.size(); i--; ) {
00129         n->sum.ti[i].x = x[i];
00130         n->sum.ti[i].a = 1;
00131       }
00132     }
00133   }
00134 
00135   forceinline
00136   LinExpr::LinExpr(const IntArgs& a, const IntVarArgs& x) :
00137     n(new Node) {
00138     if (a.size() != x.size())
00139       throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
00140     n->n_int = x.size();
00141     n->n_bool = 0;
00142     n->t = NT_SUM_INT;
00143     n->l = n->r = NULL;
00144     if (x.size() > 0) {
00145       n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
00146       for (int i=x.size(); i--; ) {
00147         n->sum.ti[i].x = x[i];
00148         n->sum.ti[i].a = a[i];
00149       }
00150     }
00151   }
00152 
00153   forceinline
00154   LinExpr::LinExpr(const BoolVarArgs& x) :
00155     n(new Node) {
00156     n->n_int = 0;
00157     n->n_bool = x.size();
00158     n->t = NT_SUM_BOOL;
00159     n->l = n->r = NULL;
00160     if (x.size() > 0) {
00161       n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
00162       for (int i=x.size(); i--; ) {
00163         n->sum.tb[i].x = x[i];
00164         n->sum.tb[i].a = 1;
00165       }
00166     }
00167   }
00168 
00169   forceinline
00170   LinExpr::LinExpr(const IntArgs& a, const BoolVarArgs& x) :
00171     n(new Node) {
00172     if (a.size() != x.size())
00173       throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
00174     n->n_int = 0;
00175     n->n_bool = x.size();
00176     n->t = NT_SUM_BOOL;
00177     n->l = n->r = NULL;
00178     if (x.size() > 0) {
00179       n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
00180       for (int i=x.size(); i--; ) {
00181         n->sum.tb[i].x = x[i];
00182         n->sum.tb[i].a = a[i];
00183       }
00184     }
00185   }
00186 
00187   forceinline
00188   LinExpr::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) :
00189     n(new Node) {
00190     n->n_int = e0.n->n_int + e1.n->n_int;
00191     n->n_bool = e0.n->n_bool + e1.n->n_bool;
00192     n->t = t;
00193     n->l = e0.n; n->l->use++;
00194     n->r = e1.n; n->r->use++;
00195   }
00196 
00197   forceinline
00198   LinExpr::LinExpr(const LinExpr& e, NodeType t, int c) :
00199     n(new Node) {
00200     n->n_int = e.n->n_int;
00201     n->n_bool = e.n->n_bool;
00202     n->t = t;
00203     n->l = NULL;
00204     n->r = e.n; n->r->use++;
00205     n->c = c;
00206   }
00207 
00208   forceinline
00209   LinExpr::LinExpr(int a, const LinExpr& e) :
00210     n(new Node) {
00211     n->n_int = e.n->n_int;
00212     n->n_bool = e.n->n_bool;
00213     n->t = NT_MUL;
00214     n->l = e.n; n->l->use++;
00215     n->r = NULL;
00216     n->a = a;
00217   }
00218 
00219 
00220   forceinline int
00221   LinExpr::Node::fill(Int::Linear::Term<Int::IntView>* ti, 
00222                       Int::Linear::Term<Int::BoolView>* tb) const {
00223     double d=0;
00224     fill(ti,tb,1.0,d);
00225     Int::Limits::check(d,"MiniModel::LinExpr");
00226     return static_cast<int>(d);
00227   }
00228 
00229   forceinline void
00230   LinExpr::post(Home home, IntRelType irt, IntConLevel icl) const {
00231     Region r(home);
00232     if (n->n_bool == 0) {
00233       // Only integer variables
00234       Int::Linear::Term<Int::IntView>* its =
00235         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
00236       int c = n->fill(its,NULL);
00237       Int::Linear::post(home, its, n->n_int, irt, -c, icl);
00238     } else if (n->n_int == 0) {
00239       // Only Boolean variables
00240       Int::Linear::Term<Int::BoolView>* bts =
00241         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00242       int c = n->fill(NULL,bts);
00243       Int::Linear::post(home, bts, n->n_bool, irt, -c, icl);
00244     } else if (n->n_bool == 1) {
00245       // Integer variables and only one Boolean variable
00246       Int::Linear::Term<Int::IntView>* its =
00247         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00248       Int::Linear::Term<Int::BoolView>* bts =
00249         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00250       int c = n->fill(its,bts);
00251       IntVar x(home,0,1);
00252       channel(home,bts[0].x,x);
00253       its[n->n_int].x = x;
00254       its[n->n_int].a = bts[0].a;
00255       Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
00256     } else {
00257       // Both integer and Boolean variables
00258       Int::Linear::Term<Int::IntView>* its =
00259         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00260       Int::Linear::Term<Int::BoolView>* bts =
00261         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00262       int c = n->fill(its,bts);
00263       int min, max;
00264       Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
00265       IntVar x(home,min,max);
00266       its[n->n_int].x = x; its[n->n_int].a = 1;
00267       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00268       Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
00269     }
00270   }
00271 
00272   forceinline void
00273   LinExpr::post(Home home, IntRelType irt, const BoolVar& b,
00274                 IntConLevel icl) const {
00275     Region r(home);
00276     if (n->n_bool == 0) {
00277       // Only integer variables
00278       Int::Linear::Term<Int::IntView>* its =
00279         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
00280       int c = n->fill(its,NULL);
00281       Int::Linear::post(home, its, n->n_int, irt, -c, b, icl);
00282     } else if (n->n_int == 0) {
00283       // Only Boolean variables
00284       Int::Linear::Term<Int::BoolView>* bts =
00285         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00286       int c = n->fill(NULL,bts);
00287       Int::Linear::post(home, bts, n->n_bool, irt, -c, b, icl);
00288     } else if (n->n_bool == 1) {
00289       // Integer variables and only one Boolean variable
00290       Int::Linear::Term<Int::IntView>* its =
00291         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00292       Int::Linear::Term<Int::BoolView>* bts =
00293         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00294       int c = n->fill(its,bts);
00295       IntVar x(home,0,1);
00296       channel(home,bts[0].x,x);
00297       its[n->n_int].x = x;
00298       its[n->n_int].a = bts[0].a;
00299       Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
00300     } else {
00301       // Both integer and Boolean variables
00302       Int::Linear::Term<Int::IntView>* its =
00303         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00304       Int::Linear::Term<Int::BoolView>* bts =
00305         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00306       int c = n->fill(its,bts);
00307       int min, max;
00308       Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
00309       IntVar x(home,min,max);
00310       its[n->n_int].x = x; its[n->n_int].a = 1;
00311       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00312       Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
00313     }
00314   }
00315 
00316   forceinline IntVar
00317   LinExpr::post(Home home, IntConLevel icl) const {
00318     Region r(home);
00319     if (n->n_bool == 0) {
00320       // Only integer variables
00321       Int::Linear::Term<Int::IntView>* its =
00322         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00323       int c = n->fill(its,NULL);
00324       int min, max;
00325       Int::Linear::estimate(&its[0],n->n_int,c,min,max);
00326       IntVar x(home, min, max);
00327       its[n->n_int].x = x; its[n->n_int].a = -1;
00328       Int::Linear::post(home, its, n->n_int+1, IRT_EQ, -c, icl);
00329       return x;
00330     } else if (n->n_int == 0) {
00331       // Only Boolean variables
00332       Int::Linear::Term<Int::BoolView>* bts =
00333         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00334       int c = n->fill(NULL,bts);
00335       int min, max;
00336       Int::Linear::estimate(&bts[0],n->n_bool,c,min,max);
00337       IntVar x(home, min, max);
00338       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, -c, icl);
00339       return x;
00340     } else if (n->n_bool == 1) {
00341       // Integer variables and single Boolean variable
00342       Int::Linear::Term<Int::IntView>* its =
00343         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
00344       Int::Linear::Term<Int::BoolView>* bts =
00345         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00346       int c = n->fill(its,bts);
00347       IntVar x(home, 0, 1);
00348       channel(home, x, bts[0].x);
00349       its[n->n_int].x = x; its[n->n_int].a = bts[0].a;
00350       int y_min, y_max;
00351       Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
00352       IntVar y(home, y_min, y_max);
00353       its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
00354       Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
00355       return y;
00356     } else {
00357       // Both integer and Boolean variables
00358       Int::Linear::Term<Int::IntView>* its =
00359         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
00360       Int::Linear::Term<Int::BoolView>* bts =
00361         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00362       int c = n->fill(its,bts);
00363       int x_min, x_max;
00364       Int::Linear::estimate(&bts[0],n->n_bool,0,x_min,x_max);
00365       IntVar x(home, x_min, x_max);
00366       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00367       its[n->n_int].x = x; its[n->n_int].a = 1;
00368       int y_min, y_max;
00369       Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
00370       IntVar y(home, y_min, y_max);
00371       its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
00372       Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
00373       return y;
00374     }
00375   }
00376 
00377 }
00378 
00379 // STATISTICS: minimodel-any