1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file struct_expr.h 26 * @ingroup INTERNALAPI 27 * @brief structure definitions related to algebraic expressions 28 * @author Ksenia Bestuzheva 29 * @author Benjamin Mueller 30 * @author Felipe Serrano 31 * @author Stefan Vigerske 32 */ 33 34 #ifndef SCIP_STRUCT_EXPR_H_ 35 #define SCIP_STRUCT_EXPR_H_ 36 37 #include "scip/type_expr.h" 38 #include "scip/type_clock.h" 39 #include "scip/type_stat.h" 40 #include "blockmemshell/memory.h" 41 42 /** generic data and callback methods of an expression handler */ 43 struct SCIP_Exprhdlr 44 { 45 char* name; /**< expression handler name */ 46 char* desc; /**< expression handler description (can be NULL) */ 47 SCIP_EXPRHDLRDATA* data; /**< data of handler */ 48 unsigned int precedence; /**< precedence of expression operation relative to other expression (used for printing) */ 49 50 /* callbacks */ 51 SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)); /**< handler copy callback (can be NULL) */ 52 SCIP_DECL_EXPRFREEHDLR((*freehdlr)); /**< handler free callback (can be NULL) */ 53 SCIP_DECL_EXPRCOPYDATA((*copydata)); /**< data copy callback, or NULL for expressions that have no data */ 54 SCIP_DECL_EXPRFREEDATA((*freedata)); /**< data free callback, or NULL for expressions that have no data or which data does not need to be freed */ 55 SCIP_DECL_EXPRSIMPLIFY((*simplify)); /**< simplify callback (can be NULL) */ 56 SCIP_DECL_EXPRCOMPARE((*compare)); /**< compare callback (can be NULL) */ 57 SCIP_DECL_EXPRPRINT((*print)); /**< print callback (can be NULL) */ 58 SCIP_DECL_EXPRPARSE((*parse)); /**< parse callback (can be NULL) */ 59 SCIP_DECL_EXPREVAL((*eval)); /**< point evaluation callback (can never be NULL) */ 60 SCIP_DECL_EXPRBWDIFF((*bwdiff)); /**< backward derivative evaluation callback (can be NULL) */ 61 SCIP_DECL_EXPRFWDIFF((*fwdiff)); /**< forward derivative evaluation callback (can be NULL) */ 62 SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)); /**< backward over forward derivative evaluation callback (can be NULL) */ 63 SCIP_DECL_EXPRINTEVAL((*inteval)); /**< interval evaluation callback (can be NULL) */ 64 SCIP_DECL_EXPRESTIMATE((*estimate)); /**< estimation callback (can be NULL) */ 65 SCIP_DECL_EXPRINITESTIMATES((*initestimates)); /**< initial estimators callback (can be NULL) */ 66 SCIP_DECL_EXPRREVERSEPROP((*reverseprop));/**< reverse propagation callback (can be NULL) */ 67 SCIP_DECL_EXPRHASH((*hash)); /**< hash callback (can be NULL) */ 68 SCIP_DECL_EXPRCURVATURE((*curvature)); /**< curvature detection callback (can be NULL) */ 69 SCIP_DECL_EXPRMONOTONICITY((*monotonicity)); /**< monotonicity detection callback (can be NULL) */ 70 SCIP_DECL_EXPRINTEGRALITY((*integrality));/**< integrality detection callback (can be NULL) */ 71 SCIP_DECL_EXPRGETSYMDATA((*getsymdata)); /**< symmetry information callback (can be NULL) */ 72 73 /* statistics */ 74 unsigned int ncreated; /**< number of times expression has been created */ 75 SCIP_Longint nestimatecalls; /**< number of times the estimation callback was called */ 76 SCIP_Longint nintevalcalls; /**< number of times the interval evaluation callback was called */ 77 SCIP_Longint npropcalls; /**< number of times the propagation callback was called */ 78 SCIP_Longint ncutoffs; /**< number of cutoffs found so far by this expression handler */ 79 SCIP_Longint ndomreds; /**< number of domain reductions found so far by this expression handler */ 80 SCIP_Longint nsimplifycalls; /**< number of times the simplification callback was called */ 81 SCIP_Longint nsimplified; /**< number of times the simplification callback simplified */ 82 SCIP_Longint nbranchscores; /**< number of times branching scores were added by (or for) this expression handler */ 83 84 SCIP_CLOCK* estimatetime; /**< time used for estimation */ 85 SCIP_CLOCK* intevaltime; /**< time used for interval evaluation */ 86 SCIP_CLOCK* proptime; /**< time used for propagation */ 87 SCIP_CLOCK* simplifytime; /**< time used for expression simplification */ 88 }; 89 90 /** expression iteration data stored in an expression */ 91 struct SCIP_ExprIterData 92 { 93 SCIP_EXPR* parent; /**< parent expression in DFS iteration */ 94 int currentchild; /**< child that is currently visited (or will be visited next) by DFS iteration */ 95 SCIP_Longint visitedtag; /**< tag to identify whether an expression has been visited already */ 96 SCIP_EXPRITER_USERDATA userdata; /**< space for iterator user to store some (temporary) data */ 97 }; 98 99 /* private types */ 100 typedef struct SCIP_QuadExpr SCIP_QUADEXPR; /**< representation of expression as quadratic */ 101 typedef struct SCIP_QuadExpr_QuadTerm SCIP_QUADEXPR_QUADTERM; /**< a single term associated to a quadratic variable */ 102 typedef struct SCIP_QuadExpr_BilinTerm SCIP_QUADEXPR_BILINTERM; /**< a single bilinear term */ 103 104 /** an algebraic expression */ 105 struct SCIP_Expr 106 { 107 SCIP_EXPRHDLR* exprhdlr; /**< expression type (as pointer to its handler) */ 108 SCIP_EXPRDATA* exprdata; /**< expression data */ 109 110 int nchildren; /**< number of children */ 111 int childrensize; /**< length of children array */ 112 SCIP_EXPR** children; /**< children expressions */ 113 114 int nuses; /**< reference counter */ 115 SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]; /**< data for expression iterators */ 116 117 /* owner data */ 118 SCIP_EXPR_OWNERDATA* ownerdata; /**< data stored by owner of expression */ 119 SCIP_DECL_EXPR_OWNERFREE((*ownerfree)); /**< callback for freeing ownerdata */ 120 SCIP_DECL_EXPR_OWNERPRINT((*ownerprint)); /**< callback for printing ownerdata */ 121 SCIP_DECL_EXPR_OWNEREVALACTIVITY((*ownerevalactivity)); /**< callback for evaluating activity */ 122 123 /* point-evaluation and differentiation*/ 124 SCIP_Real evalvalue; /**< value of expression from last evaluation (corresponding to evaltag) */ 125 SCIP_Real derivative; /**< partial derivative of a "root path" w.r.t. this expression (see \ref SCIP_EXPR_DIFF "Differentiation methods") */ 126 SCIP_Real dot; /**< directional derivative of this expr (see \ref SCIP_EXPR_DIFF "Differentiation methods") */ 127 SCIP_Real bardot; /**< directional derivative of derivative of root (strictly speaking, a path) w.r.t this expr (see \ref SCIP_EXPR_DIFF "Differentiation methods") */ 128 SCIP_Longint evaltag; /**< tag of point for which the expression has been evaluated last, or 0 */ 129 SCIP_Longint difftag; /**< when computing partial derivatives of an expression w.r.t. a variable, 130 * the tag allows us to decide whether the expression depends on the variable; 131 * the tag will be checked in SCIPgetExprPartialDiff() */ 132 133 /* interval-evaluation (activity) */ 134 SCIP_INTERVAL activity; /**< activity of expression with respect to variable bounds */ 135 SCIP_Longint activitytag; /**< tag of variable bounds for which activity is valid */ 136 137 /* curvature information */ 138 SCIP_EXPRCURV curvature; /**< curvature of the expression w.r.t. bounds that have been used in the last curvature detection */ 139 140 /* integrality information */ 141 SCIP_Bool isintegral; /**< whether expression value is integral in feasible solutions */ 142 143 /* view expression as quadratic */ 144 SCIP_QUADEXPR* quaddata; /**< representation of expression as a quadratic, if checked and being quadratic */ 145 SCIP_Bool quadchecked; /**< whether it has been checked whether the expression is quadratic */ 146 }; 147 148 /** representation of an expression as quadratic */ 149 struct SCIP_QuadExpr 150 { 151 SCIP_Real constant; /**< a constant term */ 152 153 int nlinexprs; /**< number of linear terms */ 154 SCIP_EXPR** linexprs; /**< expressions of linear terms */ 155 SCIP_Real* lincoefs; /**< coefficients of linear terms */ 156 157 int nquadexprs; /**< number of expressions in quadratic terms */ 158 SCIP_QUADEXPR_QUADTERM* quadexprterms; /**< array with quadratic expression terms */ 159 160 int nbilinexprterms; /**< number of bilinear expressions terms */ 161 SCIP_QUADEXPR_BILINTERM* bilinexprterms; /**< bilinear expression terms array */ 162 163 SCIP_Bool allexprsarevars; /**< whether all arguments (linexprs, quadexprterms[.].expr) are variable expressions */ 164 165 SCIP_EXPRCURV curvature; /**< curvature of the quadratic representation of the expression */ 166 SCIP_Bool curvaturechecked; /**< whether curvature has been checked */ 167 168 /* eigen decomposition information */ 169 SCIP_Bool eigeninfostored; /**< whether the eigen information is stored */ 170 SCIP_Real* eigenvalues; /**< eigenvalues of the Q matrix: size of nquadexprs */ 171 SCIP_Real* eigenvectors; /**< eigenvalues of the Q matrix: size of nquadexprs^2 */ 172 }; 173 174 /** a quadratic term associated to an expression */ 175 struct SCIP_QuadExpr_QuadTerm 176 { 177 SCIP_EXPR* expr; /**< expression of quadratic term */ 178 SCIP_Real lincoef; /**< linear coefficient of expression */ 179 SCIP_Real sqrcoef; /**< square coefficient of expression */ 180 181 int nadjbilin; /**< number of bilinear terms this expression is involved in */ 182 int adjbilinsize; /**< size of adjacent bilinear terms array */ 183 int* adjbilin; /**< indices of associated bilinear terms */ 184 185 SCIP_EXPR* sqrexpr; /**< expression that was found to be the square of expr, or NULL if no square term (sqrcoef==0) */ 186 }; 187 188 /** a single bilinear term coef * expr1 * expr2 189 * 190 * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2 191 */ 192 struct SCIP_QuadExpr_BilinTerm 193 { 194 SCIP_EXPR* expr1; /**< first factor of bilinear term */ 195 SCIP_EXPR* expr2; /**< second factor of bilinear term */ 196 SCIP_Real coef; /**< coefficient of bilinear term */ 197 int pos2; /**< position of expr2's quadexprterm in quadexprterms */ 198 199 SCIP_EXPR* prodexpr; /**< expression that was found to be the product of expr1 and expr2 */ 200 }; 201 202 /** expression iterator */ 203 struct SCIP_ExprIter 204 { 205 BMS_BLKMEM* blkmem; /**< block memory */ 206 SCIP_STAT* stat; /**< dynamic problem statistics */ 207 208 SCIP_Bool initialized; /**< whether the iterator has been initialized, that is, is in use */ 209 SCIP_EXPRITER_TYPE itertype; /**< type of expression iterator */ 210 SCIP_EXPR* curr; /**< current expression of the iterator */ 211 int iterindex; /**< index of iterator data in expressions, or -1 if not using iterator data in expressions */ 212 SCIP_Longint visitedtag; /**< tag to mark and recognize an expression as visited, or 0 if not avoiding multiple visits */ 213 214 /* data for rtopological mode */ 215 SCIP_EXPR** dfsexprs; /**< DFS stack */ 216 int* dfsnvisited; /**< number of visited children for each expression in the stack */ 217 int dfsnexprs; /**< total number of expression in stack */ 218 int dfssize; /**< size of DFS stack */ 219 220 /* data for BFS mode */ 221 SCIP_QUEUE* queue; /**< BFS queue */ 222 223 /* data for DFS mode */ 224 SCIP_EXPRITER_STAGE dfsstage; /**< current stage */ 225 unsigned int stopstages; /**< stages in which to interrupt iterator */ 226 }; 227 228 #endif /* SCIP_STRUCT_EXPR_H_ */ 229