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 branch_inference.c 26 * @ingroup DEFPLUGINS_BRANCH 27 * @brief inference history branching rule 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Stefan Heinz 31 */ 32 33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 34 35 #include "scip/branch_inference.h" 36 #include "scip/pub_branch.h" 37 #include "scip/pub_history.h" 38 #include "scip/pub_message.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_branch.h" 41 #include "scip/scip_message.h" 42 #include "scip/scip_mem.h" 43 #include "scip/scip_numerics.h" 44 #include "scip/scip_param.h" 45 #include "scip/scip_var.h" 46 #include <string.h> 47 48 49 /**@name Branching rule properties 50 * 51 * @{ 52 */ 53 54 #define BRANCHRULE_NAME "inference" 55 #define BRANCHRULE_DESC "inference history branching" 56 #define BRANCHRULE_PRIORITY 1000 57 #define BRANCHRULE_MAXDEPTH -1 58 #define BRANCHRULE_MAXBOUNDDIST 1.0 59 60 /**@} */ 61 62 /**@name Default parameter values 63 * 64 * @{ 65 */ 66 67 #define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight in score calculations for conflict score */ 68 #define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight in score calculations for cutoff score */ 69 #define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight in score calculations for inference score */ 70 #define DEFAULT_RELIABLESCORE 0.001 /**< score which is seen to be reliable for a branching decision */ 71 #define DEFAULT_FRACTIONALS TRUE /**< should branching on LP solution be restricted to the fractional variables? */ 72 #define DEFAULT_USEWEIGHTEDSUM TRUE /**< should a weighted sum of inference, conflict and cutoff weights be used? */ 73 74 #define DEFAULT_CONFLICTPRIO 1 /**< priority value for using conflict weights in lex. order */ 75 #define DEFAULT_CUTOFFPRIO 1 /**< priority value for using cutoff weights in lex. order */ 76 77 /**@} */ 78 79 /** branching rule data */ 80 struct SCIP_BranchruleData 81 { 82 SCIP_Real conflictweight; /**< weight in score calculations for conflict score */ 83 SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */ 84 SCIP_Real inferenceweight; /**< weight in score calculations for inference score */ 85 SCIP_Real reliablescore; /**< score which is seen to be reliable for a branching decision */ 86 SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */ 87 SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */ 88 int conflictprio; /**< priority value for using conflict weights in lexicographic order */ 89 int cutoffprio; /**< priority value for using cutoff weights in lexicographic order */ 90 }; 91 92 /** evaluate the given candidate with the given score against the currently best know candidate, tiebreaking included */ 93 static 94 void evaluateValueCand( 95 SCIP_VAR* cand, /**< candidate to be checked */ 96 SCIP_Real score, /**< score of the candidate */ 97 SCIP_Real branchpoint, /**< potential branching point */ 98 SCIP_BRANCHDIR branchdir, /**< potential branching direction */ 99 SCIP_VAR** bestcand, /**< pointer to the currently best candidate */ 100 SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */ 101 SCIP_Real* bestbranchpoint, /**< pointer to store the (best) branching point */ 102 SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */ 103 ) 104 { 105 /* evaluate the candidate against the currently best candidate */ 106 if( *bestscore < score ) 107 { 108 /* the score of the candidate is better than the currently best know candidate */ 109 *bestscore = score; 110 *bestcand = cand; 111 *bestbranchpoint = branchpoint; 112 *bestbranchdir = branchdir; 113 } 114 else if( (*bestscore) == score ) /*lint !e777*/ 115 { 116 SCIP_Real bestobj; 117 SCIP_Real candobj; 118 119 bestobj = REALABS(SCIPvarGetObj(*bestcand)); 120 candobj = REALABS(SCIPvarGetObj(cand)); 121 122 /* the candidate has the same score as the best known candidate; therefore we use a second and third 123 * criteria to detect a unique best candidate; 124 * 125 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient 126 * since branching on that variable might trigger further propagation w.r.t. objective function 127 * - if the absolute values of the objective coefficient are equal the variable index is used to define a 128 * unique best candidate 129 * 130 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the 131 * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or 132 * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular, 133 * starting a probing mode might already change the order of these arrays. To be independent of that 134 * the selection should be unique. Otherwise, to selection process can get influenced by starting a 135 * probing or not. 136 */ 137 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/ 138 { 139 *bestcand = cand; 140 *bestbranchpoint = branchpoint; 141 *bestbranchdir = branchdir; 142 } 143 } 144 } 145 146 /** evaluate the given candidate with the given score against the currently best know candidate */ 147 static 148 void evaluateAggrCand( 149 SCIP* scip, /**< SCIP data structure */ 150 SCIP_VAR* cand, /**< candidate to be checked */ 151 SCIP_Real score, /**< score of the candidate */ 152 SCIP_Real val, /**< solution value of the candidate */ 153 SCIP_VAR** bestcand, /**< pointer to the currently best candidate */ 154 SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */ 155 SCIP_Real* bestval, /**< pointer to the solution value of the currently best candidate */ 156 SCIP_VAR** bestcands, /**< buffer array to return selected candidates */ 157 int* nbestcands /**< pointer to return number of selected candidates */ 158 ) 159 { 160 /* evaluate the candidate against the currently best candidate */ 161 /* TODO: consider a weaker comparison of some kind */ 162 if( *bestscore < score ) 163 { 164 /* the score of the candidate is better than the currently best know candidate, so it should be the first candidate in bestcands and nbestcands should be set to 1*/ 165 *bestscore = score; 166 *bestcand = cand; 167 *bestval = val; 168 *nbestcands = 1; 169 bestcands[0] = cand; 170 } 171 /* TODO: consider a weaker comparison of some kind */ 172 else if( SCIPisEQ(scip, *bestscore, score) ) 173 { 174 /* the score of the candidate is comparable to the currently known best, so we add it to bestcands and increase nbestcands by 1*/ 175 bestcands[*nbestcands] = cand; 176 (*nbestcands)++; 177 } 178 } 179 180 /** choose a singular best candidate from bestcands and move it to the beginning of the candidate array */ 181 static 182 void tiebreakAggrCand( 183 SCIP_VAR** bestcands, /**< buffer array to return selected candidates */ 184 int nbestcands /**< number of selected candidates */ 185 ) 186 { 187 int c; 188 189 for( c = 0; c < nbestcands; ++c ) 190 { 191 SCIP_Real bestobj; 192 SCIP_Real candobj; 193 194 bestobj = REALABS(SCIPvarGetObj(bestcands[0])); 195 candobj = REALABS(SCIPvarGetObj(bestcands[c])); 196 197 /* the candidate has the same score as the best known candidate; therefore we use a second and third 198 * criteria to detect a unique best candidate; 199 * 200 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient 201 * since branching on that variable might trigger further propagation w.r.t. objective function 202 * - if the absolute values of the objective coefficient are equal the variable index is used to define a 203 * unique best candidate 204 * 205 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the 206 * performance too much since the candidate array which is used here (SCIPgetPseudoBranchCands() or 207 * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular, 208 * starting a probing mode might already change the order of these arrays. To be independent of that 209 * the selection should be unique. Otherwise, to selection process can get influenced by starting a 210 * probing or not. 211 */ 212 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(bestcands[0]) < SCIPvarGetIndex(bestcands[c])) ) /*lint !e777*/ 213 { 214 bestcands[0] = bestcands[c]; 215 } 216 } 217 } 218 219 /** check if the score for the given domain value and variable domain value is better than the current best know one */ 220 static 221 void checkValueScore( 222 SCIP_Real value, /**< domain value */ 223 SCIP_HISTORY* history, /**< variable history for given donain value */ 224 SCIP_BRANCHDIR dir, /**< branching direction */ 225 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */ 226 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */ 227 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */ 228 SCIP_Real* bestscore, /**< pointer to store the best score */ 229 SCIP_Real* branchpoint, /**< pointer to store the (best) branching point */ 230 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */ 231 ) 232 { 233 SCIP_Real conflictscore; 234 SCIP_Real cutoffscore; 235 SCIP_Real score; 236 237 conflictscore = SCIPhistoryGetVSIDS(history, dir); 238 cutoffscore = SCIPhistoryGetCutoffSum(history, dir); 239 240 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be 241 * unreliable 242 */ 243 if( conflictscore < reliablescore ) 244 conflictscore = 0.0; 245 246 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */ 247 if( cutoffscore < reliablescore ) 248 cutoffscore = 0.0; 249 250 /* compute weight score */ 251 score = conflictweight * conflictscore + cutoffweight * cutoffscore; 252 253 if( score > *bestscore ) 254 { 255 (*bestscore) = score; 256 (*branchpoint) = value; 257 (*branchdir) = dir; 258 } 259 } 260 261 /** return an aggregated score for the given variable using the conflict score and cutoff score */ 262 static 263 SCIP_Real getAggrScore( 264 SCIP* scip, /**< SCIP data structure */ 265 SCIP_VAR* var, /**< problem variable */ 266 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */ 267 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */ 268 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */ 269 SCIP_Real reliablescore /**< score which is seen to be reliable for a branching decision */ 270 ) 271 { 272 SCIP_Real conflictscore; 273 SCIP_Real cutoffscore; 274 275 conflictscore = SCIPgetVarConflictScore(scip, var); 276 cutoffscore = SCIPgetVarAvgInferenceCutoffScore(scip, var, cutoffweight); 277 278 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be 279 * unreliable 280 */ 281 if( conflictscore < reliablescore ) 282 conflictscore = 0.0; 283 284 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */ 285 if( cutoffscore < reliablescore ) 286 cutoffscore = 0.0; 287 288 /* compute weighted score for the candidate */ 289 return (conflictweight * conflictscore + inferenceweight * cutoffscore); 290 } 291 292 /** return an aggregated score for the given variable using the conflict score and cutoff score */ 293 static 294 SCIP_Real getValueScore( 295 SCIP_VAR* var, /**< problem variable */ 296 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */ 297 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */ 298 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */ 299 SCIP_Real* branchpoint, /**< pointer to store the branching point */ 300 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */ 301 ) 302 { 303 SCIP_VALUEHISTORY* valuehistory; 304 SCIP_Real bestscore; 305 306 (*branchpoint) = SCIP_UNKNOWN; 307 (*branchdir) = SCIP_BRANCHDIR_UPWARDS; 308 309 valuehistory = SCIPvarGetValuehistory(var); 310 bestscore = 0.0; 311 312 if( valuehistory != NULL ) 313 { 314 SCIP_HISTORY** histories; 315 SCIP_Real* values; 316 int nvalues; 317 int v; 318 319 histories = SCIPvaluehistoryGetHistories(valuehistory); 320 values = SCIPvaluehistoryGetValues(valuehistory); 321 nvalues = SCIPvaluehistoryGetNValues(valuehistory); 322 323 for( v = 0; v < nvalues; ++v ) 324 { 325 SCIP_Real value; 326 327 value = values[v]; 328 329 /* skip all domain values which are smaller or equal to the lower bound */ 330 if( value <= SCIPvarGetLbLocal(var) ) 331 continue; 332 333 /* skip all domain values which are larger or equal to the upper bound */ 334 if( value >= SCIPvarGetUbLocal(var) ) 335 break; 336 337 /* check var <= value */ 338 checkValueScore(value, histories[v], SCIP_BRANCHDIR_DOWNWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir); 339 340 /* check var >= value */ 341 checkValueScore(value, histories[v], SCIP_BRANCHDIR_UPWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir); 342 } 343 } 344 345 return bestscore; 346 } 347 348 static 349 void selectBestCands( 350 SCIP* scip, /**< SCIP data structure */ 351 SCIP_VAR** cands, /**< candidate array */ 352 SCIP_Real* candsols, /**< array of candidate solution values, or NULL */ 353 int ncands, /**< number of candidates */ 354 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */ 355 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */ 356 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */ 357 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */ 358 SCIP_VAR** bestcands, /**< buffer array to return selected candidates */ 359 int* nbestcands /**< pointer to return number of selected candidates */ 360 ) 361 { 362 SCIP_VAR* bestaggrcand; 363 SCIP_Real bestval; 364 SCIP_Real bestaggrscore; 365 int c; 366 367 bestaggrcand = cands[0]; 368 assert(cands[0] != NULL); 369 370 bestval = candsols[0]; 371 bestcands[0] = cands[0]; 372 *nbestcands = 1; 373 374 /* get aggregated score for the first candidate */ 375 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore); 376 377 for( c = 1; c < ncands; ++c ) 378 { 379 SCIP_VAR* cand; 380 SCIP_Real val; 381 SCIP_Real aggrscore; 382 383 cand = cands[c]; 384 assert(cand != NULL); 385 386 val = candsols[c]; 387 388 /* get score for the candidate */ 389 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore); 390 391 /*lint -e777*/ 392 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand), 393 val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); 394 395 /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */ 396 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, nbestcands); 397 } 398 } /*lint --e{438}*/ 399 400 401 /** selects a variable out of the given candidate array and performs the branching */ 402 static 403 SCIP_RETCODE performBranchingSol( 404 SCIP* scip, /**< SCIP data structure */ 405 SCIP_VAR** cands, /**< candidate array */ 406 SCIP_Real* candsols, /**< array of candidate solution values, or NULL */ 407 int ncands, /**< number of candidates */ 408 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */ 409 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */ 410 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */ 411 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */ 412 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */ 413 SCIP_RESULT* result, /**< buffer to store result (branched, reduced domain, ...) */ 414 int conflictprio, /**< priority value for using conflict weights in lex. order */ 415 int cutoffprio /**< priority value for using conflict weights in lex. order */ 416 ) 417 { 418 SCIP_VAR* bestaggrcand; 419 SCIP_Real bestval; 420 SCIP_NODE* downchild; 421 SCIP_NODE* eqchild; 422 SCIP_NODE* upchild; 423 SCIP_VAR** bestcands; 424 int nbestcands; 425 int c; 426 427 assert(ncands > 0); 428 assert(result != NULL); 429 430 *result = SCIP_DIDNOTFIND; 431 432 /* check if conflict score, inferences, and cutoff score should be used in combination; otherwise just use 433 * inference */ 434 if( useweightedsum == FALSE ) 435 { 436 conflictprio = 0; 437 cutoffprio = 0; 438 conflictweight = 0.0; 439 inferenceweight = 1.0; 440 cutoffweight = 0.0; 441 } 442 443 /* allocate temporary memory */ 444 SCIP_CALL( SCIPallocClearBufferArray(scip, &bestcands, ncands) ); 445 nbestcands = 0; 446 447 if( conflictprio > cutoffprio ) 448 { 449 /* select the best candidates w.r.t. the first criterion */ 450 selectBestCands(scip, cands, candsols, ncands, conflictweight, 0.0, 0.0, reliablescore, 451 bestcands, &nbestcands); 452 453 /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and 454 * output, so the method must make sure to overwrite the last argument only at the very end */ 455 if( nbestcands > 1 ) 456 { 457 selectBestCands(scip, bestcands, candsols, nbestcands, 0.0, inferenceweight, cutoffweight, reliablescore, 458 bestcands, &nbestcands); 459 } 460 } 461 else if( conflictprio == cutoffprio ) 462 { 463 /* select the best candidates w.r.t. weighted sum of both criteria */ 464 selectBestCands(scip, cands, candsols, ncands, conflictweight, inferenceweight, cutoffweight, reliablescore, 465 bestcands, &nbestcands); 466 } 467 else 468 { 469 assert(conflictprio < cutoffprio); 470 471 /* select the best candidates w.r.t. the first criterion */ 472 selectBestCands(scip, cands, candsols, ncands, 0.0, inferenceweight, cutoffweight, reliablescore, 473 bestcands, &nbestcands); 474 475 /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and 476 * output, so the method must make sure to overwrite the last argument only at the very end */ 477 if( nbestcands > 1 ) 478 { 479 /* select the best candidates w.r.t. the first criterion */ 480 selectBestCands(scip, bestcands, candsols, nbestcands, conflictweight, 0.0, 0.0, reliablescore, 481 bestcands, &nbestcands); 482 } 483 } 484 485 assert(nbestcands == 0 || bestcands[0] != NULL); 486 487 /* final tie breaking */ 488 if( nbestcands > 1 ) 489 { 490 tiebreakAggrCand(bestcands, nbestcands); 491 nbestcands = 1; 492 } 493 494 assert(nbestcands == 1); 495 496 bestaggrcand = bestcands[0]; 497 bestval = -SCIP_INVALID; 498 499 /* loop over cands, find bestcands[0], and store corresponding candsols value in bestval */ 500 for( c = 0; c < ncands; ++c ) 501 { 502 if( bestaggrcand == cands[c] ) 503 { 504 bestval = candsols[c]; 505 break; 506 } 507 } 508 509 assert(bestval != -SCIP_INVALID); 510 511 /* free temporary memory */ 512 SCIPfreeBufferArray(scip, &bestcands); 513 514 assert(bestaggrcand != NULL); 515 516 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, conflict=%g cutoff=%g, inference=%g)\n", 517 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand), 518 bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, /*lint !e777*/ 519 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight), 520 SCIPgetVarAvgInferenceScore(scip, bestaggrcand)); 521 522 assert(candsols != NULL); 523 /* perform the branching */ 524 SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) ); 525 526 if( downchild != NULL || eqchild != NULL || upchild != NULL ) 527 { 528 *result = SCIP_BRANCHED; 529 } 530 else 531 { 532 /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */ 533 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand))); 534 *result = SCIP_REDUCEDDOM; 535 } 536 537 return SCIP_OKAY; 538 } 539 540 541 /** selects a variable out of the given candidate array and performs the branching */ 542 static 543 SCIP_RETCODE performBranchingNoSol( 544 SCIP* scip, /**< SCIP data structure */ 545 SCIP_VAR** cands, /**< candidate array */ 546 int ncands, /**< number of candidates */ 547 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */ 548 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */ 549 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */ 550 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */ 551 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */ 552 SCIP_RESULT* result /**< buffer to store result (branched, reduced domain, ...) */ 553 ) 554 { 555 SCIP_VAR* bestaggrcand; 556 SCIP_VAR* bestvaluecand; 557 SCIP_Real bestval; 558 SCIP_Real bestaggrscore; 559 SCIP_Real bestvaluescore; 560 SCIP_Real bestbranchpoint; 561 SCIP_BRANCHDIR bestbranchdir; 562 SCIP_NODE* downchild; 563 SCIP_NODE* eqchild; 564 SCIP_NODE* upchild; 565 SCIP_VAR** bestcands; 566 int nbestcands; 567 568 bestbranchpoint = SCIP_UNKNOWN; 569 bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS; 570 bestvaluescore = 0.0; 571 bestvaluecand = NULL; 572 573 assert(ncands > 0); 574 assert(result != NULL); 575 576 *result = SCIP_DIDNOTFIND; 577 578 /* allocate temporary memory */ 579 SCIP_CALL( SCIPallocBufferArray(scip, &bestcands, ncands) ); 580 nbestcands = 0; 581 582 /* check if the weighted sum between the average inferences and conflict score should be used */ 583 if( useweightedsum ) 584 { 585 int c; 586 587 bestaggrcand = cands[0]; 588 bestvaluecand = cands[0]; 589 assert(cands[0] != NULL); 590 591 bestval = SCIP_UNKNOWN; 592 593 /* get domain value score for the first candidate */ 594 bestvaluescore = getValueScore(cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir); 595 SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n", 596 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand), 597 bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore); 598 599 /* get aggregated score for the first candidate */ 600 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore); 601 602 for( c = 1; c < ncands; ++c ) 603 { 604 SCIP_VAR* cand; 605 SCIP_Real val; 606 SCIP_Real aggrscore; 607 SCIP_Real branchpoint; 608 SCIP_BRANCHDIR branchdir; 609 SCIP_Real valuescore; 610 611 cand = cands[c]; 612 assert(cand != NULL); 613 614 val = SCIP_UNKNOWN; 615 616 /* get domain value score for the candidate */ 617 valuescore = getValueScore(cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir); 618 619 /* evaluate the candidate against the currently best candidate w.r.t. domain value score */ 620 evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir); 621 622 SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n", 623 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand), 624 bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore); 625 626 /* get aggregated score for the candidate */ 627 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore); 628 629 /*lint -e777*/ 630 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand), 631 val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); 632 633 /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */ 634 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands); 635 } 636 } 637 else 638 { 639 int c; 640 641 bestaggrcand = cands[0]; 642 assert(cands[0] != NULL); 643 644 bestval = SCIP_UNKNOWN; 645 646 bestaggrscore = SCIPgetVarAvgInferenceScore(scip, cands[0]); 647 648 /* search for variable with best score w.r.t. average inferences per branching */ 649 for( c = 1; c < ncands; ++c ) 650 { 651 SCIP_VAR* cand; 652 SCIP_Real val; 653 SCIP_Real aggrscore; 654 655 cand = cands[c]; 656 assert(cand != NULL); 657 658 val = SCIP_UNKNOWN; 659 660 aggrscore = SCIPgetVarAvgInferenceScore(scip, cand); 661 662 /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be 663 * unreliable 664 */ 665 if( aggrscore < reliablescore ) 666 aggrscore = 0.0; 667 668 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand), 669 val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); /*lint !e777*/ 670 671 /* evaluate the candidate against the currently best candidate */ 672 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands); 673 } 674 } 675 676 /* free temporary memory */ 677 SCIPfreeBufferArray(scip, &bestcands); 678 679 assert(bestaggrcand != NULL); 680 681 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n", 682 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand), 683 bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/ 684 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight), 685 SCIPgetVarAvgInferenceScore(scip, bestaggrcand)); 686 687 if( bestbranchpoint == SCIP_UNKNOWN ) /*lint !e777*/ 688 { 689 SCIP_CALL( SCIPbranchVar(scip, bestaggrcand, &downchild, &eqchild, &upchild) ); 690 } 691 else 692 { 693 /* perform the branching */ 694 SCIP_Real estimate; 695 SCIP_Real downprio; 696 SCIP_Real upprio; 697 SCIP_Real downub; 698 SCIP_Real uplb; 699 700 assert(bestvaluecand != NULL); 701 702 downprio = 0.0; 703 upprio = 0.0; 704 705 if( bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ) 706 { 707 downprio = 1.0; 708 downub = bestbranchpoint; 709 uplb = bestbranchpoint + 1.0; 710 } 711 else 712 { 713 upprio = 1.0; 714 downub = bestbranchpoint - 1.0; 715 uplb = bestbranchpoint; 716 } 717 718 /* calculate the child estimate */ 719 estimate = SCIPcalcChildEstimate(scip, bestvaluecand, downub); 720 721 /* create down child */ 722 SCIP_CALL( SCIPcreateChild(scip, &downchild, downprio, estimate) ); 723 724 /* change upper bound in down child */ 725 SCIP_CALL( SCIPchgVarUbNode(scip, downchild, bestvaluecand, downub) ); 726 727 /* calculate the child estimate */ 728 estimate = SCIPcalcChildEstimate(scip, bestvaluecand, uplb); 729 730 /* create up child */ 731 SCIP_CALL( SCIPcreateChild(scip, &upchild, upprio, estimate) ); 732 733 /* change lower bound in up child */ 734 SCIP_CALL( SCIPchgVarLbNode(scip, upchild, bestvaluecand, uplb) ); 735 736 SCIPdebugMsg(scip, "branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint); 737 738 eqchild = NULL; 739 } 740 if( downchild != NULL || eqchild != NULL || upchild != NULL ) 741 { 742 *result = SCIP_BRANCHED; 743 } 744 else 745 { 746 /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */ 747 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand))); 748 *result = SCIP_REDUCEDDOM; 749 } 750 751 return SCIP_OKAY; 752 } 753 754 /* 755 * Callback methods 756 */ 757 758 /** copy method for branchrule plugins (called when SCIP copies plugins) */ 759 static 760 SCIP_DECL_BRANCHCOPY(branchCopyInference) 761 { /*lint --e{715}*/ 762 assert(scip != NULL); 763 assert(branchrule != NULL); 764 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 765 766 /* call inclusion method of branchrule */ 767 SCIP_CALL( SCIPincludeBranchruleInference(scip) ); 768 769 return SCIP_OKAY; 770 } 771 772 /** destructor of branching rule to free user data (called when SCIP is exiting) */ 773 static 774 SCIP_DECL_BRANCHFREE(branchFreeInference) 775 { /*lint --e{715}*/ 776 SCIP_BRANCHRULEDATA* branchruledata; 777 778 /* free branching rule data */ 779 branchruledata = SCIPbranchruleGetData(branchrule); 780 SCIPfreeBlockMemory(scip, &branchruledata); 781 SCIPbranchruleSetData(branchrule, NULL); 782 783 return SCIP_OKAY; 784 } 785 786 /** branching execution method for fractional LP solutions */ 787 static 788 SCIP_DECL_BRANCHEXECLP(branchExeclpInference) 789 { /*lint --e{715}*/ 790 SCIP_BRANCHRULEDATA* branchruledata; 791 SCIP_VAR** cands; 792 int ncands; 793 794 SCIPdebugMsg(scip, "Execlp method of inference branching\n"); 795 796 /* get branching rule data */ 797 branchruledata = SCIPbranchruleGetData(branchrule); 798 assert(branchruledata != NULL); 799 800 if( branchruledata->fractionals ) 801 { 802 /* get LP candidates (fractional integer variables) */ 803 SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, NULL, &ncands, NULL) ); 804 } 805 else 806 { 807 /* get pseudo candidates (non-fixed integer variables) */ 808 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) ); 809 } 810 811 /* perform the branching */ 812 SCIP_CALL( performBranchingNoSol(scip, cands, ncands, branchruledata->conflictweight, 813 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore, 814 branchruledata->useweightedsum, result) ); 815 816 return SCIP_OKAY; 817 } 818 819 820 /** branching execution method for external candidates */ 821 static 822 SCIP_DECL_BRANCHEXECEXT(branchExecextInference) 823 { /*lint --e{715}*/ 824 SCIP_BRANCHRULEDATA* branchruledata; 825 SCIP_VAR** cands; 826 SCIP_Real* candsols; 827 int ncands; 828 829 SCIPdebugMsg(scip, "Execext method of inference branching\n"); 830 831 /* get branching rule data */ 832 branchruledata = SCIPbranchruleGetData(branchrule); 833 assert(branchruledata != NULL); 834 835 /* get branching candidates */ 836 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) ); 837 assert(ncands > 0); 838 839 /* perform the branching */ 840 SCIP_CALL( performBranchingSol(scip, cands, candsols, ncands, branchruledata->conflictweight, 841 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore, 842 branchruledata->useweightedsum, result, branchruledata->conflictprio, branchruledata->cutoffprio) ); 843 844 return SCIP_OKAY; 845 } 846 847 /** branching execution method for not completely fixed pseudo solutions */ 848 static 849 SCIP_DECL_BRANCHEXECPS(branchExecpsInference) 850 { /*lint --e{715}*/ 851 SCIP_BRANCHRULEDATA* branchruledata; 852 SCIP_VAR** cands; 853 int ncands; 854 855 SCIPdebugMsg(scip, "Execps method of inference branching\n"); 856 857 /* get branching rule data */ 858 branchruledata = SCIPbranchruleGetData(branchrule); 859 assert(branchruledata != NULL); 860 861 /* get pseudo candidates (non-fixed integer variables) */ 862 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) ); 863 864 /* perform the branching */ 865 SCIP_CALL( performBranchingNoSol(scip, cands, ncands, branchruledata->conflictweight, 866 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore, 867 branchruledata->useweightedsum, result) ); 868 869 return SCIP_OKAY; 870 } 871 872 873 /* 874 * branching specific interface methods 875 */ 876 877 /** creates the inference history branching rule and includes it in SCIP */ 878 SCIP_RETCODE SCIPincludeBranchruleInference( 879 SCIP* scip /**< SCIP data structure */ 880 ) 881 { 882 SCIP_BRANCHRULEDATA* branchruledata; 883 SCIP_BRANCHRULE* branchrule; 884 885 /* create inference branching rule data */ 886 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) ); 887 888 /* include branching rule */ 889 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 890 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) ); 891 892 assert(branchrule != NULL); 893 894 /* set non-fundamental callbacks via specific setter functions*/ 895 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyInference) ); 896 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeInference) ); 897 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpInference) ); 898 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextInference) ); 899 SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsInference) ); 900 901 /* inference branching rule parameters */ 902 SCIP_CALL( SCIPaddRealParam(scip, 903 "branching/inference/conflictweight", 904 "weight in score calculations for conflict score", 905 &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 906 SCIP_CALL( SCIPaddRealParam(scip, 907 "branching/inference/inferenceweight", 908 "weight in score calculations for inference score", 909 &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) ); 910 SCIP_CALL( SCIPaddRealParam(scip, 911 "branching/inference/cutoffweight", 912 "weight in score calculations for cutoff score", 913 &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 914 SCIP_CALL( SCIPaddBoolParam(scip, 915 "branching/inference/fractionals", 916 "should branching on LP solution be restricted to the fractional variables?", 917 &branchruledata->fractionals, TRUE, DEFAULT_FRACTIONALS, NULL, NULL) ); 918 SCIP_CALL( SCIPaddBoolParam(scip, 919 "branching/inference/useweightedsum", 920 "should a weighted sum of inference, conflict and cutoff weights be used?", 921 &branchruledata->useweightedsum, FALSE, DEFAULT_USEWEIGHTEDSUM, NULL, NULL) ); 922 /* inference branching rule parameters */ 923 SCIP_CALL( SCIPaddRealParam(scip, 924 "branching/inference/reliablescore", 925 "weight in score calculations for conflict score", 926 &branchruledata->reliablescore, TRUE, DEFAULT_RELIABLESCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 927 /* parameters for lexicographical ordering */ 928 SCIP_CALL( SCIPaddIntParam(scip, 929 "branching/inference/conflictprio", 930 "priority value for using conflict weights in lex. order", 931 &branchruledata->conflictprio, FALSE, DEFAULT_CONFLICTPRIO, 0, INT_MAX, NULL, NULL) ); 932 SCIP_CALL( SCIPaddIntParam(scip, 933 "branching/inference/cutoffprio", 934 "priority value for using cutoff weights in lex. order", 935 &branchruledata->cutoffprio, FALSE, DEFAULT_CUTOFFPRIO, 0, INT_MAX, NULL, NULL) ); 936 937 return SCIP_OKAY; 938 } 939