source: stable/0.2/Couenne/src/expression/operators/exprGroup.cpp @ 159

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

created new stable branch 0.2 from trunk (rev. 157)

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