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 expr.h 26 * @brief private functions to work with algebraic expressions 27 * @ingroup INTERNALAPI 28 * @author Ksenia Bestuzheva 29 * @author Benjamin Mueller 30 * @author Felipe Serrano 31 * @author Stefan Vigerske 32 */ 33 34 #ifndef SCIP_EXPR_H_ 35 #define SCIP_EXPR_H_ 36 37 #include "scip/pub_expr.h" 38 #include "scip/type_set.h" 39 #include "scip/type_stat.h" 40 #include "scip/type_clock.h" 41 #include "blockmemshell/memory.h" 42 43 #ifdef NDEBUG 44 #include "scip/struct_expr.h" 45 #include "scip/struct_set.h" 46 #endif 47 48 #ifdef __cplusplus 49 extern "C" { 50 #endif 51 52 /**@name Expression Handler Methods */ 53 /**@{ */ 54 55 /** create expression handler */ 56 SCIP_RETCODE SCIPexprhdlrCreate( 57 BMS_BLKMEM* blkmem, /**< block memory */ 58 SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */ 59 const char* name, /**< name of expression handler (must not be NULL) */ 60 const char* desc, /**< description of expression handler (can be NULL) */ 61 unsigned int precedence, /**< precedence of expression operation (used for printing) */ 62 SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */ 63 SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */ 64 ); 65 66 /** frees expression handler */ 67 SCIP_RETCODE SCIPexprhdlrFree( 68 SCIP_EXPRHDLR** exprhdlr, /**< pointer to expression handler to be freed */ 69 SCIP_SET* set, /**< global SCIP settings */ 70 BMS_BLKMEM* blkmem /**< block memory */ 71 ); 72 73 /** copies the given expression handler to a new scip */ 74 SCIP_RETCODE SCIPexprhdlrCopyInclude( 75 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 76 SCIP_SET* targetset /**< SCIP_SET of SCIP to copy to */ 77 ); 78 79 /** initialization of expression handler (resets statistics) */ 80 void SCIPexprhdlrInit( 81 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 82 SCIP_SET* set /**< global SCIP settings */ 83 ); 84 85 /** calls the print callback of an expression handler 86 * 87 * The method prints an expression. 88 * It is called while iterating over the expression graph at different stages. 89 * 90 * @see SCIP_DECL_EXPRPRINT 91 */ 92 SCIP_RETCODE SCIPexprhdlrPrintExpr( 93 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 94 SCIP_SET* set, /**< global SCIP settings */ 95 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 96 SCIP_EXPR* expr, /**< expression */ 97 SCIP_EXPRITER_STAGE stage, /**< stage of expression iteration */ 98 int currentchild, /**< index of current child if in stage visitingchild or visitedchild */ 99 unsigned int parentprecedence, /**< precedence of parent */ 100 FILE* file /**< the file to print to */ 101 ); 102 103 /** calls the parse callback of an expression handler 104 * 105 * The method parses an expression. 106 * It should be called when parsing an expression and an operator with the expr handler name is found. 107 * 108 * @see SCIP_DECL_EXPRPARSE 109 */ 110 SCIP_RETCODE SCIPexprhdlrParseExpr( 111 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 112 SCIP_SET* set, /**< global SCIP settings */ 113 const char* string, /**< string containing expression to be parse */ 114 const char** endstring, /**< buffer to store the position of string after parsing */ 115 SCIP_EXPR** expr, /**< buffer to store the parsed expression */ 116 SCIP_Bool* success, /**< buffer to store whether the parsing was successful or not */ 117 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 118 void* ownercreatedata /**< data to pass to ownercreate */ 119 ); 120 121 /** calls the curvature check callback of an expression handler 122 * 123 * @see SCIP_DECL_EXPRCURVATURE 124 */ 125 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprCurvature() macro */ 126 SCIP_RETCODE SCIPexprhdlrCurvatureExpr( 127 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 128 SCIP_SET* set, /**< global SCIP settings */ 129 SCIP_EXPR* expr, /**< expression to check the curvature for */ 130 SCIP_EXPRCURV exprcurvature, /**< desired curvature of this expression */ 131 SCIP_Bool* success, /**< buffer to store whether the desired curvature be obtained */ 132 SCIP_EXPRCURV* childcurv /**< array to store required curvature for each child */ 133 ); 134 135 /** calls the monotonicity check callback of an expression handler 136 * 137 * @see SCIP_DECL_EXPRMONOTONICITY 138 */ 139 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprMonotonicity() macro */ 140 SCIP_RETCODE SCIPexprhdlrMonotonicityExpr( 141 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 142 SCIP_SET* set, /**< global SCIP settings */ 143 SCIP_EXPR* expr, /**< expression to check the monotonicity for */ 144 int childidx, /**< index of the considered child expression */ 145 SCIP_MONOTONE* result /**< buffer to store the monotonicity */ 146 ); 147 148 /** calls the integrality check callback of an expression handler 149 * 150 * @see SCIP_DECL_EXPRINTEGRALITY 151 */ 152 SCIP_RETCODE SCIPexprhdlrIntegralityExpr( 153 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 154 SCIP_SET* set, /**< global SCIP settings */ 155 SCIP_EXPR* expr, /**< expression to check integrality for */ 156 SCIP_Bool* isintegral /**< buffer to store whether expression is integral */ 157 ); 158 159 /** calls the hash callback of an expression handler 160 * 161 * The method hashes an expression by taking the hashes of its children into account. 162 * 163 * @see SCIP_DECL_EXPRHASH 164 */ 165 SCIP_RETCODE SCIPexprhdlrHashExpr( 166 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 167 SCIP_SET* set, /**< global SCIP settings */ 168 SCIP_EXPR* expr, /**< expression to be hashed */ 169 unsigned int* hashkey, /**< buffer to store the hash value */ 170 unsigned int* childrenhashes /**< array with hash values of children */ 171 ); 172 173 /** calls the compare callback of an expression handler 174 * 175 * The method receives two expressions, expr1 and expr2, and returns 176 * - -1 if expr1 < expr2, 177 * - 0 if expr1 = expr2, 178 * - 1 if expr1 > expr2. 179 * 180 * @see SCIP_DECL_EXPRCOMPARE 181 */ 182 int SCIPexprhdlrCompareExpr( 183 SCIP_SET* set, /**< global SCIP settings */ 184 SCIP_EXPR* expr1, /**< first expression in comparison */ 185 SCIP_EXPR* expr2 /**< second expression in comparison */ 186 ); 187 188 /** calls the evaluation callback of an expression handler 189 * 190 * The method evaluates an expression by taking the values of its children into account. 191 * 192 * Further, allows to evaluate w.r.t. given expression and children values instead of those stored in children expressions. 193 * 194 * @see SCIP_DECL_EXPREVAL 195 */ 196 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprEval() macro */ 197 SCIP_RETCODE SCIPexprhdlrEvalExpr( 198 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 199 SCIP_SET* set, /**< global SCIP settings */ 200 BMS_BUFMEM* bufmem, /**< buffer memory, can be NULL if childrenvals is NULL */ 201 SCIP_EXPR* expr, /**< expression to be evaluated */ 202 SCIP_Real* val, /**< buffer to store value of expression */ 203 SCIP_Real* childrenvals, /**< values for children, or NULL if values stored in children should be used */ 204 SCIP_SOL* sol /**< solution that is evaluated (can be NULL) */ 205 ); 206 207 /** calls the backward derivative evaluation callback of an expression handler 208 * 209 * The method should compute the partial derivative of expr w.r.t its child at childidx. 210 * That is, it returns 211 * \f[ 212 * \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}} 213 * \f] 214 * 215 * Further, allows to differentiate w.r.t. given expression and children values instead of those stored in children expressions. 216 * 217 * @see SCIP_DECL_EXPRBWDIFF 218 */ 219 SCIP_RETCODE SCIPexprhdlrBwDiffExpr( 220 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 221 SCIP_SET* set, /**< global SCIP settings */ 222 BMS_BUFMEM* bufmem, /**< buffer memory, can be NULL if childrenvals is NULL */ 223 SCIP_EXPR* expr, /**< expression to be differentiated */ 224 int childidx, /**< index of the child */ 225 SCIP_Real* derivative, /**< buffer to store the partial derivative w.r.t. the i-th children */ 226 SCIP_Real* childrenvals, /**< values for children, or NULL if values stored in children should be used */ 227 SCIP_Real exprval /**< value for expression, used only if childrenvals is not NULL */ 228 ); 229 230 /** calls the forward differentiation callback of an expression handler 231 * 232 * @see SCIP_DECL_EXPRFWDIFF 233 */ 234 SCIP_RETCODE SCIPexprhdlrFwDiffExpr( 235 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 236 SCIP_SET* set, /**< global SCIP settings */ 237 SCIP_EXPR* expr, /**< expression to be differentiated */ 238 SCIP_Real* dot, /**< buffer to store derivative value */ 239 SCIP_SOL* direction /**< direction of the derivative (useful only for var expressions) */ 240 ); 241 242 /** calls the evaluation and forward-differentiation callback of an expression handler 243 * 244 * The method evaluates an expression by taking the values of its children into account. 245 * The method differentiates an expression by taking the values and directional derivatives of its children into account. 246 * 247 * Further, allows to evaluate and differentiate w.r.t. given values for children instead of those stored in children expressions. 248 * 249 * It probably doesn't make sense to call this function for a variable-expression if sol and/or direction are not given. 250 * 251 * @see SCIP_DECL_EXPREVAL 252 * @see SCIP_DECL_EXPRFWDIFF 253 */ 254 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprEvalFwdiff() macro */ 255 SCIP_RETCODE SCIPexprhdlrEvalFwDiffExpr( 256 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 257 SCIP_SET* set, /**< global SCIP settings */ 258 BMS_BUFMEM* bufmem, /**< buffer memory, can be NULL if childrenvals is NULL */ 259 SCIP_EXPR* expr, /**< expression to be evaluated */ 260 SCIP_Real* val, /**< buffer to store value of expression */ 261 SCIP_Real* dot, /**< buffer to store derivative value */ 262 SCIP_Real* childrenvals, /**< values for children, or NULL if values stored in children should be used */ 263 SCIP_SOL* sol, /**< solution that is evaluated (can be NULL) */ 264 SCIP_Real* childrendirs, /**< directional derivatives for children, or NULL if dot-values stored in children should be used */ 265 SCIP_SOL* direction /**< direction of the derivative (useful only for var expressions, can be NULL if childrendirs is given) */ 266 ); 267 268 /** calls the evaluation callback for Hessian directions (backward over forward) of an expression handler 269 * 270 * @see SCIP_DECL_EXPRBWFWDIFF 271 */ 272 SCIP_RETCODE SCIPexprhdlrBwFwDiffExpr( 273 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 274 SCIP_SET* set, /**< global SCIP settings */ 275 SCIP_EXPR* expr, /**< expression to be differentiated */ 276 int childidx, /**< index of the child */ 277 SCIP_Real* bardot, /**< buffer to store derivative value */ 278 SCIP_SOL* direction /**< direction of the derivative (useful only for var expressions) */ 279 ); 280 281 /** calls the interval evaluation callback of an expression handler 282 * 283 * @see SCIP_DECL_EXPRINTEVAL 284 */ 285 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprInteval() macro */ 286 SCIP_RETCODE SCIPexprhdlrIntEvalExpr( 287 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 288 SCIP_SET* set, /**< global SCIP settings */ 289 SCIP_EXPR* expr, /**< expression to be evaluated */ 290 SCIP_INTERVAL* interval, /**< buffer where to store interval */ 291 SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), /**< callback to be called when interval-evaluating a variable */ 292 void* intevalvardata /**< data to be passed to intevalvar callback */ 293 ); 294 295 /** calls the estimator callback of an expression handler 296 * 297 * @see SCIP_DECL_EXPRESTIMATE 298 */ 299 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprEstimate() macro */ 300 SCIP_RETCODE SCIPexprhdlrEstimateExpr( 301 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 302 SCIP_SET* set, /**< global SCIP settings */ 303 SCIP_EXPR* expr, /**< expression to be estimated */ 304 SCIP_INTERVAL* localbounds, /**< current bounds for children */ 305 SCIP_INTERVAL* globalbounds, /**< global bounds for children */ 306 SCIP_Real* refpoint, /**< children values for the reference point where to estimate */ 307 SCIP_Bool overestimate, /**< whether the expression needs to be over- or underestimated */ 308 SCIP_Real targetvalue, /**< a value that the estimator shall exceed, can be +/-infinity */ 309 SCIP_Real* coefs, /**< array to store coefficients of estimator */ 310 SCIP_Real* constant, /**< buffer to store constant part of estimator */ 311 SCIP_Bool* islocal, /**< buffer to store whether estimator is valid locally only */ 312 SCIP_Bool* success, /**< buffer to indicate whether an estimator could be computed */ 313 SCIP_Bool* branchcand /**< array to indicate which children (not) to consider for branching */ 314 ); 315 316 /** calls the intitial estimators callback of an expression handler 317 * 318 * @see SCIP_DECL_EXPRINITESTIMATES 319 */ 320 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprInitestimates() macro */ 321 SCIP_RETCODE SCIPexprhdlrInitEstimatesExpr( 322 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 323 SCIP_SET* set, /**< global SCIP settings */ 324 SCIP_EXPR* expr, /**< expression to be estimated */ 325 SCIP_INTERVAL* bounds, /**< bounds for children */ 326 SCIP_Bool overestimate, /**< whether the expression shall be overestimated or underestimated */ 327 SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES], /**< buffer to store coefficients of computed estimators */ 328 SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES], /**< buffer to store constant of computed estimators */ 329 int* nreturned /**< buffer to store number of estimators that have been computed */ 330 ); 331 332 /** calls the simplification callback of an expression handler 333 * 334 * @see SCIP_DECL_EXPRSIMPLIFY 335 */ 336 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPsimplifyExpr() and SCIPexprSimplify() macros */ 337 SCIP_RETCODE SCIPexprhdlrSimplifyExpr( 338 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 339 SCIP_SET* set, /**< global SCIP settings */ 340 SCIP_EXPR* expr, /**< expression to simplify */ 341 SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */ 342 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 343 void* ownercreatedata /**< data to pass to ownercreate */ 344 ); 345 346 /** calls the reverse propagation callback of an expression handler 347 * 348 * The method propagates given bounds over the children of an expression. 349 * 350 * @see SCIP_DECL_EXPRREVERSEPROP 351 */ 352 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprReverseprop() macro */ 353 SCIP_RETCODE SCIPexprhdlrReversePropExpr( 354 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 355 SCIP_SET* set, /**< global SCIP settings */ 356 SCIP_EXPR* expr, /**< expression to propagate */ 357 SCIP_INTERVAL bounds, /**< the bounds on the expression that should be propagated */ 358 SCIP_INTERVAL* childrenbounds, /**< array to store computed bounds for children, initialized with current activity */ 359 SCIP_Bool* infeasible /**< buffer to store whether a children bounds were propagated to an empty interval */ 360 ); 361 362 /**@} */ 363 364 365 /**@name Expression Methods */ 366 /**@{ */ 367 368 /** creates and captures an expression with given expression data and children */ 369 SCIP_RETCODE SCIPexprCreate( 370 SCIP_SET* set, /**< global SCIP settings */ 371 BMS_BLKMEM* blkmem, /**< block memory */ 372 SCIP_EXPR** expr, /**< pointer where to store expression */ 373 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 374 SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */ 375 int nchildren, /**< number of children */ 376 SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */ 377 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 378 void* ownercreatedata /**< data to pass to ownercreate */ 379 ); 380 381 /** appends child to the children list of expr */ 382 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPappendExprChild() macro */ 383 SCIP_RETCODE SCIPexprAppendChild( 384 SCIP_SET* set, /**< global SCIP settings */ 385 BMS_BLKMEM* blkmem, /**< block memory */ 386 SCIP_EXPR* expr, /**< expression */ 387 SCIP_EXPR* child /**< expression to be appended */ 388 ); 389 390 /** overwrites/replaces a child of an expressions 391 * 392 * @note the old child is released and the newchild is captured, unless they are the same (=same pointer) 393 */ 394 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPreplaceExprChild() macro */ 395 SCIP_RETCODE SCIPexprReplaceChild( 396 SCIP_SET* set, /**< global SCIP settings */ 397 SCIP_STAT* stat, /**< dynamic problem statistics */ 398 BMS_BLKMEM* blkmem, /**< block memory */ 399 SCIP_EXPR* expr, /**< expression where a child is going to be replaced */ 400 int childidx, /**< index of child being replaced */ 401 SCIP_EXPR* newchild /**< the new child */ 402 ); 403 404 /** remove all children of expr */ 405 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPremoveExprChildren() macro */ 406 SCIP_RETCODE SCIPexprRemoveChildren( 407 SCIP_SET* set, /**< global SCIP settings */ 408 SCIP_STAT* stat, /**< dynamic problem statistics */ 409 BMS_BLKMEM* blkmem, /**< block memory */ 410 SCIP_EXPR* expr /**< expression */ 411 ); 412 413 /** copies an expression including subexpressions 414 * 415 * @note If copying fails due to an expression handler not being available in the targetscip, then *targetexpr will be set to NULL. 416 * 417 * For all or some expressions, a mapping to an existing expression can be specified via the mapexpr callback. 418 * The mapped expression (including its children) will not be copied in this case and its ownerdata will not be touched. 419 * If, however, the mapexpr callback returns NULL for the targetexpr, then the expr will be copied in the usual way. 420 */ 421 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPduplicateExpr() macro */ 422 SCIP_RETCODE SCIPexprCopy( 423 SCIP_SET* set, /**< global SCIP settings */ 424 SCIP_STAT* stat, /**< dynamic problem statistics */ 425 BMS_BLKMEM* blkmem, /**< block memory */ 426 SCIP_SET* targetset, /**< global SCIP settings data structure where target expression will live */ 427 SCIP_STAT* targetstat, /**< dynamic problem statistics in target SCIP */ 428 BMS_BLKMEM* targetblkmem, /**< block memory in target SCIP */ 429 SCIP_EXPR* sourceexpr, /**< expression to be copied */ 430 SCIP_EXPR** targetexpr, /**< buffer to store pointer to copy of source expression */ 431 SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */ 432 void* mapexprdata, /**< data of expression mapping function */ 433 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 434 void* ownercreatedata /**< data to pass to ownercreate */ 435 ); 436 437 /** duplicates the given expression without its children */ 438 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPduplicateExprShallow() macro */ 439 SCIP_RETCODE SCIPexprDuplicateShallow( 440 SCIP_SET* set, /**< global SCIP settings */ 441 BMS_BLKMEM* blkmem, /**< block memory */ 442 SCIP_EXPR* expr, /**< original expression */ 443 SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */ 444 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 445 void* ownercreatedata /**< data to pass to ownercreate */ 446 ); 447 448 /** captures an expression (increments usage count) */ 449 void SCIPexprCapture( 450 SCIP_EXPR* expr /**< expression */ 451 ); 452 453 /** releases an expression (decrements usage count and possibly frees expression) */ 454 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPreleaseExpr() macro */ 455 SCIP_RETCODE SCIPexprRelease( 456 SCIP_SET* set, /**< global SCIP settings */ 457 SCIP_STAT* stat, /**< dynamic problem statistics */ 458 BMS_BLKMEM* blkmem, /**< block memory */ 459 SCIP_EXPR** expr /**< pointer to expression */ 460 ); 461 462 /** returns whether an expression is a variable expression */ 463 SCIP_Bool SCIPexprIsVar( 464 SCIP_SET* set, /**< global SCIP settings */ 465 SCIP_EXPR* expr /**< expression */ 466 ); 467 468 /** returns whether an expression is a value expression */ 469 SCIP_Bool SCIPexprIsValue( 470 SCIP_SET* set, /**< global SCIP settings */ 471 SCIP_EXPR* expr /**< expression */ 472 ); 473 474 /** returns whether an expression is a sum expression */ 475 SCIP_Bool SCIPexprIsSum( 476 SCIP_SET* set, /**< global SCIP settings */ 477 SCIP_EXPR* expr /**< expression */ 478 ); 479 480 /** returns whether an expression is a product expression */ 481 SCIP_Bool SCIPexprIsProduct( 482 SCIP_SET* set, /**< global SCIP settings */ 483 SCIP_EXPR* expr /**< expression */ 484 ); 485 486 /** returns whether an expression is a power expression */ 487 SCIP_Bool SCIPexprIsPower( 488 SCIP_SET* set, /**< global SCIP settings */ 489 SCIP_EXPR* expr /**< expression */ 490 ); 491 492 /** print an expression as info-message */ 493 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPprintExpr() macro */ 494 SCIP_RETCODE SCIPexprPrint( 495 SCIP_SET* set, /**< global SCIP settings */ 496 SCIP_STAT* stat, /**< dynamic problem statistics */ 497 BMS_BLKMEM* blkmem, /**< block memory */ 498 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 499 FILE* file, /**< file to print to, or NULL for stdout */ 500 SCIP_EXPR* expr /**< expression to be printed */ 501 ); 502 503 /** initializes printing of expressions in dot format to a give FILE* pointer */ 504 SCIP_RETCODE SCIPexprPrintDotInit( 505 SCIP_SET* set, /**< global SCIP settings */ 506 SCIP_STAT* stat, /**< dynamic problem statistics */ 507 BMS_BLKMEM* blkmem, /**< block memory */ 508 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */ 509 FILE* file, /**< file to print to, or NULL for stdout */ 510 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */ 511 ); 512 513 /** initializes printing of expressions in dot format to a file with given filename */ 514 SCIP_RETCODE SCIPexprPrintDotInit2( 515 SCIP_SET* set, /**< global SCIP settings */ 516 SCIP_STAT* stat, /**< dynamic problem statistics */ 517 BMS_BLKMEM* blkmem, /**< block memory */ 518 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */ 519 const char* filename, /**< name of file to print to */ 520 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */ 521 ); 522 523 /** main part of printing an expression in dot format */ 524 SCIP_RETCODE SCIPexprPrintDot( 525 SCIP_SET* set, /**< global SCIP settings */ 526 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 527 SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */ 528 SCIP_EXPR* expr /**< expression to be printed */ 529 ); 530 531 /** finishes printing of expressions in dot format */ 532 SCIP_RETCODE SCIPexprPrintDotFinal( 533 SCIP_SET* set, /**< global SCIP settings */ 534 SCIP_STAT* stat, /**< dynamic problem statistics */ 535 BMS_BLKMEM* blkmem, /**< block memory */ 536 SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */ 537 ); 538 539 /** prints structure of an expression a la Maple's dismantle */ 540 SCIP_RETCODE SCIPexprDismantle( 541 SCIP_SET* set, /**< global SCIP settings */ 542 SCIP_STAT* stat, /**< dynamic problem statistics */ 543 BMS_BLKMEM* blkmem, /**< block memory */ 544 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 545 FILE* file, /**< file to print to, or NULL for stdout */ 546 SCIP_EXPR* expr /**< expression to dismantle */ 547 ); 548 549 /** evaluate an expression in a point 550 * 551 * Iterates over expressions to also evaluate children, if necessary. 552 * Value can be received via SCIPexprGetEvalValue(). 553 * If an evaluation error (division by zero, ...) occurs, this value will 554 * be set to SCIP_INVALID. 555 * 556 * If a nonzero \p soltag is passed, then only (sub)expressions are 557 * reevaluated that have a different solution tag. If a soltag of 0 558 * is passed, then subexpressions are always reevaluated. 559 * The tag is stored together with the value and can be received via 560 * SCIPexprGetEvalTag(). 561 */ 562 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExpr() macro */ 563 SCIP_RETCODE SCIPexprEval( 564 SCIP_SET* set, /**< global SCIP settings */ 565 SCIP_STAT* stat, /**< dynamic problem statistics */ 566 BMS_BLKMEM* blkmem, /**< block memory */ 567 SCIP_EXPR* expr, /**< expression to be evaluated */ 568 SCIP_SOL* sol, /**< solution to be evaluated */ 569 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */ 570 ); 571 572 /** evaluates gradient of an expression for a given point 573 * 574 * Initiates an expression walk to also evaluate children, if necessary. 575 * Value can be received via SCIPgetExprPartialDiffNonlinear(). 576 * If an error (division by zero, ...) occurs, this value will 577 * be set to SCIP_INVALID. 578 */ 579 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExprGradient() macro */ 580 SCIP_RETCODE SCIPexprEvalGradient( 581 SCIP_SET* set, /**< global SCIP settings */ 582 SCIP_STAT* stat, /**< dynamic problem statistics */ 583 BMS_BLKMEM* blkmem, /**< block memory */ 584 SCIP_EXPR* rootexpr, /**< expression to be evaluated */ 585 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */ 586 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */ 587 ); 588 589 /** evaluates Hessian-vector product of an expression for a given point and direction 590 * 591 * Evaluates children, if necessary. 592 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear() 593 * If an error (division by zero, ...) occurs, this value will 594 * be set to SCIP_INVALID. 595 */ 596 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExprHessianDir() macro */ 597 SCIP_RETCODE SCIPexprEvalHessianDir( 598 SCIP_SET* set, /**< global SCIP settings */ 599 SCIP_STAT* stat, /**< dynamic problem statistics */ 600 BMS_BLKMEM* blkmem, /**< block memory */ 601 SCIP_EXPR* rootexpr, /**< expression to be evaluated */ 602 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */ 603 SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */ 604 SCIP_SOL* direction /**< direction */ 605 ); 606 607 /** possibly reevaluates and then returns the activity of the expression 608 * 609 * Reevaluate activity if currently stored is no longer uptodate. 610 * If the expr owner provided a evalactivity-callback, then call this. 611 * Otherwise, loop over descendants and compare activitytag with stat's domchgcount, i.e., 612 * whether some bound was changed since last evaluation, to check whether exprhdlrs INTEVAL should be called. 613 * 614 * @note If expression is set to be integral, then activities are tightened to integral values. 615 * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok). 616 */ 617 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExprActivity() macro */ 618 SCIP_RETCODE SCIPexprEvalActivity( 619 SCIP_SET* set, /**< global SCIP settings */ 620 SCIP_STAT* stat, /**< dynamic problem statistics */ 621 BMS_BLKMEM* blkmem, /**< block memory */ 622 SCIP_EXPR* rootexpr /**< expression */ 623 ); 624 625 /** compare expressions 626 * 627 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively 628 * @note The given expressions are assumed to be simplified. 629 */ 630 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcompareExpr() macro */ 631 int SCIPexprCompare( 632 SCIP_SET* set, /**< global SCIP settings */ 633 SCIP_EXPR* expr1, /**< first expression */ 634 SCIP_EXPR* expr2 /**< second expression */ 635 ); 636 637 /** simplifies an expression 638 * 639 * @see SCIPsimplifyExpr 640 */ 641 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPsimplifyExpr() macro */ 642 SCIP_RETCODE SCIPexprSimplify( 643 SCIP_SET* set, /**< global SCIP settings */ 644 SCIP_STAT* stat, /**< dynamic problem statistics */ 645 BMS_BLKMEM* blkmem, /**< block memory */ 646 SCIP_EXPR* rootexpr, /**< expression to be simplified */ 647 SCIP_EXPR** simplified, /**< buffer to store simplified expression */ 648 SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */ 649 SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */ 650 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 651 void* ownercreatedata /**< data to pass to ownercreate */ 652 ); 653 654 655 /** retrieves symmetry information from an expression 656 * 657 * @see SCIPgetSymDataExpr 658 */ 659 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPgetSymdataExpr() macro */ 660 SCIP_RETCODE SCIPexprGetSymData( 661 SCIP_SET* set, /**< global SCIP settings */ 662 SCIP_EXPR* expr, /**< expression from which information is retrieved */ 663 SYM_EXPRDATA** symdata /**< buffer to store symmetry information */ 664 ); 665 666 #ifdef NDEBUG 667 #define SCIPexprCapture(expr) ++(expr)->nuses 668 #define SCIPexprIsVar(set, expr) ((expr)->exprhdlr == (set)->exprhdlrvar) 669 #define SCIPexprIsValue(set, expr) ((expr)->exprhdlr == (set)->exprhdlrval) 670 #define SCIPexprIsSum(set, expr) ((expr)->exprhdlr == (set)->exprhdlrsum) 671 #define SCIPexprIsProduct(set, expr) ((expr)->exprhdlr == (set)->exprhdlrproduct) 672 #define SCIPexprIsPower(set, expr) ((expr)->exprhdlr == (set)->exprhdlrpow) 673 #endif 674 675 /**@} */ 676 677 /**@name Expression Iterator Methods */ 678 /**@{ */ 679 680 /** creates an expression iterator */ 681 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcreateExpriter() macro */ 682 SCIP_RETCODE SCIPexpriterCreate( 683 SCIP_STAT* stat, /**< dynamic problem statistics */ 684 BMS_BLKMEM* blkmem, /**< block memory */ 685 SCIP_EXPRITER** iterator /**< buffer to store expression iterator */ 686 ); 687 688 /** frees an expression iterator */ 689 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPfreeExpriter() macro */ 690 void SCIPexpriterFree( 691 SCIP_EXPRITER** iterator /**< pointer to the expression iterator */ 692 ); 693 694 /**@} */ 695 696 697 /**@name Quadratic expression functions */ 698 /**@{ */ 699 700 /** checks whether an expression is quadratic 701 * 702 * An expression is quadratic if it is either a power expression with exponent 2.0, a product of two expressions, 703 * or a sum of terms where at least one is a square or a product of two. 704 * 705 * Use \ref SCIPexprGetQuadraticData to get data about the representation as quadratic. 706 */ 707 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcheckExprQuadratic() macro */ 708 SCIP_RETCODE SCIPexprCheckQuadratic( 709 SCIP_SET* set, /**< global SCIP settings */ 710 BMS_BLKMEM* blkmem, /**< block memory */ 711 SCIP_EXPR* expr, /**< expression */ 712 SCIP_Bool* isquadratic /**< buffer to store result */ 713 ); 714 715 /** frees information on quadratic representation of an expression 716 * 717 * Reverts SCIPexprCheckQuadratic(). 718 * Before doing changes to an expression, it can be useful to call this function. 719 */ 720 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPfreeExprQuadratic() macro */ 721 void SCIPexprFreeQuadratic( 722 BMS_BLKMEM* blkmem, /**< block memory */ 723 SCIP_EXPR* expr /**< expression */ 724 ); 725 726 /** Checks the curvature of the quadratic function stored in quaddata 727 * 728 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK. 729 * If Q is 730 * - semidefinite positive -> curv is set to convex, 731 * - semidefinite negative -> curv is set to concave, 732 * - otherwise -> curv is set to unknown. 733 * 734 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in 735 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q. 736 */ 737 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPcomputeExprQuadraticCurvature() macro */ 738 SCIP_RETCODE SCIPexprComputeQuadraticCurvature( 739 SCIP_SET* set, /**< global SCIP settings */ 740 BMS_BLKMEM* blkmem, /**< block memory */ 741 BMS_BUFMEM* bufmem, /**< buffer memory */ 742 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 743 SCIP_EXPR* expr, /**< quadratic expression */ 744 SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */ 745 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ 746 SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */ 747 ); 748 749 /**@} */ 750 751 /**@name Monomial expression functions */ 752 /**@{ */ 753 754 /** returns a monomial representation of a product expression 755 * 756 * The array to store all factor expressions needs to be of size the number of 757 * children in the expression which is given by SCIPexprGetNChildren(). 758 * 759 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where 760 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can 761 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents. 762 * 763 * A non-trivial monomial is a product of a least two expressions. 764 */ 765 SCIP_EXPORT /* need SCIP_EXPORT here, because func is exposed in API via SCIPgetExprMonomialData() macro */ 766 SCIP_RETCODE SCIPexprGetMonomialData( 767 SCIP_SET* set, /**< global SCIP settings */ 768 BMS_BLKMEM* blkmem, /**< block memory */ 769 SCIP_EXPR* expr, /**< expression */ 770 SCIP_Real* coef, /**< coefficient \f$c\f$ */ 771 SCIP_Real* exponents, /**< exponents \f$\alpha\f$ */ 772 SCIP_EXPR** exprs /**< expressions \f$x\f$ */ 773 ); 774 775 /**@} */ 776 777 #ifdef __cplusplus 778 } 779 #endif 780 781 #endif /* SCIP_EXPR_H_ */ 782