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 struct_expr.h 17 * @brief data definitions for expressions and expression trees 18 * @author Stefan Vigerske 19 * @author Thorsten Gellermann 20 */ 21 22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 23 24 #ifndef __SCIP_STRUCT_EXPRESSION_H__ 25 #define __SCIP_STRUCT_EXPRESSION_H__ 26 27 #include "scip/def.h" 28 #include "scip/type_misc.h" 29 #include "nlpi/type_expr.h" 30 #include "nlpi/type_exprinterpret.h" 31 #include "blockmemshell/memory.h" 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 /** operator data of an expression */ 38 union SCIP_ExprOpData 39 { 40 int intval; /**< index of a variable or parameter or a constant integer value */ 41 SCIP_Real dbl; /**< a constant double value */ 42 void* data; /**< pointer to some data structure */ 43 }; 44 45 /** arithmetic expression node */ 46 struct SCIP_Expr 47 { 48 SCIP_EXPROP op; /**< operator of the node */ 49 int nchildren; /**< number of children */ 50 SCIP_EXPR** children; /**< children nodes */ 51 SCIP_EXPROPDATA data; /**< operator data */ 52 }; 53 54 /** expression tree */ 55 struct SCIP_ExprTree 56 { 57 BMS_BLKMEM* blkmem; /**< block memory data structure */ 58 SCIP_EXPR* root; /**< root node expression of expression tree */ 59 int nvars; /**< number of variables */ 60 void** vars; /**< mapping of variable indices to user variables, may be NULL */ 61 int nparams; /**< number of parameters (modifiable constants) in expression */ 62 SCIP_Real* params; /**< current values for parameters, or NULL if no parameters */ 63 SCIP_EXPRINTDATA* interpreterdata; /**< data of expression interpreter (evaluator) */ 64 }; 65 66 /** data of quadratic expression: sum_i coef_i x_i y_i */ 67 struct SCIP_ExprData_Quadratic 68 { 69 SCIP_Real constant; /**< constant term */ 70 SCIP_Real* lincoefs; /**< linear coefficients of children */ 71 SCIP_QUADELEM* quadelems; /**< quadratic elements */ 72 int nquadelems; /**< number of quadratic elements */ 73 SCIP_Bool sorted; /**< are the quadratic elements sorted? */ 74 }; 75 76 /** data of polynomial expression: constant + sum_i monom_i */ 77 struct SCIP_ExprData_Polynomial 78 { 79 SCIP_Real constant; /**< constant term of polynomial */ 80 SCIP_EXPRDATA_MONOMIAL** monomials; /**< monomials that constitute the polynomial */ 81 int monomialssize; /**< size of monomials array */ 82 int nmonomials; /**< number of monomials */ 83 SCIP_Bool sorted; /**< are the monomials sorted? */ 84 }; 85 86 /** data of monomial in polynomial expression: coef * prod_i child_i^exponent_i 87 * we allow for real values exponents here 88 */ 89 struct SCIP_ExprData_Monomial 90 { 91 SCIP_Real coef; /**< coefficient of monomial */ 92 int factorssize; /**< size of factors arrays */ 93 int nfactors; /**< number of factors */ 94 int* childidxs; /**< children corresponding to factors */ 95 SCIP_Real* exponents; /**< value of exponent for each factor */ 96 SCIP_Bool sorted; /**< are the factors sorted (by childidx)? */ 97 }; 98 99 /** data of a user-defined expression 100 */ 101 struct SCIP_ExprData_User 102 { 103 SCIP_USEREXPRDATA* userdata; /**< user data for expression */ 104 SCIP_EXPRINTCAPABILITY evalcapability; /**< capabilities of evaluation functions */ 105 SCIP_DECL_USEREXPREVAL ((*eval)); /**< evaluation function */ 106 SCIP_DECL_USEREXPRINTEVAL ((*inteval)); /**< interval evaluation function */ 107 SCIP_DECL_USEREXPRCURV ((*curv)); /**< curvature check function */ 108 SCIP_DECL_USEREXPRPROP ((*prop)); /**< interval propagation function */ 109 SCIP_DECL_USEREXPRESTIMATE ((*estimate)); /**< under-/over-estimator function */ 110 SCIP_DECL_USEREXPRCOPYDATA ((*copydata)); /**< expression data copy function, or NULL if nothing to copy */ 111 SCIP_DECL_USEREXPRFREEDATA ((*freedata)); /**< expression data free function, or NULL if nothing to free */ 112 SCIP_DECL_USEREXPRPRINT ((*print)); /**< expression print function, or NULL for default string "user()" */ 113 }; 114 115 /** a node in an expression graph */ 116 struct SCIP_ExprGraphNode 117 { 118 /* definition of expression */ 119 SCIP_EXPROP op; /**< operand of expression */ 120 SCIP_EXPROPDATA data; /**< data of expression */ 121 122 /* location of expression in expression graph */ 123 int depth; /**< depth of node in expression graph */ 124 int pos; /**< position of node in expression graph nodes array of depth depth*/ 125 126 /* children of expression */ 127 int nchildren; /**< number of child nodes in expression graph */ 128 SCIP_EXPRGRAPHNODE** children; /**< children nodes */ 129 130 /* parents of expression */ 131 int parentssize; /**< length of parents array */ 132 int nparents; /**< number of parent nodes in expression graph */ 133 SCIP_EXPRGRAPHNODE** parents; /**< parent nodes */ 134 SCIP_Bool parentssorted; /**< whether the parents array is sorted */ 135 136 /* domain propagation */ 137 SCIP_INTERVAL bounds; /**< bounds on expression */ 138 SCIP_EXPRBOUNDSTATUS boundstatus; /**< status of bounds */ 139 140 /* value */ 141 SCIP_Real value; /**< value of expression in last evaluation call */ 142 143 /* curvature */ 144 SCIP_EXPRCURV curv; /**< curvature of expression */ 145 146 /* miscellaneous */ 147 SCIP_Bool enabled; /**< whether the node is enabled currently */ 148 SCIP_Bool simplified; /**< whether the node has been simplified */ 149 int nuses; /**< how often node is used */ 150 }; 151 152 /** a set of expression trees, stored in a single directed acyclic graph 153 * the variables of the graph are stored at depth 0 154 * for each depth, an array of nodes is stored */ 155 struct SCIP_ExprGraph 156 { 157 BMS_BLKMEM* blkmem; /**< block memory */ 158 159 int depth; /**< depth of expression graph */ 160 int* nodessize; /**< current size of nodes array for each depth */ 161 int* nnodes; /**< number of nodes for each depth */ 162 SCIP_EXPRGRAPHNODE*** nodes; /**< nodes of expression graph for each depth */ 163 164 int varssize; /**< length of vars array */ 165 int nvars; /**< number of variables in expression graph */ 166 void** vars; /**< array for variables in expression graph, having length varssize */ 167 SCIP_EXPRGRAPHNODE** varnodes; /**< nodes corresponding to variables in expression graph */ 168 SCIP_INTERVAL* varbounds; /**< current bounds on variables */ 169 SCIP_HASHMAP* varidxs; /**< maps variables to variable indices */ 170 171 int constssize; /**< length of consts array */ 172 int nconsts; /**< number of constants in expression graph */ 173 SCIP_EXPRGRAPHNODE** constnodes; /**< nodes corresponding to constants in expression graph */ 174 SCIP_Bool constssorted; /**< whether the constnodes array has been sorted */ 175 176 SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)); /**< callback for variable addition event */ 177 SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)); /**< callback for variable removal event */ 178 SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)); /**< callback for variable index change event */ 179 void* userdata; /**< user data associated with callback methods */ 180 181 SCIP_Bool needvarboundprop; /**< whether variable bounds need be propagated, e.g., because new nodes have been added to the graph */ 182 183 int lastreplacechildpos; /**< last position where a child was found that was replaced, used to heuristically speed up consecutive calls to exprgraphNodeReplaceChild */ 184 }; 185 186 #ifdef __cplusplus 187 } 188 #endif 189 190 #endif /* __SCIP_STRUCT_EXPRESSION_H__ */ 191