source: trunk/Couenne/src/expression/operators/exprGroup.cpp @ 112

Last change on this file since 112 was 112, checked in by pbelotti, 11 years ago

isolate restoreUnused to when there is at least one unused -- takes care of reformulated stockcycle problem (thanks to C. D'Ambrosio for the bug report). Check linear terms before adding a full exprGroup -- need a constructor pilot. Quicker solution feasibility check (with initial integrality check).

File size: 8.7 KB
Line 
1/*
2 * Name:    exprGroup.cpp
3 * Author:  Pietro Belotti
4 * Purpose: implementation of some methods for exprGroup
5 *
6 * (C) Carnegie-Mellon University, 2006-08.
7 * This file is licensed under the Common Public License (CPL)
8 */
9
10#include "exprConst.hpp"
11#include "exprVar.hpp"
12#include "exprGroup.hpp"
13#include "exprClone.hpp"
14#include "exprMul.hpp"
15#include "depGraph.hpp"
16#include "CouenneProblem.hpp"
17
18class Domain;
19
20/// Generalized (static) constructor: check parameters and return a
21/// constant, a single variable, or a real exprGroup
22expression *exprGroup::genExprGroup (CouNumber c0,
23                                     std::vector <std::pair <exprVar *, CouNumber> > &lcoeff, 
24                                     expression **al, 
25                                     int n) {
26  int nl = lcoeff.size ();
27  expression *ret = NULL;
28
29  // a constant
30  if ((n==0) && (nl==0))
31    ret = new exprConst (c0); // a constant auxiliary? FIX!
32
33  else if ((n==0) && (fabs (c0) < COUENNE_EPS) && (nl==1)) { // a linear monomial, cx
34
35    if (fabs (lcoeff[0]. second - 1) < COUENNE_EPS)
36      ret    = new exprClone (lcoeff[0]. first);
37    else ret = new exprMul (new exprConst (lcoeff[0]. second), new exprClone (lcoeff[0]. first));
38   
39  } else ret = new exprGroup (c0, lcoeff, al, n);
40
41  return ret;
42}
43
44
45/// Constructor
46exprGroup::exprGroup (CouNumber c0,
47                      std::vector <std::pair <exprVar *, CouNumber> > &lcoeff, 
48                      expression **al, 
49                      int n):
50  exprSum  (al, n),
51  lcoeff_  (lcoeff),
52  c0_      (c0) {}
53
54
55/// copy constructor
56exprGroup::exprGroup  (const exprGroup &src, Domain *d): 
57  exprSum   (src.clonearglist (d), src.nargs_),
58  c0_       (src.c0_) {
59
60  for (lincoeff::iterator i = src.lcoeff_.begin (); i != src.lcoeff_.end (); ++i)
61
62    lcoeff_ . push_back (std::pair <exprVar *, CouNumber> 
63                         //(dynamic_cast <exprVar *> (i -> first -> clone (d)), i -> second));
64                         (new exprVar (i -> first -> Index (), d), i -> second));
65}
66
67
68/// Destructor -- check if there are exprBounds and delete them
69exprGroup::~exprGroup () {
70
71  for (lincoeff::iterator i = lcoeff_.begin (); i != lcoeff_.end (); ++i) {
72    enum expr_type code = i -> first -> code ();
73    if ((code == COU_EXPRLBOUND) || (code == COU_EXPRUBOUND))
74      delete i -> first;
75  }
76}
77
78
79/// I/O
80void exprGroup::print (std::ostream &out, bool descend) const {
81
82  //if (code () == COU_EXPRGROUP)
83  if (lcoeff_.size () > 0)
84    out << '(';
85
86  if (nargs_ && ((nargs_ > 1) ||
87                 ((*arglist_) -> Type () != CONST) ||
88                 (fabs ((*arglist_) -> Value ()) > COUENNE_EPS)))
89    exprSum::print (out, descend);
90
91  if      (c0_ >   0.) out << '+' << c0_;
92  else if (c0_ < - 0.) out        << c0_;
93
94  for (int n = lcoeff_.size (), i=0; n--; i++) {
95
96    CouNumber coeff = lcoeff_ [i]. second;
97    out << ' ';
98
99    if      (coeff >   0.) out << '+' << coeff << "*";
100    else if (coeff < - 0.) out        << coeff << "*";
101    //else continue;
102
103    lcoeff_ [i]. first -> print (out, descend);
104    if (!((i + 1) % MAX_ARG_LINE))
105        out << std::endl;
106  }
107
108  //if (code () == COU_EXPRGROUP)
109  if (lcoeff_.size () > 0)
110    out << ')';
111}
112
113
114/// differentiation
115expression *exprGroup::differentiate (int index) {
116
117  expression **arglist = new expression * [nargs_ + 1];
118
119  CouNumber totlin=0;
120
121  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
122    if (el -> first -> Index () == index)
123      totlin += el -> second;
124
125  int nargs = 0;
126
127  if (fabs (totlin) > COUENNE_EPS)
128    arglist [nargs++] = new exprConst (totlin);
129
130  for (int i = 0; i < nargs_; i++) 
131    if (arglist_ [i] -> dependsOn (&index, 1))
132      arglist [nargs++] = arglist_ [i] -> differentiate (index);
133
134  if ((nargs == 0) ||
135      (nargs == 1) && (fabs (totlin) > COUENNE_EPS)) {
136    delete [] arglist;
137    return new exprConst (totlin);
138  }
139  else return new exprSum (arglist, nargs);
140}
141
142
143/// get a measure of "how linear" the expression is:
144int exprGroup::Linearity () {
145
146  int 
147    nllin = exprSum::Linearity (),    // linearity of nonlinear part
148    llin  = (lcoeff_.size () == 0) ?  //              linear part
149    ((fabs (c0_) < COUENNE_EPS) ? ZERO : CONSTANT) : 
150    LINEAR;
151
152  return (llin > nllin) ? llin : nllin;
153}
154
155
156/// compare affine terms
157int exprGroup::compare (exprGroup &e) {
158
159  // !!! why?
160
161  //int sum = exprSum::compare (e);
162
163  //if (sum != 0)
164  //return sum;
165
166  if (c0_ < e.c0_ - COUENNE_EPS) return -1;
167  if (c0_ > e.c0_ + COUENNE_EPS) return  1;
168
169  if (lcoeff_.size () < e.lcoeff_.size ()) return -1;
170  if (lcoeff_.size () > e.lcoeff_.size ()) return  1;
171
172  for (lincoeff::iterator
173         el1 =   lcoeff_.begin (),
174         el2 = e.lcoeff_.begin ();
175       el1 != lcoeff_.end (); 
176       ++el1, ++el2) {
177
178    int 
179      ind1 = el1 -> first -> Index (),
180      ind2 = el2 -> first -> Index ();
181
182    CouNumber
183      coe1 = el1 -> second,
184      coe2 = el2 -> second;
185
186    if (ind1 < ind2) return -1;
187    if (ind1 > ind2) return  1;
188
189    if (coe1 < coe2 - COUENNE_EPS) return -1;
190    if (coe1 > coe2 + COUENNE_EPS) return  1;
191  }
192
193  return 0;
194}
195
196
197/// used in rank-based branching variable choice
198
199int exprGroup::rank () {
200
201  int maxrank = exprOp::rank ();
202
203  if (maxrank < 0) 
204    maxrank = 0;
205
206  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
207
208    int r = el -> first -> rank ();
209    if (r > maxrank)
210      maxrank = r;
211  }
212
213  return maxrank;
214}
215
216
217/// update dependence set with index of this variable
218void exprGroup::fillDepSet (std::set <DepNode *, compNode> *dep, DepGraph *g) {
219
220  exprOp::fillDepSet (dep, g);
221
222  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
223    dep -> insert (g -> lookup (el -> first -> Index ()));
224}
225
226
227/// fill in the set with all indices of variables appearing in the
228/// expression
229int exprGroup::DepList (std::set <int> &deplist,
230                        enum dig_type type) {
231
232  int deps = exprOp::DepList (deplist, type);
233
234  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
235    deps += el -> first -> DepList (deplist, type);
236
237  return deps;
238}
239
240
241/// is this linear term integer?
242bool exprGroup::isInteger () {
243
244  if (!(::isInteger (c0_)) ||
245      !(exprOp::isInteger ()))
246    return false;
247
248  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
249
250    CouNumber coe = el -> second;
251
252    bool
253      intCoe = ::isInteger (coe),
254      intVar = el -> first -> isInteger ();
255
256    if (intCoe && intVar)
257      continue;
258
259    CouNumber
260      lb = el -> first -> lb (), 
261      ub = el -> first -> ub ();
262
263    // check var fixed and product is integer
264    if ((fabs (lb - ub) < COUENNE_EPS) &&
265        (::isInteger (lb * coe) ||
266         (intCoe && ::isInteger (lb)))) 
267      continue;
268
269    return false;
270  }
271
272  return true;
273}
274
275
276/// replace variable x with new (aux) w
277void exprGroup::replace (exprVar *x, exprVar *w) {
278
279  exprOp::replace (x, w);
280
281  int 
282    xind = x -> Index (),
283    wind = w -> Index ();
284
285  // find occurrences of x and w in vector of variabls
286
287  lincoeff::iterator x_occur = lcoeff_.begin ();
288
289  // Do not assume index vector is sorted in ascending order
290  // w.r.t. (*iterator) -> first () -> Index()
291  while ((x_occur != lcoeff_.end ()) && 
292         (x_occur -> first -> Index () != xind))
293    ++x_occur;
294
295  if (x_occur == lcoeff_ .end ()) // not found, bail out
296    return;
297
298  if (xind == wind)
299    x_occur -> first = w;
300  else { // replacing two variables, not the features of one
301
302    lincoeff::iterator w_occur = lcoeff_.begin ();
303
304    // Do not assume index vector is sorted in ascending order
305    // w.r.t. (*iterator) -> first () -> Index()
306    while ((w_occur != lcoeff_.end ()) &&
307           (w_occur -> first -> Index () != wind))
308      ++w_occur;
309
310    if (w_occur == lcoeff_ . end ()) // not found w, simply substitute
311      x_occur -> first = w;
312    else {
313      if ((w_occur -> second += x_occur -> second) == 0.) // add coefficients
314        lcoeff_.erase (w_occur);                // if they cancel out, delete w as well
315      lcoeff_.erase   (x_occur);                // delete entry of x
316    }
317  }
318}
319
320
321/// return l-2 norm of gradient at given point. Not needed for now, as
322/// we only use it with nonlinear operators
323CouNumber exprGroup::gradientNorm (const double *x) {
324
325  CouNumber retval = 0;
326
327  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
328    retval += el -> second * el -> second;
329
330  return sqrt (retval);
331}
332
333
334/// Redirect variables to proper variable vector
335void exprGroup::realign (const CouenneProblem *p) {
336
337  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
338
339    exprVar *var = el -> first;
340
341    if (((var -> Type () == VAR) || 
342         (var -> Type () == AUX)) &&
343        (var -> Original () != p -> Var (var -> Index ()))) {
344
345      expression *trash = var;
346      el -> first = p -> Var (var -> Index ());
347      delete trash;
348    }
349  }
350}
351
352
353/// simplification
354expression *exprGroup::simplify () {
355  exprOp::simplify (); 
356  //if (lcoeff_. size () <= 0) // this is just a constant
357  //return new exprConst (c0_);
358  //else
359  return NULL;
360}
361
Note: See TracBrowser for help on using the repository browser.