00001
00002
00003
00004
00005
00006
00007
00008
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
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
00061 if ((n==0) && (nl==0))
00062 ret = new exprConst (c0);
00063
00064 else if ((n==0) && (fabs (c0) < COUENNE_EPS) && (nl==1)) {
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
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
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
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 (),
00183 llin = (lcoeff_.size () == 0) ?
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
00195
00196
00197
00198
00199
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
00272
00273
00274
00275
00276
00277 deps += el -> first -> DepList (deplist, type);
00278
00279
00280
00281
00282
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
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
00334
00335 lincoeff::iterator x_occur = lcoeff_.begin ();
00336
00337
00338
00339 while ((x_occur != lcoeff_.end ()) &&
00340 (x_occur -> first -> Index () != xind))
00341 ++x_occur;
00342
00343 if (x_occur == lcoeff_ .end ())
00344 return;
00345
00346 if (xind == wind)
00347 x_occur -> first = w;
00348 else {
00349
00350 lincoeff::iterator w_occur = lcoeff_.begin ();
00351
00352
00353
00354 while ((w_occur != lcoeff_.end ()) &&
00355 (w_occur -> first -> Index () != wind))
00356 ++w_occur;
00357
00358 if (w_occur == lcoeff_ . end ())
00359 x_occur -> first = w;
00360 else {
00361 if ((w_occur -> second += x_occur -> second) == 0.) {
00362 lcoeff_.erase (w_occur);
00363
00364
00365 for( x_occur = lcoeff_.begin (); x_occur -> first -> Index () != xind; ++x_occur )
00366 assert(x_occur != lcoeff_ .end ());
00367 }
00368 lcoeff_.erase (x_occur);
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
00410
00411
00412 return NULL;
00413 }
00414