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

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

Generated on Thu Sep 22 03:05:58 2011 by  doxygen 1.4.7