/home/coin/SVN-release/OS-2.0.1/Couenne/src/expression/operators/exprGroup.cpp

Go to the documentation of this file.
00001 /* $Id: exprGroup.cpp 154 2009-06-16 18:52:53Z pbelotti $ */
00002 /*
00003  * Name:    exprGroup.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: implementation of some methods for exprGroup
00006  *
00007  * (C) Carnegie-Mellon University, 2006-09.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "exprConst.hpp"
00012 #include "exprVar.hpp"
00013 #include "exprGroup.hpp"
00014 #include "exprClone.hpp"
00015 #include "exprMul.hpp"
00016 #include "depGraph.hpp"
00017 #include "CouenneProblem.hpp"
00018 
00019 class Domain;
00020 
00021 
00022 // eliminates elements with zero coefficients
00023 void cleanZeros (std::vector <std::pair <exprVar *, CouNumber> > &lcoeff) {
00024 
00025   std::vector <std::pair <exprVar *, CouNumber> >::iterator i = lcoeff.begin ();
00026 
00027   int 
00028     ind  = 0,
00029     size = lcoeff.size ();
00030   
00031   while (size-- > 0) {
00032     if ((i -> second ==  0.) || 
00033         (i -> second == -0.)) {
00034       lcoeff.erase (i);
00035       i = lcoeff.begin () + ind;
00036     } else {
00037       ++i;
00038       ++ind;
00039     }
00040   }
00041 }
00042 
00043 
00044 
00047 expression *exprGroup::genExprGroup (CouNumber c0,
00048                                      std::vector <std::pair <exprVar *, CouNumber> > &lcoeff, 
00049                                      expression **al, 
00050                                      int n) {
00051   int nl = lcoeff.size ();
00052   expression *ret = NULL;
00053 
00054   cleanZeros (lcoeff);
00055 
00056   // a constant
00057   if ((n==0) && (nl==0))
00058     ret = new exprConst (c0); // a constant auxiliary? FIX!
00059 
00060   else if ((n==0) && (fabs (c0) < COUENNE_EPS) && (nl==1)) { // a linear monomial, cx
00061 
00062     if (fabs (lcoeff[0]. second - 1) < COUENNE_EPS)
00063       ret    = new exprClone (lcoeff[0]. first);
00064     else ret = new exprMul (new exprConst (lcoeff[0]. second), new exprClone (lcoeff[0]. first));
00065     
00066   } else ret = new exprGroup (c0, lcoeff, al, n);
00067 
00068   return ret;
00069 }
00070 
00071 
00073 exprGroup::exprGroup (CouNumber c0,
00074                       std::vector <std::pair <exprVar *, CouNumber> > &lcoeff, 
00075                       expression **al, 
00076                       int n):
00077   exprSum  (al, n),
00078   lcoeff_  (lcoeff),
00079   c0_      (c0) {
00080 
00081   cleanZeros (lcoeff_);
00082 }
00083 
00084 
00086 exprGroup::exprGroup  (const exprGroup &src, Domain *d): 
00087   exprSum   (src.clonearglist (d), src.nargs_),
00088   c0_       (src.c0_) {
00089 
00090   for (lincoeff::iterator i = src.lcoeff_.begin (); i != src.lcoeff_.end (); ++i)
00091 
00092     lcoeff_ . push_back (std::pair <exprVar *, CouNumber> 
00093                          //(dynamic_cast <exprVar *> (i -> first -> clone (d)), i -> second));
00094                          (new exprVar (i -> first -> Index (), d), i -> second));
00095 }
00096 
00097 
00099 exprGroup::~exprGroup () {
00100 
00101   for (lincoeff::iterator i = lcoeff_.begin (); i != lcoeff_.end (); ++i) {
00102     enum expr_type code = i -> first -> code ();
00103     if ((code == COU_EXPRLBOUND) || (code == COU_EXPRUBOUND))
00104       delete i -> first;
00105   }
00106 }
00107 
00108 
00110 void exprGroup::print (std::ostream &out, bool descend) const {
00111 
00112   //if (code () == COU_EXPRGROUP)
00113   if (lcoeff_.size () > 0)
00114     out << '(';
00115 
00116   if (nargs_ && ((nargs_ > 1) ||
00117                  ((*arglist_) -> Type () != CONST) ||
00118                  (fabs ((*arglist_) -> Value ()) > COUENNE_EPS)))
00119     exprSum::print (out, descend);
00120 
00121   if      (c0_ >   0.) out << '+' << c0_;
00122   else if (c0_ < - 0.) out        << c0_;
00123 
00124   for (int n = lcoeff_.size (), i=0; n--; i++) {
00125 
00126     CouNumber coeff = lcoeff_ [i]. second;
00127     out << ' ';
00128 
00129     if      (coeff >   0.) out << '+' << coeff << "*";
00130     else if (coeff < - 0.) out        << coeff << "*";
00131     //else continue;
00132 
00133     lcoeff_ [i]. first -> print (out, descend);
00134     if (!((i + 1) % MAX_ARG_LINE))
00135         out << std::endl;
00136   }
00137 
00138   //if (code () == COU_EXPRGROUP)
00139   if (lcoeff_.size () > 0)
00140     out << ')';
00141 }
00142 
00143 
00145 expression *exprGroup::differentiate (int index) {
00146 
00147   expression **arglist = new expression * [nargs_ + 1];
00148 
00149   CouNumber totlin=0;
00150 
00151   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
00152     if (el -> first -> Index () == index)
00153       totlin += el -> second;
00154 
00155   int nargs = 0;
00156 
00157   if (fabs (totlin) > COUENNE_EPS)
00158     arglist [nargs++] = new exprConst (totlin);
00159 
00160   for (int i = 0; i < nargs_; i++) 
00161     if (arglist_ [i] -> dependsOn (&index, 1))
00162       arglist [nargs++] = arglist_ [i] -> differentiate (index);
00163 
00164   if ((nargs == 0) ||
00165       (nargs == 1) && (fabs (totlin) > COUENNE_EPS)) {
00166     delete [] arglist;
00167     return new exprConst (totlin);
00168   }
00169   else return new exprSum (arglist, nargs);
00170 }
00171 
00172 
00174 int exprGroup::Linearity () {
00175 
00176   int 
00177     nllin = exprSum::Linearity (),    // linearity of nonlinear part
00178     llin  = (lcoeff_.size () == 0) ?  //              linear part
00179     ((fabs (c0_) < COUENNE_EPS) ? ZERO : CONSTANT) : 
00180     LINEAR;
00181 
00182   return (llin > nllin) ? llin : nllin;
00183 }
00184 
00185 
00187 int exprGroup::compare (exprGroup &e) {
00188 
00189   // !!! why?
00190 
00191   //int sum = exprSum::compare (e);
00192 
00193   //if (sum != 0) 
00194   //return sum;
00195 
00196   if (c0_ < e.c0_ - COUENNE_EPS) return -1;
00197   if (c0_ > e.c0_ + COUENNE_EPS) return  1;
00198 
00199   if (lcoeff_.size () < e.lcoeff_.size ()) return -1;
00200   if (lcoeff_.size () > e.lcoeff_.size ()) return  1;
00201 
00202   for (lincoeff::iterator 
00203          el1 =   lcoeff_.begin (),
00204          el2 = e.lcoeff_.begin ();
00205        el1 != lcoeff_.end (); 
00206        ++el1, ++el2) {
00207 
00208     int 
00209       ind1 = el1 -> first -> Index (),
00210       ind2 = el2 -> first -> Index ();
00211 
00212     CouNumber 
00213       coe1 = el1 -> second,
00214       coe2 = el2 -> second;
00215 
00216     if (ind1 < ind2) return -1;
00217     if (ind1 > ind2) return  1;
00218 
00219     if (coe1 < coe2 - COUENNE_EPS) return -1;
00220     if (coe1 > coe2 + COUENNE_EPS) return  1;
00221   }
00222 
00223   return 0;
00224 }
00225 
00226 
00228 
00229 int exprGroup::rank () {
00230 
00231   int maxrank = exprOp::rank ();
00232 
00233   if (maxrank < 0) 
00234     maxrank = 0;
00235 
00236   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
00237 
00238     int r = el -> first -> rank ();
00239     if (r > maxrank)
00240       maxrank = r;
00241   }
00242 
00243   return maxrank;
00244 }
00245 
00246 
00248 void exprGroup::fillDepSet (std::set <DepNode *, compNode> *dep, DepGraph *g) {
00249 
00250   exprOp::fillDepSet (dep, g);
00251 
00252   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
00253     dep -> insert (g -> lookup (el -> first -> Index ()));
00254 }
00255 
00256 
00259 int exprGroup::DepList (std::set <int> &deplist,
00260                         enum dig_type type) {
00261 
00262   int deps = exprOp::DepList (deplist, type);
00263 
00264   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
00265     deps += el -> first -> DepList (deplist, type);
00266 
00267   return deps;
00268 }
00269 
00270 
00272 bool exprGroup::isInteger () {
00273 
00274   if (!(::isInteger (c0_)) ||
00275       !(exprOp::isInteger ()))
00276     return false;
00277 
00278   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
00279 
00280     CouNumber coe = el -> second;
00281 
00282     bool
00283       intCoe = ::isInteger (coe),
00284       intVar = el -> first -> isInteger ();
00285 
00286     if (intCoe && intVar)
00287       continue;
00288 
00289     CouNumber 
00290       lb = el -> first -> lb (), 
00291       ub = el -> first -> ub ();
00292 
00293     // check var fixed and product is integer
00294     if ((fabs (lb - ub) < COUENNE_EPS) &&
00295         (::isInteger (lb * coe) ||
00296          (intCoe && ::isInteger (lb)))) 
00297       continue;
00298 
00299     return false;
00300   }
00301 
00302   return true;
00303 }
00304 
00305 
00307 void exprGroup::replace (exprVar *x, exprVar *w) {
00308 
00309   exprOp::replace (x, w);
00310 
00311   int 
00312     xind = x -> Index (),
00313     wind = w -> Index ();
00314 
00315   // find occurrences of x and w in vector of variabls
00316 
00317   lincoeff::iterator x_occur = lcoeff_.begin ();
00318 
00319   // Do not assume index vector is sorted in ascending order
00320   // w.r.t. (*iterator) -> first () -> Index()
00321   while ((x_occur != lcoeff_.end ()) && 
00322          (x_occur -> first -> Index () != xind))
00323     ++x_occur;
00324 
00325   if (x_occur == lcoeff_ .end ()) // not found, bail out
00326     return;
00327 
00328   if (xind == wind)
00329     x_occur -> first = w;
00330   else { // replacing two variables, not the features of one
00331 
00332     lincoeff::iterator w_occur = lcoeff_.begin ();
00333 
00334     // Do not assume index vector is sorted in ascending order
00335     // w.r.t. (*iterator) -> first () -> Index()
00336     while ((w_occur != lcoeff_.end ()) &&
00337            (w_occur -> first -> Index () != wind))
00338       ++w_occur;
00339 
00340     if (w_occur == lcoeff_ . end ()) // not found w, simply substitute 
00341       x_occur -> first = w;
00342     else {
00343       if ((w_occur -> second += x_occur -> second) == 0.) // add coefficients
00344         lcoeff_.erase (w_occur);                // if they cancel out, delete w as well
00345       lcoeff_.erase   (x_occur);                // delete entry of x
00346     }
00347   }
00348 }
00349 
00350 
00353 CouNumber exprGroup::gradientNorm (const double *x) {
00354 
00355   CouNumber retval = 0;
00356 
00357   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el)
00358     retval += el -> second * el -> second;
00359 
00360   return sqrt (retval);
00361 }
00362 
00363 
00365 void exprGroup::realign (const CouenneProblem *p) {
00366 
00367   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
00368 
00369     exprVar *var = el -> first;
00370 
00371     if (((var -> Type () == VAR) ||  
00372          (var -> Type () == AUX)) &&
00373         (var -> Original () != p -> Var (var -> Index ()))) {
00374 
00375       expression *trash = var;
00376       el -> first = p -> Var (var -> Index ());
00377       delete trash;
00378     }
00379   }
00380 }
00381 
00382 
00384 expression *exprGroup::simplify () {
00385   exprOp::simplify (); 
00386   //if (lcoeff_. size () <= 0) // this is just a constant
00387   //return new exprConst (c0_);
00388   //else
00389   return NULL;
00390 }
00391 

Generated on Thu Oct 8 03:02:56 2009 by  doxygen 1.4.7