Couenne  0.5.8
CouenneExprQuad.hpp
Go to the documentation of this file.
1 /* $Id: CouenneExprQuad.hpp 490 2011-01-14 16:07:12Z pbelotti $
2  *
3  * Name: exprQuad.hpp
4  * Author: Pietro Belotti
5  * Purpose: definition of quadratic expressions (= exprGroup +
6  * quadratic = constant + linear + [nonlinear] + quadratic)
7  *
8  * (C) Carnegie-Mellon University, 2006-10.
9  * This file is licensed under the Eclipse Public License (EPL)
10  */
11 
12 #ifndef COUENNE_EXPRQUAD_H
13 #define COUENNE_EXPRQUAD_H
14 
15 #include <map>
16 #include <vector>
17 
18 #include "CoinPackedVector.hpp"
19 #include "CouenneExprGroup.hpp"
20 
21 namespace Couenne {
22 
23 class quadElem;
24 class CouenneProblem;
25 class Domain;
26 
44 class exprQuad: public exprGroup {
45 
46 public:
47 
49  typedef std::vector <std::pair <exprVar *, CouNumber> > sparseQcol;
50  typedef std::vector <std::pair <exprVar *, sparseQcol> > sparseQ;
51 
52 protected:
53 
61  mutable sparseQ matrix_;
62 
70  mutable std::vector <std::pair <CouNumber,
72  std::vector <std::pair <exprVar *,
73  CouNumber> > > > eigen_;
74 
76  std::map <exprVar *, std::pair <CouNumber, CouNumber> > bounds_;
77 
79  int nqterms_;
80 
81 public:
82 
85  std::vector <std::pair <exprVar *, CouNumber> > &lcoeff,
86  std::vector <quadElem> &qcoeff,
87  expression **al = NULL,
88  int n = 0);
89 
91  exprQuad (const exprQuad &src, Domain *d = NULL);
92 
93  // get indices and coefficients vectors of the quadratic part
94  sparseQ &getQ () const
95  {return matrix_;}
96 
97  int getnQTerms ()
98  {return nqterms_;}
99 
101  virtual expression *clone (Domain *d = NULL) const
102  {return new exprQuad (*this, d);}
103 
105  virtual void print (std::ostream & = std::cout, bool = false) const;
106 
108  virtual CouNumber operator () ();
109 
111  CouNumber gradientNorm (const double *x);
112 
115  virtual expression *differentiate (int index);
116 
118  virtual expression *simplify ();
119 
121  virtual int Linearity () {
122  int
123  lin = exprSum::Linearity (), // >= NONLINEAR,
124  lin2 = (matrix_ .size () > 0) ? QUADRATIC :
125  (lcoeff_ .size () > 0) ? LINEAR :
126  (fabs (c0_) > COUENNE_EPS) ? CONSTANT : ZERO;
127 
128  return ((lin > lin2) ? lin : lin2);
129  }
130 
132  virtual void getBounds (expression *&, expression *&);
133 
135  virtual void getBounds (CouNumber &, CouNumber &);
136 
140  virtual void generateCuts (expression *w, //const OsiSolverInterface &si,
141  OsiCuts &cs, const CouenneCutGenerator *cg,
142  t_chg_bounds * = NULL, int = -1,
145 
148  virtual bool alphaConvexify (const CouenneProblem *);
149 
225  void quadCuts (expression *w, OsiCuts & cs, const CouenneCutGenerator * cg);
226 
228  virtual int compare (exprQuad &);
229 
231  virtual enum expr_type code ()
232  {return COU_EXPRQUAD;}
233 
235  virtual int rank ();
236 
238  virtual bool isInteger ();
239 
242  virtual int DepList (std::set <int> &deplist,
243  enum dig_type type = ORIG_ONLY);
244 
247  virtual CouNumber selectBranch (const CouenneObject *obj,
248  const OsiBranchingInformation *info,
249  expression * &var,
250  double * &brpts,
251  double * &brDist, // distance of current LP
252  // point to new convexifications
253  int &way);
254 
257  virtual void fillDepSet (std::set <DepNode *, compNode> *dep, DepGraph *g);
258 
260  virtual void replace (exprVar *x, exprVar *w);
261 
263  virtual void realign (const CouenneProblem *p);
264 
267 
271 
273  virtual void closestFeasible (expression *varind,
274  expression *vardep,
275  CouNumber &left,
276  CouNumber &right) const;
277 protected:
278 
281  CouNumber *l, CouNumber *u,
282  int &indInfLo, int &indInfUp);
283 
286  virtual bool isCuttable (CouenneProblem *problem, int index) const
287  {return false;} // !!! TODO: specialize
288 };
289 
290 
292 
294 
295  // compute non-quadratic part (linear+constant)
297 
298  for (sparseQ::iterator row = matrix_.begin (); row != matrix_.end (); ++row) {
299 
300  int xind = row -> first -> Index ();
301  CouNumber x = (*(row -> first)) ();
302 
303  for (sparseQcol::iterator col = row -> second.begin (); col != row -> second.end (); ++col) {
304 
305  CouNumber term = x * (*(col -> first)) () * col -> second;
306  ret += (col -> first -> Index () == xind) ? term : 2. * term;
307  }
308  }
309 
310  return (CouNumber) ret;
311 }
312 
313 }
314 
315 #endif
Couenne::t_chg_bounds
status of lower/upper bound of a variable, to be checked/modified in bound tightening
Definition: CouenneTypes.hpp:67
Couenne::exprQuad::quadCuts
void quadCuts(expression *w, OsiCuts &cs, const CouenneCutGenerator *cg)
method exprQuad::quadCuts
Couenne::exprQuad::generateCuts
virtual void generateCuts(expression *w, OsiCuts &cs, const CouenneCutGenerator *cg, t_chg_bounds *=NULL, int=-1, CouNumber=-COUENNE_INFINITY, CouNumber=COUENNE_INFINITY)
Generate cuts for the quadratic expression, which are supporting hyperplanes of the concave upper env...
Couenne::exprQuad::replace
virtual void replace(exprVar *x, exprVar *w)
replace variable x with new (aux) w
Couenne::QUADRATIC
@ QUADRATIC
Definition: CouenneTypes.hpp:23
Couenne::exprQuad::closestFeasible
virtual void closestFeasible(expression *varind, expression *vardep, CouNumber &left, CouNumber &right) const
compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm
Couenne::exprQuad::isCuttable
virtual bool isCuttable(CouenneProblem *problem, int index) const
can this expression be further linearized or are we on its concave ("bad") side
Definition: CouenneExprQuad.hpp:286
Couenne::exprQuad::exprQuad
exprQuad(CouNumber c0, std::vector< std::pair< exprVar *, CouNumber > > &lcoeff, std::vector< quadElem > &qcoeff, expression **al=NULL, int n=0)
Constructor.
CouenneExprGroup.hpp
Couenne::exprQuad::compare
virtual int compare(exprQuad &)
Compare two exprQuad.
Couenne::exprQuad::realign
virtual void realign(const CouenneProblem *p)
replace variable x with new (aux) w
Couenne::expr_type
expr_type
code returned by the method expression::code()
Definition: CouenneTypes.hpp:40
Couenne::exprQuad::simplify
virtual expression * simplify()
Simplify expression.
Couenne::exprQuad::selectBranch
virtual CouNumber selectBranch(const CouenneObject *obj, const OsiBranchingInformation *info, expression *&var, double *&brpts, double *&brDist, int &way)
Set up branching object by evaluating many branching points for each expression's arguments.
COUENNE_INFINITY
#define COUENNE_INFINITY
Definition: CouennePrecisions.hpp:32
Couenne::exprQuad::DepList
virtual int DepList(std::set< int > &deplist, enum dig_type type=ORIG_ONLY)
fill in the set with all indices of variables appearing in the expression
Couenne::COU_EXPRQUAD
@ COU_EXPRQUAD
Definition: CouenneTypes.hpp:45
CoinPackedVector.hpp
Couenne::exprQuad::fillDepSet
virtual void fillDepSet(std::set< DepNode *, compNode > *dep, DepGraph *g)
Fill dependence set of the expression associated with this auxiliary variable.
Couenne::exprQuad::clone
virtual expression * clone(Domain *d=NULL) const
cloning method
Definition: CouenneExprQuad.hpp:101
Couenne::expression::AUX_EQ
@ AUX_EQ
Definition: CouenneExpression.hpp:55
Couenne::CouenneCutGenerator
Cut Generator for linear convexifications.
Definition: CouenneCutGenerator.hpp:49
Couenne::exprQuad::isInteger
virtual bool isInteger()
is this expression integer?
Couenne::exprQuad::code
virtual enum expr_type code()
Code for comparisons.
Definition: CouenneExprQuad.hpp:231
Couenne::exprQuad::print
virtual void print(std::ostream &=std::cout, bool=false) const
Print expression to an iostream.
Couenne
general include file for different compilers
Definition: CouenneAggrProbing.hpp:24
Couenne::exprGroup::c0_
CouNumber c0_
constant term
Definition: CouenneExprGroup.hpp:34
Couenne::exprQuad::impliedBound
virtual bool impliedBound(int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign=expression::AUX_EQ)
implied bound processing
Couenne::exprGroup::operator()
virtual CouNumber operator()()
function for the evaluation of the expression
Definition: CouenneExprGroup.hpp:127
Couenne::dig_type
dig_type
type of digging when filling the dependence list
Definition: CouenneTypes.hpp:62
Couenne::exprQuad::eigen_
std::vector< std::pair< CouNumber, std::vector< std::pair< exprVar *, CouNumber > > > > eigen_
eigenvalues and eigenvectors
Definition: CouenneExprQuad.hpp:73
Couenne::exprQuad::Linearity
virtual int Linearity()
Get a measure of "how linear" the expression is.
Definition: CouenneExprQuad.hpp:121
Couenne::CouenneObject
OsiObject for auxiliary variables $w=f(x)$.
Definition: CouenneObject.hpp:57
COUENNE_EPS
#define COUENNE_EPS
Definition: CouennePrecisions.hpp:19
Couenne::exprQuad::sparseQcol
std::vector< std::pair< exprVar *, CouNumber > > sparseQcol
matrix
Definition: CouenneExprQuad.hpp:49
Couenne::exprGroup::lcoeff_
lincoeff lcoeff_
coefficients and indices of the linear term
Definition: CouenneExprGroup.hpp:33
Couenne::DepGraph
Dependence graph.
Definition: CouenneDepGraph.hpp:115
Couenne::exprQuad::computeQuadFiniteBound
void computeQuadFiniteBound(CouNumber &qMin, CouNumber &qMax, CouNumber *l, CouNumber *u, int &indInfLo, int &indInfUp)
return lower and upper bound of quadratic expression
Couenne::exprQuad::nqterms_
int nqterms_
number of non-zeroes in Q
Definition: CouenneExprQuad.hpp:79
Couenne::exprQuad::rank
virtual int rank()
Used in rank-based branching variable choice.
Couenne::CONSTANT
@ CONSTANT
Definition: CouenneTypes.hpp:23
Couenne::exprQuad::computeQBound
CouNumber computeQBound(int sign)
method to compute the bound based on sign: -1 for lower, +1 for upper
Couenne::CouNumber
double CouNumber
main number type in Couenne
Definition: CouenneTypes.hpp:100
OsiCuts
Couenne::exprQuad::getBounds
virtual void getBounds(CouNumber &, CouNumber &)
Get lower and upper bound of an expression (if any)
Couenne::exprGroup
class Group, with constant, linear and nonlinear terms:
Definition: CouenneExprGroup.hpp:25
Couenne::expression::auxSign
auxSign
"sign" of the constraint defining an auxiliary.
Definition: CouenneExpression.hpp:55
Couenne::exprGroup::lcoeff
lincoeff & lcoeff() const
return linear term coefficients
Definition: CouenneExprGroup.hpp:63
Couenne::exprVar
variable-type operator
Definition: CouenneExprVar.hpp:45
Couenne::exprQuad::exprQuad
exprQuad(const exprQuad &src, Domain *d=NULL)
Copy constructor.
Couenne::exprQuad::matrix_
sparseQ matrix_
Definition: CouenneExprQuad.hpp:61
Couenne::exprQuad::getQ
sparseQ & getQ() const
Definition: CouenneExprQuad.hpp:94
Couenne::exprQuad::getnQTerms
int getnQTerms()
Definition: CouenneExprQuad.hpp:97
OsiBranchingInformation
Couenne::LINEAR
@ LINEAR
Definition: CouenneTypes.hpp:23
Couenne::exprQuad::alphaConvexify
virtual bool alphaConvexify(const CouenneProblem *)
Compute data for -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex un...
Couenne::ZERO
@ ZERO
Definition: CouenneTypes.hpp:23
Couenne::ORIG_ONLY
@ ORIG_ONLY
Definition: CouenneTypes.hpp:62
Couenne::CouenneProblem
Class for MINLP problems with symbolic information.
Definition: CouenneProblem.hpp:169
Couenne::exprQuad::bounds_
std::map< exprVar *, std::pair< CouNumber, CouNumber > > bounds_
current bounds (checked before re-computing eigenvalues/vectors)
Definition: CouenneExprQuad.hpp:76
Couenne::exprSum::Linearity
virtual int Linearity()
Get a measure of "how linear" the expression is:
Couenne::exprQuad::sparseQ
std::vector< std::pair< exprVar *, sparseQcol > > sparseQ
Definition: CouenneExprQuad.hpp:50
Couenne::expression
Expression base class.
Definition: CouenneExpression.hpp:48
Couenne::exprQuad::getBounds
virtual void getBounds(expression *&, expression *&)
Get lower and upper bound of an expression (if any)
Couenne::expression::Index
virtual int Index() const
Return index of variable (only valid for exprVar and exprAux)
Definition: CouenneExpression.hpp:73
Couenne::exprQuad::gradientNorm
CouNumber gradientNorm(const double *x)
return l-2 norm of gradient at given point
Couenne::Domain
Define a dynamic point+bounds, with a way to save and restore previous points+bounds through a LIFO s...
Definition: CouenneDomain.hpp:104
Couenne::exprQuad::differentiate
virtual expression * differentiate(int index)
Compute derivative of this expression with respect to variable whose index is passed as argument.
Couenne::exprQuad::operator()
virtual CouNumber operator()()
Function for the evaluation of the expression.
Definition: CouenneExprQuad.hpp:293
Couenne::exprQuad
class exprQuad, with constant, linear and quadratic terms
Definition: CouenneExprQuad.hpp:44