Generated on Thu Mar 22 10:39:43 2012 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: 2011-01-21 16:01:14 +0100 (Fri, 21 Jan 2011) $ by $Author: schulte $
00015  *     $Revision: 11553 $
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(const LinExpr& e)
00087     : n(e.n) {
00088     n->use++;
00089   }
00090 
00091   forceinline int
00092   LinExpr::Node::fill(Home home, IntConLevel icl,
00093                       Int::Linear::Term<Int::IntView>* ti, 
00094                       Int::Linear::Term<Int::BoolView>* tb) const {
00095     double d=0;
00096     fill(home,icl,ti,tb,1.0,d);
00097     Int::Limits::check(d,"MiniModel::LinExpr");
00098     return static_cast<int>(d);
00099   }
00100 
00101   inline void
00102   LinExpr::post(Home home, IntRelType irt, IntConLevel icl) const {
00103     if (home.failed()) return;
00104     Region r(home);
00105     if (n->n_bool == 0) {
00106       // Only integer variables
00107       if (n->t==NT_ADD && n->l == NULL && n->r->t==NT_NONLIN) {
00108         n->r->sum.ne->post(home,irt,-n->c,icl);
00109       } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==NULL) {
00110         switch (irt) {
00111         case IRT_LQ: irt=IRT_GQ; break;
00112         case IRT_LE: irt=IRT_GR; break;
00113         case IRT_GQ: irt=IRT_LQ; break;
00114         case IRT_GR: irt=IRT_LE; break;
00115         default: break;
00116         }
00117         n->r->sum.ne->post(home,irt,n->c,icl);
00118       } else if (irt==IRT_EQ &&
00119                  n->t==NT_SUB && n->r->t==NT_NONLIN &&
00120                  n->l != NULL && n->l->t==NT_VAR_INT
00121                  && n->l->a==1) {
00122         (void) n->r->sum.ne->post(home,&n->l->x_int,icl);
00123       } else if (irt==IRT_EQ &&
00124                  n->t==NT_SUB && n->r->t==NT_VAR_INT &&
00125                  n->l != NULL && n->l->t==NT_NONLIN
00126                  && n->r->a==1) {
00127         (void) n->l->sum.ne->post(home,&n->r->x_int,icl);
00128       } else {
00129         Int::Linear::Term<Int::IntView>* its =
00130           r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
00131         int c = n->fill(home,icl,its,NULL);
00132         Int::Linear::post(home, its, n->n_int, irt, -c, icl);
00133       }
00134     } else if (n->n_int == 0) {
00135       // Only Boolean variables
00136       Int::Linear::Term<Int::BoolView>* bts =
00137         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00138       int c = n->fill(home,icl,NULL,bts);
00139       Int::Linear::post(home, bts, n->n_bool, irt, -c, icl);
00140     } else if (n->n_bool == 1) {
00141       // Integer variables and only one Boolean variable
00142       Int::Linear::Term<Int::IntView>* its =
00143         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00144       Int::Linear::Term<Int::BoolView>* bts =
00145         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00146       int c = n->fill(home,icl,its,bts);
00147       IntVar x(home,0,1);
00148       channel(home,bts[0].x,x);
00149       its[n->n_int].x = x;
00150       its[n->n_int].a = bts[0].a;
00151       Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
00152     } else {
00153       // Both integer and Boolean variables
00154       Int::Linear::Term<Int::IntView>* its =
00155         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00156       Int::Linear::Term<Int::BoolView>* bts =
00157         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00158       int c = n->fill(home,icl,its,bts);
00159       int min, max;
00160       Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
00161       IntVar x(home,min,max);
00162       its[n->n_int].x = x; its[n->n_int].a = 1;
00163       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00164       Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
00165     }
00166   }
00167 
00168   inline void
00169   LinExpr::post(Home home, IntRelType irt, const BoolVar& b,
00170                 IntConLevel icl) const {
00171     if (home.failed()) return;
00172     Region r(home);
00173     if (n->n_bool == 0) {
00174       // Only integer variables
00175       if (n->t==NT_ADD && n->l==NULL && n->r->t==NT_NONLIN) {
00176         n->r->sum.ne->post(home,irt,-n->c,b,icl);
00177       } else if (n->t==NT_SUB && n->l==NULL && n->r->t==NT_NONLIN) {
00178         switch (irt) {
00179         case IRT_LQ: irt=IRT_GQ; break;
00180         case IRT_LE: irt=IRT_GR; break;
00181         case IRT_GQ: irt=IRT_LQ; break;
00182         case IRT_GR: irt=IRT_LE; break;
00183         default: break;
00184         }
00185         n->r->sum.ne->post(home,irt,n->c,b,icl);
00186       } else {
00187         Int::Linear::Term<Int::IntView>* its =
00188           r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int);
00189         int c = n->fill(home,icl,its,NULL);
00190         Int::Linear::post(home, its, n->n_int, irt, -c, b, icl);
00191       }
00192     } else if (n->n_int == 0) {
00193       // Only Boolean variables
00194       Int::Linear::Term<Int::BoolView>* bts =
00195         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00196       int c = n->fill(home,icl,NULL,bts);
00197       Int::Linear::post(home, bts, n->n_bool, irt, -c, b, icl);
00198     } else if (n->n_bool == 1) {
00199       // Integer variables and only one Boolean variable
00200       Int::Linear::Term<Int::IntView>* its =
00201         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00202       Int::Linear::Term<Int::BoolView>* bts =
00203         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00204       int c = n->fill(home,icl,its,bts);
00205       IntVar x(home,0,1);
00206       channel(home,bts[0].x,x);
00207       its[n->n_int].x = x;
00208       its[n->n_int].a = bts[0].a;
00209       Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
00210     } else {
00211       // Both integer and Boolean variables
00212       Int::Linear::Term<Int::IntView>* its =
00213         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00214       Int::Linear::Term<Int::BoolView>* bts =
00215         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00216       int c = n->fill(home,icl,its,bts);
00217       int min, max;
00218       Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
00219       IntVar x(home,min,max);
00220       its[n->n_int].x = x; its[n->n_int].a = 1;
00221       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00222       Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
00223     }
00224   }
00225 
00226   inline IntVar
00227   LinExpr::post(Home home, IntConLevel icl) const {
00228     if (home.failed()) return IntVar(home,0,0);
00229     Region r(home);
00230     if (n->n_bool == 0) {
00231       // Only integer variables
00232       Int::Linear::Term<Int::IntView>* its =
00233         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
00234       int c = n->fill(home,icl,its,NULL);
00235       if ((n->n_int == 1) && (c == 0) && (its[0].a == 1))
00236         return its[0].x;
00237       int min, max;
00238       Int::Linear::estimate(&its[0],n->n_int,c,min,max);
00239       IntVar x(home, min, max);
00240       its[n->n_int].x = x; its[n->n_int].a = -1;
00241       Int::Linear::post(home, its, n->n_int+1, IRT_EQ, -c, icl);
00242       return x;
00243     } else if (n->n_int == 0) {
00244       // Only Boolean variables
00245       Int::Linear::Term<Int::BoolView>* bts =
00246         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00247       int c = n->fill(home,icl,NULL,bts);
00248       int min, max;
00249       Int::Linear::estimate(&bts[0],n->n_bool,c,min,max);
00250       IntVar x(home, min, max);
00251       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, -c, icl);
00252       return x;
00253     } else if (n->n_bool == 1) {
00254       // Integer variables and single Boolean variable
00255       Int::Linear::Term<Int::IntView>* its =
00256         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
00257       Int::Linear::Term<Int::BoolView>* bts =
00258         r.alloc<Int::Linear::Term<Int::BoolView> >(1);
00259       int c = n->fill(home,icl,its,bts);
00260       IntVar x(home, 0, 1);
00261       channel(home, x, bts[0].x);
00262       its[n->n_int].x = x; its[n->n_int].a = bts[0].a;
00263       int y_min, y_max;
00264       Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
00265       IntVar y(home, y_min, y_max);
00266       its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
00267       Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
00268       return y;
00269     } else {
00270       // Both integer and Boolean variables
00271       Int::Linear::Term<Int::IntView>* its =
00272         r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
00273       Int::Linear::Term<Int::BoolView>* bts =
00274         r.alloc<Int::Linear::Term<Int::BoolView> >(n->n_bool);
00275       int c = n->fill(home,icl,its,bts);
00276       int x_min, x_max;
00277       Int::Linear::estimate(&bts[0],n->n_bool,0,x_min,x_max);
00278       IntVar x(home, x_min, x_max);
00279       Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
00280       its[n->n_int].x = x; its[n->n_int].a = 1;
00281       int y_min, y_max;
00282       Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
00283       IntVar y(home, y_min, y_max);
00284       its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
00285       Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
00286       return y;
00287     }
00288   }
00289 
00290   forceinline NonLinExpr*
00291   LinExpr::nle(void) const {
00292     return n->t == NT_NONLIN ? n->sum.ne : NULL;
00293   }
00294 
00295 }
00296 
00297 // STATISTICS: minimodel-any