1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file type_expr.h 17 * @brief type definitions for expressions and expression trees 18 * @ingroup TYPEDEFINITIONS 19 * @author Stefan Vigerske 20 * @author Thorsten Gellermann 21 */ 22 23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 24 25 #ifndef __SCIP_TYPE_EXPRESSION_H__ 26 #define __SCIP_TYPE_EXPRESSION_H__ 27 28 #include "scip/def.h" 29 30 #ifdef __cplusplus 31 extern "C" { 32 #endif 33 34 /** Operators of expressions. 35 */ 36 enum SCIP_ExprOp { 37 /**@name Terminals (Leaves) */ 38 /**@{ */ 39 SCIP_EXPR_VARIDX = 1, /**< variable given by index (stored in data.idx) */ 40 SCIP_EXPR_CONST = 2, /**< constant (value stored in data.dbl) */ 41 SCIP_EXPR_PARAM = 3, /**< parameter = a constant that can be modified (should not be simplified away) */ 42 /**@} */ 43 44 /**@name Simple Operands */ 45 /**@{ */ 46 SCIP_EXPR_PLUS = 8, /**< addition (2 operands) */ 47 SCIP_EXPR_MINUS = 9, /**< substraction (2 operands) */ 48 SCIP_EXPR_MUL = 10, /**< multiplication (2 operands) */ 49 SCIP_EXPR_DIV = 11, /**< division (2 operands) */ 50 SCIP_EXPR_SQUARE = 12, /**< square (1 operand) */ 51 SCIP_EXPR_SQRT = 13, /**< square root (1 operand) */ 52 SCIP_EXPR_REALPOWER = 14, /**< power with real exponent (1 operand!, assumed to be nonnegative, exponent is stored in expression data) */ 53 SCIP_EXPR_INTPOWER = 15, /**< power with integer exponent (1 operand!, exponent stored in expression data) */ 54 SCIP_EXPR_SIGNPOWER = 16, /**< signed power (sign(x)|x|^a, 1 operand!, exponent is stored in expression data) */ 55 SCIP_EXPR_EXP = 17, /**< exponential (e^x, 1 operand) */ 56 SCIP_EXPR_LOG = 18, /**< natural logarithm (ln(x), 1 operand) */ 57 SCIP_EXPR_SIN = 19, /**< sinus (1 operand) */ 58 SCIP_EXPR_COS = 20, /**< cosinus (1 operand) */ 59 SCIP_EXPR_TAN = 21, /**< tangent (1 operand) */ 60 /* SCIP_EXPR_ERF = 22, */ /**< gaussian error function (1 operand) */ 61 /* SCIP_EXPR_ERFI = 23, */ /**< imaginary part of gaussian error function (1 operand) */ 62 SCIP_EXPR_MIN = 24, /**< minimum (2 operands) */ 63 SCIP_EXPR_MAX = 25, /**< maximum (2 operands) */ 64 SCIP_EXPR_ABS = 26, /**< absolute value (1 operand) */ 65 SCIP_EXPR_SIGN = 27, /**< sign of value (1 operand) */ 66 /**@} */ 67 68 /**@name Complex Operands 69 */ 70 /**@{ */ 71 SCIP_EXPR_SUM = 64, /**< summation sum_{i=1}^n op_i (n operands) */ 72 SCIP_EXPR_PRODUCT = 65, /**< product prod_{i=1}^n op_i (n operands) */ 73 SCIP_EXPR_LINEAR = 66, /**< linear term sum_{i=1}^n a_i op_i (n operands) */ 74 SCIP_EXPR_QUADRATIC = 67, /**< quadratic term sum_{i,j=1}^n a_{i,j} op_i op_j (n operands) */ 75 SCIP_EXPR_POLYNOMIAL= 68, /**< polynomial term sum_{I} a_{I}ops^I (I a multiindex, n operands) */ 76 SCIP_EXPR_USER = 69, /**< a user defined expression */ 77 /**@} */ 78 79 SCIP_EXPR_LAST = 70 /**< no expression, used for counting reasons */ 80 }; 81 82 /** Curvature types */ 83 enum SCIP_ExprCurv 84 { 85 SCIP_EXPRCURV_UNKNOWN = 0, /**< unknown curvature (or indefinite) */ 86 SCIP_EXPRCURV_CONVEX = 1, /**< convex */ 87 SCIP_EXPRCURV_CONCAVE = 2, /**< concave */ 88 SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX | SCIP_EXPRCURV_CONCAVE/**< linear = convex and concave */ 89 }; 90 91 typedef enum SCIP_ExprOp SCIP_EXPROP; /**< expression operand */ 92 typedef union SCIP_ExprOpData SCIP_EXPROPDATA; /**< expression operand data */ 93 typedef struct SCIP_Expr SCIP_EXPR; /**< expression */ 94 typedef struct SCIP_ExprTree SCIP_EXPRTREE; /**< expression tree */ 95 typedef enum SCIP_ExprCurv SCIP_EXPRCURV; /**< curvature types */ 96 97 /** An element of a quadratic term: two variable indices and a coefficient. 98 * The convention is to have idx1 <= idx2. 99 */ 100 struct SCIP_QuadElement 101 { 102 int idx1; /**< index of first variable */ 103 int idx2; /**< index of second variable */ 104 SCIP_Real coef; /**< value of coefficient at position (idx1, idx2) */ 105 }; 106 /* We have defined struct SCIP_QuadElement here (instead of type_expression.h) to allow fast access, allocation, and copying. (similar to SCIP_INTERVAL) */ 107 108 typedef struct SCIP_QuadElement SCIP_QUADELEM; /**< element of a quadratic term */ 109 typedef struct SCIP_ExprData_Quadratic SCIP_EXPRDATA_QUADRATIC; /**< the data of a quadratic expression (SCIP_EXPR_QUADRATIC) */ 110 111 typedef struct SCIP_ExprData_Monomial SCIP_EXPRDATA_MONOMIAL; /**< a monomial as part of the data in a polynomial expression */ 112 typedef struct SCIP_ExprData_Polynomial SCIP_EXPRDATA_POLYNOMIAL; /**< the data of a polynomial expression (SCIP_EXPR_POLYNOMIAL) */ 113 114 typedef struct SCIP_ExprData_User SCIP_EXPRDATA_USER; /**< expression data of a user expression (not the user-data of a user expression) */ 115 116 #define SCIP_EXPR_DEGREEINFINITY 65535 /**< value that stands for an infinite degree of an expression (see SCIPexprGetMaxDegree) */ 117 118 /** signature of an expression (pointwise) evaluation function 119 * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments. 120 * 121 * - opdata operand data 122 * - nargs number of arguments 123 * - argvals values of arguments 124 * - varvals values for variables 125 * - paramvals values for parameters 126 * - result buffer where to store result of evaluation 127 */ 128 #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) 129 130 /** signature of an expression (interval) evaluation function 131 * The function should return an empty interval if the function is undefined for the given arguments. 132 * 133 * - infinity value for infinity 134 * - opdata operand data 135 * - nargs number of arguments 136 * - argvals interval values of arguments 137 * - varvals interval values for variables 138 * - paramvals values for parameters 139 * - result buffer where to store result of evaluation 140 */ 141 #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) 142 143 /** signature of a simple expression curvature check function 144 * 145 * - infinity value for infinity 146 * - opdata operand data 147 * - nargs number of arguments 148 * - argbounds bounds on value of arguments 149 * - argcurv curvature of arguments 150 * - paramvals values for parameters 151 * - result buffer where to store result of curvature check 152 */ 153 #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) 154 155 /** signature of a expression data copy function 156 * 157 * - blkmem block memory 158 * - nchildren number of children in expression 159 * - opdatasource source expression data 160 * - opdatatarget pointer to target expression data 161 */ 162 #define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdatasource, SCIP_EXPROPDATA* opdatatarget) 163 164 /** signature of a expression data free function 165 * 166 * - blkmem block memory 167 * - nchildren number of children in expression 168 * - opdata expression data to free 169 */ 170 #define SCIP_DECL_EXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdata) 171 172 typedef struct SCIP_ExprGraphNode SCIP_EXPRGRAPHNODE; /**< node in an expression graph */ 173 typedef struct SCIP_ExprGraph SCIP_EXPRGRAPH; /**< an expression graph (DAG) */ 174 175 /** callback method of expression graph invoked when a new variable has been added to the graph 176 * 177 * input: 178 * - exprgraph expression graph 179 * - userdata a pointer to user data 180 * - var variable that has been added to expression graph 181 * - varnode new expression graph node for a variable 182 */ 183 #define SCIP_DECL_EXPRGRAPHVARADDED(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode) 184 185 /** callback method of expression graph invoked when a variable is to be removed from the graph 186 * 187 * input: 188 * - exprgraph expression graph 189 * - userdata a pointer to user data 190 * - var variable that will be removed from the expression graph 191 * - varnode expression graph node corresponding to variable 192 */ 193 #define SCIP_DECL_EXPRGRAPHVARREMOVE(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode) 194 195 /** callback method of expression graph invoked when a variable changes its index 196 * 197 * input: 198 * - exprgraph expression graph 199 * - userdata a pointer to user data 200 * - var variable which will change its index 201 * - varnode expression graph node corresponding to variable 202 * - oldidx current index of variable 203 * - newidx new index the variable will have 204 */ 205 #define SCIP_DECL_EXPRGRAPHVARCHGIDX(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode, int oldidx, int newidx) 206 207 /* SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE is used to indicate that bounds in a node should be propagated down even if they are not better than the bounds given by the child nodes 208 * this is useful if the expression itself has a domain that is not the whole real numbers and we want to propagate this information down to a child node 209 * e.g., a x^0.3 should result in x >= 0 even if no new bounds on the expression x^0.3 have been obtained 210 */ 211 #define SCIP_EXPRBOUNDSTATUS_VALID 0x0 /**< bounds are valid, i.e., conform with bounds of children */ 212 #define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED 0x1 /**< a child bounds were tightened since last calculation */ 213 #define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED 0x2 /**< bounds are not valid and need to be recomputed, because the bounds in a child were relaxed */ 214 #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 */ 215 #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 */ 216 #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 */ 217 218 typedef char SCIP_EXPRBOUNDSTATUS; /**< bitflags that indicate the status of bounds stored in a node of an expression graph */ 219 220 221 typedef struct SCIP_UserExprData SCIP_USEREXPRDATA; /**< the user data of a user expression */ 222 223 /** signature of an user's expression under/over estimation function 224 * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments. 225 * 226 * - infinity value for infinity 227 * - data user expression data 228 * - nargs number of arguments 229 * - argvals values of arguments 230 * - argbounds bounds on value of arguments 231 * - overestimate flag indicating whether to over- or under estimate the expression 232 * - coeffs buffer where to store resulting coeffs of arguments for the estimator 233 * - constant buffer where to store resulting constant of the estimator 234 * - success buffer to indicate whether under-/overestimation was successful 235 */ 236 #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) 237 238 /** signature of an user's expression (pointwise) evaluation function 239 * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments. 240 * 241 * - data user expression data 242 * - nargs number of arguments 243 * - argvals values of arguments 244 * - funcvalue buffer where to store result of function evaluation 245 * - gradient buffer where to store result of gradient evaluation (NULL if not requested) 246 * - hessian buffer where to store result of Hessian evaluation (NULL if not requested, currently full dense matrix) 247 */ 248 #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) 249 250 /** signature of an user's expression (interval) evaluation function 251 * The function should return an empty interval if the function is undefined for the given arguments. 252 * 253 * - infinity value for infinity 254 * - data user expression data 255 * - nargs number of arguments 256 * - argvals interval values of arguments 257 * - funvalue buffer where to store result of function evaluation 258 * - gradient buffer where to store result of gradient evaluation (NULL if not requested) 259 * - hessian buffer where to store result of Hessian evaluation (NULL if not requested, currently full dense matrix) 260 */ 261 #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) 262 263 /** signature of a user's expression curvature check function 264 * 265 * - infinity value for infinity 266 * - data user expression data 267 * - nargs number of arguments 268 * - argbounds bounds on value of arguments 269 * - argcurv curvature of arguments 270 * - result buffer where to store result of curvature check 271 */ 272 #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) 273 274 /** signature of an user's expression interval propagation function 275 * The function should compute intervals of the arguments given an interval for the function itself and all arguments. 276 * 277 * - infinity value for infinity 278 * - data user expression data 279 * - nargs number of arguments 280 * - argbounds bounds on values of arguments (on output: tightened bounds) 281 * - funcbounds bounds on function value 282 * - cutoff buffer to indicate whether an empty child interval was found 283 */ 284 #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) 285 286 /** signature of a user's expression data copy function 287 * 288 * - blkmem block memory 289 * - nchildren number of children in expression 290 * - datasource source user expression data 291 * - datatarget target user expression data 292 */ 293 #define SCIP_DECL_USEREXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* datasource, SCIP_USEREXPRDATA** datatarget) 294 295 /** signature of a user's expression data free function 296 * 297 * - blkmem block memory 298 * - nchildren number of children in expression 299 * - data user expression data to free 300 */ 301 #define SCIP_DECL_USEREXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* data) 302 303 /** signature of a user's expression print function 304 * The function should print the user expression's name that prepends the list of arguments "(x1,x2,...)". If not specified, only "user" is printed. 305 * 306 * - data user expression data 307 * - messagehdlr SCIP message handler 308 * - file output file, or NULL if standard output should be used 309 */ 310 #define SCIP_DECL_USEREXPRPRINT(x) void x (SCIP_USEREXPRDATA* data, SCIP_MESSAGEHDLR* messagehdlr, FILE* file) 311 312 #ifdef __cplusplus 313 } 314 #endif 315 316 #endif /* __SCIP_TYPE_EXPRESSION_H__ */ 317