Couenne 0.5.8
|
class exprQuad, with constant, linear and quadratic terms More...
#include <CouenneExprQuad.hpp>
Public Types | |
typedef std::vector< std::pair< exprVar *, CouNumber > > | sparseQcol |
matrix | |
typedef std::vector< std::pair< exprVar *, sparseQcol > > | sparseQ |
![]() | |
typedef std::vector< std::pair< exprVar *, CouNumber > > | lincoeff |
![]() | |
enum | auxSign { AUX_UNDEF =-2 , AUX_LEQ =-1 , AUX_EQ , AUX_GEQ } |
"sign" of the constraint defining an auxiliary. More... | |
Protected Attributes | |
Q matrix storage | |
Sparse implementation: given expression of the form | |
sparseQ | matrix_ |
![]() | |
lincoeff | lcoeff_ |
coefficients and indices of the linear term | |
CouNumber | c0_ |
constant term | |
![]() | |
expression ** | arglist_ |
argument list is an array of pointers to other expressions | |
int | nargs_ |
number of arguments (cardinality of arglist) | |
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. | |
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 | |
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 |
int | getnQTerms () |
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, 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 | |
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 | |
Additional Inherited Members | |
![]() | |
exprGroup (CouNumber, lincoeff &, expression **=NULL, int=0) | |
Constructor. | |
exprGroup (const exprGroup &src, Domain *d=NULL) | |
Copy constructor. | |
virtual | ~exprGroup () |
Destructor – needed to clear bounds. | |
CouNumber | getc0 () |
return constant term | |
lincoeff & | lcoeff () const |
return linear term coefficients | |
virtual int | compare (exprGroup &) |
only compare with people of the same kind | |
![]() | |
exprSum (expression **=NULL, int=0) | |
Constructors, destructor. | |
exprSum (expression *, expression *) | |
Constructor with two elements. | |
virtual | ~exprSum () |
Empty destructor. | |
std::string | printOp () const |
Print operator. | |
virtual exprAux * | standardize (CouenneProblem *p, bool addAux=true) |
Reduce expression in standard form, creating additional aux variables (and constraints) | |
exprAux * | createQuadratic (CouenneProblem *) |
Checks for quadratic terms in the expression and returns an exprQuad if there are enough to create something that can be convexified. | |
![]() | |
virtual enum nodeType | Type () const |
Node type. | |
exprOp (expression **arglist, int nargs) | |
Constructor. | |
exprOp (expression *arg0, expression *arg1) | |
Constructor with two arguments (for convenience) | |
virtual | ~exprOp () |
Destructor. | |
exprOp (const exprOp &e, Domain *d=NULL) | |
Copy constructor: only allocate space for argument list, which will be copied with clonearglist() | |
expression ** | ArgList () const |
return argument list | |
virtual void | ArgList (expression **al) |
set arglist (used in deleting nodes without deleting children) | |
int | nArgs () const |
return number of arguments | |
virtual enum pos | printPos () const |
print position (PRE, INSIDE, POST) | |
expression ** | clonearglist (Domain *d=NULL) const |
clone argument list (for use with clone method) | |
int | shrink_arglist (CouNumber, CouNumber) |
compress argument list | |
virtual int | compare (exprOp &) |
compare with other generic exprOp | |
![]() | |
expression () | |
Constructor. | |
expression (const expression &e, Domain *d=NULL) | |
Copy constructor. | |
virtual | ~expression () |
Destructor. | |
virtual int | Index () const |
Return index of variable (only valid for exprVar and exprAux) | |
virtual expression * | Argument () const |
return argument (when applicable, i.e., with univariate functions) | |
virtual expression ** | ArgPtr () |
return pointer to argument (when applicable, i.e., with univariate functions) | |
virtual expression * | Image () const |
return pointer to corresponding expression (for auxiliary variables only) | |
virtual void | Image (expression *image) |
set expression associated with this auxiliary variable (for compatibility with exprAux) | |
virtual CouNumber | Value () const |
value (empty) | |
virtual const expression * | Original () const |
If this is an exprClone of a exprClone of an expr???, point to the original expr??? instead of an exprClone – improve computing efficiency. | |
virtual int | dependsOn (int *ind, int n, enum dig_type type=STOP_AT_AUX) |
dependence on variable set: return cardinality of subset of the set of indices in first argument which occur in expression. | |
int | dependsOn (int singleton, enum dig_type type=STOP_AT_AUX) |
version with one index only | |
virtual bool | isDefinedInteger () |
is this expression defined as an integer? | |
virtual enum convexity | convexity () const |
either CONVEX, CONCAVE, AFFINE, or NONCONVEX | |
virtual int | compare (expression &) |
compare expressions | |
virtual int | compare (exprCopy &) |
compare copies of expressions | |
virtual int | Multiplicity () |
multiplicity of a variable | |
virtual void | linkDomain (Domain *d) |
empty function to update domain pointer | |
virtual bool | isBijective () const |
indicating if function is monotonically increasing | |
virtual CouNumber | inverse (expression *vardep) const |
compute the inverse function | |
virtual bool | isaCopy () const |
return true if this is a copy of something (i.e. an exprCopy) | |
virtual expression * | Copy () const |
return copy of this expression (only makes sense in exprCopy) | |
![]() | |
static expression * | genExprGroup (CouNumber, lincoeff &, expression **=NULL, int=0) |
Generalized (static) constructor: check parameters and return a constant, a single variable, or a real exprGroup. | |
![]() | |
int | impliedBoundSum (CouNumber wl, CouNumber wu, std::vector< CouNumber > &xl, std::vector< CouNumber > &xu, std::vector< std::pair< int, CouNumber > > &nl, std::vector< std::pair< int, CouNumber > > &nu) |
inferring bounds on factors of a product | |
class exprQuad, with constant, linear and quadratic terms
It represents an expression of the form
If
Definition at line 44 of file CouenneExprQuad.hpp.
typedef std::vector<std::pair <exprVar *, CouNumber> > Couenne::exprQuad::sparseQcol |
matrix
Definition at line 49 of file CouenneExprQuad.hpp.
typedef std::vector<std::pair <exprVar *, sparseQcol> > Couenne::exprQuad::sparseQ |
Definition at line 50 of file CouenneExprQuad.hpp.
Couenne::exprQuad::exprQuad | ( | CouNumber | c0, |
std::vector< std::pair< exprVar *, CouNumber > > & | lcoeff, | ||
std::vector< quadElem > & | qcoeff, | ||
expression ** | al = NULL , |
||
int | n = 0 |
||
) |
Constructor.
|
inline |
Definition at line 94 of file CouenneExprQuad.hpp.
|
inline |
Definition at line 97 of file CouenneExprQuad.hpp.
|
inlinevirtual |
cloning method
Reimplemented from Couenne::exprGroup.
Definition at line 101 of file CouenneExprQuad.hpp.
|
virtual |
Print expression to an iostream.
Reimplemented from Couenne::exprGroup.
|
inlinevirtual |
Function for the evaluation of the expression.
Compute sum of linear and nonlinear terms.
Reimplemented from Couenne::exprGroup.
Definition at line 293 of file CouenneExprQuad.hpp.
|
virtual |
return l-2 norm of gradient at given point
Reimplemented from Couenne::exprGroup.
|
virtual |
Compute derivative of this expression with respect to variable whose index is passed as argument.
Reimplemented from Couenne::exprGroup.
|
virtual |
Simplify expression.
Reimplemented from Couenne::exprGroup.
|
inlinevirtual |
Get a measure of "how linear" the expression is.
Reimplemented from Couenne::exprGroup.
Definition at line 121 of file CouenneExprQuad.hpp.
|
virtual |
Get lower and upper bound of an expression (if any)
Reimplemented from Couenne::exprGroup.
Get lower and upper bound of an expression (if any)
Reimplemented from Couenne::exprGroup.
|
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.
|
virtual |
Compute data for
void Couenne::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
The under-estimator of
and its over-estimator is given by
(where
Let
The convex relaxation of the initial constraint is then given by the two constraints
The cut is computed as follow. Let
and
grouping coefficients, we get:
and
|
inlinevirtual |
Code for comparisons.
Reimplemented from Couenne::exprGroup.
Definition at line 231 of file CouenneExprQuad.hpp.
|
virtual |
Used in rank-based branching variable choice.
Reimplemented from Couenne::exprGroup.
|
virtual |
is this expression integer?
Reimplemented from Couenne::exprGroup.
|
virtual |
fill in the set with all indices of variables appearing in the expression
Reimplemented from Couenne::exprGroup.
|
virtual |
Set up branching object by evaluating many branching points for each expression's arguments.
Reimplemented from Couenne::expression.
|
virtual |
Fill dependence set of the expression associated with this auxiliary variable.
Reimplemented from Couenne::exprGroup.
replace variable x with new (aux) w
Reimplemented from Couenne::exprGroup.
|
virtual |
replace variable x with new (aux) w
Reimplemented from Couenne::exprGroup.
|
virtual |
implied bound processing
Reimplemented from Couenne::exprSum.
CouNumber Couenne::exprQuad::computeQBound | ( | int | sign | ) |
method to compute the bound based on sign: -1 for lower, +1 for upper
|
virtual |
compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm
Reimplemented from Couenne::expression.
|
protected |
return lower and upper bound of quadratic expression
|
inlineprotectedvirtual |
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.
|
mutableprotected |
Definition at line 61 of file CouenneExprQuad.hpp.
|
mutableprotected |
eigenvalues and eigenvectors
Definition at line 73 of file CouenneExprQuad.hpp.
current bounds (checked before re-computing eigenvalues/vectors)
Definition at line 76 of file CouenneExprQuad.hpp.
|
protected |
number of non-zeroes in Q
Definition at line 79 of file CouenneExprQuad.hpp.