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.c 26 * @ingroup OTHER_CFILES 27 * @brief methods for branching rules and branching candidate storage 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Gerald Gamrath 31 * @author Stefan Heinz 32 * @author Michael Winkler 33 * @author Stefan Vigerske 34 */ 35 36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 37 38 #include <assert.h> 39 #include <string.h> 40 41 #include "scip/def.h" 42 #include "blockmemshell/memory.h" 43 #include "scip/set.h" 44 #include "scip/stat.h" 45 #include "scip/clock.h" 46 #include "scip/paramset.h" 47 #include "scip/event.h" 48 #include "scip/lp.h" 49 #include "scip/var.h" 50 #include "scip/prob.h" 51 #include "scip/tree.h" 52 #include "scip/sepastore.h" 53 #include "scip/scip.h" 54 #include "scip/branch.h" 55 #include "scip/solve.h" 56 57 #include "scip/struct_branch.h" 58 59 /* 60 * memory growing methods for dynamically allocated arrays 61 */ 62 63 /** ensures, that lpcands array can store at least num entries */ 64 static 65 SCIP_RETCODE ensureLpcandsSize( 66 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 67 SCIP_SET* set, /**< global SCIP settings */ 68 int num /**< minimum number of entries to store */ 69 ) 70 { 71 assert(branchcand->nlpcands <= branchcand->lpcandssize); 72 73 if( num > branchcand->lpcandssize ) 74 { 75 int newsize; 76 77 newsize = SCIPsetCalcMemGrowSize(set, num); 78 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcands, newsize) ); 79 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandssol, newsize) ); 80 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandsfrac, newsize) ); 81 branchcand->lpcandssize = newsize; 82 } 83 assert(num <= branchcand->lpcandssize); 84 85 return SCIP_OKAY; 86 } 87 88 /** ensures, that pseudocands array can store at least num entries */ 89 static 90 SCIP_RETCODE ensurePseudocandsSize( 91 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 92 SCIP_SET* set, /**< global SCIP settings */ 93 int num /**< minimum number of entries to store */ 94 ) 95 { 96 assert(branchcand->npseudocands <= branchcand->pseudocandssize); 97 98 if( num > branchcand->pseudocandssize ) 99 { 100 int newsize; 101 102 newsize = SCIPsetCalcMemGrowSize(set, num); 103 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->pseudocands, newsize) ); 104 branchcand->pseudocandssize = newsize; 105 } 106 assert(num <= branchcand->pseudocandssize); 107 108 return SCIP_OKAY; 109 } 110 111 /** ensures, that externcands array can store at least num entries */ 112 static 113 SCIP_RETCODE ensureExterncandsSize( 114 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 115 SCIP_SET* set, /**< global SCIP settings */ 116 int num /**< minimum number of entries to store */ 117 ) 118 { 119 assert(branchcand->nexterncands <= branchcand->externcandssize); 120 121 if( num > branchcand->externcandssize ) 122 { 123 int newsize; 124 125 newsize = SCIPsetCalcMemGrowSize(set, num); 126 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcands, newsize) ); 127 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandsscore, newsize) ); 128 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandssol, newsize) ); 129 branchcand->externcandssize = newsize; 130 } 131 assert(num <= branchcand->externcandssize); 132 133 return SCIP_OKAY; 134 } 135 136 137 138 /* 139 * branching candidate storage methods 140 */ 141 142 /** creates a branching candidate storage */ 143 SCIP_RETCODE SCIPbranchcandCreate( 144 SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */ 145 ) 146 { 147 assert(branchcand != NULL); 148 149 SCIP_ALLOC( BMSallocMemory(branchcand) ); 150 (*branchcand)->lpcands = NULL; 151 (*branchcand)->lpcandssol = NULL; 152 (*branchcand)->lpcandsfrac = NULL; 153 (*branchcand)->externcands = NULL; 154 (*branchcand)->externcandssol = NULL; 155 (*branchcand)->externcandsscore = NULL; 156 (*branchcand)->pseudocands = NULL; 157 (*branchcand)->lpcandssize = 0; 158 (*branchcand)->nlpcands = 0; 159 (*branchcand)->nimpllpfracs = 0; 160 (*branchcand)->npriolpcands = 0; 161 (*branchcand)->npriolpbins = 0; 162 (*branchcand)->lpmaxpriority = INT_MIN; 163 (*branchcand)->externcandssize = 0; 164 (*branchcand)->nexterncands = 0; 165 (*branchcand)->nprioexterncands = 0; 166 (*branchcand)->nprioexternbins = 0; 167 (*branchcand)->nprioexternints = 0; 168 (*branchcand)->nprioexternimpls = 0; 169 (*branchcand)->externmaxpriority = INT_MIN; 170 (*branchcand)->pseudocandssize = 0; 171 (*branchcand)->npseudocands = 0; 172 (*branchcand)->npriopseudocands = 0; 173 (*branchcand)->npriopseudobins = 0; 174 (*branchcand)->npriopseudoints = 0; 175 (*branchcand)->pseudomaxpriority = INT_MIN; 176 177 SCIPbranchcandInvalidate(*branchcand); 178 179 return SCIP_OKAY; 180 } 181 182 /** frees branching candidate storage */ 183 SCIP_RETCODE SCIPbranchcandFree( 184 SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */ 185 ) 186 { 187 assert(branchcand != NULL); 188 189 BMSfreeMemoryArrayNull(&(*branchcand)->lpcands); 190 BMSfreeMemoryArrayNull(&(*branchcand)->lpcandssol); 191 BMSfreeMemoryArrayNull(&(*branchcand)->lpcandsfrac); 192 BMSfreeMemoryArrayNull(&(*branchcand)->pseudocands); 193 BMSfreeMemoryArrayNull(&(*branchcand)->externcands); 194 BMSfreeMemoryArrayNull(&(*branchcand)->externcandsscore); 195 BMSfreeMemoryArrayNull(&(*branchcand)->externcandssol); 196 BMSfreeMemory(branchcand); 197 198 return SCIP_OKAY; 199 } 200 201 /** resets branching candidates storage */ 202 void SCIPbranchcandInvalidate( 203 SCIP_BRANCHCAND* branchcand /**< pointer to store branching candidate storage */ 204 ) 205 { 206 assert(branchcand != NULL); 207 208 branchcand->validlpcandslp = -1; 209 } 210 211 /** calculates branching candidates for LP solution branching (fractional variables) */ 212 static 213 SCIP_RETCODE branchcandCalcLPCands( 214 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 215 SCIP_SET* set, /**< global SCIP settings */ 216 SCIP_STAT* stat, /**< problem statistics */ 217 SCIP_LP* lp /**< current LP data */ 218 ) 219 { 220 assert(branchcand != NULL); 221 assert(stat != NULL); 222 assert(branchcand->validlpcandslp <= stat->lpcount); 223 assert(lp != NULL); 224 assert(lp->solved); 225 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY); 226 227 SCIPsetDebugMsg(set, "calculating LP branching candidates: validlp=%" SCIP_LONGINT_FORMAT ", lpcount=%" SCIP_LONGINT_FORMAT "\n", 228 branchcand->validlpcandslp, stat->lpcount); 229 230 /* check, if the current LP branching candidate array is invalid */ 231 if( branchcand->validlpcandslp < stat->lpcount ) 232 { 233 SCIP_COL** cols; 234 SCIP_VAR* var; 235 SCIP_COL* col; 236 SCIP_Real primsol; 237 SCIP_Real frac; 238 SCIP_VARTYPE vartype; 239 int branchpriority; 240 int ncols; 241 int c; 242 int insertpos; 243 244 SCIPsetDebugMsg(set, " -> recalculating LP branching candidates\n"); 245 246 cols = SCIPlpGetCols(lp); 247 ncols = SCIPlpGetNCols(lp); 248 249 /* construct the LP branching candidate set, moving the candidates with maximal priority to the front */ 250 SCIP_CALL( ensureLpcandsSize(branchcand, set, ncols) ); 251 252 branchcand->lpmaxpriority = INT_MIN / 2; 253 branchcand->nlpcands = 0; 254 branchcand->nimpllpfracs = 0; 255 branchcand->npriolpcands = 0; 256 branchcand->npriolpbins = 0; 257 for( c = 0; c < ncols; ++c ) 258 { 259 col = cols[c]; 260 assert(col != NULL); 261 assert(col->lppos == c); 262 assert(col->lpipos >= 0); 263 264 primsol = SCIPcolGetPrimsol(col); 265 assert(primsol != SCIP_INVALID); /*lint !e777*/ 266 assert(SCIPsetIsInfinity(set, -col->lb) || SCIPsetIsFeasGE(set, primsol, col->lb)); 267 assert(SCIPsetIsInfinity(set, col->ub) || SCIPsetIsFeasLE(set, primsol, col->ub)); 268 269 /* count values at infinity as integral */ 270 if( SCIPsetIsInfinity(set, REALABS(primsol)) ) 271 continue; 272 273 var = col->var; 274 assert(var != NULL); 275 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 276 assert(SCIPvarGetCol(var) == col); 277 278 /* LP branching candidates are fractional binary and integer variables; implicit variables are kept at the end 279 * of the candidates array for some rounding heuristics 280 */ 281 vartype = SCIPvarGetType(var); 282 if( vartype == SCIP_VARTYPE_CONTINUOUS ) 283 continue; 284 285 /* ignore fixed variables (due to numerics, it is possible, that the LP solution of a fixed integer variable 286 * (with large fixed value) is fractional in terms of absolute feasibility measure) 287 */ 288 if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 ) 289 continue; 290 291 /* check, if the LP solution value is fractional */ 292 frac = SCIPsetFeasFrac(set, primsol); 293 294 /* The fractionality should not be smaller than -feastol, however, if the primsol is large enough 295 * and close to an integer, fixed precision floating point arithmetic might give us values slightly 296 * smaller than -feastol. Originally, the "frac >= -feastol"-check was within SCIPsetIsFeasFracIntegral(), 297 * however, we relaxed it to "frac >= -2*feastol" and have the stricter check here for small-enough primsols. 298 */ 299 assert(SCIPsetIsGE(set, frac, -SCIPsetFeastol(set)) || (primsol > 1e14 * SCIPsetFeastol(set))); 300 301 if( SCIPsetIsFeasFracIntegral(set, frac) ) 302 continue; 303 304 /* insert candidate in candidate list */ 305 branchpriority = SCIPvarGetBranchPriority(var); 306 insertpos = branchcand->nlpcands + branchcand->nimpllpfracs; 307 assert(insertpos < branchcand->lpcandssize); 308 309 if( vartype == SCIP_VARTYPE_IMPLINT ) 310 branchpriority = INT_MIN; 311 312 assert(vartype == SCIP_VARTYPE_IMPLINT || branchpriority >= INT_MIN/2); 313 /* ensure that implicit variables are stored at the end of the array */ 314 if( vartype != SCIP_VARTYPE_IMPLINT && branchcand->nimpllpfracs > 0 ) 315 { 316 assert(branchcand->lpcands[branchcand->nlpcands] != NULL 317 && SCIPvarGetType(branchcand->lpcands[branchcand->nlpcands]) == SCIP_VARTYPE_IMPLINT ); 318 319 branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->nlpcands]; 320 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->nlpcands]; 321 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->nlpcands]; 322 323 insertpos = branchcand->nlpcands; 324 } 325 326 if( branchpriority > branchcand->lpmaxpriority ) 327 { 328 /* candidate has higher priority than the current maximum: 329 * move it to the front and declare it to be the single best candidate 330 */ 331 if( insertpos != 0 ) 332 { 333 branchcand->lpcands[insertpos] = branchcand->lpcands[0]; 334 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[0]; 335 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[0]; 336 insertpos = 0; 337 } 338 branchcand->npriolpcands = 1; 339 branchcand->npriolpbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0); 340 branchcand->lpmaxpriority = branchpriority; 341 } 342 else if( branchpriority == branchcand->lpmaxpriority ) 343 { 344 /* candidate has equal priority as the current maximum: 345 * move away the first non-maximal priority candidate, move the current candidate to the correct 346 * slot (binaries first) and increase the number of maximal priority candidates 347 */ 348 if( insertpos != branchcand->npriolpcands ) 349 { 350 branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpcands]; 351 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpcands]; 352 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpcands]; 353 insertpos = branchcand->npriolpcands; 354 } 355 branchcand->npriolpcands++; 356 if( vartype == SCIP_VARTYPE_BINARY ) 357 { 358 if( insertpos != branchcand->npriolpbins ) 359 { 360 branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpbins]; 361 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpbins]; 362 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpbins]; 363 insertpos = branchcand->npriolpbins; 364 } 365 branchcand->npriolpbins++; 366 } 367 } 368 /* insert variable at the correct position of the candidates storage */ 369 branchcand->lpcands[insertpos] = var; 370 branchcand->lpcandssol[insertpos] = primsol; 371 branchcand->lpcandsfrac[insertpos] = frac; 372 373 /* increase the counter depending on the variable type */ 374 if( vartype != SCIP_VARTYPE_IMPLINT ) 375 branchcand->nlpcands++; 376 else 377 branchcand->nimpllpfracs++; 378 379 SCIPsetDebugMsg(set, " -> candidate %d: var=<%s>, sol=%g, frac=%g, prio=%d (max: %d) -> pos %d\n", 380 branchcand->nlpcands, SCIPvarGetName(var), primsol, frac, branchpriority, branchcand->lpmaxpriority, 381 insertpos); 382 } 383 384 #ifndef NDEBUG 385 /* in debug mode we assert that the variables are positioned correctly (binaries and integers first, 386 * implicit integers last) 387 */ 388 for( c = 0; c < branchcand->nlpcands + branchcand->nimpllpfracs; ++c ) 389 { 390 assert(c >= branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) != SCIP_VARTYPE_IMPLINT); 391 assert(c < branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) == SCIP_VARTYPE_IMPLINT); 392 } 393 #endif 394 395 branchcand->validlpcandslp = stat->lpcount; 396 } 397 assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands); 398 399 SCIPsetDebugMsg(set, " -> %d fractional variables (%d of maximal priority)\n", branchcand->nlpcands, branchcand->npriolpcands); 400 401 return SCIP_OKAY; 402 } 403 404 /** gets branching candidates for LP solution branching (fractional variables) */ 405 SCIP_RETCODE SCIPbranchcandGetLPCands( 406 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 407 SCIP_SET* set, /**< global SCIP settings */ 408 SCIP_STAT* stat, /**< problem statistics */ 409 SCIP_LP* lp, /**< current LP data */ 410 SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */ 411 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */ 412 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */ 413 int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */ 414 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */ 415 int* nfracimplvars /**< pointer to store the number of implicit fractional variables, or NULL */ 416 ) 417 { 418 /* calculate branching candidates */ 419 SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) ); 420 421 /* assign return values */ 422 if( lpcands != NULL ) 423 *lpcands = branchcand->lpcands; 424 if( lpcandssol != NULL ) 425 *lpcandssol = branchcand->lpcandssol; 426 if( lpcandsfrac != NULL ) 427 *lpcandsfrac = branchcand->lpcandsfrac; 428 if( nlpcands != NULL ) 429 *nlpcands = branchcand->nlpcands; 430 if( npriolpcands != NULL ) 431 *npriolpcands = (set->branch_preferbinary && branchcand->npriolpbins > 0 ? branchcand->npriolpbins 432 : branchcand->npriolpcands); 433 if( nfracimplvars != NULL ) 434 *nfracimplvars = branchcand->nimpllpfracs; 435 436 return SCIP_OKAY; 437 } 438 439 /** gets external branching candidates */ 440 SCIP_RETCODE SCIPbranchcandGetExternCands( 441 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 442 SCIP_VAR*** externcands, /**< pointer to store the array of external branching candidates, or NULL */ 443 SCIP_Real** externcandssol, /**< pointer to store the array of external candidate solution values, or NULL */ 444 SCIP_Real** externcandsscore, /**< pointer to store the array of external candidate scores, or NULL */ 445 int* nexterncands, /**< pointer to store the number of external branching candidates, or NULL */ 446 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */ 447 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */ 448 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */ 449 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority, 450 * or NULL */ 451 ) 452 { 453 assert(branchcand != NULL); 454 455 /* assign return values */ 456 if( externcands != NULL ) 457 *externcands = branchcand->externcands; 458 if( externcandssol != NULL ) 459 *externcandssol = branchcand->externcandssol; 460 if( externcandsscore != NULL ) 461 *externcandsscore = branchcand->externcandsscore; 462 if( nexterncands != NULL ) 463 *nexterncands = branchcand->nexterncands; 464 if( nprioexterncands != NULL ) 465 *nprioexterncands = branchcand->nprioexterncands; 466 if( nprioexternbins != NULL ) 467 *nprioexternbins = branchcand->nprioexternbins; 468 if( nprioexternints != NULL ) 469 *nprioexternints = branchcand->nprioexternints; 470 if( nprioexternimpls != NULL ) 471 *nprioexternimpls = branchcand->nprioexternimpls; 472 473 return SCIP_OKAY; 474 } 475 476 /** gets maximal branching priority of LP branching candidates */ 477 int SCIPbranchcandGetLPMaxPrio( 478 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 479 ) 480 { 481 assert(branchcand != NULL); 482 483 return branchcand->lpmaxpriority; 484 } 485 486 /** gets number of LP branching candidates with maximal branch priority */ 487 int SCIPbranchcandGetNPrioLPCands( 488 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 489 ) 490 { 491 assert(branchcand != NULL); 492 493 return branchcand->npriolpcands; 494 } 495 496 /** gets maximal branching priority of external branching candidates */ 497 int SCIPbranchcandGetExternMaxPrio( 498 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 499 ) 500 { 501 assert(branchcand != NULL); 502 503 return branchcand->externmaxpriority; 504 } 505 506 /** gets number of external branching candidates */ 507 int SCIPbranchcandGetNExternCands( 508 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 509 ) 510 { 511 assert(branchcand != NULL); 512 513 return branchcand->nexterncands; 514 } 515 516 /** gets number of external branching candidates with maximal branch priority */ 517 int SCIPbranchcandGetNPrioExternCands( 518 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 519 ) 520 { 521 assert(branchcand != NULL); 522 523 return branchcand->nprioexterncands; 524 } 525 526 /** gets number of binary external branching candidates with maximal branch priority */ 527 int SCIPbranchcandGetNPrioExternBins( 528 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 529 ) 530 { 531 assert(branchcand != NULL); 532 533 return branchcand->nprioexternbins; 534 } 535 536 /** gets number of integer external branching candidates with maximal branch priority */ 537 int SCIPbranchcandGetNPrioExternInts( 538 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 539 ) 540 { 541 assert(branchcand != NULL); 542 543 return branchcand->nprioexternints; 544 } 545 546 /** gets number of implicit integer external branching candidates with maximal branch priority */ 547 int SCIPbranchcandGetNPrioExternImpls( 548 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 549 ) 550 { 551 assert(branchcand != NULL); 552 553 return branchcand->nprioexternimpls; 554 } 555 556 /** gets number of continuous external branching candidates with maximal branch priority */ 557 int SCIPbranchcandGetNPrioExternConts( 558 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 559 ) 560 { 561 assert(branchcand != NULL); 562 563 return branchcand->nprioexterncands - branchcand->nprioexternbins - branchcand->nprioexternints - branchcand->nprioexternimpls; 564 } 565 566 /** insert variable, its score and its solution value into the external branching candidate storage 567 * the absolute difference of the current lower and upper bounds of the variable must be at least epsilon 568 */ 569 SCIP_RETCODE SCIPbranchcandAddExternCand( 570 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 571 SCIP_SET* set, /**< global SCIP settings */ 572 SCIP_VAR* var, /**< variable to insert */ 573 SCIP_Real score, /**< score of external candidate, e.g. infeasibility */ 574 SCIP_Real solval /**< value of the variable in the current solution */ 575 ) 576 { 577 SCIP_VARTYPE vartype; 578 int branchpriority; 579 int insertpos; 580 581 assert(branchcand != NULL); 582 assert(var != NULL); 583 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); /* the variable should not be fixed yet */ 584 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || !SCIPsetIsEQ(set, SCIPsetCeil(set, SCIPvarGetLbLocal(var)), SCIPsetFloor(set, SCIPvarGetUbLocal(var)))); /* a discrete variable should also not be fixed, even after rounding bounds to integral values */ 585 assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR || !SCIPsetIsEQ(set, SCIPvarGetMultaggrLbLocal(var, set), SCIPvarGetMultaggrUbLocal(var, set))); /* also the current bounds of a multi-aggregated variable should not be fixed yet */ 586 assert(branchcand->nprioexterncands <= branchcand->nexterncands); 587 assert(branchcand->nexterncands <= branchcand->externcandssize); 588 589 vartype = SCIPvarGetType(var); 590 branchpriority = SCIPvarGetBranchPriority(var); 591 insertpos = branchcand->nexterncands; 592 593 SCIP_CALL( ensureExterncandsSize(branchcand, set, branchcand->nexterncands+1) ); 594 595 SCIPsetDebugMsg(set, "inserting external candidate <%s> of type %d and priority %d into candidate set (maxprio: %d), score = %g, solval = %g\n", 596 SCIPvarGetName(var), vartype, branchpriority, branchcand->externmaxpriority, score, solval); 597 598 /* insert the variable into externcands, making sure, that the highest priority candidates are at the front 599 * and ordered binaries, integers, implicit integers, continuous 600 */ 601 if( branchpriority > branchcand->externmaxpriority ) 602 { 603 /* candidate has higher priority than the current maximum: 604 * move it to the front and declare it to be the single best candidate 605 */ 606 branchcand->externcands[insertpos] = branchcand->externcands[0]; 607 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[0]; 608 branchcand->externcandssol[insertpos] = branchcand->externcandssol[0]; 609 610 insertpos = 0; 611 612 branchcand->nprioexterncands = 1; 613 branchcand->nprioexternbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0); 614 branchcand->nprioexternints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0); 615 branchcand->nprioexternimpls = (vartype == SCIP_VARTYPE_IMPLINT ? 1 : 0); 616 branchcand->externmaxpriority = branchpriority; 617 } 618 else if( branchpriority == branchcand->externmaxpriority ) 619 { 620 /* candidate has equal priority as the current maximum: 621 * move away the first non-maximal priority candidate, move the current candidate to the correct 622 * slot (binaries first, integers next, implicit integers next, continuous last) and increase the number 623 * of maximal priority candidates 624 */ 625 if( insertpos != branchcand->nprioexterncands ) 626 { 627 branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexterncands]; 628 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexterncands]; 629 branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexterncands]; 630 631 insertpos = branchcand->nprioexterncands; 632 } 633 branchcand->nprioexterncands++; 634 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER || vartype == SCIP_VARTYPE_IMPLINT ) 635 { 636 if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls ) 637 { 638 branchcand->externcands[insertpos] = 639 branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls]; 640 branchcand->externcandsscore[insertpos] = 641 branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls]; 642 branchcand->externcandssol[insertpos] = 643 branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls]; 644 645 insertpos = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls; 646 } 647 branchcand->nprioexternimpls++; 648 649 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER ) 650 { 651 if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints ) 652 { 653 branchcand->externcands[insertpos] = 654 branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints]; 655 branchcand->externcandsscore[insertpos] = 656 branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints]; 657 branchcand->externcandssol[insertpos] = 658 branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints]; 659 660 insertpos = branchcand->nprioexternbins + branchcand->nprioexternints; 661 } 662 branchcand->nprioexternints++; 663 branchcand->nprioexternimpls--; 664 665 if( vartype == SCIP_VARTYPE_BINARY ) 666 { 667 if( insertpos != branchcand->nprioexternbins ) 668 { 669 branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexternbins]; 670 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexternbins]; 671 branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexternbins]; 672 673 insertpos = branchcand->nprioexternbins; 674 } 675 branchcand->nprioexternbins++; 676 branchcand->nprioexternints--; 677 } 678 } 679 } 680 } 681 branchcand->externcands[insertpos] = var; 682 branchcand->externcandsscore[insertpos] = score; 683 branchcand->externcandssol[insertpos] = solval; 684 branchcand->nexterncands++; 685 686 SCIPsetDebugMsg(set, " -> inserted at position %d (nprioexterncands=%d)\n", insertpos, branchcand->nprioexterncands); 687 688 assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands); 689 assert(0 <= branchcand->nprioexternbins && branchcand->nprioexternbins <= branchcand->nprioexterncands); 690 assert(0 <= branchcand->nprioexternints && branchcand->nprioexternints <= branchcand->nprioexterncands); 691 assert(0 <= branchcand->nprioexternimpls && branchcand->nprioexternimpls <= branchcand->nprioexterncands); 692 693 return SCIP_OKAY; 694 } 695 696 /** removes all external candidates from the storage for external branching */ 697 void SCIPbranchcandClearExternCands( 698 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 699 ) 700 { 701 assert(branchcand != NULL); 702 703 branchcand->nexterncands = 0; 704 branchcand->nprioexterncands = 0; 705 branchcand->nprioexternbins = 0; 706 branchcand->nprioexternints = 0; 707 branchcand->nprioexternimpls = 0; 708 branchcand->externmaxpriority = INT_MIN; 709 } 710 711 /** checks whether the given variable is contained in the candidate storage for external branching */ 712 SCIP_Bool SCIPbranchcandContainsExternCand( 713 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 714 SCIP_VAR* var /**< variable to look for */ 715 ) 716 { 717 int branchpriority; 718 int i; 719 720 assert(branchcand != NULL); 721 assert(var != NULL); 722 assert(branchcand->nprioexterncands <= branchcand->nexterncands); 723 assert(branchcand->nexterncands <= branchcand->externcandssize); 724 725 branchpriority = SCIPvarGetBranchPriority(var); 726 727 /* look for the variable in the externcands, using the fact, that the highest priority candidates are at the front 728 * and ordered binaries, integers, implicit integers, continuous 729 */ 730 if( branchpriority > branchcand->externmaxpriority ) 731 { 732 /* the branching priority of the variable is higher than the maximal priority contained in the array; 733 * the variable can thus not be contained */ 734 return FALSE; 735 } 736 if( branchpriority == branchcand->externmaxpriority ) 737 { 738 SCIP_VARTYPE vartype; 739 740 vartype = SCIPvarGetType(var); 741 742 /* variable has equal priority as the current maximum: 743 * look for it in the correct slot (binaries first, integers next, implicit integers next, continuous last) 744 */ 745 if( vartype == SCIP_VARTYPE_BINARY ) 746 { 747 /* the variable is binary, look at the first branchcand->nprioexternbins slots */ 748 for( i = 0; i < branchcand->nprioexternbins; i++ ) 749 if( branchcand->externcands[i] == var ) 750 return TRUE; 751 return FALSE; 752 } 753 if( vartype == SCIP_VARTYPE_INTEGER ) 754 { 755 /* the variable is integer, look at the slots containing integers */ 756 for( i = 0; i < branchcand->nprioexternints; i++ ) 757 if( branchcand->externcands[branchcand->nprioexternbins + i] == var ) 758 return TRUE; 759 return FALSE; 760 } 761 if( vartype == SCIP_VARTYPE_IMPLINT ) 762 { 763 /* the variable is implicit integer, look at the slots containing implicit integers */ 764 for( i = 0; i < branchcand->nprioexternimpls; i++ ) 765 if( branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + i] == var ) 766 return TRUE; 767 return FALSE; 768 } 769 /* the variable is continuous, look at the slots containing continuous variables */ 770 assert(vartype == SCIP_VARTYPE_CONTINUOUS); 771 for( i = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls; 772 i < branchcand->nprioexterncands; i++ ) 773 if( branchcand->externcands[i] == var ) 774 return TRUE; 775 return FALSE; 776 } 777 /* the branching priority of the variable is lower than the maximal priority contained in the array; 778 * look for the variable in the candidates which do not have maximal priority */ 779 assert(branchpriority < branchcand->externmaxpriority); 780 781 for( i = branchcand->nprioexterncands; i < branchcand->nexterncands; i++ ) 782 if( branchcand->externcands[i] == var ) 783 return TRUE; 784 return FALSE; 785 } 786 787 /** gets branching candidates for pseudo solution branching (non-fixed variables) */ 788 SCIP_RETCODE SCIPbranchcandGetPseudoCands( 789 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 790 SCIP_SET* set, /**< global SCIP settings */ 791 SCIP_PROB* prob, /**< problem data */ 792 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */ 793 int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */ 794 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */ 795 ) 796 { 797 assert(branchcand != NULL); 798 799 #ifndef NDEBUG 800 /* check, if the current pseudo branching candidate array is correct */ 801 { 802 SCIP_VAR* var; 803 int npcs; 804 int v; 805 806 assert(prob != NULL); 807 808 /* pseudo branching candidates are non-fixed binary, integer, and implicit integer variables */ 809 npcs = 0; 810 for( v = 0; v < prob->nbinvars + prob->nintvars + prob->nimplvars; ++v ) 811 { 812 var = prob->vars[v]; 813 assert(var != NULL); 814 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN); 815 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY 816 || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER 817 || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT); 818 assert(SCIPsetIsFeasIntegral(set, SCIPvarGetLbLocal(var))); 819 assert(SCIPsetIsFeasIntegral(set, SCIPvarGetUbLocal(var))); 820 assert(SCIPsetIsLE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); 821 822 if( SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 823 { 824 assert(0 <= var->pseudocandindex && var->pseudocandindex < branchcand->npseudocands); 825 assert(branchcand->pseudocands[var->pseudocandindex] == var); 826 npcs++; 827 } 828 else 829 { 830 assert(var->pseudocandindex == -1); 831 } 832 } 833 assert(branchcand->npseudocands == npcs); 834 for (v = 0; v < branchcand->npriopseudocands; ++v) 835 assert( branchcand->pseudocands[v]->branchpriority == branchcand->pseudomaxpriority ); 836 } 837 #endif 838 839 /* assign return values */ 840 if( pseudocands != NULL ) 841 *pseudocands = branchcand->pseudocands; 842 if( npseudocands != NULL ) 843 *npseudocands = branchcand->npseudocands; 844 if( npriopseudocands != NULL ) 845 *npriopseudocands = (set->branch_preferbinary && branchcand->npriopseudobins > 0 ? branchcand->npriopseudobins 846 : branchcand->npriopseudocands); 847 848 return SCIP_OKAY; 849 } 850 851 /** gets number of branching candidates for pseudo solution branching (non-fixed variables) */ 852 int SCIPbranchcandGetNPseudoCands( 853 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 854 ) 855 { 856 assert(branchcand != NULL); 857 858 return branchcand->npseudocands; 859 } 860 861 /** gets number of branching candidates with maximal branch priority for pseudo solution branching */ 862 int SCIPbranchcandGetNPrioPseudoCands( 863 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 864 ) 865 { 866 assert(branchcand != NULL); 867 868 return branchcand->npriopseudocands; 869 } 870 871 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching */ 872 int SCIPbranchcandGetNPrioPseudoBins( 873 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 874 ) 875 { 876 assert(branchcand != NULL); 877 878 return branchcand->npriopseudobins; 879 } 880 881 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching */ 882 int SCIPbranchcandGetNPrioPseudoInts( 883 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 884 ) 885 { 886 assert(branchcand != NULL); 887 888 return branchcand->npriopseudoints; 889 } 890 891 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching */ 892 int SCIPbranchcandGetNPrioPseudoImpls( 893 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 894 ) 895 { 896 assert(branchcand != NULL); 897 898 return branchcand->npriopseudocands - branchcand->npriopseudobins - branchcand->npriopseudoints; 899 } 900 901 /** insert pseudocand at given position, or to the first positions of the maximal priority candidates, using the 902 * given position as free slot for the other candidates 903 */ 904 static 905 void branchcandInsertPseudoCand( 906 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 907 SCIP_VAR* var, /**< variable to insert */ 908 int insertpos /**< free position to insert the variable */ 909 ) 910 { 911 SCIP_VARTYPE vartype; 912 int branchpriority; 913 914 assert(branchcand != NULL); 915 assert(var != NULL); 916 assert(branchcand->npriopseudocands <= insertpos && insertpos < branchcand->npseudocands); 917 assert(branchcand->npseudocands <= branchcand->pseudocandssize); 918 919 vartype = SCIPvarGetType(var); 920 branchpriority = SCIPvarGetBranchPriority(var); 921 922 SCIPdebugMessage("inserting pseudo candidate <%s> of type %d and priority %d into candidate set at position %d (maxprio: %d)\n", 923 SCIPvarGetName(var), vartype, branchpriority, insertpos, branchcand->pseudomaxpriority); 924 925 /* insert the variable into pseudocands, making sure, that the highest priority candidates are at the front 926 * and ordered binaries, integers, implicit integers 927 */ 928 if( branchpriority > branchcand->pseudomaxpriority ) 929 { 930 /* candidate has higher priority than the current maximum: 931 * move it to the front and declare it to be the single best candidate 932 */ 933 if( insertpos != 0 ) 934 { 935 branchcand->pseudocands[insertpos] = branchcand->pseudocands[0]; 936 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos; 937 insertpos = 0; 938 } 939 branchcand->npriopseudocands = 1; 940 branchcand->npriopseudobins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0); 941 branchcand->npriopseudoints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0); 942 branchcand->pseudomaxpriority = branchpriority; 943 } 944 else if( branchpriority == branchcand->pseudomaxpriority ) 945 { 946 /* candidate has equal priority as the current maximum: 947 * move away the first non-maximal priority candidate, move the current candidate to the correct 948 * slot (binaries first, integers next, implicit integers last) and increase the number of maximal priority candidates 949 */ 950 if( insertpos != branchcand->npriopseudocands ) 951 { 952 branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudocands]; 953 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos; 954 insertpos = branchcand->npriopseudocands; 955 } 956 branchcand->npriopseudocands++; 957 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER ) 958 { 959 if( insertpos != branchcand->npriopseudobins + branchcand->npriopseudoints ) 960 { 961 branchcand->pseudocands[insertpos] = 962 branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints]; 963 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos; 964 insertpos = branchcand->npriopseudobins + branchcand->npriopseudoints; 965 } 966 branchcand->npriopseudoints++; 967 968 if( vartype == SCIP_VARTYPE_BINARY ) 969 { 970 if( insertpos != branchcand->npriopseudobins ) 971 { 972 branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudobins]; 973 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos; 974 insertpos = branchcand->npriopseudobins; 975 } 976 branchcand->npriopseudobins++; 977 branchcand->npriopseudoints--; 978 } 979 } 980 } 981 branchcand->pseudocands[insertpos] = var; 982 var->pseudocandindex = insertpos; 983 984 SCIPdebugMessage(" -> inserted at position %d (npriopseudocands=%d)\n", insertpos, branchcand->npriopseudocands); 985 986 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands); 987 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands); 988 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands); 989 } 990 991 /** sorts the pseudo branching candidates, such that the candidates of maximal priority are at the front, 992 * ordered by binaries, integers, implicit integers 993 */ 994 static 995 void branchcandSortPseudoCands( 996 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */ 997 ) 998 { 999 SCIP_VAR* var; 1000 int i; 1001 1002 assert(branchcand != NULL); 1003 assert(branchcand->npriopseudocands == 0); /* is only be called after removal of last maximal candidate */ 1004 assert(branchcand->npriopseudobins == 0); 1005 assert(branchcand->npriopseudoints == 0); 1006 1007 SCIPdebugMessage("resorting pseudo candidates\n"); 1008 1009 branchcand->pseudomaxpriority = INT_MIN; 1010 1011 for( i = 0; i < branchcand->npseudocands; ++i ) 1012 { 1013 var = branchcand->pseudocands[i]; 1014 assert(var->pseudocandindex == i); 1015 1016 if( SCIPvarGetBranchPriority(var) >= branchcand->pseudomaxpriority ) 1017 branchcandInsertPseudoCand(branchcand, var, i); 1018 } 1019 1020 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands); 1021 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands); 1022 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands); 1023 #ifndef NDEBUG 1024 { 1025 for (i = 0; i < branchcand->npriopseudocands; ++i) 1026 assert( branchcand->pseudocands[i]->branchpriority == branchcand->pseudomaxpriority ); 1027 } 1028 #endif 1029 } 1030 1031 /** removes pseudo candidate from pseudocands array 1032 */ 1033 static 1034 void branchcandRemovePseudoCand( 1035 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1036 SCIP_VAR* var /**< variable to remove */ 1037 ) 1038 { 1039 int freepos; 1040 1041 assert(branchcand != NULL); 1042 assert(var != NULL); 1043 assert(var->pseudocandindex < branchcand->npseudocands); 1044 assert(branchcand->pseudocands[var->pseudocandindex] == var); 1045 assert(branchcand->pseudocands[branchcand->npseudocands-1] != NULL); 1046 1047 /* Note that the branching priority of the variable to be removed is not necessarily equal to pseudomaxpriority, since 1048 * the status of the variable might have changed, leading to a change in the branching priority. Moreover, if the 1049 * variable was part of an aggregation, even other variables might at this point have different priorities. */ 1050 SCIPdebugMessage("removing pseudo candidate <%s> of type %d and priority %d at %d from candidate set (maxprio: %d)\n", 1051 SCIPvarGetName(var), SCIPvarGetType(var), SCIPvarGetBranchPriority(var), var->pseudocandindex, 1052 branchcand->pseudomaxpriority); 1053 1054 /* delete the variable from pseudocands, making sure, that the highest priority candidates are at the front 1055 * and ordered binaries, integers, implicit integers 1056 */ 1057 freepos = var->pseudocandindex; 1058 var->pseudocandindex = -1; 1059 assert(0 <= freepos && freepos < branchcand->npseudocands); 1060 1061 if( freepos < branchcand->npriopseudobins ) 1062 { 1063 /* a binary candidate of maximal priority was removed */ 1064 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY); 1065 if( freepos != branchcand->npriopseudobins - 1 ) 1066 { 1067 branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudobins - 1]; 1068 branchcand->pseudocands[freepos]->pseudocandindex = freepos; 1069 freepos = branchcand->npriopseudobins - 1; 1070 } 1071 branchcand->npriopseudobins--; 1072 branchcand->npriopseudoints++; 1073 } 1074 1075 if( freepos < branchcand->npriopseudobins + branchcand->npriopseudoints ) 1076 { 1077 /* a binary or integer candidate of maximal priority was removed */ 1078 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER); 1079 if( freepos != branchcand->npriopseudobins + branchcand->npriopseudoints - 1 ) 1080 { 1081 branchcand->pseudocands[freepos] = 1082 branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints - 1]; 1083 branchcand->pseudocands[freepos]->pseudocandindex = freepos; 1084 freepos = branchcand->npriopseudobins + branchcand->npriopseudoints - 1; 1085 } 1086 branchcand->npriopseudoints--; 1087 } 1088 1089 if( freepos < branchcand->npriopseudocands ) 1090 { 1091 /* a candidate of maximal priority was removed */ 1092 if( freepos != branchcand->npriopseudocands - 1 ) 1093 { 1094 branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudocands - 1]; 1095 branchcand->pseudocands[freepos]->pseudocandindex = freepos; 1096 freepos = branchcand->npriopseudocands - 1; 1097 } 1098 branchcand->npriopseudocands--; 1099 } 1100 if( freepos != branchcand->npseudocands - 1 ) 1101 { 1102 branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npseudocands - 1]; 1103 branchcand->pseudocands[freepos]->pseudocandindex = freepos; 1104 } 1105 branchcand->npseudocands--; 1106 1107 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands); 1108 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands); 1109 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands); 1110 1111 /* if all maximal priority candidates were removed, resort the array s.t. the new maximal priority candidates 1112 * are at the front 1113 */ 1114 if( branchcand->npriopseudocands == 0 ) 1115 branchcandSortPseudoCands(branchcand); 1116 } 1117 1118 /** removes variable from branching candidate list */ 1119 SCIP_RETCODE SCIPbranchcandRemoveVar( 1120 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1121 SCIP_VAR* var /**< variable that changed its bounds */ 1122 ) 1123 { 1124 assert(var != NULL); 1125 1126 /* make sure, variable is not member of the pseudo branching candidate list */ 1127 if( var->pseudocandindex >= 0 ) 1128 { 1129 branchcandRemovePseudoCand(branchcand, var); 1130 } 1131 1132 return SCIP_OKAY; 1133 } 1134 1135 /** updates branching candidate list for a given variable */ 1136 SCIP_RETCODE SCIPbranchcandUpdateVar( 1137 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1138 SCIP_SET* set, /**< global SCIP settings */ 1139 SCIP_VAR* var /**< variable that changed its bounds */ 1140 ) 1141 { 1142 assert(branchcand != NULL); 1143 assert(var != NULL); 1144 1145 if( (SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN) 1146 && SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS 1147 && SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 1148 { 1149 /* variable is neither continuous nor fixed and has non-empty domain: make sure it is member of the pseudo branching candidate list */ 1150 if( var->pseudocandindex == -1 ) 1151 { 1152 SCIP_CALL( ensurePseudocandsSize(branchcand, set, branchcand->npseudocands+1) ); 1153 1154 branchcand->npseudocands++; 1155 branchcandInsertPseudoCand(branchcand, var, branchcand->npseudocands-1); 1156 } 1157 } 1158 else 1159 { 1160 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL 1161 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED 1162 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED 1163 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR 1164 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED 1165 || SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS 1166 || SCIPsetIsGE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); 1167 1168 /* variable is continuous or fixed or has empty domain: make sure it is not member of the pseudo branching candidate list */ 1169 SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) ); 1170 } 1171 1172 return SCIP_OKAY; 1173 } 1174 1175 /** updates branching priority of the given variable and update the pseudo candidate array if needed */ 1176 SCIP_RETCODE SCIPbranchcandUpdateVarBranchPriority( 1177 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 1178 SCIP_SET* set, /**< global SCIP settings */ 1179 SCIP_VAR* var, /**< variable that changed its bounds */ 1180 int branchpriority /**< branch priority of the variable */ 1181 ) 1182 { 1183 int oldbranchpriority; 1184 int pseudomaxpriority; 1185 1186 assert(branchcand != NULL); 1187 1188 oldbranchpriority = SCIPvarGetBranchPriority(var); 1189 1190 if( oldbranchpriority == branchpriority ) 1191 return SCIP_OKAY; 1192 1193 pseudomaxpriority = branchcand->pseudomaxpriority; 1194 1195 /* if the variable currently belongs to the priority set or the new branching priority is larger than the current one, 1196 * remove it from the pseudo branch candidate array */ 1197 if( oldbranchpriority == pseudomaxpriority || branchpriority > pseudomaxpriority ) 1198 { 1199 SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) ); 1200 assert(var->pseudocandindex == -1); 1201 } 1202 1203 /* change the branching priority of the variable */ 1204 SCIP_CALL( SCIPvarChgBranchPriority(var, branchpriority) ); 1205 1206 /* if the variable is not part of the pseudo branching candidate array, check if it is a pseudo branching candidate 1207 * and add it if so */ 1208 SCIP_CALL( SCIPbranchcandUpdateVar(branchcand, set, var) ); 1209 1210 return SCIP_OKAY; 1211 } 1212 1213 1214 1215 /* 1216 * branching rule methods 1217 */ 1218 1219 /** compares two branching rules w. r. to their priority */ 1220 SCIP_DECL_SORTPTRCOMP(SCIPbranchruleComp) 1221 { /*lint --e{715}*/ 1222 return ((SCIP_BRANCHRULE*)elem2)->priority - ((SCIP_BRANCHRULE*)elem1)->priority; 1223 } 1224 1225 /** comparison method for sorting branching rules w.r.t. to their name */ 1226 SCIP_DECL_SORTPTRCOMP(SCIPbranchruleCompName) 1227 { 1228 return strcmp(SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem1), SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem2)); 1229 } 1230 1231 /** method to call, when the priority of a branching rule was changed */ 1232 static 1233 SCIP_DECL_PARAMCHGD(paramChgdBranchrulePriority) 1234 { /*lint --e{715}*/ 1235 SCIP_PARAMDATA* paramdata; 1236 1237 paramdata = SCIPparamGetData(param); 1238 assert(paramdata != NULL); 1239 1240 /* use SCIPsetBranchrulePriority() to mark the branchrules unsorted */ 1241 SCIP_CALL( SCIPsetBranchrulePriority(scip, (SCIP_BRANCHRULE*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/ 1242 1243 return SCIP_OKAY; 1244 } 1245 1246 /** copies the given branchrule to a new scip */ 1247 SCIP_RETCODE SCIPbranchruleCopyInclude( 1248 SCIP_BRANCHRULE* branchrule, /**< branchrule */ 1249 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */ 1250 ) 1251 { 1252 assert(branchrule != NULL); 1253 assert(set != NULL); 1254 assert(set->scip != NULL); 1255 1256 if( branchrule->branchcopy != NULL ) 1257 { 1258 SCIPsetDebugMsg(set, "including branching rule %s in subscip %p\n", SCIPbranchruleGetName(branchrule), (void*)set->scip); 1259 SCIP_CALL( branchrule->branchcopy(set->scip, branchrule) ); 1260 } 1261 1262 return SCIP_OKAY; 1263 } 1264 1265 /** internal method for creating a branching rule */ 1266 static 1267 SCIP_RETCODE doBranchruleCreate( 1268 SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */ 1269 SCIP_SET* set, /**< global SCIP settings */ 1270 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1271 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 1272 const char* name, /**< name of branching rule */ 1273 const char* desc, /**< description of branching rule */ 1274 int priority, /**< priority of the branching rule */ 1275 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */ 1276 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound 1277 * compared to best node's dual bound for applying branching rule 1278 * (0.0: only on current best node, 1.0: on all nodes) */ 1279 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */ 1280 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */ 1281 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */ 1282 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */ 1283 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */ 1284 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */ 1285 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */ 1286 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */ 1287 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */ 1288 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 1289 ) 1290 { 1291 char paramname[SCIP_MAXSTRLEN]; 1292 char paramdesc[SCIP_MAXSTRLEN]; 1293 1294 assert(branchrule != NULL); 1295 assert(name != NULL); 1296 assert(desc != NULL); 1297 1298 SCIP_ALLOC( BMSallocMemory(branchrule) ); 1299 BMSclearMemory(*branchrule); 1300 1301 SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->name, name, strlen(name)+1) ); 1302 SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->desc, desc, strlen(desc)+1) ); 1303 (*branchrule)->priority = priority; 1304 (*branchrule)->maxdepth = maxdepth; 1305 (*branchrule)->maxbounddist = maxbounddist; 1306 (*branchrule)->branchcopy = branchcopy; 1307 (*branchrule)->branchfree = branchfree; 1308 (*branchrule)->branchinit = branchinit; 1309 (*branchrule)->branchexit = branchexit; 1310 (*branchrule)->branchinitsol = branchinitsol; 1311 (*branchrule)->branchexitsol = branchexitsol; 1312 (*branchrule)->branchexeclp = branchexeclp; 1313 (*branchrule)->branchexecext = branchexecext; 1314 (*branchrule)->branchexecps = branchexecps; 1315 (*branchrule)->branchruledata = branchruledata; 1316 SCIP_CALL( SCIPclockCreate(&(*branchrule)->setuptime, SCIP_CLOCKTYPE_DEFAULT) ); 1317 SCIP_CALL( SCIPclockCreate(&(*branchrule)->branchclock, SCIP_CLOCKTYPE_DEFAULT) ); 1318 (*branchrule)->nlpcalls = 0; 1319 (*branchrule)->nexterncalls = 0; 1320 (*branchrule)->npseudocalls = 0; 1321 (*branchrule)->ncutoffs = 0; 1322 (*branchrule)->ncutsfound = 0; 1323 (*branchrule)->nconssfound = 0; 1324 (*branchrule)->ndomredsfound = 0; 1325 (*branchrule)->nchildren = 0; 1326 (*branchrule)->initialized = FALSE; 1327 1328 /* add parameters */ 1329 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/priority", name); 1330 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of branching rule <%s>", name); 1331 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 1332 &(*branchrule)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4, 1333 paramChgdBranchrulePriority, (SCIP_PARAMDATA*)(*branchrule)) ); /*lint !e740*/ 1334 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxdepth", name); 1335 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level, up to which branching rule <%s> should be used (-1 for no limit)", name); 1336 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc, 1337 &(*branchrule)->maxdepth, FALSE, maxdepth, -1, SCIP_MAXTREEDEPTH, 1338 NULL, NULL) ); /*lint !e740*/ 1339 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxbounddist", name); 1340 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching rule (0.0: only on current best node, 1.0: on all nodes)"); 1341 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, paramdesc, 1342 &(*branchrule)->maxbounddist, FALSE, maxbounddist, 0.0, 1.0, 1343 NULL, NULL) ); /*lint !e740*/ 1344 1345 return SCIP_OKAY; 1346 } 1347 1348 /** creates a branching rule */ 1349 SCIP_RETCODE SCIPbranchruleCreate( 1350 SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */ 1351 SCIP_SET* set, /**< global SCIP settings */ 1352 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */ 1353 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 1354 const char* name, /**< name of branching rule */ 1355 const char* desc, /**< description of branching rule */ 1356 int priority, /**< priority of the branching rule */ 1357 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */ 1358 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound 1359 * compared to best node's dual bound for applying branching rule 1360 * (0.0: only on current best node, 1.0: on all nodes) */ 1361 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */ 1362 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */ 1363 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */ 1364 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */ 1365 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */ 1366 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */ 1367 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */ 1368 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */ 1369 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */ 1370 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 1371 ) 1372 { 1373 assert(branchrule != NULL); 1374 assert(name != NULL); 1375 assert(desc != NULL); 1376 1377 SCIP_CALL_FINALLY( doBranchruleCreate(branchrule, set, messagehdlr, blkmem, name, desc, priority, maxdepth, 1378 maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol, branchexeclp, 1379 branchexecext, branchexecps, branchruledata), (void) SCIPbranchruleFree(branchrule, set) ); 1380 1381 return SCIP_OKAY; 1382 } 1383 1384 /** frees memory of branching rule */ 1385 SCIP_RETCODE SCIPbranchruleFree( 1386 SCIP_BRANCHRULE** branchrule, /**< pointer to branching rule data structure */ 1387 SCIP_SET* set /**< global SCIP settings */ 1388 ) 1389 { 1390 assert(branchrule != NULL); 1391 if( *branchrule == NULL ) 1392 return SCIP_OKAY; 1393 assert(!(*branchrule)->initialized); 1394 assert(set != NULL); 1395 1396 /* call destructor of branching rule */ 1397 if( (*branchrule)->branchfree != NULL ) 1398 { 1399 SCIP_CALL( (*branchrule)->branchfree(set->scip, *branchrule) ); 1400 } 1401 1402 SCIPclockFree(&(*branchrule)->branchclock); 1403 SCIPclockFree(&(*branchrule)->setuptime); 1404 BMSfreeMemoryArrayNull(&(*branchrule)->name); 1405 BMSfreeMemoryArrayNull(&(*branchrule)->desc); 1406 BMSfreeMemory(branchrule); 1407 1408 return SCIP_OKAY; 1409 } 1410 1411 /** initializes branching rule */ 1412 SCIP_RETCODE SCIPbranchruleInit( 1413 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1414 SCIP_SET* set /**< global SCIP settings */ 1415 ) 1416 { 1417 assert(branchrule != NULL); 1418 assert(set != NULL); 1419 1420 if( branchrule->initialized ) 1421 { 1422 SCIPerrorMessage("branching rule <%s> already initialized\n", branchrule->name); 1423 return SCIP_INVALIDCALL; 1424 } 1425 1426 if( set->misc_resetstat ) 1427 { 1428 SCIPclockReset(branchrule->setuptime); 1429 SCIPclockReset(branchrule->branchclock); 1430 branchrule->nlpcalls = 0; 1431 branchrule->nexterncalls = 0; 1432 branchrule->npseudocalls = 0; 1433 branchrule->ncutoffs = 0; 1434 branchrule->ncutsfound = 0; 1435 branchrule->nconssfound = 0; 1436 branchrule->ndomredsfound = 0; 1437 branchrule->nchildren = 0; 1438 } 1439 1440 if( branchrule->branchinit != NULL ) 1441 { 1442 /* start timing */ 1443 SCIPclockStart(branchrule->setuptime, set); 1444 1445 SCIP_CALL( branchrule->branchinit(set->scip, branchrule) ); 1446 1447 /* stop timing */ 1448 SCIPclockStop(branchrule->setuptime, set); 1449 } 1450 branchrule->initialized = TRUE; 1451 1452 return SCIP_OKAY; 1453 } 1454 1455 /** deinitializes branching rule */ 1456 SCIP_RETCODE SCIPbranchruleExit( 1457 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1458 SCIP_SET* set /**< global SCIP settings */ 1459 ) 1460 { 1461 assert(branchrule != NULL); 1462 assert(set != NULL); 1463 1464 if( !branchrule->initialized ) 1465 { 1466 SCIPerrorMessage("branching rule <%s> not initialized\n", branchrule->name); 1467 return SCIP_INVALIDCALL; 1468 } 1469 1470 if( branchrule->branchexit != NULL ) 1471 { 1472 /* start timing */ 1473 SCIPclockStart(branchrule->setuptime, set); 1474 1475 SCIP_CALL( branchrule->branchexit(set->scip, branchrule) ); 1476 1477 /* stop timing */ 1478 SCIPclockStop(branchrule->setuptime, set); 1479 } 1480 branchrule->initialized = FALSE; 1481 1482 return SCIP_OKAY; 1483 } 1484 1485 /** informs branching rule that the branch and bound process is being started */ 1486 SCIP_RETCODE SCIPbranchruleInitsol( 1487 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1488 SCIP_SET* set /**< global SCIP settings */ 1489 ) 1490 { 1491 assert(branchrule != NULL); 1492 assert(set != NULL); 1493 1494 /* call solving process initialization method of branching rule */ 1495 if( branchrule->branchinitsol != NULL ) 1496 { 1497 /* start timing */ 1498 SCIPclockStart(branchrule->setuptime, set); 1499 1500 SCIP_CALL( branchrule->branchinitsol(set->scip, branchrule) ); 1501 1502 /* stop timing */ 1503 SCIPclockStop(branchrule->setuptime, set); 1504 } 1505 1506 return SCIP_OKAY; 1507 } 1508 1509 /** informs branching rule that the branch and bound process data is being freed */ 1510 SCIP_RETCODE SCIPbranchruleExitsol( 1511 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1512 SCIP_SET* set /**< global SCIP settings */ 1513 ) 1514 { 1515 assert(branchrule != NULL); 1516 assert(set != NULL); 1517 1518 /* call solving process deinitialization method of branching rule */ 1519 if( branchrule->branchexitsol != NULL ) 1520 { 1521 /* start timing */ 1522 SCIPclockStart(branchrule->setuptime, set); 1523 1524 SCIP_CALL( branchrule->branchexitsol(set->scip, branchrule) ); 1525 1526 /* stop timing */ 1527 SCIPclockStop(branchrule->setuptime, set); 1528 } 1529 1530 return SCIP_OKAY; 1531 } 1532 1533 /** executes branching rule for fractional LP solution */ 1534 SCIP_RETCODE SCIPbranchruleExecLPSol( 1535 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1536 SCIP_SET* set, /**< global SCIP settings */ 1537 SCIP_STAT* stat, /**< problem statistics */ 1538 SCIP_TREE* tree, /**< branch and bound tree */ 1539 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1540 SCIP_Real cutoffbound, /**< global upper cutoff bound */ 1541 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */ 1542 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 1543 ) 1544 { 1545 assert(branchrule != NULL); 1546 assert(set != NULL); 1547 assert(tree != NULL); 1548 assert(tree->focusnode != NULL); 1549 assert(tree->nchildren == 0); 1550 assert(result != NULL); 1551 1552 *result = SCIP_DIDNOTRUN; 1553 if( branchrule->branchexeclp != NULL 1554 && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) ) 1555 { 1556 SCIP_Real loclowerbound; 1557 SCIP_Real glblowerbound; 1558 SCIP_Bool runbranchrule; 1559 1560 loclowerbound = SCIPnodeGetLowerbound(tree->focusnode); 1561 glblowerbound = SCIPtreeGetLowerbound(tree, set); 1562 1563 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */ 1564 if( SCIPsetIsInfinity(set, -glblowerbound) ) 1565 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0); 1566 else 1567 { 1568 assert(!SCIPsetIsInfinity(set, -loclowerbound)); 1569 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound)); 1570 } 1571 1572 if( runbranchrule ) 1573 { 1574 SCIP_Longint oldndomchgs; 1575 SCIP_Longint oldnprobdomchgs; 1576 SCIP_Longint oldnactiveconss; 1577 int oldncuts; 1578 1579 SCIPsetDebugMsg(set, "executing LP branching rule <%s>\n", branchrule->name); 1580 1581 oldndomchgs = stat->nboundchgs + stat->nholechgs; 1582 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs; 1583 oldncuts = SCIPsepastoreGetNCuts(sepastore); 1584 oldnactiveconss = stat->nactiveconssadded; 1585 1586 /* start timing */ 1587 SCIPclockStart(branchrule->branchclock, set); 1588 1589 /* call external method */ 1590 SCIP_CALL( branchrule->branchexeclp(set->scip, branchrule, allowaddcons, result) ); 1591 1592 /* stop timing */ 1593 SCIPclockStop(branchrule->branchclock, set); 1594 1595 /* evaluate result */ 1596 if( *result != SCIP_CUTOFF 1597 && *result != SCIP_CONSADDED 1598 && *result != SCIP_REDUCEDDOM 1599 && *result != SCIP_SEPARATED 1600 && *result != SCIP_BRANCHED 1601 && *result != SCIP_DIDNOTFIND 1602 && *result != SCIP_DIDNOTRUN ) 1603 { 1604 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from LP solution branching\n", 1605 branchrule->name, *result); 1606 return SCIP_INVALIDRESULT; 1607 } 1608 if( *result == SCIP_CONSADDED && !allowaddcons ) 1609 { 1610 SCIPerrorMessage("branching rule <%s> added a constraint in LP solution branching without permission\n", 1611 branchrule->name); 1612 return SCIP_INVALIDRESULT; 1613 } 1614 1615 /* update statistics */ 1616 if( *result != SCIP_DIDNOTRUN ) 1617 branchrule->nlpcalls++; 1618 if( *result == SCIP_CUTOFF ) 1619 branchrule->ncutoffs++; 1620 if( *result != SCIP_BRANCHED ) 1621 { 1622 assert(tree->nchildren == 0); 1623 1624 /* update domain reductions; therefore remove the domain 1625 * reduction counts which were generated in probing mode */ 1626 branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs; 1627 branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs); 1628 1629 branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/ 1630 branchrule->nconssfound += stat->nactiveconssadded - oldnactiveconss; /*lint !e776*/ 1631 } 1632 else 1633 branchrule->nchildren += tree->nchildren; 1634 } 1635 } 1636 1637 return SCIP_OKAY; 1638 } 1639 1640 /** executes branching rule for external branching candidates */ 1641 SCIP_RETCODE SCIPbranchruleExecExternSol( 1642 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1643 SCIP_SET* set, /**< global SCIP settings */ 1644 SCIP_STAT* stat, /**< problem statistics */ 1645 SCIP_TREE* tree, /**< branch and bound tree */ 1646 SCIP_SEPASTORE* sepastore, /**< separation storage */ 1647 SCIP_Real cutoffbound, /**< global upper cutoff bound */ 1648 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */ 1649 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 1650 ) 1651 { 1652 assert(branchrule != NULL); 1653 assert(set != NULL); 1654 assert(tree != NULL); 1655 assert(tree->focusnode != NULL); 1656 assert(tree->nchildren == 0); 1657 assert(result != NULL); 1658 1659 *result = SCIP_DIDNOTRUN; 1660 if( branchrule->branchexecext != NULL 1661 && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) ) 1662 { 1663 SCIP_Real loclowerbound; 1664 SCIP_Real glblowerbound; 1665 SCIP_Bool runbranchrule; 1666 1667 loclowerbound = SCIPnodeGetLowerbound(tree->focusnode); 1668 glblowerbound = SCIPtreeGetLowerbound(tree, set); 1669 assert(!SCIPsetIsInfinity(set, loclowerbound)); 1670 1671 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */ 1672 if( SCIPsetIsInfinity(set, -glblowerbound) ) 1673 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0); 1674 else 1675 { 1676 assert(!SCIPsetIsInfinity(set, -loclowerbound)); 1677 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound)); 1678 } 1679 1680 if( runbranchrule ) 1681 { 1682 SCIP_Longint oldndomchgs; 1683 SCIP_Longint oldnprobdomchgs; 1684 int oldncuts; 1685 int oldnactiveconss; 1686 1687 SCIPsetDebugMsg(set, "executing external solution branching rule <%s>\n", branchrule->name); 1688 1689 oldndomchgs = stat->nboundchgs + stat->nholechgs; 1690 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs; 1691 oldncuts = SCIPsepastoreGetNCuts(sepastore); 1692 oldnactiveconss = stat->nactiveconss; 1693 1694 /* start timing */ 1695 SCIPclockStart(branchrule->branchclock, set); 1696 1697 /* call external method */ 1698 SCIP_CALL( branchrule->branchexecext(set->scip, branchrule, allowaddcons, result) ); 1699 1700 /* stop timing */ 1701 SCIPclockStop(branchrule->branchclock, set); 1702 1703 /* evaluate result */ 1704 if( *result != SCIP_CUTOFF 1705 && *result != SCIP_CONSADDED 1706 && *result != SCIP_REDUCEDDOM 1707 && *result != SCIP_SEPARATED 1708 && *result != SCIP_BRANCHED 1709 && *result != SCIP_DIDNOTFIND 1710 && *result != SCIP_DIDNOTRUN ) 1711 { 1712 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from external solution branching\n", 1713 branchrule->name, *result); 1714 return SCIP_INVALIDRESULT; 1715 } 1716 if( *result == SCIP_CONSADDED && !allowaddcons ) 1717 { 1718 SCIPerrorMessage("branching rule <%s> added a constraint in external solution branching without permission\n", 1719 branchrule->name); 1720 return SCIP_INVALIDRESULT; 1721 } 1722 1723 /* update statistics */ 1724 if( *result != SCIP_DIDNOTRUN ) 1725 branchrule->nexterncalls++; 1726 if( *result == SCIP_CUTOFF ) 1727 branchrule->ncutoffs++; 1728 if( *result != SCIP_BRANCHED ) 1729 { 1730 assert(tree->nchildren == 0); 1731 1732 /* update domain reductions; therefore remove the domain 1733 * reduction counts which were generated in probing mode */ 1734 branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs; 1735 branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs); 1736 1737 branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/ 1738 branchrule->nconssfound += stat->nactiveconss - oldnactiveconss; /*lint !e776*/ 1739 } 1740 else 1741 branchrule->nchildren += tree->nchildren; 1742 } 1743 } 1744 return SCIP_OKAY; 1745 } 1746 1747 /** executes branching rule for not completely fixed pseudo solution */ 1748 SCIP_RETCODE SCIPbranchruleExecPseudoSol( 1749 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1750 SCIP_SET* set, /**< global SCIP settings */ 1751 SCIP_STAT* stat, /**< problem statistics */ 1752 SCIP_TREE* tree, /**< branch and bound tree */ 1753 SCIP_Real cutoffbound, /**< global upper cutoff bound */ 1754 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */ 1755 SCIP_RESULT* result /**< pointer to store the result of the callback method */ 1756 ) 1757 { 1758 assert(branchrule != NULL); 1759 assert(set != NULL); 1760 assert(tree != NULL); 1761 assert(tree->nchildren == 0); 1762 assert(result != NULL); 1763 1764 *result = SCIP_DIDNOTRUN; 1765 if( branchrule->branchexecps != NULL 1766 && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) ) 1767 { 1768 SCIP_Real loclowerbound; 1769 SCIP_Real glblowerbound; 1770 SCIP_Bool runbranchrule; 1771 1772 loclowerbound = SCIPnodeGetLowerbound(tree->focusnode); 1773 glblowerbound = SCIPtreeGetLowerbound(tree, set); 1774 1775 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */ 1776 if( SCIPsetIsInfinity(set, -glblowerbound) ) 1777 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0); 1778 else 1779 { 1780 assert(!SCIPsetIsInfinity(set, -loclowerbound)); 1781 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound)); 1782 } 1783 1784 if( runbranchrule ) 1785 { 1786 SCIP_Longint oldndomchgs; 1787 SCIP_Longint oldnprobdomchgs; 1788 SCIP_Longint oldnactiveconss; 1789 1790 SCIPsetDebugMsg(set, "executing pseudo branching rule <%s>\n", branchrule->name); 1791 1792 oldndomchgs = stat->nboundchgs + stat->nholechgs; 1793 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs; 1794 oldnactiveconss = stat->nactiveconss; 1795 1796 /* start timing */ 1797 SCIPclockStart(branchrule->branchclock, set); 1798 1799 /* call external method */ 1800 SCIP_CALL( branchrule->branchexecps(set->scip, branchrule, allowaddcons, result) ); 1801 1802 /* stop timing */ 1803 SCIPclockStop(branchrule->branchclock, set); 1804 1805 /* evaluate result */ 1806 if( *result != SCIP_CUTOFF 1807 && *result != SCIP_CONSADDED 1808 && *result != SCIP_REDUCEDDOM 1809 && *result != SCIP_BRANCHED 1810 && *result != SCIP_DIDNOTFIND 1811 && *result != SCIP_DIDNOTRUN ) 1812 { 1813 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from pseudo solution branching\n", 1814 branchrule->name, *result); 1815 return SCIP_INVALIDRESULT; 1816 } 1817 if( *result == SCIP_CONSADDED && !allowaddcons ) 1818 { 1819 SCIPerrorMessage("branching rule <%s> added a constraint in pseudo solution branching without permission\n", 1820 branchrule->name); 1821 return SCIP_INVALIDRESULT; 1822 } 1823 1824 /* update statistics */ 1825 if( *result != SCIP_DIDNOTRUN ) 1826 branchrule->npseudocalls++; 1827 if( *result == SCIP_CUTOFF ) 1828 branchrule->ncutoffs++; 1829 if( *result != SCIP_BRANCHED ) 1830 { 1831 assert(tree->nchildren == 0); 1832 1833 /* update domain reductions; therefore remove the domain 1834 * reduction counts which were generated in probing mode */ 1835 branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs; 1836 branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs); 1837 1838 branchrule->nconssfound += stat->nactiveconss - oldnactiveconss; 1839 } 1840 else 1841 branchrule->nchildren += tree->nchildren; 1842 } 1843 } 1844 1845 return SCIP_OKAY; 1846 } 1847 1848 /** gets user data of branching rule */ 1849 SCIP_BRANCHRULEDATA* SCIPbranchruleGetData( 1850 SCIP_BRANCHRULE* branchrule /**< branching rule */ 1851 ) 1852 { 1853 assert(branchrule != NULL); 1854 1855 return branchrule->branchruledata; 1856 } 1857 1858 /** sets user data of branching rule; user has to free old data in advance! */ 1859 void SCIPbranchruleSetData( 1860 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1861 SCIP_BRANCHRULEDATA* branchruledata /**< new branching rule user data */ 1862 ) 1863 { 1864 assert(branchrule != NULL); 1865 1866 branchrule->branchruledata = branchruledata; 1867 } 1868 1869 /** sets copy method of branching rule */ 1870 void SCIPbranchruleSetCopy( 1871 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1872 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */ 1873 ) 1874 { 1875 assert(branchrule != NULL); 1876 1877 branchrule->branchcopy = branchcopy; 1878 } 1879 1880 /** sets destructor method of branching rule */ 1881 void SCIPbranchruleSetFree( 1882 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1883 SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */ 1884 ) 1885 { 1886 assert(branchrule != NULL); 1887 1888 branchrule->branchfree = branchfree; 1889 } 1890 1891 /** sets initialization method of branching rule */ 1892 void SCIPbranchruleSetInit( 1893 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1894 SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */ 1895 ) 1896 { 1897 assert(branchrule != NULL); 1898 1899 branchrule->branchinit = branchinit; 1900 } 1901 1902 /** sets deinitialization method of branching rule */ 1903 void SCIPbranchruleSetExit( 1904 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1905 SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */ 1906 ) 1907 { 1908 assert(branchrule != NULL); 1909 1910 branchrule->branchexit = branchexit; 1911 } 1912 1913 /** sets solving process initialization method of branching rule */ 1914 void SCIPbranchruleSetInitsol( 1915 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1916 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */ 1917 ) 1918 { 1919 assert(branchrule != NULL); 1920 1921 branchrule->branchinitsol = branchinitsol; 1922 } 1923 1924 /** sets solving process deinitialization method of branching rule */ 1925 void SCIPbranchruleSetExitsol( 1926 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1927 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */ 1928 ) 1929 { 1930 assert(branchrule != NULL); 1931 1932 branchrule->branchexitsol = branchexitsol; 1933 } 1934 1935 1936 1937 /** sets branching execution method for fractional LP solutions */ 1938 void SCIPbranchruleSetExecLp( 1939 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1940 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */ 1941 ) 1942 { 1943 assert(branchrule != NULL); 1944 1945 branchrule->branchexeclp = branchexeclp; 1946 } 1947 1948 /** sets branching execution method for external candidates */ 1949 void SCIPbranchruleSetExecExt( 1950 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1951 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */ 1952 ) 1953 { 1954 assert(branchrule != NULL); 1955 1956 branchrule->branchexecext = branchexecext; 1957 } 1958 1959 /** sets branching execution method for not completely fixed pseudo solutions */ 1960 void SCIPbranchruleSetExecPs( 1961 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 1962 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */ 1963 ) 1964 { 1965 assert(branchrule != NULL); 1966 1967 branchrule->branchexecps = branchexecps; 1968 } 1969 1970 /** gets name of branching rule */ 1971 const char* SCIPbranchruleGetName( 1972 SCIP_BRANCHRULE* branchrule /**< branching rule */ 1973 ) 1974 { 1975 assert(branchrule != NULL); 1976 1977 return branchrule->name; 1978 } 1979 1980 /** gets description of branching rule */ 1981 const char* SCIPbranchruleGetDesc( 1982 SCIP_BRANCHRULE* branchrule /**< branching rule */ 1983 ) 1984 { 1985 assert(branchrule != NULL); 1986 1987 return branchrule->desc; 1988 } 1989 1990 /** gets priority of branching rule */ 1991 int SCIPbranchruleGetPriority( 1992 SCIP_BRANCHRULE* branchrule /**< branching rule */ 1993 ) 1994 { 1995 assert(branchrule != NULL); 1996 1997 return branchrule->priority; 1998 } 1999 2000 /** sets priority of branching rule */ 2001 void SCIPbranchruleSetPriority( 2002 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 2003 SCIP_SET* set, /**< global SCIP settings */ 2004 int priority /**< new priority of the branching rule */ 2005 ) 2006 { 2007 assert(branchrule != NULL); 2008 assert(set != NULL); 2009 2010 branchrule->priority = priority; 2011 set->branchrulessorted = FALSE; 2012 } 2013 2014 /** gets maximal depth level, up to which this branching rule should be used (-1 for no limit) */ 2015 int SCIPbranchruleGetMaxdepth( 2016 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2017 ) 2018 { 2019 assert(branchrule != NULL); 2020 2021 return branchrule->maxdepth; 2022 } 2023 2024 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */ 2025 void SCIPbranchruleSetMaxdepth( 2026 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 2027 int maxdepth /**< new maxdepth of the branching rule */ 2028 ) 2029 { 2030 assert(branchrule != NULL); 2031 assert(maxdepth >= -1); 2032 2033 branchrule->maxdepth = maxdepth; 2034 } 2035 2036 /** gets maximal relative distance from current node's dual bound to primal bound for applying branching rule */ 2037 SCIP_Real SCIPbranchruleGetMaxbounddist( 2038 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2039 ) 2040 { 2041 assert(branchrule != NULL); 2042 2043 return branchrule->maxbounddist; 2044 } 2045 2046 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */ 2047 void SCIPbranchruleSetMaxbounddist( 2048 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 2049 SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */ 2050 ) 2051 { 2052 assert(branchrule != NULL); 2053 assert(maxbounddist >= -1); 2054 2055 branchrule->maxbounddist = maxbounddist; 2056 } 2057 2058 /** enables or disables all clocks of \p branchrule, depending on the value of the flag */ 2059 void SCIPbranchruleEnableOrDisableClocks( 2060 SCIP_BRANCHRULE* branchrule, /**< the branching rule for which all clocks should be enabled or disabled */ 2061 SCIP_Bool enable /**< should the clocks of the branching rule be enabled? */ 2062 ) 2063 { 2064 assert(branchrule != NULL); 2065 2066 SCIPclockEnableOrDisable(branchrule->setuptime, enable); 2067 SCIPclockEnableOrDisable(branchrule->branchclock, enable); 2068 } 2069 2070 /** gets time in seconds used in this branching rule for setting up for next stages */ 2071 SCIP_Real SCIPbranchruleGetSetupTime( 2072 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2073 ) 2074 { 2075 assert(branchrule != NULL); 2076 2077 return SCIPclockGetTime(branchrule->setuptime); 2078 } 2079 2080 /** gets time in seconds used in this branching rule */ 2081 SCIP_Real SCIPbranchruleGetTime( 2082 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2083 ) 2084 { 2085 assert(branchrule != NULL); 2086 2087 return SCIPclockGetTime(branchrule->branchclock); 2088 } 2089 2090 /** gets the total number of times, the branching rule was called on an LP solution */ 2091 SCIP_Longint SCIPbranchruleGetNLPCalls( 2092 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2093 ) 2094 { 2095 assert(branchrule != NULL); 2096 2097 return branchrule->nlpcalls; 2098 } 2099 2100 /** gets the total number of times, the branching rule was called on an external solution */ 2101 SCIP_Longint SCIPbranchruleGetNExternCalls( 2102 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2103 ) 2104 { 2105 assert(branchrule != NULL); 2106 2107 return branchrule->nexterncalls; 2108 } 2109 2110 /** gets the total number of times, the branching rule was called on a pseudo solution */ 2111 SCIP_Longint SCIPbranchruleGetNPseudoCalls( 2112 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2113 ) 2114 { 2115 assert(branchrule != NULL); 2116 2117 return branchrule->npseudocalls; 2118 } 2119 2120 /** gets the total number of times, the branching rule detected a cutoff */ 2121 SCIP_Longint SCIPbranchruleGetNCutoffs( 2122 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2123 ) 2124 { 2125 assert(branchrule != NULL); 2126 2127 return branchrule->ncutoffs; 2128 } 2129 2130 /** gets the total number of cuts, the branching rule separated */ 2131 SCIP_Longint SCIPbranchruleGetNCutsFound( 2132 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2133 ) 2134 { 2135 assert(branchrule != NULL); 2136 2137 return branchrule->ncutsfound; 2138 } 2139 2140 /** gets the total number of constraints, the branching rule added to the respective local nodes (not counting constraints 2141 * that were added to the child nodes as branching decisions) 2142 */ 2143 SCIP_Longint SCIPbranchruleGetNConssFound( 2144 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2145 ) 2146 { 2147 assert(branchrule != NULL); 2148 2149 return branchrule->nconssfound; 2150 } 2151 2152 /** gets the total number of domain reductions, the branching rule found */ 2153 SCIP_Longint SCIPbranchruleGetNDomredsFound( 2154 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2155 ) 2156 { 2157 assert(branchrule != NULL); 2158 2159 return branchrule->ndomredsfound; 2160 } 2161 2162 /** gets the total number of children, the branching rule created */ 2163 SCIP_Longint SCIPbranchruleGetNChildren( 2164 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2165 ) 2166 { 2167 assert(branchrule != NULL); 2168 2169 return branchrule->nchildren; 2170 } 2171 2172 /** is branching rule initialized? */ 2173 SCIP_Bool SCIPbranchruleIsInitialized( 2174 SCIP_BRANCHRULE* branchrule /**< branching rule */ 2175 ) 2176 { 2177 assert(branchrule != NULL); 2178 2179 return branchrule->initialized; 2180 } 2181 2182 2183 2184 2185 /* 2186 * branching methods 2187 */ 2188 2189 /** calculates the branching score out of the gain predictions for a binary branching */ 2190 SCIP_Real SCIPbranchGetScore( 2191 SCIP_SET* set, /**< global SCIP settings */ 2192 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 2193 SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */ 2194 SCIP_Real upgain /**< prediction of objective gain for rounding upwards */ 2195 ) 2196 { 2197 SCIP_Real score; 2198 SCIP_Real eps; 2199 2200 assert(set != NULL); 2201 2202 /* adjust scores near zero to always yield product score greater than 0 */ 2203 eps = SCIPsetSumepsilon(set); 2204 if( set->branch_sumadjustscore ) 2205 { 2206 /* adjust scores by adding eps to keep near zero score differences between variables */ 2207 downgain = downgain + eps; 2208 upgain = upgain + eps; 2209 } 2210 else 2211 { 2212 /* disregard near zero score differences between variables and consider the branching factor for them */ 2213 downgain = MAX(downgain, eps); 2214 upgain = MAX(upgain, eps); 2215 } 2216 2217 switch( set->branch_scorefunc ) 2218 { 2219 case 's': /* linear sum score function */ 2220 /* weigh the two child nodes with branchscorefac and 1-branchscorefac */ 2221 if( downgain > upgain ) 2222 score = set->branch_scorefac * downgain + (1.0-set->branch_scorefac) * upgain; 2223 else 2224 score = set->branch_scorefac * upgain + (1.0-set->branch_scorefac) * downgain; 2225 break; 2226 2227 case 'p': /* product score function */ 2228 score = downgain * upgain; 2229 break; 2230 case 'q': /* quotient score function */ 2231 if( downgain > upgain ) 2232 score = upgain * upgain / downgain; 2233 else 2234 score = downgain * downgain / upgain; 2235 break; 2236 default: 2237 SCIPerrorMessage("invalid branching score function <%c>\n", set->branch_scorefunc); 2238 SCIPABORT(); 2239 score = 0.0; 2240 } 2241 2242 /* apply the branch factor of the variable */ 2243 if( var != NULL ) 2244 score *= SCIPvarGetBranchFactor(var); 2245 2246 return score; 2247 } 2248 2249 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children */ 2250 SCIP_Real SCIPbranchGetScoreMultiple( 2251 SCIP_SET* set, /**< global SCIP settings */ 2252 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 2253 int nchildren, /**< number of children that the branching will create */ 2254 SCIP_Real* gains /**< prediction of objective gain for each child */ 2255 ) 2256 { 2257 SCIP_Real min1; 2258 SCIP_Real min2; 2259 int c; 2260 2261 assert(nchildren == 0 || gains != NULL); 2262 2263 /* search for the two minimal gains in the child list and use these to calculate the branching score */ 2264 min1 = SCIPsetInfinity(set); 2265 min2 = SCIPsetInfinity(set); 2266 for( c = 0; c < nchildren; ++c ) 2267 { 2268 if( gains[c] < min1 ) 2269 { 2270 min2 = min1; 2271 min1 = gains[c]; 2272 } 2273 else if( gains[c] < min2 ) 2274 min2 = gains[c]; 2275 } 2276 2277 return SCIPbranchGetScore(set, var, min1, min2); 2278 } 2279 2280 /** computes a branching point for a (not necessarily discrete) variable 2281 * a suggested branching point is first projected onto the box 2282 * if no point is suggested, then the value in the current LP or pseudo solution is used 2283 * if this value is at infinity, then 0.0 projected onto the bounds and then moved inside the interval is used 2284 * for a discrete variable, it is ensured that the returned value is fractional 2285 * for a continuous variable, the parameter branching/clamp defines how far a branching point need to be from the bounds of a variable 2286 * the latter is only applied if no point has been suggested, or the suggested point is not inside the variable's interval 2287 */ 2288 SCIP_Real SCIPbranchGetBranchingPoint( 2289 SCIP_SET* set, /**< global SCIP settings */ 2290 SCIP_TREE* tree, /**< branch and bound tree */ 2291 SCIP_VAR* var, /**< variable, of which the branching point should be computed */ 2292 SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */ 2293 ) 2294 { 2295 SCIP_Real branchpoint; 2296 SCIP_Real lb; 2297 SCIP_Real ub; 2298 2299 assert(set != NULL); 2300 assert(var != NULL); 2301 2302 lb = SCIPvarGetLbLocal(var); 2303 ub = SCIPvarGetUbLocal(var); 2304 2305 /* for a fixed variable, we cannot branch further */ 2306 assert(!SCIPsetIsEQ(set, lb, ub)); 2307 2308 if( !SCIPsetIsInfinity(set, REALABS(suggestion)) ) 2309 { 2310 /* use user suggested branching point */ 2311 2312 /* first, project it onto the current domain */ 2313 branchpoint = MAX(lb, MIN(suggestion, ub)); 2314 2315 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ) 2316 { 2317 /* if it is a discrete variable, then round it down and up and accept this choice */ 2318 if( SCIPsetIsEQ(set, branchpoint, ub) ) 2319 { 2320 /* in the right branch, variable is fixed to its current upper bound */ 2321 return SCIPsetFloor(set, branchpoint) - 0.5; 2322 } 2323 else 2324 { 2325 /* in the left branch, variable is fixed to its current lower bound */ 2326 return SCIPsetFloor(set, branchpoint) + 0.5; 2327 } 2328 } 2329 else if( (SCIPsetIsInfinity(set, -lb) || SCIPsetIsRelGT(set, branchpoint, lb)) && 2330 (SCIPsetIsInfinity(set, ub) || SCIPsetIsRelLT(set, branchpoint, ub)) ) 2331 { 2332 /* if it is continuous and inside the box, then accept it */ 2333 return branchpoint; 2334 } 2335 /* if it is continuous and suggestion is on of the bounds, continue below */ 2336 } 2337 else 2338 { 2339 /* if no point is suggested, try the LP or pseudo solution */ 2340 branchpoint = SCIPvarGetSol(var, SCIPtreeHasCurrentNodeLP(tree)); 2341 2342 if( REALABS(branchpoint) > 1e+12 ) 2343 { 2344 /* if the value in the LP or pseudosolution is large (here 1e+12), use 0.0 (will be projected onto bounds below) */ 2345 branchpoint = 0.0; 2346 } 2347 else if( SCIPtreeHasCurrentNodeLP(tree) && set->branch_midpull > 0.0 && !SCIPsetIsInfinity(set, -lb) && !SCIPsetIsInfinity(set, ub) ) 2348 { 2349 /* if the value is from the LP and midpull is activated, then push towards middle of domain */ 2350 SCIP_Real midpull = set->branch_midpull; 2351 SCIP_Real glb; 2352 SCIP_Real gub; 2353 SCIP_Real reldomainwidth; 2354 2355 /* shrink midpull if width of local domain, relative to global domain, is small 2356 * that is, if there has been already one or several branchings on this variable, then give more emphasis on LP solution 2357 * 2358 * do this only if the relative domain width is below the minreldomainwidth value 2359 */ 2360 glb = SCIPvarGetLbGlobal(var); 2361 gub = SCIPvarGetUbGlobal(var); 2362 assert(glb < gub); 2363 2364 if( !SCIPsetIsInfinity(set, -glb) && !SCIPsetIsInfinity(set, gub) ) 2365 reldomainwidth = (ub - lb) / (gub - glb); 2366 else 2367 reldomainwidth = SCIPsetEpsilon(set); 2368 2369 if( reldomainwidth < set->branch_midpullreldomtrig ) 2370 midpull *= reldomainwidth; 2371 2372 branchpoint = midpull * (lb+ub) / 2.0 + (1.0 - midpull) * branchpoint; 2373 } 2374 2375 /* make sure branchpoint is on interval, below we make sure that it is within bounds for continuous vars */ 2376 branchpoint = MAX(lb, MIN(branchpoint, ub)); 2377 } 2378 2379 /* if value is at +/- infty, then choose some value a bit off from bounds or 0.0 */ 2380 if( SCIPsetIsInfinity(set, branchpoint) ) 2381 { 2382 /* if value is at +infty, then the upper bound should be at infinity */ 2383 assert(SCIPsetIsInfinity(set, ub)); 2384 2385 /* choose 0.0 or something above lower bound if lower bound > 0 */ 2386 if( SCIPsetIsPositive(set, lb) ) 2387 branchpoint = lb + 1000.0; 2388 else 2389 branchpoint = 0.0; 2390 } 2391 else if( SCIPsetIsInfinity(set, -branchpoint) ) 2392 { 2393 /* if value is at -infty, then the lower bound should be at -infinity */ 2394 assert(SCIPsetIsInfinity(set, -lb)); 2395 2396 /* choose 0.0 or something below upper bound if upper bound < 0 */ 2397 if( SCIPsetIsNegative(set, ub) ) 2398 branchpoint = ub - 1000.0; 2399 else 2400 branchpoint = 0.0; 2401 } 2402 2403 assert(SCIPsetIsInfinity(set, ub) || SCIPsetIsLE(set, branchpoint, ub)); 2404 assert(SCIPsetIsInfinity(set, -lb) || SCIPsetIsGE(set, branchpoint, lb)); 2405 2406 if( SCIPvarGetType(var) >= SCIP_VARTYPE_IMPLINT ) 2407 { 2408 if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) ) 2409 { 2410 /* if one bound is missing, we are temporarily guessing the other one, so we can apply the clamp below */ 2411 if( SCIPsetIsInfinity(set, ub) ) 2412 { 2413 ub = lb + MIN(MAX(0.5 * REALABS(lb), 1000), 0.9 * (SCIPsetInfinity(set) - lb)); /*lint !e666*/ 2414 } 2415 else if( SCIPsetIsInfinity(set, -lb) ) 2416 { 2417 lb = ub - MIN(MAX(0.5 * REALABS(ub), 1000), 0.9 * (SCIPsetInfinity(set) + ub)); /*lint !e666*/ 2418 } 2419 2420 /* if branching point is too close to the bounds, move more into the middle of the interval */ 2421 if( SCIPrelDiff(ub, lb) <= 2.02 * SCIPsetEpsilon(set) ) 2422 { 2423 /* for very tiny intervals we set it exactly into the middle */ 2424 branchpoint = (lb+ub)/2.0; 2425 } 2426 else 2427 { 2428 /* otherwise we project it away from the bounds */ 2429 SCIP_Real minbrpoint; 2430 SCIP_Real maxbrpoint; 2431 SCIP_Real scale; 2432 SCIP_Real lbabs; 2433 SCIP_Real ubabs; 2434 2435 lbabs = REALABS(lb); 2436 ubabs = REALABS(ub); 2437 2438 scale = MAX3(lbabs, ubabs, 1.0); 2439 2440 /* the minimal branching point should be 2441 * - set->clamp away from the lower bound - relative to the local domain size 2442 * - SCIPsetEpsilon(set)*scale above the lower bound - in absolute value 2443 */ 2444 minbrpoint = (1.0 - set->branch_clamp) * lb + set->branch_clamp * ub; 2445 minbrpoint = MAX(lb + 1.01*SCIPsetEpsilon(set)*scale, minbrpoint); /*lint !e666*/ 2446 2447 /* the maximal branching point should be 2448 * - set->clamp away from the upper bound - relative to the local domain size 2449 * - SCIPsetEpsilon(set)*scale below the upper bound - in absolute value 2450 */ 2451 maxbrpoint = set->branch_clamp * lb + (1.0 - set->branch_clamp) * ub; 2452 maxbrpoint = MIN(ub - 1.01*SCIPsetEpsilon(set)*scale, maxbrpoint); /*lint !e666*/ 2453 2454 /* project branchpoint into [minbrpoint, maxbrpoint] */ 2455 branchpoint = MAX(minbrpoint, MIN(branchpoint, maxbrpoint)); 2456 2457 /* if selected branching point is close to 0.0 and bounds are away from 0.0, it often makes sense to branch exactly on 0.0 */ 2458 if( SCIPsetIsFeasZero(set, branchpoint) && SCIPsetIsFeasNegative(set, lb) && SCIPsetIsFeasPositive(set, ub) ) 2459 branchpoint = 0.0; 2460 2461 assert(SCIPsetIsRelLT(set, SCIPvarGetLbLocal(var), branchpoint)); 2462 assert(SCIPsetIsRelLT(set, branchpoint, SCIPvarGetUbLocal(var))); 2463 } 2464 } 2465 2466 /* ensure fractional branching point for implicit integer variables */ 2467 if( SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT && SCIPsetIsIntegral(set, branchpoint) ) 2468 { 2469 /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */ 2470 assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0)); 2471 assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0)); 2472 /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x' 2473 * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better? 2474 */ 2475 return branchpoint - 0.5; 2476 } 2477 2478 return branchpoint; 2479 } 2480 else 2481 { 2482 /* discrete variables */ 2483 if( branchpoint <= lb + 0.5 ) 2484 { 2485 /* if branchpoint is on lower bound, create one branch with x = lb and one with x >= lb+1 */ 2486 return lb + 0.5; 2487 } 2488 else if( branchpoint >= ub - 0.5 ) 2489 { 2490 /* if branchpoint is on upper bound, create one branch with x = ub and one with x <= ub-1 */ 2491 return ub - 0.5; 2492 } 2493 else if( SCIPsetIsIntegral(set, branchpoint) ) 2494 { 2495 /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */ 2496 assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0)); 2497 assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0)); 2498 /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x' 2499 * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better? */ 2500 return branchpoint - 0.5; 2501 } 2502 else 2503 { 2504 /* branchpoint is somewhere between bounds and fractional, so just round down and up */ 2505 return branchpoint; 2506 } 2507 } 2508 } 2509 2510 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN; 2511 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional 2512 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority 2513 */ 2514 SCIP_RETCODE SCIPbranchExecLP( 2515 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 2516 SCIP_SET* set, /**< global SCIP settings */ 2517 SCIP_STAT* stat, /**< problem statistics */ 2518 SCIP_PROB* transprob, /**< transformed problem after presolve */ 2519 SCIP_PROB* origprob, /**< original problem */ 2520 SCIP_TREE* tree, /**< branch and bound tree */ 2521 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2522 SCIP_LP* lp, /**< current LP data */ 2523 SCIP_SEPASTORE* sepastore, /**< separation storage */ 2524 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2525 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2526 SCIP_Real cutoffbound, /**< global upper cutoff bound */ 2527 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */ 2528 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 2529 ) 2530 { 2531 int i; 2532 int nalllpcands; /* sum of binary, integer, and implicit branching candidates */ 2533 2534 assert(branchcand != NULL); 2535 assert(result != NULL); 2536 2537 *result = SCIP_DIDNOTRUN; 2538 2539 /* calculate branching candidates */ 2540 SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) ); 2541 assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands); 2542 assert((branchcand->npriolpcands == 0) == (branchcand->nlpcands == 0)); 2543 2544 SCIPsetDebugMsg(set, "branching on LP solution with %d (+%d) fractional (+implicit fractional) variables (%d of maximal priority)\n", 2545 branchcand->nlpcands, branchcand->nimpllpfracs, branchcand->npriolpcands); 2546 2547 nalllpcands = branchcand->nlpcands + branchcand->nimpllpfracs; 2548 /* do nothing, if no fractional variables exist */ 2549 if( nalllpcands == 0 ) 2550 return SCIP_OKAY; 2551 2552 /* if there is a non-fixed variable with higher priority than the maximal priority of the fractional candidates, 2553 * use pseudo solution branching instead 2554 */ 2555 if( branchcand->pseudomaxpriority > branchcand->lpmaxpriority ) 2556 { 2557 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound, 2558 allowaddcons, result) ); 2559 assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND); 2560 return SCIP_OKAY; 2561 } 2562 2563 /* sort the branching rules by priority */ 2564 SCIPsetSortBranchrules(set); 2565 2566 /* try all branching rules until one succeeded to branch */ 2567 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i ) 2568 { 2569 SCIP_CALL( SCIPbranchruleExecLPSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) ); 2570 } 2571 2572 if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND ) 2573 { 2574 SCIP_VAR* var; 2575 SCIP_Real factor; 2576 SCIP_Real bestfactor; 2577 int priority; 2578 int bestpriority; 2579 int bestcand; 2580 2581 /* no branching method succeeded in choosing a branching: just branch on the first fractional variable with maximal 2582 * priority, and out of these on the one with maximal branch factor 2583 */ 2584 bestcand = -1; 2585 bestpriority = INT_MIN; 2586 bestfactor = SCIP_REAL_MIN; 2587 for( i = 0; i < nalllpcands; ++i ) 2588 { 2589 priority = SCIPvarGetBranchPriority(branchcand->lpcands[i]); 2590 factor = SCIPvarGetBranchFactor(branchcand->lpcands[i]); 2591 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) ) 2592 { 2593 bestcand = i; 2594 bestpriority = priority; 2595 bestfactor = factor; 2596 } 2597 } 2598 assert(0 <= bestcand && bestcand < nalllpcands); 2599 2600 var = branchcand->lpcands[bestcand]; 2601 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS); 2602 assert(branchcand->nlpcands == 0 || SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT); 2603 2604 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); 2605 2606 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID, 2607 NULL, NULL, NULL) ); 2608 2609 *result = SCIP_BRANCHED; 2610 } 2611 2612 return SCIP_OKAY; 2613 } 2614 2615 /** calls branching rules to branch on an external solution; if no external branching candidates exist, the result is SCIP_DIDNOTRUN */ 2616 SCIP_RETCODE SCIPbranchExecExtern( 2617 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 2618 SCIP_SET* set, /**< global SCIP settings */ 2619 SCIP_STAT* stat, /**< problem statistics */ 2620 SCIP_PROB* transprob, /**< transformed problem after presolve */ 2621 SCIP_PROB* origprob, /**< original problem */ 2622 SCIP_TREE* tree, /**< branch and bound tree */ 2623 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2624 SCIP_LP* lp, /**< current LP data */ 2625 SCIP_SEPASTORE* sepastore, /**< separation storage */ 2626 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2627 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2628 SCIP_Real cutoffbound, /**< global upper cutoff bound */ 2629 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */ 2630 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 2631 ) 2632 { 2633 int i; 2634 2635 assert(branchcand != NULL); 2636 assert(result != NULL); 2637 assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands); 2638 assert((branchcand->nprioexterncands == 0) == (branchcand->nexterncands == 0)); 2639 2640 *result = SCIP_DIDNOTRUN; 2641 2642 SCIPsetDebugMsg(set, "branching on external solution with %d branching candidates (%d of maximal priority)\n", 2643 branchcand->nexterncands, branchcand->nprioexterncands); 2644 2645 /* do nothing, if no external candidates exist */ 2646 if( branchcand->nexterncands == 0 ) 2647 return SCIP_OKAY; 2648 2649 /* if there is a non-fixed variable with higher priority than the maximal priority of the external candidates, 2650 * use pseudo solution branching instead 2651 */ 2652 if( branchcand->pseudomaxpriority > branchcand->externmaxpriority ) 2653 { 2654 /* @todo: adjust this, that also LP branching might be called, if lpmaxpriority != externmaxpriority. 2655 * Therefor, it has to be clear which of both has the higher priority 2656 */ 2657 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound, 2658 allowaddcons, result) ); 2659 assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND); 2660 return SCIP_OKAY; 2661 } 2662 2663 /* sort the branching rules by priority */ 2664 SCIPsetSortBranchrules(set); 2665 2666 /* try all branching rules until one succeeded to branch */ 2667 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i ) 2668 { 2669 SCIP_CALL( SCIPbranchruleExecExternSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) ); 2670 } 2671 2672 if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND ) 2673 { 2674 SCIP_VAR* var; 2675 SCIP_Real val; 2676 SCIP_Real bestfactor; 2677 SCIP_Real bestdomain; 2678 int bestpriority; 2679 int bestcand; 2680 2681 /* if all branching rules did nothing, then they should also not have cleared all branching candidates */ 2682 assert(branchcand->nexterncands > 0); 2683 2684 /* no branching method succeeded in choosing a branching: just branch on the first branching candidates with maximal 2685 * priority, and out of these on the one with maximal branch factor, and out of these on the one with largest domain 2686 */ 2687 bestcand = -1; 2688 bestpriority = INT_MIN; 2689 bestfactor = SCIP_REAL_MIN; 2690 bestdomain = 0.0; 2691 for( i = 0; i < branchcand->nexterncands; ++i ) 2692 { 2693 SCIP_VAR* cand; 2694 SCIP_Real domain; 2695 SCIP_Real factor; 2696 int priority; 2697 2698 cand = branchcand->externcands[i]; 2699 priority = SCIPvarGetBranchPriority(cand); 2700 factor = SCIPvarGetBranchFactor(cand); 2701 2702 /* the domain size is infinite, iff one of the bounds is infinite */ 2703 if( SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(cand)) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(cand)) ) 2704 domain = SCIPsetInfinity(set); 2705 else 2706 domain = SCIPvarGetUbLocal(cand) - SCIPvarGetLbLocal(cand); 2707 2708 /* choose variable with higher priority, higher factor, larger domain (in that order) */ 2709 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) || (priority == bestpriority && factor == bestfactor && domain > bestdomain) ) /*lint !e777*/ 2710 { 2711 bestcand = i; 2712 bestpriority = priority; 2713 bestfactor = factor; 2714 bestdomain = domain; 2715 } 2716 } 2717 assert(0 <= bestcand && bestcand < branchcand->nexterncands); 2718 2719 var = branchcand->externcands[bestcand]; 2720 val = SCIPbranchGetBranchingPoint(set, tree, var, branchcand->externcandssol[bestcand]); 2721 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); 2722 assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set) 2723 || SCIPsetIsLT(set, SCIPvarGetLbLocal(var), val)); 2724 assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set) 2725 || SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var))); 2726 2727 SCIPsetDebugMsg(set, "no branching method succeeded; fallback selected to branch on variable <%s> with bounds [%g, %g] on value %g\n", 2728 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), val); 2729 2730 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, val, 2731 NULL, NULL, NULL) ); 2732 2733 if( tree->nchildren >= 1 ) 2734 *result = SCIP_BRANCHED; 2735 /* if the bounds are too close, it may happen that we cannot branch but rather fix the variable */ 2736 else 2737 { 2738 assert(SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); 2739 *result = SCIP_REDUCEDDOM; 2740 } 2741 } 2742 2743 return SCIP_OKAY; 2744 } 2745 2746 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN */ 2747 SCIP_RETCODE SCIPbranchExecPseudo( 2748 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */ 2749 SCIP_SET* set, /**< global SCIP settings */ 2750 SCIP_STAT* stat, /**< problem statistics */ 2751 SCIP_PROB* transprob, /**< transformed problem after presolve */ 2752 SCIP_PROB* origprob, /**< original problem */ 2753 SCIP_TREE* tree, /**< branch and bound tree */ 2754 SCIP_REOPT* reopt, /**< reoptimization data structure */ 2755 SCIP_LP* lp, /**< current LP data */ 2756 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */ 2757 SCIP_EVENTQUEUE* eventqueue, /**< event queue */ 2758 SCIP_Real cutoffbound, /**< global upper cutoff bound */ 2759 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */ 2760 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 2761 ) 2762 { 2763 int i; 2764 2765 assert(branchcand != NULL); 2766 assert(result != NULL); 2767 2768 SCIPsetDebugMsg(set, "branching on pseudo solution with %d unfixed variables\n", branchcand->npseudocands); 2769 2770 *result = SCIP_DIDNOTRUN; 2771 2772 /* do nothing, if no unfixed variables exist */ 2773 if( branchcand->npseudocands == 0 ) 2774 return SCIP_OKAY; 2775 2776 /* sort the branching rules by priority */ 2777 SCIPsetSortBranchrules(set); 2778 2779 /* try all branching rules until one succeeded to branch */ 2780 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i ) 2781 { 2782 SCIP_CALL( SCIPbranchruleExecPseudoSol(set->branchrules[i], set, stat, tree, cutoffbound, allowaddcons, result) ); 2783 } 2784 2785 if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND ) 2786 { 2787 SCIP_VAR* var; 2788 SCIP_Real factor; 2789 SCIP_Real bestfactor; 2790 int priority; 2791 int bestpriority; 2792 int bestcand; 2793 2794 /* no branching method succeeded in choosing a branching: just branch on the first unfixed variable with maximal 2795 * priority, and out of these on the one with maximal branch factor 2796 */ 2797 bestcand = -1; 2798 bestpriority = INT_MIN; 2799 bestfactor = SCIP_REAL_MIN; 2800 for( i = 0; i < branchcand->npseudocands; ++i ) 2801 { 2802 priority = SCIPvarGetBranchPriority(branchcand->pseudocands[i]); 2803 factor = SCIPvarGetBranchFactor(branchcand->pseudocands[i]); 2804 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) ) 2805 { 2806 bestcand = i; 2807 bestpriority = priority; 2808 bestfactor = factor; 2809 } 2810 } 2811 assert(0 <= bestcand && bestcand < branchcand->npseudocands); 2812 2813 var = branchcand->pseudocands[bestcand]; 2814 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS); 2815 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); 2816 2817 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID, 2818 NULL, NULL, NULL) ); 2819 2820 *result = SCIP_BRANCHED; 2821 } 2822 2823 return SCIP_OKAY; 2824 } 2825 2826