Detailed Description

type definitions for expressions and expression trees

Author: Stefan Vigerske; Thorsten Gellermann

Definition in file type_expr.h.

Macros
#define	SCIP_EXPR_DEGREEINFINITY 65535

#define	SCIP_DECL_EXPREVAL(x) SCIP_RETCODE x (SCIP_EXPROPDATA opdata, int nargs, SCIP_Real* argvals, SCIP_Real* varvals, SCIP_Real* paramvals, SCIP_Real* result)

#define	SCIP_DECL_EXPRINTEVAL(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_EXPROPDATA opdata, int nargs, SCIP_INTERVAL* argvals, SCIP_INTERVAL* varvals, SCIP_Real* paramvals, SCIP_INTERVAL* result)

#define	SCIP_DECL_EXPRCURV(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_EXPROPDATA opdata, int nargs, SCIP_INTERVAL* argbounds, SCIP_EXPRCURV* argcurv, SCIP_EXPRCURV* result)

#define	SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdatasource, SCIP_EXPROPDATA* opdatatarget)

#define	SCIP_DECL_EXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdata)

#define	SCIP_DECL_EXPRGRAPHVARADDED(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)

#define	SCIP_DECL_EXPRGRAPHVARREMOVE(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)

#define	SCIP_DECL_EXPRGRAPHVARCHGIDX(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode, int oldidx, int newidx)

#define	SCIP_EXPRBOUNDSTATUS_VALID 0x0

#define	SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED 0x1

#define	SCIP_EXPRBOUNDSTATUS_CHILDRELAXED 0x2

#define	SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT 0x4

#define	SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT (0x8 \| SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT)

#define	SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE (0x10 \| SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT)

#define	SCIP_DECL_USEREXPRESTIMATE(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_Real* argvals, SCIP_INTERVAL* argbounds, SCIP_Bool overestimate, SCIP_Real* coeffs, SCIP_Real* constant, SCIP_Bool *success)

#define	SCIP_DECL_USEREXPREVAL(x) SCIP_RETCODE x (SCIP_USEREXPRDATA* data, int nargs, SCIP_Real* argvals, SCIP_Real* funcvalue, SCIP_Real* gradient, SCIP_Real* hessian)

#define	SCIP_DECL_USEREXPRINTEVAL(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argvals, SCIP_INTERVAL* funcvalue, SCIP_INTERVAL* gradient, SCIP_INTERVAL* hessian)

#define	SCIP_DECL_USEREXPRCURV(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argbounds, SCIP_EXPRCURV* argcurv, SCIP_EXPRCURV* result)

#define	SCIP_DECL_USEREXPRPROP(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argbounds, SCIP_INTERVAL funcbounds, SCIP_Bool* cutoff)

#define	SCIP_DECL_USEREXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* datasource, SCIP_USEREXPRDATA** datatarget)

#define	SCIP_DECL_USEREXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* data)

Typedefs
typedef enum SCIP_ExprOp	SCIP_EXPROP

typedef union SCIP_ExprOpData	SCIP_EXPROPDATA

typedef struct SCIP_Expr	SCIP_EXPR

typedef struct SCIP_ExprTree	SCIP_EXPRTREE

typedef enum SCIP_ExprCurv	SCIP_EXPRCURV

typedef struct SCIP_QuadElement	SCIP_QUADELEM

typedef struct SCIP_ExprData_Quadratic	SCIP_EXPRDATA_QUADRATIC

typedef struct SCIP_ExprData_Monomial	SCIP_EXPRDATA_MONOMIAL

typedef struct SCIP_ExprData_Polynomial	SCIP_EXPRDATA_POLYNOMIAL

typedef struct SCIP_ExprData_User	SCIP_EXPRDATA_USER

typedef struct SCIP_ExprGraphNode	SCIP_EXPRGRAPHNODE

typedef struct SCIP_ExprGraph	SCIP_EXPRGRAPH

typedef char	SCIP_EXPRBOUNDSTATUS

typedef struct SCIP_UserExprData	SCIP_USEREXPRDATA

Enumerations
enum	SCIP_ExprOp { SCIP_EXPR_VARIDX = 1, SCIP_EXPR_CONST = 2, SCIP_EXPR_PARAM = 3, SCIP_EXPR_PLUS = 8, SCIP_EXPR_MINUS = 9, SCIP_EXPR_MUL = 10, SCIP_EXPR_DIV = 11, SCIP_EXPR_SQUARE = 12, SCIP_EXPR_SQRT = 13, SCIP_EXPR_REALPOWER = 14, SCIP_EXPR_INTPOWER = 15, SCIP_EXPR_SIGNPOWER = 16, SCIP_EXPR_EXP = 17, SCIP_EXPR_LOG = 18, SCIP_EXPR_SIN = 19, SCIP_EXPR_COS = 20, SCIP_EXPR_TAN = 21, SCIP_EXPR_MIN = 24, SCIP_EXPR_MAX = 25, SCIP_EXPR_ABS = 26, SCIP_EXPR_SIGN = 27, SCIP_EXPR_SUM = 64, SCIP_EXPR_PRODUCT = 65, SCIP_EXPR_LINEAR = 66, SCIP_EXPR_QUADRATIC = 67, SCIP_EXPR_POLYNOMIAL = 68, SCIP_EXPR_USER = 69, SCIP_EXPR_LAST = 70 }

enum	SCIP_ExprCurv { SCIP_EXPRCURV_UNKNOWN = 0, SCIP_EXPRCURV_CONVEX = 1, SCIP_EXPRCURV_CONCAVE = 2, SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX \| SCIP_EXPRCURV_CONCAVE }

Macro Definition Documentation

#define SCIP_EXPR_DEGREEINFINITY 65535

value that stands for an infinite degree of an expression (see SCIPexprGetMaxDegree)

Definition at line 114 of file type_expr.h.

Referenced by exprUnconvertPolynomial(), readPolynomial(), and SCIPexprGetMaxDegree().

#define SCIP_DECL_EXPREVAL ( x ) SCIP_RETCODE x (SCIP_EXPROPDATA opdata, int nargs, SCIP_Real* argvals, SCIP_Real* varvals, SCIP_Real* paramvals, SCIP_Real* result)

signature of an expression (pointwise) evaluation function The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.

opdata operand data
nargs number of arguments
argvals values of arguments
varvals values for variables
paramvals values for parameters
result buffer where to store result of evaluation

Definition at line 126 of file type_expr.h.

#define SCIP_DECL_EXPRINTEVAL ( x ) SCIP_RETCODE x (SCIP_Real infinity, SCIP_EXPROPDATA opdata, int nargs, SCIP_INTERVAL* argvals, SCIP_INTERVAL* varvals, SCIP_Real* paramvals, SCIP_INTERVAL* result)

signature of an expression (interval) evaluation function The function should return an empty interval if the function is undefined for the given arguments.

infinity value for infinity
opdata operand data
nargs number of arguments
argvals interval values of arguments
varvals interval values for variables
paramvals values for parameters
result buffer where to store result of evaluation

Definition at line 139 of file type_expr.h.

#define SCIP_DECL_EXPRCURV ( x ) SCIP_RETCODE x (SCIP_Real infinity, SCIP_EXPROPDATA opdata, int nargs, SCIP_INTERVAL* argbounds, SCIP_EXPRCURV* argcurv, SCIP_EXPRCURV* result)

signature of a simple expression curvature check function

infinity value for infinity
opdata operand data
nargs number of arguments
argbounds bounds on value of arguments
argcurv curvature of arguments
paramvals values for parameters
result buffer where to store result of curvature check

Definition at line 151 of file type_expr.h.

#define SCIP_DECL_EXPRCOPYDATA ( x ) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdatasource, SCIP_EXPROPDATA* opdatatarget)

signature of a expression data copy function

blkmem block memory
nchildren number of children in expression
opdatasource source expression data
opdatatarget pointer to target expression data

Definition at line 160 of file type_expr.h.

#define SCIP_DECL_EXPRFREEDATA ( x ) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdata)

signature of a expression data free function

blkmem block memory
nchildren number of children in expression
opdata expression data to free

Definition at line 168 of file type_expr.h.

#define SCIP_DECL_EXPRGRAPHVARADDED ( x ) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)

callback method of expression graph invoked when a new variable has been added to the graph

input:

exprgraph expression graph
userdata a pointer to user data
var variable that has been added to expression graph
varnode new expression graph node for a variable

Definition at line 181 of file type_expr.h.

#define SCIP_DECL_EXPRGRAPHVARREMOVE ( x ) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)

callback method of expression graph invoked when a variable is to be removed from the graph

input:

exprgraph expression graph
userdata a pointer to user data
var variable that will be removed from the expression graph
varnode expression graph node corresponding to variable

Definition at line 191 of file type_expr.h.

#define SCIP_DECL_EXPRGRAPHVARCHGIDX ( x ) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode, int oldidx, int newidx)

callback method of expression graph invoked when a variable changes its index

input:

exprgraph expression graph
userdata a pointer to user data
var variable which will change its index
varnode expression graph node corresponding to variable
oldidx current index of variable
newidx new index the variable will have

Definition at line 203 of file type_expr.h.

#define SCIP_EXPRBOUNDSTATUS_VALID 0x0

bounds are valid, i.e., conform with bounds of children

Definition at line 209 of file type_expr.h.

Referenced by exprgraphCreateNode(), exprgraphNodeUpdateBounds(), exprgraphUpdateVarNodeBounds(), SCIPexprgraphAddNode(), SCIPexprgraphGetNodePolynomialMonomialCurvature(), SCIPexprgraphReplaceVarByLinearSum(), and SCIPexprgraphUpdateNodeBoundsCurvature().

#define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED 0x1

a child bounds were tightened since last calculation

Definition at line 210 of file type_expr.h.

Referenced by exprgraphNodeUpdateBounds(), exprgraphPrintNodeDot(), exprgraphUpdateVarNodeBounds(), SCIPexprgraphAddNode(), SCIPexprgraphNodeSplitOffLinear(), and SCIPexprgraphUpdateNodeBoundsCurvature().

#define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED 0x2

bounds are not valid and need to be recomputed, because the bounds in a child were relaxed

Definition at line 211 of file type_expr.h.

Referenced by exprgraphNodePropagateBounds(), exprgraphNodeUpdateBounds(), exprgraphPrintNodeDot(), exprgraphUpdateVarNodeBounds(), SCIPexprgraphGetNodePolynomialMonomialCurvature(), SCIPexprgraphReplaceVarByLinearSum(), SCIPexprgraphTightenNodeBounds(), and SCIPexprgraphUpdateNodeBoundsCurvature().

#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT 0x4

bounds have been tightened by reverse propagation in a parent, they are valid as long as there has been no relaxation of bounds somewhere in the graph

Definition at line 212 of file type_expr.h.

Referenced by exprgraphNodePropagateBounds(), exprgraphNodeUpdateBounds(), exprgraphPrintNodeDot(), SCIPexprgraphTightenNodeBounds(), and SCIPexprgraphUpdateNodeBoundsCurvature().

#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT (0x8 | SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT)

bounds have recently been tightened by reverse propagation in a parent, this tightening has not been propagated further down yet

Definition at line 213 of file type_expr.h.

Referenced by exprgraphNodePropagateBounds(), and SCIPexprgraphTightenNodeBounds().

#define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE (0x10 | SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT)

bounds may have recently been tightened by reverse propagation in a parent, in any case we want to propagate bounds further down

Definition at line 214 of file type_expr.h.

Referenced by exprgraphNodePropagateBounds(), and SCIPexprgraphTightenNodeBounds().

#define SCIP_DECL_USEREXPRESTIMATE ( x ) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_Real* argvals, SCIP_INTERVAL* argbounds, SCIP_Bool overestimate, SCIP_Real* coeffs, SCIP_Real* constant, SCIP_Bool *success)

signature of an user's expression under/over estimation function The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.

infinity value for infinity
data user expression data
nargs number of arguments
argvals values of arguments
argbounds bounds on value of arguments
overestimate flag indicating whether to over- or under estimate the expression
coeffs buffer where to store resulting coeffs of arguments for the estimator
constant buffer where to store resulting constant of the estimator
success buffer to indicate whether under-/overestimation was successful

Definition at line 234 of file type_expr.h.

#define SCIP_DECL_USEREXPREVAL ( x ) SCIP_RETCODE x (SCIP_USEREXPRDATA* data, int nargs, SCIP_Real* argvals, SCIP_Real* funcvalue, SCIP_Real* gradient, SCIP_Real* hessian)

signature of an user's expression (pointwise) evaluation function The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.

data user expression data
nargs number of arguments
argvals values of arguments
funcvalue buffer where to store result of function evaluation
gradient buffer where to store result of gradient evaluation (NULL if not requested)
hessian buffer where to store result of Hessian evaluation (NULL if not requested, currently full dense matrix)

Definition at line 246 of file type_expr.h.

#define SCIP_DECL_USEREXPRINTEVAL ( x ) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argvals, SCIP_INTERVAL* funcvalue, SCIP_INTERVAL* gradient, SCIP_INTERVAL* hessian)

signature of an user's expression (interval) evaluation function The function should return an empty interval if the function is undefined for the given arguments.

infinity value for infinity
data user expression data
nargs number of arguments
argvals interval values of arguments
funvalue buffer where to store result of function evaluation
gradient buffer where to store result of gradient evaluation (NULL if not requested)
hessian buffer where to store result of Hessian evaluation (NULL if not requested, currently full dense matrix)

Definition at line 259 of file type_expr.h.

#define SCIP_DECL_USEREXPRCURV ( x ) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argbounds, SCIP_EXPRCURV* argcurv, SCIP_EXPRCURV* result)

signature of a user's expression curvature check function

infinity value for infinity
data user expression data
nargs number of arguments
argbounds bounds on value of arguments
argcurv curvature of arguments
result buffer where to store result of curvature check

Definition at line 270 of file type_expr.h.

#define SCIP_DECL_USEREXPRPROP ( x ) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argbounds, SCIP_INTERVAL funcbounds, SCIP_Bool* cutoff)

signature of an user's expression interval propagation function The function should compute intervals of the arguments given an interval for the function itself and all arguments.

infinity value for infinity
data user expression data
nargs number of arguments
argbounds bounds on values of arguments (on output: tightened bounds)
funcbounds bounds on function value
cutoff buffer to indicate whether an empty child interval was found

Definition at line 282 of file type_expr.h.

#define SCIP_DECL_USEREXPRCOPYDATA ( x ) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* datasource, SCIP_USEREXPRDATA** datatarget)

signature of a user's expression data copy function

blkmem block memory
nchildren number of children in expression
datasource source user expression data
datatarget target user expression data

Definition at line 291 of file type_expr.h.

#define SCIP_DECL_USEREXPRFREEDATA ( x ) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* data)

signature of a user's expression data free function

blkmem block memory
nchildren number of children in expression
data user expression data to free

Definition at line 299 of file type_expr.h.

Typedef Documentation

typedef enum SCIP_ExprOp SCIP_EXPROP

expression operand

Definition at line 89 of file type_expr.h.

typedef union SCIP_ExprOpData SCIP_EXPROPDATA

expression operand data

Definition at line 90 of file type_expr.h.

typedef struct SCIP_Expr SCIP_EXPR

expression

Definition at line 91 of file type_expr.h.

typedef struct SCIP_ExprTree SCIP_EXPRTREE

expression tree

Definition at line 92 of file type_expr.h.

typedef enum SCIP_ExprCurv SCIP_EXPRCURV

curvature types

Definition at line 93 of file type_expr.h.

typedef struct SCIP_QuadElement SCIP_QUADELEM

element of a quadratic term

Definition at line 106 of file type_expr.h.

typedef struct SCIP_ExprData_Quadratic SCIP_EXPRDATA_QUADRATIC

the data of a quadratic expression (SCIP_EXPR_QUADRATIC)

Definition at line 107 of file type_expr.h.

typedef struct SCIP_ExprData_Monomial SCIP_EXPRDATA_MONOMIAL

a monomial as part of the data in a polynomial expression

Definition at line 109 of file type_expr.h.

typedef struct SCIP_ExprData_Polynomial SCIP_EXPRDATA_POLYNOMIAL

the data of a polynomial expression (SCIP_EXPR_POLYNOMIAL)

Definition at line 110 of file type_expr.h.

typedef struct SCIP_ExprData_User SCIP_EXPRDATA_USER

expression data of a user expression (not the user-data of a user expression)

Definition at line 112 of file type_expr.h.

typedef struct SCIP_ExprGraphNode SCIP_EXPRGRAPHNODE

node in an expression graph

Definition at line 170 of file type_expr.h.

typedef struct SCIP_ExprGraph SCIP_EXPRGRAPH

an expression graph (DAG)

Definition at line 171 of file type_expr.h.

typedef char SCIP_EXPRBOUNDSTATUS

bitflags that indicate the status of bounds stored in a node of an expression graph

Definition at line 216 of file type_expr.h.

typedef struct SCIP_UserExprData SCIP_USEREXPRDATA

the user data of a user expression

Definition at line 219 of file type_expr.h.

Enumeration Type Documentation

enum SCIP_ExprOp

Operators of expressions.

Enumerator
SCIP_EXPR_VARIDX	variable given by index (stored in data.idx)
SCIP_EXPR_CONST	constant (value stored in data.dbl)
SCIP_EXPR_PARAM	parameter = a constant that can be modified (should not be simplified away)
SCIP_EXPR_PLUS	addition (2 operands)
SCIP_EXPR_MINUS	substraction (2 operands)
SCIP_EXPR_MUL	multiplication (2 operands)
SCIP_EXPR_DIV	division (2 operands)
SCIP_EXPR_SQUARE	square (1 operand)
SCIP_EXPR_SQRT	square root (1 operand)
SCIP_EXPR_REALPOWER	power with real exponent (1 operand!, assumed to be nonnegative, exponent is stored in expression data)
SCIP_EXPR_INTPOWER	power with integer exponent (1 operand!, exponent stored in expression data)
SCIP_EXPR_SIGNPOWER	signed power (sign(x)\|x\|^a, 1 operand!, exponent is stored in expression data)
SCIP_EXPR_EXP	exponential (e^x, 1 operand)
SCIP_EXPR_LOG	natural logarithm (ln(x), 1 operand)
SCIP_EXPR_SIN	sinus (1 operand)
SCIP_EXPR_COS	cosinus (1 operand)
SCIP_EXPR_TAN	tangent (1 operand)
SCIP_EXPR_MIN	gaussian error function (1 operand) imaginary part of gaussian error function (1 operand) minimum (2 operands)
SCIP_EXPR_MAX	maximum (2 operands)
SCIP_EXPR_ABS	absolute value (1 operand)
SCIP_EXPR_SIGN	sign of value (1 operand)
SCIP_EXPR_SUM	summation sum_{i=1}^n op_i (n operands)
SCIP_EXPR_PRODUCT	product prod_{i=1}^n op_i (n operands)
SCIP_EXPR_LINEAR	linear term sum_{i=1}^n a_i op_i (n operands)
SCIP_EXPR_QUADRATIC	quadratic term sum_{i,j=1}^n a_{i,j} op_i op_j (n operands)
SCIP_EXPR_POLYNOMIAL	polynomial term sum_{I} a_{I}ops^I (I a multiindex, n operands)
SCIP_EXPR_USER	a user defined expression
SCIP_EXPR_LAST	no expression, used for counting reasons

Definition at line 34 of file type_expr.h.

enum SCIP_ExprCurv

Curvature types

Enumerator
SCIP_EXPRCURV_UNKNOWN	unknown curvature (or indefinite)
SCIP_EXPRCURV_CONVEX	convex
SCIP_EXPRCURV_CONCAVE	concave
SCIP_EXPRCURV_LINEAR	linear = convex and concave

Definition at line 81 of file type_expr.h.

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation