Detailed Description

methods to interpret (evaluate) an expression tree "fast" using CppAD

Author: Stefan Vigerske

Definition in file exprinterpret_cppad.cpp.

#include "scip/def.h"
#include "blockmemshell/memory.h"
#include "nlpi/pub_expr.h"
#include "nlpi/exprinterpret.h"
#include <cmath>
#include <vector>
#include "nlpi/intervalarithext.h"
#include <cppad/cppad.hpp>
#include <cppad/error_handler.hpp>
#include <pthread.h>

Go to the source code of this file.

Macros
#define	SIGN(x) ((x) >= 0.0 ? 1.0 : -1.0)

#define	SCIPInterval_NAMESPACE CppAD

#define	CPPAD_MAX_NUM_THREADS 64

Functions
SCIPInterval	CondExpOp (enum CppAD::CompareOp cop, const SCIPInterval &left, const SCIPInterval &right, const SCIPInterval &trueCase, const SCIPInterval &falseCase)

bool	EqualOpSeq (const SCIPInterval &x, const SCIPInterval &y)

bool	IdenticalPar (const SCIPInterval &x)

bool	IdenticalZero (const SCIPInterval &x)

bool	IdenticalOne (const SCIPInterval &x)

bool	IdenticalEqualPar (const SCIPInterval &x, const SCIPInterval &y)

bool	GreaterThanZero (const SCIPInterval &x)

bool	GreaterThanOrZero (const SCIPInterval &x)

bool	LessThanZero (const SCIPInterval &x)

bool	LessThanOrZero (const SCIPInterval &x)

int	Integer (const SCIPInterval &x)

std::ostream &	operator<< (std::ostream &out, const SCIP_INTERVAL &x)

template<>
void	evalMin (CppAD::AD< double > &resultant, const CppAD::AD< double > &arg1, const CppAD::AD< double > &arg2)

template<>
void	evalMax (CppAD::AD< double > &resultant, const CppAD::AD< double > &arg1, const CppAD::AD< double > &arg2)

template<>
void	evalSqrt (CppAD::AD< double > &resultant, const CppAD::AD< double > &arg)

template<>
void	evalAbs (CppAD::AD< SCIPInterval > &resultant, const CppAD::AD< SCIPInterval > &arg)

const char *	SCIPexprintGetName (void)

const char *	SCIPexprintGetDesc (void)

SCIP_EXPRINTCAPABILITY	SCIPexprintGetCapability (void)

SCIP_RETCODE	SCIPexprintCreate (BMS_BLKMEM blkmem, SCIP_EXPRINT *exprint)

SCIP_RETCODE	SCIPexprintFree (SCIP_EXPRINT **exprint)

SCIP_RETCODE	SCIPexprintCompile (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree)

SCIP_RETCODE	SCIPexprintFreeData (SCIP_EXPRINTDATA **interpreterdata)

SCIP_RETCODE	SCIPexprintNewParametrization (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree)

SCIP_RETCODE	SCIPexprintEval (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree, SCIP_Real varvals, SCIP_Real val)

SCIP_RETCODE	SCIPexprintEvalInt (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree, SCIP_Real infinity, SCIP_INTERVAL varvals, SCIP_INTERVAL val)

SCIP_RETCODE	SCIPexprintGrad (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree, SCIP_Real varvals, SCIP_Bool new_varvals, SCIP_Real val, SCIP_Real *gradient)

SCIP_RETCODE	SCIPexprintGradInt (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree, SCIP_Real infinity, SCIP_INTERVAL varvals, SCIP_Bool new_varvals, SCIP_INTERVAL val, SCIP_INTERVAL *gradient)

SCIP_RETCODE	SCIPexprintHessianSparsityDense (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree, SCIP_Real varvals, SCIP_Bool sparsity)

SCIP_RETCODE	SCIPexprintHessianDense (SCIP_EXPRINT exprint, SCIP_EXPRTREE tree, SCIP_Real varvals, SCIP_Bool new_varvals, SCIP_Real val, SCIP_Real *hessian)

Macro Definition Documentation

#define SIGN ( x ) ((x) >= 0.0 ? 1.0 : -1.0)

sign of a value (-1 or +1)

0.0 has sign +1

Definition at line 56 of file exprinterpret_cppad.cpp.

#define SCIPInterval_NAMESPACE CppAD

Definition at line 60 of file exprinterpret_cppad.cpp.

#define CPPAD_MAX_NUM_THREADS 64

Definition at line 71 of file exprinterpret_cppad.cpp.

Function Documentation

SCIPInterval CondExpOp	(	enum CppAD::CompareOp	cop,
		const SCIPInterval &	left,
		const SCIPInterval &	right,
		const SCIPInterval &	trueCase,
		const SCIPInterval &	falseCase
	)

inline

definition of CondExpOp for SCIPInterval (required by CppAD)

Definition at line 191 of file exprinterpret_cppad.cpp.

bool EqualOpSeq	(	const SCIPInterval &	x,
		const SCIPInterval &	y
	)

inline

another function that returns whether two intervals are the same (required by CppAD)

Parameters

x	first operand
y	second operand

Definition at line 208 of file exprinterpret_cppad.cpp.

bool IdenticalPar ( const SCIPInterval & x )

inline

another function required by CppAD

Parameters

x operand

Definition at line 218 of file exprinterpret_cppad.cpp.

bool IdenticalZero ( const SCIPInterval & x )

inline

returns whether the interval equals [0,0]

Parameters

x operand

Definition at line 227 of file exprinterpret_cppad.cpp.

bool IdenticalOne ( const SCIPInterval & x )

inline

returns whether the interval equals [1,1]

Parameters

x operand

Definition at line 236 of file exprinterpret_cppad.cpp.

bool IdenticalEqualPar	(	const SCIPInterval &	x,
		const SCIPInterval &	y
	)

inline

yet another function that checks whether two intervals are equal

Parameters

x	first operand
y	second operand

Definition at line 245 of file exprinterpret_cppad.cpp.

bool GreaterThanZero ( const SCIPInterval & x )

inline

greater than zero not defined for intervals

Parameters

x operand

Definition at line 255 of file exprinterpret_cppad.cpp.

bool GreaterThanOrZero ( const SCIPInterval & x )

inline

greater than or equal zero not defined for intervals

Parameters

x operand

Definition at line 269 of file exprinterpret_cppad.cpp.

bool LessThanZero ( const SCIPInterval & x )

inline

less than not defined for intervals

Parameters

x operand

Definition at line 283 of file exprinterpret_cppad.cpp.

bool LessThanOrZero ( const SCIPInterval & x )

inline

less than or equal not defined for intervals

Parameters

x operand

Definition at line 297 of file exprinterpret_cppad.cpp.

int Integer ( const SCIPInterval & x )

inline

conversion to integers not defined for intervals

Parameters

x operand

Definition at line 311 of file exprinterpret_cppad.cpp.

std::ostream& operator<<	(	std::ostream &	out,
		const SCIP_INTERVAL &	x
	)

inline

printing of an interval (required by CppAD)

Definition at line 325 of file exprinterpret_cppad.cpp.

template<>

void evalMin	(	CppAD::AD< double > &	resultant,
		const CppAD::AD< double > &	arg1,
		const CppAD::AD< double > &	arg2
	)

specialization of minimum evaluation for real numbers

Parameters

resultant	resultant
arg1	first operand
arg2	second operand

Definition at line 1228 of file exprinterpret_cppad.cpp.

template<>

void evalMax	(	CppAD::AD< double > &	resultant,
		const CppAD::AD< double > &	arg1,
		const CppAD::AD< double > &	arg2
	)

specialization of maximum evaluation for real numbers

Parameters

resultant	resultant
arg1	first operand
arg2	second operand

Definition at line 1258 of file exprinterpret_cppad.cpp.

References MAX.

template<>

void evalSqrt	(	CppAD::AD< double > &	resultant,
		const CppAD::AD< double > &	arg
	)

specialization of square-root operator for numbers

We perturb the function a little bit so that it's derivatives are defined in 0.0.

Parameters

resultant	resultant
arg	operand

Definition at line 1286 of file exprinterpret_cppad.cpp.

References sqrt().

template<>

void evalAbs	(	CppAD::AD< SCIPInterval > &	resultant,
		const CppAD::AD< SCIPInterval > &	arg
	)

specialization of absolute value evaluation for intervals

Use sqrt(x^2) for now

Parameters

resultant	resultant
arg	operand

Definition at line 1310 of file exprinterpret_cppad.cpp.

References sqrt().

const char* SCIPexprintGetName ( void )

gets name and version of expression interpreter

Definition at line 1732 of file exprinterpret_cppad.cpp.

const char* SCIPexprintGetDesc ( void )

gets descriptive text of expression interpreter

Definition at line 1738 of file exprinterpret_cppad.cpp.

SCIP_EXPRINTCAPABILITY SCIPexprintGetCapability ( void )

gets capabilities of expression interpreter (using bitflags)

Definition at line 1744 of file exprinterpret_cppad.cpp.

References SCIP_EXPRINTCAPABILITY_FUNCVALUE, SCIP_EXPRINTCAPABILITY_GRADIENT, SCIP_EXPRINTCAPABILITY_HESSIAN, SCIP_EXPRINTCAPABILITY_INTFUNCVALUE, and SCIP_EXPRINTCAPABILITY_INTGRADIENT.

SCIP_RETCODE SCIPexprintCreate	(	BMS_BLKMEM *	blkmem,
		SCIP_EXPRINT **	exprint
	)

creates an expression interpreter object

Parameters

blkmem	block memory data structure
exprint	buffer to store pointer to expression interpreter

Definition at line 1754 of file exprinterpret_cppad.cpp.

References NULL, SCIP_NOMEMORY, and SCIP_OKAY.

SCIP_RETCODE SCIPexprintFree ( SCIP_EXPRINT ** exprint )

frees an expression interpreter object

Parameters

exprint expression interpreter that should be freed

Definition at line 1771 of file exprinterpret_cppad.cpp.

References NULL, and SCIP_OKAY.

SCIP_RETCODE SCIPexprintCompile	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree
	)

compiles an expression tree and stores compiled data in expression tree

Parameters

exprint	interpreter data structure
tree	expression tree

Definition at line 1784 of file exprinterpret_cppad.cpp.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPexprCopyDeep(), SCIPexprFreeDeep(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetRoot(), and SCIPexprtreeSetInterpreterData().

SCIP_RETCODE SCIPexprintFreeData ( SCIP_EXPRINTDATA ** interpreterdata )

frees interpreter data

Parameters

interpreterdata interpreter data that should freed

Definition at line 1832 of file exprinterpret_cppad.cpp.

References NULL, SCIP_OKAY, and SCIPexprFreeDeep().

SCIP_RETCODE SCIPexprintNewParametrization	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree
	)

notify expression interpreter that a new parameterization is used

This probably causes retaping by AD algorithms.

Parameters

exprint	interpreter data structure
tree	expression tree

Definition at line 1852 of file exprinterpret_cppad.cpp.

References NULL, SCIP_OKAY, and SCIPexprtreeGetInterpreterData().

SCIP_RETCODE SCIPexprintEval	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree,
		SCIP_Real *	varvals,
		SCIP_Real *	val
	)

evaluates an expression tree

Parameters

exprint	interpreter data structure
tree	expression tree
varvals	values of variables
val	buffer to store value

Definition at line 1871 of file exprinterpret_cppad.cpp.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetParamVals(), and SCIPexprtreeGetRoot().

Referenced by SCIPexprintGrad(), SCIPexprintHessianDense(), and SCIPexprintHessianSparsityDense().

SCIP_RETCODE SCIPexprintEvalInt	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree,
		SCIP_Real	infinity,
		SCIP_INTERVAL *	varvals,
		SCIP_INTERVAL *	val
	)

evaluates an expression tree on intervals

Parameters

exprint	interpreter data structure
tree	expression tree
infinity	value for infinity
varvals	interval values of variables
val	buffer to store interval value of expression

Definition at line 1933 of file exprinterpret_cppad.cpp.

References SCIPInterval::infinity, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetParamVals(), and SCIPexprtreeGetRoot().

Referenced by SCIPexprintGradInt().

SCIP_RETCODE SCIPexprintGrad	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree,
		SCIP_Real *	varvals,
		SCIP_Bool	new_varvals,
		SCIP_Real *	val,
		SCIP_Real *	gradient
	)

computes value and gradient of an expression tree

Parameters

exprint	interpreter data structure
tree	expression tree
varvals	values of variables, can be NULL if new_varvals is FALSE
new_varvals	have variable values changed since last call to a point evaluation routine?
val	buffer to store expression value
gradient	buffer to store expression gradient, need to have length at least SCIPexprtreeGetNVars(tree)

Definition at line 1993 of file exprinterpret_cppad.cpp.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprintEval(), SCIPexprtreeGetInterpreterData(), and SCIPexprtreeGetNVars().

SCIP_RETCODE SCIPexprintGradInt	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree,
		SCIP_Real	infinity,
		SCIP_INTERVAL *	varvals,
		SCIP_Bool	new_varvals,
		SCIP_INTERVAL *	val,
		SCIP_INTERVAL *	gradient
	)

computes interval value and interval gradient of an expression tree

Parameters

exprint	interpreter data structure
tree	expression tree
infinity	value for infinity
varvals	interval values of variables, can be NULL if new_varvals is FALSE
new_varvals	have variable interval values changed since last call to an interval evaluation routine?
val	buffer to store expression interval value
gradient	buffer to store expression interval gradient, need to have length at least SCIPexprtreeGetNVars(tree)

Definition at line 2037 of file exprinterpret_cppad.cpp.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPexprintEvalInt(), SCIPexprtreeGetInterpreterData(), and SCIPexprtreeGetNVars().

SCIP_RETCODE SCIPexprintHessianSparsityDense	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree,
		SCIP_Real *	varvals,
		SCIP_Bool *	sparsity
	)

gives sparsity pattern of hessian

NOTE: this function might be replaced later by something nicer. Since the AD code might need to do a forward sweep, you should pass variable values in here.

Parameters

exprint	interpreter data structure
tree	expression tree
varvals	values of variables
sparsity	buffer to store sparsity pattern of Hessian, sparsity[i+n*j] indicates whether entry (i,j) is nonzero in the hessian

Definition at line 2084 of file exprinterpret_cppad.cpp.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPexprintEval(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), and TRUE.

SCIP_RETCODE SCIPexprintHessianDense	(	SCIP_EXPRINT *	exprint,
		SCIP_EXPRTREE *	tree,
		SCIP_Real *	varvals,
		SCIP_Bool	new_varvals,
		SCIP_Real *	val,
		SCIP_Real *	hessian
	)

computes value and dense hessian of an expression tree

The full hessian is computed (lower left and upper right triangle).

Parameters

exprint	interpreter data structure
tree	expression tree
varvals	values of variables, can be NULL if new_varvals is FALSE
new_varvals	have variable values changed since last call to an evaluation routine?
val	buffer to store function value
hessian	buffer to store hessian values, need to have size at least n*n

Definition at line 2154 of file exprinterpret_cppad.cpp.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprintEval(), SCIPexprtreeGetInterpreterData(), and SCIPexprtreeGetNVars().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation