source: stable/0.3/Couenne/src/expression/operators/exprGroup.cpp @ 320

Last change on this file since 320 was 320, checked in by stefan, 10 years ago

fix for MS compiler: iterator in a vector gets invalidated if some element is erased from the vector

  • Property svn:keywords set to Id
File size: 9.5 KB
Line 
1/* $Id: exprGroup.cpp 320 2010-03-26 19:12:20Z stefan $ */
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) || 
104        (code == COU_EXPRUBOUND))
105      delete i -> first;
106  }
107}
108
109
110/// I/O
111void exprGroup::print (std::ostream &out, bool descend) const {
112
113  //if (code () == COU_EXPRGROUP)
114  if (lcoeff_.size () > 0)
115    out << '(';
116
117  if (nargs_ && ((nargs_ > 1) ||
118                 ((*arglist_) -> Type () != CONST) ||
119                 (fabs ((*arglist_) -> Value ()) > COUENNE_EPS)))
120    exprSum::print (out, descend);
121
122  if      (c0_ >   0.) out << '+' << c0_;
123  else if (c0_ < - 0.) out        << c0_;
124
125  for (int n = lcoeff_.size (), i=0; n--; i++) {
126
127    CouNumber coeff = lcoeff_ [i]. second;
128    out << ' ';
129
130    if      (coeff >   0.) out << '+' << coeff << "*";
131    else if (coeff < - 0.) out        << coeff << "*";
132    //else continue;
133
134    lcoeff_ [i]. first -> print (out, descend);
135    if (!((i + 1) % MAX_ARG_LINE))
136        out << std::endl;
137  }
138
139  //if (code () == COU_EXPRGROUP)
140  if (lcoeff_.size () > 0)
141    out << ')';
142}
143
144
145/// differentiation
146expression *exprGroup::differentiate (int index) {
147
148  expression **arglist = new expression * [nargs_ + 1];
149
150  CouNumber totlin=0;
151
152  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
153    if (el -> first -> Index () == index)
154      totlin += el -> second;
155
156  int nargs = 0;
157
158  if (fabs (totlin) > COUENNE_EPS)
159    arglist [nargs++] = new exprConst (totlin);
160
161  for (int i = 0; i < nargs_; i++) 
162    if (arglist_ [i] -> dependsOn (&index, 1))
163      arglist [nargs++] = arglist_ [i] -> differentiate (index);
164
165  if ((nargs == 0) ||
166      (nargs == 1) && (fabs (totlin) > COUENNE_EPS)) {
167    delete [] arglist;
168    return new exprConst (totlin);
169  }
170  else return new exprSum (arglist, nargs);
171}
172
173
174/// get a measure of "how linear" the expression is:
175int exprGroup::Linearity () {
176
177  int 
178    nllin = exprSum::Linearity (),    // linearity of nonlinear part
179    llin  = (lcoeff_.size () == 0) ?  //              linear part
180    ((fabs (c0_) < COUENNE_EPS) ? ZERO : CONSTANT) : 
181    LINEAR;
182
183  return (llin > nllin) ? llin : nllin;
184}
185
186
187/// compare affine terms
188int exprGroup::compare (exprGroup &e) {
189
190  // !!! why?
191
192  //int sum = exprSum::compare (e);
193
194  //if (sum != 0)
195  //return sum;
196
197  if (c0_ < e.c0_ - COUENNE_EPS) return -1;
198  if (c0_ > e.c0_ + COUENNE_EPS) return  1;
199
200  if (lcoeff_.size () < e.lcoeff_.size ()) return -1;
201  if (lcoeff_.size () > e.lcoeff_.size ()) return  1;
202
203  for (lincoeff::iterator
204         el1 =   lcoeff_.begin (),
205         el2 = e.lcoeff_.begin ();
206       el1 != lcoeff_.end (); 
207       ++el1, ++el2) {
208
209    int 
210      ind1 = el1 -> first -> Index (),
211      ind2 = el2 -> first -> Index ();
212
213    CouNumber
214      coe1 = el1 -> second,
215      coe2 = el2 -> second;
216
217    if (ind1 < ind2) return -1;
218    if (ind1 > ind2) return  1;
219
220    if (coe1 < coe2 - COUENNE_EPS) return -1;
221    if (coe1 > coe2 + COUENNE_EPS) return  1;
222  }
223
224  return 0;
225}
226
227
228/// used in rank-based branching variable choice
229
230int exprGroup::rank () {
231
232  int maxrank = exprOp::rank ();
233
234  if (maxrank < 0) 
235    maxrank = 0;
236
237  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
238
239    int r = el -> first -> rank ();
240    if (r > maxrank)
241      maxrank = r;
242  }
243
244  return maxrank;
245}
246
247
248/// update dependence set with index of this variable
249void exprGroup::fillDepSet (std::set <DepNode *, compNode> *dep, DepGraph *g) {
250
251  exprOp::fillDepSet (dep, g);
252
253  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
254    dep -> insert (g -> lookup (el -> first -> Index ()));
255}
256
257
258/// fill in the set with all indices of variables appearing in the
259/// expression
260int exprGroup::DepList (std::set <int> &deplist,
261                        enum dig_type type) {
262
263  int deps = exprOp::DepList (deplist, type);
264
265  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
266    deps += el -> first -> DepList (deplist, type);
267
268  return deps;
269}
270
271
272/// is this linear term integer?
273bool exprGroup::isInteger () {
274
275  if (!(::isInteger (c0_)) ||
276      !(exprOp::isInteger ()))
277    return false;
278
279  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
280
281    CouNumber coe = el -> second;
282
283    bool
284      intCoe = ::isInteger (coe),
285      intVar = el -> first -> isInteger ();
286
287    if (intCoe && intVar)
288      continue;
289
290    CouNumber
291      lb = el -> first -> lb (), 
292      ub = el -> first -> ub ();
293
294    // check var fixed and product is integer
295    if ((fabs (lb - ub) < COUENNE_EPS) &&
296        (::isInteger (lb * coe) ||
297         (intCoe && ::isInteger (lb)))) 
298      continue;
299
300    return false;
301  }
302
303  return true;
304}
305
306
307/// replace variable x with new (aux) w
308void exprGroup::replace (exprVar *x, exprVar *w) {
309
310  exprOp::replace (x, w);
311
312  int 
313    xind = x -> Index (),
314    wind = w -> Index ();
315
316  // find occurrences of x and w in vector of variabls
317
318  lincoeff::iterator x_occur = lcoeff_.begin ();
319
320  // Do not assume index vector is sorted in ascending order
321  // w.r.t. (*iterator) -> first () -> Index()
322  while ((x_occur != lcoeff_.end ()) && 
323         (x_occur -> first -> Index () != xind))
324    ++x_occur;
325
326  if (x_occur == lcoeff_ .end ()) // not found, bail out
327    return;
328
329  if (xind == wind)
330    x_occur -> first = w;
331  else { // replacing two variables, not the features of one
332
333    lincoeff::iterator w_occur = lcoeff_.begin ();
334
335    // Do not assume index vector is sorted in ascending order
336    // w.r.t. (*iterator) -> first () -> Index()
337    while ((w_occur != lcoeff_.end ()) &&
338           (w_occur -> first -> Index () != wind))
339      ++w_occur;
340
341    if (w_occur == lcoeff_ . end ()) // not found w, simply substitute
342      x_occur -> first = w;
343    else {
344                if ((w_occur -> second += x_occur -> second) == 0.) { // add coefficients
345        lcoeff_.erase (w_occur);                // if they cancel out, delete w as well
346
347        // under Microsoft, x_occur may have been invalidated by removing w_occur from lcoeff_, so we search for it again
348        for( x_occur = lcoeff_.begin (); x_occur -> first -> Index () != xind; ++x_occur )
349                assert(x_occur != lcoeff_ .end ()); // it was found before, so it should be still found
350        }
351      lcoeff_.erase   (x_occur);                // delete entry of x
352    }
353  }
354}
355
356
357/// return l-2 norm of gradient at given point. Not needed for now, as
358/// we only use it with nonlinear operators
359CouNumber exprGroup::gradientNorm (const double *x) {
360
361  CouNumber retval = 0;
362
363  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
364    retval += el -> second * el -> second;
365
366  return sqrt (retval);
367}
368
369
370/// Redirect variables to proper variable vector
371void exprGroup::realign (const CouenneProblem *p) {
372
373  for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
374
375    exprVar *var = el -> first;
376
377    if (((var -> Type () == VAR) || 
378         (var -> Type () == AUX)) &&
379        (var -> Original () != p -> Var (var -> Index ()))) {
380
381      expression *trash = var;
382      el -> first = p -> Var (var -> Index ());
383      delete trash;
384    }
385  }
386}
387
388
389/// simplification
390expression *exprGroup::simplify () {
391  exprOp::simplify (); 
392  //if (lcoeff_. size () <= 0) // this is just a constant
393  //return new exprConst (c0_);
394  //else
395  return NULL;
396}
397
Note: See TracBrowser for help on using the repository browser.