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