#include <exprQuad.hpp>
Inheritance diagram for exprQuad:
Convexification data structures | |
These are filled by alphaConvexify, which implements the alpha-convexification method described in the LaGO paper by Nowak and Vigerske -- see also Adjiman and Floudas. | |
exprQuad (CouNumber c0, std::vector< std::pair< exprVar *, CouNumber > > &lcoeff, std::vector< quadElem > &qcoeff, expression **al=NULL, int n=0) | |
Constructor. | |
exprQuad (const exprQuad &src, Domain *d=NULL) | |
Copy constructor. | |
sparseQ & | getQ () const |
Constructor. | |
int | getnQTerms () |
Constructor. | |
virtual expression * | clone (Domain *d=NULL) const |
cloning method | |
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. | |
CouNumber | gradientNorm (const double *x) |
return l-2 norm of gradient at given point | |
virtual expression * | differentiate (int index) |
Compute derivative of this expression with respect to variable whose index is passed as argument. | |
virtual expression * | simplify () |
Simplify expression. | |
virtual int | Linearity () |
Get a measure of "how linear" the expression is. | |
virtual void | getBounds (expression *&, expression *&) |
Get lower and upper bound of an expression (if any). | |
virtual void | getBounds (CouNumber &, CouNumber &) |
Get lower and upper bound of an expression (if any). | |
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) |
Generate cuts for the quadratic expression, which are supporting hyperplanes of the concave upper envelope and the convex lower envelope. | |
virtual bool | alphaConvexify (const CouenneProblem *, const OsiSolverInterface &) |
Compute data for ![]() | |
void | quadCuts (expression *w, OsiCuts &cs, const CouenneCutGenerator *cg) |
method exprQuad::quadCuts Based on the information (dIndex_, dCoeffLo_, dCoeffUp_) created/modified by alphaConvexify(), create convexification cuts for this expression. | |
virtual int | compare (exprQuad &) |
Compare two exprQuad. | |
virtual enum expr_type | code () |
Code for comparisons. | |
virtual int | rank () |
Used in rank-based branching variable choice. | |
virtual bool | isInteger () |
is this expression integer? | |
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 | |
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 void | fillDepSet (std::set< DepNode *, compNode > *dep, DepGraph *g) |
Fill dependence set of the expression associated with this auxiliary variable. | |
virtual void | replace (exprVar *x, exprVar *w) |
replace variable x with new (aux) w | |
virtual void | realign (const CouenneProblem *p) |
replace variable x with new (aux) w | |
virtual bool | impliedBound (int, CouNumber *, CouNumber *, t_chg_bounds *) |
implied bound processing | |
CouNumber | computeQBound (int sign) |
method to compute the bound based on sign: -1 for lower, +1 for upper | |
virtual void | closestFeasible (expression *varind, expression *vardep, CouNumber &left, CouNumber &right) const |
compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm | |
void | computeQuadFiniteBound (CouNumber &qMin, CouNumber &qMax, CouNumber *l, CouNumber *u, int &indInfLo, int &indInfUp) |
return lower and upper bound of quadratic expression | |
virtual bool | isCuttable (CouenneProblem *problem, int index) const |
can this expression be further linearized or are we on its concave ("bad") side | |
std::vector< std::pair< CouNumber, std::vector< std::pair< exprVar *, CouNumber > > > > | eigen_ |
eigenvalues and eigenvectors | |
std::map< exprVar *, std::pair< CouNumber, CouNumber > > | bounds_ |
current bounds (checked before re-computing eigenvalues/vectors) | |
int | nqterms_ |
number of non-zeroes in Q | |
Public Types | |
typedef std::vector< std::pair< exprVar *, CouNumber > > | sparseQcol |
matrix | |
typedef std::vector< std::pair< exprVar *, sparseQcol > > | sparseQ |
Protected Attributes | |
Q matrix storage | |
Sparse implementation: given expression of the form ![]() ![]() ![]() ![]() ![]() | |
sparseQ | matrix_ |
It represents an expression of the form , with
an affine term,
a quadratic term, and a nonlinear sum
. Standardization checks possible quadratic or linear terms in the latter and includes them in the former parts.
If is a product of two nonlinear, nonquadratic functions
, two auxiliary variables
and
are created and the product
is included in the quadratic part of the exprQuad. If
nonquadratic, nonlinear function, an auxiliary variable
is created and included in the linear part.
Definition at line 42 of file exprQuad.hpp.
typedef std::vector<std::pair <exprVar *, CouNumber> > exprQuad::sparseQcol |
typedef std::vector<std::pair <exprVar *, sparseQcol> > exprQuad::sparseQ |
Definition at line 48 of file exprQuad.hpp.
exprQuad::exprQuad | ( | CouNumber | c0, | |
std::vector< std::pair< exprVar *, CouNumber > > & | lcoeff, | |||
std::vector< quadElem > & | qcoeff, | |||
expression ** | al = NULL , |
|||
int | n = 0 | |||
) |
sparseQ& exprQuad::getQ | ( | ) | const [inline] |
int exprQuad::getnQTerms | ( | ) | [inline] |
virtual expression* exprQuad::clone | ( | Domain * | d = NULL |
) | const [inline, virtual] |
cloning method
Reimplemented from exprGroup.
Definition at line 99 of file exprQuad.hpp.
References exprQuad().
virtual void exprQuad::print | ( | std::ostream & | = std::cout , |
|
bool | = false | |||
) | const [virtual] |
CouNumber exprQuad::operator() | ( | ) | [inline, virtual] |
Function for the evaluation of the expression.
Reimplemented from exprGroup.
Definition at line 291 of file exprQuad.hpp.
References expression::Index(), matrix_, and exprGroup::operator()().
CouNumber exprQuad::gradientNorm | ( | const double * | x | ) | [virtual] |
virtual expression* exprQuad::differentiate | ( | int | index | ) | [virtual] |
Compute derivative of this expression with respect to variable whose index is passed as argument.
Reimplemented from exprGroup.
virtual expression* exprQuad::simplify | ( | ) | [virtual] |
virtual int exprQuad::Linearity | ( | ) | [inline, virtual] |
Get a measure of "how linear" the expression is.
Reimplemented from exprGroup.
Definition at line 119 of file exprQuad.hpp.
References exprGroup::c0_, CONSTANT, COUENNE_EPS, exprGroup::lcoeff_, LINEAR, exprSum::Linearity(), matrix_, QUADRATIC, and ZERO.
virtual void exprQuad::getBounds | ( | expression *& | , | |
expression *& | ||||
) | [virtual] |
virtual void exprQuad::generateCuts | ( | expression * | w, | |
const OsiSolverInterface & | si, | |||
OsiCuts & | cs, | |||
const CouenneCutGenerator * | cg, | |||
t_chg_bounds * | = NULL , |
|||
int | = -1 , |
|||
CouNumber | = -COUENNE_INFINITY , |
|||
CouNumber | = COUENNE_INFINITY | |||
) | [virtual] |
Generate cuts for the quadratic expression, which are supporting hyperplanes of the concave upper envelope and the convex lower envelope.
Reimplemented from exprGroup.
virtual bool exprQuad::alphaConvexify | ( | const CouenneProblem * | , | |
const OsiSolverInterface & | ||||
) | [virtual] |
Compute data for -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex underestimator).
void exprQuad::quadCuts | ( | expression * | w, | |
OsiCuts & | cs, | |||
const CouenneCutGenerator * | cg | |||
) |
method exprQuad::quadCuts Based on the information (dIndex_, dCoeffLo_, dCoeffUp_) created/modified by alphaConvexify(), create convexification cuts for this expression.
The original constraint is :
where is the auxiliary corresponding to this expression and
are the auxiliaries corresponding to the other non-linear terms contained in the expression.
The under-estimator of is given by
and its over-estimator is given by
(where ,
, and
), where
(
) is the minimum (maximum) eigenvalue of the matrix
, obtained by pre- and post-multiplying
by the diagonal matrix whose
-th element is
.
Let ,
and
be
The convex relaxation of the initial constraint is then given by the two constraints
The cut is computed as follow. Let be the solution at hand. The two outer-approximation cuts are:
and
grouping coefficients, we get:
and
virtual enum expr_type exprQuad::code | ( | ) | [inline, virtual] |
Code for comparisons.
Reimplemented from exprGroup.
Definition at line 229 of file exprQuad.hpp.
References COU_EXPRQUAD.
virtual int exprQuad::rank | ( | ) | [virtual] |
virtual bool exprQuad::isInteger | ( | ) | [virtual] |
virtual int exprQuad::DepList | ( | std::set< int > & | deplist, | |
enum dig_type | type = ORIG_ONLY | |||
) | [virtual] |
fill in the set with all indices of variables appearing in the expression
Reimplemented from exprGroup.
virtual CouNumber exprQuad::selectBranch | ( | const CouenneObject * | obj, | |
const OsiBranchingInformation * | info, | |||
expression *& | var, | |||
double *& | brpts, | |||
double *& | brDist, | |||
int & | way | |||
) | [virtual] |
Set up branching object by evaluating many branching points for each expression's arguments.
Reimplemented from expression.
Fill dependence set of the expression associated with this auxiliary variable.
Reimplemented from exprGroup.
virtual void exprQuad::realign | ( | const CouenneProblem * | p | ) | [virtual] |
virtual bool exprQuad::impliedBound | ( | int | , | |
CouNumber * | , | |||
CouNumber * | , | |||
t_chg_bounds * | ||||
) | [virtual] |
CouNumber exprQuad::computeQBound | ( | int | sign | ) |
method to compute the bound based on sign: -1 for lower, +1 for upper
virtual void exprQuad::closestFeasible | ( | expression * | varind, | |
expression * | vardep, | |||
CouNumber & | left, | |||
CouNumber & | right | |||
) | const [virtual] |
void exprQuad::computeQuadFiniteBound | ( | CouNumber & | qMin, | |
CouNumber & | qMax, | |||
CouNumber * | l, | |||
CouNumber * | u, | |||
int & | indInfLo, | |||
int & | indInfUp | |||
) | [protected] |
return lower and upper bound of quadratic expression
virtual bool exprQuad::isCuttable | ( | CouenneProblem * | problem, | |
int | index | |||
) | const [inline, protected, virtual] |
can this expression be further linearized or are we on its concave ("bad") side
Reimplemented from expression.
Definition at line 284 of file exprQuad.hpp.
sparseQ exprQuad::matrix_ [mutable, protected] |
std::vector<std::pair <CouNumber, std::vector <std::pair <exprVar *, CouNumber> > > > exprQuad::eigen_ [mutable, protected] |
std::map<exprVar *, std::pair <CouNumber, CouNumber> > exprQuad::bounds_ [protected] |
current bounds (checked before re-computing eigenvalues/vectors)
Definition at line 74 of file exprQuad.hpp.
int exprQuad::nqterms_ [protected] |