Scippy

SCIP

Solving Constraint Integer Programs

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/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, CppAD::AD< double > &arg1, CppAD::AD< double > &arg2)
 
template<>
void evalMax (CppAD::AD< double > &resultant, CppAD::AD< double > &arg1, CppAD::AD< double > &arg2)
 
template<>
void evalSqrt (CppAD::AD< double > &resultant, CppAD::AD< double > &arg)
 
template<>
void evalAbs (CppAD::AD< SCIPInterval > &resultant, 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 43 of file exprinterpret_cppad.cpp.

#define SCIPInterval_NAMESPACE   CppAD

Definition at line 47 of file exprinterpret_cppad.cpp.

#define CPPAD_MAX_NUM_THREADS   64

CppAD needs to know a fixed upper bound on the number of threads at compile time. It is wise to set it to a power of 2, so that if the tape id overflows, it is likely to start at 0 again, which avoids difficult to debug errors.

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

Definition at line 192 of file exprinterpret_cppad.cpp.

bool IdenticalPar ( const SCIPInterval x)
inline

another function required by CppAD

Parameters
xoperand

Definition at line 202 of file exprinterpret_cppad.cpp.

bool IdenticalZero ( const SCIPInterval x)
inline

returns whether the interval equals [0,0]

Parameters
xoperand

Definition at line 211 of file exprinterpret_cppad.cpp.

bool IdenticalOne ( const SCIPInterval x)
inline

returns whether the interval equals [1,1]

Parameters
xoperand

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

Definition at line 229 of file exprinterpret_cppad.cpp.

bool GreaterThanZero ( const SCIPInterval x)
inline

greater than zero not defined for intervals

Parameters
xoperand

Definition at line 239 of file exprinterpret_cppad.cpp.

bool GreaterThanOrZero ( const SCIPInterval x)
inline

greater than or equal zero not defined for intervals

Parameters
xoperand

Definition at line 253 of file exprinterpret_cppad.cpp.

bool LessThanZero ( const SCIPInterval x)
inline

less than not defined for intervals

Parameters
xoperand

Definition at line 267 of file exprinterpret_cppad.cpp.

bool LessThanOrZero ( const SCIPInterval x)
inline

less than or equal not defined for intervals

Parameters
xoperand

Definition at line 281 of file exprinterpret_cppad.cpp.

int Integer ( const SCIPInterval x)
inline

conversion to integers not defined for intervals

Parameters
xoperand

Definition at line 295 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 309 of file exprinterpret_cppad.cpp.

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

specialization of minimum evaluation for real numbers

Parameters
resultantresultant
arg1first operand
arg2second operand

Definition at line 1197 of file exprinterpret_cppad.cpp.

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

specialization of maximum evaluation for real numbers

Parameters
resultantresultant
arg1first operand
arg2second operand

Definition at line 1227 of file exprinterpret_cppad.cpp.

References MAX.

template<>
void evalSqrt ( CppAD::AD< double > &  resultant,
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
resultantresultant
argoperand

Definition at line 1253 of file exprinterpret_cppad.cpp.

References sqrt().

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

specialization of absolute value evaluation for intervals use sqrt(x^2) for now

Parameters
resultantresultant
argoperand

Definition at line 1277 of file exprinterpret_cppad.cpp.

References sqrt().

const char* SCIPexprintGetName ( void  )

gets name and version of expression interpreter

Definition at line 1670 of file exprinterpret_cppad.cpp.

const char* SCIPexprintGetDesc ( void  )

gets descriptive text of expression interpreter

Definition at line 1676 of file exprinterpret_cppad.cpp.

SCIP_EXPRINTCAPABILITY SCIPexprintGetCapability ( void  )
SCIP_RETCODE SCIPexprintCreate ( BMS_BLKMEM *  blkmem,
SCIP_EXPRINT **  exprint 
)

creates an expression interpreter object

Parameters
blkmemblock memory data structure
exprintbuffer to store pointer to expression interpreter

Definition at line 1692 of file exprinterpret_cppad.cpp.

References NULL, SCIP_NOMEMORY, and SCIP_OKAY.

SCIP_RETCODE SCIPexprintFree ( SCIP_EXPRINT **  exprint)

frees an expression interpreter object

Parameters
exprintexpression interpreter that should be freed

Definition at line 1709 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
exprintinterpreter data structure
treeexpression tree

Definition at line 1722 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
interpreterdatainterpreter data that should freed

Definition at line 1770 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
exprintinterpreter data structure
treeexpression tree

Definition at line 1789 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
exprintinterpreter data structure
treeexpression tree
varvalsvalues of variables
valbuffer to store value

Definition at line 1808 of file exprinterpret_cppad.cpp.

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

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
exprintinterpreter data structure
treeexpression tree
infinityvalue for infinity
varvalsinterval values of variables
valbuffer to store interval value of expression

Definition at line 1871 of file exprinterpret_cppad.cpp.

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

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
exprintinterpreter data structure
treeexpression tree
varvalsvalues of variables, can be NULL if new_varvals is FALSE
new_varvalshave variable values changed since last call to a point evaluation routine?
valbuffer to store expression value
gradientbuffer to store expression gradient, need to have length at least SCIPexprtreeGetNVars(tree)

Definition at line 1931 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
exprintinterpreter data structure
treeexpression tree
infinityvalue for infinity
varvalsinterval values of variables, can be NULL if new_varvals is FALSE
new_varvalshave variable interval values changed since last call to an interval evaluation routine?
valbuffer to store expression interval value
gradientbuffer to store expression interval gradient, need to have length at least SCIPexprtreeGetNVars(tree)

Definition at line 1975 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
exprintinterpreter data structure
treeexpression tree
varvalsvalues of variables
sparsitybuffer to store sparsity pattern of Hessian, sparsity[i+n*j] indicates whether entry (i,j) is nonzero in the hessian

Definition at line 2021 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
exprintinterpreter data structure
treeexpression tree
varvalsvalues of variables, can be NULL if new_varvals is FALSE
new_varvalshave variable values changed since last call to an evaluation routine?
valbuffer to store function value
hessianbuffer to store hessian values, need to have size at least n*n

Definition at line 2090 of file exprinterpret_cppad.cpp.

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