1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file expr_entropy.c 26 * @ingroup DEFPLUGINS_EXPR 27 * @brief handler for -x*log(x) expressions 28 * @author Benjamin Mueller 29 * @author Fabian Wegscheider 30 * @author Ksenia Bestuzheva 31 * 32 * @todo replace exp(-1.0) by 1.0/M_E 33 */ 34 35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 36 37 #include "scip/expr_entropy.h" 38 #include "scip/expr_value.h" 39 #include "scip/expr.h" 40 41 #include <string.h> 42 43 /* fundamental expression handler properties */ 44 #define EXPRHDLR_NAME "entropy" 45 #define EXPRHDLR_DESC "entropy expression (-x*log(x))" 46 #define EXPRHDLR_PRECEDENCE 81000 47 #define EXPRHDLR_HASHKEY SCIPcalcFibHash(7477.0) 48 49 /* 50 * Data structures 51 */ 52 53 /* 54 * Local methods 55 */ 56 57 /** helper function for reverseProp() which returns an x* in [xmin,xmax] s.t. the distance -x*log(x) and a given target 58 * value is minimized; the function assumes that -x*log(x) is monotone on [xmin,xmax]; 59 */ 60 static 61 SCIP_Real reversePropBinarySearch( 62 SCIP* scip, /**< SCIP data structure */ 63 SCIP_Real xmin, /**< smallest possible x */ 64 SCIP_Real xmax, /**< largest possible x */ 65 SCIP_Bool increasing, /**< -x*log(x) is increasing or decreasing on [xmin,xmax] */ 66 SCIP_Real targetval /**< target value */ 67 ) 68 { 69 SCIP_Real xminval = (xmin == 0.0) ? 0.0 : -xmin * log(xmin); 70 SCIP_Real xmaxval = (xmax == 0.0) ? 0.0 : -xmax * log(xmax); 71 int i; 72 73 assert(xmin <= xmax); 74 assert(increasing ? xminval <= xmaxval : xminval >= xmaxval); 75 76 /* function can not achieve -x*log(x) -> return xmin or xmax */ 77 if( SCIPisGE(scip, xminval, targetval) && SCIPisGE(scip, xmaxval, targetval) ) 78 return increasing ? xmin : xmax; 79 else if( SCIPisLE(scip, xminval, targetval) && SCIPisLE(scip, xmaxval, targetval) ) 80 return increasing ? xmax : xmin; 81 82 /* binary search */ 83 for( i = 0; i < 1000; ++i ) 84 { 85 SCIP_Real x = (xmin + xmax) / 2.0; 86 SCIP_Real xval = (x == 0.0) ? 0.0 : -x * log(x); 87 88 /* found the corresponding point -> skip */ 89 if( SCIPisEQ(scip, xval, targetval) ) 90 return x; 91 else if( SCIPisLT(scip, xval, targetval) ) 92 { 93 if( increasing ) 94 xmin = x; 95 else 96 xmax = x; 97 } 98 else 99 { 100 if( increasing ) 101 xmax = x; 102 else 103 xmin = x; 104 } 105 } 106 107 return SCIP_INVALID; 108 } 109 110 /** helper function for reverse propagation; needed for proper unittest */ 111 static 112 SCIP_RETCODE reverseProp( 113 SCIP* scip, /**< SCIP data structure */ 114 SCIP_INTERVAL exprinterval, /**< bounds on the expression */ 115 SCIP_INTERVAL childinterval, /**< bounds on the interval of the child */ 116 SCIP_INTERVAL* interval /**< resulting interval */ 117 ) 118 { 119 SCIP_INTERVAL childentropy; 120 SCIP_INTERVAL intersection; 121 SCIP_INTERVAL tmp; 122 SCIP_Real childinf; 123 SCIP_Real childsup; 124 SCIP_Real extremum; 125 SCIP_Real boundinf; 126 SCIP_Real boundsup; 127 128 assert(scip != NULL); 129 assert(interval != NULL); 130 131 /* check whether domain is empty, i.e., bounds on -x*log(x) > 1/e */ 132 if( SCIPisGT(scip, SCIPintervalGetInf(exprinterval), exp(-1.0)) 133 || SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childinterval) ) 134 { 135 SCIPintervalSetEmpty(interval); 136 return SCIP_OKAY; 137 } 138 139 /* compute the intersection between entropy([childinf,childsup]) and [expr.inf, expr.sup] */ 140 SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, &childentropy, childinterval); 141 SCIPintervalIntersect(&intersection, childentropy, exprinterval); 142 143 /* intersection empty -> infeasible */ 144 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, intersection) ) 145 { 146 SCIPintervalSetEmpty(interval); 147 return SCIP_OKAY; 148 } 149 150 /* intersection = childentropy -> nothing can be learned */ 151 if( SCIPintervalIsSubsetEQ(SCIP_INTERVAL_INFINITY, childentropy, intersection) ) 152 { 153 SCIPintervalSetBounds(interval, 0.0, SCIP_INTERVAL_INFINITY); 154 SCIPintervalIntersect(interval, *interval, childinterval); 155 return SCIP_OKAY; 156 } 157 158 childinf = MAX(0.0, SCIPintervalGetInf(childinterval)); /*lint !e666*/ 159 childsup = SCIPintervalGetSup(childinterval); 160 extremum = exp(-1.0); 161 boundinf = SCIP_INVALID; 162 boundsup = SCIP_INVALID; 163 164 /* 165 * check whether lower bound of child can be improved 166 */ 167 SCIPintervalSet(&tmp, childinf); 168 SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, &tmp, tmp); 169 170 /* entropy(childinf) < intersection.inf -> consider [childinf, MIN(childsup, extremum)] */ 171 if( SCIPintervalGetInf(intersection) > -SCIP_INTERVAL_INFINITY && SCIPintervalGetSup(tmp) - SCIPintervalGetInf(intersection) < -SCIPepsilon(scip) ) 172 { 173 boundinf = reversePropBinarySearch(scip, childinf, MIN(extremum, childsup), TRUE, 174 SCIPintervalGetInf(intersection)); 175 } 176 /* entropy(childinf) > intersection.sup -> consider [MAX(childinf,extremum), childsup] */ 177 else if( SCIPintervalGetSup(intersection) < SCIP_INTERVAL_INFINITY && SCIPintervalGetInf(tmp) - SCIPintervalGetSup(intersection) > SCIPepsilon(scip) ) 178 { 179 boundinf = reversePropBinarySearch(scip, MAX(childinf, extremum), childsup, FALSE, 180 SCIPintervalGetSup(intersection)); 181 } 182 /* using a strict greater-than here because we expect a tightening because we saw an at-least-epsilon-potential above */ 183 assert(boundinf == SCIP_INVALID || boundinf > childinf); /*lint !e777*/ 184 185 /* 186 * check whether upper bound of child can be improved 187 */ 188 if( childsup < SCIP_INTERVAL_INFINITY ) 189 { 190 SCIPintervalSet(&tmp, childsup); 191 SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, &tmp, tmp); 192 } 193 else 194 SCIPintervalSetBounds(&tmp, -SCIP_INTERVAL_INFINITY, -SCIP_INTERVAL_INFINITY); /* entropy(inf) = -inf */ 195 196 /* entropy(childsup) < intersection.inf -> consider [MAX(childinf,extremum), childsup] */ 197 if( SCIPintervalGetInf(intersection) > -SCIP_INTERVAL_INFINITY && SCIPintervalGetSup(tmp) - SCIPintervalGetInf(intersection) < -SCIPepsilon(scip) ) 198 { 199 boundsup = reversePropBinarySearch(scip, MAX(childinf, extremum), childsup, FALSE, 200 SCIPintervalGetInf(intersection)); 201 } 202 /* entropy(childsup) > intersection.sup -> consider [childinf, MIN(childsup,extremum)] */ 203 else if( SCIPintervalGetSup(intersection) < SCIP_INTERVAL_INFINITY && SCIPintervalGetInf(tmp) - SCIPintervalGetSup(intersection) > SCIPepsilon(scip) ) 204 { 205 boundsup = reversePropBinarySearch(scip, childinf, MIN(childsup, extremum), TRUE, 206 SCIPintervalGetSup(intersection)); 207 } 208 /* using a strict smaller-than here because we expect a tightening because we saw an at-least-epsilon-potential above */ 209 assert(boundsup == SCIP_INVALID || boundsup < childsup); /*lint !e777*/ 210 211 if( boundinf != SCIP_INVALID ) /*lint !e777*/ 212 { 213 childinf = MAX(childinf, boundinf); 214 } 215 if( boundsup != SCIP_INVALID ) /*lint !e777*/ 216 { 217 childsup = boundsup; 218 } 219 assert(childinf <= childsup); /* infeasible case has been handled already */ 220 221 /* set the resulting bounds */ 222 SCIPintervalSetBounds(interval, childinf, childsup); 223 224 return SCIP_OKAY; 225 } 226 227 /* 228 * Callback methods of expression handler 229 */ 230 231 /** expression handler copy callback */ 232 static 233 SCIP_DECL_EXPRCOPYHDLR(copyhdlrEntropy) 234 { /*lint --e{715}*/ 235 SCIP_CALL( SCIPincludeExprhdlrEntropy(scip) ); 236 237 return SCIP_OKAY; 238 } 239 240 /** simplifies an entropy expression */ 241 static 242 SCIP_DECL_EXPRSIMPLIFY(simplifyEntropy) 243 { /*lint --e{715}*/ 244 SCIP_EXPR* child; 245 246 assert(scip != NULL); 247 assert(expr != NULL); 248 assert(simplifiedexpr != NULL); 249 assert(SCIPexprGetNChildren(expr) == 1); 250 251 child = SCIPexprGetChildren(expr)[0]; 252 assert(child != NULL); 253 254 /* check for value expression */ 255 if( SCIPisExprValue(scip, child) ) 256 { 257 SCIP_Real childvalue = SCIPgetValueExprValue(child); 258 259 /* TODO how to handle a negative value? */ 260 assert(childvalue >= 0.0); 261 262 if( childvalue == 0.0 || childvalue == 1.0 ) 263 { 264 SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, 0.0, ownercreate, ownercreatedata) ); 265 } 266 else 267 { 268 SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, -childvalue * log(childvalue), ownercreate, 269 ownercreatedata) ); 270 } 271 } 272 else 273 { 274 *simplifiedexpr = expr; 275 276 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */ 277 SCIPcaptureExpr(*simplifiedexpr); 278 } 279 280 /* TODO handle -x*log(x) = 0 if x in {0,1} */ 281 282 return SCIP_OKAY; 283 } 284 285 /** expression data copy callback */ 286 static 287 SCIP_DECL_EXPRCOPYDATA(copydataEntropy) 288 { /*lint --e{715}*/ 289 assert(targetexprdata != NULL); 290 assert(sourceexpr != NULL); 291 assert(SCIPexprGetData(sourceexpr) == NULL); 292 293 *targetexprdata = NULL; 294 return SCIP_OKAY; 295 } 296 297 /** expression data free callback */ 298 static 299 SCIP_DECL_EXPRFREEDATA(freedataEntropy) 300 { /*lint --e{715}*/ 301 assert(expr != NULL); 302 303 SCIPexprSetData(expr, NULL); 304 return SCIP_OKAY; 305 } 306 307 /** expression parse callback */ 308 static 309 SCIP_DECL_EXPRPARSE(parseEntropy) 310 { /*lint --e{715}*/ 311 SCIP_EXPR* childexpr; 312 313 assert(expr != NULL); 314 315 /* parse child expression from remaining string */ 316 SCIP_CALL( SCIPparseExpr(scip, &childexpr, string, endstring, ownercreate, ownercreatedata) ); 317 assert(childexpr != NULL); 318 319 /* create entropy expression */ 320 SCIP_CALL( SCIPcreateExprEntropy(scip, expr, childexpr, ownercreate, ownercreatedata) ); 321 assert(*expr != NULL); 322 323 /* release child expression since it has been captured by the entropy expression */ 324 SCIP_CALL( SCIPreleaseExpr(scip, &childexpr) ); 325 326 *success = TRUE; 327 328 return SCIP_OKAY; 329 } 330 331 332 /** expression (point-) evaluation callback */ 333 static 334 SCIP_DECL_EXPREVAL(evalEntropy) 335 { /*lint --e{715}*/ 336 SCIP_Real childvalue; 337 338 assert(expr != NULL); 339 assert(SCIPexprGetData(expr) == NULL); 340 assert(SCIPexprGetNChildren(expr) == 1); 341 assert(SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[0]) != SCIP_INVALID); /*lint !e777*/ 342 343 childvalue = SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[0]); 344 345 if( childvalue < 0.0 ) 346 { 347 SCIPdebugMsg(scip, "invalid evaluation of entropy expression\n"); 348 *val = SCIP_INVALID; 349 } 350 else if( childvalue == 0.0 || childvalue == 1.0 ) 351 { 352 /* -x*log(x) = 0 iff x in {0,1} */ 353 *val = 0.0; 354 } 355 else 356 { 357 *val = -childvalue * log(childvalue); 358 } 359 360 return SCIP_OKAY; 361 } 362 363 /** expression derivative evaluation callback */ 364 static 365 SCIP_DECL_EXPRBWDIFF(bwdiffEntropy) 366 { /*lint --e{715}*/ 367 SCIP_EXPR* child; 368 SCIP_Real childvalue; 369 370 assert(expr != NULL); 371 assert(childidx == 0); 372 assert(SCIPexprGetNChildren(expr) == 1); 373 assert(SCIPexprGetEvalValue(expr) != SCIP_INVALID); /*lint !e777*/ 374 375 child = SCIPexprGetChildren(expr)[0]; 376 assert(child != NULL); 377 assert(!SCIPisExprValue(scip, child)); 378 379 childvalue = SCIPexprGetEvalValue(child); 380 381 /* derivative is not defined for x = 0 */ 382 if( childvalue <= 0.0 ) 383 *val = SCIP_INVALID; 384 else 385 *val = -1.0 - log(childvalue); 386 387 return SCIP_OKAY; 388 } 389 390 /** expression interval evaluation callback */ 391 static 392 SCIP_DECL_EXPRINTEVAL(intevalEntropy) 393 { /*lint --e{715}*/ 394 SCIP_INTERVAL childinterval; 395 396 assert(expr != NULL); 397 assert(SCIPexprGetData(expr) == NULL); 398 assert(SCIPexprGetNChildren(expr) == 1); 399 400 childinterval = SCIPexprGetActivity(SCIPexprGetChildren(expr)[0]); 401 402 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childinterval) ) 403 SCIPintervalSetEmpty(interval); 404 else 405 SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, interval, childinterval); 406 407 return SCIP_OKAY; 408 } 409 410 /** expression estimator callback */ 411 static 412 SCIP_DECL_EXPRESTIMATE(estimateEntropy) 413 { /*lint --e{715}*/ 414 assert(scip != NULL); 415 assert(expr != NULL); 416 assert(localbounds != NULL); 417 assert(globalbounds != NULL); 418 assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0); 419 assert(refpoint != NULL); 420 assert(coefs != NULL); 421 assert(constant != NULL); 422 assert(islocal != NULL); 423 assert(branchcand != NULL); 424 assert(*branchcand == TRUE); 425 assert(success != NULL); 426 427 *success = FALSE; 428 429 /* use secant for underestimate (locally valid) */ 430 if( !overestimate ) 431 { 432 SCIP_Real lb; 433 SCIP_Real ub; 434 SCIP_Real vallb; 435 SCIP_Real valub; 436 437 lb = localbounds[0].inf; 438 ub = localbounds[0].sup; 439 440 if( lb < 0.0 || SCIPisInfinity(scip, ub) || SCIPisEQ(scip, lb, ub) ) 441 return SCIP_OKAY; 442 443 assert(lb >= 0.0 && ub >= 0.0); 444 assert(ub - lb != 0.0); 445 446 vallb = (lb == 0.0) ? 0.0 : -lb * log(lb); 447 valub = (ub == 0.0) ? 0.0 : -ub * log(ub); 448 449 coefs[0] = (valub - vallb) / (ub - lb); 450 *constant = valub - coefs[0] * ub; 451 assert(SCIPisEQ(scip, *constant, vallb - coefs[0] * lb)); 452 453 *islocal = TRUE; 454 } 455 /* use gradient cut for overestimate (globally valid) */ 456 else 457 { 458 if( !SCIPisPositive(scip, refpoint[0]) ) 459 { 460 /* if refpoint is 0 (then lb=0 probably) or negative, then slope is infinite (or not defined), then try to move away from 0 */ 461 if( SCIPisZero(scip, localbounds[0].sup) ) 462 return SCIP_OKAY; 463 464 refpoint[0] = SCIPepsilon(scip); 465 } 466 467 /* -x*(1+log(x*)) + x* <= -x*log(x) */ 468 coefs[0] = -(1.0 + log(refpoint[0])); 469 *constant = refpoint[0]; 470 471 *islocal = FALSE; 472 *branchcand = FALSE; 473 } 474 475 /* give up if the constant or coefficient is too large */ 476 if( SCIPisInfinity(scip, REALABS(*constant)) || SCIPisInfinity(scip, REALABS(coefs[0])) ) 477 return SCIP_OKAY; 478 479 *success = TRUE; 480 481 return SCIP_OKAY; 482 } 483 484 /** initial estimates callback */ 485 static 486 SCIP_DECL_EXPRINITESTIMATES(initestimatesEntropy) 487 { /*lint --e{715}*/ 488 SCIP_Real refpointsover[3] = {SCIP_INVALID, SCIP_INVALID, SCIP_INVALID}; 489 SCIP_Bool overest[4] = {TRUE, TRUE, TRUE, FALSE}; 490 SCIP_Real lb; 491 SCIP_Real ub; 492 int i; 493 494 assert(scip != NULL); 495 assert(expr != NULL); 496 assert(SCIPexprGetNChildren(expr) == 1); 497 assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0); 498 499 lb = bounds[0].inf; 500 ub = bounds[0].sup; 501 502 if( SCIPisEQ(scip, lb, ub) ) 503 return SCIP_OKAY; 504 505 if( overestimate ) 506 { 507 /* adjust lb */ 508 lb = MAX(lb, SCIPepsilon(scip)); /*lint !e666*/ 509 510 refpointsover[0] = lb; 511 refpointsover[1] = SCIPisInfinity(scip, ub) ? lb + 2.0 : (lb + ub) / 2; 512 refpointsover[2] = SCIPisInfinity(scip, ub) ? lb + 20.0 : ub; 513 } 514 515 *nreturned = 0; 516 517 for( i = 0; i < 4; ++i ) 518 { 519 if( (overest[i] && !overestimate) || (!overest[i] && (overestimate || SCIPisInfinity(scip, ub))) ) 520 continue; 521 522 assert(!overest[i] || (SCIPisLE(scip, refpointsover[i], ub) && SCIPisGE(scip, refpointsover[i], lb))); /*lint !e661*/ 523 524 if( overest[i] ) 525 { /*lint !e661*/ 526 /* -x*(1+log(x*)) + x* <= -x*log(x) */ 527 assert(i < 3); 528 /* coverity[overrun] */ 529 coefs[*nreturned][0] = -(1.0 + log(refpointsover[i])); 530 /* coverity[overrun] */ 531 constant[*nreturned] = refpointsover[i]; 532 } 533 else 534 { 535 assert(lb > 0.0 && ub >= 0.0); 536 assert(ub - lb != 0.0); 537 538 coefs[*nreturned][0] = (-ub * log(ub) + lb * log(lb)) / (ub - lb); 539 constant[*nreturned] = -ub * log(ub) - coefs[*nreturned][0] * ub; 540 assert(SCIPisEQ(scip, constant[*nreturned], -lb * log(lb) - coefs[*nreturned][0] * lb)); 541 } 542 543 ++(*nreturned); 544 } 545 546 return SCIP_OKAY; 547 } 548 549 /** expression reverse propagation callback */ 550 static 551 SCIP_DECL_EXPRREVERSEPROP(reversepropEntropy) 552 { /*lint --e{715}*/ 553 SCIP_INTERVAL newinterval; 554 555 assert(scip != NULL); 556 assert(expr != NULL); 557 assert(SCIPexprGetNChildren(expr) == 1); 558 assert(childrenbounds != NULL); 559 assert(infeasible != NULL); 560 561 /* compute resulting intervals (reverseProp handles childinterval being empty) */ 562 SCIP_CALL( reverseProp(scip, bounds, childrenbounds[0], &newinterval) ); 563 assert(SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, newinterval) || newinterval.inf >= 0.0); 564 565 childrenbounds[0] = newinterval; 566 567 return SCIP_OKAY; 568 } 569 570 /** entropy hash callback */ 571 static 572 SCIP_DECL_EXPRHASH(hashEntropy) 573 { /*lint --e{715}*/ 574 assert(expr != NULL); 575 assert(SCIPexprGetNChildren(expr) == 1); 576 assert(hashkey != NULL); 577 assert(childrenhashes != NULL); 578 579 *hashkey = EXPRHDLR_HASHKEY; 580 *hashkey ^= childrenhashes[0]; 581 582 return SCIP_OKAY; 583 } 584 585 /** expression curvature detection callback */ 586 static 587 SCIP_DECL_EXPRCURVATURE(curvatureEntropy) 588 { /*lint --e{715}*/ 589 assert(scip != NULL); 590 assert(expr != NULL); 591 assert(childcurv != NULL); 592 assert(success != NULL); 593 assert(SCIPexprGetNChildren(expr) == 1); 594 595 /* to be concave, the child needs to be concave, too; we cannot be convex or linear */ 596 if( exprcurvature == SCIP_EXPRCURV_CONCAVE ) 597 { 598 *childcurv = SCIP_EXPRCURV_CONCAVE; 599 *success = TRUE; 600 } 601 else 602 *success = FALSE; 603 604 return SCIP_OKAY; 605 } 606 607 /** expression monotonicity detection callback */ 608 static 609 SCIP_DECL_EXPRMONOTONICITY(monotonicityEntropy) 610 { /*lint --e{715}*/ 611 SCIP_EXPR* child; 612 SCIP_INTERVAL childbounds; 613 SCIP_Real brpoint = exp(-1.0); 614 615 assert(scip != NULL); 616 assert(expr != NULL); 617 assert(result != NULL); 618 assert(childidx == 0); 619 620 child = SCIPexprGetChildren(expr)[0]; 621 assert(child != NULL); 622 623 SCIP_CALL( SCIPevalExprActivity(scip, child) ); 624 childbounds = SCIPexprGetActivity(child); 625 626 if( childbounds.sup <= brpoint ) 627 *result = SCIP_MONOTONE_INC; 628 else if( childbounds.inf >= brpoint ) 629 *result = SCIP_MONOTONE_DEC; 630 else 631 *result = SCIP_MONOTONE_UNKNOWN; 632 633 return SCIP_OKAY; 634 } 635 636 /** expression integrality detection callback */ 637 static 638 SCIP_DECL_EXPRINTEGRALITY(integralityEntropy) 639 { /*lint --e{715}*/ 640 assert(scip != NULL); 641 assert(expr != NULL); 642 assert(isintegral != NULL); 643 644 /* TODO it is possible to check for the special case that the child is integral and its bounds are [0,1]; in 645 * this case the entropy expression can only achieve 0 and is thus integral 646 */ 647 *isintegral = FALSE; 648 649 return SCIP_OKAY; 650 } 651 652 /** creates the handler for entropy expressions and includes it into SCIP */ 653 SCIP_RETCODE SCIPincludeExprhdlrEntropy( 654 SCIP* scip /**< SCIP data structure */ 655 ) 656 { 657 SCIP_EXPRHDLRDATA* exprhdlrdata; 658 SCIP_EXPRHDLR* exprhdlr; 659 660 /* create expression handler data */ 661 exprhdlrdata = NULL; 662 663 /* include expression handler */ 664 SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, EXPRHDLR_NAME, EXPRHDLR_DESC, EXPRHDLR_PRECEDENCE, 665 evalEntropy, exprhdlrdata) ); 666 assert(exprhdlr != NULL); 667 668 SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrEntropy, NULL); 669 SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataEntropy, freedataEntropy); 670 SCIPexprhdlrSetSimplify(exprhdlr, simplifyEntropy); 671 SCIPexprhdlrSetParse(exprhdlr, parseEntropy); 672 SCIPexprhdlrSetIntEval(exprhdlr, intevalEntropy); 673 SCIPexprhdlrSetEstimate(exprhdlr, initestimatesEntropy, estimateEntropy); 674 SCIPexprhdlrSetReverseProp(exprhdlr, reversepropEntropy); 675 SCIPexprhdlrSetHash(exprhdlr, hashEntropy); 676 SCIPexprhdlrSetDiff(exprhdlr, bwdiffEntropy, NULL ,NULL); 677 SCIPexprhdlrSetCurvature(exprhdlr, curvatureEntropy); 678 SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityEntropy); 679 SCIPexprhdlrSetIntegrality(exprhdlr, integralityEntropy); 680 681 return SCIP_OKAY; 682 } 683 684 /** creates an entropy expression */ 685 SCIP_RETCODE SCIPcreateExprEntropy( 686 SCIP* scip, /**< SCIP data structure */ 687 SCIP_EXPR** expr, /**< pointer where to store expression */ 688 SCIP_EXPR* child, /**< child expression */ 689 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */ 690 void* ownercreatedata /**< data to pass to ownercreate */ 691 ) 692 { 693 SCIP_EXPRHDLR* exprhdlr; 694 SCIP_EXPRDATA* exprdata; 695 696 assert(expr != NULL); 697 assert(child != NULL); 698 699 exprhdlr = SCIPfindExprhdlr(scip, EXPRHDLR_NAME); 700 assert(exprhdlr != NULL); 701 702 /* create expression data */ 703 exprdata = NULL; 704 705 /* create expression */ 706 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 1, &child, ownercreate, ownercreatedata) ); 707 708 return SCIP_OKAY; 709 } 710 711 /** indicates whether expression is of entropy-type */ /*lint -e{715}*/ 712 SCIP_Bool SCIPisExprEntropy( 713 SCIP* scip, /**< SCIP data structure */ 714 SCIP_EXPR* expr /**< expression */ 715 ) 716 { /*lint --e{715}*/ 717 assert(expr != NULL); 718 719 return strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0; 720 } 721