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

Go to the documentation of this file.
00001 /* $Id: conv-exprGroup.cpp 141 2009-06-03 04:19:19Z pbelotti $ */
00002 /*
00003  * Name:    conv-exprGroup.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: implementation of convexification methods for exprGroup
00006  *
00007  * (C) Carnegie-Mellon University, 2006. 
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "OsiRowCut.hpp"
00012 #include "OsiCuts.hpp"
00013 
00014 #include "exprGroup.hpp"
00015 #include "exprBound.hpp"
00016 #include "exprMul.hpp"
00017 
00018 #include "CouenneProblem.hpp"
00019 #include "CouenneCutGenerator.hpp"
00020 
00022 void exprGroup::getBounds (expression *&lb, expression *&ub) {
00023 
00024   expression 
00025     **lbnl = new expression * [1], 
00026     **ubnl = new expression * [1];
00027 
00028   // TODO: do not aggregate members of exprSum
00029 
00030   // compute lower/upper bound of nonlinear part
00031   exprSum::getBounds (*lbnl, *ubnl);
00032 
00033   lincoeff 
00034     *coeL = new lincoeff,
00035     *coeU = new lincoeff;
00036 
00037   // derive linear part (obtain constant)
00038   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
00039 
00040     std::pair <exprVar *, CouNumber> pairL, pairU;
00041 
00042     CouNumber coeff = el -> second;
00043     int         ind = el -> first -> Index ();
00044 
00045     pairL .second = pairU .second = coeff;
00046 
00047     if (coeff < 0.) {
00048       pairL.first = new exprUpperBound (ind, el -> first -> domain ());
00049       pairU.first = new exprLowerBound (ind, el -> first -> domain ());
00050     } else {
00051       pairL.first = new exprLowerBound (ind, el -> first -> domain ());
00052       pairU.first = new exprUpperBound (ind, el -> first -> domain ());
00053     }
00054 
00055     coeL -> push_back (pairL);
00056     coeU -> push_back (pairU);
00057   }
00058 
00059   lb = new exprGroup (c0_, *coeL, lbnl, 1);
00060   ub = new exprGroup (c0_, *coeU, ubnl, 1);
00061 
00062   delete coeL;
00063   delete coeU;
00064 }
00065 
00066 
00067 // /// Get expressions of lower and upper bound of an expression (if any)
00068 // void exprGroup::getBounds (expression *&lb, expression *&ub) {
00069 
00070 //   expression *lbnl, *ubnl;
00071 
00072 //   // TODO: do not aggregate members of exprSum
00073 
00074 //   // compute lower/upper bound of nonlinear part
00075 //   exprSum::getBounds (lbnl, ubnl);
00076 
00077 //   // count linear and constant terms
00078 //   int nlin = lcoeff_.size();
00079 //   if (fabs (c0_) > COUENNE_EPS) nlin++;
00080 //   //  for (register int *ind = index_; *ind++>=0; nlin++);
00081 
00082 //   expression 
00083 //     **linall = new expression * [nlin + 1], // linear arglist for lower bound
00084 //     **linalu = new expression * [nlin + 1]; //                    upper
00085 
00086 //   // add constant to bounds
00087 //   if (fabs (c0_) > COUENNE_EPS) {
00088 //     *linall++ = new exprConst (c0_);
00089 //     *linalu++ = new exprConst (c0_);
00090 //   }
00091 
00092 //   // TODO: make it another exprGroup!
00093 
00094 //   // derive linear part (obtain constant)
00095 //   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
00096 
00097 //     //    c0 += el -> second;
00098 
00099 //     CouNumber coeff = el -> second;
00100 //     int         ind = el -> first -> Index ();
00101 
00102 //     expression *l = new exprLowerBound (ind, el -> first -> domain ()),
00103 //                *u = new exprUpperBound (ind, el -> first -> domain ());
00104 
00105 //     if (fabs (coeff - 1.) < COUENNE_EPS) {
00106 //       *linall++ = l;
00107 //       *linalu++ = u;
00108 //     } else {
00109 
00110 //       expression *c1 = new exprConst (coeff),
00111 //                  *c2 = new exprConst (coeff);
00112 
00113 //       if (coeff < 0) {
00114 //      *linall++ = new exprMul (c1, u);
00115 //      *linalu++ = new exprMul (c2, l);
00116 //       } else {
00117 //      *linall++ = new exprMul (c1, l);
00118 //      *linalu++ = new exprMul (c2, u);
00119 //       }
00120 //     }
00121 //   }
00122 
00123 //   *linall = lbnl;
00124 //   *linalu = ubnl;
00125 
00126 //   lb = new exprSum (linall - nlin, nlin + 1);
00127 //   ub = new exprSum (linalu - nlin, nlin + 1);
00128 // }
00129 
00130 
00131 
00133 void exprGroup::getBounds (CouNumber &lb, CouNumber &ub) {
00134 
00135   // compute lower/upper bound of nonlinear part
00136 
00137   exprSum::getBounds (lb, ub);
00138   /*{
00139     expression *le, *ue;
00140     getBounds (le, ue);
00141 
00142     lb = (*le) ();
00143     ub = (*ue) ();
00144 
00145     delete le;
00146     delete ue;
00147     }*/
00148 
00149   lb += c0_;
00150   ub += c0_;
00151 
00152   // derive linear part (obtain constant)
00153   for (lincoeff::iterator el = lcoeff_.begin (); el != lcoeff_.end (); ++el) {
00154 
00155     exprVar    *var = el -> first;
00156     CouNumber coeff = el -> second, vlb, vub;
00157 
00158     bool 
00159       inf_lb = false,
00160       inf_ub = false;
00161 
00162     if ((vlb = var -> lb ()) < -COUENNE_INFINITY) {
00163       if (coeff > 0) inf_lb = true;
00164       else           inf_ub = true;
00165     } else {
00166       if (coeff > 0) lb += vlb * coeff;
00167       else           ub += vlb * coeff;
00168     }
00169 
00170     if ((vub = var -> ub ()) >  COUENNE_INFINITY) {
00171       if (coeff > 0) inf_ub = true;
00172       else           inf_lb = true;
00173     } else {
00174       if (coeff > 0) ub += vub * coeff;
00175       else           lb += vub * coeff;
00176     }
00177 
00178     if (inf_lb)
00179       lb = -COUENNE_INFINITY;
00180 
00181     if (inf_ub) {
00182       ub =  COUENNE_INFINITY;
00183       if (inf_lb)
00184         break;
00185     }
00186 
00187     //if (inf_lb && inf_ub) break; // no need to keep computing...
00188   }
00189 }
00190 
00191 
00192 // generate equality between *this and *w
00193 void exprGroup::generateCuts (expression *w, const OsiSolverInterface &si, 
00194                               OsiCuts &cs, const CouenneCutGenerator *cg,
00195                               t_chg_bounds *chg, 
00196                               int wind, CouNumber lb, CouNumber ub) {
00197 
00198   // very similar to exprSum::generateCuts. First of all, this has
00199   // been standardized into a sum, so it only gets a cut in the
00200   // initial relaxation
00201   if (!(cg -> isFirst ()))
00202     return;
00203 
00204   // there is one linear term so far: -w
00205   int nterms = lcoeff_.size ();
00206 
00207   OsiRowCut *cut = new OsiRowCut;
00208 
00209   int displacement = (wind < 0) ? 1: 0;
00210 
00211   CouNumber *coeff = new CouNumber [nargs_ + nterms + displacement];
00212   int       *index = new int       [nargs_ + nterms + displacement];
00213 
00214   if (wind < 0) {
00215     // first, make room for aux variable
00216     coeff [0] = -1.; 
00217     index [0] = w -> Index ();
00218     lb = ub = 0;
00219   }
00220 
00221   lb -= c0_;
00222   ub -= c0_;
00223 
00224   // now add linear terms
00225   lincoeff::iterator el = lcoeff_.begin ();
00226 
00227   for (int i=0; el != lcoeff_.end (); ++el) 
00228 
00229     if (fabs (el -> second) > 1.0e-21) { 
00230       // why 1.0e-21? Look at CoinPackedMatrix.cpp:2188
00231 
00232       coeff [i   + displacement] = el -> second; 
00233       index [i++ + displacement] = el -> first -> Index ();
00234     }
00235 
00236   // scan arglist for (aux) variables and constants
00237   for (int i=0; i<nargs_; i++) {
00238 
00239     expression *curr = arglist_ [i];
00240 
00241     if (curr -> Type () == CONST) {// constant term in sum
00242       lb -= curr -> Value ();
00243       ub -= curr -> Value ();
00244     }
00245     else {                        // variable
00246       coeff [++nterms] = 1.; 
00247       index   [nterms] = curr -> Index ();
00248     }
00249   }
00250 
00251   cut -> setRow (nterms + displacement, index, coeff);
00252 
00253   delete [] index;
00254   delete [] coeff;
00255 
00256   if (lb > -COUENNE_INFINITY) cut -> setLb (lb);
00257   if (ub <  COUENNE_INFINITY) cut -> setUb (ub);
00258 
00259   cut -> setGloballyValid (); // added only once, it is global
00260   cs.insert (cut);
00261   delete cut;
00262 }

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