Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions | Variables
exprinterpret_cppad.cpp File Reference
Public API of SCIP » Plugin API of SCIP » Expression Interpreter

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

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 pthread_mutex_t cppadmutex = PTHREAD_MUTEX_INITIALIZER
 
static pthread_key_t thread_specific_key
 
static size_t ncurthreads = 0
 

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

Referenced by init_parallel().

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

References ncurthreads.

Referenced by init_parallel().

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

References cppadmutex, ncurthreads, NULL, SCIPdebugMessage, and thread_specific_key.

Referenced by init_parallel().

◆ init_parallel()

static char init_parallel ( void  )
static

sets up CppAD's datastructures for running in multithreading mode

It must be called once before multithreading is started.

Definition at line 151 of file exprinterpret_cppad.cpp.

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

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

◆ IdenticalPar()

bool IdenticalPar ( const SCIPInterval &  x)
inline

another function required by CppAD

Parameters
xoperand

Definition at line 192 of file exprinterpret_cppad.cpp.

◆ IdenticalZero()

bool IdenticalZero ( const SCIPInterval &  x)
inline

returns whether the interval equals [0,0]

Parameters
xoperand

Definition at line 201 of file exprinterpret_cppad.cpp.

◆ IdenticalOne()

bool IdenticalOne ( const SCIPInterval &  x)
inline

returns whether the interval equals [1,1]

Parameters
xoperand

Definition at line 210 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
xfirst operand
ysecond operand

Definition at line 219 of file exprinterpret_cppad.cpp.

◆ GreaterThanZero()

bool GreaterThanZero ( const SCIPInterval &  x)
inline

greater than zero not defined for intervals

Parameters
xoperand

Definition at line 229 of file exprinterpret_cppad.cpp.

◆ GreaterThanOrZero()

bool GreaterThanOrZero ( const SCIPInterval &  x)
inline

greater than or equal zero not defined for intervals

Parameters
xoperand

Definition at line 243 of file exprinterpret_cppad.cpp.

◆ LessThanZero()

bool LessThanZero ( const SCIPInterval &  x)
inline

less than not defined for intervals

Parameters
xoperand

Definition at line 257 of file exprinterpret_cppad.cpp.

◆ LessThanOrZero()

bool LessThanOrZero ( const SCIPInterval &  x)
inline

less than or equal not defined for intervals

Parameters
xoperand

Definition at line 271 of file exprinterpret_cppad.cpp.

◆ Integer()

int Integer ( const SCIPInterval &  x)
inline

conversion to integers not defined for intervals

Parameters
xoperand

Definition at line 285 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
xfirst operand
ysecond operand

Definition at line 302 of file exprinterpret_cppad.cpp.

◆ operator<<()

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

printing of an interval (required by CppAD)

Definition at line 314 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
qnumber of columns in R
rsparsity of R, columnwise
svector to store sparsity of S, columnwise

Definition at line 372 of file exprinterpret_cppad.cpp.

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
qnumber of rows in R
rsparsity of R, rowwise
svector to store sparsity of S, rowwise

Definition at line 392 of file exprinterpret_cppad.cpp.

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
vxindicates whether argument is a variable, or empty vector
ssparsity pattern of S = g'(y)
tvector to store sparsity pattern of T(x) = (g(f(x)))'
qnumber of columns in R, U, and V
rsparsity pattern of R
usparsity pattern of U(x) = g''(f(x)) f'(x) R
vvector to store sparsity pattern of V(x) = (g(f(x)))'' R

Definition at line 412 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
invector which first argument is base
outvector where to store result in first argument
exponentexponent

Definition at line 671 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
resultantresultant
argoperand
exprexpression that holds the exponent

Definition at line 1138 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 1200 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 1212 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
resultantresultant
argsoperands
exprexpression that holds the user expression

Definition at line 1589 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
resultantresultant
arg1first operand
arg2second operand

Definition at line 1631 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
resultantresultant
arg1first operand
arg2second operand

Definition at line 1645 of file exprinterpret_cppad.cpp.

References MIN.

◆ 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
resultantresultant
arg1first operand
arg2second operand

Definition at line 1661 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
resultantresultant
arg1first operand
arg2second operand

Definition at line 1675 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
resultantresultant
argoperand

Definition at line 1690 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
resultantresultant
argoperand

Definition at line 1701 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
resultantresultant
argoperand

Definition at line 1714 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
resultantresultant
argoperand
exponentexponent

Definition at line 1730 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
exprexpression
xvalues of variables
paramvalues of parameters
valbuffer to store expression value

Definition at line 1777 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 2092 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
knownis the error from a known source?
lineline where error occured
filefile where error occured
conderror condition
msgerror message

Definition at line 2131 of file exprinterpret_cppad.cpp.

References errorhandler(), and SCIPdebugMessage.

◆ errorhandler()

static CppAD::ErrorHandler errorhandler ( cppaderrorcallback  )
static

Referenced by cppaderrorcallback().

Variable Documentation

◆ cppadmutex

pthread_mutex_t cppadmutex = PTHREAD_MUTEX_INITIALIZER
static

mutex for locking in pthread case

Definition at line 89 of file exprinterpret_cppad.cpp.

Referenced by thread_num().

◆ thread_specific_key

pthread_key_t thread_specific_key
static

key for accessing thread specific information

Definition at line 92 of file exprinterpret_cppad.cpp.

Referenced by init_parallel(), and thread_num().

◆ ncurthreads

size_t ncurthreads = 0
static

currently registered number of threads

Definition at line 95 of file exprinterpret_cppad.cpp.

Referenced by in_parallel(), and thread_num().