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 scip_expr.h 26 * @ingroup PUBLICCOREAPI 27 * @brief public functions to work with algebraic expressions 28 * @author Ksenia Bestuzheva 29 * @author Benjamin Mueller 30 * @author Felipe Serrano 31 * @author Stefan Vigerske 32 */ 33 34 #ifndef SCIP_SCIP_EXPR_H_ 35 #define SCIP_SCIP_EXPR_H_ 36 37 #include "scip/type_scip.h" 38 #include "scip/type_expr.h" 39 #include "scip/type_misc.h" 40 41 #ifdef NDEBUG 42 #include "scip/struct_scip.h" 43 #include "scip/struct_set.h" 44 #include "scip/struct_mem.h" 45 #include "scip/struct_stat.h" 46 #include "scip/set.h" 47 #include "scip/expr.h" 48 #endif 49 50 #ifdef __cplusplus 51 extern "C" { 52 #endif 53 54 /**@addtogroup PublicExprHandlerMethods 55 * @{ 56 */ 57 58 /** creates the handler for an expression handler and includes it into SCIP */ 59 SCIP_EXPORT 60 SCIP_RETCODE SCIPincludeExprhdlr( 61 SCIP* scip, /**< SCIP data structure */ 62 SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */ 63 const char* name, /**< name of expression handler (must not be NULL) */ 64 const char* desc, /**< description of expression handler (can be NULL) */ 65 unsigned int precedence, /**< precedence of expression operation (used for printing) */ 66 SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */ 67 SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */ 68 ); 69 70 /** gives expression handlers */ 71 SCIP_EXPORT 72 SCIP_EXPRHDLR** SCIPgetExprhdlrs( 73 SCIP* scip /**< SCIP data structure */ 74 ); 75 76 /** gives number of expression handlers */ 77 SCIP_EXPORT 78 int SCIPgetNExprhdlrs( 79 SCIP* scip /**< SCIP data structure */ 80 ); 81 82 /** returns an expression handler of a given name (or NULL if not found) */ 83 SCIP_EXPORT 84 SCIP_EXPRHDLR* SCIPfindExprhdlr( 85 SCIP* scip, /**< SCIP data structure */ 86 const char* name /**< name of expression handler */ 87 ); 88 89 /** returns expression handler for variable expressions (or NULL if not included) */ 90 SCIP_EXPORT 91 SCIP_EXPRHDLR* SCIPgetExprhdlrVar( 92 SCIP* scip /**< SCIP data structure */ 93 ); 94 95 /** returns expression handler for constant value expressions (or NULL if not included) */ 96 SCIP_EXPORT 97 SCIP_EXPRHDLR* SCIPgetExprhdlrValue( 98 SCIP* scip /**< SCIP data structure */ 99 ); 100 101 /** returns expression handler for sum expressions (or NULL if not included) */ 102 SCIP_EXPORT 103 SCIP_EXPRHDLR* SCIPgetExprhdlrSum( 104 SCIP* scip /**< SCIP data structure */ 105 ); 106 107 /** returns expression handler for product expressions (or NULL if not included) */ 108 SCIP_EXPORT 109 SCIP_EXPRHDLR* SCIPgetExprhdlrProduct( 110 SCIP* scip /**< SCIP data structure */ 111 ); 112 113 /** returns expression handler for power expressions (or NULL if not included) */ 114 SCIP_EXPORT 115 SCIP_EXPRHDLR* SCIPgetExprhdlrPower( 116 SCIP* scip /**< SCIP data structure */ 117 ); 118 119 #ifdef NDEBUG 120 /* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and 121 * speed up the algorithms. 122 */ 123 #define SCIPgetExprhdlrs(scip) (scip)->set->exprhdlrs 124 #define SCIPgetNExprhdlrs(scip) (scip)->set->nexprhdlrs 125 #define SCIPfindExprhdlr(scip, name) SCIPsetFindExprhdlr((scip)->set, name) 126 #define SCIPgetExprhdlrVar(scip) (scip)->set->exprhdlrvar 127 #define SCIPgetExprhdlrValue(scip) (scip)->set->exprhdlrval 128 #define SCIPgetExprhdlrSum(scip) (scip)->set->exprhdlrsum 129 #define SCIPgetExprhdlrProduct(scip) (scip)->set->exprhdlrproduct 130 #define SCIPgetExprhdlrPower(scip) (scip)->set->exprhdlrpow 131 #endif 132 133 /** @} */ 134 135 /**@addtogroup PublicExprMethods 136 * @{ 137 */ 138 139 /**@name Expressions */ 140 /**@{ */ 141 142 /** creates and captures an expression with given expression data and children */ 143 SCIP_EXPORT 144 SCIP_RETCODE SCIPcreateExpr( 145 SCIP* scip, /**< SCIP data structure */ 146 SCIP_EXPR** expr, /**< pointer where to store expression */ 147 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 148 SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */ 149 int nchildren, /**< number of children */ 150 SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */ 151 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 152 void* ownercreatedata /**< data to pass to ownercreate */ 153 ); 154 155 /** creates and captures an expression with given expression data and up to two children */ 156 SCIP_EXPORT 157 SCIP_RETCODE SCIPcreateExpr2( 158 SCIP* scip, /**< SCIP data structure */ 159 SCIP_EXPR** expr, /**< pointer where to store expression */ 160 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 161 SCIP_EXPRDATA* exprdata, /**< expression data */ 162 SCIP_EXPR* child1, /**< first child (can be NULL) */ 163 SCIP_EXPR* child2, /**< second child (can be NULL) */ 164 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 165 void* ownercreatedata /**< data to pass to ownercreate */ 166 ); 167 168 /** creates and captures an expression representing a quadratic function */ 169 SCIP_EXPORT 170 SCIP_RETCODE SCIPcreateExprQuadratic( 171 SCIP* scip, /**< SCIP data structure */ 172 SCIP_EXPR** expr, /**< pointer where to store expression */ 173 int nlinvars, /**< number of linear terms */ 174 SCIP_VAR** linvars, /**< array with variables in linear part */ 175 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part */ 176 int nquadterms, /**< number of quadratic terms */ 177 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms */ 178 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms */ 179 SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms */ 180 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 181 void* ownercreatedata /**< data to pass to ownercreate */ 182 ); 183 184 /** creates and captures an expression representing a monomial 185 * 186 * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents. 187 * So this function actually creates an expression for a signomial that has exactly one term. 188 */ 189 SCIP_EXPORT 190 SCIP_RETCODE SCIPcreateExprMonomial( 191 SCIP* scip, /**< SCIP data structure */ 192 SCIP_EXPR** expr, /**< pointer where to store expression */ 193 int nfactors, /**< number of factors in monomial */ 194 SCIP_VAR** vars, /**< variables in the monomial */ 195 SCIP_Real* exponents, /**< exponent in each factor, or NULL if all 1.0 */ 196 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 197 void* ownercreatedata /**< data to pass to ownercreate */ 198 ); 199 200 /** appends child to the children list of expr 201 * 202 * @attention Only use if you really know what you are doing. The expression handler of the expression needs to be able to handle an increase in the number of children. 203 */ 204 SCIP_EXPORT 205 SCIP_RETCODE SCIPappendExprChild( 206 SCIP* scip, /**< SCIP data structure */ 207 SCIP_EXPR* expr, /**< expression */ 208 SCIP_EXPR* child /**< expression to be appended */ 209 ); 210 211 /** overwrites/replaces a child of an expressions 212 * 213 * The old child is released and the newchild is captured, unless they are the same (=same pointer). 214 */ 215 SCIP_EXPORT 216 SCIP_RETCODE SCIPreplaceExprChild( 217 SCIP* scip, /**< SCIP data structure */ 218 SCIP_EXPR* expr, /**< expression which is going to replace a child */ 219 int childidx, /**< index of child being replaced */ 220 SCIP_EXPR* newchild /**< the new child */ 221 ); 222 223 /** remove all children of expr 224 * 225 * @attention Only use if you really know what you are doing. The expression handler of the expression needs to be able to handle the removal of all children. 226 */ 227 SCIP_EXPORT 228 SCIP_RETCODE SCIPremoveExprChildren( 229 SCIP* scip, /**< SCIP data structure */ 230 SCIP_EXPR* expr /**< expression */ 231 ); 232 233 /** duplicates the given expression and its children */ 234 SCIP_EXPORT 235 SCIP_RETCODE SCIPduplicateExpr( 236 SCIP* scip, /**< SCIP data structure */ 237 SCIP_EXPR* expr, /**< original expression */ 238 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */ 239 SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */ 240 void* mapexprdata, /**< data of expression mapping function */ 241 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 242 void* ownercreatedata /**< data to pass to ownercreate */ 243 ); 244 245 /** duplicates the given expression, but reuses its children */ 246 SCIP_EXPORT 247 SCIP_RETCODE SCIPduplicateExprShallow( 248 SCIP* scip, /**< SCIP data structure */ 249 SCIP_EXPR* expr, /**< original expression */ 250 SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */ 251 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 252 void* ownercreatedata /**< data to pass to ownercreate */ 253 ); 254 255 /** copies an expression including children to use in a (possibly different) SCIP instance */ 256 SCIP_EXPORT 257 SCIP_RETCODE SCIPcopyExpr( 258 SCIP* sourcescip, /**< source SCIP data structure */ 259 SCIP* targetscip, /**< target SCIP data structure */ 260 SCIP_EXPR* expr, /**< original expression */ 261 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */ 262 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 263 void* ownercreatedata, /**< data to pass to ownercreate */ 264 SCIP_HASHMAP* varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding 265 * variables of the target SCIP, or NULL */ 266 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding 267 * target constraints, or NULL */ 268 SCIP_Bool global, /**< create a global or a local copy? */ 269 SCIP_Bool* valid /**< pointer to store whether all checked or enforced constraints were validly copied */ 270 ); 271 272 /** creates an expression from a string 273 * 274 * We specify the grammar that defines the syntax of an expression. 275 * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power, 276 * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`. 277 * 278 * The actual definition: 279 * <pre> 280 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term } 281 * Term -> Factor { ("*" | "/" ) Factor } 282 * Factor -> Base [ "^" "number" | "^(" "number" ")" ] 283 * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ") 284 * </pre> 285 * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`. 286 * 287 * Note that `Op` and `OpExpression` are undefined. 288 * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method). 289 */ 290 SCIP_EXPORT 291 SCIP_RETCODE SCIPparseExpr( 292 SCIP* scip, /**< SCIP data structure */ 293 SCIP_EXPR** expr, /**< pointer to store the expr parsed */ 294 const char* exprstr, /**< string with the expr to parse */ 295 const char** finalpos, /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */ 296 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 297 void* ownercreatedata /**< data to pass to ownercreate */ 298 ); 299 300 /** captures an expression (increments usage count) */ 301 SCIP_EXPORT 302 void SCIPcaptureExpr( 303 SCIP_EXPR* expr /**< expression to be captured */ 304 ); 305 306 /** releases an expression (decrements usage count and possibly frees expression) */ 307 SCIP_EXPORT 308 SCIP_RETCODE SCIPreleaseExpr( 309 SCIP* scip, /**< SCIP data structure */ 310 SCIP_EXPR** expr /**< pointer to expression to be released */ 311 ); 312 313 /** returns whether an expression is a variable expression */ 314 SCIP_EXPORT 315 SCIP_Bool SCIPisExprVar( 316 SCIP* scip, /**< SCIP data structure */ 317 SCIP_EXPR* expr /**< expression */ 318 ); 319 320 /** returns whether an expression is a value expression */ 321 SCIP_EXPORT 322 SCIP_Bool SCIPisExprValue( 323 SCIP* scip, /**< SCIP data structure */ 324 SCIP_EXPR* expr /**< expression */ 325 ); 326 327 /** returns whether an expression is a sum expression */ 328 SCIP_EXPORT 329 SCIP_Bool SCIPisExprSum( 330 SCIP* scip, /**< SCIP data structure */ 331 SCIP_EXPR* expr /**< expression */ 332 ); 333 334 /** returns whether an expression is a product expression */ 335 SCIP_EXPORT 336 SCIP_Bool SCIPisExprProduct( 337 SCIP* scip, /**< SCIP data structure */ 338 SCIP_EXPR* expr /**< expression */ 339 ); 340 341 /** returns whether an expression is a power expression */ 342 SCIP_EXPORT 343 SCIP_Bool SCIPisExprPower( 344 SCIP* scip, /**< SCIP data structure */ 345 SCIP_EXPR* expr /**< expression */ 346 ); 347 348 /** print an expression as info-message */ 349 SCIP_EXPORT 350 SCIP_RETCODE SCIPprintExpr( 351 SCIP* scip, /**< SCIP data structure */ 352 SCIP_EXPR* expr, /**< expression to be printed */ 353 FILE* file /**< file to print to, or NULL for stdout */ 354 ); 355 356 /** initializes printing of expressions in dot format to a give FILE* pointer */ 357 SCIP_EXPORT 358 SCIP_RETCODE SCIPprintExprDotInit( 359 SCIP* scip, /**< SCIP data structure */ 360 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */ 361 FILE* file, /**< file to print to, or NULL for stdout */ 362 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */ 363 ); 364 365 /** initializes printing of expressions in dot format to a file with given filename */ 366 SCIP_EXPORT 367 SCIP_RETCODE SCIPprintExprDotInit2( 368 SCIP* scip, /**< SCIP data structure */ 369 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */ 370 const char* filename, /**< name of file to print to */ 371 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */ 372 ); 373 374 /** main part of printing an expression in dot format */ 375 SCIP_EXPORT 376 SCIP_RETCODE SCIPprintExprDot( 377 SCIP* scip, /**< SCIP data structure */ 378 SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */ 379 SCIP_EXPR* expr /**< expression to be printed */ 380 ); 381 382 /** finishes printing of expressions in dot format */ 383 SCIP_EXPORT 384 SCIP_RETCODE SCIPprintExprDotFinal( 385 SCIP* scip, /**< SCIP data structure */ 386 SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */ 387 ); 388 389 /** shows a single expression by use of dot and gv 390 * 391 * This function is meant for debugging purposes. 392 * It's signature is kept as simple as possible to make it 393 * easily callable from gdb, for example. 394 * 395 * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file, then calls ghostview (gv) to show the file. 396 * SCIP will hold until ghostscript is closed. 397 */ 398 SCIP_EXPORT 399 SCIP_RETCODE SCIPshowExpr( 400 SCIP* scip, /**< SCIP data structure */ 401 SCIP_EXPR* expr /**< expression to be printed */ 402 ); 403 404 /** prints structure of an expression a la Maple's dismantle */ 405 SCIP_EXPORT 406 SCIP_RETCODE SCIPdismantleExpr( 407 SCIP* scip, /**< SCIP data structure */ 408 FILE* file, /**< file to print to, or NULL for stdout */ 409 SCIP_EXPR* expr /**< expression to dismantle */ 410 ); 411 412 /** evaluate an expression in a point 413 * 414 * Iterates over expressions to also evaluate children, if necessary. 415 * Value can be received via SCIPexprGetEvalValue(). 416 * If an evaluation error (division by zero, ...) occurs, this value will 417 * be set to SCIP_INVALID. 418 * 419 * If a nonzero \p soltag is passed, then only (sub)expressions are 420 * reevaluated that have a different solution tag. If a soltag of 0 421 * is passed, then subexpressions are always reevaluated. 422 * The tag is stored together with the value and can be received via 423 * SCIPexprGetEvalTag(). 424 */ 425 SCIP_EXPORT 426 SCIP_RETCODE SCIPevalExpr( 427 SCIP* scip, /**< SCIP data structure */ 428 SCIP_EXPR* expr, /**< expression to be evaluated */ 429 SCIP_SOL* sol, /**< solution to be evaluated */ 430 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */ 431 ); 432 433 /** returns a previously unused solution tag for expression evaluation */ 434 SCIP_EXPORT 435 SCIP_Longint SCIPgetExprNewSoltag( 436 SCIP* scip /**< SCIP data structure */ 437 ); 438 439 /**@} */ 440 441 /** @name Differentiation 442 * @anchor SCIP_EXPR_DIFF 443 * 444 * @par Gradients (Automatic differentiation Backward mode) 445 * 446 * Given a function, say, \f$f(s(x,y),t(x,y))\f$ there is a common mnemonic technique to compute its partial derivatives, using a tree diagram. 447 * Suppose we want to compute the partial derivative of \f$f\f$ w.r.t. \f$x\f$. 448 * Write the function as a tree: 449 * 450 * f 451 * |-----| 452 * s t 453 * |--| |--| 454 * x y x y 455 * 456 * The weight of an edge between two nodes represents the partial derivative of the parent w.r.t. the children, e.g., 457 * 458 * f 459 * | 460 * s 461 * 462 * is \f$ \partial_sf \f$. 463 * The weight of a path is the product of the weight of the edges in the path. 464 * The partial derivative of \f$f\f$ w.r.t. \f$x\f$ is then the sum of the weights of all paths connecting \f$f\f$ with \f$x\f$: 465 * \f[ \frac{\partial f}{\partial x} = \partial_s f \cdot \partial_x s + \partial_t f \cdot \partial_x t. \f] 466 * 467 * We follow this method in order to compute the gradient of an expression (root) at a given point (point). 468 * Note that an expression is a DAG representation of a function, but there is a 1-1 correspondence between paths 469 * in the DAG and path in a tree diagram of a function. 470 * Initially, we set `root->derivative` to 1.0. 471 * Then, traversing the tree in Depth First (see \ref SCIPexpriterInit), for every expr that *has* children, 472 * we store in its i-th child, `child[i]->derivative`, the derivative of expr w.r.t. child evaluated at point multiplied with `expr->derivative`. 473 * 474 * For example: 475 * 1. `f->derivative` = 1.0 476 * 2. `s->derivative` = \f$\partial_s f \,\cdot\f$ `f->derivative` = \f$\partial_s f\f$ 477 * 3. `x->derivative` = \f$\partial_x s \,\cdot\f$ `s->derivative` = \f$\partial_x s \cdot \partial_s f\f$ 478 * 479 * However, when the child is a variable expressions, we actually need to initialize `child->derivative` to 0.0 480 * and afterwards add, instead of overwrite the computed value. 481 * The complete example would then be: 482 * 483 * 1. `f->derivative` = 1.0, `x->derivative` = 0.0, `y->derivative` = 0.0 484 * 2. `s->derivative` = \f$\partial_s f \,\cdot\f$ `f->derivative` = \f$\partial_s f\f$ 485 * 3. `x->derivative` += \f$\partial_x s \,\cdot\f$ `s->derivative` = \f$\partial_x s \cdot \partial_s f\f$ 486 * 4. `y->derivative` += \f$\partial_y s \,\cdot\f$ `s->derivative` = \f$\partial_y s \cdot \partial_s f\f$ 487 * 5. `t->derivative` = \f$\partial_t f \,\cdot\f$ `f->derivative` = \f$\partial_t f\f$ 488 * 6. `x->derivative` += \f$\partial_x t \,\cdot\f$ `t->derivative` = \f$\partial_x t \cdot \partial_t f\f$ 489 * 7. `y->derivative` += \f$\partial_y t \,\cdot\f$ `t->derivative` = \f$\partial_y t \cdot \partial_t f\f$ 490 * 491 * Note that, to compute this, we only need to know, for each expression, its partial derivatives w.r.t a given child at a point. 492 * This is what the callback `SCIP_DECL_EXPRBWDIFF` should return. 493 * Indeed, from "derivative of expr w.r.t. child evaluated at point multiplied with expr->derivative", 494 * note that at the moment of processing a child, we already know `expr->derivative`, so the only 495 * missing piece of information is "the derivative of expr w.r.t. child evaluated at point". 496 * 497 * An equivalent way of interpreting the procedure is that `expr->derivative` stores the derivative of the root w.r.t. expr. 498 * This way, `x->derivative` and `y->derivative` will contain the partial derivatives of root w.r.t. the variable, that is, the gradient. 499 * Note, however, that this analogy is only correct for leave expressions, since the derivative value of an intermediate expression gets overwritten. 500 * 501 * 502 * \par Hessian (Automatic differentiation Backward on Forward mode) 503 * 504 * Computing the Hessian is more complicated since it is the derivative of the gradient, which is a function with more than one output. 505 * We compute the Hessian by computing "directions" of the Hessian, that is \f$H\cdot u\f$ for different \f$u\f$. 506 * This is easy in general, since it is the gradient of the *scalar* function \f$\nabla f u\f$, that is, 507 * the directional derivative of \f$f\f$ in the direction \f$u\f$: \f$D_u f\f$. 508 * 509 * This is easily computed via the so called forward mode. 510 * Just as `expr->derivative` stores the partial derivative of the root w.r.t. expr, 511 * `expr->dot` stores the directional derivative of expr in the direction \f$u\f$. 512 * Then, by the chain rule, `expr->dot` = \f$\sum_{c:\text{children}} \partial_c \text{expr} \,\cdot\f$ `c->dot`. 513 * 514 * Starting with `x[i]->dot` = \f$u_i\f$, we can compute `expr->dot` for every expression at the same time we evaluate expr. 515 * Computing `expr->dot` is the purpose of the callback `SCIP_DECL_EXPRFWDIFF`. 516 * Obviously, when this callback is called, the "dots" of all children are known 517 * (just like evaluation, where the value of all children are known). 518 * 519 * Once we have this information, we compute the gradient of this function, following the same idea as before. 520 * We define `expr->bardot` to be the directional derivative in direction \f$u\f$ of the partial derivative of the root w.r.t `expr`, 521 * that is \f$D_u (\partial_{\text{expr}} f) = D_u\f$ (`expr->derivative`). 522 * 523 * This way, `x[i]->bardot` = \f$D_u (\partial_{x_i} f) = e_i^T H_f u\f$. 524 * Hence `vars->bardot` contain \f$H_f u\f$. 525 * By the chain rule, product rule, and definition we have 526 * \f{eqnarray*}{ 527 * \texttt{expr->bardot} & = & D_u (\partial_{\text{expr}} f) \\ 528 * & = & D_u ( \partial_{\text{parent}} f \cdot \partial_{\text{expr}} \text{parent} ) \\ 529 * & = & D_u ( \texttt{parent->derivative} \cdot \partial_{\text{expr}} \text{parent} ) \\ 530 * & = & \partial_{\text{expr}} \text{parent} \cdot D_u (\texttt{parent->derivative}) + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent}) \\ 531 * & = & \texttt{parent->bardot} \cdot \partial_{\text{expr}} \text{parent} + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent}) 532 * \f} 533 * 534 * Note that we have computed `parent->bardot` and `parent->derivative` at this point, 535 * while \f$\partial_{\text{expr}} \text{parent}\f$ is the return of `SCIP_DECL_EXPRBWDIFF`. 536 * Hence the only information we need to compute is \f$D_u (\partial_{\text{expr}} \text{parent})\f$. 537 * This is the purpose of the callback `SCIP_DECL_EXPRBWFWDIFF`. 538 * 539 * @{ 540 */ 541 542 /** evaluates gradient of an expression for a given point 543 * 544 * Initiates an expression walk to also evaluate children, if necessary. 545 * Value can be received via SCIPgetExprPartialDiffNonlinear(). 546 * If an error (division by zero, ...) occurs, this value will 547 * be set to SCIP_INVALID. 548 */ 549 SCIP_EXPORT 550 SCIP_RETCODE SCIPevalExprGradient( 551 SCIP* scip, /**< SCIP data structure */ 552 SCIP_EXPR* expr, /**< expression to be differentiated */ 553 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */ 554 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */ 555 ); 556 557 /** evaluates Hessian-vector product of an expression for a given point and direction 558 * 559 * Evaluates children, if necessary. 560 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear(). 561 * If an error (division by zero, ...) occurs, this value will 562 * be set to SCIP_INVALID. 563 */ 564 SCIP_EXPORT 565 SCIP_RETCODE SCIPevalExprHessianDir( 566 SCIP* scip, /**< SCIP data structure */ 567 SCIP_EXPR* expr, /**< expression to be differentiated */ 568 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */ 569 SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */ 570 SCIP_SOL* direction /**< direction */ 571 ); 572 573 /**@} */ /* end of differentiation methods */ 574 575 /**@name Expressions 576 * @{ 577 */ 578 579 /** possibly reevaluates and then returns the activity of the expression 580 * 581 * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation). 582 * 583 * The owner of the expression may overwrite the methods used to evaluate the activity, 584 * including whether the local or global domain of variables is used. 585 * By default (no owner, or owner doesn't overwrite activity evaluation), 586 * the local domain of variables is used. 587 * 588 * @note If expression is set to be integral, then activities are tightened to integral values. 589 * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok). 590 */ 591 SCIP_EXPORT 592 SCIP_RETCODE SCIPevalExprActivity( 593 SCIP* scip, /**< SCIP data structure */ 594 SCIP_EXPR* expr /**< expression */ 595 ); 596 597 /** compare expressions 598 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively 599 * @note The given expressions are assumed to be simplified. 600 */ 601 SCIP_EXPORT 602 int SCIPcompareExpr( 603 SCIP* scip, /**< SCIP data structure */ 604 SCIP_EXPR* expr1, /**< first expression */ 605 SCIP_EXPR* expr2 /**< second expression */ 606 ); 607 608 /** compute the hash value of an expression */ 609 SCIP_EXPORT 610 SCIP_RETCODE SCIPhashExpr( 611 SCIP* scip, /**< SCIP data structure */ 612 SCIP_EXPR* expr, /**< expression */ 613 unsigned int* hashval /**< pointer to store the hash value */ 614 ); 615 616 /** simplifies an expression 617 * 618 * This is largely inspired by Joel Cohen's 619 * *Computer algebra and symbolic computation: Mathematical methods*, 620 * in particular Chapter 3. 621 * The other fountain of inspiration are the simplifying methods of expr.c in SCIP 7. 622 * 623 * Note: The things to keep in mind when adding simplification rules are the following. 624 * I will be using the product expressions (see expr_product.c) as an example. 625 * There are mainly 3 parts of the simplification process. You need to decide 626 * at which stage the simplification rule makes sense. 627 * 1. Simplify each factor (simplifyFactor()): At this stage we got the children of the product expression. 628 * At this point, each child is simplified when viewed as a stand-alone expression, but not necessarily when viewed as child of a product expression. 629 * Rules like SP2, SP7, etc are enforced at this point. 630 * 2. Multiply the factors (mergeProductExprlist()): At this point rules like SP4, SP5 and SP14 are enforced. 631 * 3. Build the actual simplified product expression (buildSimplifiedProduct()): 632 * At this point rules like SP10, SP11, etc are enforced. 633 * 634 * During steps 1 and 2 do not forget to set the flag `changed` to TRUE when something actually changes. 635 * 636 * \par Definition of simplified expressions 637 * 638 * An expression is simplified if it 639 * - is a value expression 640 * - is a var expression 641 * - is a product expression such that 642 * - SP1: every child is simplified 643 * - SP2: no child is a product 644 * - SP4: no two children are the same expression (those should be multiplied) 645 * - SP5: the children are sorted [commutative rule] 646 * - SP7: no child is a value 647 * - SP8: its coefficient is 1.0 (otherwise should be written as sum) 648 * - SP10: it has at least two children 649 * - TODO?: at most one child is an `abs` 650 * - SP11: no two children are `expr*log(expr)` 651 * (TODO: we could handle more complicated stuff like \f$xy\log(x) \to - y * \mathrm{entropy}(x)\f$, but I am not sure this should happen at the simplification level; 652 * similar for \f$(xy) \log(xy)\f$, which currently simplifies to \f$xy \log(xy)\f$) 653 * - SP12: if it has two children, then neither of them is a sum (expand sums) 654 * - SP12b: if it has at least two children and expandalways is set, then no child is a sum (expand sums always) 655 * - SP13: no child is a sum with a single term 656 * - SP14: at most one child is an `exp` 657 * - is a power expression such that 658 * - POW1: exponent is not 0 659 * - POW2: exponent is not 1 660 * - POW3: its child is not a value 661 * - POW4: its child is simplified 662 * - POW5: if exponent is integer, its child is not a product 663 * - POW5a: if exponent is fractional and distribfracexponent param is enabled, its child is not a product 664 * - POW6: if exponent is integer, its child is not a sum with a single term (\f$(2x)^2 \to 4x^2\f$) 665 * - POW7: if exponent is integer and at most expandmaxeponent param, its child is not a sum (expand sums) 666 * - POW8: its child is not a power unless \f$(x^n)^m\f$ with \f$nm\f$ being integer and \f$n\f$ or \f$m\f$ fractional and \f$n\f$ not being even integer 667 * - POW9: its child is not a sum with a single term with a positive coefficient: \f$(25x)^{0.5} \to 5 x^{0.5}\f$ 668 * - POW10: its child is not a binary variable: \f$b^e, e > 0 \to b\f$; \f$b^e, e < 0 \to b := 1\f$ 669 * - POW11: its child is not an exponential: \f$\exp(\text{expr})^e \to \exp(e\cdot\text{expr})\f$ 670 * - POW12: its child is not an absolute value if the exponent is an even integer: \f$\abs(\text{expr})^e, e \text{ even} \to \text{expr}^e\f$ 671 * - is a signedpower expression such that 672 * - SPOW1: exponent is not 0 673 * - SPOW2: exponent is not 1 674 * - SPOW3: its child is not a value 675 * - SPOW4: its child is simplified 676 * - SPOW5: (TODO) do we want to distribute signpowers over products like we do for powers? 677 * - SPOW6: exponent is not an odd integer: (signpow odd expr) -> (pow odd expr) 678 * - SPOW8: if exponent is integer, its child is not a power 679 * - SPOW9: its child is not a sum with a single term: \f$\mathrm{signpow}(25x,0.5) \to 5\mathrm{signpow}(x,0.5)\f$ 680 * - SPOW10: its child is not a binary variable: \f$\mathrm{signpow}(b,e), e > 0 \to b\f$; \f$\mathrm{signpow}(b,e), e < 0 \to b := 1\f$ 681 * - SPOW11: its child is not an exponential: \f$\mathrm{signpow}(\exp(\text{expr}),e) \to \exp(e\cdot\text{expr})\f$ 682 * - TODO: what happens when child is another signed power? 683 * - TODO: if child ≥ 0 -> transform to normal power; if child < 0 -> transform to - normal power 684 * 685 * TODO: Some of these criteria are too restrictive for signed powers; for example, the exponent does not need to be 686 * an integer for signedpower to distribute over a product (SPOW5, SPOW6, SPOW8). Others can also be improved. 687 * - is a sum expression such that 688 * - SS1: every child is simplified 689 * - SS2: no child is a sum 690 * - SS3: no child is a value (values should go in the constant of the sum) 691 * - SS4: no two children are the same expression (those should be summed up) 692 * - SS5: the children are sorted [commutative rule] 693 * - SS6: it has at least one child 694 * - SS7: if it consists of a single child, then either constant is != 0.0 or coef != 1 695 * - SS8: no child has coefficient 0 696 * - SS9: if a child c is a product that has an exponential expression as one of its factors, then the coefficient of c is +/-1.0 697 * - SS10: if a child c is an exponential, then the coefficient of c is +/-1.0 698 * - it is a function with simplified arguments, but not all of them can be values 699 * - TODO? a logarithm doesn't have a product as a child 700 * - TODO? the exponent of an exponential is always 1 701 * 702 * \par Ordering Rules (see SCIPexprCompare()) 703 * \anchor EXPR_ORDER 704 * These rules define a total order on *simplified* expressions. 705 * There are two groups of rules, when comparing equal type expressions and different type expressions. 706 * 707 * Equal type expressions: 708 * - OR1: u,v value expressions: u < v ⇔ val(u) < val(v) 709 * - OR2: u,v var expressions: u < v ⇔ `SCIPvarGetIndex(var(u))` < `SCIPvarGetIndex(var(v))` 710 * - OR3: u,v are both sum or product expression: < is a lexicographical order on the terms 711 * - OR4: u,v are both pow: u < v ⇔ base(u) < base(v) or, base(u) = base(v) and expo(u) < expo(v) 712 * - OR5: u,v are \f$u = f(u_1, ..., u_n), v = f(v_1, ..., v_m)\f$: u < v ⇔ For the first k such that \f$u_k \neq v_k\f$, \f$u_k < v_k\f$, or if such a \f$k\f$ doesn't exist, then \f$n < m\f$. 713 * 714 * Different type expressions: 715 * - OR6: u value, v other: u < v always 716 * - OR7: u sum, v var or func: u < v ⇔ u < 0+v; 717 * In other words, if \f$u = \sum_{i=1}^n \alpha_i u_i\f$, then u < v ⇔ \f$u_n\f$ < v or if \f$u_n\f$ = v and \f$\alpha_n\f$ < 1. 718 * - OR8: u product, v pow, sum, var or func: u < v ⇔ u < 1*v; 719 * In other words, if \f$u = \prod_{i=1}^n u_i\f$, then u < v ⇔ \f$u_n\f$ < v. 720 * Note: since this applies only to simplified expressions, the form of the product is correct. 721 * Simplified products do *not* have constant coefficients. 722 * - OR9: u pow, v sum, var or func: u < v ⇔ u < v^1 723 * - OR10: u var, v func: u < v always 724 * - OR11: u func, v other type of func: u < v ⇔ name(type(u)) < name(type(v)) 725 * - OR12: none of the rules apply: u < v ⇔ ! v < u 726 * 727 * Examples: 728 * - x < x^2 ?: x is var and x^2 power, so none applies (OR12). 729 * Hence, we try to answer x^2 < x ?: x^2 < x ⇔ x < x or if x = x and 2 < 1 ⇔ 2 < 1 ⇔ False. So x < x^2 is True. 730 * - x < x^-1 --OR12→ ~(x^-1 < x) --OR9→ ~(x^-1 < x^1) --OR4→ ~(x < x or -1 < 1) → ~True → False 731 * - x*y < x --OR8→ x*y < 1*x --OR3→ y < x --OR2→ False 732 * - x*y < y --OR8→ x*y < 1*y --OR3→ y < x --OR2→ False 733 * 734 * \par Algorithm 735 * 736 * The recursive version of the algorithm is 737 * 738 * EXPR simplify(expr) 739 * for c in 1..expr->nchildren 740 * expr->children[c] = simplify(expr->children[c]) 741 * end 742 * return expr->exprhdlr->simplify(expr) 743 * end 744 * 745 * Important: Whatever is returned by a simplify callback **has** to be simplified. 746 * Also, all children of the given expression **are** already simplified. 747 */ 748 SCIP_EXPORT 749 SCIP_RETCODE SCIPsimplifyExpr( 750 SCIP* scip, /**< SCIP data structure */ 751 SCIP_EXPR* rootexpr, /**< expression to be simplified */ 752 SCIP_EXPR** simplified, /**< buffer to store simplified expression */ 753 SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */ 754 SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */ 755 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 756 void* ownercreatedata /**< data to pass to ownercreate */ 757 ); 758 759 /** retrieves symmetry information from an expression */ 760 SCIP_EXPORT 761 SCIP_RETCODE SCIPgetSymDataExpr( 762 SCIP* scip, /**< SCIP data structure */ 763 SCIP_EXPR* expr, /**< expression from which information needs to be retrieved */ 764 SYM_EXPRDATA** symdata /**< buffer to store symmetry data */ 765 ); 766 767 /** replaces common sub-expressions in a given expression graph by using a hash key for each expression 768 * 769 * The algorithm consists of two steps: 770 * 771 * 1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash 772 * 773 * 2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a 774 * structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the 775 * hash table, otherwise we add it to the hash table 776 * 777 * @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions 778 * (with the same hash) are structurally the same we use the function SCIPexprCompare(). 779 */ 780 SCIP_EXPORT 781 SCIP_RETCODE SCIPreplaceCommonSubexpressions( 782 SCIP* scip, /**< SCIP data structure */ 783 SCIP_EXPR** exprs, /**< expressions (possibly replaced by equivalent on output) */ 784 int nexprs, /**< total number of expressions */ 785 SCIP_Bool* replacedroot /**< buffer to store whether any root expression (expression in exprs) was replaced */ 786 ); 787 788 /** computes the curvature of a given expression and all its subexpressions 789 * 790 * @note this function also evaluates all subexpressions w.r.t. current variable bounds 791 * @note this function relies on information from the curvature callback of expression handlers only, 792 * consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity 793 */ 794 SCIP_EXPORT 795 SCIP_RETCODE SCIPcomputeExprCurvature( 796 SCIP* scip, /**< SCIP data structure */ 797 SCIP_EXPR* expr /**< expression */ 798 ); 799 800 /** computes integrality information of a given expression and all its subexpressions 801 * 802 * The integrality information can be accessed via SCIPexprIsIntegral(). 803 */ 804 SCIP_EXPORT 805 SCIP_RETCODE SCIPcomputeExprIntegrality( 806 SCIP* scip, /**< SCIP data structure */ 807 SCIP_EXPR* expr /**< expression */ 808 ); 809 810 /** returns the total number of variable expressions in an expression 811 * 812 * The function counts variable expressions in common sub-expressions only once, but 813 * counts variables appearing in several variable expressions multiple times. 814 */ 815 SCIP_EXPORT 816 SCIP_RETCODE SCIPgetExprNVars( 817 SCIP* scip, /**< SCIP data structure */ 818 SCIP_EXPR* expr, /**< expression */ 819 int* nvars /**< buffer to store the total number of variables */ 820 ); 821 822 /** returns all variable expressions contained in a given expression 823 * 824 * The array to store all variable expressions needs to be at least of size 825 * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars(). 826 * 827 * If every variable is represented by only one variable expression (common subexpression have been removed) 828 * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars(). 829 * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying, 830 * then SCIPgetExprNVars() can be bounded by SCIPgetNVars(). 831 * 832 * @note function captures variable expressions 833 */ 834 SCIP_EXPORT 835 SCIP_RETCODE SCIPgetExprVarExprs( 836 SCIP* scip, /**< SCIP data structure */ 837 SCIP_EXPR* expr, /**< expression */ 838 SCIP_EXPR** varexprs, /**< array to store all variable expressions */ 839 int* nvarexprs /**< buffer to store the total number of variable expressions */ 840 ); 841 842 /** @} */ 843 844 /**@name Expression Handler Callbacks 845 * @{ 846 */ 847 848 /** calls the print callback for an expression 849 * 850 * @see SCIP_DECL_EXPRPRINT 851 */ 852 SCIP_EXPORT 853 SCIP_DECL_EXPRPRINT(SCIPcallExprPrint); 854 855 /** calls the curvature callback for an expression 856 * 857 * @see SCIP_DECL_EXPRCURVATURE 858 * 859 * Returns unknown curvature if callback not implemented. 860 */ 861 SCIP_EXPORT 862 SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature); 863 864 /** calls the monotonicity callback for an expression 865 * 866 * @see SCIP_DECL_EXPRMONOTONICITY 867 * 868 * Returns unknown monotonicity if callback not implemented. 869 */ 870 SCIP_EXPORT 871 SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity); 872 873 /** calls the eval callback for an expression with given values for children 874 * 875 * Does not iterates over expressions, but requires values for children to be given. 876 * Value is not stored in expression, but returned in `val`. 877 * If an evaluation error (division by zero, ...) occurs, this value will 878 * be set to `SCIP_INVALID`. 879 */ 880 SCIP_EXPORT 881 SCIP_RETCODE SCIPcallExprEval( 882 SCIP* scip, /**< SCIP data structure */ 883 SCIP_EXPR* expr, /**< expression to be evaluated */ 884 SCIP_Real* childrenvalues, /**< values for children */ 885 SCIP_Real* val /**< buffer to store evaluated value */ 886 ); 887 888 /** calls the eval and fwdiff callback of an expression with given values for children 889 * 890 * Does not iterates over expressions, but requires values for children and direction to be given. 891 * 892 * Value is not stored in expression, but returned in `val`. 893 * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`. 894 * 895 * Direction is not stored in expression, but returned in `dot`. 896 * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`. 897 */ 898 SCIP_EXPORT 899 SCIP_RETCODE SCIPcallExprEvalFwdiff( 900 SCIP* scip, /**< SCIP data structure */ 901 SCIP_EXPR* expr, /**< expression to be evaluated */ 902 SCIP_Real* childrenvalues, /**< values for children */ 903 SCIP_Real* direction, /**< direction in which to differentiate */ 904 SCIP_Real* val, /**< buffer to store evaluated value */ 905 SCIP_Real* dot /**< buffer to store derivative value */ 906 ); 907 908 /** calls the interval evaluation callback for an expression 909 * 910 * @see SCIP_DECL_EXPRINTEVAL 911 * 912 * Returns entire interval if callback not implemented. 913 */ 914 SCIP_EXPORT 915 SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval); 916 917 /** calls the estimate callback for an expression 918 * 919 * @see SCIP_DECL_EXPRESTIMATE 920 * 921 * Returns without success if callback not implemented. 922 */ 923 SCIP_EXPORT 924 SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate); 925 926 /** calls the initial estimators callback for an expression 927 * 928 * @see SCIP_DECL_EXPRINITESTIMATES 929 * 930 * Returns no estimators if callback not implemented. 931 */ 932 SCIP_EXPORT 933 SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates); 934 935 /** calls the simplify callback for an expression 936 * 937 * @see SCIP_DECL_EXPRSIMPLIFY 938 * 939 * Returns unmodified expression if simplify callback not implemented. 940 * 941 * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that. 942 */ 943 SCIP_EXPORT 944 SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify); 945 946 /** calls the reverse propagation callback for an expression 947 * 948 * @see SCIP_DECL_EXPRREVERSEPROP 949 * 950 * Returns unmodified `childrenbounds` if reverseprop callback not implemented. 951 */ 952 SCIP_EXPORT 953 SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop); 954 955 /** calls the symmetry information callback for an expression 956 * 957 * Returns NULL pointer if not implemented. 958 */ 959 SCIP_EXPORT 960 SCIP_DECL_EXPRGETSYMDATA(SCIPcallExprGetSymData); 961 962 #ifdef NDEBUG 963 #define SCIPappendExprChild(scip, expr, child) SCIPexprAppendChild((scip)->set, (scip)->mem->probmem, expr, child) 964 #define SCIPreplaceExprChild(scip, expr, childidx, newchild) SCIPexprReplaceChild((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, childidx, newchild) 965 #define SCIPremoveExprChildren(scip, expr) SCIPexprRemoveChildren((scip)->set, (scip)->stat, (scip)->mem->probmem, expr) 966 #define SCIPduplicateExpr(scip, expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) SCIPexprCopy((scip)->set, (scip)->stat, (scip)->mem->probmem, (scip)->set, (scip)->stat, (scip)->mem->probmem, expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) 967 #define SCIPduplicateExprShallow(scip, expr, copyexpr, ownercreate, ownercreatedata) SCIPexprDuplicateShallow((scip)->set, (scip)->mem->probmem, expr, copyexpr, ownercreate, ownercreatedata) 968 #define SCIPcaptureExpr(expr) SCIPexprCapture(expr) 969 #define SCIPreleaseExpr(scip, expr) SCIPexprRelease((scip)->set, (scip)->stat, (scip)->mem->probmem, expr) 970 #define SCIPisExprVar(scip, expr) SCIPexprIsVar((scip)->set, expr) 971 #define SCIPisExprValue(scip, expr) SCIPexprIsValue((scip)->set, expr) 972 #define SCIPisExprSum(scip, expr) SCIPexprIsSum((scip)->set, expr) 973 #define SCIPisExprProduct(scip, expr) SCIPexprIsProduct((scip)->set, expr) 974 #define SCIPisExprPower(scip, expr) SCIPexprIsPower((scip)->set, expr) 975 #define SCIPprintExpr(scip, expr, file) SCIPexprPrint((scip)->set, (scip)->stat, (scip)->mem->probmem, (scip)->messagehdlr, file, expr) 976 #define SCIPevalExpr(scip, expr, sol, soltag) SCIPexprEval((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag) 977 #define SCIPgetExprNewSoltag(scip) (++((scip)->stat->exprlastsoltag)) 978 #define SCIPevalExprGradient(scip, expr, sol, soltag) SCIPexprEvalGradient((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag) 979 #define SCIPevalExprHessianDir(scip, expr, sol, soltag, direction) SCIPexprEvalHessianDir((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag, direction) 980 #define SCIPevalExprActivity(scip, expr) SCIPexprEvalActivity((scip)->set, (scip)->stat, (scip)->mem->probmem, expr) 981 #define SCIPcompareExpr(scip, expr1, expr2) SCIPexprCompare((scip)->set, expr1, expr2) 982 #define SCIPsimplifyExpr(scip, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) SCIPexprSimplify((scip)->set, (scip)->stat, (scip)->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) 983 #define SCIPcallExprCurvature(scip, expr, exprcurvature, success, childcurv) SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, exprcurvature, success, childcurv) 984 #define SCIPcallExprMonotonicity(scip, expr, childidx, result) SCIPexprhdlrMonotonicityExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, childidx, result) 985 #define SCIPcallExprEval(scip, expr, childrenvalues, val) SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), (scip)->set, (scip)->mem->buffer, expr, val, childrenvalues, NULL) 986 #define SCIPcallExprEvalFwdiff(scip, expr, childrenvalues, direction, val, dot) SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), (scip)->set, (scip)->mem->buffer, expr, val, dot, childrenvalues, NULL, direction, NULL) 987 #define SCIPcallExprInteval(scip, expr, interval, intevalvar, intevalvardata) SCIPexprhdlrIntEvalExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, interval, intevalvar, intevalvardata) 988 #define SCIPcallExprEstimate(scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, coefs, constant, islocal, success, branchcand) SCIPexprhdlrEstimateExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, coefs, constant, islocal, success, branchcand) 989 #define SCIPcallExprInitestimates(scip, expr, bounds, overestimate, coefs, constant, nreturned) SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, bounds, overestimate, coefs, constant, nreturned) 990 #define SCIPcallExprSimplify(scip, expr, simplifiedexpr, ownercreate, ownercreatedata) SCIPexprhdlrSimplifyExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, simplifiedexpr, ownercreate, ownercreatedata) 991 #define SCIPcallExprReverseprop(scip, expr, bounds, childrenbounds, infeasible) SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, bounds, childrenbounds, infeasible) 992 #define SCIPcallExprGetSymData(scip, expr, symdata) SCIPexprhdlrGetSymdata(SCIPexprGetHdlr(expr), (scip)->set, expr, symdata) 993 #endif 994 995 /** @} */ 996 997 998 /**@name Expression Iterator */ 999 /**@{ */ 1000 1001 /** creates an expression iterator */ 1002 SCIP_EXPORT 1003 SCIP_RETCODE SCIPcreateExpriter( 1004 SCIP* scip, /**< SCIP data structure */ 1005 SCIP_EXPRITER** iterator /**< buffer to store expression iterator */ 1006 ); 1007 1008 /** frees an expression iterator */ 1009 SCIP_EXPORT 1010 void SCIPfreeExpriter( 1011 SCIP_EXPRITER** iterator /**< pointer to the expression iterator */ 1012 ); 1013 1014 #ifdef NDEBUG 1015 #define SCIPcreateExpriter(scip, iterator) SCIPexpriterCreate((scip)->stat, (scip)->mem->probmem, iterator) 1016 #define SCIPfreeExpriter(iterator) SCIPexpriterFree(iterator) 1017 #endif 1018 1019 /** @} */ 1020 1021 1022 /**@name Quadratic Expressions */ 1023 /**@{ */ 1024 1025 /** checks whether an expression is quadratic 1026 * 1027 * An expression is quadratic if it is either a square (of some expression), a product (of two expressions), 1028 * or a sum of terms where at least one is a square or a product. 1029 * 1030 * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic. 1031 */ 1032 SCIP_EXPORT 1033 SCIP_RETCODE SCIPcheckExprQuadratic( 1034 SCIP* scip, /**< SCIP data structure */ 1035 SCIP_EXPR* expr, /**< expression */ 1036 SCIP_Bool* isquadratic /**< buffer to store result */ 1037 ); 1038 1039 /** frees information on quadratic representation of an expression 1040 * 1041 * Before doing changes to an expression, it can be useful to call this function. 1042 */ 1043 SCIP_EXPORT 1044 void SCIPfreeExprQuadratic( 1045 SCIP* scip, /**< SCIP data structure */ 1046 SCIP_EXPR* expr /**< expression */ 1047 ); 1048 1049 /** evaluates quadratic term in a solution 1050 * 1051 * \note This requires that every expression used in the quadratic data is a variable expression. 1052 */ 1053 SCIP_EXPORT 1054 SCIP_Real SCIPevalExprQuadratic( 1055 SCIP* scip, /**< SCIP data structure */ 1056 SCIP_EXPR* expr, /**< quadratic expression */ 1057 SCIP_SOL* sol /**< solution to evaluate, or NULL for LP solution */ 1058 ); 1059 1060 /** prints quadratic expression */ 1061 SCIP_EXPORT 1062 SCIP_RETCODE SCIPprintExprQuadratic( 1063 SCIP* scip, /**< SCIP data structure */ 1064 SCIP_EXPR* expr /**< quadratic expression */ 1065 ); 1066 1067 /** checks the curvature of the quadratic expression 1068 * 1069 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK. 1070 * If Q is 1071 * - semidefinite positive -> curv is set to convex, 1072 * - semidefinite negative -> curv is set to concave, 1073 * - otherwise -> curv is set to unknown. 1074 * 1075 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in 1076 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q. 1077 */ 1078 SCIP_EXPORT 1079 SCIP_RETCODE SCIPcomputeExprQuadraticCurvature( 1080 SCIP* scip, /**< SCIP data structure */ 1081 SCIP_EXPR* expr, /**< quadratic expression */ 1082 SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */ 1083 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ 1084 SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */ 1085 ); 1086 1087 #ifdef NDEBUG 1088 #define SCIPcheckExprQuadratic(scip, expr, isquadratic) SCIPexprCheckQuadratic((scip)->set, (scip)->mem->probmem, expr, isquadratic) 1089 #define SCIPfreeExprQuadratic(scip, expr) SCIPexprFreeQuadratic((scip)->mem->probmem, expr) 1090 #define SCIPcomputeExprQuadraticCurvature(scip, expr, curv, assumevarfixed, storeeigeninfo) SCIPexprComputeQuadraticCurvature((scip)->set, (scip)->mem->probmem, (scip)->mem->buffer, (scip)->messagehdlr, expr, curv, assumevarfixed, storeeigeninfo) 1091 #endif 1092 1093 /** @} */ 1094 1095 /**@name Monomial Expressions */ 1096 /**@{ */ 1097 1098 /** returns a monomial representation of a product expression 1099 * 1100 * The array to store all factor expressions needs to be of size the number of 1101 * children in the expression which is given by SCIPexprGetNChildren(). 1102 * 1103 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where 1104 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can 1105 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents. 1106 * 1107 * A non-trivial monomial is a product of a least two expressions. 1108 */ 1109 SCIP_EXPORT 1110 SCIP_RETCODE SCIPgetExprMonomialData( 1111 SCIP* scip, /**< SCIP data structure */ 1112 SCIP_EXPR* expr, /**< expression */ 1113 SCIP_Real* coef, /**< coefficient \f$c\f$ */ 1114 SCIP_Real* exponents, /**< exponents \f$\alpha\f$ */ 1115 SCIP_EXPR** factors /**< factor expressions \f$x\f$ */ 1116 ); 1117 1118 #ifdef NDEBUG 1119 #define SCIPgetExprMonomialData(scip, expr, coef, exponents, factors) SCIPexprGetMonomialData((scip)->set, (scip)->mem->probmem, expr, coef, exponents, factors) 1120 #endif 1121 1122 /** @} */ 1123 1124 /** @} */ 1125 1126 #ifdef __cplusplus 1127 } 1128 #endif 1129 1130 #endif /* SCIP_SCIP_EXPR_H_ */ 1131