source: stable/0.4/Couenne/src/expression/operators/exprGroup.cpp @ 905

Last change on this file since 905 was 905, checked in by pbelotti, 8 years ago

merged change 904 from trunk

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