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.c 26 * @ingroup OTHER_CFILES 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 #include <string.h> 35 #include <ctype.h> 36 37 #include "scip/scip_expr.h" 38 #include "scip/expr.h" 39 #include "scip/set.h" 40 #include "scip/misc.h" 41 #include "scip/scip_copy.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_message.h" 44 #include "scip/scip_prob.h" 45 #include "scip/scip_var.h" 46 #include "scip/scip_sol.h" 47 #include "scip/pub_var.h" 48 #include "scip/struct_scip.h" 49 #include "scip/struct_mem.h" 50 #include "scip/struct_stat.h" 51 52 /* core expression handler plugins */ 53 #include "scip/expr_value.h" 54 #include "scip/expr_var.h" 55 #include "scip/expr_sum.h" 56 #include "scip/expr_product.h" 57 #include "scip/expr_pow.h" 58 59 /* #define PARSE_DEBUG */ 60 61 /*lint -e440*/ 62 /*lint -e441*/ 63 64 /* 65 * local functions 66 */ 67 68 /** variable mapping data passed on during copying expressions when copying SCIP instances */ 69 typedef struct 70 { 71 SCIP_HASHMAP* varmap; /**< SCIP_HASHMAP mapping variables of the source SCIP to corresponding 72 variables of the target SCIP */ 73 SCIP_HASHMAP* consmap; /**< SCIP_HASHMAP mapping constraints of the source SCIP to corresponding 74 constraints of the target SCIP */ 75 SCIP_Bool global; /**< should a global or a local copy be created */ 76 SCIP_Bool valid; /**< indicates whether every variable copy was valid */ 77 } COPY_MAPEXPR_DATA; 78 79 /** variable expression mapping callback to call when copying expressions (within same or different SCIPs) */ 80 static 81 SCIP_DECL_EXPR_MAPEXPR(copyVarExpr) 82 { 83 COPY_MAPEXPR_DATA* data; 84 SCIP_Bool valid; 85 SCIP_VAR* targetvar; 86 87 assert(sourcescip != NULL); 88 assert(sourceexpr != NULL); 89 assert(targetscip != NULL); 90 assert(targetexpr != NULL); 91 assert(mapexprdata != NULL); 92 93 *targetexpr = NULL; 94 95 if( !SCIPisExprVar(sourcescip, sourceexpr) ) 96 return SCIP_OKAY; 97 98 data = (COPY_MAPEXPR_DATA*)mapexprdata; 99 100 SCIP_CALL( SCIPgetVarCopy(sourcescip, targetscip, SCIPgetVarExprVar(sourceexpr), &targetvar, data->varmap, 101 data->consmap, data->global, &valid) ); 102 assert(targetvar != NULL); 103 104 /* if copy was not valid, store so in mapvar data */ 105 if( !valid ) 106 data->valid = FALSE; 107 108 SCIP_CALL( SCIPcreateExprVar(targetscip, targetexpr, targetvar, ownercreate, ownercreatedata) ); 109 110 return SCIP_OKAY; 111 } 112 113 114 /** @name Parsing methods (internal) 115 * @{ 116 * Here is an attempt at defining the grammar of an expression. 117 * We use upper case names for variables (in the grammar sense) and terminals are between "". 118 * Loosely speaking, a Base will be any "block", a Factor is a Base to a power, a Term is a product of Factors 119 * and an Expression is a sum of terms. 120 * The actual definition: 121 * <pre> 122 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term } 123 * Term -> Factor { ("*" | "/" ) Factor } 124 * Factor -> Base [ "^" "number" | "^(" "number" ")" ] 125 * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ") 126 * </pre> 127 * where [a|b] means a or b or none, (a|b) means a or b, {a} means 0 or more a. 128 * 129 * Note that Op and OpExpression are undefined. Op corresponds to the name of an expression handler and 130 * OpExpression to whatever string the expression handler accepts (through its parse method). 131 * 132 * parse(Expr|Term|Base) returns an SCIP_EXPR 133 * 134 * @todo We can change the grammar so that Factor becomes base and we allow a Term to be 135 * <pre> Term -> Factor { ("*" | "/" | "^") Factor } </pre> 136 */ 137 138 /*lint -emacro(681,debugParse) */ 139 /*lint -emacro(506,debugParse) */ 140 /*lint -emacro(774,debugParse) */ 141 #ifdef PARSE_DEBUG 142 #define debugParse printf 143 #else 144 #define debugParse while( FALSE ) printf 145 #endif 146 147 /* forward declaration */ 148 static 149 SCIP_RETCODE parseExpr( 150 SCIP* scip, /**< SCIP data structure */ 151 SCIP_HASHMAP* vartoexprvarmap, /**< hashmap to map between scip vars and var expressions */ 152 const char* expr, /**< expr that we are parsing */ 153 const char** newpos, /**< buffer to store the position of expr where we finished reading */ 154 SCIP_EXPR** exprtree, /**< buffer to store the expr parsed by Expr */ 155 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 156 void* ownercreatedata /**< data to pass to ownercreate */ 157 ); 158 159 /** Parses base to build a value, variable, sum, or function-like ("func(...)") expression. 160 * <pre> 161 * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ") 162 * </pre> 163 */ 164 static 165 SCIP_RETCODE parseBase( 166 SCIP* scip, /**< SCIP data structure */ 167 SCIP_HASHMAP* vartoexprvarmap, /**< hashmap to map between SCIP vars and var expressions */ 168 const char* expr, /**< expr that we are parsing */ 169 const char** newpos, /**< buffer to store the position of expr where we finished reading */ 170 SCIP_EXPR** basetree, /**< buffer to store the expr parsed by Base */ 171 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 172 void* ownercreatedata /**< data to pass to ownercreate */ 173 ) 174 { 175 debugParse("parsing base from %s\n", expr); 176 177 /* ignore whitespace */ 178 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 179 180 if( *expr == '\0' ) 181 { 182 SCIPerrorMessage("Unexpected end of expression string\n"); 183 return SCIP_READERROR; 184 } 185 186 if( *expr == '<' ) 187 { 188 /* parse a variable */ 189 SCIP_VAR* var; 190 191 SCIP_CALL( SCIPparseVarName(scip, expr, &var, (char**)newpos) ); 192 193 if( var == NULL ) 194 { 195 SCIPerrorMessage("Could not find variable with name '%s'\n", expr); 196 return SCIP_READERROR; 197 } 198 199 expr = *newpos; 200 201 /* check if we have already created an expression out of this var */ 202 if( SCIPhashmapExists(vartoexprvarmap, (void*)var) ) 203 { 204 debugParse("Variable <%s> has already been parsed, capturing its expression\n", SCIPvarGetName(var)); 205 *basetree = (SCIP_EXPR*)SCIPhashmapGetImage(vartoexprvarmap, (void*)var); 206 SCIPexprCapture(*basetree); 207 } 208 else 209 { 210 debugParse("First time parsing variable <%s>, creating varexpr and adding it to hashmap\n", SCIPvarGetName(var)); 211 /* intentionally not using createExprVar here, since parsed expressions are not part of a constraint 212 * (they will be copied when a constraint is created) 213 */ 214 SCIP_CALL( SCIPcreateExprVar(scip, basetree, var, ownercreate, ownercreatedata) ); 215 SCIP_CALL( SCIPhashmapInsert(vartoexprvarmap, (void*)var, (void*)(*basetree)) ); 216 } 217 } 218 else if( *expr == '(' ) 219 { 220 /* parse expression */ 221 SCIP_CALL( parseExpr(scip, vartoexprvarmap, ++expr, newpos, basetree, ownercreate, ownercreatedata) ); 222 expr = *newpos; 223 224 /* expect ')' */ 225 if( *expr != ')' ) 226 { 227 SCIPerrorMessage("Read a '(', parsed expression inside --> expecting closing ')'. Got <%c>: rest of string <%s>\n", *expr, expr); 228 SCIP_CALL( SCIPreleaseExpr(scip, basetree) ); 229 return SCIP_READERROR; 230 } 231 ++expr; 232 debugParse("Done parsing expression, continue with <%s>\n", expr); 233 } 234 else if( isdigit(*expr) ) 235 { 236 /* parse number */ 237 SCIP_Real value; 238 if( !SCIPstrToRealValue(expr, &value, (char**)&expr) ) 239 { 240 SCIPerrorMessage("error parsing number from <%s>\n", expr); 241 return SCIP_READERROR; 242 } 243 debugParse("Parsed value %g, creating a value-expression.\n", value); 244 SCIP_CALL( SCIPcreateExprValue(scip, basetree, value, ownercreate, ownercreatedata) ); 245 } 246 else if( isalpha(*expr) ) 247 { 248 /* a (function) name is coming, should find exprhandler with such name */ 249 int i; 250 char operatorname[SCIP_MAXSTRLEN]; 251 SCIP_EXPRHDLR* exprhdlr; 252 SCIP_Bool success; 253 254 /* get name */ 255 i = 0; 256 while( *expr != '(' && *expr != '\0' && !isspace(*expr) 257 && !( *expr == '\\' && *(expr+1) != '\0' && strchr(SCIP_SPACECONTROL, *(expr+1)) ) ) 258 { 259 operatorname[i] = *expr; 260 ++expr; 261 ++i; 262 } 263 operatorname[i] = '\0'; 264 265 /* after name we must see a '(' */ 266 if( *expr != '(' ) 267 { 268 SCIPerrorMessage("Expected '(' after operator name <%s>, but got %s.\n", operatorname, expr); 269 return SCIP_READERROR; 270 } 271 272 /* search for expression handler */ 273 exprhdlr = SCIPfindExprhdlr(scip, operatorname); 274 275 /* check expression handler exists and has a parsing method */ 276 if( exprhdlr == NULL ) 277 { 278 SCIPerrorMessage("No expression handler with name <%s> found.\n", operatorname); 279 return SCIP_READERROR; 280 } 281 282 ++expr; 283 SCIP_CALL( SCIPexprhdlrParseExpr(exprhdlr, scip->set, expr, newpos, basetree, &success, ownercreate, ownercreatedata) ); 284 285 if( !success ) 286 { 287 SCIPerrorMessage("Error while expression handler <%s> was parsing %s\n", operatorname, expr); 288 assert(*basetree == NULL); 289 return SCIP_READERROR; 290 } 291 expr = *newpos; 292 293 /* we should see the ')' of Op "(" OpExpression ") */ 294 assert(*expr == ')'); 295 296 /* move one character forward */ 297 ++expr; 298 } 299 else 300 { 301 /* Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ") */ 302 SCIPerrorMessage("Expected a number, (expression), <varname>, Opname(Opexpr), instead got <%c> from %s\n", *expr, expr); 303 return SCIP_READERROR; 304 } 305 306 *newpos = expr; 307 308 return SCIP_OKAY; 309 } 310 311 /** Parses a factor and builds a product-expression if there is an exponent, otherwise returns the base expression. 312 * <pre> 313 * Factor -> Base [ "^" "number" | "^(" "number" ")" ] 314 * </pre> 315 */ 316 static 317 SCIP_RETCODE parseFactor( 318 SCIP* scip, /**< SCIP data structure */ 319 SCIP_Bool isdenominator, /**< whether factor is in the denominator */ 320 SCIP_HASHMAP* vartoexprvarmap, /**< hashmap to map between scip vars and var expressions */ 321 const char* expr, /**< expr that we are parsing */ 322 const char** newpos, /**< buffer to store the position of expr where we finished reading */ 323 SCIP_EXPR** factortree, /**< buffer to store the expr parsed by Factor */ 324 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 325 void* ownercreatedata /**< data to pass to ownercreate */ 326 ) 327 { 328 SCIP_EXPR* basetree; 329 SCIP_Real exponent; 330 331 debugParse("parsing factor from %s\n", expr); 332 333 if( *expr == '\0' ) 334 { 335 SCIPerrorMessage("Unexpected end of expression string.\n"); 336 return SCIP_READERROR; 337 } 338 339 /* parse Base */ 340 /* ignore whitespace */ 341 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 342 343 SCIP_CALL( parseBase(scip, vartoexprvarmap, expr, newpos, &basetree, ownercreate, ownercreatedata) ); 344 expr = *newpos; 345 346 /* check if there is an exponent */ 347 /* ignore whitespace */ 348 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 349 350 if( *expr == '^' ) 351 { 352 ++expr; 353 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 354 355 if( *expr == '\0' ) 356 { 357 SCIPerrorMessage("Unexpected end of expression string after '^'.\n"); 358 SCIP_CALL( SCIPreleaseExpr(scip, &basetree) ); 359 return SCIP_READERROR; 360 } 361 362 if( *expr == '(' ) 363 { 364 ++expr; 365 366 /* it is exponent with parenthesis; expect number possibly starting with + or - */ 367 if( !SCIPstrToRealValue(expr, &exponent, (char**)&expr) ) 368 { 369 SCIPerrorMessage("error parsing number from <%s>\n", expr); 370 SCIP_CALL( SCIPreleaseExpr(scip, &basetree) ); 371 return SCIP_READERROR; 372 } 373 374 /* expect the ')' */ 375 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 376 if( *expr != ')' ) 377 { 378 SCIPerrorMessage("error in parsing exponent: expected ')', received <%c> from <%s>\n", *expr, expr); 379 SCIP_CALL( SCIPreleaseExpr(scip, &basetree) ); 380 return SCIP_READERROR; 381 } 382 ++expr; 383 } 384 else 385 { 386 /* no parenthesis, we should see just a positive number */ 387 388 /* expect a digit */ 389 if( isdigit(*expr) ) 390 { 391 if( !SCIPstrToRealValue(expr, &exponent, (char**)&expr) ) 392 { 393 SCIPerrorMessage("error parsing number from <%s>\n", expr); 394 SCIP_CALL( SCIPreleaseExpr(scip, &basetree) ); 395 return SCIP_READERROR; 396 } 397 } 398 else 399 { 400 SCIPerrorMessage("error in parsing exponent, expected a digit, received <%c> from <%s>\n", *expr, expr); 401 SCIP_CALL( SCIPreleaseExpr(scip, &basetree) ); 402 return SCIP_READERROR; 403 } 404 } 405 406 debugParse("parsed the exponent %g\n", exponent); /*lint !e506 !e681*/ 407 } 408 else 409 { 410 /* there is no explicit exponent */ 411 exponent = 1.0; 412 } 413 *newpos = expr; 414 415 /* multiply with -1 when we are in the denominator */ 416 if( isdenominator ) 417 exponent *= -1.0; 418 419 /* create power */ 420 if( exponent != 1.0 ) 421 { 422 SCIP_CALL( SCIPcreateExprPow(scip, factortree, basetree, exponent, ownercreate, ownercreatedata) ); 423 SCIP_CALL( SCIPreleaseExpr(scip, &basetree) ); 424 } 425 else 426 /* Factor consists of this unique Base */ 427 *factortree = basetree; 428 429 return SCIP_OKAY; 430 } 431 432 /** Parses a term and builds a product-expression, where each factor is a child. 433 * <pre> 434 * Term -> Factor { ("*" | "/" ) Factor } 435 * </pre> 436 */ 437 static 438 SCIP_RETCODE parseTerm( 439 SCIP* scip, /**< SCIP data structure */ 440 SCIP_HASHMAP* vartoexprvarmap, /**< hashmap to map between scip vars and var expressions */ 441 const char* expr, /**< expr that we are parsing */ 442 const char** newpos, /**< buffer to store the position of expr where we finished reading */ 443 SCIP_EXPR** termtree, /**< buffer to store the expr parsed by Term */ 444 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 445 void* ownercreatedata /**< data to pass to ownercreate */ 446 ) 447 { 448 SCIP_EXPR* factortree; 449 450 debugParse("parsing term from %s\n", expr); 451 452 /* parse Factor */ 453 /* ignore whitespace */ 454 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 455 456 SCIP_CALL( parseFactor(scip, FALSE, vartoexprvarmap, expr, newpos, &factortree, ownercreate, ownercreatedata) ); 457 expr = *newpos; 458 459 debugParse("back to parsing Term, continue parsing from %s\n", expr); 460 461 /* check if Terms has another Factor incoming */ 462 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 463 if( *expr == '*' || *expr == '/' ) 464 { 465 /* initialize termtree as a product expression with a single term, so we can append the extra Factors */ 466 SCIP_CALL( SCIPcreateExprProduct(scip, termtree, 1, &factortree, 1.0, ownercreate, ownercreatedata) ); 467 SCIP_CALL( SCIPreleaseExpr(scip, &factortree) ); 468 469 /* loop: parse Factor, find next symbol */ 470 do 471 { 472 SCIP_RETCODE retcode; 473 SCIP_Bool isdivision; 474 475 isdivision = (*expr == '/') ? TRUE : FALSE; 476 477 debugParse("while parsing term, read char %c\n", *expr); /*lint !e506 !e681*/ 478 479 ++expr; 480 retcode = parseFactor(scip, isdivision, vartoexprvarmap, expr, newpos, &factortree, ownercreate, ownercreatedata); 481 482 /* release termtree, if parseFactor fails with a read-error */ 483 if( retcode == SCIP_READERROR ) 484 { 485 SCIP_CALL( SCIPreleaseExpr(scip, termtree) ); 486 } 487 SCIP_CALL( retcode ); 488 489 /* append newly created factor */ 490 SCIP_CALL( SCIPappendExprChild(scip, *termtree, factortree) ); 491 SCIP_CALL( SCIPreleaseExpr(scip, &factortree) ); 492 493 /* find next symbol */ 494 expr = *newpos; 495 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 496 } 497 while( *expr == '*' || *expr == '/' ); 498 } 499 else 500 { 501 /* Term consists of this unique factor */ 502 *termtree = factortree; 503 } 504 505 *newpos = expr; 506 507 return SCIP_OKAY; 508 } 509 510 /** parses an expression and builds a sum-expression with children 511 * 512 * <pre> 513 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term } 514 * </pre> 515 */ 516 static 517 SCIP_RETCODE parseExpr( 518 SCIP* scip, /**< SCIP data structure */ 519 SCIP_HASHMAP* vartoexprvarmap, /**< hashmap to map between scip vars and var expressions */ 520 const char* expr, /**< expr that we are parsing */ 521 const char** newpos, /**< buffer to store the position of expr where we finished reading */ 522 SCIP_EXPR** exprtree, /**< buffer to store the expr parsed by Expr */ 523 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 524 void* ownercreatedata /**< data to pass to ownercreate */ 525 ) 526 { 527 SCIP_Real sign; 528 SCIP_EXPR* termtree; 529 530 debugParse("parsing expression %s\n", expr); /*lint !e506 !e681*/ 531 532 /* ignore whitespace */ 533 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 534 535 /* if '+' or '-', store it */ 536 sign = 1.0; 537 if( *expr == '+' || *expr == '-' ) 538 { 539 debugParse("while parsing expression, read char %c\n", *expr); /*lint !e506 !e681*/ 540 sign = *expr == '+' ? 1.0 : -1.0; 541 ++expr; 542 } 543 544 SCIP_CALL( parseTerm(scip, vartoexprvarmap, expr, newpos, &termtree, ownercreate, ownercreatedata) ); 545 expr = *newpos; 546 547 debugParse("back to parsing expression (we have the following term), continue parsing from %s\n", expr); /*lint !e506 !e681*/ 548 549 /* check if Expr has another Term incoming */ 550 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 551 if( *expr == '+' || *expr == '-' ) 552 { 553 if( SCIPexprIsValue(scip->set, termtree) ) 554 { 555 /* initialize exprtree as a sum expression with a constant only, so we can append the following terms */ 556 SCIP_CALL( SCIPcreateExprSum(scip, exprtree, 0, NULL, NULL, sign * SCIPgetValueExprValue(termtree), ownercreate, ownercreatedata) ); 557 SCIP_CALL( SCIPreleaseExpr(scip, &termtree) ); 558 } 559 else 560 { 561 /* initialize exprtree as a sum expression with a single term, so we can append the following terms */ 562 SCIP_CALL( SCIPcreateExprSum(scip, exprtree, 1, &termtree, &sign, 0.0, ownercreate, ownercreatedata) ); 563 SCIP_CALL( SCIPreleaseExpr(scip, &termtree) ); 564 } 565 566 /* loop: parse Term, find next symbol */ 567 do 568 { 569 SCIP_RETCODE retcode; 570 SCIP_Real coef; 571 572 /* check if we have a "coef * <term>" */ 573 if( SCIPstrToRealValue(expr, &coef, (char**)newpos) ) 574 { 575 SCIP_CALL( SCIPskipSpace((char**)newpos) ); 576 577 if( **newpos != '*' ) 578 { 579 /* no '*', so fall back to parsing term after sign */ 580 coef = (*expr == '+') ? 1.0 : -1.0; 581 ++expr; 582 } 583 else 584 { 585 /* keep coefficient in coef and continue parsing term after coefficient */ 586 expr = (*newpos)+1; 587 588 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 589 } 590 } 591 else 592 { 593 coef = (*expr == '+') ? 1.0 : -1.0; 594 ++expr; 595 } 596 597 debugParse("while parsing expression, read coefficient %g\n", coef); /*lint !e506 !e681*/ 598 599 retcode = parseTerm(scip, vartoexprvarmap, expr, newpos, &termtree, ownercreate, ownercreatedata); 600 601 /* release exprtree if parseTerm fails with an read-error */ 602 if( retcode == SCIP_READERROR ) 603 { 604 SCIP_CALL( SCIPreleaseExpr(scip, exprtree) ); 605 } 606 SCIP_CALL( retcode ); 607 608 /* append newly created term */ 609 SCIP_CALL( SCIPappendExprSumExpr(scip, *exprtree, termtree, coef) ); 610 SCIP_CALL( SCIPreleaseExpr(scip, &termtree) ); 611 612 /* find next symbol */ 613 expr = *newpos; 614 SCIP_CALL( SCIPskipSpace((char**)&expr) ); 615 } while( *expr == '+' || *expr == '-' ); 616 } 617 else 618 { 619 /* Expr consists of this unique ['+' | '-'] Term */ 620 if( sign < 0.0 ) 621 { 622 assert(sign == -1.0); 623 SCIP_CALL( SCIPcreateExprSum(scip, exprtree, 1, &termtree, &sign, 0.0, ownercreate, ownercreatedata) ); 624 SCIP_CALL( SCIPreleaseExpr(scip, &termtree) ); 625 } 626 else 627 *exprtree = termtree; 628 } 629 630 *newpos = expr; 631 632 return SCIP_OKAY; 633 } 634 635 /** @} */ /* end of parsing methods */ 636 637 /** @name Simplify methods (internal) 638 * @{ 639 */ 640 641 /** returns an equivalent expression for a given expression if possible 642 * 643 * it adds the expression to key2expr if the map does not contain the key 644 */ 645 static 646 SCIP_RETCODE findEqualExpr( 647 SCIP_SET* set, /**< global SCIP settings */ 648 SCIP_EXPR* expr, /**< expression to replace */ 649 SCIP_MULTIHASH* key2expr, /**< mapping of hashes to expressions */ 650 SCIP_EXPR** newexpr /**< pointer to store an equivalent expression (NULL if there is none) */ 651 ) 652 { /*lint --e{438}*/ 653 SCIP_MULTIHASHLIST* multihashlist; 654 655 assert(set != NULL); 656 assert(expr != NULL); 657 assert(key2expr != NULL); 658 assert(newexpr != NULL); 659 660 *newexpr = NULL; 661 multihashlist = NULL; 662 do 663 { 664 /* search for an equivalent expression */ 665 *newexpr = (SCIP_EXPR*)(SCIPmultihashRetrieveNext(key2expr, &multihashlist, (void*)expr)); 666 667 if( *newexpr == NULL ) 668 { 669 /* processed all expressions like expr from hash table, so insert expr */ 670 SCIP_CALL( SCIPmultihashInsert(key2expr, (void*) expr) ); 671 break; 672 } 673 else if( expr != *newexpr ) 674 { 675 assert(SCIPexprCompare(set, expr, *newexpr) == 0); 676 break; 677 } 678 else 679 { 680 /* can not replace expr since it is already contained in the hashtablelist */ 681 assert(expr == *newexpr); 682 *newexpr = NULL; 683 break; 684 } 685 } 686 while( TRUE ); /*lint !e506*/ 687 688 return SCIP_OKAY; 689 } 690 691 /** userdata for multihash for common subexpression */ 692 typedef struct 693 { 694 SCIP_SET* set; 695 SCIP_EXPRITER* hashiterator; 696 } COMMONSUBEXPR_HASH_DATA; 697 698 /** get key of hash element */ 699 static 700 SCIP_DECL_HASHGETKEY(hashCommonSubexprGetKey) 701 { 702 return elem; 703 } /*lint !e715*/ 704 705 /** checks if two expressions are structurally the same */ 706 static 707 SCIP_DECL_HASHKEYEQ(hashCommonSubexprEq) 708 { 709 COMMONSUBEXPR_HASH_DATA* data; 710 SCIP_EXPR* expr1; 711 SCIP_EXPR* expr2; 712 713 data = (COMMONSUBEXPR_HASH_DATA*)userptr; 714 assert(data != NULL); 715 716 expr1 = (SCIP_EXPR*)key1; 717 expr2 = (SCIP_EXPR*)key2; 718 assert(expr1 != NULL); 719 assert(expr2 != NULL); 720 721 return expr1 == expr2 || SCIPexprCompare(data->set, expr1, expr2) == 0; 722 } /*lint !e715*/ 723 724 /** get value of hash element when comparing with another expression */ 725 static 726 SCIP_DECL_HASHKEYVAL(hashCommonSubexprKeyval) 727 { 728 COMMONSUBEXPR_HASH_DATA* data; 729 SCIP_EXPR* expr; 730 731 expr = (SCIP_EXPR*) key; 732 assert(expr != NULL); 733 734 data = (COMMONSUBEXPR_HASH_DATA*) userptr; 735 assert(data != NULL); 736 737 return SCIPexpriterGetExprUserData(data->hashiterator, expr).uintval; 738 } /*lint !e715*/ 739 740 /** hashes an expression using an already existing iterator 741 * 742 * The iterator must by of type DFS with allowrevisit=FALSE and only the leaveexpr stage enabled. 743 * The hashes of all visited expressions will be stored in the iterators expression data. 744 */ 745 static 746 SCIP_RETCODE hashExpr( 747 SCIP_SET* set, /**< global SCIP settings */ 748 BMS_BUFMEM* bufmem, /**< buffer memory */ 749 SCIP_EXPR* expr, /**< expression to hash */ 750 SCIP_EXPRITER* hashiterator, /**< iterator to use for hashing */ 751 int* nvisitedexprs /**< counter to increment by the number of expressions visited, or NULL */ 752 ) 753 { 754 SCIP_EXPRITER_USERDATA iterdata; 755 unsigned int* childrenhashes; 756 int childrenhashessize; 757 int i; 758 759 assert(set != NULL); 760 assert(expr != NULL); 761 assert(hashiterator != NULL); 762 763 childrenhashessize = 5; 764 SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &childrenhashes, childrenhashessize) ); 765 766 for( expr = SCIPexpriterRestartDFS(hashiterator, expr); !SCIPexpriterIsEnd(hashiterator); expr = SCIPexpriterGetNext(hashiterator) ) /*lint !e441*/ 767 { 768 assert(SCIPexpriterGetStageDFS(hashiterator) == SCIP_EXPRITER_LEAVEEXPR); 769 770 if( nvisitedexprs != NULL ) 771 ++*nvisitedexprs; 772 773 /* collect hashes of children */ 774 if( childrenhashessize < SCIPexprGetNChildren(expr) ) 775 { 776 childrenhashessize = SCIPsetCalcMemGrowSize(set, SCIPexprGetNChildren(expr)); 777 SCIP_ALLOC( BMSreallocBufferMemoryArray(bufmem, &childrenhashes, childrenhashessize) ); 778 } 779 for( i = 0; i < SCIPexprGetNChildren(expr); ++i ) 780 childrenhashes[i] = SCIPexpriterGetExprUserData(hashiterator, SCIPexprGetChildren(expr)[i]).uintval; 781 782 SCIP_CALL( SCIPexprhdlrHashExpr(SCIPexprGetHdlr(expr), set, expr, &iterdata.uintval, childrenhashes) ); 783 784 SCIPexpriterSetCurrentUserData(hashiterator, iterdata); 785 } 786 787 BMSfreeBufferMemoryArray(bufmem, &childrenhashes); 788 789 return SCIP_OKAY; 790 } 791 792 /** @} */ /* end of simplify methods */ 793 794 /* 795 * public functions 796 */ 797 798 /**@addtogroup PublicExprHandlerMethods 799 * @{ 800 */ 801 802 #ifdef NDEBUG 803 #undef SCIPgetExprhdlrs 804 #undef SCIPgetNExprhdlrs 805 #undef SCIPfindExprhdlr 806 #undef SCIPgetExprhdlrVar 807 #undef SCIPgetExprhdlrValue 808 #undef SCIPgetExprhdlrSum 809 #undef SCIPgetExprhdlrProduct 810 #undef SCIPgetExprhdlrPower 811 #endif 812 813 /** creates the handler for an expression handler and includes it into SCIP */ 814 SCIP_RETCODE SCIPincludeExprhdlr( 815 SCIP* scip, /**< SCIP data structure */ 816 SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */ 817 const char* name, /**< name of expression handler (must not be NULL) */ 818 const char* desc, /**< description of expression handler (can be NULL) */ 819 unsigned int precedence, /**< precedence of expression operation (used for printing) */ 820 SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */ 821 SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */ 822 ) 823 { 824 assert(scip != NULL); 825 assert(scip->mem != NULL); 826 assert(exprhdlr != NULL); 827 828 SCIP_CALL( SCIPexprhdlrCreate(scip->mem->setmem, exprhdlr, name, desc, precedence, eval, data) ); 829 assert(*exprhdlr != NULL); 830 831 SCIP_CALL( SCIPsetIncludeExprhdlr(scip->set, *exprhdlr) ); 832 833 return SCIP_OKAY; 834 } 835 836 /** gives expression handlers */ 837 SCIP_EXPRHDLR** SCIPgetExprhdlrs( 838 SCIP* scip /**< SCIP data structure */ 839 ) 840 { 841 assert(scip != NULL); 842 assert(scip->set != NULL); 843 844 return scip->set->exprhdlrs; 845 } 846 847 /** gives number of expression handlers */ 848 int SCIPgetNExprhdlrs( 849 SCIP* scip /**< SCIP data structure */ 850 ) 851 { 852 assert(scip != NULL); 853 assert(scip->set != NULL); 854 855 return scip->set->nexprhdlrs; 856 } 857 858 /** returns an expression handler of a given name (or NULL if not found) */ 859 SCIP_EXPRHDLR* SCIPfindExprhdlr( 860 SCIP* scip, /**< SCIP data structure */ 861 const char* name /**< name of expression handler */ 862 ) 863 { 864 assert(scip != NULL); 865 assert(scip->set != NULL); 866 867 return SCIPsetFindExprhdlr(scip->set, name); 868 } 869 870 /** returns expression handler for variable expressions (or NULL if not included) */ 871 SCIP_EXPRHDLR* SCIPgetExprhdlrVar( 872 SCIP* scip /**< SCIP data structure */ 873 ) 874 { 875 assert(scip != NULL); 876 assert(scip->set != NULL); 877 878 return scip->set->exprhdlrvar; 879 } 880 881 /** returns expression handler for constant value expressions (or NULL if not included) */ 882 SCIP_EXPRHDLR* SCIPgetExprhdlrValue( 883 SCIP* scip /**< SCIP data structure */ 884 ) 885 { 886 assert(scip != NULL); 887 assert(scip->set != NULL); 888 889 return scip->set->exprhdlrval; 890 } 891 892 /** returns expression handler for sum expressions (or NULL if not included) */ 893 SCIP_EXPRHDLR* SCIPgetExprhdlrSum( 894 SCIP* scip /**< SCIP data structure */ 895 ) 896 { 897 assert(scip != NULL); 898 assert(scip->set != NULL); 899 900 return scip->set->exprhdlrsum; 901 } 902 903 /** returns expression handler for product expressions (or NULL if not included) */ 904 SCIP_EXPRHDLR* SCIPgetExprhdlrProduct( 905 SCIP* scip /**< SCIP data structure */ 906 ) 907 { 908 assert(scip != NULL); 909 assert(scip->set != NULL); 910 911 return scip->set->exprhdlrproduct; 912 } 913 914 /** returns expression handler for power expressions (or NULL if not included) */ 915 SCIP_EXPRHDLR* SCIPgetExprhdlrPower( 916 SCIP* scip /**< SCIP data structure */ 917 ) 918 { 919 assert(scip != NULL); 920 assert(scip->set != NULL); 921 922 return scip->set->exprhdlrpow; 923 } 924 925 /**@} */ 926 927 928 /**@name Expression Methods */ 929 /**@{ */ 930 931 #ifdef NDEBUG 932 #undef SCIPappendExprChild 933 #undef SCIPreplaceExprChild 934 #undef SCIPremoveExprChildren 935 #undef SCIPduplicateExpr 936 #undef SCIPduplicateExprShallow 937 #undef SCIPcaptureExpr 938 #undef SCIPreleaseExpr 939 #undef SCIPisExprVar 940 #undef SCIPisExprValue 941 #undef SCIPisExprSum 942 #undef SCIPisExprProduct 943 #undef SCIPisExprPower 944 #undef SCIPprintExpr 945 #undef SCIPevalExpr 946 #undef SCIPgetExprNewSoltag 947 #undef SCIPevalExprGradient 948 #undef SCIPevalExprHessianDir 949 #undef SCIPevalExprActivity 950 #undef SCIPcompareExpr 951 #undef SCIPsimplifyExpr 952 #undef SCIPcallExprCurvature 953 #undef SCIPcallExprMonotonicity 954 #undef SCIPcallExprEval 955 #undef SCIPcallExprEvalFwdiff 956 #undef SCIPcallExprInteval 957 #undef SCIPcallExprEstimate 958 #undef SCIPcallExprInitestimates 959 #undef SCIPcallExprSimplify 960 #undef SCIPcallExprReverseprop 961 #undef SCIPcallExprGetSymData 962 #endif 963 964 /** creates and captures an expression with given expression data and children */ 965 SCIP_RETCODE SCIPcreateExpr( 966 SCIP* scip, /**< SCIP data structure */ 967 SCIP_EXPR** expr, /**< pointer where to store expression */ 968 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 969 SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */ 970 int nchildren, /**< number of children */ 971 SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */ 972 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 973 void* ownercreatedata /**< data to pass to ownercreate */ 974 ) 975 { 976 assert(scip != NULL); 977 assert(scip->set != NULL); 978 979 SCIP_CALL( SCIPexprCreate(scip->set, scip->mem->probmem, expr, exprhdlr, exprdata, nchildren, children, ownercreate, 980 ownercreatedata) ); 981 982 return SCIP_OKAY; 983 } 984 985 /** creates and captures an expression with given expression data and up to two children */ 986 SCIP_RETCODE SCIPcreateExpr2( 987 SCIP* scip, /**< SCIP data structure */ 988 SCIP_EXPR** expr, /**< pointer where to store expression */ 989 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */ 990 SCIP_EXPRDATA* exprdata, /**< expression data */ 991 SCIP_EXPR* child1, /**< first child (can be NULL) */ 992 SCIP_EXPR* child2, /**< second child (can be NULL) */ 993 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 994 void* ownercreatedata /**< data to pass to ownercreate */ 995 ) 996 { 997 assert(scip != NULL); 998 assert(expr != NULL); 999 assert(exprhdlr != NULL); 1000 1001 if( child1 != NULL && child2 != NULL ) 1002 { 1003 SCIP_EXPR* pair[2]; 1004 pair[0] = child1; 1005 pair[1] = child2; 1006 1007 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 2, pair, ownercreate, ownercreatedata) ); 1008 } 1009 else if( child2 == NULL ) 1010 { 1011 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, child1 == NULL ? 0 : 1, &child1, ownercreate, 1012 ownercreatedata) ); 1013 } 1014 else 1015 { 1016 /* child2 != NULL, child1 == NULL */ 1017 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 1, &child2, ownercreate, ownercreatedata) ); 1018 } 1019 1020 return SCIP_OKAY; 1021 } 1022 1023 /** creates and captures an expression representing a quadratic function */ 1024 SCIP_RETCODE SCIPcreateExprQuadratic( 1025 SCIP* scip, /**< SCIP data structure */ 1026 SCIP_EXPR** expr, /**< pointer where to store expression */ 1027 int nlinvars, /**< number of linear terms */ 1028 SCIP_VAR** linvars, /**< array with variables in linear part */ 1029 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part */ 1030 int nquadterms, /**< number of quadratic terms */ 1031 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms */ 1032 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms */ 1033 SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms */ 1034 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 1035 void* ownercreatedata /**< data to pass to ownercreate */ 1036 ) 1037 { 1038 SCIP_EXPR** children; 1039 SCIP_Real* coefs; 1040 int i; 1041 1042 assert(scip != NULL); 1043 assert(expr != NULL); 1044 assert(nlinvars == 0 || (linvars != NULL && lincoefs != NULL)); 1045 assert(nquadterms == 0 || (quadvars1 != NULL && quadvars2 != NULL && quadcoefs != NULL)); 1046 1047 /* allocate memory */ 1048 SCIP_CALL( SCIPallocBufferArray(scip, &children, nquadterms + nlinvars) ); 1049 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nquadterms + nlinvars) ); 1050 1051 /* create children for quadratic terms */ 1052 for( i = 0; i < nquadterms; ++i ) 1053 { 1054 assert(quadvars1 != NULL && quadvars1[i] != NULL); 1055 assert(quadvars2 != NULL && quadvars2[i] != NULL); 1056 1057 /* quadratic term */ 1058 if( quadvars1[i] == quadvars2[i] ) 1059 { 1060 SCIP_EXPR* xexpr; 1061 1062 /* create variable expression; intentionally not using createExprVar here, 1063 * since expression created here is not part of a constraint (they will be copied when a constraint is created) 1064 */ 1065 SCIP_CALL( SCIPcreateExprVar(scip, &xexpr, quadvars1[i], ownercreate, ownercreatedata) ); 1066 1067 /* create pow expression */ 1068 SCIP_CALL( SCIPcreateExprPow(scip, &children[i], xexpr, 2.0, ownercreate, ownercreatedata) ); 1069 1070 /* release variable expression; note that the variable expression is still captured by children[i] */ 1071 SCIP_CALL( SCIPreleaseExpr(scip, &xexpr) ); 1072 } 1073 else /* bilinear term */ 1074 { 1075 SCIP_EXPR* exprs[2]; 1076 1077 /* create variable expressions; intentionally not using createExprVar here, 1078 * since expression created here is not part of a constraint (they will be copied when a constraint is created) 1079 */ 1080 SCIP_CALL( SCIPcreateExprVar(scip, &exprs[0], quadvars1[i], ownercreate, ownercreatedata) ); 1081 SCIP_CALL( SCIPcreateExprVar(scip, &exprs[1], quadvars2[i], ownercreate, ownercreatedata) ); 1082 1083 /* create product expression */ 1084 SCIP_CALL( SCIPcreateExprProduct(scip, &children[i], 2, exprs, 1.0, ownercreate, ownercreatedata) ); 1085 1086 /* release variable expressions; note that the variable expressions are still captured by children[i] */ 1087 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[1]) ); 1088 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[0]) ); 1089 } 1090 1091 /* store coefficient */ 1092 coefs[i] = quadcoefs[i]; 1093 } 1094 1095 /* create children for linear terms */ 1096 for( i = 0; i < nlinvars; ++i ) 1097 { 1098 assert(linvars != NULL && linvars[i] != NULL); 1099 1100 /* create variable expression; intentionally not using createExprVar here, 1101 * since expression created here is not part of a constraint (they will be copied when a constraint is created); 1102 * release variable expression after the sum expression has been created 1103 */ 1104 SCIP_CALL( SCIPcreateExprVar(scip, &children[nquadterms + i], linvars[i], ownercreate, ownercreatedata) ); 1105 1106 /* store coefficient */ 1107 coefs[nquadterms + i] = lincoefs[i]; 1108 } 1109 1110 /* create sum expression */ 1111 SCIP_CALL( SCIPcreateExprSum(scip, expr, nquadterms + nlinvars, children, coefs, 0.0, ownercreate, ownercreatedata) ); 1112 1113 /* release children */ 1114 for( i = 0; i < nquadterms + nlinvars; ++i ) 1115 { 1116 assert(children[i] != NULL); 1117 SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) ); 1118 } 1119 1120 /* free memory */ 1121 SCIPfreeBufferArray(scip, &coefs); 1122 SCIPfreeBufferArray(scip, &children); 1123 1124 return SCIP_OKAY; 1125 } 1126 1127 /** creates and captures an expression representing a monomial 1128 * 1129 * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents. 1130 * So this function actually creates an expression for a signomial that has exactly one term. 1131 */ 1132 SCIP_RETCODE SCIPcreateExprMonomial( 1133 SCIP* scip, /**< SCIP data structure */ 1134 SCIP_EXPR** expr, /**< pointer where to store expression */ 1135 int nfactors, /**< number of factors in monomial */ 1136 SCIP_VAR** vars, /**< variables in the monomial */ 1137 SCIP_Real* exponents, /**< exponent in each factor, or NULL if all 1.0 */ 1138 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 1139 void* ownercreatedata /**< data to pass to ownercreate */ 1140 ) 1141 { 1142 assert(scip != NULL); 1143 assert(expr != NULL); 1144 assert(nfactors >= 0); 1145 1146 /* return 1 as constant expression if there are no factors */ 1147 if( nfactors == 0 ) 1148 { 1149 SCIP_CALL( SCIPcreateExprValue(scip, expr, 1.0, ownercreate, ownercreatedata) ); 1150 } 1151 else if( nfactors == 1 ) 1152 { 1153 /* only one factor and exponent is 1 => return factors[0] */ 1154 if( exponents == NULL || exponents[0] == 1.0 ) 1155 { 1156 /* intentionally not using createExprVar here, since expression created here is not part of 1157 * a constraint (they will be copied when a constraint is created) 1158 */ 1159 SCIP_CALL( SCIPcreateExprVar(scip, expr, vars[0], ownercreate, ownercreatedata) ); 1160 } 1161 else 1162 { 1163 SCIP_EXPR* varexpr; 1164 1165 /* create variable and power expression; intentionally not using createExprVar here, 1166 * since expression created here is not part of a constraint (they will be copied when a constraint is created) 1167 */ 1168 SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, vars[0], ownercreate, ownercreatedata) ); 1169 SCIP_CALL( SCIPcreateExprPow(scip, expr, varexpr, exponents[0], ownercreate, ownercreatedata) ); 1170 SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) ); 1171 } 1172 } 1173 else 1174 { 1175 SCIP_EXPR** children; 1176 int i; 1177 1178 /* allocate memory to store the children */ 1179 SCIP_CALL( SCIPallocBufferArray(scip, &children, nfactors) ); 1180 1181 /* create children */ 1182 for( i = 0; i < nfactors; ++i ) 1183 { 1184 /* check whether to create a power expression or not, i.e., exponent == 1 */ 1185 if( exponents == NULL || exponents[i] == 1.0 ) 1186 { 1187 SCIP_CALL( SCIPcreateExprVar(scip, &children[i], vars[i], ownercreate, ownercreatedata) ); 1188 } 1189 else 1190 { 1191 SCIP_EXPR* varexpr; 1192 1193 /* create variable and pow expression */ 1194 SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, vars[i], ownercreate, ownercreatedata) ); 1195 SCIP_CALL( SCIPcreateExprPow(scip, &children[i], varexpr, exponents[i], ownercreate, ownercreatedata) ); 1196 SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) ); 1197 } 1198 } 1199 1200 /* create product expression */ 1201 SCIP_CALL( SCIPcreateExprProduct(scip, expr, nfactors, children, 1.0, ownercreate, ownercreatedata) ); 1202 1203 /* release children */ 1204 for( i = 0; i < nfactors; ++i ) 1205 { 1206 assert(children[i] != NULL); 1207 SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) ); 1208 } 1209 1210 /* free memory */ 1211 SCIPfreeBufferArray(scip, &children); 1212 } 1213 1214 return SCIP_OKAY; 1215 } 1216 1217 /** appends child to the children list of expr 1218 * 1219 * @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. 1220 */ 1221 SCIP_RETCODE SCIPappendExprChild( 1222 SCIP* scip, /**< SCIP data structure */ 1223 SCIP_EXPR* expr, /**< expression */ 1224 SCIP_EXPR* child /**< expression to be appended */ 1225 ) 1226 { 1227 assert(scip != NULL); 1228 assert(scip->mem != NULL); 1229 1230 SCIP_CALL( SCIPexprAppendChild(scip->set, scip->mem->probmem, expr, child) ); 1231 1232 return SCIP_OKAY; 1233 } 1234 1235 /** overwrites/replaces a child of an expressions 1236 * 1237 * The old child is released and the newchild is captured, unless they are the same (=same pointer). 1238 */ 1239 SCIP_RETCODE SCIPreplaceExprChild( 1240 SCIP* scip, /**< SCIP data structure */ 1241 SCIP_EXPR* expr, /**< expression which is going to replace a child */ 1242 int childidx, /**< index of child being replaced */ 1243 SCIP_EXPR* newchild /**< the new child */ 1244 ) 1245 { 1246 assert(scip != NULL); 1247 assert(scip->mem != NULL); 1248 1249 SCIP_CALL( SCIPexprReplaceChild(scip->set, scip->stat, scip->mem->probmem, expr, childidx, newchild) ); 1250 1251 return SCIP_OKAY; 1252 } 1253 1254 /** remove all children of expr 1255 * 1256 * @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. 1257 */ 1258 SCIP_RETCODE SCIPremoveExprChildren( 1259 SCIP* scip, /**< SCIP data structure */ 1260 SCIP_EXPR* expr /**< expression */ 1261 ) 1262 { 1263 assert(scip != NULL); 1264 assert(scip->mem != NULL); 1265 1266 SCIP_CALL( SCIPexprRemoveChildren(scip->set, scip->stat, scip->mem->probmem, expr) ); 1267 1268 return SCIP_OKAY; 1269 } 1270 1271 /** duplicates the given expression and its children */ 1272 SCIP_RETCODE SCIPduplicateExpr( 1273 SCIP* scip, /**< SCIP data structure */ 1274 SCIP_EXPR* expr, /**< original expression */ 1275 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */ 1276 SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */ 1277 void* mapexprdata, /**< data of expression mapping function */ 1278 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 1279 void* ownercreatedata /**< data to pass to ownercreate */ 1280 ) 1281 { 1282 assert(scip != NULL); 1283 assert(scip->mem != NULL); 1284 1285 SCIP_CALL( SCIPexprCopy(scip->set, scip->stat, scip->mem->probmem, scip->set, scip->stat, scip->mem->probmem, 1286 expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) ); 1287 1288 return SCIP_OKAY; 1289 } 1290 1291 /** duplicates the given expression, but reuses its children */ 1292 SCIP_RETCODE SCIPduplicateExprShallow( 1293 SCIP* scip, /**< SCIP data structure */ 1294 SCIP_EXPR* expr, /**< original expression */ 1295 SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */ 1296 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 1297 void* ownercreatedata /**< data to pass to ownercreate */ 1298 ) 1299 { 1300 assert(scip != NULL); 1301 assert(scip->mem != NULL); 1302 1303 SCIP_CALL( SCIPexprDuplicateShallow(scip->set, scip->mem->probmem, expr, copyexpr, ownercreate, ownercreatedata) ); 1304 1305 return SCIP_OKAY; 1306 } 1307 1308 /** copies an expression including children to use in a (possibly different) SCIP instance */ 1309 SCIP_RETCODE SCIPcopyExpr( 1310 SCIP* sourcescip, /**< source SCIP data structure */ 1311 SCIP* targetscip, /**< target SCIP data structure */ 1312 SCIP_EXPR* expr, /**< original expression */ 1313 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */ 1314 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */ 1315 void* ownercreatedata, /**< data to pass to ownercreate */ 1316 SCIP_HASHMAP* varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding 1317 * variables of the target SCIP, or NULL */ 1318 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding 1319 * target constraints, or NULL */ 1320 SCIP_Bool global, /**< create a global or a local copy? */ 1321 SCIP_Bool* valid /**< pointer to store whether all checked or enforced constraints were validly copied */ 1322 ) 1323 { 1324 #ifndef _MSC_VER 1325 COPY_MAPEXPR_DATA copydata = { 1326 .varmap = varmap, 1327 .consmap = consmap, 1328 .global = global, 1329 .valid = TRUE 1330 }; 1331 #else /* MS compiler doesn't have proper C99 support... */ 1332 COPY_MAPEXPR_DATA copydata; 1333 copydata.varmap = varmap; 1334 copydata.consmap = consmap; 1335 copydata.global = global; 1336 copydata.valid = TRUE; 1337 #endif 1338 1339 assert(sourcescip != NULL); 1340 assert(sourcescip->mem != NULL); 1341 assert(targetscip != NULL); 1342 assert(targetscip->mem != NULL); 1343 1344 SCIP_CALL( SCIPexprCopy(sourcescip->set, sourcescip->stat, sourcescip->mem->probmem, 1345 targetscip->set, targetscip->stat, targetscip->mem->probmem, 1346 expr, copyexpr, copyVarExpr, ©data, ownercreate, ownercreatedata) ); 1347 1348 *valid = copydata.valid; 1349 1350 return SCIP_OKAY; 1351 } 1352 1353 /** creates an expression from a string 1354 * 1355 * We specify the grammar that defines the syntax of an expression. 1356 * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power, 1357 * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`. 1358 * 1359 * The actual definition: 1360 * <pre> 1361 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term } 1362 * Term -> Factor { ("*" | "/" ) Factor } 1363 * Factor -> Base [ "^" "number" | "^(" "number" ")" ] 1364 * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ") 1365 * </pre> 1366 * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`. 1367 * 1368 * Note that `Op` and `OpExpression` are undefined. 1369 * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method). 1370 */ 1371 SCIP_RETCODE SCIPparseExpr( 1372 SCIP* scip, /**< SCIP data structure */ 1373 SCIP_EXPR** expr, /**< pointer to store the expr parsed */ 1374 const char* exprstr, /**< string with the expr to parse */ 1375 const char** finalpos, /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */ 1376 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 1377 void* ownercreatedata /**< data to pass to ownercreate */ 1378 ) 1379 { 1380 const char* finalpos_; 1381 SCIP_RETCODE retcode; 1382 SCIP_HASHMAP* vartoexprvarmap; 1383 1384 assert(scip != NULL); 1385 1386 SCIP_CALL( SCIPhashmapCreate(&vartoexprvarmap, SCIPblkmem(scip), 5 * SCIPgetNVars(scip)) ); 1387 1388 /* if parseExpr fails, we still want to free hashmap */ 1389 retcode = parseExpr(scip, vartoexprvarmap, exprstr, &finalpos_, expr, ownercreate, ownercreatedata); 1390 1391 SCIPhashmapFree(&vartoexprvarmap); 1392 1393 if( finalpos != NULL ) 1394 *finalpos = finalpos_; 1395 1396 return retcode; 1397 } 1398 1399 /** captures an expression (increments usage count) */ 1400 void SCIPcaptureExpr( 1401 SCIP_EXPR* expr /**< expression to be captured */ 1402 ) 1403 { 1404 SCIPexprCapture(expr); 1405 } 1406 1407 /** releases an expression (decrements usage count and possibly frees expression) */ 1408 SCIP_RETCODE SCIPreleaseExpr( 1409 SCIP* scip, /**< SCIP data structure */ 1410 SCIP_EXPR** expr /**< pointer to expression to be released */ 1411 ) 1412 { 1413 assert(scip != NULL); 1414 assert(scip->mem != NULL); 1415 1416 SCIP_CALL( SCIPexprRelease(scip->set, scip->stat, scip->mem->probmem, expr) ); 1417 1418 return SCIP_OKAY; 1419 } 1420 1421 /** returns whether an expression is a variable expression */ 1422 SCIP_Bool SCIPisExprVar( 1423 SCIP* scip, /**< SCIP data structure */ 1424 SCIP_EXPR* expr /**< expression */ 1425 ) 1426 { 1427 assert(scip != NULL); 1428 1429 return SCIPexprIsVar(scip->set, expr); 1430 } 1431 1432 /** returns whether an expression is a value expression */ 1433 SCIP_Bool SCIPisExprValue( 1434 SCIP* scip, /**< SCIP data structure */ 1435 SCIP_EXPR* expr /**< expression */ 1436 ) 1437 { 1438 assert(scip != NULL); 1439 1440 return SCIPexprIsValue(scip->set, expr); 1441 } 1442 1443 /** returns whether an expression is a sum expression */ 1444 SCIP_Bool SCIPisExprSum( 1445 SCIP* scip, /**< SCIP data structure */ 1446 SCIP_EXPR* expr /**< expression */ 1447 ) 1448 { 1449 assert(scip != NULL); 1450 1451 return SCIPexprIsSum(scip->set, expr); 1452 } 1453 1454 /** returns whether an expression is a product expression */ 1455 SCIP_Bool SCIPisExprProduct( 1456 SCIP* scip, /**< SCIP data structure */ 1457 SCIP_EXPR* expr /**< expression */ 1458 ) 1459 { 1460 assert(scip != NULL); 1461 1462 return SCIPexprIsProduct(scip->set, expr); 1463 } 1464 1465 /** returns whether an expression is a power expression */ 1466 SCIP_Bool SCIPisExprPower( 1467 SCIP* scip, /**< SCIP data structure */ 1468 SCIP_EXPR* expr /**< expression */ 1469 ) 1470 { 1471 assert(scip != NULL); 1472 1473 return SCIPexprIsPower(scip->set, expr); 1474 } 1475 1476 /** print an expression as info-message */ 1477 SCIP_RETCODE SCIPprintExpr( 1478 SCIP* scip, /**< SCIP data structure */ 1479 SCIP_EXPR* expr, /**< expression to be printed */ 1480 FILE* file /**< file to print to, or NULL for stdout */ 1481 ) 1482 { 1483 assert(scip != NULL); 1484 assert(scip->mem != NULL); 1485 1486 SCIP_CALL( SCIPexprPrint(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) ); 1487 1488 return SCIP_OKAY; 1489 } 1490 1491 /** initializes printing of expressions in dot format to a give FILE* pointer */ 1492 SCIP_RETCODE SCIPprintExprDotInit( 1493 SCIP* scip, /**< SCIP data structure */ 1494 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */ 1495 FILE* file, /**< file to print to, or NULL for stdout */ 1496 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */ 1497 ) 1498 { 1499 assert(scip != NULL); 1500 assert(scip->mem != NULL); 1501 1502 SCIP_CALL( SCIPexprPrintDotInit(scip->set, scip->stat, scip->mem->probmem, printdata, file, whattoprint) ); 1503 1504 return SCIP_OKAY; 1505 } 1506 1507 /** initializes printing of expressions in dot format to a file with given filename */ 1508 SCIP_RETCODE SCIPprintExprDotInit2( 1509 SCIP* scip, /**< SCIP data structure */ 1510 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */ 1511 const char* filename, /**< name of file to print to */ 1512 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */ 1513 ) 1514 { 1515 assert(scip != NULL); 1516 assert(scip->mem != NULL); 1517 1518 SCIP_CALL( SCIPexprPrintDotInit2(scip->set, scip->stat, scip->mem->probmem, printdata, filename, whattoprint) ); 1519 1520 return SCIP_OKAY; 1521 } 1522 1523 /** main part of printing an expression in dot format */ 1524 SCIP_RETCODE SCIPprintExprDot( 1525 SCIP* scip, /**< SCIP data structure */ 1526 SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */ 1527 SCIP_EXPR* expr /**< expression to be printed */ 1528 ) 1529 { 1530 assert(scip != NULL); 1531 1532 SCIP_CALL( SCIPexprPrintDot(scip->set, scip->messagehdlr, printdata, expr) ); 1533 1534 return SCIP_OKAY; 1535 } 1536 1537 /** finishes printing of expressions in dot format */ 1538 SCIP_RETCODE SCIPprintExprDotFinal( 1539 SCIP* scip, /**< SCIP data structure */ 1540 SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */ 1541 ) 1542 { 1543 assert(scip != NULL); 1544 assert(scip->mem != NULL); 1545 1546 SCIP_CALL( SCIPexprPrintDotFinal(scip->set, scip->stat, scip->mem->probmem, printdata) ); 1547 1548 return SCIP_OKAY; 1549 } 1550 1551 /** shows a single expression by use of dot and gv 1552 * 1553 * This function is meant for debugging purposes. 1554 * It's signature is kept as simple as possible to make it 1555 * easily callable from gdb, for example. 1556 * 1557 * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file, 1558 * then calls ghostview (gv) to show the file. SCIP will hold until ghostscript is closed. 1559 */ 1560 SCIP_RETCODE SCIPshowExpr( 1561 SCIP* scip, /**< SCIP data structure */ 1562 SCIP_EXPR* expr /**< expression to be printed */ 1563 ) 1564 { 1565 /* this function is for developers, so don't bother with C variants that don't have popen() */ 1566 #if _POSIX_C_SOURCE < 2 1567 SCIPerrorMessage("No POSIX version 2. Try http://distrowatch.com/."); 1568 return SCIP_ERROR; 1569 #else 1570 SCIP_EXPRPRINTDATA* dotdata; 1571 FILE* f; 1572 SCIP_RETCODE retcode = SCIP_OKAY; 1573 1574 assert(scip != NULL); 1575 assert(expr != NULL); 1576 1577 /* call dot to generate postscript output and show it via ghostview */ 1578 f = popen("dot -Tps | gv --media=a3 -", "w"); 1579 if( f == NULL ) 1580 { 1581 SCIPerrorMessage("Calling popen() failed"); 1582 return SCIP_FILECREATEERROR; 1583 } 1584 1585 /* print all of the expression into the pipe */ 1586 SCIP_CALL_TERMINATE( retcode, SCIPprintExprDotInit(scip, &dotdata, f, SCIP_EXPRPRINT_ALL), TERMINATE ); 1587 SCIP_CALL_TERMINATE( retcode, SCIPprintExprDot(scip, dotdata, expr), TERMINATE ); 1588 SCIP_CALL_TERMINATE( retcode, SCIPprintExprDotFinal(scip, &dotdata), TERMINATE ); 1589 1590 TERMINATE: 1591 /* close the pipe */ 1592 (void) pclose(f); 1593 1594 return retcode; 1595 #endif 1596 } 1597 1598 /** prints structure of an expression a la Maple's dismantle */ 1599 SCIP_RETCODE SCIPdismantleExpr( 1600 SCIP* scip, /**< SCIP data structure */ 1601 FILE* file, /**< file to print to, or NULL for stdout */ 1602 SCIP_EXPR* expr /**< expression to dismantle */ 1603 ) 1604 { 1605 assert(scip != NULL); 1606 assert(scip->mem != NULL); 1607 1608 SCIP_CALL( SCIPexprDismantle(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) ); 1609 1610 return SCIP_OKAY; 1611 } 1612 1613 /** evaluate an expression in a point 1614 * 1615 * Iterates over expressions to also evaluate children, if necessary. 1616 * Value can be received via SCIPexprGetEvalValue(). 1617 * If an evaluation error (division by zero, ...) occurs, this value will 1618 * be set to SCIP_INVALID. 1619 * 1620 * If a nonzero \p soltag is passed, then only (sub)expressions are 1621 * reevaluated that have a different solution tag. If a soltag of 0 1622 * is passed, then subexpressions are always reevaluated. 1623 * The tag is stored together with the value and can be received via 1624 * SCIPexprGetEvalTag(). 1625 */ 1626 SCIP_RETCODE SCIPevalExpr( 1627 SCIP* scip, /**< SCIP data structure */ 1628 SCIP_EXPR* expr, /**< expression to be evaluated */ 1629 SCIP_SOL* sol, /**< solution to be evaluated */ 1630 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */ 1631 ) 1632 { 1633 assert(scip != NULL); 1634 assert(scip->mem != NULL); 1635 1636 SCIP_CALL( SCIPexprEval(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) ); 1637 1638 return SCIP_OKAY; 1639 } 1640 1641 /** returns a previously unused solution tag for expression evaluation */ 1642 SCIP_Longint SCIPgetExprNewSoltag( 1643 SCIP* scip /**< SCIP data structure */ 1644 ) 1645 { 1646 assert(scip != NULL); 1647 1648 return ++(scip->stat->exprlastsoltag); 1649 } 1650 1651 /** evaluates gradient of an expression for a given point 1652 * 1653 * Initiates an expression walk to also evaluate children, if necessary. 1654 * Value can be received via SCIPgetExprPartialDiffNonlinear(). 1655 * If an error (division by zero, ...) occurs, this value will 1656 * be set to SCIP_INVALID. 1657 */ 1658 SCIP_RETCODE SCIPevalExprGradient( 1659 SCIP* scip, /**< SCIP data structure */ 1660 SCIP_EXPR* expr, /**< expression to be differentiated */ 1661 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */ 1662 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */ 1663 ) 1664 { 1665 assert(scip != NULL); 1666 assert(scip->mem != NULL); 1667 1668 SCIP_CALL( SCIPexprEvalGradient(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) ); 1669 1670 return SCIP_OKAY; 1671 } 1672 1673 /** evaluates Hessian-vector product of an expression for a given point and direction 1674 * 1675 * Evaluates children, if necessary. 1676 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear(). 1677 * If an error (division by zero, ...) occurs, this value will 1678 * be set to SCIP_INVALID. 1679 */ 1680 SCIP_RETCODE SCIPevalExprHessianDir( 1681 SCIP* scip, /**< SCIP data structure */ 1682 SCIP_EXPR* expr, /**< expression to be differentiated */ 1683 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */ 1684 SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */ 1685 SCIP_SOL* direction /**< direction */ 1686 ) 1687 { 1688 assert(scip != NULL); 1689 assert(scip->mem != NULL); 1690 1691 SCIP_CALL( SCIPexprEvalHessianDir(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag, direction) ); 1692 1693 return SCIP_OKAY; 1694 } 1695 1696 /** possibly reevaluates and then returns the activity of the expression 1697 * 1698 * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation). 1699 * 1700 * The owner of the expression may overwrite the methods used to evaluate the activity, 1701 * including whether the local or global domain of variables is used. 1702 * By default (no owner, or owner doesn't overwrite activity evaluation), 1703 * the local domain of variables is used. 1704 * 1705 * @note If expression is set to be integral, then activities are tightened to integral values. 1706 * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok). 1707 */ 1708 SCIP_RETCODE SCIPevalExprActivity( 1709 SCIP* scip, /**< SCIP data structure */ 1710 SCIP_EXPR* expr /**< expression */ 1711 ) 1712 { 1713 assert(scip != NULL); 1714 assert(scip->mem != NULL); 1715 1716 SCIP_CALL( SCIPexprEvalActivity(scip->set, scip->stat, scip->mem->probmem, expr) ); 1717 1718 return SCIP_OKAY; 1719 } 1720 1721 /** compare expressions 1722 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively 1723 * @note The given expressions are assumed to be simplified. 1724 */ 1725 int SCIPcompareExpr( 1726 SCIP* scip, /**< SCIP data structure */ 1727 SCIP_EXPR* expr1, /**< first expression */ 1728 SCIP_EXPR* expr2 /**< second expression */ 1729 ) 1730 { 1731 assert(scip != NULL); 1732 1733 return SCIPexprCompare(scip->set, expr1, expr2); 1734 } 1735 1736 /** compute the hash value of an expression */ 1737 SCIP_RETCODE SCIPhashExpr( 1738 SCIP* scip, /**< SCIP data structure */ 1739 SCIP_EXPR* expr, /**< expression */ 1740 unsigned int* hashval /**< pointer to store the hash value */ 1741 ) 1742 { 1743 SCIP_EXPRITER* it; 1744 1745 assert(scip != NULL); 1746 assert(scip->mem != NULL); 1747 assert(expr != NULL); 1748 assert(hashval != NULL); 1749 1750 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) ); 1751 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 1752 SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_LEAVEEXPR); 1753 1754 SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, expr, it, NULL) ); 1755 1756 *hashval = SCIPexpriterGetExprUserData(it, expr).uintval; 1757 1758 SCIPexpriterFree(&it); 1759 1760 return SCIP_OKAY; 1761 } 1762 1763 /** simplifies an expression (duplication of long doxygen comment omitted here) */ 1764 SCIP_RETCODE SCIPsimplifyExpr( 1765 SCIP* scip, /**< SCIP data structure */ 1766 SCIP_EXPR* rootexpr, /**< expression to be simplified */ 1767 SCIP_EXPR** simplified, /**< buffer to store simplified expression */ 1768 SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */ 1769 SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */ 1770 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 1771 void* ownercreatedata /**< data to pass to ownercreate */ 1772 ) 1773 { 1774 assert(scip != NULL); 1775 assert(scip->mem != NULL); 1776 1777 SCIP_CALL( SCIPexprSimplify(scip->set, scip->stat, scip->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) ); 1778 1779 return SCIP_OKAY; 1780 } 1781 1782 /** retrieves symmetry information from an expression */ 1783 SCIP_RETCODE SCIPgetSymDataExpr( 1784 SCIP* scip, /**< SCIP data structure */ 1785 SCIP_EXPR* expr, /**< expression from which information needs to be retrieved */ 1786 SYM_EXPRDATA** symdata /**< buffer to store symmetry data */ 1787 ) 1788 { 1789 assert(scip != NULL); 1790 assert(expr != NULL); 1791 assert(symdata != NULL); 1792 1793 SCIP_CALL( SCIPexprGetSymData(scip->set, expr, symdata) ); 1794 1795 return SCIP_OKAY; 1796 } 1797 1798 /** replaces common sub-expressions in a given expression graph by using a hash key for each expression 1799 * 1800 * The algorithm consists of two steps: 1801 * 1802 * 1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash 1803 * 1804 * 2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a 1805 * structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the 1806 * hash table, otherwise we add it to the hash table 1807 * 1808 * @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions 1809 * (with the same hash) are structurally the same we use the function SCIPexprCompare(). 1810 */ 1811 SCIP_RETCODE SCIPreplaceCommonSubexpressions( 1812 SCIP* scip, /**< SCIP data structure */ 1813 SCIP_EXPR** exprs, /**< expressions (possibly replaced by equivalent on output) */ 1814 int nexprs, /**< total number of expressions */ 1815 SCIP_Bool* replacedroot /**< buffer to store whether any root expression (expression in exprs) was replaced */ 1816 ) 1817 { 1818 COMMONSUBEXPR_HASH_DATA hashdata; 1819 SCIP_EXPRITER* hashiterator; 1820 SCIP_EXPRITER* repliterator; 1821 SCIP_MULTIHASH* key2expr; 1822 int i; 1823 int nvisitedexprs = 0; 1824 1825 assert(scip != NULL); 1826 assert(scip->mem != NULL); 1827 assert(exprs != NULL); 1828 assert(nexprs >= 0); 1829 assert(replacedroot != NULL); 1830 1831 *replacedroot = FALSE; 1832 1833 if( nexprs == 0 ) 1834 return SCIP_OKAY; 1835 1836 SCIP_CALL( SCIPcreateExpriter(scip, &hashiterator) ); 1837 SCIP_CALL( SCIPexpriterInit(hashiterator, NULL, SCIP_EXPRITER_DFS, FALSE) ); 1838 SCIPexpriterSetStagesDFS(hashiterator, SCIP_EXPRITER_LEAVEEXPR); 1839 1840 /* compute all hashes for each sub-expression */ 1841 for( i = 0; i < nexprs; ++i ) 1842 { 1843 assert(exprs[i] != NULL); 1844 SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, exprs[i], hashiterator, &nvisitedexprs) ); 1845 } 1846 1847 /* replace equivalent sub-expressions */ 1848 hashdata.hashiterator = hashiterator; 1849 hashdata.set = scip->set; 1850 SCIP_CALL( SCIPmultihashCreate(&key2expr, scip->mem->probmem, nvisitedexprs, 1851 hashCommonSubexprGetKey, hashCommonSubexprEq, hashCommonSubexprKeyval, (void*)&hashdata) ); 1852 1853 SCIP_CALL( SCIPcreateExpriter(scip, &repliterator) ); 1854 1855 for( i = 0; i < nexprs; ++i ) 1856 { 1857 SCIP_EXPR* newroot; 1858 SCIP_EXPR* newchild; 1859 SCIP_EXPR* child; 1860 1861 /* check the root for equivalence separately first */ 1862 SCIP_CALL( findEqualExpr(scip->set, exprs[i], key2expr, &newroot) ); 1863 1864 if( newroot != NULL ) 1865 { 1866 assert(newroot != exprs[i]); 1867 assert(SCIPexprCompare(scip->set, exprs[i], newroot) == 0); 1868 1869 SCIPdebugMsg(scip, "replacing common root expression of %dth expr: %p -> %p\n", i, (void*)exprs[i], (void*)newroot); 1870 1871 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[i]) ); 1872 1873 exprs[i] = newroot; 1874 SCIPexprCapture(newroot); 1875 1876 *replacedroot = TRUE; 1877 1878 continue; 1879 } 1880 1881 /* replace equivalent sub-expressions in the tree */ 1882 SCIP_CALL( SCIPexpriterInit(repliterator, exprs[i], SCIP_EXPRITER_DFS, FALSE) ); 1883 SCIPexpriterSetStagesDFS(repliterator, SCIP_EXPRITER_VISITINGCHILD); 1884 1885 while( !SCIPexpriterIsEnd(repliterator) ) 1886 { 1887 child = SCIPexpriterGetChildExprDFS(repliterator); 1888 assert(child != NULL); 1889 1890 /* try to find an equivalent expression */ 1891 SCIP_CALL( findEqualExpr(scip->set, child, key2expr, &newchild) ); 1892 1893 /* replace child with newchild */ 1894 if( newchild != NULL ) 1895 { 1896 assert(child != newchild); 1897 assert(SCIPexprCompare(scip->set, child, newchild) == 0); 1898 1899 SCIPdebugMsg(scip, "replacing common child expression %p -> %p\n", (void*)child, (void*)newchild); 1900 1901 SCIP_CALL( SCIPreplaceExprChild(scip, SCIPexpriterGetCurrent(repliterator), SCIPexpriterGetChildIdxDFS(repliterator), newchild) ); 1902 1903 (void) SCIPexpriterSkipDFS(repliterator); 1904 } 1905 else 1906 { 1907 (void) SCIPexpriterGetNext(repliterator); 1908 } 1909 } 1910 } 1911 1912 /* free memory */ 1913 SCIPexpriterFree(&repliterator); 1914 SCIPmultihashFree(&key2expr); 1915 SCIPexpriterFree(&hashiterator); 1916 1917 return SCIP_OKAY; 1918 } 1919 1920 /** computes the curvature of a given expression and all its subexpressions 1921 * 1922 * @note this function also evaluates all subexpressions w.r.t. current variable bounds 1923 * @note this function relies on information from the curvature callback of expression handlers only, 1924 * consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity 1925 */ 1926 SCIP_RETCODE SCIPcomputeExprCurvature( 1927 SCIP* scip, /**< SCIP data structure */ 1928 SCIP_EXPR* expr /**< expression */ 1929 ) 1930 { 1931 SCIP_EXPRITER* it; 1932 SCIP_EXPRCURV curv; 1933 SCIP_EXPRCURV* childcurv; 1934 int childcurvsize; 1935 SCIP_Bool success; 1936 SCIP_EXPRCURV trialcurv[3] = { SCIP_EXPRCURV_LINEAR, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_CONCAVE }; 1937 int i, c; 1938 1939 assert(scip != NULL); 1940 assert(scip->mem != NULL); 1941 assert(expr != NULL); 1942 1943 childcurvsize = 5; 1944 SCIP_CALL( SCIPallocBufferArray(scip, &childcurv, childcurvsize) ); 1945 1946 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) ); 1947 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 1948 SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_LEAVEEXPR); 1949 1950 for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) 1951 { 1952 curv = SCIP_EXPRCURV_UNKNOWN; 1953 1954 if( !SCIPexprhdlrHasCurvature(SCIPexprGetHdlr(expr)) ) 1955 { 1956 /* set curvature in expression */ 1957 SCIPexprSetCurvature(expr, curv); 1958 continue; 1959 } 1960 1961 if( SCIPexprGetNChildren(expr) > childcurvsize ) 1962 { 1963 childcurvsize = SCIPcalcMemGrowSize(scip, SCIPexprGetNChildren(expr)); 1964 SCIP_CALL( SCIPreallocBufferArray(scip, &childcurv, childcurvsize) ); 1965 } 1966 1967 for( i = 0; i < 3; ++i ) 1968 { 1969 /* check if expression can have a curvature trialcurv[i] */ 1970 SCIP_CALL( SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), scip->set, expr, trialcurv[i], &success, childcurv) ); 1971 if( !success ) 1972 continue; 1973 1974 /* check if conditions on children are satisfied */ 1975 for( c = 0; c < SCIPexprGetNChildren(expr); ++c ) 1976 { 1977 if( (childcurv[c] & SCIPexprGetCurvature(SCIPexprGetChildren(expr)[c])) != childcurv[c] ) 1978 { 1979 success = FALSE; 1980 break; 1981 } 1982 } 1983 1984 if( success ) 1985 { 1986 curv = trialcurv[i]; 1987 break; 1988 } 1989 } 1990 1991 /* set curvature in expression */ 1992 SCIPexprSetCurvature(expr, curv); 1993 } 1994 1995 SCIPexpriterFree(&it); 1996 1997 SCIPfreeBufferArray(scip, &childcurv); 1998 1999 return SCIP_OKAY; 2000 } 2001 2002 /** computes integrality information of a given expression and all its subexpressions 2003 * 2004 * The integrality information can be accessed via SCIPexprIsIntegral(). 2005 */ 2006 SCIP_RETCODE SCIPcomputeExprIntegrality( 2007 SCIP* scip, /**< SCIP data structure */ 2008 SCIP_EXPR* expr /**< expression */ 2009 ) 2010 { 2011 SCIP_EXPRITER* it; 2012 SCIP_Bool isintegral; 2013 2014 assert(scip != NULL); 2015 assert(scip->mem != NULL); 2016 assert(expr != NULL); 2017 2018 /* shortcut for expr without children */ 2019 if( SCIPexprGetNChildren(expr) == 0 ) 2020 { 2021 /* compute integrality information */ 2022 SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) ); 2023 SCIPexprSetIntegrality(expr, isintegral); 2024 2025 return SCIP_OKAY; 2026 } 2027 2028 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) ); 2029 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 2030 SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_LEAVEEXPR); 2031 2032 for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) 2033 { 2034 /* compute integrality information */ 2035 SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) ); 2036 SCIPexprSetIntegrality(expr, isintegral); 2037 } 2038 2039 SCIPexpriterFree(&it); 2040 2041 return SCIP_OKAY; 2042 } 2043 2044 /** returns the total number of variable expressions in an expression 2045 * 2046 * The function counts variable expressions in common sub-expressions only once, but 2047 * counts variables appearing in several variable expressions multiple times. 2048 */ 2049 SCIP_RETCODE SCIPgetExprNVars( 2050 SCIP* scip, /**< SCIP data structure */ 2051 SCIP_EXPR* expr, /**< expression */ 2052 int* nvars /**< buffer to store the total number of variables */ 2053 ) 2054 { 2055 SCIP_EXPRITER* it; 2056 2057 assert(scip != NULL); 2058 assert(scip->mem != NULL); 2059 assert(expr != NULL); 2060 assert(nvars != NULL); 2061 2062 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) ); 2063 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 2064 2065 *nvars = 0; 2066 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) 2067 if( SCIPexprIsVar(scip->set, expr) ) 2068 ++(*nvars); 2069 2070 SCIPexpriterFree(&it); 2071 2072 return SCIP_OKAY; 2073 } 2074 2075 /** returns all variable expressions contained in a given expression 2076 * 2077 * The array to store all variable expressions needs to be at least of size 2078 * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars(). 2079 * 2080 * If every variable is represented by only one variable expression (common subexpression have been removed) 2081 * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars(). 2082 * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying, 2083 * then SCIPgetExprNVars() can be bounded by SCIPgetNVars(). 2084 * 2085 * @note function captures variable expressions 2086 */ 2087 SCIP_RETCODE SCIPgetExprVarExprs( 2088 SCIP* scip, /**< SCIP data structure */ 2089 SCIP_EXPR* expr, /**< expression */ 2090 SCIP_EXPR** varexprs, /**< array to store all variable expressions */ 2091 int* nvarexprs /**< buffer to store the total number of variable expressions */ 2092 ) 2093 { 2094 SCIP_EXPRITER* it; 2095 2096 assert(scip != NULL); 2097 assert(scip->mem != NULL); 2098 assert(expr != NULL); 2099 assert(varexprs != NULL); 2100 assert(nvarexprs != NULL); 2101 2102 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) ); 2103 SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) ); 2104 2105 *nvarexprs = 0; 2106 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) 2107 { 2108 assert(expr != NULL); 2109 2110 if( SCIPexprIsVar(scip->set, expr) ) 2111 { 2112 varexprs[(*nvarexprs)++] = expr; 2113 2114 /* capture expression */ 2115 SCIPcaptureExpr(expr); 2116 } 2117 } 2118 2119 /* @todo sort variable expressions here? */ 2120 2121 SCIPexpriterFree(&it); 2122 2123 return SCIP_OKAY; 2124 } 2125 2126 /** calls the print callback for an expression 2127 * 2128 * @see SCIP_DECL_EXPRPRINT 2129 */ 2130 SCIP_DECL_EXPRPRINT(SCIPcallExprPrint) 2131 { 2132 assert(scip != NULL); 2133 2134 SCIP_CALL( SCIPexprhdlrPrintExpr(SCIPexprGetHdlr(expr), scip->set, scip->messagehdlr, expr, stage, currentchild, parentprecedence, file) ); 2135 2136 return SCIP_OKAY; 2137 } 2138 2139 /** calls the curvature callback for an expression 2140 * 2141 * @see SCIP_DECL_EXPRCURVATURE 2142 * 2143 * Returns unknown curvature if callback not implemented. 2144 */ 2145 SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature) 2146 { 2147 assert(scip != NULL); 2148 2149 SCIP_CALL( SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), scip->set, expr, exprcurvature, success, childcurv) ); 2150 2151 return SCIP_OKAY; 2152 } 2153 2154 /** calls the monotonicity callback for an expression 2155 * 2156 * @see SCIP_DECL_EXPRMONOTONICITY 2157 * 2158 * Returns unknown monotonicity if callback not implemented. 2159 */ 2160 SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity) 2161 { 2162 assert(scip != NULL); 2163 2164 SCIP_CALL( SCIPexprhdlrMonotonicityExpr(SCIPexprGetHdlr(expr), scip->set, expr, childidx, result) ); 2165 2166 return SCIP_OKAY; 2167 } 2168 2169 /** calls the eval callback for an expression with given values for children 2170 * 2171 * Does not iterates over expressions, but requires values for children to be given. 2172 * Value is not stored in expression, but returned in `val`. 2173 * If an evaluation error (division by zero, ...) occurs, this value will 2174 * be set to `SCIP_INVALID`. 2175 */ 2176 SCIP_RETCODE SCIPcallExprEval( 2177 SCIP* scip, /**< SCIP data structure */ 2178 SCIP_EXPR* expr, /**< expression to be evaluated */ 2179 SCIP_Real* childrenvalues, /**< values for children */ 2180 SCIP_Real* val /**< buffer to store evaluated value */ 2181 ) 2182 { 2183 assert(scip != NULL); 2184 assert(scip->mem != NULL); 2185 assert(childrenvalues != NULL); 2186 assert(val != NULL); 2187 2188 SCIP_CALL( SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, childrenvalues, NULL) ); 2189 2190 return SCIP_OKAY; 2191 } 2192 2193 /** calls the eval and fwdiff callback of an expression with given values for children 2194 * 2195 * Does not iterates over expressions, but requires values for children and direction to be given. 2196 * 2197 * Value is not stored in expression, but returned in `val`. 2198 * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`. 2199 * 2200 * Direction is not stored in expression, but returned in `dot`. 2201 * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`. 2202 */ 2203 SCIP_RETCODE SCIPcallExprEvalFwdiff( 2204 SCIP* scip, /**< SCIP data structure */ 2205 SCIP_EXPR* expr, /**< expression to be evaluated */ 2206 SCIP_Real* childrenvalues, /**< values for children */ 2207 SCIP_Real* direction, /**< direction in which to differentiate */ 2208 SCIP_Real* val, /**< buffer to store evaluated value */ 2209 SCIP_Real* dot /**< buffer to store derivative value */ 2210 ) 2211 { 2212 assert(scip != NULL); 2213 assert(scip->mem != NULL); 2214 2215 SCIP_CALL( SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, dot, 2216 childrenvalues, NULL, direction, NULL) ); 2217 2218 return SCIP_OKAY; 2219 } 2220 2221 /** calls the interval evaluation callback for an expression 2222 * 2223 * @see SCIP_DECL_EXPRINTEVAL 2224 * 2225 * Returns entire interval if callback not implemented. 2226 */ 2227 SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval) 2228 { 2229 assert(scip != NULL); 2230 2231 SCIP_CALL( SCIPexprhdlrIntEvalExpr(SCIPexprGetHdlr(expr), scip->set, expr, interval, intevalvar, intevalvardata) ); 2232 2233 return SCIP_OKAY; 2234 } 2235 2236 /** calls the estimate callback for an expression 2237 * 2238 * @see SCIP_DECL_EXPRESTIMATE 2239 * 2240 * Returns without success if callback not implemented. 2241 */ 2242 SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate) 2243 { 2244 assert(scip != NULL); 2245 2246 SCIP_CALL( SCIPexprhdlrEstimateExpr(SCIPexprGetHdlr(expr), scip->set, expr, localbounds, globalbounds, refpoint, 2247 overestimate, targetvalue, coefs, constant, islocal, success, branchcand) ); 2248 2249 return SCIP_OKAY; 2250 } 2251 2252 /** calls the initial estimators callback for an expression 2253 * 2254 * @see SCIP_DECL_EXPRINITESTIMATES 2255 * 2256 * Returns no estimators if callback not implemented. 2257 */ 2258 SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates) 2259 { 2260 assert(scip != NULL); 2261 2262 SCIP_CALL( SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, overestimate, coefs, 2263 constant, nreturned) ); 2264 2265 return SCIP_OKAY; 2266 } 2267 2268 /** calls the simplify callback for an expression 2269 * 2270 * @see SCIP_DECL_EXPRSIMPLIFY 2271 * 2272 * Returns unmodified expression if simplify callback not implemented. 2273 * 2274 * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that. 2275 */ 2276 SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify) 2277 { 2278 assert(scip != NULL); 2279 2280 /* use simplification of expression handlers */ 2281 SCIP_CALL( SCIPexprhdlrSimplifyExpr(SCIPexprGetHdlr(expr), scip->set, expr, simplifiedexpr, ownercreate, 2282 ownercreatedata) ); 2283 2284 return SCIP_OKAY; 2285 } 2286 2287 /** calls the reverse propagation callback for an expression 2288 * 2289 * @see SCIP_DECL_EXPRREVERSEPROP 2290 * 2291 * Returns unmodified childrenbounds if reverseprop callback not implemented. 2292 */ 2293 SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop) 2294 { 2295 assert(scip != NULL); 2296 2297 SCIP_CALL( SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, childrenbounds, infeasible) ); 2298 2299 return SCIP_OKAY; 2300 } 2301 2302 /** calls the symmetry data callback for an expression 2303 * 2304 * Returns no information if not implemented. 2305 */ 2306 SCIP_DECL_EXPRGETSYMDATA(SCIPcallExprGetSymData) 2307 { 2308 assert(scip != NULL); 2309 assert(expr != NULL); 2310 assert(symdata != NULL); 2311 2312 SCIP_CALL( SCIPexprGetSymData(scip->set, expr, symdata) ); 2313 2314 return SCIP_OKAY; 2315 } 2316 2317 /**@} */ 2318 2319 /**@name Expression Iterator Methods */ 2320 /**@{ */ 2321 2322 #ifdef NDEBUG 2323 #undef SCIPcreateExpriter 2324 #undef SCIPfreeExpriter 2325 #endif 2326 2327 /** creates an expression iterator */ 2328 SCIP_RETCODE SCIPcreateExpriter( 2329 SCIP* scip, /**< SCIP data structure */ 2330 SCIP_EXPRITER** iterator /**< buffer to store expression iterator */ 2331 ) 2332 { 2333 assert(scip != NULL); 2334 assert(scip->mem != NULL); 2335 2336 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, iterator) ); 2337 2338 return SCIP_OKAY; 2339 } 2340 2341 /** frees an expression iterator */ 2342 void SCIPfreeExpriter( 2343 SCIP_EXPRITER** iterator /**< pointer to the expression iterator */ 2344 ) 2345 { 2346 SCIPexpriterFree(iterator); 2347 } 2348 2349 /**@} */ 2350 2351 2352 /**@name Quadratic expression functions */ 2353 /**@{ */ 2354 2355 #ifdef NDEBUG 2356 #undef SCIPcheckExprQuadratic 2357 #undef SCIPfreeExprQuadratic 2358 #undef SCIPcomputeExprQuadraticCurvature 2359 #endif 2360 2361 /** checks whether an expression is quadratic 2362 * 2363 * An expression is quadratic if it is either a square (of some expression), a product (of two expressions), 2364 * or a sum of terms where at least one is a square or a product. 2365 * 2366 * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic. 2367 */ 2368 SCIP_RETCODE SCIPcheckExprQuadratic( 2369 SCIP* scip, /**< SCIP data structure */ 2370 SCIP_EXPR* expr, /**< expression */ 2371 SCIP_Bool* isquadratic /**< buffer to store result */ 2372 ) 2373 { 2374 assert(scip != NULL); 2375 assert(scip->mem != NULL); 2376 2377 SCIP_CALL( SCIPexprCheckQuadratic(scip->set, scip->mem->probmem, expr, isquadratic) ); 2378 2379 return SCIP_OKAY; 2380 } 2381 2382 /** frees information on quadratic representation of an expression 2383 * 2384 * Before doing changes to an expression, it can be useful to call this function. 2385 */ 2386 void SCIPfreeExprQuadratic( 2387 SCIP* scip, /**< SCIP data structure */ 2388 SCIP_EXPR* expr /**< expression */ 2389 ) 2390 { 2391 assert(scip != NULL); 2392 assert(scip->mem != NULL); 2393 2394 SCIPexprFreeQuadratic(scip->mem->probmem, expr); 2395 } 2396 2397 /** evaluates quadratic term in a solution 2398 * 2399 * \note This requires that every expression used in the quadratic data is a variable expression. 2400 */ 2401 SCIP_Real SCIPevalExprQuadratic( 2402 SCIP* scip, /**< SCIP data structure */ 2403 SCIP_EXPR* expr, /**< quadratic expression */ 2404 SCIP_SOL* sol /**< solution to evaluate, or NULL for LP solution */ 2405 ) 2406 { 2407 SCIP_Real auxvalue; 2408 int nlinexprs; 2409 SCIP_Real* lincoefs; 2410 SCIP_EXPR** linexprs; 2411 int nquadexprs; 2412 int nbilinexprs; 2413 int i; 2414 2415 assert(scip != NULL); 2416 assert(expr != NULL); 2417 2418 SCIPexprGetQuadraticData(expr, &auxvalue, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL); 2419 2420 /* linear terms */ 2421 for( i = 0; i < nlinexprs; ++i ) 2422 { 2423 assert(SCIPexprIsVar(scip->set, linexprs[i])); 2424 auxvalue += lincoefs[i] * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(linexprs[i])); 2425 } 2426 2427 /* quadratic terms */ 2428 for( i = 0; i < nquadexprs; ++i ) 2429 { 2430 SCIP_EXPR* quadexprterm; 2431 SCIP_Real lincoef; 2432 SCIP_Real sqrcoef; 2433 SCIP_Real solval; 2434 2435 SCIPexprGetQuadraticQuadTerm(expr, i, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL); 2436 2437 assert(SCIPexprIsVar(scip->set, quadexprterm)); 2438 2439 solval = SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(quadexprterm)); 2440 auxvalue += (lincoef + sqrcoef * solval) * solval; 2441 } 2442 2443 /* bilinear terms */ 2444 for( i = 0; i < nbilinexprs; ++i ) 2445 { 2446 SCIP_EXPR* expr1; 2447 SCIP_EXPR* expr2; 2448 SCIP_Real coef; 2449 2450 SCIPexprGetQuadraticBilinTerm(expr, i, &expr1, &expr2, &coef, NULL, NULL); 2451 2452 assert(SCIPexprIsVar(scip->set, expr1)); 2453 assert(SCIPexprIsVar(scip->set, expr2)); 2454 auxvalue += coef * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr1)) * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr2)); 2455 } 2456 2457 return auxvalue; 2458 } 2459 2460 /** prints quadratic expression */ 2461 SCIP_RETCODE SCIPprintExprQuadratic( 2462 SCIP* scip, /**< SCIP data structure */ 2463 SCIP_EXPR* expr /**< quadratic expression */ 2464 ) 2465 { 2466 SCIP_Real constant; 2467 int nlinexprs; 2468 SCIP_Real* lincoefs; 2469 SCIP_EXPR** linexprs; 2470 int nquadexprs; 2471 int nbilinexprs; 2472 int c; 2473 2474 assert(scip != NULL); 2475 assert(expr != NULL); 2476 2477 SCIPexprGetQuadraticData(expr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL); 2478 2479 SCIPinfoMessage(scip, NULL, "Constant: %g\n", constant); 2480 2481 SCIPinfoMessage(scip, NULL, "Linear: "); 2482 for( c = 0; c < nlinexprs; ++c ) 2483 { 2484 SCIPinfoMessage(scip, NULL, "%g * ", lincoefs[c]); 2485 SCIP_CALL( SCIPprintExpr(scip, linexprs[c], NULL) ); 2486 if( c < nlinexprs - 1 ) 2487 SCIPinfoMessage(scip, NULL, " + "); 2488 } 2489 SCIPinfoMessage(scip, NULL, "\n"); 2490 2491 SCIPinfoMessage(scip, NULL, "Quadratic: "); 2492 for( c = 0; c < nquadexprs; ++c ) 2493 { 2494 SCIP_EXPR* quadexprterm; 2495 SCIP_Real lincoef; 2496 SCIP_Real sqrcoef; 2497 2498 SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL); 2499 SCIPinfoMessage(scip, NULL, "(%g * sqr(", sqrcoef); 2500 SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) ); 2501 SCIPinfoMessage(scip, NULL, ") + %g) * ", lincoef); 2502 SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) ); 2503 if( c < nquadexprs - 1 ) 2504 SCIPinfoMessage(scip, NULL, " + "); 2505 } 2506 SCIPinfoMessage(scip, NULL, "\n"); 2507 2508 if( nbilinexprs == 0 ) 2509 { 2510 SCIPinfoMessage(scip, NULL, "Bilinear: none\n"); 2511 return SCIP_OKAY; 2512 } 2513 2514 SCIPinfoMessage(scip, NULL, "Bilinear: "); 2515 for( c = 0; c < nbilinexprs; ++c ) 2516 { 2517 SCIP_EXPR* expr1; 2518 SCIP_EXPR* expr2; 2519 SCIP_Real coef; 2520 2521 SCIPexprGetQuadraticBilinTerm(expr, c, &expr1, &expr2, &coef, NULL, NULL); 2522 2523 SCIPinfoMessage(scip, NULL, "%g * ", coef); 2524 SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) ); 2525 SCIPinfoMessage(scip, NULL, " * "); 2526 SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) ); 2527 if( c < nbilinexprs - 1 ) 2528 SCIPinfoMessage(scip, NULL, " + "); 2529 } 2530 SCIPinfoMessage(scip, NULL, "\n"); 2531 2532 SCIPinfoMessage(scip, NULL, "Bilinear of quadratics: \n"); 2533 for( c = 0; c < nquadexprs; ++c ) 2534 { 2535 SCIP_EXPR* quadexprterm; 2536 int nadjbilin; 2537 int* adjbilin; 2538 int i; 2539 2540 SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, NULL, NULL, &nadjbilin, &adjbilin, NULL); 2541 2542 SCIPinfoMessage(scip, NULL, " For "); 2543 SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) ); 2544 SCIPinfoMessage(scip, NULL, " we see: "); 2545 for( i = 0; i < nadjbilin; ++i ) 2546 { 2547 SCIP_EXPR* expr1; 2548 SCIP_EXPR* expr2; 2549 SCIP_Real coef; 2550 2551 SCIPexprGetQuadraticBilinTerm(expr, adjbilin[i], &expr1, &expr2, &coef, NULL, NULL); 2552 2553 SCIPinfoMessage(scip, NULL, "%g * ", coef); 2554 SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) ); 2555 SCIPinfoMessage(scip, NULL, " * "); 2556 SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) ); 2557 if( i < nadjbilin - 1 ) 2558 SCIPinfoMessage(scip, NULL, " + "); 2559 } 2560 SCIPinfoMessage(scip, NULL, "\n"); 2561 } 2562 2563 return SCIP_OKAY; 2564 } 2565 2566 /** checks the curvature of the quadratic expression 2567 * 2568 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK. 2569 * If Q is 2570 * - semidefinite positive -> curv is set to convex, 2571 * - semidefinite negative -> curv is set to concave, 2572 * - otherwise -> curv is set to unknown. 2573 * 2574 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in 2575 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q. 2576 */ 2577 SCIP_RETCODE SCIPcomputeExprQuadraticCurvature( 2578 SCIP* scip, /**< SCIP data structure */ 2579 SCIP_EXPR* expr, /**< quadratic expression */ 2580 SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */ 2581 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ 2582 SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */ 2583 ) 2584 { 2585 assert(scip != NULL); 2586 assert(scip->mem != NULL); 2587 2588 SCIP_CALL( SCIPexprComputeQuadraticCurvature(scip->set, scip->mem->probmem, scip->mem->buffer, scip->messagehdlr, 2589 expr, curv, assumevarfixed, storeeigeninfo) ); 2590 2591 return SCIP_OKAY; 2592 } 2593 2594 /**@} */ 2595 2596 /**@name Monomial expression functions */ 2597 /**@{ */ 2598 2599 #ifdef NDEBUG 2600 #undef SCIPgetExprMonomialData 2601 #endif 2602 2603 /** returns a monomial representation of a product expression 2604 * 2605 * The array to store all factor expressions needs to be of size the number of 2606 * children in the expression which is given by SCIPexprGetNChildren(). 2607 * 2608 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where 2609 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can 2610 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents. 2611 * 2612 * A non-trivial monomial is a product of a least two expressions. 2613 */ 2614 SCIP_RETCODE SCIPgetExprMonomialData( 2615 SCIP* scip, /**< SCIP data structure */ 2616 SCIP_EXPR* expr, /**< expression */ 2617 SCIP_Real* coef, /**< coefficient \f$c\f$ */ 2618 SCIP_Real* exponents, /**< exponents \f$\alpha\f$ */ 2619 SCIP_EXPR** factors /**< factor expressions \f$x\f$ */ 2620 ) 2621 { 2622 assert(scip != NULL); 2623 assert(scip->mem != NULL); 2624 2625 SCIP_CALL( SCIPexprGetMonomialData(scip->set, scip->mem->probmem, expr, coef, exponents, factors) ); 2626 2627 return SCIP_OKAY; 2628 } 2629 2630 /**@} */ 2631