CouenneExprQuad.hpp

Go to the documentation of this file.

/* $Id: CouenneExprQuad.hpp 490 2011-01-14 16:07:12Z pbelotti $
 *
 * Name:    exprQuad.hpp
 * Author:  Pietro Belotti
 * Purpose: definition of quadratic expressions (= exprGroup +
 *          quadratic = constant + linear + [nonlinear] + quadratic)
 *
 * (C) Carnegie-Mellon University, 2006-10.
 * This file is licensed under the Eclipse Public License (EPL)
 */

#ifndef COUENNE_EXPRQUAD_H
#define COUENNE_EXPRQUAD_H

#include <map>
#include <vector>

#include "CoinPackedVector.hpp"
#include "CouenneExprGroup.hpp"

namespace Couenne {

class quadElem;
class CouenneProblem;
class Domain;

class exprQuad: public exprGroup {

public:

  typedef std::vector <std::pair <exprVar *, CouNumber> >  sparseQcol;
  typedef std::vector <std::pair <exprVar *, sparseQcol> > sparseQ;

protected:

  mutable sparseQ matrix_;

  mutable std::vector <std::pair <CouNumber,
                          std::vector <std::pair <exprVar *,
                                                  CouNumber> > > > eigen_;

  std::map <exprVar *, std::pair <CouNumber, CouNumber> > bounds_;

  int nqterms_;

public:

  exprQuad  (CouNumber c0,
             std::vector <std::pair <exprVar *, CouNumber> > &lcoeff,
             std::vector <quadElem> &qcoeff,
             expression **al = NULL,
             int n = 0);

  exprQuad (const exprQuad &src, Domain *d = NULL);

  // get indices and coefficients vectors of the quadratic part
  sparseQ &getQ () const 
  {return matrix_;}

  int getnQTerms  () 
  {return nqterms_;}

  virtual expression *clone (Domain *d = NULL) const
  {return new exprQuad (*this, d);}

  virtual void print (std::ostream & = std::cout, bool = false) const;

  virtual CouNumber operator () ();

  CouNumber gradientNorm (const double *x);

  virtual expression *differentiate (int index);

  virtual expression *simplify ();

  virtual int Linearity () {
    int 
      lin  = exprSum::Linearity (), // >= NONLINEAR,
      lin2 = (matrix_ .size () > 0)     ? QUADRATIC :
             (lcoeff_ .size () > 0)     ? LINEAR    :
             (fabs (c0_) > COUENNE_EPS) ? CONSTANT  : ZERO;

    return ((lin > lin2) ? lin : lin2);
  }

  virtual void getBounds (expression *&, expression *&);

  virtual void getBounds (CouNumber &, CouNumber &);

  virtual void generateCuts (expression *w, //const OsiSolverInterface &si, 
                             OsiCuts &cs, const CouenneCutGenerator *cg, 
                             t_chg_bounds * = NULL, int = -1, 
                             CouNumber = -COUENNE_INFINITY, 
                             CouNumber =  COUENNE_INFINITY);

  virtual bool alphaConvexify (const CouenneProblem *);

  void quadCuts (expression *w, OsiCuts & cs, const CouenneCutGenerator * cg);

  virtual int compare (exprQuad &);

  virtual enum expr_type code ()
  {return COU_EXPRQUAD;}

  virtual int rank ();

  virtual bool isInteger ();

  virtual int DepList (std::set <int> &deplist, 
                       enum dig_type type = ORIG_ONLY);

  virtual CouNumber selectBranch (const CouenneObject *obj, 
                                  const OsiBranchingInformation *info,
                                  expression * &var, 
                                  double * &brpts, 
                                  double * &brDist, // distance of current LP
                                                    // point to new convexifications
                                  int &way);

  virtual void fillDepSet (std::set <DepNode *, compNode> *dep, DepGraph *g);

  virtual void replace (exprVar *x, exprVar *w);

  virtual void realign (const CouenneProblem *p);

  virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign = expression::AUX_EQ);

  CouNumber computeQBound (int sign);

  virtual void closestFeasible (expression *varind,
                                expression *vardep, 
                                CouNumber &left,
                                CouNumber &right) const;
protected:

  void computeQuadFiniteBound (CouNumber &qMin, CouNumber &qMax, 
                               CouNumber *l, CouNumber *u,
                               int &indInfLo, int &indInfUp);

  virtual bool isCuttable (CouenneProblem *problem, int index) const
  {return false;} // !!! TODO: specialize
};



inline CouNumber exprQuad::operator () () {

  // compute non-quadratic part (linear+constant)
  CouNumber ret = exprGroup::operator () ();

  for (sparseQ::iterator row = matrix_.begin (); row != matrix_.end (); ++row) {

    int xind = row -> first -> Index ();
    CouNumber x = (*(row -> first)) ();

    for (sparseQcol::iterator col = row -> second.begin (); col != row -> second.end (); ++col) {

      CouNumber term = x * (*(col -> first)) () * col -> second;
      ret += (col -> first -> Index () == xind) ? term : 2. * term;
    }
  }

  return (CouNumber) ret;
}

}

#endif