#include <CouenneExprQuad.hpp>
Inheritance diagram for Couenne::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() () |
Compute sum of linear and nonlinear terms. | |
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, 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 *) |
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 *, enum auxSign=expression::AUX_EQ) |
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 44 of file CouenneExprQuad.hpp.
typedef std::vector<std::pair <exprVar *, CouNumber> > Couenne::exprQuad::sparseQcol |
typedef std::vector<std::pair <exprVar *, sparseQcol> > Couenne::exprQuad::sparseQ |
Definition at line 50 of file CouenneExprQuad.hpp.
exprQuad::exprQuad | ( | CouNumber | c0, | |
std::vector< std::pair< exprVar *, CouNumber > > & | lcoeff, | |||
std::vector< quadElem > & | qcoeff, | |||
expression ** | al = NULL , |
|||
int | n = 0 | |||
) |
Constructor.
Definition at line 36 of file exprQuad.cpp.
References bounds_, COUENNE_EPS, Couenne::expression::Index(), matrix_, and nqterms_.
Referenced by clone().
Copy constructor.
Definition at line 135 of file exprQuad.cpp.
References clone(), eigen_, Couenne::expression::Index(), and matrix_.
sparseQ& Couenne::exprQuad::getQ | ( | ) | const [inline] |
int Couenne::exprQuad::getnQTerms | ( | ) | [inline] |
virtual expression* Couenne::exprQuad::clone | ( | Domain * | d = NULL |
) | const [inline, virtual] |
cloning method
Reimplemented from Couenne::exprGroup.
Definition at line 101 of file CouenneExprQuad.hpp.
References exprQuad().
Referenced by exprQuad().
void exprQuad::print | ( | std::ostream & | = std::cout , |
|
bool | = false | |||
) | const [virtual] |
Print expression to an iostream.
Reimplemented from Couenne::exprGroup.
Definition at line 178 of file exprQuad.cpp.
References COUENNE_EPS, Couenne::expression::Index(), m, matrix_, MAX_ARG_LINE, n, and print().
Referenced by impliedBound(), and quadCuts().
CouNumber Couenne::exprQuad::operator() | ( | ) | [inline, virtual] |
Compute sum of linear and nonlinear terms.
Reimplemented from Couenne::exprGroup.
Definition at line 293 of file CouenneExprQuad.hpp.
References Couenne::expression::Index(), matrix_, Couenne::exprGroup::operator()(), and x.
CouNumber exprQuad::gradientNorm | ( | const double * | x | ) | [virtual] |
return l-2 norm of gradient at given point
Reimplemented from Couenne::exprGroup.
Definition at line 530 of file exprQuad.cpp.
References Couenne::expression::Index(), and matrix_.
expression * exprQuad::differentiate | ( | int | index | ) | [virtual] |
Compute derivative of this expression with respect to variable whose index is passed as argument.
Reimplemented from Couenne::exprGroup.
Definition at line 227 of file exprQuad.cpp.
References Couenne::exprOp::arglist_, COUENNE_EPS, Couenne::expression::dependsOn(), Couenne::exprGroup::exprGroup(), Couenne::exprSum::exprSum(), Couenne::expression::Index(), Couenne::exprGroup::lcoeff_, matrix_, and Couenne::exprOp::nargs_.
expression * exprQuad::simplify | ( | ) | [virtual] |
Simplify expression.
Reimplemented from Couenne::exprGroup.
Definition at line 547 of file exprQuad.cpp.
References Couenne::exprOp::simplify().
virtual int Couenne::exprQuad::Linearity | ( | ) | [inline, virtual] |
Get a measure of "how linear" the expression is.
Reimplemented from Couenne::exprGroup.
Definition at line 121 of file CouenneExprQuad.hpp.
References Couenne::exprGroup::c0_, Couenne::CONSTANT, COUENNE_EPS, Couenne::exprGroup::lcoeff_, Couenne::LINEAR, Couenne::exprSum::Linearity(), matrix_, Couenne::QUADRATIC, and Couenne::ZERO.
void exprQuad::getBounds | ( | expression *& | , | |
expression *& | ||||
) | [virtual] |
Get lower and upper bound of an expression (if any).
Reimplemented from Couenne::exprGroup.
Definition at line 25 of file conv-exprQuad.cpp.
Get lower and upper bound of an expression (if any).
Reimplemented from Couenne::exprGroup.
Definition at line 37 of file conv-exprQuad.cpp.
References Couenne::expression::getBounds().
void exprQuad::generateCuts | ( | expression * | w, | |
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 Couenne::exprGroup.
Definition at line 44 of file conv-exprQuad.cpp.
References alphaConvexify(), COUENNE_EPS, quadCuts(), and w.
bool exprQuad::alphaConvexify | ( | const CouenneProblem * | p | ) | [virtual] |
Compute data for -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex underestimator).
For the underestimator, dCoeffLo_ is computed such that
x^TQx + sum_i dCoeffLo_i (x_i - lb x_i)(ub x_i - x-i) is convex and underestimating (alpha_i is negative),
Regarding the overestimator, dCoeffUp_ are computed such that
x^TQx + sum_i dCoeffUp_i (x_i - lb x_i)(ub x_i - x-i) is concave and overestimating (alpha_i is positive).
If the method hasn't been called, dIndex_ will be NULL. If Q is positive semidefinite, then dCoeffLo_ will be NULL. If Q is negative semidefinite, then dCoeffUp_ will be NULL.
Return true if a convexification is there, false otherwise.
Definition at line 43 of file alphaConvexify.cpp.
References bounds_, COUENNE_EPS, COUENNE_INFINITY, DEBUG, eigen_, Couenne::expression::Index(), info, irow, k, and matrix_.
Referenced by generateCuts().
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
Definition at line 22 of file quadCuts.cpp.
References a, Couenne::expression::AUX_GEQ, Couenne::expression::AUX_LEQ, bounds_, Couenne::exprGroup::c0_, COUENNE_EPS, DEBUG, e, eigen_, Couenne::expression::Index(), Couenne::CouenneProblem::Lb(), Couenne::exprGroup::lcoeff_, matrix_, nqterms_, Couenne::CouenneProblem::nVars(), print(), Couenne::CouenneProblem::Ub(), w, and Couenne::CouenneProblem::X().
Referenced by generateCuts().
int exprQuad::compare | ( | exprQuad & | ) | [virtual] |
Compare two exprQuad.
Definition at line 303 of file exprQuad.cpp.
References compare(), COUENNE_EPS, e, Couenne::expression::Index(), and matrix_.
virtual enum expr_type Couenne::exprQuad::code | ( | ) | [inline, virtual] |
Code for comparisons.
Reimplemented from Couenne::exprGroup.
Definition at line 231 of file CouenneExprQuad.hpp.
References Couenne::COU_EXPRQUAD.
int exprQuad::rank | ( | ) | [virtual] |
Used in rank-based branching variable choice.
Reimplemented from Couenne::exprGroup.
Definition at line 349 of file exprQuad.cpp.
References matrix_, r, and Couenne::exprGroup::rank().
bool exprQuad::isInteger | ( | ) | [virtual] |
is this expression integer?
Reimplemented from Couenne::exprGroup.
Definition at line 403 of file exprQuad.cpp.
References Couenne::exprGroup::isInteger(), and matrix_.
Referenced by impliedBound().
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 Couenne::exprGroup.
Definition at line 387 of file exprQuad.cpp.
References Couenne::exprGroup::DepList(), and matrix_.
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 Couenne::expression.
Definition at line 23 of file branchExprQuad.cpp.
References bounds_, COUENNE_EPS, COUENNE_INFINITY, eigen_, Couenne::expression::Index(), and Couenne::TWO_RAND.
Fill dependence set of the expression associated with this auxiliary variable.
Reimplemented from Couenne::exprGroup.
Definition at line 371 of file exprQuad.cpp.
References Couenne::exprGroup::fillDepSet(), g, Couenne::expression::Index(), and matrix_.
replace variable x with new (aux) w
Reimplemented from Couenne::exprGroup.
Definition at line 447 of file exprQuad.cpp.
References Couenne::expression::Index(), matrix_, replace(), w, and x.
void exprQuad::realign | ( | const CouenneProblem * | p | ) | [virtual] |
replace variable x with new (aux) w
Reimplemented from Couenne::exprGroup.
Definition at line 478 of file exprQuad.cpp.
References Couenne::AUX, Couenne::expression::Index(), matrix_, Couenne::expression::Original(), Couenne::exprOp::Type(), and Couenne::VAR.
bool exprQuad::impliedBound | ( | int | , | |
CouNumber * | , | |||
CouNumber * | , | |||
t_chg_bounds * | , | |||
enum | auxSign = expression::AUX_EQ | |||
) | [virtual] |
implied bound processing
Reimplemented from Couenne::exprSum.
Definition at line 37 of file impliedBounds-exprQuad.cpp.
References Couenne::expression::AUX_GEQ, Couenne::expression::AUX_LEQ, Couenne::exprGroup::c0_, Couenne::t_chg_bounds::CHANGED, computeQuadFiniteBound(), COUENNE_EPS, COUENNE_INFINITY, Couenne::exprSum::getBounds(), Couenne::expression::Index(), isInteger(), Couenne::exprGroup::lcoeff_, li, matrix_, print(), Couenne::t_chg_bounds::setLower(), Couenne::t_chg_bounds::setUpper(), and Couenne::updateBound().
CouNumber exprQuad::computeQBound | ( | int | sign | ) |
method to compute the bound based on sign: -1 for lower, +1 for upper
Definition at line 18 of file exprBQuad.cpp.
References Couenne::exprGroup::c0_, COUENNE_INFINITY, Couenne::expression::Index(), Couenne::exprGroup::lcoeff_, and matrix_.
void exprQuad::closestFeasible | ( | expression * | varind, | |
expression * | vardep, | |||
CouNumber & | left, | |||
CouNumber & | right | |||
) | const [virtual] |
compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm
Reimplemented from Couenne::expression.
Definition at line 519 of file exprQuad.cpp.
void exprQuad::computeQuadFiniteBound | ( | CouNumber & | qMin, | |
CouNumber & | qMax, | |||
CouNumber * | l, | |||
CouNumber * | u, | |||
int & | indInfLo, | |||
int & | indInfUp | |||
) | [protected] |
return lower and upper bound of quadratic expression
Definition at line 30 of file compQuadFinBounds.cpp.
References COUENNE_INFINITY, Couenne::expression::Index(), Couenne::exprGroup::lcoeff_, li, matrix_, and updateInf().
Referenced by impliedBound().
virtual bool Couenne::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 Couenne::expression.
Definition at line 286 of file CouenneExprQuad.hpp.
sparseQ Couenne::exprQuad::matrix_ [mutable, protected] |
Definition at line 61 of file CouenneExprQuad.hpp.
Referenced by alphaConvexify(), compare(), computeQBound(), computeQuadFiniteBound(), DepList(), differentiate(), exprQuad(), fillDepSet(), getQ(), gradientNorm(), impliedBound(), isInteger(), Linearity(), operator()(), print(), quadCuts(), rank(), realign(), and replace().
std::vector<std::pair <CouNumber, std::vector <std::pair <exprVar *, CouNumber> > > > Couenne::exprQuad::eigen_ [mutable, protected] |
eigenvalues and eigenvectors
Definition at line 73 of file CouenneExprQuad.hpp.
Referenced by alphaConvexify(), exprQuad(), quadCuts(), and selectBranch().
std::map<exprVar *, std::pair <CouNumber, CouNumber> > Couenne::exprQuad::bounds_ [protected] |
current bounds (checked before re-computing eigenvalues/vectors)
Definition at line 76 of file CouenneExprQuad.hpp.
Referenced by alphaConvexify(), exprQuad(), quadCuts(), and selectBranch().
int Couenne::exprQuad::nqterms_ [protected] |
number of non-zeroes in Q
Definition at line 79 of file CouenneExprQuad.hpp.
Referenced by exprQuad(), getnQTerms(), and quadCuts().