Detailed Description
methods to interpret (evaluate) an expression tree "fast" using CppAD
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) |
static char | init_parallel (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} |
Macro Definition Documentation
◆ SIGN
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 init_parallel().
Function Documentation
◆ in_parallel()
|
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 init_parallel().
◆ thread_num()
|
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, and thread_number.
Referenced by init_parallel().
◆ init_parallel()
|
static |
sets up CppAD's datastructures for running in multithreading mode
It must be called once before multithreading is started.
Definition at line 138 of file exprinterpret_cppad.cpp.
References CPPAD_MAX_NUM_THREADS, in_parallel(), and thread_num().
◆ CondExpOp()
|
inline |
definition of CondExpOp for SCIPInterval (required by CppAD)
Definition at line 160 of file exprinterpret_cppad.cpp.
◆ IdenticalPar()
|
inline |
another function required by CppAD
- Parameters
-
x operand
Definition at line 177 of file exprinterpret_cppad.cpp.
◆ IdenticalZero()
|
inline |
returns whether the interval equals [0,0]
- Parameters
-
x operand
Definition at line 186 of file exprinterpret_cppad.cpp.
◆ IdenticalOne()
|
inline |
returns whether the interval equals [1,1]
- Parameters
-
x operand
Definition at line 195 of file exprinterpret_cppad.cpp.
◆ IdenticalEqualPar()
|
inline |
yet another function that checks whether two intervals are equal
- Parameters
-
x first operand y second operand
Definition at line 204 of file exprinterpret_cppad.cpp.
◆ GreaterThanZero()
|
inline |
greater than zero not defined for intervals
- Parameters
-
x operand
Definition at line 214 of file exprinterpret_cppad.cpp.
◆ GreaterThanOrZero()
|
inline |
greater than or equal zero not defined for intervals
- Parameters
-
x operand
Definition at line 228 of file exprinterpret_cppad.cpp.
◆ LessThanZero()
|
inline |
less than not defined for intervals
- Parameters
-
x operand
Definition at line 242 of file exprinterpret_cppad.cpp.
◆ LessThanOrZero()
|
inline |
less than or equal not defined for intervals
- Parameters
-
x operand
Definition at line 256 of file exprinterpret_cppad.cpp.
◆ Integer()
|
inline |
conversion to integers not defined for intervals
- Parameters
-
x operand
Definition at line 270 of file exprinterpret_cppad.cpp.
◆ azmul()
|
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 287 of file exprinterpret_cppad.cpp.
References y.
◆ operator<<()
|
inline |
printing of an interval (required by CppAD)
Definition at line 299 of file exprinterpret_cppad.cpp.
References SCIP_Interval::inf, and SCIP_Interval::sup.
◆ univariate_for_sparse_jac()
|
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 357 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 |
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 377 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 |
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 397 of file exprinterpret_cppad.cpp.
Referenced by atomic_posintpower< Type >::atomic_posintpower(), and atomic_signpower< Type >::atomic_signpower().
◆ posintpower()
|
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 657 of file exprinterpret_cppad.cpp.
References pow().
Referenced by eval(), evalAbs(), and evalIntPower().
◆ evalSignPower()
|
static |
template for evaluation for signpower operator
- Parameters
-
resultant resultant arg operand expr expression that holds the exponent
Definition at line 1126 of file exprinterpret_cppad.cpp.
References pow(), SCIP_Real, and SCIPexprGetSignPowerExponent().
Referenced by eval().
◆ exprEvalUser() [1/2]
SCIP_RETCODE exprEvalUser | ( | SCIP_EXPR * | expr, |
Type * | x, | ||
Type & | funcval, | ||
Type * | gradient, | ||
Type * | hessian | ||
) |
Definition at line 1188 of file exprinterpret_cppad.cpp.
References SCIPexprEvalUser().
Referenced by atomic_userexpr< Type >::atomic_userexpr().
◆ exprEvalUser() [2/2]
SCIP_RETCODE exprEvalUser | ( | SCIP_EXPR * | expr, |
SCIPInterval * | x, | ||
SCIPInterval & | funcval, | ||
SCIPInterval * | gradient, | ||
SCIPInterval * | hessian | ||
) |
Definition at line 1200 of file exprinterpret_cppad.cpp.
References infinity, and SCIPexprEvalIntUser().
◆ evalUser()
|
static |
- Parameters
-
resultant resultant args operands expr expression that holds the user expression
Definition at line 1578 of file exprinterpret_cppad.cpp.
References SCIPexprGetNChildren().
Referenced by eval().
◆ evalMin() [1/2]
|
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 1620 of file exprinterpret_cppad.cpp.
Referenced by eval().
◆ evalMin() [2/2]
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 1634 of file exprinterpret_cppad.cpp.
References MIN.
◆ evalMax() [1/2]
|
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 1650 of file exprinterpret_cppad.cpp.
Referenced by eval().
◆ evalMax() [2/2]
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 1664 of file exprinterpret_cppad.cpp.
References MAX.
◆ evalSqrt()
template for evaluation for square-root operator
Default is to use the standard sqrt-function.
- Parameters
-
resultant resultant arg operand
Definition at line 1679 of file exprinterpret_cppad.cpp.
References sqrt().
Referenced by eval().
◆ evalAbs() [1/2]
template for evaluation for absolute value operator
- Parameters
-
resultant resultant arg operand
Definition at line 1690 of file exprinterpret_cppad.cpp.
References abs().
Referenced by eval().
◆ evalAbs() [2/2]
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 1703 of file exprinterpret_cppad.cpp.
References posintpower(), and sqrt().
◆ evalIntPower()
|
static |
integer power operation for arbitrary integer exponents
- Parameters
-
resultant resultant arg operand exponent exponent
Definition at line 1719 of file exprinterpret_cppad.cpp.
References posintpower().
Referenced by eval().
◆ eval()
|
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 1766 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 |
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 2081 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 |
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 2120 of file exprinterpret_cppad.cpp.
References errorhandler(), and SCIPdebugMessage.
◆ errorhandler()
|
static |
Referenced by cppaderrorcallback().
Variable Documentation
◆ ncurthreads
|
static |
currently registered number of threads
Definition at line 102 of file exprinterpret_cppad.cpp.
Referenced by in_parallel(), and thread_num().
◆ thread_number
|
static |
Definition at line 103 of file exprinterpret_cppad.cpp.
Referenced by thread_num().