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_fullstrong.c 26 * @ingroup DEFPLUGINS_BRANCH 27 * @brief full strong LP branching rule 28 * @author Tobias Achterberg 29 * @author Gerald Gamrath 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include "blockmemshell/memory.h" 35 #include "scip/branch_fullstrong.h" 36 #include "scip/pub_branch.h" 37 #include "scip/pub_message.h" 38 #include "scip/pub_tree.h" 39 #include "scip/pub_var.h" 40 #include "scip/scip_branch.h" 41 #include "scip/scip_general.h" 42 #include "scip/scip_lp.h" 43 #include "scip/scip_mem.h" 44 #include "scip/scip_message.h" 45 #include "scip/scip_numerics.h" 46 #include "scip/scip_param.h" 47 #include "scip/scip_prob.h" 48 #include "scip/scip_solvingstats.h" 49 #include "scip/scip_tree.h" 50 #include "scip/scip_var.h" 51 #include <string.h> 52 53 54 #define BRANCHRULE_NAME "fullstrong" 55 #define BRANCHRULE_DESC "full strong branching" 56 #define BRANCHRULE_PRIORITY 0 57 #define BRANCHRULE_MAXDEPTH -1 58 #define BRANCHRULE_MAXBOUNDDIST 1.0 59 60 #define DEFAULT_REEVALAGE 10LL /**< number of intermediate LPs solved to trigger reevaluation of strong branching 61 * value for a variable that was already evaluated at the current node */ 62 #define DEFAULT_MAXPROPROUNDS -2 /**< maximum number of propagation rounds to be performed during strong branching 63 * before solving the LP (-1: no limit, -2: parameter settings) */ 64 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during strong 65 * branching (only with propagation)? */ 66 #define DEFAULT_FORCESTRONGBRANCH FALSE /**< should strong branching be applied even if there is just a single candidate? */ 67 68 69 /** branching rule data */ 70 struct SCIP_BranchruleData 71 { 72 SCIP_Longint reevalage; /**< number of intermediate LPs solved to trigger reevaluation of strong branching 73 * value for a variable that was already evaluated at the current node */ 74 int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching 75 * before solving the LP (-1: no limit, -2: parameter settings) */ 76 SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong 77 * branching (only with propagation)? */ 78 SCIP_Bool forcestrongbranch; /**< should strong branching be applied even if there is just a single candidate? */ 79 int lastcand; /**< last evaluated candidate of last branching rule execution */ 80 int skipsize; /**< size of skipdown and skipup array */ 81 SCIP_Bool* skipdown; /**< should be branching on down child be skipped? */ 82 SCIP_Bool* skipup; /**< should be branching on up child be skipped? */ 83 }; 84 85 86 /* 87 * Callback methods 88 */ 89 90 /** copy method for branchrule plugins (called when SCIP copies plugins) */ 91 static 92 SCIP_DECL_BRANCHCOPY(branchCopyFullstrong) 93 { /*lint --e{715}*/ 94 assert(scip != NULL); 95 assert(branchrule != NULL); 96 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 97 98 /* call inclusion method of branchrule */ 99 SCIP_CALL( SCIPincludeBranchruleFullstrong(scip) ); 100 101 return SCIP_OKAY; 102 } 103 104 /** destructor of branching rule to free user data (called when SCIP is exiting) */ 105 static 106 SCIP_DECL_BRANCHFREE(branchFreeFullstrong) 107 { /*lint --e{715}*/ 108 SCIP_BRANCHRULEDATA* branchruledata; 109 110 /* free branching rule data */ 111 branchruledata = SCIPbranchruleGetData(branchrule); 112 assert(branchruledata != NULL); 113 114 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize); 115 SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize); 116 117 SCIPfreeBlockMemory(scip, &branchruledata); 118 SCIPbranchruleSetData(branchrule, NULL); 119 120 return SCIP_OKAY; 121 } 122 123 124 /** initialization method of branching rule (called after problem was transformed) */ 125 static 126 SCIP_DECL_BRANCHINIT(branchInitFullstrong) 127 { /*lint --e{715}*/ 128 SCIP_BRANCHRULEDATA* branchruledata; 129 130 /* initialize branching rule data */ 131 branchruledata = SCIPbranchruleGetData(branchrule); 132 assert(branchruledata != NULL); 133 134 branchruledata->lastcand = 0; 135 136 return SCIP_OKAY; 137 } 138 139 /** deinitialization method of branching rule (called before transformed problem is freed) */ 140 static 141 SCIP_DECL_BRANCHEXIT(branchExitFullstrong) 142 { /*lint --e{715}*/ 143 SCIP_BRANCHRULEDATA* branchruledata; 144 145 /* initialize branching rule data */ 146 branchruledata = SCIPbranchruleGetData(branchrule); 147 assert(branchruledata != NULL); 148 assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL)); 149 150 if( branchruledata->skipdown != NULL ) 151 { 152 SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize); 153 SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize); 154 branchruledata->skipdown = NULL; 155 branchruledata->skipup = NULL; 156 branchruledata->skipsize = 0; 157 } 158 159 return SCIP_OKAY; 160 } 161 162 /** 163 * Selects a variable from a set of candidates by strong branching 164 * 165 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 166 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 167 * 168 * @note The variables in the lpcands array must have a fractional value in the current LP solution 169 */ 170 SCIP_RETCODE SCIPselectVarStrongBranching( 171 SCIP* scip, /**< original SCIP data structure */ 172 SCIP_VAR** lpcands, /**< branching candidates */ 173 SCIP_Real* lpcandssol, /**< solution values of the branching candidates */ 174 SCIP_Real* lpcandsfrac, /**< fractional values of the branching candidates */ 175 SCIP_Bool* skipdown, /**< should down branchings be skipped? */ 176 SCIP_Bool* skipup, /**< should up branchings be skipped? */ 177 int nlpcands, /**< number of branching candidates */ 178 int npriolpcands, /**< number of priority branching candidates */ 179 int ncomplete, /**< number of branching candidates without skip */ 180 int* start, /**< starting index in lpcands */ 181 int maxproprounds, /**< maximum number of propagation rounds to be performed during strong 182 * branching before solving the LP (-1: no limit, -2: parameter settings) */ 183 SCIP_Bool probingbounds, /**< should valid bounds be identified in a probing-like fashion during 184 * strong branching (only with propagation)? */ 185 SCIP_Bool forcestrongbranch, /**< should strong branching be applied even if there is just a single candidate? */ 186 int* bestcand, /**< best candidate for branching */ 187 SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */ 188 SCIP_Real* bestup, /**< objective value of the up branch for bestcand */ 189 SCIP_Real* bestscore, /**< score for bestcand */ 190 SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */ 191 SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */ 192 SCIP_Real* provedbound, /**< proved dual bound for current subtree */ 193 SCIP_RESULT* result /**< result pointer */ 194 ) 195 { /*lint --e{715}*/ 196 SCIP_VAR** vars = NULL; 197 SCIP_Real* newlbs = NULL; 198 SCIP_Real* newubs = NULL; 199 SCIP_BRANCHRULE* branchrule; 200 SCIP_BRANCHRULEDATA* branchruledata; 201 SCIP_Longint reevalage; 202 SCIP_Longint nodenum; 203 SCIP_Real down; 204 SCIP_Real up; 205 SCIP_Real downgain; 206 SCIP_Real upgain; 207 SCIP_Real score; 208 SCIP_Real lpobjval; 209 SCIP_Bool exactsolve; 210 SCIP_Bool lperror; 211 SCIP_Bool allcolsinlp; 212 SCIP_Bool downvalid; 213 SCIP_Bool upvalid; 214 SCIP_Bool downinf; 215 SCIP_Bool upinf; 216 SCIP_Bool downconflict; 217 SCIP_Bool upconflict; 218 SCIP_Bool bothgains; 219 SCIP_Bool propagate; 220 int nvars = 0; 221 int nsbcalls; 222 int i; 223 int c; 224 225 assert(scip != NULL); 226 assert(lpcands != NULL); 227 assert(lpcandssol != NULL); 228 assert(lpcandsfrac != NULL); 229 assert(bestcand != NULL); 230 assert(skipdown != NULL); 231 assert(skipup != NULL); 232 assert(bestdown != NULL); 233 assert(bestup != NULL); 234 assert(bestscore != NULL); 235 assert(bestdownvalid != NULL); 236 assert(bestupvalid != NULL); 237 assert(provedbound != NULL); 238 assert(result != NULL); 239 assert(nlpcands > 0); 240 241 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful 242 * for cutting off sub problems and improving lower bounds of children 243 */ 244 exactsolve = SCIPisExactSolve(scip); 245 246 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */ 247 allcolsinlp = SCIPallColsInLP(scip); 248 249 /* get current node number */ 250 nodenum = SCIPgetNNodes(scip); 251 252 /* get current LP objective bound of the local sub problem and global cutoff bound */ 253 lpobjval = SCIPgetLPObjval(scip); 254 *provedbound = lpobjval; 255 256 *bestcand = 0; 257 *bestdown = lpobjval; 258 *bestup = lpobjval; 259 *bestdownvalid = TRUE; 260 *bestupvalid = TRUE; 261 *bestscore = -SCIPinfinity(scip); 262 263 /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be 264 * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately 265 */ 266 if( (!forcestrongbranch && nlpcands == 1) || SCIPisStopped(scip) ) 267 return SCIP_OKAY; 268 269 /* this assert may not hold if SCIP is stopped, thus we only check it here */ 270 assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL); 271 272 /* get branching rule */ 273 branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME); 274 assert(branchrule != NULL); 275 276 /* get branching rule data */ 277 branchruledata = SCIPbranchruleGetData(branchrule); 278 assert(branchruledata != NULL); 279 280 /* auto-setting for reevalage */ 281 reevalage = branchruledata->reevalage; 282 283 /* check whether propagation should be performed */ 284 propagate = (maxproprounds != 0); 285 286 /* if we don't do propagation, we cannot identify valid bounds in a probing-like fashion */ 287 if( !propagate && maxproprounds > -3 ) 288 probingbounds = FALSE; 289 290 /* create arrays for probing-like bound tightening */ 291 if( probingbounds ) 292 { 293 vars = SCIPgetVars(scip); 294 nvars = SCIPgetNVars(scip); 295 296 SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) ); 297 SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) ); 298 } 299 300 /* initialize strong branching */ 301 SCIP_CALL( SCIPstartStrongbranch(scip, propagate) ); 302 303 /* search the full strong candidate 304 * cycle through the candidates, starting with the position evaluated in the last run 305 */ 306 nsbcalls = 0; 307 bothgains = TRUE; 308 for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c ) 309 { 310 c = c % nlpcands; 311 assert(lpcands[c] != NULL); 312 313 /* don't use strong branching on variables that have already been initialized at the current node, 314 * and that were evaluated not too long ago 315 */ 316 if( SCIPgetVarStrongbranchNode(scip, lpcands[c]) == nodenum 317 && SCIPgetVarStrongbranchLPAge(scip, lpcands[c]) < reevalage ) 318 { 319 SCIP_Real lastlpobjval; 320 321 /* use the score of the strong branching call at the current node */ 322 SCIP_CALL( SCIPgetVarStrongbranchLast(scip, lpcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) ); 323 downgain = MAX(down - lastlpobjval, 0.0); 324 upgain = MAX(up - lastlpobjval, 0.0); 325 downvalid = FALSE; 326 upvalid = FALSE; 327 downinf = FALSE; 328 upinf = FALSE; 329 downconflict = FALSE; 330 upconflict = FALSE; 331 lperror = FALSE; 332 SCIPdebugMsg(scip, "strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT ", down=%g (%+g), up=%g (%+g))\n", 333 SCIPvarGetName(lpcands[c]), SCIPgetVarStrongbranchLPAge(scip, lpcands[c]), down, downgain, up, upgain); 334 } 335 else 336 { 337 SCIPdebugMsg(scip, "applying strong branching%s on variable <%s> with solution %g\n", 338 propagate ? "with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]); 339 assert(i >= ncomplete || (!skipdown[i] && !skipup[i])); 340 341 /* apply strong branching */ 342 up = -SCIPinfinity(scip); 343 down = -SCIPinfinity(scip); 344 345 if( propagate ) 346 { 347 SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, lpcands[c], lpcandssol[c], lpobjval, INT_MAX, 348 maxproprounds, skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, 349 &upvalid, NULL, NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) ); 350 351 SCIPdebugMsg(scip, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n", 352 down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict); 353 } 354 else 355 { 356 SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, lpcands[c], INT_MAX, FALSE, 357 skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, 358 &downconflict, &upconflict, &lperror) ); 359 } 360 nsbcalls++; 361 362 /* display node information line */ 363 if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 ) 364 { 365 SCIP_CALL( SCIPprintDisplayLine(scip, NULL, SCIP_VERBLEVEL_HIGH, TRUE) ); 366 } 367 368 /* check for an error in strong branching */ 369 if( lperror ) 370 { 371 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, 372 "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call%s for variable <%s> with solution %g\n", 373 SCIPgetNNodes(scip), propagate ? " with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]); 374 break; 375 } 376 377 /* evaluate strong branching */ 378 down = MAX(down, lpobjval); 379 up = MAX(up, lpobjval); 380 downgain = down - lpobjval; 381 upgain = up - lpobjval; 382 if( !SCIPisFeasZero(scip,downgain) && !SCIPisFeasZero(scip,upgain) ) 383 bothgains = TRUE; 384 385 assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip))); 386 assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip))); 387 assert(downinf || !downconflict); 388 assert(upinf || !upconflict); 389 390 /* update pseudo cost values */ 391 if( !downinf && downvalid ) 392 { 393 SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 0.0-lpcandsfrac[c], downgain, 1.0) ); 394 } 395 if( !upinf && upvalid ) 396 { 397 SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 1.0-lpcandsfrac[c], upgain, 1.0) ); 398 } 399 400 /* check if there are infeasible roundings */ 401 if( downinf || upinf ) 402 { 403 /* if we didn't do propagation, we can only detect infeasibility if the LP is a valid relaxation */ 404 assert(allcolsinlp || propagate); 405 assert(!exactsolve); 406 407 if( downinf && upinf ) 408 { 409 /* both roundings are infeasible -> node is infeasible */ 410 *result = SCIP_CUTOFF; 411 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(lpcands[c])); 412 break; /* terminate initialization loop, because node is infeasible */ 413 } 414 else if( downinf ) 415 { 416 SCIP_Bool infeasible; 417 SCIP_Bool tightened; 418 419 /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */ 420 SCIP_CALL( SCIPtightenVarLb(scip, lpcands[c], SCIPfeasCeil(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) ); 421 assert(!infeasible); 422 423 /* if we did propagation, the bound change might already have been added */ 424 assert(tightened || propagate); 425 426 *result = SCIP_REDUCEDDOM; 427 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(lpcands[c])); 428 break; /* terminate initialization loop, because LP was changed */ 429 } 430 else 431 { 432 SCIP_Bool infeasible; 433 SCIP_Bool tightened; 434 435 /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */ 436 assert(upinf); 437 SCIP_CALL( SCIPtightenVarUb(scip, lpcands[c], SCIPfeasFloor(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) ); 438 assert(!infeasible); 439 440 /* if we did propagation, the bound change might already have been added */ 441 assert(tightened || propagate); 442 443 *result = SCIP_REDUCEDDOM; 444 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(lpcands[c])); 445 break; /* terminate initialization loop, because LP was changed */ 446 } 447 } 448 else if( allcolsinlp && !exactsolve && downvalid && upvalid ) 449 { 450 SCIP_Real minbound; 451 452 /* the minimal lower bound of both children is a proved lower bound of the current subtree */ 453 minbound = MIN(down, up); 454 *provedbound = MAX(*provedbound, minbound); 455 456 /* apply probing-like bounds detected during strong branching */ 457 if( probingbounds ) 458 { 459 int nboundchgs; 460 int v; 461 462 assert(vars != NULL); 463 assert(nvars > 0); 464 assert(newlbs != NULL); 465 assert(newubs != NULL); 466 467 nboundchgs = 0; 468 469 for( v = 0; v < nvars; ++v ) 470 { 471 if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) ) 472 { 473 SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n", 474 SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(lpcands[c])); 475 476 SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlbs[v]) ); 477 ++nboundchgs; 478 } 479 if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) ) 480 { 481 SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n", 482 SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(lpcands[c])); 483 484 SCIP_CALL( SCIPchgVarUb(scip, vars[v], newubs[v]) ); 485 ++nboundchgs; 486 } 487 } 488 489 if( nboundchgs > 0 ) 490 { 491 *result = SCIP_REDUCEDDOM; 492 SCIPdebugMsg(scip, " -> strong branching with propagation on variable <%s> led to %d bound changes\n", 493 SCIPvarGetName(lpcands[c]), nboundchgs); 494 break; /* terminate initialization loop, because LP was changed */ 495 } 496 } 497 } 498 } 499 500 /* check for a better score, if we are within the maximum priority candidates */ 501 if( c < npriolpcands ) 502 { 503 score = SCIPgetBranchScore(scip, lpcands[c], downgain, upgain); 504 if( score > *bestscore ) 505 { 506 *bestcand = c; 507 *bestdown = down; 508 *bestup = up; 509 *bestdownvalid = downvalid; 510 *bestupvalid = upvalid; 511 *bestscore = score; 512 } 513 } 514 else 515 { 516 SCIPdebug(score = 0.0;) 517 } 518 519 SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n", 520 c, nlpcands, npriolpcands, SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score, 521 SCIPvarGetName(lpcands[*bestcand]), *bestscore); 522 } 523 524 /* end strong branching */ 525 SCIP_CALL( SCIPendStrongbranch(scip) ); 526 527 *start = c; 528 529 if( probingbounds ) 530 { 531 assert(newlbs != NULL); 532 assert(newubs != NULL); 533 534 SCIPfreeBufferArray(scip, &newlbs); 535 SCIPfreeBufferArray(scip, &newubs); 536 } 537 538 return SCIP_OKAY; 539 } 540 541 /** branching execution method for fractional LP solutions */ 542 static 543 SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong) 544 { /*lint --e{715}*/ 545 SCIP_BRANCHRULEDATA* branchruledata; 546 SCIP_VAR** tmplpcands; 547 SCIP_VAR** lpcands; 548 SCIP_Real* tmplpcandssol; 549 SCIP_Real* lpcandssol; 550 SCIP_Real* tmplpcandsfrac; 551 SCIP_Real* lpcandsfrac; 552 SCIP_Real bestdown; 553 SCIP_Real bestup; 554 SCIP_Real bestscore; 555 SCIP_Real provedbound; 556 SCIP_Bool bestdownvalid; 557 SCIP_Bool bestupvalid; 558 int nlpcands; 559 int npriolpcands; 560 int bestcand; 561 562 assert(branchrule != NULL); 563 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 564 assert(scip != NULL); 565 assert(result != NULL); 566 567 SCIPdebugMsg(scip, "Execlp method of fullstrong branching\n"); 568 569 *result = SCIP_DIDNOTRUN; 570 571 /* get branching rule data */ 572 branchruledata = SCIPbranchruleGetData(branchrule); 573 assert(branchruledata != NULL); 574 575 /* get branching candidates */ 576 SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) ); 577 assert(nlpcands > 0); 578 assert(npriolpcands > 0); 579 580 /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP 581 * solution 582 */ 583 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) ); 584 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) ); 585 SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) ); 586 587 if( branchruledata->skipdown == NULL ) 588 { 589 assert(branchruledata->skipup == NULL); 590 591 branchruledata->skipsize = SCIPgetNVars(scip); 592 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) ); 593 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) ); 594 BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize); 595 BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize); 596 } 597 598 SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown, 599 branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand, 600 branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand, 601 &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) ); 602 603 if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED ) 604 { 605 SCIP_NODE* downchild; 606 SCIP_NODE* upchild; 607 SCIP_VAR* var; 608 SCIP_Real val; 609 SCIP_Bool allcolsinlp; 610 SCIP_Bool exactsolve; 611 612 assert(*result == SCIP_DIDNOTRUN); 613 assert(0 <= bestcand && bestcand < nlpcands); 614 assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip))); 615 616 var = lpcands[bestcand]; 617 val = lpcandssol[bestcand]; 618 619 /* perform the branching */ 620 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n", 621 nlpcands, bestcand, SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore); 622 SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) ); 623 assert(downchild != NULL); 624 assert(upchild != NULL); 625 626 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful 627 * for cutting off sub problems and improving lower bounds of children 628 */ 629 exactsolve = SCIPisExactSolve(scip); 630 631 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */ 632 allcolsinlp = SCIPallColsInLP(scip); 633 634 /* update the lower bounds in the children */ 635 if( allcolsinlp && !exactsolve ) 636 { 637 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) ); 638 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) ); 639 } 640 SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild)); 641 SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild)); 642 643 *result = SCIP_BRANCHED; 644 } 645 646 SCIPfreeBufferArray(scip, &lpcandsfrac); 647 SCIPfreeBufferArray(scip, &lpcandssol); 648 SCIPfreeBufferArray(scip, &lpcands); 649 650 return SCIP_OKAY; 651 } 652 653 654 /* 655 * branching specific interface methods 656 */ 657 658 /** creates the full strong LP branching rule and includes it in SCIP */ 659 SCIP_RETCODE SCIPincludeBranchruleFullstrong( 660 SCIP* scip /**< SCIP data structure */ 661 ) 662 { 663 SCIP_BRANCHRULEDATA* branchruledata; 664 SCIP_BRANCHRULE* branchrule; 665 666 /* create fullstrong branching rule data */ 667 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) ); 668 branchruledata->lastcand = 0; 669 branchruledata->skipsize = 0; 670 branchruledata->skipup = NULL; 671 branchruledata->skipdown = NULL; 672 673 /* include branching rule */ 674 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 675 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) ); 676 677 assert(branchrule != NULL); 678 679 /* set non-fundamental callbacks via specific setter functions*/ 680 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyFullstrong) ); 681 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeFullstrong) ); 682 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitFullstrong) ); 683 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitFullstrong) ); 684 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpFullstrong) ); 685 686 /* fullstrong branching rule parameters */ 687 SCIP_CALL( SCIPaddLongintParam(scip, 688 "branching/fullstrong/reevalage", 689 "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node", 690 &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 691 SCIP_CALL( SCIPaddIntParam(scip, 692 "branching/fullstrong/maxproprounds", 693 "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)", 694 &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -3, INT_MAX, NULL, NULL) ); 695 SCIP_CALL( SCIPaddBoolParam(scip, 696 "branching/fullstrong/probingbounds", 697 "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?", 698 &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) ); 699 SCIP_CALL( SCIPaddBoolParam(scip, 700 "branching/fullstrong/forcestrongbranch", 701 "should strong branching be applied even if there is just a single candidate?", 702 &branchruledata->forcestrongbranch, TRUE, DEFAULT_FORCESTRONGBRANCH, NULL, NULL) ); 703 704 return SCIP_OKAY; 705 } 706