exprinterpret_cppad.cpp File Reference

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/utility/error_handler.hpp>
#include <atomic>

Go to the source code of this file.

Data Structures
struct	SCIP_ExprInt
class	atomic_posintpower< Type >
class	atomic_signpower< Type >
class	atomic_userexpr< Type >

Macros
#define	SIGN(x)   ((x) >= 0.0 ? 1.0 : -1.0)
#define	SCIPInterval_NAMESPACE   CppAD
#define	CPPAD_MAX_NUM_THREADS   64

Functions
static bool	in_parallel (void)
static size_t	thread_num (void)
SCIP_EXPORT char	SCIPexprintCppADInitParallel (void)
SCIPInterval	CondExpOp (enum CppAD::CompareOp cop, const SCIPInterval &left, const SCIPInterval &right, const SCIPInterval &trueCase, const SCIPInterval &falseCase)
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)
SCIPInterval	azmul (const SCIPInterval &x, const SCIPInterval &y)
std::ostream &	operator<< (std::ostream &out, const SCIP_INTERVAL &x)
static bool	univariate_for_sparse_jac (size_t q, const CppAD::vector< bool > &r, CppAD::vector< bool > &s)
static bool	univariate_rev_sparse_jac (size_t q, const CppAD::vector< bool > &r, CppAD::vector< bool > &s)
static bool	univariate_rev_sparse_hes (const CppAD::vector< bool > &vx, const CppAD::vector< bool > &s, CppAD::vector< bool > &t, size_t q, const CppAD::vector< bool > &r, const CppAD::vector< bool > &u, CppAD::vector< bool > &v)
template<class Type >
static void	posintpower (const vector< Type > &in, vector< Type > &out, size_t exponent)
template<class Type >
static void	evalSignPower (Type &resultant, const Type &arg, SCIP_EXPR *expr)
template<class Type >
SCIP_RETCODE	exprEvalUser (SCIP_EXPR *expr, Type *x, Type &funcval, Type *gradient, Type *hessian)
template<>
SCIP_RETCODE	exprEvalUser (SCIP_EXPR *expr, SCIPInterval *x, SCIPInterval &funcval, SCIPInterval *gradient, SCIPInterval *hessian)
template<class Type >
static void	evalUser (Type &resultant, const Type *args, SCIP_EXPR *expr)
template<class Type >
static void	evalMin (Type &resultant, const Type &arg1, const Type &arg2)
template<>
void	evalMin (CppAD::AD< double > &resultant, const CppAD::AD< double > &arg1, const CppAD::AD< double > &arg2)
template<class Type >
static void	evalMax (Type &resultant, const Type &arg1, const Type &arg2)
template<>
void	evalMax (CppAD::AD< double > &resultant, const CppAD::AD< double > &arg1, const CppAD::AD< double > &arg2)
template<class Type >
static void	evalSqrt (Type &resultant, const Type &arg)
template<class Type >
static void	evalAbs (Type &resultant, const Type &arg)
template<>
void	evalAbs (CppAD::AD< SCIPInterval > &resultant, const CppAD::AD< SCIPInterval > &arg)
template<class Type >
static void	evalIntPower (Type &resultant, const Type &arg, const int exponent)
template<class Type >
static SCIP_RETCODE	eval (SCIP_EXPR *expr, const vector< Type > &x, SCIP_Real *param, Type &val)
static void	analyzeTree (SCIP_EXPRINTDATA *data, SCIP_EXPR *expr)
static void	cppaderrorcallback (bool known, int line, const char *file, const char *cond, const char *msg)
static CppAD::ErrorHandler	errorhandler (cppaderrorcallback)
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_EXPRINTCAPABILITY	SCIPexprintGetExprtreeCapability (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)

Variables
static std::atomic_size_t	ncurthreads {0}
static thread_local int	thread_number {-1}
static char	init_parallel_return = SCIPexprintCppADInitParallel()

Macro Definition Documentation

SIGN

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

Referenced by atomic_signpower< Type >::atomic_signpower().

SCIPInterval_NAMESPACE

#define SCIPInterval_NAMESPACE   CppAD

Definition at line 60 of file exprinterpret_cppad.cpp.

CPPAD_MAX_NUM_THREADS

#define CPPAD_MAX_NUM_THREADS   64

Definition at line 74 of file exprinterpret_cppad.cpp.

Referenced by SCIPexprintCppADInitParallel().

Function Documentation

in_parallel()

static bool in_parallel ( void  )

static

CppAD callback function that indicates whether we are running in parallel mode

Definition at line 107 of file exprinterpret_cppad.cpp.

References ncurthreads.

Referenced by SCIPexprintCppADInitParallel().

thread_num()

static size_t thread_num ( void  )

static

CppAD callback function that returns the number of the current thread

assigns a new number to the thread if new

Definition at line 117 of file exprinterpret_cppad.cpp.

References ncurthreads, SCIP_EXPORT, SCIPexprintCppADInitParallel(), and thread_number.

Referenced by SCIPexprintCppADInitParallel().

SCIPexprintCppADInitParallel()

char SCIPexprintCppADInitParallel

(

void

)

sets up CppAD's datastructures for running in multithreading mode

It must be called once before multithreading is started. For GCC-compatible compilers, this will happen automatically.

Definition at line 142 of file exprinterpret_cppad.cpp.

References CPPAD_MAX_NUM_THREADS, in_parallel(), and thread_num().

Referenced by thread_num().

CondExpOp()

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 163 of file exprinterpret_cppad.cpp.

IdenticalPar()

bool IdenticalPar ( const SCIPInterval &  x )

inline

another function required by CppAD

Parameters

x

operand

Definition at line 180 of file exprinterpret_cppad.cpp.

IdenticalZero()

bool IdenticalZero ( const SCIPInterval &  x )

inline

returns whether the interval equals [0,0]

Parameters

x

operand

Definition at line 189 of file exprinterpret_cppad.cpp.

IdenticalOne()

bool IdenticalOne ( const SCIPInterval &  x )

inline

returns whether the interval equals [1,1]

Parameters

x

operand

Definition at line 198 of file exprinterpret_cppad.cpp.

IdenticalEqualPar()

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 207 of file exprinterpret_cppad.cpp.

GreaterThanZero()

bool GreaterThanZero ( const SCIPInterval &  x )

inline

greater than zero not defined for intervals

Parameters

x

operand

Definition at line 217 of file exprinterpret_cppad.cpp.

GreaterThanOrZero()

bool GreaterThanOrZero ( const SCIPInterval &  x )

inline

greater than or equal zero not defined for intervals

Parameters

x

operand

Definition at line 231 of file exprinterpret_cppad.cpp.

LessThanZero()

bool LessThanZero ( const SCIPInterval &  x )

inline

less than not defined for intervals

Parameters

x

operand

Definition at line 245 of file exprinterpret_cppad.cpp.

LessThanOrZero()

bool LessThanOrZero ( const SCIPInterval &  x )

inline

less than or equal not defined for intervals

Parameters

x

operand

Definition at line 259 of file exprinterpret_cppad.cpp.

Integer()

int Integer ( const SCIPInterval &  x )

inline

conversion to integers not defined for intervals

Parameters

x

operand

Definition at line 273 of file exprinterpret_cppad.cpp.

azmul()

SCIPInterval azmul ( const SCIPInterval &  x, const SCIPInterval &  y  )

inline

absolute zero multiplication

Returns

[0,0] if first argument is [0,0] independent of whether the second argument is an empty interval or not

Parameters

x	first operand
y	second operand

Definition at line 290 of file exprinterpret_cppad.cpp.

References y.

operator<<()

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

inline

printing of an interval (required by CppAD)

Definition at line 302 of file exprinterpret_cppad.cpp.

References SCIP_Interval::inf, and SCIP_Interval::sup.

univariate_for_sparse_jac()

static bool univariate_for_sparse_jac ( size_t  q, const CppAD::vector< bool > &  r, CppAD::vector< bool > &  s  )

static

computes sparsity of jacobian for a univariate function during a forward sweep

For a 1 x q matrix R, we have to return the sparsity pattern of the 1 x q matrix S(x) = f'(x) * R. Since f'(x) is dense, the sparsity of S will be the sparsity of R.

Parameters

q	number of columns in R
r	sparsity of R, columnwise
s	vector to store sparsity of S, columnwise

Definition at line 360 of file exprinterpret_cppad.cpp.

References r.

Referenced by atomic_posintpower< Type >::atomic_posintpower(), and atomic_signpower< Type >::atomic_signpower().

univariate_rev_sparse_jac()

static bool univariate_rev_sparse_jac ( size_t  q, const CppAD::vector< bool > &  r, CppAD::vector< bool > &  s  )

static

Computes sparsity of jacobian during a reverse sweep

For a q x 1 matrix R, we have to return the sparsity pattern of the q x 1 matrix S(x) = R * f'(x). Since f'(x) is dense, the sparsity of S will be the sparsity of R.

Parameters

q	number of rows in R
r	sparsity of R, rowwise
s	vector to store sparsity of S, rowwise

Definition at line 380 of file exprinterpret_cppad.cpp.

References r.

Referenced by atomic_posintpower< Type >::atomic_posintpower(), and atomic_signpower< Type >::atomic_signpower().

univariate_rev_sparse_hes()

static bool univariate_rev_sparse_hes ( const CppAD::vector< bool > &  vx, const CppAD::vector< bool > &  s, CppAD::vector< bool > &  t, size_t  q, const CppAD::vector< bool > &  r, const CppAD::vector< bool > &  u, CppAD::vector< bool > &  v  )

static

computes sparsity of hessian during a reverse sweep

Assume V(x) = (g(f(x)))'' R with f(x) = x^p for a function g:R->R and a matrix R. we have to specify the sparsity pattern of V(x) and T(x) = (g(f(x)))'.

Parameters

vx	indicates whether argument is a variable, or empty vector
s	sparsity pattern of S = g'(y)
t	vector to store sparsity pattern of T(x) = (g(f(x)))'
q	number of columns in R, U, and V
r	sparsity pattern of R
u	sparsity pattern of U(x) = g''(f(x)) f'(x) R
v	vector to store sparsity pattern of V(x) = (g(f(x)))'' R

Definition at line 400 of file exprinterpret_cppad.cpp.

Referenced by atomic_posintpower< Type >::atomic_posintpower(), and atomic_signpower< Type >::atomic_signpower().

posintpower()

template<class Type >

static void posintpower ( const vector< Type > &  in, vector< Type > &  out, size_t  exponent  )

static

power function with natural exponents

Parameters

in	vector which first argument is base
out	vector where to store result in first argument
exponent	exponent

Definition at line 660 of file exprinterpret_cppad.cpp.

References pow().

Referenced by eval(), evalAbs(), and evalIntPower().

evalSignPower()

template<class Type >

static void evalSignPower ( Type &  resultant, const Type &  arg, SCIP_EXPR *  expr  )

static

template for evaluation for signpower operator

Parameters

resultant	resultant
arg	operand
expr	expression that holds the exponent

Definition at line 1129 of file exprinterpret_cppad.cpp.

References pow(), SCIP_Real, and SCIPexprGetSignPowerExponent().

Referenced by eval().

exprEvalUser() [1/2]

template<class Type >

SCIP_RETCODE exprEvalUser	(	SCIP_EXPR *	expr,
		Type *	x,
		Type &	funcval,
		Type *	gradient,
		Type *	hessian
	)

Definition at line 1191 of file exprinterpret_cppad.cpp.

References SCIPexprEvalUser().

Referenced by atomic_userexpr< Type >::atomic_userexpr().

exprEvalUser() [2/2]

template<>

SCIP_RETCODE exprEvalUser	(	SCIP_EXPR *	expr,
		SCIPInterval *	x,
		SCIPInterval &	funcval,
		SCIPInterval *	gradient,
		SCIPInterval *	hessian
	)

Definition at line 1203 of file exprinterpret_cppad.cpp.

References infinity, and SCIPexprEvalIntUser().

evalUser()

template<class Type >

static void evalUser ( Type &  resultant, const Type *  args, SCIP_EXPR *  expr  )

static

Parameters

resultant	resultant
args	operands
expr	expression that holds the user expression

Definition at line 1581 of file exprinterpret_cppad.cpp.

References SCIPexprGetNChildren().

Referenced by eval().

evalMin() [1/2]

template<class Type >

static void evalMin ( Type &  resultant, const Type &  arg1, const Type &  arg2  )

static

template for evaluation for minimum operator

Only implemented for real numbers, thus gives error by default.

Parameters

resultant	resultant
arg1	first operand
arg2	second operand

Definition at line 1623 of file exprinterpret_cppad.cpp.

Referenced by eval().

evalMin() [2/2]

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 1637 of file exprinterpret_cppad.cpp.

evalMax() [1/2]

template<class Type >

static void evalMax ( Type &  resultant, const Type &  arg1, const Type &  arg2  )

static

template for evaluation for maximum operator

Only implemented for real numbers, thus gives error by default.

Parameters

resultant	resultant
arg1	first operand
arg2	second operand

Definition at line 1653 of file exprinterpret_cppad.cpp.

Referenced by eval().

evalMax() [2/2]

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 1667 of file exprinterpret_cppad.cpp.

References MAX.

evalSqrt()

template<class Type >

static void evalSqrt ( Type &  resultant, const Type &  arg  )

static

template for evaluation for square-root operator

Default is to use the standard sqrt-function.

Parameters

resultant	resultant
arg	operand

Definition at line 1682 of file exprinterpret_cppad.cpp.

References sqrt().

Referenced by eval().

evalAbs() [1/2]

template<class Type >

static void evalAbs ( Type &  resultant, const Type &  arg  )

static

template for evaluation for absolute value operator

Parameters

resultant	resultant
arg	operand

Definition at line 1693 of file exprinterpret_cppad.cpp.

References abs().

Referenced by eval().

evalAbs() [2/2]

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 1706 of file exprinterpret_cppad.cpp.

References posintpower(), and sqrt().

evalIntPower()

template<class Type >

static void evalIntPower ( Type &  resultant, const Type &  arg, const int  exponent  )

static

integer power operation for arbitrary integer exponents

Parameters

resultant	resultant
arg	operand
exponent	exponent

Definition at line 1722 of file exprinterpret_cppad.cpp.

References posintpower().

Referenced by eval().

eval()

template<class Type >

static SCIP_RETCODE eval ( SCIP_EXPR *  expr, const vector< Type > &  x, SCIP_Real *  param, Type &  val  )

static

CppAD compatible evaluation of an expression for given arguments and parameters

Parameters

expr	expression
x	values of variables
param	values of parameters
val	buffer to store expression value

Definition at line 1769 of file exprinterpret_cppad.cpp.

References BMSallocMemoryArray, BMSfreeMemoryArrayNull, SCIP_QuadElement::coef, cos(), evalAbs(), evalIntPower(), evalMax(), evalMin(), evalSignPower(), evalSqrt(), evalUser(), exp(), SCIP_QuadElement::idx2, log(), NULL, posintpower(), pow(), SCIP_CALL, SCIP_ERROR, SCIP_EXPR_ABS, SCIP_EXPR_CONST, SCIP_EXPR_COS, SCIP_EXPR_DIV, SCIP_EXPR_EXP, SCIP_EXPR_INTPOWER, SCIP_EXPR_LAST, SCIP_EXPR_LINEAR, SCIP_EXPR_LOG, SCIP_EXPR_MAX, SCIP_EXPR_MIN, SCIP_EXPR_MINUS, SCIP_EXPR_MUL, SCIP_EXPR_PARAM, SCIP_EXPR_PLUS, SCIP_EXPR_POLYNOMIAL, SCIP_EXPR_PRODUCT, SCIP_EXPR_QUADRATIC, SCIP_EXPR_REALPOWER, SCIP_EXPR_SIGN, SCIP_EXPR_SIGNPOWER, SCIP_EXPR_SIN, SCIP_EXPR_SQRT, SCIP_EXPR_SQUARE, SCIP_EXPR_SUM, SCIP_EXPR_TAN, SCIP_EXPR_USER, SCIP_EXPR_VARIDX, SCIP_NOMEMORY, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetIntPowerExponent(), SCIPexprGetLinearCoefs(), SCIPexprGetLinearConstant(), SCIPexprGetMonomialChildIndices(), SCIPexprGetMonomialCoef(), SCIPexprGetMonomialExponents(), SCIPexprGetMonomialNFactors(), SCIPexprGetMonomials(), SCIPexprGetNChildren(), SCIPexprGetNMonomials(), SCIPexprGetNQuadElements(), SCIPexprGetOperator(), SCIPexprGetOpIndex(), SCIPexprGetOpReal(), SCIPexprGetPolynomialConstant(), SCIPexprGetQuadConstant(), SCIPexprGetQuadElements(), SCIPexprGetQuadLinearCoefs(), SCIPexprGetRealPowerExponent(), SCIPexprSortQuadElems(), sign(), and sin().

Referenced by SCIP_DECL_EXPRFREEDATA(), SCIPexprCreateUser(), SCIPexprgraphCreateNodeUser(), SCIPexprintEval(), and SCIPexprintEvalInt().

analyzeTree()

static void analyzeTree ( SCIP_EXPRINTDATA *  data, SCIP_EXPR *  expr  )

static

analysis an expression tree whether it requires retaping on every evaluation

This may be the case if the evaluation sequence depends on values of operands (e.g., in case of abs, sign, signpower, ...).

Definition at line 2084 of file exprinterpret_cppad.cpp.

References NULL, SCIP_EXPR_ABS, SCIP_EXPR_MAX, SCIP_EXPR_MIN, SCIP_EXPR_SIGNPOWER, SCIP_EXPR_USER, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexprGetOperator(), and SCIPexprGetUserEvalCapability().

Referenced by SCIPexprintCompile().

cppaderrorcallback()

static void cppaderrorcallback ( bool  known, int  line, const char *  file, const char *  cond, const char *  msg  )

static

replacement for CppAD's default error handler

In debug mode, CppAD gives an error when an evaluation contains a nan. We do not want to stop execution in such a case, since the calling routine should check for nan's and decide what to do. Since we cannot ignore this particular error, we ignore all.

Parameters

known	is the error from a known source?
line	line where error occured
file	file where error occured
cond	error condition
msg	error message

Definition at line 2123 of file exprinterpret_cppad.cpp.

References errorhandler(), and SCIPdebugMessage.

errorhandler()

static CppAD::ErrorHandler errorhandler ( cppaderrorcallback  )

static

Referenced by cppaderrorcallback().

Variable Documentation

ncurthreads

std::atomic_size_t ncurthreads {0}

static

currently registered number of threads

Definition at line 102 of file exprinterpret_cppad.cpp.

Referenced by in_parallel(), and thread_num().

thread_number

thread_local int thread_number {-1}

static

Definition at line 103 of file exprinterpret_cppad.cpp.

Referenced by thread_num().

init_parallel_return

char init_parallel_return = SCIPexprintCppADInitParallel()

static

a dummy variable that is initialized to the result of init_parallel

The purpose is to make sure that init_parallel() is called before any multithreading is started.

Definition at line 156 of file exprinterpret_cppad.cpp.