# CouenneExprQuad.hpp

Go to the documentation of this file.

    00001 /* $Id: CouenneExprQuad.hpp 490 2011-01-14 16:07:12Z pbelotti $
    00002  *
    00003  * Name:    exprQuad.hpp
    00004  * Author:  Pietro Belotti
    00005  * Purpose: definition of quadratic expressions (= exprGroup +
    00006  *          quadratic = constant + linear + [nonlinear] + quadratic)
    00007  *
    00008  * (C) Carnegie-Mellon University, 2006-10.
    00009  * This file is licensed under the Eclipse Public License (EPL)
    00010  */
    00011
    00012 #ifndef COUENNE_EXPRQUAD_H
    00013 #define COUENNE_EXPRQUAD_H
    00014
    00015 #include <map>
    00016 #include <vector>
    00017
    00018 #include "CoinPackedVector.hpp"
    00019 #include "CouenneExprGroup.hpp"
    00020
    00021 namespace Couenne {
    00022
    00023 class quadElem;
    00024 class CouenneProblem;
    00025 class Domain;
    00026
    00044 class exprQuad: public exprGroup {
    00045
    00046 public:
    00047
    00049   typedef std::vector <std::pair <exprVar *, CouNumber> >  sparseQcol;
    00050   typedef std::vector <std::pair <exprVar *, sparseQcol> > sparseQ;
    00051
    00052 protected:
    00053
    00061   mutable sparseQ matrix_;
    00062
    00070
    00071   mutable std::vector <std::pair <CouNumber,
    00072                           std::vector <std::pair <exprVar *,
    00073                                                   CouNumber> > > > eigen_;
    00074
    00076   std::map <exprVar *, std::pair <CouNumber, CouNumber> > bounds_;
    00077
    00079   int nqterms_;
    00080
    00081 public:
    00082
    00084   exprQuad  (CouNumber c0,
    00085              std::vector <std::pair <exprVar *, CouNumber> > &lcoeff,
    00086              std::vector <quadElem> &qcoeff,
    00087              expression **al = NULL,
    00088              int n = 0);
    00089
    00091   exprQuad (const exprQuad &src, Domain *d = NULL);
    00092
    00093   // get indices and coefficients vectors of the quadratic part
    00094   sparseQ &getQ () const
    00095   {return matrix_;}
    00096
    00097   int getnQTerms  ()
    00098   {return nqterms_;}
    00099
    00101   virtual expression *clone (Domain *d = NULL) const
    00102   {return new exprQuad (*this, d);}
    00103
    00105   virtual void print (std::ostream & = std::cout, bool = false) const;
    00106
    00108   virtual CouNumber operator () ();
    00109
    00111   CouNumber gradientNorm (const double *x);
    00112
    00115   virtual expression *differentiate (int index);
    00116
    00118   virtual expression *simplify ();
    00119
    00121   virtual int Linearity () {
    00122     int
    00123       lin  = exprSum::Linearity (), // >= NONLINEAR,
    00124       lin2 = (matrix_ .size () > 0)     ? QUADRATIC :
    00125              (lcoeff_ .size () > 0)     ? LINEAR    :
    00126              (fabs (c0_) > COUENNE_EPS) ? CONSTANT  : ZERO;
    00127
    00128     return ((lin > lin2) ? lin : lin2);
    00129   }
    00130
    00132   virtual void getBounds (expression *&, expression *&);
    00133
    00135   virtual void getBounds (CouNumber &, CouNumber &);
    00136
    00140   virtual void generateCuts (expression *w, //const OsiSolverInterface &si,
    00141                              OsiCuts &cs, const CouenneCutGenerator *cg,
    00142                              t_chg_bounds * = NULL, int = -1,
    00143                              CouNumber = -COUENNE_INFINITY,
    00144                              CouNumber =  COUENNE_INFINITY);
    00145
    00148   virtual bool alphaConvexify (const CouenneProblem *);
    00149
    00225   void quadCuts (expression *w, OsiCuts & cs, const CouenneCutGenerator * cg);
    00226
    00228   virtual int compare (exprQuad &);
    00229
    00231   virtual enum expr_type code ()
    00232   {return COU_EXPRQUAD;}
    00233
    00235   virtual int rank ();
    00236
    00238   virtual bool isInteger ();
    00239
    00242   virtual int DepList (std::set <int> &deplist,
    00243                        enum dig_type type = ORIG_ONLY);
    00244
    00247   virtual CouNumber selectBranch (const CouenneObject *obj,
    00248                                   const OsiBranchingInformation *info,
    00249                                   expression * &var,
    00250                                   double * &brpts,
    00251                                   double * &brDist, // distance of current LP
    00252                                                     // point to new convexifications
    00253                                   int &way);
    00254
    00257   virtual void fillDepSet (std::set <DepNode *, compNode> *dep, DepGraph *g);
    00258
    00260   virtual void replace (exprVar *x, exprVar *w);
    00261
    00263   virtual void realign (const CouenneProblem *p);
    00264
    00266   virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign = expression::AUX_EQ);
    00267
    00270   CouNumber computeQBound (int sign);
    00271
    00273   virtual void closestFeasible (expression *varind,
    00274                                 expression *vardep,
    00275                                 CouNumber &left,
    00276                                 CouNumber &right) const;
    00277 protected:
    00278
    00280   void computeQuadFiniteBound (CouNumber &qMin, CouNumber &qMax,
    00281                                CouNumber *l, CouNumber *u,
    00282                                int &indInfLo, int &indInfUp);
    00283
    00286   virtual bool isCuttable (CouenneProblem *problem, int index) const
    00287   {return false;} // !!! TODO: specialize
    00288 };
    00289
    00290
    00292
    00293 inline CouNumber exprQuad::operator () () {
    00294
    00295   // compute non-quadratic part (linear+constant)
    00296   CouNumber ret = exprGroup::operator () ();
    00297
    00298   for (sparseQ::iterator row = matrix_.begin (); row != matrix_.end (); ++row) {
    00299
    00300     int xind = row -> first -> Index ();
    00301     CouNumber x = (*(row -> first)) ();
    00302
    00303     for (sparseQcol::iterator col = row -> second.begin (); col != row -> second.end (); ++col) {
    00304
    00305       CouNumber term = x * (*(col -> first)) () * col -> second;
    00306       ret += (col -> first -> Index () == xind) ? term : 2. * term;
    00307     }
    00308   }
    00309
    00310   return (CouNumber) ret;
    00311 }
    00312
    00313 }
    00314
    00315 #endif

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines