Couenne 0.5.8
Loading...
Searching...
No Matches
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
21namespace Couenne {
22
23class quadElem;
24class CouenneProblem;
25class Domain;
26
43
44class exprQuad: public exprGroup {
45
46public:
47
49 typedef std::vector <std::pair <exprVar *, CouNumber> > sparseQcol;
50 typedef std::vector <std::pair <exprVar *, sparseQcol> > sparseQ;
51
52protected:
53
60
62
69
71 mutable std::vector <std::pair <CouNumber,
72 std::vector <std::pair <exprVar *,
74
76 std::map <exprVar *, std::pair <CouNumber, CouNumber> > bounds_;
77
80
81public:
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
224
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
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;
277protected:
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
#define COUENNE_EPS
#define COUENNE_INFINITY
IPOPT_DEPRECATED typedef int Index
Cut Generator for linear convexifications.
OsiObject for auxiliary variables $w=f(x)$.
Class for MINLP problems with symbolic information.
Dependence graph.
Define a dynamic point+bounds, with a way to save and restore previous points+bounds through a LIFO s...
lincoeff & lcoeff() const
return linear term coefficients
CouNumber c0_
constant term
virtual CouNumber operator()()
function for the evaluation of the expression
exprGroup(CouNumber, lincoeff &, expression **=NULL, int=0)
Constructor.
lincoeff lcoeff_
coefficients and indices of the linear term
virtual void replace(exprVar *x, exprVar *w)
replace variable x with new (aux) w
virtual void getBounds(expression *&, expression *&)
Get lower and upper bound of an expression (if any)
virtual expression * clone(Domain *d=NULL) const
cloning method
virtual bool isInteger()
is this expression integer?
void computeQuadFiniteBound(CouNumber &qMin, CouNumber &qMax, CouNumber *l, CouNumber *u, int &indInfLo, int &indInfUp)
return lower and upper bound of quadratic expression
std::map< exprVar *, std::pair< CouNumber, CouNumber > > bounds_
current bounds (checked before re-computing eigenvalues/vectors)
CouNumber gradientNorm(const double *x)
return l-2 norm of gradient at given point
std::vector< std::pair< CouNumber, std::vector< std::pair< exprVar *, CouNumber > > > > eigen_
eigenvalues and eigenvectors
std::vector< std::pair< exprVar *, CouNumber > > sparseQcol
matrix
virtual bool alphaConvexify(const CouenneProblem *)
Compute data for -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex un...
virtual enum expr_type code()
Code for comparisons.
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...
void quadCuts(expression *w, OsiCuts &cs, const CouenneCutGenerator *cg)
method exprQuad::quadCuts
virtual void getBounds(CouNumber &, CouNumber &)
Get lower and upper bound of an expression (if any)
int nqterms_
number of non-zeroes in Q
virtual bool impliedBound(int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign=expression::AUX_EQ)
implied bound processing
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.
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
sparseQ & getQ() const
exprQuad(const exprQuad &src, Domain *d=NULL)
Copy constructor.
virtual int Linearity()
Get a measure of "how linear" the expression is.
virtual expression * simplify()
Simplify expression.
virtual int rank()
Used in rank-based branching variable choice.
virtual void print(std::ostream &=std::cout, bool=false) const
Print expression to an iostream.
virtual CouNumber operator()()
Function for the evaluation of the expression.
std::vector< std::pair< exprVar *, sparseQcol > > sparseQ
virtual bool isCuttable(CouenneProblem *problem, int index) const
can this expression be further linearized or are we on its concave ("bad") side
virtual expression * differentiate(int index)
Compute derivative of this expression with respect to variable whose index is passed as argument.
virtual int compare(exprQuad &)
Compare two exprQuad.
CouNumber computeQBound(int sign)
method to compute the bound based on sign: -1 for lower, +1 for upper
exprQuad(CouNumber c0, std::vector< std::pair< exprVar *, CouNumber > > &lcoeff, std::vector< quadElem > &qcoeff, expression **al=NULL, int n=0)
Constructor.
virtual void realign(const CouenneProblem *p)
replace variable x with new (aux) w
virtual void closestFeasible(expression *varind, expression *vardep, CouNumber &left, CouNumber &right) const
compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm
virtual void fillDepSet(std::set< DepNode *, compNode > *dep, DepGraph *g)
Fill dependence set of the expression associated with this auxiliary variable.
virtual int Linearity()
Get a measure of "how linear" the expression is:
variable-type operator
Expression base class.
auxSign
"sign" of the constraint defining an auxiliary.
status of lower/upper bound of a variable, to be checked/modified in bound tightening
general include file for different compilers
dig_type
type of digging when filling the dependence list
double CouNumber
main number type in Couenne
expr_type
code returned by the method expression::code()