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