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 history.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for branching and inference history 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #include <assert.h> 34 35 #include "scip/def.h" 36 #include "scip/set.h" 37 #include "scip/history.h" 38 #include "scip/pub_misc.h" 39 #include "scip/pub_history.h" 40 #include "scip/pub_message.h" 41 42 #ifndef NDEBUG 43 #include "scip/struct_history.h" 44 #endif 45 46 /* 47 * methods for branching and inference history 48 */ 49 50 /** creates an empty history entry */ 51 SCIP_RETCODE SCIPhistoryCreate( 52 SCIP_HISTORY** history, /**< pointer to store branching and inference history */ 53 BMS_BLKMEM* blkmem /**< block memory */ 54 ) 55 { 56 assert(history != NULL); 57 58 SCIP_ALLOC( BMSallocBlockMemory(blkmem, history) ); 59 60 SCIPhistoryReset(*history); 61 62 return SCIP_OKAY; 63 } 64 65 /** frees a history entry */ 66 void SCIPhistoryFree( 67 SCIP_HISTORY** history, /**< pointer to branching and inference history */ 68 BMS_BLKMEM* blkmem /**< block memory */ 69 ) 70 { 71 assert(history != NULL); 72 assert(*history != NULL); 73 74 BMSfreeBlockMemory(blkmem, history); 75 } 76 77 /** resets history entry to zero */ 78 void SCIPhistoryReset( 79 SCIP_HISTORY* history /**< branching and inference history */ 80 ) 81 { 82 assert(history != NULL); 83 84 history->pscostcount[0] = 0.0; 85 history->pscostcount[1] = 0.0; 86 history->pscostweightedmean[0] = 0.0; 87 history->pscostweightedmean[1] = 0.0; 88 history->pscostvariance[0] = 0.0; 89 history->pscostvariance[1] = 0.0; 90 history->vsids[0] = 0.0; 91 history->vsids[1] = 0.0; 92 history->conflengthsum[0] = 0.0; 93 history->conflengthsum[1] = 0.0; 94 history->inferencesum[0] = 0.0; 95 history->inferencesum[1] = 0.0; 96 history->cutoffsum[0] = 0.0; 97 history->cutoffsum[1] = 0.0; 98 history->ratio = 0.0; 99 history->ratiovalid = FALSE; 100 history->balance = 0.0; 101 history->ngmi = 0; 102 history->gmieff = 0.0; 103 history->gmieffsum = 0.0; 104 history->nactiveconflicts[0] = 0; 105 history->nactiveconflicts[1] = 0; 106 history->nbranchings[0] = 0; 107 history->nbranchings[1] = 0; 108 history->branchdepthsum[0] = 0; 109 history->branchdepthsum[1] = 0; 110 } 111 112 /** unites two history entries by adding the values of the second one to the first one */ 113 void SCIPhistoryUnite( 114 SCIP_HISTORY* history, /**< branching and inference history */ 115 SCIP_HISTORY* addhistory, /**< history values to add to history */ 116 SCIP_Bool switcheddirs /**< should the history entries be united with switched directories */ 117 ) 118 { 119 int i; 120 121 assert(history != NULL); 122 assert(addhistory != NULL); 123 124 /* loop over both directions and combine the statistics */ 125 for( i = 0; i <= 1; ++i ) 126 { 127 int d; 128 d = (switcheddirs ? 1 - i : i); 129 130 history->pscostcount[i] += addhistory->pscostcount[d]; 131 132 /* if both histories a count of zero, there is nothing to do */ 133 if( history->pscostcount[i] > 0.0 ) 134 { 135 SCIP_Real oldmean; 136 137 oldmean = history->pscostweightedmean[i]; 138 139 /* we update the mean as if the history was one observation with a large weight */ 140 history->pscostweightedmean[i] += addhistory->pscostcount[d] * (addhistory->pscostweightedmean[d] - history->pscostweightedmean[i]) / history->pscostcount[i]; 141 142 /* we update the variance of two sets A and B as S_A+B = S_A + (mu_A)^2 * count_A ...*/ 143 /* @todo is there a numerically more stable variant for this merge? */ 144 history->pscostvariance[i] = history->pscostvariance[i] + oldmean * oldmean * (history->pscostcount[i] - addhistory->pscostcount[d]) + \ 145 /* S_B + (mu_B)^2 * count_B */ 146 addhistory->pscostvariance[d] + addhistory->pscostcount[d] * addhistory->pscostweightedmean[d] * addhistory->pscostweightedmean[d] - \ 147 /* - count_A+B * mu_A+B^ 2 */ 148 history->pscostcount[i] * history->pscostweightedmean[i] * history->pscostweightedmean[i]; 149 150 /* slight violations of nonnegativity are numerically possible */ 151 history->pscostvariance[i] = MAX(history->pscostvariance[i], 0.0); 152 } 153 #ifndef NDEBUG 154 else 155 { 156 assert(history->pscostweightedmean[i] == 0.0); 157 assert(history->pscostvariance[i] == 0.0); 158 } 159 #endif 160 161 history->vsids[i] += addhistory->vsids[d]; 162 history->conflengthsum[i] += addhistory->conflengthsum[d]; 163 history->inferencesum[i] += addhistory->inferencesum[d]; 164 history->cutoffsum[i] += addhistory->cutoffsum[d]; 165 history->nactiveconflicts[i] += addhistory->nactiveconflicts[d]; 166 history->nbranchings[i] += addhistory->nbranchings[d]; 167 history->branchdepthsum[i] += addhistory->branchdepthsum[d]; 168 } 169 } 170 171 /** updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta" 172 * in the LP's objective value 173 */ 174 void SCIPhistoryUpdatePseudocost( 175 SCIP_HISTORY* history, /**< branching and inference history */ 176 SCIP_SET* set, /**< global SCIP settings */ 177 SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */ 178 SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */ 179 SCIP_Real weight /**< weight of this update in pseudo cost sum (added to pscostcount) */ 180 ) 181 { 182 SCIP_Real distance; 183 SCIP_Real eps; 184 SCIP_Real sumcontribution; 185 SCIP_Real olddelta; 186 int dir; 187 188 assert(history != NULL); 189 assert(set != NULL); 190 assert(!SCIPsetIsInfinity(set, REALABS(solvaldelta))); 191 assert(!SCIPsetIsInfinity(set, objdelta)); 192 assert(!SCIPsetIsNegative(set, objdelta)); 193 assert(0.0 < weight && weight <= 1.0); 194 195 if( SCIPsetIsPositive(set, solvaldelta) ) 196 { 197 /* variable's solution value moved upwards */ 198 dir = 1; 199 distance = solvaldelta; 200 } 201 else if( SCIPsetIsNegative(set, solvaldelta) ) 202 { 203 /* variable's solution value moved downwards */ 204 dir = 0; 205 distance = -solvaldelta; 206 } 207 else 208 { 209 /* the variable's solution value didn't change, and the pseudo costs cannot be updated */ 210 return; 211 } 212 assert(dir == 0 || dir == 1); 213 assert(SCIPsetIsPositive(set, distance)); 214 215 /* apply a lower limit on the distance to avoid numerical instabilities due to very large summands */ 216 eps = SCIPsetPseudocosteps(set); 217 distance = MAX(distance, eps); 218 219 /* slightly increase objective delta, s.t. pseudo cost values are not zero, and fractionalities are 220 * always used at least a bit 221 */ 222 objdelta += SCIPsetPseudocostdelta(set); 223 224 sumcontribution = objdelta/distance; 225 /* update the pseudo cost values */ 226 olddelta = sumcontribution - history->pscostweightedmean[dir]; 227 history->pscostcount[dir] += weight; 228 history->pscostweightedmean[dir] += weight * olddelta / history->pscostcount[dir]; 229 history->pscostvariance[dir] = history->pscostvariance[dir] + weight * olddelta * (sumcontribution - history->pscostweightedmean[dir]); 230 231 SCIPsetDebugMsg(set, "updated pseudo costs of history %p: dir=%d, distance=%g, objdelta=%g, weight=%g -> %g/%g\n", 232 (void*)history, dir, distance, objdelta, weight, history->pscostcount[dir], history->pscostweightedmean[dir]); 233 } 234 235 /**@name Value based history 236 * 237 * Value based history methods 238 * 239 * @{ 240 */ 241 242 /** creates an empty value history */ 243 SCIP_RETCODE SCIPvaluehistoryCreate( 244 SCIP_VALUEHISTORY** valuehistory, /**< pointer to store the value based branching and inference histories */ 245 BMS_BLKMEM* blkmem /**< block memory */ 246 ) 247 { 248 assert(valuehistory != NULL); 249 250 SCIP_ALLOC( BMSallocBlockMemory(blkmem, valuehistory) ); 251 252 (*valuehistory)->nvalues = 0; 253 (*valuehistory)->sizevalues = 5; 254 255 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*valuehistory)->histories, (*valuehistory)->sizevalues) ); 256 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*valuehistory)->values, (*valuehistory)->sizevalues) ); 257 258 return SCIP_OKAY; 259 } 260 261 /** frees a value history */ 262 void SCIPvaluehistoryFree( 263 SCIP_VALUEHISTORY** valuehistory, /**< pointer to value based history */ 264 BMS_BLKMEM* blkmem /**< block memory */ 265 ) 266 { 267 assert(valuehistory != NULL); 268 269 if( *valuehistory != NULL ) 270 { 271 int i; 272 273 for( i = (*valuehistory)->nvalues-1; i >= 0; --i ) 274 SCIPhistoryFree(&(*valuehistory)->histories[i], blkmem); 275 276 BMSfreeBlockMemoryArray(blkmem, &(*valuehistory)->histories, (*valuehistory)->sizevalues); 277 BMSfreeBlockMemoryArray(blkmem, &(*valuehistory)->values, (*valuehistory)->sizevalues); 278 279 BMSfreeBlockMemory(blkmem, valuehistory); 280 } 281 } 282 283 /** finds for the given domain value the history if it does not exist yet it will be created */ 284 SCIP_RETCODE SCIPvaluehistoryFind( 285 SCIP_VALUEHISTORY* valuehistory, /**< value based history */ 286 BMS_BLKMEM* blkmem, /**< block memory */ 287 SCIP_SET* set, /**< global SCIP settings */ 288 SCIP_Real value, /**< domain value of interest */ 289 SCIP_HISTORY** history /**< pointer to store the history for the given domain value */ 290 ) 291 { 292 int pos; 293 294 assert(valuehistory != NULL); 295 assert(blkmem != NULL); 296 assert(set != NULL); 297 assert(history != NULL); 298 299 *history = NULL; 300 301 if( valuehistory->nvalues == 0 || !SCIPsortedvecFindReal(valuehistory->values, value, valuehistory->nvalues, &pos) ) 302 { 303 /* check if we need to resize the history array */ 304 if( valuehistory->nvalues == valuehistory->sizevalues ) 305 { 306 int newsize; 307 308 newsize = SCIPsetCalcMemGrowSize(set, valuehistory->sizevalues + 1); 309 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &valuehistory->histories, valuehistory->nvalues, newsize) ); 310 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &valuehistory->values, valuehistory->nvalues, newsize) ); 311 valuehistory->sizevalues = newsize; 312 } 313 314 /* create new empty history entry */ 315 SCIP_CALL( SCIPhistoryCreate(history, blkmem) ); 316 317 /* insert new history into the value based history array */ 318 SCIPsortedvecInsertRealPtr(valuehistory->values, (void**)valuehistory->histories, value, (void*)(*history), &valuehistory->nvalues, NULL); 319 } 320 else 321 (*history) = valuehistory->histories[pos]; /*lint !e530*/ 322 323 assert(*history != NULL); 324 325 return SCIP_OKAY; 326 } 327 328 /** scales the conflict score values with the given scalar for each value history entry */ 329 void SCIPvaluehistoryScaleVSIDS( 330 SCIP_VALUEHISTORY* valuehistory, /**< value based history */ 331 SCIP_Real scalar /**< scalar to multiply the conflict scores with */ 332 ) 333 { 334 if( valuehistory != NULL ) 335 { 336 int i; 337 338 for( i = valuehistory->nvalues-1; i >= 0; --i ) 339 { 340 SCIPhistoryScaleVSIDS(valuehistory->histories[i], scalar); 341 } 342 } 343 } 344 345 346 /* 347 * simple functions implemented as defines 348 */ 349 350 #ifndef NDEBUG 351 352 /* In debug mode, the following methods are implemented as function calls to ensure 353 * type validity. 354 * In optimized mode, the methods are implemented as defines to improve performance. 355 * However, we want to have them in the library anyways, so we have to undef the defines. 356 */ 357 358 #undef SCIPvaluehistoryGetNValues 359 #undef SCIPvaluehistoryGetHistories 360 #undef SCIPvaluehistoryGetValues 361 362 /** return the number of (domain) values for which a history exists */ 363 int SCIPvaluehistoryGetNValues( 364 SCIP_VALUEHISTORY* valuehistory /**< value based history */ 365 ) 366 { 367 assert(valuehistory != NULL); 368 369 return valuehistory->nvalues; 370 } 371 372 /** return the array containing the histories for the individual (domain) values */ 373 SCIP_HISTORY** SCIPvaluehistoryGetHistories( 374 SCIP_VALUEHISTORY* valuehistory /**< value based history */ 375 ) 376 { 377 assert(valuehistory != NULL); 378 379 return valuehistory->histories; 380 } 381 382 /** return the array containing the (domain) values for which a history exists */ 383 SCIP_Real* SCIPvaluehistoryGetValues( 384 SCIP_VALUEHISTORY* valuehistory /**< value based history */ 385 ) 386 { 387 assert(valuehistory != NULL); 388 389 return valuehistory->values; 390 } 391 392 #endif 393 394 /**@} */ 395 396 /* 397 * simple functions implemented as defines 398 */ 399 400 #ifndef NDEBUG 401 402 /* In debug mode, the following methods are implemented as function calls to ensure 403 * type validity. 404 * In optimized mode, the methods are implemented as defines to improve performance. 405 * However, we want to have them in the library anyways, so we have to undef the defines. 406 */ 407 408 #undef SCIPbranchdirOpposite 409 #undef SCIPhistoryGetPseudocost 410 #undef SCIPhistoryGetPseudocostCount 411 #undef SCIPhistoryIsPseudocostEmpty 412 #undef SCIPhistoryIncVSIDS 413 #undef SCIPhistoryScaleVSIDS 414 #undef SCIPhistoryGetVSIDS 415 #undef SCIPhistoryIncNActiveConflicts 416 #undef SCIPhistoryGetNActiveConflicts 417 #undef SCIPhistoryGetAvgConflictlength 418 #undef SCIPhistoryIncNBranchings 419 #undef SCIPhistoryIncInferenceSum 420 #undef SCIPhistoryIncCutoffSum 421 #undef SCIPhistoryGetNBranchings 422 #undef SCIPhistoryGetInferenceSum 423 #undef SCIPhistoryGetAvgInferences 424 #undef SCIPhistoryGetCutoffSum 425 #undef SCIPhistoryGetAvgCutoffs 426 #undef SCIPhistoryGetAvgBranchdepth 427 #undef SCIPhistoryIsRatioValid 428 #undef SCIPhistoryGetLastRatio 429 #undef SCIPhistorySetRatioHistory 430 #undef SCIPhistoryGetLastBalance 431 #undef SCIPhistorySetLastGMIeff 432 #undef SCIPhistoryGetLastGMIeff 433 #undef SCIPhistoryIncGMIeffSum 434 #undef SCIPhistoryGetAvgGMIeff 435 436 /** returns the opposite direction of the given branching direction */ 437 SCIP_BRANCHDIR SCIPbranchdirOpposite( 438 SCIP_BRANCHDIR dir /**< branching direction */ 439 ) 440 { 441 return (dir == SCIP_BRANCHDIR_DOWNWARDS ? SCIP_BRANCHDIR_UPWARDS 442 : (dir == SCIP_BRANCHDIR_UPWARDS ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_AUTO)); 443 } 444 445 /** returns the expected dual gain for moving the corresponding variable by "solvaldelta" */ 446 SCIP_Real SCIPhistoryGetPseudocost( 447 SCIP_HISTORY* history, /**< branching and inference history */ 448 SCIP_Real solvaldelta /**< difference of variable's new LP value - old LP value */ 449 ) 450 { 451 assert(history != NULL); 452 453 if( solvaldelta >= 0.0 ) 454 return solvaldelta * (history->pscostcount[1] > 0.0 ? history->pscostweightedmean[1] : 1.0); 455 else 456 return -solvaldelta * (history->pscostcount[0] > 0.0 ? history->pscostweightedmean[0] : 1.0); 457 } 458 459 /** returns the variance of pseudo costs about the mean. */ 460 SCIP_Real SCIPhistoryGetPseudocostVariance( 461 SCIP_HISTORY* history, /**< branching and inference history */ 462 SCIP_BRANCHDIR direction /**< direction of variable: 1 for upwards history, 0 for downwards history */ 463 ) 464 { 465 int dir; 466 SCIP_Real correctionfactor; 467 468 assert(history != NULL); 469 assert(direction == SCIP_BRANCHDIR_UPWARDS || direction == SCIP_BRANCHDIR_DOWNWARDS); 470 471 dir = (direction == SCIP_BRANCHDIR_UPWARDS ? 1 : 0); 472 correctionfactor = history->pscostcount[dir] - 1.0; 473 474 /** @todo for an unbiased estimate of the weighted sample variance, we need a correction factor that uses the sum of squared weights */ 475 if( correctionfactor > 0.9 ) 476 return history->pscostvariance[dir] / correctionfactor; 477 else 478 return 0.0; 479 } 480 481 /** returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in 482 * the given branching direction 483 */ 484 SCIP_Real SCIPhistoryGetPseudocostCount( 485 SCIP_HISTORY* history, /**< branching and inference history */ 486 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 487 ) 488 { 489 assert(history != NULL); 490 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 491 assert((int)dir == 0 || (int)dir == 1); 492 493 return history->pscostcount[dir]; 494 } 495 496 /** returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet) */ 497 SCIP_Bool SCIPhistoryIsPseudocostEmpty( 498 SCIP_HISTORY* history, /**< branching and inference history */ 499 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 500 ) 501 { 502 assert(history != NULL); 503 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 504 assert((int)dir == 0 || (int)dir == 1); 505 506 return (history->pscostcount[dir] == 0.0); 507 } 508 509 /** increases the conflict score of the history entry by the given weight */ 510 void SCIPhistoryIncVSIDS( 511 SCIP_HISTORY* history, /**< branching and inference history */ 512 SCIP_BRANCHDIR dir, /**< branching direction */ 513 SCIP_Real weight /**< weight of this update in conflict score */ 514 ) 515 { 516 assert(history != NULL); 517 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 518 assert((int)dir == 0 || (int)dir == 1); 519 520 history->vsids[dir] += weight; 521 } 522 523 /** scales the conflict score values with the given scalar */ 524 void SCIPhistoryScaleVSIDS( 525 SCIP_HISTORY* history, /**< branching and inference history */ 526 SCIP_Real scalar /**< scalar to multiply the conflict scores with */ 527 ) 528 { 529 assert(history != NULL); 530 531 history->vsids[0] *= scalar; 532 history->vsids[1] *= scalar; 533 } 534 535 /** gets the conflict score of the history entry */ 536 SCIP_Real SCIPhistoryGetVSIDS( 537 SCIP_HISTORY* history, /**< branching and inference history */ 538 SCIP_BRANCHDIR dir /**< branching direction */ 539 ) 540 { 541 assert(history != NULL); 542 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 543 assert((int)dir == 0 || (int)dir == 1); 544 545 return history->vsids[dir]; 546 } 547 548 /** increases the number of active conflicts by one and the overall length of the history entry by the given weight */ 549 void SCIPhistoryIncNActiveConflicts( 550 SCIP_HISTORY* history, /**< branching and inference history */ 551 SCIP_BRANCHDIR dir, /**< branching direction */ 552 SCIP_Real length /**< length of the conflict */ 553 ) 554 { 555 assert(history != NULL); 556 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 557 assert((int)dir == 0 || (int)dir == 1); 558 assert(length >= 0.0); 559 560 history->nactiveconflicts[dir]++; 561 history->conflengthsum[dir] += length; 562 } 563 564 /** gets the number of active conflicts of the history entry */ 565 SCIP_Longint SCIPhistoryGetNActiveConflicts( 566 SCIP_HISTORY* history, /**< branching and inference history */ 567 SCIP_BRANCHDIR dir /**< branching direction */ 568 ) 569 { 570 assert(history != NULL); 571 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 572 assert((int)dir == 0 || (int)dir == 1); 573 574 return history->nactiveconflicts[dir]; 575 } 576 577 /** gets the average conflict length of the history entry */ 578 SCIP_Real SCIPhistoryGetAvgConflictlength( 579 SCIP_HISTORY* history, /**< branching and inference history */ 580 SCIP_BRANCHDIR dir /**< branching direction */ 581 ) 582 { 583 assert(history != NULL); 584 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 585 assert((int)dir == 0 || (int)dir == 1); 586 587 return history->conflengthsum[dir] > 0.0 ? (SCIP_Real)history->nactiveconflicts[dir]/(SCIP_Real)history->conflengthsum[dir] : 0.0; 588 } 589 590 /** increases the number of branchings counter */ 591 void SCIPhistoryIncNBranchings( 592 SCIP_HISTORY* history, /**< branching and inference history */ 593 SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */ 594 int depth /**< depth at which the bound change took place */ 595 ) 596 { 597 assert(history != NULL); 598 assert(depth >= 1); 599 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 600 assert((int)dir == 0 || (int)dir == 1); 601 602 history->nbranchings[dir]++; 603 history->branchdepthsum[dir] += depth; 604 } 605 606 /** increases the number of inferences counter by a certain value */ 607 void SCIPhistoryIncInferenceSum( 608 SCIP_HISTORY* history, /**< branching and inference history */ 609 SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */ 610 SCIP_Real weight /**< weight of this update in inference score */ 611 ) 612 { 613 assert(history != NULL); 614 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 615 assert((int)dir == 0 || (int)dir == 1); 616 assert(history->nbranchings[dir] >= 1); 617 assert(weight >= 0.0); 618 619 history->inferencesum[dir] += weight; 620 } 621 622 /** increases the number of cutoffs counter */ 623 void SCIPhistoryIncCutoffSum( 624 SCIP_HISTORY* history, /**< branching and inference history */ 625 SCIP_BRANCHDIR dir, /**< branching direction (downwards, or upwards) */ 626 SCIP_Real weight /**< weight of this update in cutoff score */ 627 ) 628 { 629 assert(history != NULL); 630 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 631 assert((int)dir == 0 || (int)dir == 1); 632 assert(history->nbranchings[dir] >= 1); 633 assert(weight >= 0.0); 634 635 history->cutoffsum[dir] += weight; 636 } 637 638 /** get number of branchings counter */ 639 SCIP_Longint SCIPhistoryGetNBranchings( 640 SCIP_HISTORY* history, /**< branching and inference history */ 641 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 642 ) 643 { 644 assert(history != NULL); 645 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 646 assert((int)dir == 0 || (int)dir == 1); 647 648 return history->nbranchings[dir]; 649 } 650 651 /** get number of inferences counter */ 652 SCIP_Real SCIPhistoryGetInferenceSum( 653 SCIP_HISTORY* history, /**< branching and inference history */ 654 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 655 ) 656 { 657 assert(history != NULL); 658 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 659 assert((int)dir == 0 || (int)dir == 1); 660 661 return history->inferencesum[dir]; 662 } 663 664 /** returns the average number of inferences per branching */ 665 SCIP_Real SCIPhistoryGetAvgInferences( 666 SCIP_HISTORY* history, /**< branching and inference history */ 667 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 668 ) 669 { 670 assert(history != NULL); 671 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 672 assert((int)dir == 0 || (int)dir == 1); 673 674 return history->nbranchings[dir] > 0 ? (SCIP_Real)history->inferencesum[dir]/(SCIP_Real)history->nbranchings[dir] : 0.0; 675 } 676 677 /** get number of cutoffs counter */ 678 SCIP_Real SCIPhistoryGetCutoffSum( 679 SCIP_HISTORY* history, /**< branching and inference history */ 680 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 681 ) 682 { 683 assert(history != NULL); 684 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 685 assert((int)dir == 0 || (int)dir == 1); 686 687 return history->cutoffsum[dir]; 688 } 689 690 /** returns the average number of cutoffs per branching */ 691 SCIP_Real SCIPhistoryGetAvgCutoffs( 692 SCIP_HISTORY* history, /**< branching and inference history */ 693 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 694 ) 695 { 696 assert(history != NULL); 697 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 698 assert((int)dir == 0 || (int)dir == 1); 699 700 return history->nbranchings[dir] > 0 ? (SCIP_Real)history->cutoffsum[dir]/(SCIP_Real)history->nbranchings[dir] : 0.0; 701 } 702 703 /** returns the average depth of bound changes due to branching */ 704 SCIP_Real SCIPhistoryGetAvgBranchdepth( 705 SCIP_HISTORY* history, /**< branching and inference history */ 706 SCIP_BRANCHDIR dir /**< branching direction (downwards, or upwards) */ 707 ) 708 { 709 assert(history != NULL); 710 assert(dir == SCIP_BRANCHDIR_DOWNWARDS || dir == SCIP_BRANCHDIR_UPWARDS); 711 assert((int)dir == 0 || (int)dir == 1); 712 713 return history->nbranchings[dir] > 0 ? (SCIP_Real)history->branchdepthsum[dir]/(SCIP_Real)history->nbranchings[dir] : 1.0; 714 } 715 716 /** returns true if the given history contains a valid ratio */ 717 SCIP_Bool SCIPhistoryIsRatioValid( 718 SCIP_HISTORY* history /**< branching and inference history */ 719 ) 720 { 721 assert(history != NULL); 722 723 return history->ratiovalid; 724 } 725 726 /** returns the most recent ratio computed given the variable history */ 727 SCIP_Real SCIPhistoryGetLastRatio( 728 SCIP_HISTORY* history /**< branching and inference history */ 729 ) 730 { 731 assert(history != NULL); 732 assert(history->ratiovalid); 733 734 return history->ratio; 735 } 736 737 /** returns the most recent value of r/l used to compute this variable's ratio */ 738 SCIP_Real SCIPhistoryGetLastBalance( 739 SCIP_HISTORY* history /**< branching and inference history */ 740 ) 741 { 742 assert(history != NULL); 743 assert(history->ratiovalid); 744 745 return history->balance; 746 } 747 748 /** returns the average efficacy value for the GMI cut produced by this variable */ 749 SCIP_Real SCIPhistoryGetAvgGMIeff( 750 SCIP_HISTORY* history /**< branching and inference history */ 751 ) 752 { 753 assert(history != NULL); 754 755 return history->ngmi > 0 ? history->gmieffsum / history->ngmi : 0.0; 756 } 757 758 /** increases the average efficacy value for the GMI cut produced by this variable */ 759 void SCIPhistoryIncGMIeffSum( 760 SCIP_HISTORY* history, /**< branching and inference history */ 761 SCIP_Real gmieff /**< normalized efficacy value of a cut which will increase gmieff */ 762 ) 763 { 764 assert(history != NULL); 765 assert(gmieff >= 0.0); 766 767 history->gmieffsum += gmieff; 768 history->ngmi += 1; 769 } 770 771 /** returns the most recent efficacy value for the GMI cut produced by this variable */ 772 SCIP_Real SCIPhistoryGetLastGMIeff( 773 SCIP_HISTORY* history /**< branching and inference history */ 774 ) 775 { 776 assert(history != NULL); 777 778 return history->gmieff; 779 } 780 781 /** sets the new most recent efficacy value for the GMI cut produced by this variable */ 782 void SCIPhistorySetLastGMIeff( 783 SCIP_HISTORY* history, /**< branching and inference history */ 784 SCIP_Real gmieff /**< Efficacy of GMI cut produced from simplex tableau row of this var */ 785 ) 786 { 787 assert(history != NULL); 788 789 history->gmieff = gmieff; 790 } 791 792 /** sets the ratio history for a particular variable */ 793 void SCIPhistorySetRatioHistory( 794 SCIP_HISTORY* history, /**< branching and inference history */ 795 SCIP_Bool valid, /**< True iff the ratio computed is valid */ 796 SCIP_Real ratio, /**< Ratio of the characteristic polynomial with gains (1, rightgain/leftgain) */ 797 SCIP_Real balance /**< The value of rightgain/leftgain */ 798 ) 799 { 800 assert(history != NULL); 801 802 history->ratiovalid = valid; 803 history->ratio = ratio; 804 history->balance = balance; 805 } 806 807 #endif 808