Generated on Sun Aug 26 2012 08:43:17 for Gecode by doxygen 1.8.1.1
lin-expr.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Contributing authors:
7  * Guido Tack <tack@gecode.org>
8  *
9  * Copyright:
10  * Christian Schulte, 2010
11  * Guido Tack, 2004
12  *
13  * Last modified:
14  * $Date: 2011-01-22 02:01:14 +1100 (Sat, 22 Jan 2011) $ by $Author: schulte $
15  * $Revision: 11553 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode {
43 
44  /*
45  * Operations for nodes
46  *
47  */
49  LinExpr::Node::Node(void) : use(1) {
50  }
51 
53  LinExpr::Node::~Node(void) {
54  switch (t) {
55  case NT_SUM_INT:
56  if (n_int > 0)
57  heap.free<Int::Linear::Term<Int::IntView> >(sum.ti,n_int);
58  break;
59  case NT_SUM_BOOL:
60  if (n_bool > 0)
61  heap.free<Int::Linear::Term<Int::BoolView> >(sum.tb,n_bool);
62  break;
63  case NT_NONLIN:
64  delete sum.ne;
65  break;
66  default: ;
67  }
68  }
69 
70  forceinline void*
71  LinExpr::Node::operator new(size_t size) {
72  return heap.ralloc(size);
73  }
74 
75  forceinline void
76  LinExpr::Node::operator delete(void* p, size_t) {
77  heap.rfree(p);
78  }
79 
80 
81  /*
82  * Operations for expressions
83  *
84  */
86  LinExpr::LinExpr(const LinExpr& e)
87  : n(e.n) {
88  n->use++;
89  }
90 
91  forceinline int
92  LinExpr::Node::fill(Home home, IntConLevel icl,
95  double d=0;
96  fill(home,icl,ti,tb,1.0,d);
97  Int::Limits::check(d,"MiniModel::LinExpr");
98  return static_cast<int>(d);
99  }
100 
101  inline void
102  LinExpr::post(Home home, IntRelType irt, IntConLevel icl) const {
103  if (home.failed()) return;
104  Region r(home);
105  if (n->n_bool == 0) {
106  // Only integer variables
107  if (n->t==NT_ADD && n->l == NULL && n->r->t==NT_NONLIN) {
108  n->r->sum.ne->post(home,irt,-n->c,icl);
109  } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==NULL) {
110  switch (irt) {
111  case IRT_LQ: irt=IRT_GQ; break;
112  case IRT_LE: irt=IRT_GR; break;
113  case IRT_GQ: irt=IRT_LQ; break;
114  case IRT_GR: irt=IRT_LE; break;
115  default: break;
116  }
117  n->r->sum.ne->post(home,irt,n->c,icl);
118  } else if (irt==IRT_EQ &&
119  n->t==NT_SUB && n->r->t==NT_NONLIN &&
120  n->l != NULL && n->l->t==NT_VAR_INT
121  && n->l->a==1) {
122  (void) n->r->sum.ne->post(home,&n->l->x_int,icl);
123  } else if (irt==IRT_EQ &&
124  n->t==NT_SUB && n->r->t==NT_VAR_INT &&
125  n->l != NULL && n->l->t==NT_NONLIN
126  && n->r->a==1) {
127  (void) n->l->sum.ne->post(home,&n->r->x_int,icl);
128  } else {
131  int c = n->fill(home,icl,its,NULL);
132  Int::Linear::post(home, its, n->n_int, irt, -c, icl);
133  }
134  } else if (n->n_int == 0) {
135  // Only Boolean variables
138  int c = n->fill(home,icl,NULL,bts);
139  Int::Linear::post(home, bts, n->n_bool, irt, -c, icl);
140  } else if (n->n_bool == 1) {
141  // Integer variables and only one Boolean variable
143  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
146  int c = n->fill(home,icl,its,bts);
147  IntVar x(home,0,1);
148  channel(home,bts[0].x,x);
149  its[n->n_int].x = x;
150  its[n->n_int].a = bts[0].a;
151  Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
152  } else {
153  // Both integer and Boolean variables
155  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
158  int c = n->fill(home,icl,its,bts);
159  int min, max;
160  Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
161  IntVar x(home,min,max);
162  its[n->n_int].x = x; its[n->n_int].a = 1;
163  Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
164  Int::Linear::post(home, its, n->n_int+1, irt, -c, icl);
165  }
166  }
167 
168  inline void
169  LinExpr::post(Home home, IntRelType irt, const BoolVar& b,
170  IntConLevel icl) const {
171  if (home.failed()) return;
172  Region r(home);
173  if (n->n_bool == 0) {
174  // Only integer variables
175  if (n->t==NT_ADD && n->l==NULL && n->r->t==NT_NONLIN) {
176  n->r->sum.ne->post(home,irt,-n->c,b,icl);
177  } else if (n->t==NT_SUB && n->l==NULL && n->r->t==NT_NONLIN) {
178  switch (irt) {
179  case IRT_LQ: irt=IRT_GQ; break;
180  case IRT_LE: irt=IRT_GR; break;
181  case IRT_GQ: irt=IRT_LQ; break;
182  case IRT_GR: irt=IRT_LE; break;
183  default: break;
184  }
185  n->r->sum.ne->post(home,irt,n->c,b,icl);
186  } else {
189  int c = n->fill(home,icl,its,NULL);
190  Int::Linear::post(home, its, n->n_int, irt, -c, b, icl);
191  }
192  } else if (n->n_int == 0) {
193  // Only Boolean variables
196  int c = n->fill(home,icl,NULL,bts);
197  Int::Linear::post(home, bts, n->n_bool, irt, -c, b, icl);
198  } else if (n->n_bool == 1) {
199  // Integer variables and only one Boolean variable
201  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
204  int c = n->fill(home,icl,its,bts);
205  IntVar x(home,0,1);
206  channel(home,bts[0].x,x);
207  its[n->n_int].x = x;
208  its[n->n_int].a = bts[0].a;
209  Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
210  } else {
211  // Both integer and Boolean variables
213  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
216  int c = n->fill(home,icl,its,bts);
217  int min, max;
218  Int::Linear::estimate(&bts[0],n->n_bool,0,min,max);
219  IntVar x(home,min,max);
220  its[n->n_int].x = x; its[n->n_int].a = 1;
221  Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
222  Int::Linear::post(home, its, n->n_int+1, irt, -c, b, icl);
223  }
224  }
225 
226  inline IntVar
227  LinExpr::post(Home home, IntConLevel icl) const {
228  if (home.failed()) return IntVar(home,0,0);
229  Region r(home);
230  if (n->n_bool == 0) {
231  // Only integer variables
233  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+1);
234  int c = n->fill(home,icl,its,NULL);
235  if ((n->n_int == 1) && (c == 0) && (its[0].a == 1))
236  return its[0].x;
237  int min, max;
238  Int::Linear::estimate(&its[0],n->n_int,c,min,max);
239  IntVar x(home, min, max);
240  its[n->n_int].x = x; its[n->n_int].a = -1;
241  Int::Linear::post(home, its, n->n_int+1, IRT_EQ, -c, icl);
242  return x;
243  } else if (n->n_int == 0) {
244  // Only Boolean variables
247  int c = n->fill(home,icl,NULL,bts);
248  int min, max;
249  Int::Linear::estimate(&bts[0],n->n_bool,c,min,max);
250  IntVar x(home, min, max);
251  Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, -c, icl);
252  return x;
253  } else if (n->n_bool == 1) {
254  // Integer variables and single Boolean variable
256  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
259  int c = n->fill(home,icl,its,bts);
260  IntVar x(home, 0, 1);
261  channel(home, x, bts[0].x);
262  its[n->n_int].x = x; its[n->n_int].a = bts[0].a;
263  int y_min, y_max;
264  Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
265  IntVar y(home, y_min, y_max);
266  its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
267  Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
268  return y;
269  } else {
270  // Both integer and Boolean variables
272  r.alloc<Int::Linear::Term<Int::IntView> >(n->n_int+2);
275  int c = n->fill(home,icl,its,bts);
276  int x_min, x_max;
277  Int::Linear::estimate(&bts[0],n->n_bool,0,x_min,x_max);
278  IntVar x(home, x_min, x_max);
279  Int::Linear::post(home, bts, n->n_bool, IRT_EQ, x, 0, icl);
280  its[n->n_int].x = x; its[n->n_int].a = 1;
281  int y_min, y_max;
282  Int::Linear::estimate(&its[0],n->n_int+1,c,y_min,y_max);
283  IntVar y(home, y_min, y_max);
284  its[n->n_int+1].x = y; its[n->n_int+1].a = -1;
285  Int::Linear::post(home, its, n->n_int+2, IRT_EQ, -c, icl);
286  return y;
287  }
288  }
289 
291  LinExpr::nle(void) const {
292  return n->t == NT_NONLIN ? n->sum.ne : NULL;
293  }
294 
295 }
296 
297 // STATISTICS: minimodel-any