Couenne  0.2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 
84  exprQuad (CouNumber c0,
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 
266  virtual bool impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign = expression::AUX_EQ);
267 
270  CouNumber computeQBound (int sign);
271 
273  virtual void closestFeasible (expression *varind,
274  expression *vardep,
275  CouNumber &left,
276  CouNumber &right) const;
277 protected:
278 
280  void computeQuadFiniteBound (CouNumber &qMin, CouNumber &qMax,
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
Cut Generator for linear convexifications.
class Group, with constant, linear and nonlinear terms:
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...
std::vector< std::pair< exprVar *, sparseQcol > > sparseQ
void computeQuadFiniteBound(CouNumber &qMin, CouNumber &qMax, CouNumber *l, CouNumber *u, int &indInfLo, int &indInfUp)
return lower and upper bound of quadratic expression
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&#39;s arguments...
OsiObject for auxiliary variables $w=f(x)$.
CouNumber gradientNorm(const double *x)
return l-2 norm of gradient at given point
status of lower/upper bound of a variable, to be checked/modified in bound tightening ...
virtual CouNumber operator()()
function for the evaluation of the expression
virtual void print(std::ostream &=std::cout, bool=false) const
Print expression to an iostream.
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
lincoeff & lcoeff() const
return linear term coefficients
virtual bool alphaConvexify(const CouenneProblem *)
Compute data for -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex un...
CouNumber c0_
constant term
sparseQ & getQ() const
eigenvalues and eigenvectors
CouNumber computeQBound(int sign)
method to compute the bound based on sign: -1 for lower, +1 for upper
virtual void replace(exprVar *x, exprVar *w)
replace variable x with new (aux) w
virtual enum expr_type code()
Code for comparisons.
void quadCuts(expression *w, OsiCuts &cs, const CouenneCutGenerator *cg)
method exprQuad::quadCuts
int nqterms_
number of non-zeroes in Q
exprQuad(CouNumber c0, std::vector< std::pair< exprVar *, CouNumber > > &lcoeff, std::vector< quadElem > &qcoeff, expression **al=NULL, int n=0)
Constructor.
virtual void closestFeasible(expression *varind, expression *vardep, CouNumber &left, CouNumber &right) const
compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm
virtual void getBounds(expression *&, expression *&)
Get lower and upper bound of an expression (if any)
virtual int Index() const
Return index of variable (only valid for exprVar and exprAux)
auxSign
&quot;sign&quot; of the constraint defining an auxiliary.
virtual int Linearity()
Get a measure of &quot;how linear&quot; the expression is:
virtual int Linearity()
Get a measure of &quot;how linear&quot; the expression is.
lincoeff lcoeff_
coefficients and indices of the linear term
Class for MINLP problems with symbolic information.
std::vector< std::pair< CouNumber, std::vector< std::pair< exprVar *, CouNumber > > > > eigen_
eigenvalues and eigenvectors
#define COUENNE_EPS
virtual void realign(const CouenneProblem *p)
replace variable x with new (aux) w
virtual bool impliedBound(int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign=expression::AUX_EQ)
implied bound processing
std::map< exprVar *, std::pair< CouNumber, CouNumber > > bounds_
current bounds (checked before re-computing eigenvalues/vectors)
virtual CouNumber operator()()
Function for the evaluation of the expression.
double CouNumber
main number type in Couenne
class exprQuad, with constant, linear and quadratic terms
#define COUENNE_INFINITY
Dependence graph.
virtual bool isInteger()
is this expression integer?
dig_type
type of digging when filling the dependence list
virtual int rank()
Used in rank-based branching variable choice.
variable-type operator
expr_type
code returned by the method expression::code()
virtual expression * clone(Domain *d=NULL) const
cloning method
virtual int compare(exprQuad &)
Compare two exprQuad.
Expression base class.
virtual expression * differentiate(int index)
Compute derivative of this expression with respect to variable whose index is passed as argument...
virtual bool isCuttable(CouenneProblem *problem, int index) const
can this expression be further linearized or are we on its concave (&quot;bad&quot;) side
int getnQTerms()
eigenvalues and eigenvectors
virtual void fillDepSet(std::set< DepNode *, compNode > *dep, DepGraph *g)
Fill dependence set of the expression associated with this auxiliary variable.
virtual expression * simplify()
Simplify expression.
Define a dynamic point+bounds, with a way to save and restore previous points+bounds through a LIFO s...
std::vector< std::pair< exprVar *, CouNumber > > sparseQcol
matrix