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 type_expr.h 26 * @ingroup TYPEDEFINITIONS 27 * @brief type and macro definitions related to algebraic expressions 28 * @author Ksenia Bestuzheva 29 * @author Benjamin Mueller 30 * @author Felipe Serrano 31 * @author Stefan Vigerske 32 * 33 * This file defines the interface for expression handlers. 34 * 35 * - \ref EXPRHDLRS "List of available expression handlers" 36 */ 37 38 /** @defgroup DEFPLUGINS_EXPR Default expression handlers 39 * @ingroup DEFPLUGINS 40 * @brief implementation files (.c files) of the default expression handlers of SCIP 41 */ 42 43 #ifndef SCIP_TYPE_EXPR_H_ 44 #define SCIP_TYPE_EXPR_H_ 45 46 #include "scip/def.h" 47 #include "scip/intervalarith.h" 48 #include "scip/type_scip.h" 49 #include "scip/type_sol.h" 50 #include "scip/type_var.h" 51 #include "scip/type_tree.h" 52 53 typedef struct SCIP_ExprData SCIP_EXPRDATA; /**< expression data, e.g., coefficients */ 54 typedef struct SCIP_Expr SCIP_EXPR; /**< expression */ 55 typedef struct SYM_ExprData SYM_EXPRDATA; /**< (additional) data used to encode an expression, 56 * which is not encoded as another expression */ 57 58 /** curvature types */ 59 typedef enum 60 { 61 SCIP_EXPRCURV_UNKNOWN = 0, /**< unknown or indefinite curvature */ 62 SCIP_EXPRCURV_CONVEX = 1, /**< convex */ 63 SCIP_EXPRCURV_CONCAVE = 2, /**< concave */ 64 SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX | SCIP_EXPRCURV_CONCAVE/**< linear = convex and concave */ 65 } SCIP_EXPRCURV; 66 67 /** monotonicity */ 68 typedef enum 69 { 70 SCIP_MONOTONE_UNKNOWN = 0, /**< unknown or non-monotone */ 71 SCIP_MONOTONE_INC = 1, /**< increasing */ 72 SCIP_MONOTONE_DEC = 2, /**< decreasing */ 73 SCIP_MONOTONE_CONST = SCIP_MONOTONE_INC | SCIP_MONOTONE_DEC /**< constant = increasing and decreasing */ 74 } SCIP_MONOTONE; 75 76 /**@name Expression Owner */ 77 /**@{ */ 78 79 typedef struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA; /**< data stored by expression owner (e.g., conshdlr, nlp) in expression */ 80 81 /** callback for freeing ownerdata of expression 82 * 83 * This callback is called while an expression is freed. 84 * The callback shall free the ownerdata, if any. 85 * That is, the callback is also called on expressions that only store this callback, but no ownerdata. 86 * 87 * Note, that the children of the expression have already been released when this callback is called. 88 * The callback must not try to access the expressions children. 89 * 90 * \param[in] scip SCIP main data structure 91 * \param[in] expr the expression which is freed 92 * \param[in] ownerdata the ownerdata stored in the expression 93 */ 94 #define SCIP_DECL_EXPR_OWNERFREE(x) SCIP_RETCODE x(\ 95 SCIP* scip, \ 96 SCIP_EXPR* expr, \ 97 SCIP_EXPR_OWNERDATA** ownerdata) 98 99 /** callback for printing ownerdata of expression 100 * 101 * This callback is called when printing details on an expression, e.g., SCIPdismantleExpr(). 102 * 103 * \param[in] scip SCIP main data structure 104 * \param[in] expr the expression which is printed 105 * \param[in] file file to print to, or NULL for stdout 106 * \param[in] ownerdata the ownerdata stored in the expression 107 */ 108 #define SCIP_DECL_EXPR_OWNERPRINT(x) SCIP_RETCODE x(\ 109 SCIP* scip, \ 110 FILE* file, \ 111 SCIP_EXPR* expr, \ 112 SCIP_EXPR_OWNERDATA* ownerdata) 113 114 /** callback for owner-specific activity evaluation 115 * 116 * This callback is called when evaluating the activity of an expression, e.g., SCIPevalActivity(). 117 * The callback should ensure that activity is updated, if required, by calling SCIPsetActivity(). 118 * The callback can use the activitytag in the expression to recognize whether it needs to become active. 119 * 120 * \param[in] scip SCIP main data structure 121 * \param[in] expr the expression for which activity should be updated 122 * \param[in] ownerdata the ownerdata stored in the expression 123 */ 124 #define SCIP_DECL_EXPR_OWNEREVALACTIVITY(x) SCIP_RETCODE x(\ 125 SCIP* scip, \ 126 SCIP_EXPR* expr, \ 127 SCIP_EXPR_OWNERDATA* ownerdata) 128 129 /** callback for creating ownerdata of expression 130 * 131 * This callback is called when an expression has been created. 132 * It can create data which is then stored in the expression. 133 * 134 * \param[in] scip SCIP main data structure 135 * \param[in] expr the expression that has been created 136 * \param[out] ownerdata buffer to store ownerdata that shall be stored in expression (can be NULL, initialized to NULL) 137 * \param[out] ownerfree buffer to store function to be called to free ownerdata when expression is freed (can be NULL, initialized to NULL) 138 * \param[out] ownerprint buffer to store function to be called to print ownerdata (can be NULL, initialized to NULL) 139 * \param[out] ownerevalactivity buffer to store function to be called to evaluate activity (can be NULL, initialized to NULL) 140 * \param[in] ownercreatedata data that has been passed on by future owner of expression that can be used to create ownerdata 141 */ 142 #define SCIP_DECL_EXPR_OWNERCREATE(x) SCIP_RETCODE x(\ 143 SCIP* scip, \ 144 SCIP_EXPR* expr, \ 145 SCIP_EXPR_OWNERDATA** ownerdata, \ 146 SCIP_DECL_EXPR_OWNERFREE((**ownerfree)), \ 147 SCIP_DECL_EXPR_OWNERPRINT((**ownerprint)), \ 148 SCIP_DECL_EXPR_OWNEREVALACTIVITY((**ownerevalactivity)), \ 149 void* ownercreatedata) 150 151 /** @} */ /* expression owner */ 152 153 /** callback that returns bounds for a given variable as used in interval evaluation 154 * 155 * Implements a relaxation scheme for variable bounds and translates between different infinity values. 156 * Returns an interval that contains the current variable bounds, but might be (slightly) larger. 157 * 158 * \param[in] scip SCIP main data structure 159 * \param[in] var variable for which to obtain bounds 160 * \param[in] intevalvardata data that belongs to this callback 161 */ 162 #define SCIP_DECL_EXPR_INTEVALVAR(x) SCIP_INTERVAL x (\ 163 SCIP* scip, \ 164 SCIP_VAR* var, \ 165 void* intevalvardata \ 166 ) 167 168 /** expression mapping callback for expression copy callback 169 * 170 * The method maps an expression (in a source SCIP instance) to an expression 171 * (in a target SCIP instance) and captures the target expression. 172 * 173 * \param[in] targetscip target SCIP main data structure 174 * \param[out] targetexpr pointer to store the mapped expression, or NULL if expression shall be copied; initialized to NULL 175 * \param[in] sourcescip source SCIP main data structure 176 * \param[in] sourceexpr expression to be mapped 177 * \param[in] ownercreate callback to call when creating a new expression 178 * \param[in] ownercreatedata data for ownercreate callback 179 * \param[in] mapexprdata data of mapexpr callback 180 */ 181 #define SCIP_DECL_EXPR_MAPEXPR(x) SCIP_RETCODE x (\ 182 SCIP* targetscip, \ 183 SCIP_EXPR** targetexpr, \ 184 SCIP* sourcescip, \ 185 SCIP_EXPR* sourceexpr, \ 186 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \ 187 void* ownercreatedata, \ 188 void* mapexprdata) 189 190 /**@name Expression Handler */ 191 /**@{ */ 192 193 typedef struct SCIP_Exprhdlr SCIP_EXPRHDLR; /**< expression handler */ 194 typedef struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA; /**< expression handler data, e.g., SCIP parameter values */ 195 196 /** the maximal number of estimates an expression handler can return in the INITESTIMATES callback */ 197 #define SCIP_EXPR_MAXINITESTIMATES 10 198 199 /** expression handler copy callback 200 * 201 * The method should include the expression handler into a given SCIP instance. 202 * It is usually called when doing a copy of SCIP. 203 * 204 * \param[in] scip target SCIP main data structure where to include expression handler 205 * \param[in] sourceexprhdlr expression handler in source SCIP 206 * 207 * See also \ref EXPRCOPYHDLR. 208 */ 209 #define SCIP_DECL_EXPRCOPYHDLR(x) SCIP_RETCODE x (\ 210 SCIP* scip, \ 211 SCIP_EXPRHDLR* sourceexprhdlr) 212 213 /** expression handler free callback 214 * 215 * Frees the data of an expression handler. 216 * 217 * \param[in] scip SCIP main data structure 218 * \param[in] exprhdlr expression handler 219 * \param[in] exprhdlrdata expression handler data to be freed 220 * 221 * See also \ref EXPRFREEHDLR. 222 */ 223 #define SCIP_DECL_EXPRFREEHDLR(x) SCIP_RETCODE x (\ 224 SCIP* scip, \ 225 SCIP_EXPRHDLR* exprhdlr, \ 226 SCIP_EXPRHDLRDATA** exprhdlrdata) 227 228 /** expression data copy callback 229 * 230 * Copies the data of an expression. 231 * 232 * This method is called when creating copies of an expression within 233 * the same or between different SCIP instances. It is given the 234 * source expression, which data shall be copied. It expects 235 * that *targetexprdata will be set. This data will then be used 236 * to create a new expression. 237 * 238 * This callback must be implemented for expressions that have data. 239 * 240 * \param[in] targetscip target SCIP main data structure 241 * \param[in] targetexprhdlr expression handler in target SCIP 242 * \param[out] targetexprdata pointer to store the copied expression data 243 * \param[in] sourcescip source SCIP main data structure 244 * \param[in] sourceexpr expression in source SCIP which data is to be copied 245 * 246 * See also \ref EXPRCOPYDATA. 247 */ 248 #define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (\ 249 SCIP* targetscip, \ 250 SCIP_EXPRHDLR* targetexprhdlr, \ 251 SCIP_EXPRDATA** targetexprdata, \ 252 SCIP* sourcescip, \ 253 SCIP_EXPR* sourceexpr) 254 255 /** expression data free callback 256 * 257 * Frees the data of an expression. 258 * Shall call SCIPexprSetData(expr, NULL). 259 * 260 * This callback must be implemented for expressions that have data. 261 * 262 * \param[in] scip SCIP main data structure 263 * \param[in] expr the expression which data to be freed 264 * 265 * See also \ref EXPRFREEDATA. 266 */ 267 #define SCIP_DECL_EXPRFREEDATA(x) SCIP_RETCODE x (\ 268 SCIP* scip, \ 269 SCIP_EXPR* expr) 270 271 /** expression print callback 272 * 273 * Prints an expression. 274 * It is called while DFS-iterating over the expression at different stages, that is, 275 * when the expression is visited the first time, before each child of the expression is visited, 276 * after each child of the expression has been visited, and when the iterator leaves the expression 277 * for its parent. See also \ref SCIP_EXPRITER_DFS "expression iteration docu". 278 * 279 * \param[in] scip SCIP main data structure 280 * \param[in] expr expression which data is to be printed 281 * \param[in] stage stage of expression iteration 282 * \param[in] currentchild index of current child if in stage visitingchild or visitedchild 283 * \param[in] parentprecedence precedence of parent 284 * \param[in] file the file to print to 285 * 286 * See also \ref EXPRPRINT. 287 */ 288 #define SCIP_DECL_EXPRPRINT(x) SCIP_RETCODE x (\ 289 SCIP* scip, \ 290 SCIP_EXPR* expr, \ 291 SCIP_EXPRITER_STAGE stage, \ 292 int currentchild, \ 293 unsigned int parentprecedence, \ 294 FILE* file) 295 296 /** expression parse callback 297 * 298 * Parses an expression. 299 * It is called when parsing an expression and an operator with the expr handler name is found. 300 * 301 * \param[in] scip SCIP main data structure 302 * \param[in] string string containing expression to be parse 303 * \param[in] ownercreate function to call to create ownerdata 304 * \param[in] ownercreatedata data to pass to ownercreate 305 * \param[out] endstring buffer to store the position of string after parsing 306 * \param[out] expr buffer to store the parsed expression 307 * \param[out] success buffer to store whether the parsing was successful or not 308 * 309 * See also \ref EXPRPARSE. 310 */ 311 #define SCIP_DECL_EXPRPARSE(x) SCIP_RETCODE x (\ 312 SCIP* scip, \ 313 SCIP_EXPRHDLR* exprhdlr, \ 314 const char* string, \ 315 const char** endstring, \ 316 SCIP_EXPR** expr, \ 317 SCIP_Bool* success, \ 318 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \ 319 void* ownercreatedata) 320 321 /** expression curvature detection callback 322 * 323 * The method returns whether an expression can have a desired curvature under conditions on the 324 * curvature of the children. 325 * That is, the method shall return TRUE in success and requirements on the curvature for each child 326 * which will suffice for this expression to be convex (or concave, or linear, as specified by caller) 327 * w.r.t. the current activities of all children. 328 * It can return "unknown" for a child's curvature if its curvature does not matter (though that's 329 * rarely the case). 330 * 331 * \param[in] scip SCIP main data structure 332 * \param[in] expr expression to check the curvature for 333 * \param[in] exprcurvature desired curvature of this expression 334 * \param[out] success buffer to store whether the desired curvature was obtained 335 * \param[out] childcurv array to store required curvature for each child 336 * 337 * See also \ref EXPRCURVATURE. 338 */ 339 #define SCIP_DECL_EXPRCURVATURE(x) SCIP_RETCODE x (\ 340 SCIP* scip, \ 341 SCIP_EXPR* expr, \ 342 SCIP_EXPRCURV exprcurvature, \ 343 SCIP_Bool* success, \ 344 SCIP_EXPRCURV* childcurv) 345 346 /** expression monotonicity detection callback 347 * 348 * The method computes the monotonicity of an expression with respect to a given child. 349 * 350 * \param[in] scip SCIP main data structure 351 * \param[in] expr expression to check the monotonicity for 352 * \param[in] childidx index of the considered child expression 353 * \param[out] result buffer to store the monotonicity 354 * 355 * See also \ref EXPRMONOTONICITY. 356 */ 357 #define SCIP_DECL_EXPRMONOTONICITY(x) SCIP_RETCODE x (\ 358 SCIP* scip, \ 359 SCIP_EXPR* expr, \ 360 int childidx, \ 361 SCIP_MONOTONE* result) 362 363 /** expression integrality detection callback 364 * 365 * The method checks whether an expression evaluates always to an integral value in a feasible solution. 366 * Usually uses SCIPexprIsIntegral() to check whether children evaluate to an integral value. 367 * 368 * \param[in] scip SCIP main data structure 369 * \param[in] expr expression to check the integrality for 370 * \param[out] isintegral buffer to store whether expr is integral 371 * 372 * See also \ref EXPRINTEGRALITY. 373 */ 374 #define SCIP_DECL_EXPRINTEGRALITY(x) SCIP_RETCODE x (\ 375 SCIP* scip, \ 376 SCIP_EXPR* expr, \ 377 SCIP_Bool* isintegral) 378 379 /** expression hash callback 380 * 381 * The method hashes an expression by taking the hashes of its children into account. 382 * 383 * \param[in] scip SCIP main data structure 384 * \param[in] expr expression to be hashed 385 * \param[out] hashkey buffer to store the hash value 386 * \param[in] childrenhashes array with hash values of children 387 * 388 * See also \ref EXPRHASH. 389 */ 390 #define SCIP_DECL_EXPRHASH(x) SCIP_RETCODE x (\ 391 SCIP* scip, \ 392 SCIP_EXPR* expr, \ 393 unsigned int* hashkey, \ 394 unsigned int* childrenhashes) 395 396 /** expression compare callback 397 * 398 * the method receives two expressions, expr1 and expr2. Must return 399 * -1 if expr1 < expr2, or 400 * 0 if expr1 = expr2, or 401 * 1 if expr1 > expr2. 402 * 403 * \param[in] scip SCIP main data structure 404 * \param[in] expr1 first expression in comparison 405 * \param[in] expr2 second expression in comparison 406 * 407 * See also \ref EXPRCOMPARE. 408 */ 409 #define SCIP_DECL_EXPRCOMPARE(x) int x (\ 410 SCIP* scip, \ 411 SCIP_EXPR* expr1, \ 412 SCIP_EXPR* expr2) 413 414 /** expression (point-) evaluation callback 415 * 416 * The method evaluates an expression by taking the values of its children into account. 417 * 418 * \param[in] scip SCIP main data structure 419 * \param[in] expr expression to be evaluated 420 * \param[out] val buffer where to store value 421 * \param[in] sol solution that is evaluated (can be NULL) 422 * 423 * See also \ref EXPREVAL. 424 */ 425 #define SCIP_DECL_EXPREVAL(x) SCIP_RETCODE x (\ 426 SCIP* scip, \ 427 SCIP_EXPR* expr, \ 428 SCIP_Real* val, \ 429 SCIP_SOL* sol) 430 431 /** backward derivative evaluation callback 432 * 433 * The method should compute the partial derivative of expr w.r.t. its child at childidx. 434 * That is, it should return 435 * \f[ 436 * \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}} 437 * \f] 438 * 439 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details. 440 * 441 * \param[in] scip SCIP main data structure 442 * \param[in] expr expression to be differentiated 443 * \param[in] childidx index of the child 444 * \param[out] val buffer to store the partial derivative w.r.t. the childidx-th children 445 * 446 * See also \ref EXPRBWDIFF. 447 */ 448 #define SCIP_DECL_EXPRBWDIFF(x) SCIP_RETCODE x (\ 449 SCIP* scip, \ 450 SCIP_EXPR* expr, \ 451 int childidx, \ 452 SCIP_Real* val) 453 454 /** forward derivative evaluation callback 455 * 456 * The method should evaluate the directional derivative of expr. 457 * The expr should be interpreted as an operator \f$ \text{expr}(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$ 458 * are the children of the expr. 459 * The directional derivative is evaluated at the point 460 * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$ 461 * in the direction given by direction. 462 * 463 * This method should return 464 * \f[ 465 * \sum_{i = 1}^n \frac{\partial \text{expr}}{\partial c_i} D_u c_i, 466 * \f] 467 * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child, 468 * which can be accessed via SCIPexprGetDot(). 469 * 470 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details. 471 * 472 * \param[in] scip SCIP main data structure 473 * \param[in] expr expression to be differentiated 474 * \param[out] dot buffer to store derivative value 475 * \param[in] direction direction of the derivative (useful only for var expressions) 476 * 477 * See also \ref EXPRFWDIFF. 478 */ 479 #define SCIP_DECL_EXPRFWDIFF(x) SCIP_RETCODE x (\ 480 SCIP* scip, \ 481 SCIP_EXPR* expr, \ 482 SCIP_Real* dot, \ 483 SCIP_SOL* direction) 484 485 /** derivative evaluation callback for Hessian directions (backward over forward) 486 * 487 * The method computes the total derivative, w.r.t. its children, of the partial derivative of expr w.r.t. childidx. 488 * Equivalently, it computes the partial derivative w.r.t. childidx of the total derivative. 489 * 490 * The expr should be interpreted as an operator \f$ \text{expr}(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$ 491 * are the children of the expr. 492 * The directional derivative is evaluated at the point 493 * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$ 494 * in the direction given by direction. 495 * 496 * This method should return 497 * \f[ 498 * \sum_{i = 1}^n \frac{\partial^2 \text{expr}}{\partial c_i} \partial c_{\text{childidx}} D_u c_i, 499 * \f] 500 * 501 * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child, 502 * which can be accessed via SCIPexprGetDot(). 503 * 504 * Thus, if \f$ n = 1 \f$ (i.e. if expr represents an univariate operator), the method should return 505 * \f[ 506 * \text{expr}^{\prime \prime}(\text{SCIPexprGetEvalValue}(c)) D_u c. 507 * \f] 508 * 509 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details. 510 * 511 * \param[in] scip SCIP main data structure 512 * \param[in] expr expression to be evaluated 513 * \param[in] childidx index of the child 514 * \param[out] bardot buffer to store derivative value 515 * \param[in] direction direction of the derivative (useful only for var expressions) 516 * 517 * See also \ref EXPRBWFWDIFF. 518 */ 519 #define SCIP_DECL_EXPRBWFWDIFF(x) SCIP_RETCODE x (\ 520 SCIP* scip, \ 521 SCIP_EXPR* expr, \ 522 int childidx, \ 523 SCIP_Real* bardot, \ 524 SCIP_SOL* direction) 525 526 /** expression (interval-) evaluation callback 527 * 528 * The method evaluates an expression by taking the intervals of its children into account. 529 * 530 * \param[in] scip SCIP main data structure 531 * \param[in] expr expression to be evaluated 532 * \param[out] interval buffer where to store interval 533 * \param[in] intevalvar callback to be called when interval evaluating a variable 534 * \param[in] intevalvardata data to be passed to intevalvar callback 535 * 536 * See also \ref EXPRINTEVAL. 537 */ 538 #define SCIP_DECL_EXPRINTEVAL(x) SCIP_RETCODE x (\ 539 SCIP* scip, \ 540 SCIP_EXPR* expr, \ 541 SCIP_INTERVAL* interval, \ 542 SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), \ 543 void* intevalvardata) 544 545 /** expression under/overestimation callback 546 * 547 * The method tries to compute a linear under- or overestimator that is as tight as possible 548 * at a given point. The estimator must be valid w.r.t. the bounds given by localbounds. 549 * If the value of the estimator in the reference point is smaller (larger) than targetvalue 550 * when underestimating (overestimating), then no estimator needs to be computed. 551 * Note, that targetvalue can be infinite if any estimator will be accepted. 552 * If successful, it shall store the coefficient of the i-th child in entry coefs[i] and 553 * the constant part in constant. 554 * If the estimator is also valid w.r.t. the bounds given by globalbounds, then *islocal shall 555 * be set to FALSE. 556 * The callback shall indicate in branchcand[i] whether branching on the i-th child would improve 557 * the estimator. It can be assumed that branchcand[i] has been initialized to TRUE for all children. 558 * 559 * \param[in] scip SCIP main data structure 560 * \param[in] expr expression 561 * \param[in] localbounds current bounds for children 562 * \param[in] globalbounds global bounds for children 563 * \param[in] refpoint values for children in the reference point where to estimate 564 * \param[in] overestimate whether the expression needs to be over- or underestimated 565 * \param[in] targetvalue a value that the estimator shall exceed, can be +/-infinity 566 * \param[out] coefs array to store coefficients of estimator 567 * \param[out] constant buffer to store constant part of estimator 568 * \param[out] islocal buffer to store whether estimator is valid locally only 569 * \param[out] success buffer to indicate whether an estimator could be computed 570 * \param[out] branchcand array to indicate which children to consider for branching 571 * 572 * See also \ref EXPRESTIMATE. 573 */ 574 #define SCIP_DECL_EXPRESTIMATE(x) SCIP_RETCODE x (\ 575 SCIP* scip, \ 576 SCIP_EXPR* expr, \ 577 SCIP_INTERVAL* localbounds, \ 578 SCIP_INTERVAL* globalbounds, \ 579 SCIP_Real* refpoint, \ 580 SCIP_Bool overestimate, \ 581 SCIP_Real targetvalue, \ 582 SCIP_Real* coefs, \ 583 SCIP_Real* constant, \ 584 SCIP_Bool* islocal, \ 585 SCIP_Bool* success, \ 586 SCIP_Bool* branchcand) 587 588 /** expression initial under/overestimation callback 589 * 590 * The method tries to compute a few linear under- or overestimator that approximate the 591 * behavior of the expression. The estimator must be valid w.r.t. the bounds given by bounds. 592 * These estimators may be used to initialize a linear relaxation. 593 * The callback shall return the number of computed estimators in nreturned, 594 * store the coefficient of the i-th child for the j-th estimator in entry coefs[j][i], 595 * and store the constant part for the j-th estimator in constant[j]. 596 * 597 * \param[in] scip SCIP main data structure 598 * \param[in] expr expression 599 * \param[in] bounds bounds for children 600 * \param[in] overestimate whether the expression shall be overestimated or underestimated 601 * \param[out] coefs buffer to store coefficients of computed estimators 602 * \param[out] constant buffer to store constant of computed estimators 603 * \param[out] nreturned buffer to store number of estimators that have been computed 604 * 605 * See also \ref EXPRINITESTIMATES. 606 */ 607 #define SCIP_DECL_EXPRINITESTIMATES(x) SCIP_RETCODE x ( \ 608 SCIP* scip, \ 609 SCIP_EXPR* expr, \ 610 SCIP_INTERVAL* bounds, \ 611 SCIP_Bool overestimate, \ 612 SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES], \ 613 SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES], \ 614 int* nreturned) 615 616 /** expression simplify callback 617 * 618 * The method shall try to simplify an expression by applying algebraic transformations 619 * and return the simplified expression. 620 * It can assume that children have been simplified. 621 * If no simplification is possible, then shall set *simplifiedexpr to expr and capture *simplifiedexpr. 622 * 623 * \param[in] scip SCIP main data structure 624 * \param[in] expr expression to simplify 625 * \param[in] ownercreate function to call to create ownerdata 626 * \param[in] ownercreatedata data to pass to ownercreate 627 * \param[out] simplifiedexpr buffer to store the simplified expression 628 * 629 * See also \ref EXPRSIMPLIFY and SCIPsimplifyExpr(). 630 */ 631 #define SCIP_DECL_EXPRSIMPLIFY(x) SCIP_RETCODE x (\ 632 SCIP* scip, \ 633 SCIP_EXPR* expr, \ 634 SCIP_EXPR** simplifiedexpr, \ 635 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \ 636 void* ownercreatedata) 637 638 /** expression callback for reverse propagation 639 * 640 * The method propagates given bounds over the children of an expression. 641 * Shall compute an interval overestimate on 642 * \f[ 643 * \{ x_i : \text{expr}(c_1,\ldots,c_{i-1},x_i,c_{i+1},\ldots,c_n) \in \text{bounds} \} 644 * \f] 645 * for each child i and store it in childrenbounds[i]. 646 * The initial intervals \f$c_i, i=1,\ldots,n,\f$ are given by childrenbounds, too. 647 * 648 * \param[in] scip SCIP main data structure 649 * \param[in] expr expression 650 * \param[in] bounds the bounds on the expression that should be propagated 651 * \param[in,out] childrenbounds array to store computed bounds for children, initialized with current activity 652 * \param[out] infeasible buffer to store whether a children bounds were propagated to an empty interval 653 * 654 * See also \ref EXPRREVERSEPROP. 655 */ 656 #define SCIP_DECL_EXPRREVERSEPROP(x) SCIP_RETCODE x (\ 657 SCIP* scip, \ 658 SCIP_EXPR* expr, \ 659 SCIP_INTERVAL bounds, \ 660 SCIP_INTERVAL* childrenbounds, \ 661 SCIP_Bool* infeasible) 662 663 /** expression callback to get information for symmetry detection 664 * 665 * The method returns information regarding constants and coefficients used in an expression. 666 * 667 * \param[in] scip SCIP main data structure 668 * \param[in] expr expression to retrieve information from 669 * \param[out] exprdata buffer to store retrieved data 670 */ 671 #define SCIP_DECL_EXPRGETSYMDATA(x) SCIP_RETCODE x (\ 672 SCIP* scip, \ 673 SCIP_EXPR* expr, \ 674 SYM_EXPRDATA** symdata) 675 676 /** @} */ /* expression handler */ 677 678 679 680 /** @name Expression iterator 681 * @{ 682 */ 683 684 /** maximal number of iterators that can be active on an expression graph concurrently 685 * 686 * How often an expression graph iteration can be started within an active iteration, plus one. 687 */ 688 #define SCIP_EXPRITER_MAXNACTIVE 5 689 690 /* stages of expression DFS iteration */ 691 #define SCIP_EXPRITER_ENTEREXPR 1u /**< an expression is visited the first time (before any of its children are visited) */ 692 #define SCIP_EXPRITER_VISITINGCHILD 2u /**< a child of an expression is to be visited */ 693 #define SCIP_EXPRITER_VISITEDCHILD 4u /**< a child of an expression has been visited */ 694 #define SCIP_EXPRITER_LEAVEEXPR 8u /**< an expression is to be left (all of its children have been processed) */ 695 #define SCIP_EXPRITER_ALLSTAGES (SCIP_EXPRITER_ENTEREXPR | SCIP_EXPRITER_VISITINGCHILD | SCIP_EXPRITER_VISITEDCHILD | SCIP_EXPRITER_LEAVEEXPR) 696 697 /** stage of DFS iterator */ 698 typedef unsigned int SCIP_EXPRITER_STAGE; 699 700 /** user data storage type for expression iteration */ 701 typedef union 702 { 703 SCIP_Real realval; /**< a floating-point value */ 704 int intval; /**< an integer value */ 705 int intvals[2]; /**< two integer values */ 706 unsigned int uintval; /**< an unsigned integer value */ 707 void* ptrval; /**< a pointer */ 708 } SCIP_EXPRITER_USERDATA; 709 710 /** mode for expression iterator */ 711 typedef enum 712 { 713 SCIP_EXPRITER_RTOPOLOGIC, /**< reverse topological order */ 714 SCIP_EXPRITER_BFS, /**< breadth-first search */ 715 SCIP_EXPRITER_DFS /**< depth-first search */ 716 } SCIP_EXPRITER_TYPE; 717 718 typedef struct SCIP_ExprIterData SCIP_EXPRITERDATA; /**< expression iterator data of a specific expression */ 719 typedef struct SCIP_ExprIter SCIP_EXPRITER; /**< expression iterator */ 720 721 /** @} */ /* expression iterator */ 722 723 /** @name Expression printing 724 * @{ 725 */ 726 727 #define SCIP_EXPRPRINT_EXPRSTRING 0x1u /**< print the math. function that the expression represents (e.g., "c0+c1") */ 728 #define SCIP_EXPRPRINT_EXPRHDLR 0x2u /**< print expression handler name */ 729 #define SCIP_EXPRPRINT_NUSES 0x4u /**< print number of uses (reference counting) */ 730 #define SCIP_EXPRPRINT_EVALVALUE 0x8u /**< print evaluation value */ 731 #define SCIP_EXPRPRINT_EVALTAG 0x18u /**< print evaluation value and tag */ 732 #define SCIP_EXPRPRINT_ACTIVITY 0x20u /**< print activity value */ 733 #define SCIP_EXPRPRINT_ACTIVITYTAG 0x60u /**< print activity value and corresponding tag */ 734 #define SCIP_EXPRPRINT_OWNER 0x80u /**< print ownerdata */ 735 736 /** print everything */ 737 #define SCIP_EXPRPRINT_ALL SCIP_EXPRPRINT_EXPRSTRING | SCIP_EXPRPRINT_EXPRHDLR | SCIP_EXPRPRINT_NUSES | SCIP_EXPRPRINT_EVALTAG | SCIP_EXPRPRINT_ACTIVITYTAG | SCIP_EXPRPRINT_OWNER 738 739 typedef unsigned int SCIP_EXPRPRINT_WHAT; /**< exprprint bitflags */ 740 typedef struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA; /**< data when printing an expression */ 741 742 /** @} */ 743 744 745 #endif /* SCIP_TYPE_EXPR_H_ */ 746