class exprQuad, with constant, linear and quadratic terms More...

#include <CouenneExprQuad.hpp>

Inheritance diagram for Couenne::exprQuad:

Public Types
typedef std::vector< std::pair < exprVar *, CouNumber > >	sparseQcol
	matrix More...

typedef std::vector< std::pair < exprVar *, sparseQcol > >	sparseQ

Public Types inherited from Couenne::exprGroup
typedef std::vector< std::pair < exprVar *, CouNumber > >	lincoeff

Public Types inherited from Couenne::expression
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 $\sum_{i \in N, j \in N} q_{ij} x_i x_j$ , qindexI_ and qindexJ_ contain respectively entries and for which $q_{ij}$ is nonzero in $q_{ij} x_i x_j$ :
sparseQ	matrix_

Protected Attributes inherited from Couenne::exprGroup
lincoeff	lcoeff_
	coefficients and indices of the linear term More...

CouNumber	c0_
	constant term More...

Protected Attributes inherited from Couenne::exprOp
expression **	arglist_
	argument list is an array of pointers to other expressions More...

int	nargs_
	number of arguments (cardinality of arglist) More...

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 More...

std::map< exprVar *, std::pair < CouNumber, CouNumber > >	bounds_
	current bounds (checked before re-computing eigenvalues/vectors) More...

int	nqterms_
	number of non-zeroes in Q More...

	exprQuad (CouNumber c0, std::vector< std::pair< exprVar , CouNumber > > &lcoeff, std::vector< quadElem > &qcoeff, expression *al=NULL, int n=0)
	Constructor. More...

	exprQuad (const exprQuad &src, Domain *d=NULL)
	Copy constructor. More...

sparseQ &	getQ () const
	eigenvalues and eigenvectors More...

int	getnQTerms ()
	eigenvalues and eigenvectors More...

virtual expression *	clone (Domain *d=NULL) const
	cloning method More...

virtual void	print (std::ostream &=std::cout, bool=false) const
	Print expression to an iostream. More...

virtual CouNumber	operator() ()
	Function for the evaluation of the expression. More...

CouNumber	gradientNorm (const double *x)
	return l-2 norm of gradient at given point More...

virtual expression *	differentiate (int index)
	Compute derivative of this expression with respect to variable whose index is passed as argument. More...

virtual expression *	simplify ()
	Simplify expression. More...

virtual int	Linearity ()
	Get a measure of "how linear" the expression is. More...

virtual void	getBounds (expression &, expression &)
	Get lower and upper bound of an expression (if any) More...

virtual void	getBounds (CouNumber &, CouNumber &)
	Get lower and upper bound of an expression (if any) More...

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. More...

virtual bool	alphaConvexify (const CouenneProblem *)
	Compute data for $\alpha$ -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex underestimator) More...

void	quadCuts (expression w, OsiCuts &cs, const CouenneCutGenerator cg)
	method exprQuad::quadCuts More...

virtual int	compare (exprQuad &)
	Compare two exprQuad. More...

virtual enum expr_type	code ()
	Code for comparisons. More...

virtual int	rank ()
	Used in rank-based branching variable choice. More...

virtual bool	isInteger ()
	is this expression integer? More...

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 More...

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. More...

virtual void	fillDepSet (std::set< DepNode , compNode > dep, DepGraph *g)
	Fill dependence set of the expression associated with this auxiliary variable. More...

virtual void	replace (exprVar x, exprVar w)
	replace variable x with new (aux) w More...

virtual void	realign (const CouenneProblem *p)
	replace variable x with new (aux) w More...

virtual bool	impliedBound (int, CouNumber , CouNumber , t_chg_bounds *, enum auxSign=expression::AUX_EQ)
	implied bound processing More...

CouNumber	computeQBound (int sign)
	method to compute the bound based on sign: -1 for lower, +1 for upper More...

virtual void	closestFeasible (expression varind, expression vardep, CouNumber &left, CouNumber &right) const
	compute $y^{lv}$ and $y^{uv}$ for Violation Transfer algorithm More...

void	computeQuadFiniteBound (CouNumber &qMin, CouNumber &qMax, CouNumber l, CouNumber u, int &indInfLo, int &indInfUp)
	return lower and upper bound of quadratic expression More...

virtual bool	isCuttable (CouenneProblem *problem, int index) const
	can this expression be further linearized or are we on its concave ("bad") side More...

Additional Inherited Members
Public Member Functions inherited from Couenne::exprGroup
	exprGroup (CouNumber, lincoeff &, expression **=NULL, int=0)
	Constructor. More...

	exprGroup (const exprGroup &src, Domain *d=NULL)
	Copy constructor. More...

virtual	~exprGroup ()
	Destructor – needed to clear bounds. More...

CouNumber	getc0 ()
	return constant term More...

lincoeff &	lcoeff () const
	return linear term coefficients More...

virtual int	compare (exprGroup &)
	only compare with people of the same kind More...

Public Member Functions inherited from Couenne::exprSum
	exprSum (expression **=NULL, int=0)
	Constructors, destructor. More...

	exprSum (expression , expression )
	Constructor with two elements. More...

virtual	~exprSum ()
	Empty destructor. More...

std::string	printOp () const
	Print operator. More...

virtual exprAux *	standardize (CouenneProblem *p, bool addAux=true)
	Reduce expression in standard form, creating additional aux variables (and constraints) More...

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. More...

Public Member Functions inherited from Couenne::exprOp
virtual enum nodeType	Type () const
	Node type. More...

	exprOp (expression **arglist, int nargs)
	Constructor. More...

	exprOp (expression arg0, expression arg1)
	Constructor with two arguments (for convenience) More...

virtual	~exprOp ()
	Destructor. More...

	exprOp (const exprOp &e, Domain *d=NULL)
	Copy constructor: only allocate space for argument list, which will be copied with clonearglist() More...

expression **	ArgList () const
	return argument list More...

virtual void	ArgList (expression **al)
	set arglist (used in deleting nodes without deleting children) More...

int	nArgs () const
	return number of arguments More...

virtual enum pos	printPos () const
	print position (PRE, INSIDE, POST) More...

expression **	clonearglist (Domain *d=NULL) const
	clone argument list (for use with clone method) More...

int	shrink_arglist (CouNumber, CouNumber)
	compress argument list More...

virtual int	compare (exprOp &)
	compare with other generic exprOp More...

Public Member Functions inherited from Couenne::expression
	expression ()
	Constructor. More...

	expression (const expression &e, Domain *d=NULL)
	Copy constructor. More...

virtual	~expression ()
	Destructor. More...

virtual int	Index () const
	Return index of variable (only valid for exprVar and exprAux) More...

virtual expression *	Argument () const
	return argument (when applicable, i.e., with univariate functions) More...

virtual expression **	ArgPtr ()
	return pointer to argument (when applicable, i.e., with univariate functions) More...

virtual expression *	Image () const
	return pointer to corresponding expression (for auxiliary variables only) More...

virtual void	Image (expression *image)
	set expression associated with this auxiliary variable (for compatibility with exprAux) More...

virtual CouNumber	Value () const
	value (empty) More...

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. More...

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. More...

int	dependsOn (int singleton, enum dig_type type=STOP_AT_AUX)
	version with one index only More...

virtual bool	isDefinedInteger ()
	is this expression defined as an integer? More...

virtual enum convexity	convexity () const
	either CONVEX, CONCAVE, AFFINE, or NONCONVEX More...

virtual int	compare (expression &)
	compare expressions More...

virtual int	compare (exprCopy &)
	compare copies of expressions More...

virtual int	Multiplicity ()
	multiplicity of a variable More...

virtual void	linkDomain (Domain *d)
	empty function to update domain pointer More...

virtual bool	isBijective () const
	indicating if function is monotonically increasing More...

virtual CouNumber	inverse (expression *vardep) const
	compute the inverse function More...

virtual bool	isaCopy () const
	return true if this is a copy of something (i.e. an exprCopy) More...

virtual expression *	Copy () const
	return copy of this expression (only makes sense in exprCopy) More...

Static Public Member Functions inherited from Couenne::exprGroup
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. More...

Protected Member Functions inherited from Couenne::exprSum
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 More...

Detailed Description

class exprQuad, with constant, linear and quadratic terms

It represents an expression of the form $a_0 + \sum_{i\in I} b_i x_i + x^T Q x + \sum_{i \in J} h_i (x)$ , with $a_0 + \sum_{i\in I} b_i x_i$ an affine term, $x^T Q x$ a quadratic term, and a nonlinear sum $\sum_{i \in J} h_i (x)$ . Standardization checks possible quadratic or linear terms in the latter and includes them in the former parts.

If $h_i(x)$ is a product of two nonlinear, nonquadratic functions $h'(x)h''(x)$ , two auxiliary variables $w'=f'(x)$ and $w''=h''(x)$ are created and the product $w'w''$ is included in the quadratic part of the exprQuad. If $h(x)$ nonquadratic, nonlinear function, an auxiliary variable $w=h(x)$ is created and included in the linear part.

Definition at line 44 of file CouenneExprQuad.hpp.

Member Typedef Documentation

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.

Constructor & Destructor Documentation

Couenne::exprQuad::exprQuad	(	CouNumber	c0,
		std::vector< std::pair< exprVar *, CouNumber > > &	lcoeff,
		std::vector< quadElem > &	qcoeff,
		expression **	al = `NULL`,
		int	n = `0`
	)

Constructor.

Referenced by clone().

Couenne::exprQuad::exprQuad	(	const exprQuad &	src,
		Domain *	d = `NULL`
	)

Copy constructor.

Member Function Documentation

sparseQ& Couenne::exprQuad::getQ ( ) const

inline

eigenvalues and eigenvectors

Definition at line 94 of file CouenneExprQuad.hpp.

References matrix_.

int Couenne::exprQuad::getnQTerms ( )

inline

eigenvalues and eigenvectors

Definition at line 97 of file CouenneExprQuad.hpp.

References nqterms_.

virtual expression* Couenne::exprQuad::clone ( Domain * d = NULL ) const

inlinevirtual

cloning method

Reimplemented from Couenne::exprGroup.

Definition at line 101 of file CouenneExprQuad.hpp.

References exprQuad().

virtual void Couenne::exprQuad::print	(	std::ostream &	= `std::cout`,
		bool	= `false`
	)		const

virtual

Print expression to an iostream.

Reimplemented from Couenne::exprGroup.

CouNumber Couenne::exprQuad::operator() ( )

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.

References Couenne::expression::Index(), matrix_, and Couenne::exprGroup::operator()().

CouNumber Couenne::exprQuad::gradientNorm ( const double * x )

virtual

return l-2 norm of gradient at given point

Reimplemented from Couenne::exprGroup.

virtual expression* Couenne::exprQuad::differentiate ( int index )

virtual

Compute derivative of this expression with respect to variable whose index is passed as argument.

Reimplemented from Couenne::exprGroup.

virtual expression* Couenne::exprQuad::simplify ( )

virtual

Simplify expression.

Reimplemented from Couenne::exprGroup.

virtual int Couenne::exprQuad::Linearity ( )

inlinevirtual

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.

virtual void Couenne::exprQuad::getBounds	(	expression *&	,
		expression *&
	)

virtual

Get lower and upper bound of an expression (if any)

Reimplemented from Couenne::exprGroup.

virtual void Couenne::exprQuad::getBounds	(	CouNumber &	,
		CouNumber &
	)

virtual

Get lower and upper bound of an expression (if any)

Reimplemented from Couenne::exprGroup.

virtual void Couenne::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.

virtual bool Couenne::exprQuad::alphaConvexify ( const CouenneProblem * )

virtual

Compute data for $\alpha$ -convexification of a quadratic form (fills in dCoeff_ and dIndex_ for the convex underestimator)

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 :

$\eta = a_0 + a^T x + x^T Q x$

where $\eta$ is the auxiliary corresponding to this expression and $ w_j $ are the auxiliaries corresponding to the other non-linear terms contained in the expression.

The under-estimator of $ x^T Q x$ is given by

$x^T Q x + \sum \lambda_{\min,i} (x_i - l_i ) (u_i - x_i )$

and its over-estimator is given by

$x^T Q x + \sum \lambda_{\max, i} (x_i - l_i ) (u_i - x_i )$

(where $\lambda_{\min, i} = \frac{\lambda_{\min}}{w_i^2}$ , $\lambda_{\max, i} = \frac{\lambda_{\max}}{w_i^2}$ , and $w_i = u_i - l_i$ ), where $\lambda_{\max}$ ( $\lambda_{\max}$ ) is the minimum (maximum) eigenvalue of the matrix $A={\rm Diag}({\bf u} - {\bf l}) Q {\rm Diag}({\bf u} - {\bf l})$ , obtained by pre- and post-multiplying $ Q $ by the diagonal matrix whose $i$ -th element is $u_i - l_i$ .

Let $\tilde a_0(\lambda)$ , $\tilde a(\lambda)$ and $\tilde Q (\lambda)$ be

$\tilde a_0(\lambda) = a_0 - \sum_{i = 1}^n \lambda_i l_i u_i$

$\tilde a(\lambda) = a + \left[ \begin{array}{c} \lambda_1 (u_1 + l_1) \\ \vdots \\ \lambda_n (u_n + l_n) \end{array} \right],$

$\tilde Q(\lambda) = Q - \left( \begin{array}{ccc} {\lambda_1} & & 0 \\ & \ddots & \\ 0 & & \lambda_n \end{array} \right).$

The convex relaxation of the initial constraint is then given by the two constraints

$\eta \geq \tilde a_0(\lambda_{\min}) + \tilde a(\lambda_{\min})^T x + x^T \tilde Q(\lambda_{\min}) x$

$\eta \leq \tilde a_0(\lambda_{\max}) + \tilde a(\lambda_{\max})^T x + x^T \tilde Q(\lambda_{\max}) x$

The cut is computed as follow. Let $(x^*, \eta^*)$ be the solution at hand. The two outer-approximation cuts are:

$\eta \geq \tilde a_0(\lambda_{\min}) + \tilde a(\lambda_{\min})^T x + {x^*}^T \tilde Q(\lambda_{\min}) (2x - x^*)$

and

$\eta \leq \tilde a_0(\lambda_{\max}) + \tilde a(\lambda_{\max})^T x + {x^*}^T \tilde Q(\lambda_{\max}) (2x - x^*);$

grouping coefficients, we get:

${x^*}^T \tilde Q(\lambda_{\min}) x^* - \tilde a_0(\lambda_{\min}) \geq (\tilde a(\lambda_{\min}) + 2 \tilde Q(\lambda_{\min} ) x^*)^T x - \eta$

and

${x^*}^T \tilde Q(\lambda_{\max}) x^* - \tilde a_0(\lambda_{\max}) \leq (\tilde a(\lambda_{\max}) + 2 \tilde Q (\lambda_{\max}) x^* )^T x - \eta$

virtual int Couenne::exprQuad::compare ( exprQuad & )

virtual

Compare two exprQuad.

virtual enum expr_type Couenne::exprQuad::code ( )

inlinevirtual

Code for comparisons.

Reimplemented from Couenne::exprGroup.

Definition at line 231 of file CouenneExprQuad.hpp.

References Couenne::COU_EXPRQUAD.

virtual int Couenne::exprQuad::rank ( )

virtual

Used in rank-based branching variable choice.

Reimplemented from Couenne::exprGroup.

virtual bool Couenne::exprQuad::isInteger ( )

virtual

is this expression integer?

Reimplemented from Couenne::exprGroup.

virtual int Couenne::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.

virtual CouNumber Couenne::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.

virtual void Couenne::exprQuad::fillDepSet	(	std::set< DepNode , compNode >	dep,
		DepGraph *	g
	)

virtual

Fill dependence set of the expression associated with this auxiliary variable.

Reimplemented from Couenne::exprGroup.

virtual void Couenne::exprQuad::replace	(	exprVar *	x,
		exprVar *	w
	)

virtual

replace variable x with new (aux) w

Reimplemented from Couenne::exprGroup.

virtual void Couenne::exprQuad::realign ( const CouenneProblem * p )

virtual

replace variable x with new (aux) w

Reimplemented from Couenne::exprGroup.

virtual bool Couenne::exprQuad::impliedBound	(	int	,
		CouNumber *	,
		CouNumber *	,
		t_chg_bounds *	,
		enum	auxSign = `expression::AUX_EQ`
	)

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 void Couenne::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.

void Couenne::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 Couenne::exprQuad::isCuttable	(	CouenneProblem *	problem,
		int	index
	)		const

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.

Member Data Documentation

sparseQ Couenne::exprQuad::matrix_

mutableprotected

Definition at line 61 of file CouenneExprQuad.hpp.

Referenced by getQ(), Linearity(), and operator()().

std::vector<std::pair <CouNumber, std::vector <std::pair <exprVar *, CouNumber> > > > Couenne::exprQuad::eigen_

mutableprotected

eigenvalues and eigenvectors

Definition at line 73 of file CouenneExprQuad.hpp.

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.

int Couenne::exprQuad::nqterms_

protected

number of non-zeroes in Q

Definition at line 79 of file CouenneExprQuad.hpp.

Referenced by getnQTerms().

The documentation for this class was generated from the following file:

CouenneExprQuad.hpp

Public Types

Protected Attributes

Convexification data structures

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation