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_lookahead.c 26 * @ingroup DEFPLUGINS_BRANCH 27 * @ingroup BRANCHINGRULES 28 * @brief lookahead LP branching rule 29 * @author Christoph Schubert 30 * @author Gerald Gamrath 31 * 32 * The (multi-level) lookahead branching rule applies strong branching to every fractional value of the LP solution 33 * at the current node of the branch-and-bound tree, as well as recursivly to every temporary child problem created by this 34 * strong branching. The rule selects the candidate with the best proven dual bound. 35 * 36 * The branching rule was motivated by the following technical report: 37 * 38 * @par 39 * Wasu Glankwamdee and Jeff Linderoth@n 40 * Lookahead Branching for Mixed Integer Programming@n 41 * Technical Report 06T-004, Department of Industrial and Systems Engineering, Lehigh University. 42 * 43 * For a more mathematical description and a comparison between lookahead branching and other branching rules 44 * in SCIP, we refer to 45 * 46 * @par 47 * Christoph Schubert@n 48 * Multi-Level Lookahead Branching@n 49 * Master Thesis, Technische Universität Berlin, 2017@n 50 */ 51 52 /* Supported defines: 53 * PRINTNODECONS: prints the binary constraints added 54 * SCIP_DEBUG: prints detailed execution information 55 * SCIP_STATISTIC: prints some statistics after the branching rule is freed */ 56 57 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 58 59 #include "blockmemshell/memory.h" 60 #include "lpi/lpi.h" 61 #include "scip/branch_lookahead.h" 62 #include "scip/cons_logicor.h" 63 #include "scip/pub_branch.h" 64 #include "scip/pub_message.h" 65 #include "scip/pub_misc.h" 66 #include "scip/pub_tree.h" 67 #include "scip/pub_var.h" 68 #include "scip/scip_branch.h" 69 #include "scip/scip_cons.h" 70 #include "scip/scip_general.h" 71 #include "scip/scip_lp.h" 72 #include "scip/scip_mem.h" 73 #include "scip/scip_message.h" 74 #include "scip/scip_numerics.h" 75 #include "scip/scip_param.h" 76 #include "scip/scip_prob.h" 77 #include "scip/scip_probing.h" 78 #include "scip/scip_sol.h" 79 #include "scip/scip_solvingstats.h" 80 #include "scip/scip_tree.h" 81 #include "scip/scip_var.h" 82 #include <string.h> 83 84 #define BRANCHRULE_NAME "lookahead" 85 #define BRANCHRULE_DESC "full strong branching over multiple levels" 86 #define BRANCHRULE_PRIORITY 0 87 #define BRANCHRULE_MAXDEPTH -1 88 #define BRANCHRULE_MAXBOUNDDIST 1.0 89 90 #define DEFAULT_USEBINARYCONSTRAINTS FALSE /**< should binary constraints be collected and applied? */ 91 #define DEFAULT_ADDCLIQUE FALSE /**< add binary constraints with two variables found at the root node also as a clique? */ 92 #define DEFAULT_ADDBINCONSROW 0 /**< should binary constraints be added as rows to the base LP? 93 * (0: no, 1: separate, 2: as initial rows) */ 94 #define DEFAULT_USEDOMAINREDUCTION TRUE /**< Should domain reductions be collected and applied? */ 95 #define DEFAULT_MERGEDOMAINREDUCTIONS FALSE /**< should domain reductions of feasible siblings should be merged? */ 96 #define DEFAULT_PREFERSIMPLEBOUNDS FALSE /**< should domain reductions only be applied if there are simple bound changes? */ 97 #define DEFAULT_ONLYVIOLDOMREDS FALSE /**< Should only domain reductions that violate the LP solution be applied? */ 98 #define DEFAULT_MAXNVIOLATEDCONS 1 /**< How many constraints that are violated by the base lp solution 99 * should be gathered until the rule is stopped and they are added? */ 100 #define DEFAULT_MAXNVIOLATEDBINCONS 0 /**< How many binary constraints that are violated by the base lp 101 * solution should be gathered until the rule is stopped and they are 102 * added? */ 103 #define DEFAULT_MAXNVIOLATEDDOMREDS 1 /**< How many domain reductions that are violated by the base lp solution 104 * should be gathered until the rule is stopped and they are added? */ 105 #define DEFAULT_STOREUNVIOLATEDSOL TRUE /**< If only non violating constraints are added, should the branching 106 * decision be stored till the next call? */ 107 #define DEFAULT_REEVALAGE 10LL /**< Max number of LPs solved after which a previous prob branching 108 * result is recalculated. */ 109 #define DEFAULT_REEVALAGEFSB 10LL /**< Max number of LPs solved after which a previous FSB scoring 110 * result is recalculated. */ 111 #define DEFAULT_RECURSIONDEPTH 2 /**< The max depth of LAB. */ 112 #define DEFAULT_ADDNONVIOCONS FALSE /**< Should binary constraints, that are not violated by the base LP, be 113 * collected and added? */ 114 #define DEFAULT_PROPAGATE TRUE /**< Should domain propagation be executed before each temporary node is 115 * solved? */ 116 #define DEFAULT_USELEVEL2DATA TRUE /**< should branching data generated at depth level 2 be stored for re-using it? */ 117 #define DEFAULT_APPLYCHILDBOUNDS FALSE /**< should bounds known for child nodes be applied? */ 118 #define DEFAULT_ENFORCEMAXDOMREDS FALSE /**< should the maximum number of domain reductions maxnviolateddomreds be enforced? */ 119 #define DEFAULT_UPDATEBRANCHINGRESULTS FALSE /**< should branching results (and scores) be updated w.r.t. proven dual bounds? */ 120 #define DEFAULT_MAXPROPROUNDS 0 /**< maximum number of propagation rounds to perform at temporary 121 * nodes (-1: unlimited, 0: SCIP default) */ 122 #define DEFAULT_ABBREVIATED TRUE /**< Toggles the abbreviated LAB. */ 123 #define DEFAULT_MAXNCANDS 4 /**< If abbreviated: The max number of candidates to consider at the base node */ 124 #define DEFAULT_MAXNDEEPERCANDS 2 /**< If abbreviated: The max number of candidates to consider per deeper node 125 * (0: same as base node) */ 126 #define DEFAULT_REUSEBASIS TRUE /**< If abbreviated: Should the information gathered to obtain the best 127 * candidates be reused? */ 128 #define DEFAULT_ABBREVPSEUDO FALSE /**< If abbreviated: Use pseudo costs to estimate the score of a 129 * candidate. */ 130 #define DEFAULT_LEVEL2AVGSCORE FALSE /**< should the average score be used for uninitialized scores in level 2? */ 131 #define DEFAULT_LEVEL2ZEROSCORE FALSE /**< should uninitialized scores be set to 0? */ 132 #define DEFAULT_SCORINGFUNCTION 'a' /**< scoring function to be used at the base level */ 133 #define DEFAULT_DEEPERSCORINGFUNCTION 'x' /**< scoring function to be used at deeper levels */ 134 #define DEFAULT_SCORINGSCORINGFUNCTION 'd' /**< scoring function to be used for FSB scoring */ 135 #define DEFAULT_MINWEIGHT 0.8 /**< default value for the weight of the minimum in the convex combination of two 136 * child gains (taken from the paper) */ 137 #define DEFAULT_WORSEFACTOR -1.0 /**< if the FSB score is of a candidate is worse than the best by this factor, skip this candidate (-1: disable) */ 138 #define DEFAULT_FILTERBYMAXGAIN FALSE /**< should lookahead branching only be applied if the max gain in level 1 is not uniquely that of the best candidate? */ 139 140 #ifdef SCIP_DEBUG 141 /* Adjusted debug message that also prints the current probing depth. */ 142 #define LABdebugMessage(scip,lvl,...) do \ 143 { \ 144 SCIP_STAGE stage; \ 145 SCIPverbMessage(scip, lvl, NULL, "[%s:%-4d] ", __FILE__, __LINE__); \ 146 stage = SCIPgetStage(scip); \ 147 if( stage == SCIP_STAGE_INIT ) \ 148 { \ 149 SCIPverbMessage(scip, lvl, NULL, "Init : "); \ 150 } \ 151 else if( stage == SCIP_STAGE_FREE ) \ 152 { \ 153 SCIPverbMessage(scip, lvl, NULL, "Free : "); \ 154 } \ 155 else if( SCIPinProbing(scip) ) \ 156 { \ 157 SCIPverbMessage(scip, lvl, NULL, "%*sDepth %i: ", \ 158 2 * SCIPgetProbingDepth(scip), "", SCIPgetProbingDepth(scip)); \ 159 } \ 160 else \ 161 { \ 162 SCIPverbMessage(scip, lvl, NULL, "Base : "); \ 163 } \ 164 SCIPverbMessage(scip, lvl, NULL, __VA_ARGS__); \ 165 } \ 166 while( FALSE ) 167 168 /* Writes a debug message without the leading information. Can be used to append something to an output of LABdebugMessage*/ 169 #define LABdebugMessagePrint(scip,lvl,...) do \ 170 { \ 171 SCIPverbMessage(scip, lvl, NULL, __VA_ARGS__); \ 172 } \ 173 while( FALSE ) 174 #else 175 #define LABdebugMessage(scip,lvl,...) /**/ 176 /*#define LABdebugMessagePrint(scip,lvl,...) only used with SCIP_DEBUG defined */ 177 #endif 178 179 /* 180 * Data structures 181 */ 182 183 /** A struct holding information to speed up the solving time for solving a problem again. This is filled by the FSB 184 * scoring routine that is run to get the best candidates. It is then read by the actual ALAB routine. */ 185 typedef struct 186 { 187 SCIP_LPISTATE* lpistate; /**< the basis information that may be set before another solve lp call */ 188 SCIP_LPINORMS* lpinorms; /**< the norms that may be set before another solve lp call */ 189 SCIP_Bool primalfeas; /**< indicates whether the solution was primal feasible */ 190 SCIP_Bool dualfeas; /**< indicates whether the solution was dual feasible */ 191 } WARMSTARTINFO; 192 193 /** Allocates the warm start information on the buffer and initializes it with default values. */ 194 static 195 SCIP_RETCODE warmStartInfoCreate( 196 SCIP* scip, /**< SCIP data structure */ 197 WARMSTARTINFO** warmstartinfo /**< the warmstartinfo to allocate and initialize */ 198 ) 199 { 200 assert(scip != NULL); 201 assert(warmstartinfo != NULL); 202 203 SCIP_CALL( SCIPallocBlockMemory(scip, warmstartinfo) ); 204 205 (*warmstartinfo)->lpistate = NULL; 206 (*warmstartinfo)->lpinorms = NULL; 207 (*warmstartinfo)->primalfeas = FALSE; 208 (*warmstartinfo)->dualfeas = FALSE; 209 210 return SCIP_OKAY; 211 } 212 213 /** checks that the warm start info can be read into the lp solver. */ 214 static 215 SCIP_Bool warmStartInfoIsAvailable( 216 WARMSTARTINFO* warmstartinfo /**< the warm start info to check (may be NULL) */ 217 ) 218 { 219 return warmstartinfo != NULL && warmstartinfo->lpistate != NULL; 220 } 221 222 /** Frees the allocated buffer memory of the warm start info. */ 223 static 224 SCIP_RETCODE warmStartInfoFree( 225 SCIP* scip, /**< SCIP data structure */ 226 WARMSTARTINFO** warmstartinfo /**< the warm start info to free */ 227 ) 228 { 229 SCIP_LPI* lpi; 230 BMS_BLKMEM* blkmem; 231 232 assert(scip != NULL); 233 assert(warmstartinfo != NULL); 234 235 SCIP_CALL( SCIPgetLPI(scip, &lpi) ); 236 blkmem = SCIPblkmem(scip); 237 238 if( (*warmstartinfo)->lpistate != NULL ) 239 { 240 SCIP_CALL( SCIPlpiFreeState(lpi, blkmem, &(*warmstartinfo)->lpistate) ); 241 } 242 243 if( (*warmstartinfo)->lpinorms != NULL ) 244 { 245 SCIP_CALL( SCIPlpiFreeNorms(lpi, blkmem, &(*warmstartinfo)->lpinorms) ); 246 } 247 248 SCIPfreeBlockMemory(scip, warmstartinfo); 249 250 return SCIP_OKAY; 251 } 252 253 /** A struct containing all information needed to branch on a variable. */ 254 typedef struct 255 { 256 SCIP_VAR* branchvar; /**< the variable to branch on */ 257 SCIP_Real branchval; /**< the fractional value to branch on */ 258 SCIP_Real fracval; /**< the fractional part of the value to branch on (val - floor(val)) */ 259 WARMSTARTINFO* downwarmstartinfo; /**< the warm start info containing the lp data from a previous down branch */ 260 WARMSTARTINFO* upwarmstartinfo; /**< the warm start info containing the lp data from a previous up branch */ 261 } CANDIDATE; 262 263 /** Allocates the candidate on the buffer and initializes it with default values. */ 264 static 265 SCIP_RETCODE candidateCreate( 266 SCIP* scip, /**< SCIP data structure */ 267 CANDIDATE** candidate /**< the candidate to allocate and initialize */ 268 ) 269 { 270 assert(scip != NULL); 271 assert(candidate != NULL); 272 273 SCIP_CALL( SCIPallocBlockMemory(scip, candidate) ); 274 275 (*candidate)->downwarmstartinfo = NULL; 276 (*candidate)->upwarmstartinfo = NULL; 277 (*candidate)->branchvar = NULL; 278 279 return SCIP_OKAY; 280 } 281 282 /** free the warm starting information for the given candidate */ 283 static 284 SCIP_RETCODE candidateFreeWarmStartInfo( 285 SCIP* scip, /**< SCIP data structure */ 286 CANDIDATE* candidate /**< the candidate to free the warm starting information for */ 287 ) 288 { 289 assert(scip != NULL); 290 assert(candidate != NULL); 291 292 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "freeing warmstart info of candidate <%s>(%u/%u)...\n", 293 SCIPvarGetName(candidate->branchvar), 294 candidate->upwarmstartinfo != NULL, candidate->downwarmstartinfo != NULL); 295 296 if( candidate->upwarmstartinfo != NULL ) 297 { 298 SCIP_CALL( warmStartInfoFree(scip, &candidate->upwarmstartinfo) ); 299 } 300 if( candidate->downwarmstartinfo != NULL ) 301 { 302 SCIP_CALL( warmStartInfoFree(scip, &candidate->downwarmstartinfo) ); 303 } 304 305 return SCIP_OKAY; 306 } 307 308 309 /** Frees the allocated buffer memory of the candidate and clears the contained lpi memories. */ 310 static 311 SCIP_RETCODE candidateFree( 312 SCIP* scip, /**< SCIP data structure */ 313 CANDIDATE** candidate /**< the candidate to free */ 314 ) 315 { 316 assert(scip != NULL); 317 assert(candidate != NULL); 318 319 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "freeing candidate <%s>(%u/%u)...\n", 320 (*candidate) != NULL ? SCIPvarGetName((*candidate)->branchvar) : "none", 321 (*candidate)->upwarmstartinfo != NULL, (*candidate)->downwarmstartinfo != NULL); 322 323 /* if a candidate is freed, we no longer need the content of the warm start info */ 324 SCIP_CALL( candidateFreeWarmStartInfo(scip, *candidate) ); 325 326 SCIPfreeBlockMemory(scip, candidate); 327 return SCIP_OKAY; 328 } 329 330 /** Store the current lp solution in the warm start info for further usage. */ 331 static 332 SCIP_RETCODE candidateStoreWarmStartInfo( 333 SCIP* scip, /**< SCIP data structure */ 334 CANDIDATE* candidate, /**< the branching candidate */ 335 SCIP_Bool down /**< is the info for down branching? */ 336 ) 337 { 338 SCIP_LPI* lpi; 339 BMS_BLKMEM* blkmem; 340 WARMSTARTINFO* warmstartinfo; 341 342 assert(scip != NULL); 343 assert(candidate != NULL); 344 345 SCIP_CALL( SCIPgetLPI(scip, &lpi) ); 346 blkmem = SCIPblkmem(scip); 347 348 if( down ) 349 { 350 if( candidate->downwarmstartinfo == NULL ) 351 { 352 SCIP_CALL( warmStartInfoCreate(scip, &candidate->downwarmstartinfo) ); 353 } 354 warmstartinfo = candidate->downwarmstartinfo; 355 } 356 else 357 { 358 if( candidate->upwarmstartinfo == NULL ) 359 { 360 SCIP_CALL( warmStartInfoCreate(scip, &candidate->upwarmstartinfo) ); 361 } 362 warmstartinfo = candidate->upwarmstartinfo; 363 } 364 365 SCIP_CALL( SCIPlpiGetState(lpi, blkmem, &warmstartinfo->lpistate) ); 366 367 SCIP_CALL( SCIPlpiGetNorms(lpi, blkmem, &warmstartinfo->lpinorms) ); 368 369 warmstartinfo->primalfeas = SCIPlpiIsPrimalFeasible(lpi); 370 warmstartinfo->dualfeas = SCIPlpiIsDualFeasible(lpi); 371 372 assert(warmstartinfo->lpistate != NULL); 373 /* warmstartinfo->lpinorms may be NULL */ 374 375 return SCIP_OKAY; 376 } 377 378 /** returns whether the candidate has stored warm starting information for the given direction */ 379 static 380 SCIP_Bool candidateHasWarmStartInfo( 381 CANDIDATE* candidate, /**< the branching candidate */ 382 SCIP_Bool down /**< is the info for down branching? */ 383 ) 384 { 385 assert(candidate != NULL); 386 387 return warmStartInfoIsAvailable(down ? candidate->downwarmstartinfo : candidate->upwarmstartinfo); 388 } 389 390 391 /** loads the warm starting information of the candidate for the given direction */ 392 static 393 SCIP_RETCODE candidateLoadWarmStartInfo( 394 SCIP* scip, /**< SCIP data structure */ 395 CANDIDATE* candidate, /**< the branching candidate */ 396 SCIP_Bool down /**< is the info for down branching? */ 397 ) 398 { 399 WARMSTARTINFO* warmstartinfo; 400 401 assert(scip != NULL); 402 assert(candidate != NULL); 403 404 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "loading basis...\n"); 405 406 if( down ) 407 warmstartinfo = candidate->downwarmstartinfo; 408 else 409 warmstartinfo = candidate->upwarmstartinfo; 410 411 /* As we solved the very same LP some time earlier and stored the state (the basis) and the norms, we can now set those in 412 * the LP solver, such that the solution does not (in best case) need any further calculation. 413 * Some iterations may occur, as the conflict analysis may have added some constraints in the meantime. */ 414 SCIP_CALL( SCIPsetProbingLPState(scip, &(warmstartinfo->lpistate), &(warmstartinfo->lpinorms), warmstartinfo->primalfeas, 415 warmstartinfo->dualfeas) ); 416 417 /* The state and norms will be freed later by the SCIP framework. Therefore they are set to NULL to enforce that we won't 418 * free them on our own. */ 419 assert(warmstartinfo->lpistate == NULL); 420 assert(warmstartinfo->lpinorms == NULL); 421 422 return SCIP_OKAY; 423 } 424 425 426 /** Holds the information needed for branching on a variable. */ 427 typedef struct 428 { 429 SCIP_VAR* branchvar; /**< the variable to branch on, may be NULL */ 430 SCIP_Real branchval; /**< the fractional value to branch on */ 431 SCIP_Real* downlowerbounds; /**< variable lower bounds for down child */ 432 SCIP_Real* downupperbounds; /**< variable upper bounds for down child */ 433 SCIP_Real* uplowerbounds; /**< variable lower bounds for up child */ 434 SCIP_Real* upupperbounds; /**< variable upper bounds for up child */ 435 SCIP_Real downdb; /**< dual bound for down branch */ 436 SCIP_Real updb; /**< dual bound for the up branch */ 437 SCIP_Real proveddb; /**< proven dual bound for the current node */ 438 SCIP_Real score; /**< score of the branching decision */ 439 SCIP_Bool downdbvalid; /**< Indicator for the validity of the downdb value. Is FALSE, if no actual 440 * branching occurred or the value was determined by an LP not solved to 441 * optimality. */ 442 SCIP_Bool updbvalid; /**< Indicator for the validity of the updb value. Is FALSE, if no actual 443 * branching occurred or the value was determined by an LP not solved to 444 * optimality. */ 445 SCIP_Bool boundsvalid; /**< are variable bounds for down and up child valid? */ 446 int boundssize; /**< size of bounds arrays */ 447 } BRANCHINGDECISION; 448 449 /** initialize a branching decsion with default values */ 450 static 451 void branchingDecisionInit( 452 SCIP* scip, /**< SCIP data structure */ 453 BRANCHINGDECISION* decision /**< the decision to initialize */ 454 ) 455 { 456 assert(scip != NULL); 457 assert(decision != NULL); 458 459 decision->branchvar = NULL; 460 decision->branchval = SCIP_INVALID; 461 decision->downlowerbounds = NULL; 462 decision->downupperbounds = NULL; 463 decision->uplowerbounds = NULL; 464 decision->upupperbounds = NULL; 465 decision->downdb = -SCIPinfinity(scip); 466 decision->downdbvalid = FALSE; 467 decision->updb = -SCIPinfinity(scip); 468 decision->updbvalid = FALSE; 469 decision->boundsvalid = FALSE; 470 decision->proveddb = -SCIPinfinity(scip); 471 decision->score = -SCIPinfinity(scip); 472 decision->boundssize = 0; 473 } 474 475 476 /** allocates a branching decision in the buffer and initializes it with default values. */ 477 static 478 SCIP_RETCODE branchingDecisionCreate( 479 SCIP* scip, /**< SCIP data structure */ 480 BRANCHINGDECISION** decision /**< pointer to the decision to allocate and initialize */ 481 ) 482 { 483 assert(scip != NULL); 484 assert(decision != NULL); 485 486 SCIP_CALL( SCIPallocBuffer(scip, decision) ); 487 488 branchingDecisionInit(scip, *decision); 489 490 return SCIP_OKAY; 491 } 492 493 /** copies the data from the source branching decision storage to the target storage; 494 * this is used to store the most important information (i.e., the dual bounds obtained) so that it can be used in a 495 * subsequent call in case the LP solution did not change because we only added bound changes that did not forbid the 496 * current LP solution; 497 * however, we do not want to store all the domain changes for the two potential child nodes for this rare case, they 498 * will be identified when processing the child nodes anyway 499 */ 500 static 501 void branchingDecisionCopy( 502 BRANCHINGDECISION* sourcedecision, /**< the source branching decision */ 503 BRANCHINGDECISION* targetdecision /**< the target branching decision */ 504 ) 505 { 506 assert(sourcedecision != NULL); 507 assert(targetdecision != NULL); 508 509 targetdecision->branchvar = sourcedecision->branchvar; 510 targetdecision->branchval = sourcedecision->branchval; 511 targetdecision->downdb = sourcedecision->downdb; 512 targetdecision->downdbvalid = sourcedecision->downdbvalid; 513 targetdecision->updb = sourcedecision->updb; 514 targetdecision->updbvalid = sourcedecision->updbvalid; 515 targetdecision->proveddb = sourcedecision->proveddb; 516 targetdecision->score = sourcedecision->score; 517 518 assert(targetdecision->downlowerbounds == NULL); 519 assert(targetdecision->downupperbounds == NULL); 520 assert(targetdecision->uplowerbounds == NULL); 521 assert(targetdecision->upupperbounds == NULL); 522 assert(targetdecision->boundsvalid == FALSE); 523 assert(targetdecision->boundssize == 0); 524 } 525 526 /** Checks whether the given branching decision can be used to branch on. */ 527 static 528 SCIP_Bool branchingDecisionIsValid( 529 BRANCHINGDECISION* decision /**< the branching decision to check */ 530 ) 531 { 532 assert(decision != NULL); 533 534 /* a branching decision is deemed valid, if the var pointer is not on the default NULL value (see the allocate method) */ 535 return decision->branchvar != NULL; 536 } 537 538 /* ensure that the array that stores the bounds for both child nodes is large enough */ 539 static 540 SCIP_RETCODE branchingDecisionEnsureBoundArraysSize( 541 SCIP* scip, /**< SCIP data structure */ 542 BRANCHINGDECISION* decision, /**< branching decision */ 543 int nvars /**< number of problem variables */ 544 ) 545 { 546 assert(decision != NULL); 547 548 if( decision->boundssize == 0 ) 549 { 550 decision->boundssize = nvars; 551 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->downlowerbounds, decision->boundssize) ); 552 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->downupperbounds, decision->boundssize) ); 553 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->uplowerbounds, decision->boundssize) ); 554 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->upupperbounds, decision->boundssize) ); 555 } 556 assert(decision->boundssize == nvars); 557 558 return SCIP_OKAY; 559 } 560 561 /** Frees the allocated memory of the branching decision. */ 562 static 563 void branchingDecisionFree( 564 SCIP* scip, /**< SCIP data structure */ 565 BRANCHINGDECISION** decision /**< pointer to the decision to be freed */ 566 ) 567 { 568 assert(scip != NULL); 569 assert(decision != NULL); 570 571 if( (*decision)->boundssize != 0 ) 572 { 573 assert((*decision)->downlowerbounds != NULL); 574 assert((*decision)->downupperbounds != NULL); 575 assert((*decision)->uplowerbounds != NULL); 576 assert((*decision)->upupperbounds != NULL); 577 578 SCIPfreeBlockMemoryArray(scip, &(*decision)->downlowerbounds, (*decision)->boundssize); 579 SCIPfreeBlockMemoryArray(scip, &(*decision)->downupperbounds, (*decision)->boundssize); 580 SCIPfreeBlockMemoryArray(scip, &(*decision)->uplowerbounds, (*decision)->boundssize); 581 SCIPfreeBlockMemoryArray(scip, &(*decision)->upupperbounds, (*decision)->boundssize); 582 } 583 584 SCIPfreeBuffer(scip, decision); 585 } 586 587 /** A container to hold the result of a branching. */ 588 typedef struct 589 { 590 SCIP_Real objval; /**< The objective value of the solved lp. Only contains meaningful data, if 591 * cutoff == FALSE. */ 592 SCIP_Real dualbound; /**< The best dual bound for this branching, may be changed by deeper level 593 * branchings. */ 594 SCIP_Longint niterations; /**< The number of probing iterations needed in sub branch. */ 595 SCIP_Bool cutoff; /**< Indicates whether the node was infeasible and was cutoff. */ 596 SCIP_Bool dualboundvalid; /**< Is the value of the dual bound valid? That means, was the according LP 597 * or the sub problems solved to optimality? */ 598 int ndeepestcutoffs; /**< number of cutoffs on the lowest level below this child */ 599 SCIP_Real deeperscore; /**< best score computed for the deeper lookahead level */ 600 SCIP_Real bestgain; /**< best gain (w.r.t. to the base lp) on the lowest level below this child */ 601 SCIP_Real totalgains; /**< sum over all gains that are valid in both children */ 602 int ntotalgains; /**< number of gains summed in totalgains */ 603 int ndeepestnodes; /**< number of nodes processed in the deepest level */ 604 } BRANCHINGRESULTDATA; 605 606 /** Allocates a branching result in the buffer. */ 607 static 608 SCIP_RETCODE branchingResultDataCreate( 609 SCIP* scip, /**< SCIP data structure */ 610 BRANCHINGRESULTDATA** resultdata /**< pointer to the result to be allocated */ 611 ) 612 { 613 assert(scip != NULL); 614 assert(resultdata != NULL); 615 616 SCIP_CALL( SCIPallocBuffer(scip, resultdata) ); 617 618 return SCIP_OKAY; 619 } 620 621 /** Initiates the branching result with default values. */ 622 static 623 void branchingResultDataInit( 624 SCIP* scip, /**< SCIP data structure */ 625 BRANCHINGRESULTDATA* resultdata /**< pointer to the result to be initialized */ 626 ) 627 { 628 assert(scip != NULL); 629 assert(resultdata != NULL); 630 631 resultdata->objval = -SCIPinfinity(scip); 632 resultdata->dualbound = -SCIPinfinity(scip); 633 resultdata->cutoff = FALSE; 634 resultdata->dualboundvalid = FALSE; 635 resultdata->niterations = 0; 636 resultdata->ndeepestcutoffs = 0; 637 resultdata->deeperscore = -SCIPinfinity(scip); 638 resultdata->bestgain = 0.; 639 resultdata->totalgains = 0.; 640 resultdata->ntotalgains = 0; 641 resultdata->ndeepestnodes = 0; 642 } 643 644 /** Copies the data from the source to the target. */ 645 static 646 void branchingResultDataCopy( 647 BRANCHINGRESULTDATA* sourcedata, /**< the source branching result */ 648 BRANCHINGRESULTDATA* targetdata /**< the target branching result */ 649 ) 650 { 651 assert(sourcedata != NULL); 652 assert(targetdata != NULL); 653 654 targetdata->cutoff = sourcedata->cutoff; 655 targetdata->objval = sourcedata->objval; 656 targetdata->dualbound = sourcedata->dualbound; 657 targetdata->dualboundvalid = sourcedata->dualboundvalid; 658 targetdata->niterations = sourcedata->niterations; 659 targetdata->ndeepestcutoffs = sourcedata->ndeepestcutoffs; 660 targetdata->deeperscore = sourcedata->deeperscore; 661 targetdata->bestgain = sourcedata->bestgain; 662 targetdata->totalgains = sourcedata->totalgains; 663 targetdata->ntotalgains = sourcedata->ntotalgains; 664 targetdata->ndeepestnodes = sourcedata->ndeepestnodes; 665 } 666 667 /** Frees the allocated buffer memory of the branching result. */ 668 static 669 void branchingResultDataFree( 670 SCIP* scip, /**< SCIP data structure */ 671 BRANCHINGRESULTDATA** resultdata /**< pointer to the result to be freed */ 672 ) 673 { 674 assert(scip != NULL); 675 assert(resultdata != NULL); 676 677 SCIPfreeBuffer(scip, resultdata); 678 } 679 680 /** a container to hold the result of a second-level LP */ 681 typedef struct 682 { 683 SCIP_Real lpobjval; /**< the objective value of the solved lp; only contains meaningful data, if 684 * cutoff == FALSE. */ 685 SCIP_Real branchval1; /**< new bound for first branching variable */ 686 SCIP_Real branchval2; /**< new bound for second branching variable */ 687 unsigned int branchvar1:30; /**< problem index of first branching variable */ 688 unsigned int branchvar2:30; /**< problem index of second branching variable */ 689 unsigned int branchdir1:1; /**< branching direction for first branching variable (0:down, 1:up) */ 690 unsigned int branchdir2:1; /**< branching direction for second branching variable (0:down, 1:up) */ 691 unsigned int cutoff:1; /**< indicates whether the node was infeasible and was cut off. */ 692 unsigned int valid:1; /**< is the lpobjval a valid dual bound? */ 693 } LEVEL2RESULT; 694 695 /** a container to hold the results of all second-level LPs */ 696 typedef struct 697 { 698 LEVEL2RESULT** level2results; /**< array with all level2 results */ 699 SCIP_Real branchval1; /**< new bound for first branching variable */ 700 SCIP_Real branchval2; /**< new bound for second branching variable */ 701 int nlevel2results; /**< number of level2 results stored */ 702 int level2resultssize; /**< size of level2results array */ 703 unsigned int branchvar1:30; /**< problem index of first branching variable */ 704 unsigned int branchvar2:30; /**< problem index of second branching variable */ 705 unsigned int branchdir1:1; /**< branching direction for first branching variable (0:down, 1:up) */ 706 unsigned int branchdir2:1; /**< branching direction for second branching variable (0:down, 1:up) */ 707 } LEVEL2DATA; 708 709 /** allocates a double branching result in the memory and fills it with the information stored in the level 2 data */ 710 static 711 SCIP_RETCODE level2resultCreateFromData( 712 SCIP* scip, /**< SCIP data structure */ 713 LEVEL2DATA* data, /**< level2 data */ 714 LEVEL2RESULT** result /**< pointer to the result to be allocated */ 715 ) 716 { 717 assert(scip != NULL); 718 assert(data != NULL); 719 assert(result != NULL); 720 721 SCIP_CALL( SCIPallocBlockMemory(scip, result) ); 722 723 if( data->branchvar1 < data->branchvar2 ) 724 { 725 (*result)->branchval1 = data->branchval1; 726 (*result)->branchval2 = data->branchval2; 727 (*result)->branchvar1 = data->branchvar1; /*lint !e732*/ 728 (*result)->branchvar2 = data->branchvar2; /*lint !e732*/ 729 (*result)->branchdir1 = data->branchdir1; 730 (*result)->branchdir2 = data->branchdir2; 731 } 732 else 733 { 734 (*result)->branchval1 = data->branchval2; 735 (*result)->branchval2 = data->branchval1; 736 (*result)->branchvar1 = data->branchvar2; /*lint !e732*/ 737 (*result)->branchvar2 = data->branchvar1; /*lint !e732*/ 738 (*result)->branchdir1 = data->branchdir2; 739 (*result)->branchdir2 = data->branchdir1; 740 } 741 742 return SCIP_OKAY; 743 } 744 745 746 #ifdef SCIP_DEBUG 747 /** prints the double branching result */ 748 static 749 void level2resultPrint( 750 SCIP* scip, /**< SCIP data structure */ 751 LEVEL2RESULT* result /**< pointer to the result to be initialized */ 752 ) 753 { 754 SCIP_VAR** vars; 755 756 assert(result != NULL); 757 758 vars = SCIPgetVars(scip); 759 760 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, 761 "level 2 result: <%s> %s %g + <%s> %s %g: lpval: %.9g, inf: %d, valid: %d\n", 762 SCIPvarGetName(vars[result->branchvar1]), result->branchdir1 ? ">=" : "<=", result->branchval1, 763 SCIPvarGetName(vars[result->branchvar2]), result->branchdir2 ? ">=" : "<=", result->branchval2, 764 result->lpobjval, result->cutoff, result->valid); 765 } 766 #else 767 #define level2resultPrint(scip,result) /**/ 768 #endif 769 770 /** frees the allocated memory of the double branching result */ 771 static 772 void level2resultFree( 773 SCIP* scip, /**< SCIP data structure */ 774 LEVEL2RESULT** result /**< pointer to the result to be freed */ 775 ) 776 { 777 assert(scip != NULL); 778 assert(result != NULL); 779 780 SCIPfreeBlockMemory(scip, result); 781 } 782 783 /** returns TRUE iff both level 2 results are equal; two branchings are equal if they branched on the same variables 784 * with the same values 785 */ 786 static 787 SCIP_Bool level2resultEqual( 788 LEVEL2RESULT* result1, /**< first level 2 result */ 789 LEVEL2RESULT* result2 /**< second level 2 result */ 790 ) 791 { 792 assert(result1->branchvar1 < result1->branchvar2); 793 assert(result2->branchvar1 < result2->branchvar2); 794 795 /* check all cases */ 796 if( result1->branchvar1 != result2->branchvar1 797 || result1->branchvar2 != result2->branchvar2 798 || result1->branchdir1 != result2->branchdir1 799 || result1->branchdir2 != result2->branchdir2 800 || result1->branchval1 > result2->branchval1 + 0.5 801 || result1->branchval1 < result2->branchval1 - 0.5 802 || result1->branchval2 > result2->branchval2 + 0.5 803 || result1->branchval2 < result2->branchval2 - 0.5) 804 return FALSE; 805 806 return TRUE; 807 } 808 809 /** allocates the level2 data */ 810 static 811 SCIP_RETCODE level2dataCreate( 812 SCIP* scip, /**< SCIP data structure */ 813 LEVEL2DATA** data /**< pointer to the data to be allocated */ 814 ) 815 { 816 assert(scip != NULL); 817 assert(data != NULL); 818 819 SCIP_CALL( SCIPallocBlockMemory(scip, data) ); 820 821 (*data)->level2results = NULL; 822 (*data)->branchval1 = -SCIPinfinity(scip); 823 (*data)->branchval2 = -SCIPinfinity(scip); 824 (*data)->nlevel2results = 0; 825 (*data)->level2resultssize = 0; 826 (*data)->branchvar1 = 0; 827 (*data)->branchvar2 = 0; 828 (*data)->branchdir1 = 0; 829 (*data)->branchdir2 = 0; 830 831 return SCIP_OKAY; 832 } 833 834 /** frees the allocated memory of the level2 data */ 835 static 836 void level2dataFree( 837 SCIP* scip, /**< SCIP data structure */ 838 LEVEL2DATA** data /**< pointer to the data to be freed */ 839 ) 840 { 841 assert(scip != NULL); 842 assert(data != NULL); 843 844 while( (*data)->nlevel2results > 0 ) 845 { 846 --(*data)->nlevel2results; 847 level2resultFree(scip, &((*data)->level2results[(*data)->nlevel2results])); 848 } 849 assert((*data)->nlevel2results == 0); 850 851 if( (*data)->level2results != NULL ) 852 { 853 SCIPfreeBlockMemoryArray(scip, &(*data)->level2results, (*data)->level2resultssize); 854 } 855 856 SCIPfreeBlockMemory(scip, data); 857 } 858 859 /** ensures that level2results can store at least one more element */ 860 static 861 SCIP_RETCODE level2dataEnsureSize( 862 SCIP* scip, /**< SCIP data structure */ 863 LEVEL2DATA* data /**< level2 data */ 864 ) 865 { 866 assert(scip != NULL); 867 assert(data != NULL); 868 869 if( data->nlevel2results >= data->level2resultssize ) 870 { 871 int newsize = SCIPcalcMemGrowSize(scip, data->level2resultssize + 1); 872 873 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->level2results, data->level2resultssize, newsize) ); 874 data->level2resultssize = newsize; 875 } 876 877 return SCIP_OKAY; 878 } 879 880 /** get a result from the level 2 data */ 881 static 882 SCIP_RETCODE level2dataGetResult( 883 SCIP* scip, /**< SCIP data structure */ 884 LEVEL2DATA* data, /**< level2 data */ 885 LEVEL2RESULT** result /**< pointer to store result */ 886 ) 887 { 888 LEVEL2RESULT* tmpresult; 889 int i; 890 891 assert(data != NULL); 892 assert(result != NULL); 893 894 *result = NULL; 895 896 /* we branched twice on the same variable; the result cannot be stored already */ 897 if( data->branchvar1 == data->branchvar2 ) 898 { 899 assert(SCIPvarGetType(SCIPgetVars(scip)[data->branchvar1]) != SCIP_VARTYPE_BINARY); 900 return SCIP_OKAY; 901 } 902 903 SCIP_CALL( level2resultCreateFromData(scip, data, &tmpresult) ); 904 905 /* search for a level 2 result with the same branching decisions */ 906 for( i = 0; i < data->nlevel2results; ++i ) 907 { 908 if( level2resultEqual(data->level2results[i], tmpresult) ) 909 { 910 *result = data->level2results[i]; 911 } 912 } 913 914 level2resultFree(scip, &tmpresult); 915 916 return SCIP_OKAY; 917 } 918 919 920 /** store a new result in the level 2 data */ 921 static 922 SCIP_RETCODE level2dataStoreResult( 923 SCIP* scip, /**< SCIP data structure */ 924 LEVEL2DATA* data, /**< level2 data */ 925 SCIP_Real lpobjval, /**< LP objective value */ 926 SCIP_Bool cutoff, /**< was the LP infeasible? */ 927 SCIP_Bool valid, /**< is the LP value a valid dual bound? */ 928 SCIP_Bool* duplicate /**< pointer to store whether information for the same branching decisions was already stored */ 929 ) 930 { 931 LEVEL2RESULT* result; 932 int i; 933 934 assert(scip != NULL); 935 assert(data != NULL); 936 assert(duplicate != NULL); 937 938 *duplicate = FALSE; 939 940 /* we branched twice on the same variable; the result cannot be re-used lated */ 941 if( data->branchvar1 == data->branchvar2 ) 942 { 943 assert(SCIPvarGetType(SCIPgetVars(scip)[data->branchvar1]) != SCIP_VARTYPE_BINARY); 944 return SCIP_OKAY; 945 } 946 947 SCIP_CALL( level2dataEnsureSize(scip, data) ); 948 949 SCIP_CALL( level2resultCreateFromData(scip, data, &result) ); 950 951 result->lpobjval = lpobjval; 952 result->cutoff = cutoff; 953 result->valid = valid; 954 955 /* search for a level 2 result with the same branching decisions*/ 956 for( i = 0; i < data->nlevel2results; ++i ) 957 { 958 if( level2resultEqual( data->level2results[i], result) ) 959 { 960 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "same level2 node already processed:\n"); 961 level2resultPrint(scip, data->level2results[i]); 962 level2resultPrint(scip, result); 963 *duplicate = TRUE; 964 } 965 } 966 967 data->level2results[data->nlevel2results] = result; 968 ++data->nlevel2results; 969 assert(data->nlevel2results <= data->level2resultssize); 970 971 return SCIP_OKAY; 972 } 973 974 975 /** The data that is preserved over multiple runs of the branching rule. */ 976 typedef struct 977 { 978 BRANCHINGDECISION* olddecision; /**< The previous decision that gets used for the case that in the previous run 979 * only non-violating implicit binary constraints were added.*/ 980 SCIP_Longint oldnnodelpiterations; /**< node LP iterations when previous branching decision was stored */ 981 SCIP_Longint oldnnodelps; /**< node LPs when previous branching decision was stored */ 982 SCIP_Longint oldntotalnodes; /**< node at which previous branching decision was stored */ 983 SCIP_Longint* lastbranchid; /**< The node id at which the var was last branched on (for a given branching 984 * var). */ 985 SCIP_Longint* lastbranchnlps; /**< The number of (non-probing) LPs that where solved when the var was last 986 * branched on. */ 987 SCIP_Real* lastbranchlpobjval; /**< The lp objval at which var was last branched on. */ 988 BRANCHINGRESULTDATA** lastbranchupres; /**< The result of the last up branching for a given var. */ 989 BRANCHINGRESULTDATA** lastbranchdownres; /**< The result of the last down branching for a given var. */ 990 int restartindex; /**< The index at which the iteration over the number of candidates starts. */ 991 int nvars; /**< The number of variables that can be stored in the arrays. */ 992 } PERSISTENTDATA; 993 994 /** The parameter that can be changed by the user/caller and alter the behaviour of the lookahead branching. */ 995 typedef struct 996 { 997 SCIP_Longint reevalage; /**< The number of "normal" (not probing) lps that may have been solved before 998 * we stop using old data and start recalculating new first level data. */ 999 SCIP_Longint reevalagefsb; /**< The number of "normal" (not probing) lps that may have been solved before 1000 * we stop using old FSB data and start recalculating new first level data. */ 1001 int maxnviolatedcons; /**< The number of constraints (domain reductions and binary constraints) we 1002 * want to gather before restarting the run. Set to -1 for an unbounded 1003 * number of constraints. */ 1004 int maxnviolatedbincons;/**< The number of binary constraints we want to gather before restarting the 1005 * run. Set to -1 for an undbounded number of binary constraints. */ 1006 int maxnviolateddomreds;/**< The number of domain reductions we want to gather before restarting the 1007 * run. Set to -1 for an undbounded number of domain reductions. */ 1008 int recursiondepth; /**< How deep should the recursion go? Default for Lookahead: 2 */ 1009 int maxncands; /**< If abbreviated == TRUE, at most how many candidates should be handled at the base node? */ 1010 int maxndeepercands; /**< If abbreviated == TRUE, at most how many candidates should be handled in deeper nodes? */ 1011 SCIP_Bool usedomainreduction; /**< indicates whether the data for domain reductions should be gathered and 1012 * used. */ 1013 SCIP_Bool mergedomainreductions; /**< should domain reductions of feasible siblings should be merged? */ 1014 SCIP_Bool prefersimplebounds; /**< should domain reductions only be applied if there are simple bound changes? */ 1015 SCIP_Bool onlyvioldomreds; /**< Should only domain reductions that violate the LP solution be applied? */ 1016 SCIP_Bool usebincons; /**< indicates whether the data for the implicit binary constraints should 1017 * be gathered and used */ 1018 int addbinconsrow; /**< should binary constraints be added as rows to the base LP? 1019 * (0: no, 1: separate, 2: as initial rows) */ 1020 SCIP_Bool addnonviocons; /**< Should constraints be added, that are not violated by the base LP? */ 1021 SCIP_Bool abbreviated; /**< Should the abbreviated version be used? */ 1022 SCIP_Bool reusebasis; /**< If abbreviated == TRUE, should the solution lp-basis of the FSB run be 1023 * used in the first abbreviated level? */ 1024 SCIP_Bool storeunviolatedsol; /**< Should a solution/decision be stored, to speed up the next iteration 1025 * after adding the constraints/domreds? */ 1026 SCIP_Bool abbrevpseudo; /**< If abbreviated == TRUE, should pseudocost values be used, to approximate 1027 * the scoring? */ 1028 SCIP_Bool level2avgscore; /**< should the average score be used for uninitialized scores in level 2? */ 1029 SCIP_Bool level2zeroscore; /**< should uninitialized scores in level 2 be set to zero? */ 1030 SCIP_Bool addclique; /**< add binary constraints with two variables found at the root node also as a clique? */ 1031 SCIP_Bool propagate; /**< Should the problem be propagated before solving each inner node? */ 1032 SCIP_Bool uselevel2data; /**< should branching data generated at depth level 2 be stored for re-using it? */ 1033 SCIP_Bool applychildbounds; /**< should bounds known for child nodes be applied? */ 1034 SCIP_Bool enforcemaxdomreds; /**< should the maximum number of domain reductions maxnviolateddomreds be enforced? */ 1035 SCIP_Bool updatebranchingresults; /**< should branching results (and scores) be updated w.r.t. proven dual bounds? */ 1036 SCIP_Bool inscoring; /**< are we currently in FSB-scoring (only used internally) */ 1037 int maxproprounds; /**< maximum number of propagation rounds to perform at temporary nodes 1038 * (-1: unlimited, 0: SCIP default) */ 1039 char scoringfunction; /**< scoring function at base level */ 1040 char deeperscoringfunction; /**< scoring function at deeper levels */ 1041 char scoringscoringfunction;/**< scoring function for FSB scoring */ 1042 SCIP_Real minweight; /**< weight of the min gain of two child problems */ 1043 SCIP_Real worsefactor; /**< if the FSB score is of a candidate is worse than the best by this factor, skip this candidate (-1: disable) */ 1044 SCIP_Bool filterbymaxgain; /**< should lookahead branching only be applied if the max gain in level 1 is not uniquely that of the best candidate? */ 1045 } CONFIGURATION; 1046 1047 1048 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 1049 #define MAXRESULT SCIP_DELAYNODE 1050 1051 /** returns a human readable name for the given result enum value */ 1052 static 1053 const char* getStatusString( 1054 SCIP_RESULT result /**< enum value to get the string representation for */ 1055 ) 1056 { 1057 assert(result >= 1); 1058 assert(result <= 18); 1059 1060 switch( result ) 1061 { 1062 case SCIP_DIDNOTRUN: 1063 return "SCIP_DIDNOTRUN"; 1064 case SCIP_DELAYED: 1065 return "SCIP_DELAYED"; 1066 case SCIP_DIDNOTFIND: 1067 return "SCIP_DIDNOTFIND"; 1068 case SCIP_FEASIBLE: 1069 return "SCIP_FEASIBLE"; 1070 case SCIP_INFEASIBLE: 1071 return "SCIP_INFEASIBLE"; 1072 case SCIP_UNBOUNDED: 1073 return "SCIP_UNBOUNDED"; 1074 case SCIP_CUTOFF: 1075 return "SCIP_CUTOFF"; 1076 case SCIP_SEPARATED: 1077 return "SCIP_SEPARATED"; 1078 case SCIP_NEWROUND: 1079 return "SCIP_NEWROUND"; 1080 case SCIP_REDUCEDDOM: 1081 return "SCIP_REDUCEDDOM"; 1082 case SCIP_CONSADDED: 1083 return "SCIP_CONSADDED"; 1084 case SCIP_CONSCHANGED: 1085 return "SCIP_CONSCHANGED"; 1086 case SCIP_BRANCHED: 1087 return "SCIP_BRANCHED"; 1088 case SCIP_SOLVELP: 1089 return "SCIP_SOLVELP"; 1090 case SCIP_FOUNDSOL: 1091 return "SCIP_FOUNDSOL"; 1092 case SCIP_SUSPENDED: 1093 return "SCIP_SUSPENDED"; 1094 case SCIP_SUCCESS: 1095 return "SCIP_SUCCESS"; 1096 case SCIP_DELAYNODE: 1097 return "SCIP_DELAYNODE"; 1098 default: 1099 SCIPerrorMessage("result code %d not treated in lookahead branching rule\n", result); 1100 SCIPABORT(); 1101 return "UNKNOWN"; 1102 } 1103 } 1104 #endif 1105 1106 #ifdef SCIP_STATISTIC 1107 /** The data used for some statistical analysis. */ 1108 typedef struct 1109 { 1110 int* nresults; /**< Array of counters for each result state the lookahead branching finished. 1111 * The first (0) entry is unused, as the result states are indexed 1-based 1112 * and we use this index as our array index. */ 1113 int* nsinglecutoffs; /**< The number of single cutoffs on a (probing) node per probingdepth. */ 1114 int* nfullcutoffs; /**< The number of double cutoffs on a (probing) node per probingdepth. */ 1115 int* nlpssolved; /**< The number of all lps solved for a given probingdepth (incl. FSB). */ 1116 int* nlpssolvedfsb; /**< The number of lps solved by the initial FSB to get the FSB scores. */ 1117 int* nduplicatelps; /**< The number of lps solved for duplicate grand-child nodes. */ 1118 SCIP_Longint* nlpiterations; /**< The number of all lp iterations needed for a given probingdepth 1119 * (incl. FSB). */ 1120 SCIP_Longint* nlpiterationsfsb; /**< The number of lp iterations needed to get the FSB scores. */ 1121 int* npropdomred; /**< The number of domain reductions based on domain propagation per 1122 * progingdepth. */ 1123 int* noldbranchused; /**< The number of times old branching data is used (see the reevalage 1124 * parameter in the CONFIGURATION struct) */ 1125 int* noldbranchusedfsb; /**< The number of times old FSB scoring data is used (see the reevalagefsb 1126 * parameter in the CONFIGURATION struct) */ 1127 int* chosenfsbcand; /**< If abbreviated, this is the number of times each candidate was finally 1128 * chosen by the following LAB */ 1129 int* stopafterfsb; /**< If abbreviated, this is the number of times the rule was stopped after 1130 * scoring candidates by FSB, e.g., by adding constraints or domreds. */ 1131 int* cutoffafterfsb; /**< If abbreviated, this is the number of times the rule was stopped after 1132 * scoring candidates by FSB because of a found cutoff. */ 1133 int* domredafterfsb; /**< If abbreviated, this is the number of times the rule was stopped after 1134 * scoring candidates by FSB because of a found domain reduction. */ 1135 int nsinglecandidate; /**< number of times a single candidate was given to the recursion routine */ 1136 int nsingleafterfilter; /**< number of times a single candidate remained after filtering */ 1137 int noldcandidate; /**< number of times the old candidate from last call with nonviolating 1138 * reductions was branched on */ 1139 int nlperrorcalls; /**< number of times an LP error occured and LAB branched without completely 1140 * evaluating all candidates */ 1141 int nlimitcalls; /**< number of times a time limit was reached and LAB branched without 1142 * completely evaluating all candidates */ 1143 int ntotalresults; /**< The total sum of the entries in nresults. */ 1144 int nbinconst; /**< The number of binary constraints added to the base node. */ 1145 int nbinconstvio; /**< The number of binary constraints added to the base node, that are violated 1146 * by the LP at that node. */ 1147 int ndomred; /**< The number of domain reductions added to the base node. */ 1148 int ndomredvio; /**< The number of domain reductions added to the base node, that are violated 1149 * by the LP at that node. */ 1150 int ndepthreached; /**< The number of times the branching was aborted due to a too small depth. */ 1151 int ndomredcons; /**< The number of binary constraints ignored, as they would be dom reds. */ 1152 int ncutoffproofnodes; /**< The number of nodes needed to prove all found cutoffs. */ 1153 int ndomredproofnodes; /**< The number of nodes needed to prove all found domreds. */ 1154 int ncliquesadded; /**< The number of cliques added in the root node. */ 1155 int maxnbestcands; /**< if abbreviated, this is the maximum number of candidates to investigate */ 1156 int recursiondepth; /**< The recursiondepth of the LAB. Can be used to access the depth-dependent 1157 * arrays contained in the statistics. */ 1158 } STATISTICS; 1159 1160 /** Initializes the statistics with the start values. */ 1161 static 1162 void statisticsInit( 1163 STATISTICS* statistics /**< the statistics to be initialized */ 1164 ) 1165 { 1166 int i; 1167 1168 assert(statistics != NULL); 1169 assert(statistics->recursiondepth > 0); 1170 1171 statistics->nsinglecandidate = 0; 1172 statistics->nsingleafterfilter = 0; 1173 statistics->noldcandidate = 0; 1174 statistics->nlperrorcalls = 0; 1175 statistics->nlimitcalls = 0; 1176 statistics->ntotalresults = 0; 1177 statistics->nbinconst = 0; 1178 statistics->nbinconstvio = 0; 1179 statistics->ndomredvio = 0; 1180 statistics->ndepthreached = 0; 1181 statistics->ndomred = 0; 1182 statistics->ndomredcons = 0; 1183 statistics->ncutoffproofnodes = 0; 1184 statistics->ndomredproofnodes = 0; 1185 statistics->ncliquesadded = 0; 1186 1187 for( i = 0; i <= MAXRESULT; i++) 1188 { 1189 statistics->nresults[i] = 0; 1190 } 1191 1192 for( i = 0; i < statistics->recursiondepth; i++ ) 1193 { 1194 statistics->noldbranchused[i] = 0; 1195 statistics->noldbranchusedfsb[i] = 0; 1196 statistics->npropdomred[i] = 0; 1197 statistics->nfullcutoffs[i] = 0; 1198 statistics->nlpssolved[i] = 0; 1199 statistics->nlpssolvedfsb[i] = 0; 1200 statistics->nduplicatelps[i] = 0; 1201 statistics->nlpiterations[i] = 0; 1202 statistics->nlpiterationsfsb[i] = 0; 1203 statistics->nsinglecutoffs[i] = 0; 1204 statistics->stopafterfsb[i] = 0; 1205 statistics->cutoffafterfsb[i] = 0; 1206 statistics->domredafterfsb[i] = 0; 1207 } 1208 1209 for( i = 0; i < statistics->maxnbestcands; i++ ) 1210 { 1211 statistics->chosenfsbcand[i] = 0; 1212 } 1213 } 1214 1215 /** Prints the content of the statistics to stdout. */ 1216 static 1217 void statisticsPrint( 1218 SCIP* scip, /**< SCIP data structure */ 1219 STATISTICS* statistics /**< the statistics to print */ 1220 ) 1221 { 1222 assert(scip != NULL); 1223 assert(statistics != NULL); 1224 assert(statistics->recursiondepth > 0); 1225 1226 /* only print something, if we have any statistics */ 1227 if( statistics->ntotalresults > 0 ) 1228 { 1229 int i; 1230 1231 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Lookahead Branching was called <%i> times.\n", statistics->ntotalresults); 1232 1233 for( i = 1; i <= MAXRESULT; i++ ) 1234 { 1235 SCIP_RESULT currentresult = (SCIP_RESULT)i; 1236 /* see type_result.h for the id <-> enum mapping */ 1237 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Result <%s> was chosen <%i> times\n", getStatusString(currentresult), 1238 statistics->nresults[i]); 1239 } 1240 1241 for( i = 0; i < statistics->maxnbestcands; i++ ) 1242 { 1243 if( statistics->chosenfsbcand[i] > 0 ) 1244 { 1245 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "The %i. variable (w.r.t. the FSB score) was chosen as the final result %i times.\n", 1246 i+1, statistics->chosenfsbcand[i]); 1247 } 1248 } 1249 1250 for( i = 0; i < statistics->recursiondepth; i++ ) 1251 { 1252 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, branching was stopped after the scoring FSB %i times, %i times because of a cutoff and %i times because of a domain reduction\n", 1253 i, statistics->stopafterfsb[i], statistics->cutoffafterfsb[i], statistics->domredafterfsb[i]); 1254 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, <%i> fullcutoffs and <%i> single cutoffs were found.\n", 1255 i, statistics->nfullcutoffs[i], statistics->nsinglecutoffs[i]); 1256 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, <%i> LPs were solved, <%i> of them to calculate the FSB score, <%i> were saved for duplicate grandchildren.\n", 1257 i, statistics->nlpssolved[i], statistics->nlpssolvedfsb[i], statistics->nduplicatelps[i]); 1258 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, <%" SCIP_LONGINT_FORMAT "> iterations were needed to solve the LPs, <%" 1259 SCIP_LONGINT_FORMAT "> of them to calculate the FSB score.\n", i, statistics->nlpiterations[i], 1260 statistics->nlpiterationsfsb[i]); 1261 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, a decision was discarded <%i> times due to domain reduction because of" 1262 " propagation.\n", i, statistics->npropdomred[i]); 1263 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, old LAB branching results were used in <%i> cases, old FSB scores in <%d> cases.\n", 1264 i, statistics->noldbranchused[i], statistics->noldbranchusedfsb[i]); 1265 } 1266 1267 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "One single branching candidate was given <%i> times, after filtering, a single candidate remained <%i> times.\n", 1268 statistics->nsinglecandidate, statistics->nsingleafterfilter); 1269 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "The old branching candidate was used <%i> times.\n", 1270 statistics->noldcandidate); 1271 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "An LP error led to branching before all candidates were evaluated <%i> times.\n", 1272 statistics->nlperrorcalls); 1273 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "A reached (time) limit led to branching before all candidates were evaluated <%i> times.\n", 1274 statistics->nlimitcalls); 1275 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Depth limit was reached <%i> times.\n", statistics->ndepthreached); 1276 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Ignored <%i> binary constraints, that would be domain reductions.\n", 1277 statistics->ndomredcons); 1278 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Added <%i> binary constraints, of which <%i> where violated by the base LP.\n", 1279 statistics->nbinconst, statistics->nbinconstvio); 1280 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Reduced the domain of <%i> vars, <%i> of them where violated by the base LP.\n", 1281 statistics->ndomred, statistics->ndomredvio); 1282 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Added <%i> cliques found as binary constraint in the root node\n", 1283 statistics->ncliquesadded); 1284 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Needed <%i> additional nodes to prove the cutoffs of base nodes\n", 1285 statistics->ncutoffproofnodes); 1286 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Needed <%i> additional nodes to prove the domain reductions\n", 1287 statistics->ndomredproofnodes); 1288 } 1289 } 1290 1291 /** Helper struct to store the statistical data needed in a single run. */ 1292 typedef struct 1293 { 1294 int ncutoffproofnodes; /**< The number of nodes needed to prove the current cutoff. */ 1295 } LOCALSTATISTICS; 1296 1297 /** Allocates the local statistics in buffer memory and initializes it with default values. */ 1298 static 1299 SCIP_RETCODE localStatisticsAllocate( 1300 SCIP* scip, /**< SCIP data structure */ 1301 LOCALSTATISTICS** localstats /**< pointer to the local statistics to allocate and initialize */ 1302 ) 1303 { 1304 assert(scip != NULL); 1305 assert(localstats != NULL); 1306 1307 SCIP_CALL( SCIPallocBuffer(scip, localstats) ); 1308 1309 (*localstats)->ncutoffproofnodes = 0; 1310 1311 return SCIP_OKAY; 1312 } 1313 1314 /** Frees the allocated buffer memory of the local statistics. */ 1315 static 1316 void localStatisticsFree( 1317 SCIP* scip, /**< SCIP data structure */ 1318 LOCALSTATISTICS** localstats /**< pointer to the local statistics to be freed */ 1319 ) 1320 { 1321 assert(scip != NULL); 1322 assert(localstats != NULL); 1323 1324 SCIPfreeBuffer(scip, localstats); 1325 } 1326 #endif 1327 1328 /** branching rule data */ 1329 struct SCIP_BranchruleData 1330 { 1331 CONFIGURATION* config; /**< the parameter that influence the behaviour of the lookahead branching */ 1332 PERSISTENTDATA* persistent; /**< the data that persists over multiple branching decisions */ 1333 SCIP_Bool isinitialized; /**< indicates whether the fields in this struct are initialized */ 1334 #ifdef SCIP_STATISTIC 1335 STATISTICS* statistics; /**< statistical data container */ 1336 #endif 1337 }; 1338 1339 /** all constraints that were created and may be added to the base node */ 1340 typedef struct 1341 { 1342 SCIP_VAR*** consvars; /**< array containing the variables for each constraint to be created */ 1343 int* nconsvars; /**< number of vars in each element of 'consvars' */ 1344 SCIP_Bool* violated; /**< indicating whether a constraint is violated by the base solution */ 1345 int nelements; /**< number of elements in 'consvars' and 'nconsvars' */ 1346 int memorysize; /**< number of entries that the array 'consvars' may hold before the 1347 * array is reallocated. */ 1348 int nviolatedcons; /**< number of constraints that are violated by the base LP solution. */ 1349 } CONSTRAINTLIST; 1350 1351 /** Allocate and initialize the list holding the constraints. */ 1352 static 1353 SCIP_RETCODE constraintListCreate( 1354 SCIP* scip, /**< SCIP data structure */ 1355 CONSTRAINTLIST** conslist, /**< Pointer to the list to be allocated and initialized. */ 1356 int startsize /**< The number of entries the list initially can hold. */ 1357 ) 1358 { 1359 assert(scip != NULL); 1360 assert(conslist != NULL); 1361 assert(startsize > 0); 1362 1363 SCIP_CALL( SCIPallocBuffer(scip, conslist) ); 1364 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*conslist)->consvars, startsize) ); 1365 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*conslist)->nconsvars, startsize) ); 1366 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*conslist)->violated, startsize) ); 1367 1368 /* We start without any constraints */ 1369 (*conslist)->nelements = 0; 1370 (*conslist)->memorysize = startsize; 1371 (*conslist)->nviolatedcons = 0; 1372 1373 return SCIP_OKAY; 1374 } 1375 1376 /** Append an element to the end of the list of constraints. */ 1377 static 1378 SCIP_RETCODE constraintListAppend( 1379 SCIP* scip, /**< SCIP data structure */ 1380 CONSTRAINTLIST* list, /**< list to add the consvars to */ 1381 SCIP_VAR** consvars, /**< array of variables for the constraint to be created later */ 1382 int nconsvars, /**< number of elements in 'consvars' */ 1383 SCIP_Bool violated /**< indicates whether the constraint is violated by the base lp */ 1384 ) 1385 { 1386 assert(scip != NULL); 1387 assert(list != NULL); 1388 assert(consvars != NULL); 1389 assert(nconsvars > 0); 1390 1391 /* In case the list tries to hold more elements than it has space, reallocate */ 1392 if( list->memorysize == list->nelements ) 1393 { 1394 /* resize the array, such that it can hold the new element */ 1395 int newmemsize = SCIPcalcMemGrowSize(scip, list->memorysize + 1); 1396 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &list->consvars, list->memorysize, newmemsize) ); 1397 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &list->nconsvars, list->memorysize, newmemsize) ); 1398 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &list->violated, list->memorysize, newmemsize) ); 1399 list->memorysize = newmemsize; 1400 } 1401 1402 /* Set the new vars at the first unused place, which is the length used as index */ 1403 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &list->consvars[list->nelements], consvars, nconsvars) ); /*lint !e866*/ 1404 list->nconsvars[list->nelements] = nconsvars; 1405 list->violated[list->nelements] = violated; 1406 list->nelements++; 1407 1408 return SCIP_OKAY; 1409 } 1410 1411 /** Free all resources of a constraint list in opposite order to the allocation. */ 1412 static 1413 void constraintListFree( 1414 SCIP* scip, /**< SCIP data structure */ 1415 CONSTRAINTLIST** conslist /**< Pointer to the list to be freed. */ 1416 ) 1417 { 1418 int i; 1419 1420 assert(scip != NULL); 1421 assert(conslist != NULL); 1422 1423 for( i = 0; i < (*conslist)->nelements; i++ ) 1424 { 1425 SCIPfreeBlockMemoryArray(scip, &(*conslist)->consvars[i], (*conslist)->nconsvars[i]); 1426 } 1427 1428 SCIPfreeBlockMemoryArray(scip, &(*conslist)->violated, (*conslist)->memorysize); 1429 SCIPfreeBlockMemoryArray(scip, &(*conslist)->nconsvars, (*conslist)->memorysize); 1430 SCIPfreeBlockMemoryArray(scip, &(*conslist)->consvars, (*conslist)->memorysize); 1431 SCIPfreeBuffer(scip, conslist); 1432 } 1433 1434 /** 1435 * list of binary variables currently branched on 1436 * a down branching (x <= 0) is saved as the negated variable (1-x) 1437 * an up branching (x >= 1) is saved as the original variable (x) 1438 * these variables are used to build the binary constraint in case that a ('binary') branch is cut off 1439 */ 1440 typedef struct 1441 { 1442 SCIP_VAR** binaryvars; /**< The binary variables currently branched on. */ 1443 int nbinaryvars; /**< The number of entries in 'nbinaryvars'. */ 1444 int memorysize; /**< The number of entries that the array 'binaryvars' may hold before the 1445 * array is reallocated. */ 1446 } BINARYVARLIST; 1447 1448 /** Allocates and initializes the BINARYVARLIST struct. */ 1449 static 1450 SCIP_RETCODE binaryVarListCreate( 1451 SCIP* scip, /**< SCIP data structure */ 1452 BINARYVARLIST** list, /**< Pointer to the list to be allocated and initialized. */ 1453 int startsize /**< The number of entries the list initially can hold. */ 1454 ) 1455 { 1456 assert(scip != NULL); 1457 assert(list != NULL); 1458 assert(startsize > 0); 1459 1460 SCIP_CALL( SCIPallocBuffer(scip, list) ); 1461 SCIP_CALL( SCIPallocBufferArray(scip, &(*list)->binaryvars, startsize) ); 1462 1463 /* We start with no entries and the (current) max length */ 1464 (*list)->nbinaryvars = 0; 1465 (*list)->memorysize = startsize; 1466 1467 return SCIP_OKAY; 1468 } 1469 1470 /** Appends a binary variable to the list, reallocating the list if necessary. */ 1471 static 1472 void binaryVarListAppend( 1473 SCIP* scip, /**< SCIP data structure */ 1474 BINARYVARLIST* list, /**< The list to add the var to. */ 1475 SCIP_VAR* vartoadd /**< The binary var to add to the list. */ 1476 ) 1477 { 1478 assert(scip != NULL); 1479 assert(list != NULL); 1480 assert(vartoadd != NULL); 1481 assert(SCIPvarIsBinary(vartoadd)); 1482 assert(list->nbinaryvars < list->memorysize); 1483 1484 /* Set the new var at the first unused place, which is the length used as index */ 1485 list->binaryvars[list->nbinaryvars] = vartoadd; 1486 list->nbinaryvars++; 1487 } 1488 1489 /** Remove the last element from the list. */ 1490 static 1491 void binaryVarListDrop( 1492 BINARYVARLIST* list /**< The list to remove the last element from. */ 1493 ) 1494 { 1495 assert(list != NULL); 1496 assert(list->nbinaryvars > 0); 1497 assert(list->binaryvars[list->nbinaryvars-1] != NULL); 1498 1499 /* decrement the number of entries in the actual list */ 1500 list->nbinaryvars--; 1501 } 1502 1503 /** Frees all resources allocated by a BINARYVARLIST in opposite order of allocation. */ 1504 static 1505 void binaryVarListFree( 1506 SCIP* scip, /**< SCIP data structure */ 1507 BINARYVARLIST** list /**< Pointer to the list to free */ 1508 ) 1509 { 1510 assert(scip != NULL); 1511 assert(list != NULL); 1512 1513 SCIPfreeBufferArray(scip, &(*list)->binaryvars); 1514 SCIPfreeBuffer(scip, list); 1515 } 1516 1517 /** struct holding the relevant data for handling binary constraints */ 1518 typedef struct 1519 { 1520 BINARYVARLIST* binaryvars; /**< current binary vars, used to fill the conslist */ 1521 CONSTRAINTLIST* conslist; /**< list of constraints to be created */ 1522 } BINCONSDATA; 1523 1524 /** Allocate and initialize the BINCONSDATA struct. */ 1525 static 1526 SCIP_RETCODE binConsDataCreate( 1527 SCIP* scip, /**< SCIP data structure */ 1528 BINCONSDATA** consdata, /**< Pointer to the struct to be allocated and initialized. */ 1529 int maxdepth, /**< The depth of the recursion as an upper bound of branch vars to hold. */ 1530 int nstartcons /**< The start size of the array containing the constraints. */ 1531 ) 1532 { 1533 assert(scip != NULL); 1534 assert(consdata != NULL); 1535 assert(maxdepth > 0); 1536 assert(nstartcons > 0); 1537 1538 SCIP_CALL( SCIPallocBuffer(scip, consdata) ); 1539 SCIP_CALL( binaryVarListCreate(scip, &(*consdata)->binaryvars, maxdepth) ); 1540 SCIP_CALL( constraintListCreate(scip, &(*consdata)->conslist, nstartcons) ); 1541 1542 return SCIP_OKAY; 1543 } 1544 1545 /** Free all resources in a BINCONSDATA in opposite order of allocation. */ 1546 static 1547 void binConsDataFree( 1548 SCIP* scip, /**< SCIP data structure */ 1549 BINCONSDATA** consdata /**< Pointer to the struct to be freed. */ 1550 ) 1551 { 1552 assert(scip != NULL); 1553 assert(consdata != NULL); 1554 1555 constraintListFree(scip, &(*consdata)->conslist); 1556 binaryVarListFree(scip, &(*consdata)->binaryvars); 1557 SCIPfreeBuffer(scip, consdata); 1558 } 1559 1560 /** A struct acting as a fixed list of candidates */ 1561 typedef struct 1562 { 1563 CANDIDATE** candidates; /**< the array of candidates */ 1564 int ncandidates; /**< the number of actual entries in candidates (without trailing NULLs); this 1565 * is NOT the length of the candidates array, but the number of candidates in 1566 * it */ 1567 } CANDIDATELIST; 1568 1569 /** allocates the candidate list on the buffer WITHOUT initializing the contained array of candidates. */ 1570 static 1571 SCIP_RETCODE candidateListCreate( 1572 SCIP* scip, /**< SCIP data structure */ 1573 CANDIDATELIST** candidatelist, /**< the candidate list to allocate */ 1574 int ncandidates /**< the number of candidates the list must hold */ 1575 ) 1576 { 1577 assert(scip != NULL); 1578 assert(candidatelist != NULL); 1579 assert(ncandidates >= 0); 1580 1581 SCIP_CALL( SCIPallocBuffer(scip, candidatelist) ); 1582 1583 if( ncandidates > 0 ) 1584 { 1585 SCIP_CALL( SCIPallocBufferArray(scip, &(*candidatelist)->candidates, ncandidates) ); 1586 } 1587 else 1588 (*candidatelist)->candidates = NULL; 1589 1590 (*candidatelist)->ncandidates = ncandidates; 1591 1592 return SCIP_OKAY; 1593 } 1594 1595 /** allocates the given list and fills it with all fractional candidates of the current LP solution. */ 1596 static 1597 SCIP_RETCODE candidateListGetAllFractionalCandidates( 1598 SCIP* scip, /**< SCIP data structure */ 1599 CANDIDATELIST** candidatelist /**< the list to allocate and fill */ 1600 ) 1601 { 1602 SCIP_VAR** lpcands; 1603 SCIP_Real* lpcandssol; 1604 SCIP_Real* lpcandsfrac; 1605 int nlpcands; 1606 int i; 1607 1608 assert(scip != NULL); 1609 assert(candidatelist != NULL); 1610 1611 /* get all fractional candidates */ 1612 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) ); 1613 1614 assert(lpcands != NULL); 1615 assert(lpcandssol != NULL); 1616 assert(lpcandsfrac != NULL); 1617 1618 SCIP_CALL( candidateListCreate(scip, candidatelist, nlpcands) ); 1619 1620 for( i = 0; i < nlpcands; i++ ) 1621 { 1622 CANDIDATE* candidate; 1623 1624 SCIP_CALL( candidateCreate(scip, &candidate) ); 1625 assert(candidate != NULL); 1626 1627 candidate->branchvar = lpcands[i]; 1628 candidate->branchval = lpcandssol[i]; 1629 candidate->fracval = lpcandsfrac[i]; 1630 1631 (*candidatelist)->candidates[i] = candidate; 1632 1633 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "created candidate <%s>...\n", 1634 (candidate) != NULL ? SCIPvarGetName((candidate)->branchvar) : "none"); 1635 } 1636 1637 return SCIP_OKAY; 1638 } 1639 1640 /** frees the allocated buffer memory of the candidate list and frees the contained candidates. */ 1641 static 1642 SCIP_RETCODE candidateListFree( 1643 SCIP* scip, /**< SCIP data structure */ 1644 CANDIDATELIST** candidatelist /**< the list to be freed */ 1645 ) 1646 { 1647 int i; 1648 1649 assert(scip != NULL); 1650 assert(candidatelist != NULL); 1651 assert((*candidatelist)->ncandidates > 0 || (*candidatelist)->candidates == NULL); 1652 1653 if( (*candidatelist)->candidates != NULL ) 1654 { 1655 for( i = (*candidatelist)->ncandidates - 1; i >= 0; i-- ) 1656 { 1657 CANDIDATE* cand = (*candidatelist)->candidates[i]; 1658 if( cand != NULL ) 1659 { 1660 SCIP_CALL( candidateFree(scip, &cand) ); 1661 } 1662 } 1663 1664 SCIPfreeBufferArray(scip, &(*candidatelist)->candidates); 1665 } 1666 SCIPfreeBuffer(scip, candidatelist); 1667 1668 return SCIP_OKAY; 1669 } 1670 1671 /** keeps only the first candidates and frees the remaining ones */ 1672 static 1673 SCIP_RETCODE candidateListKeep( 1674 SCIP* scip, /**< SCIP data structure */ 1675 CANDIDATELIST* candidatelist, /**< the list to allocate and fill */ 1676 int nindices /**< the number of candidates to keep (starting from 0) */ 1677 ) 1678 { 1679 int i; 1680 1681 assert(scip != NULL); 1682 assert(candidatelist != NULL); 1683 assert(0 < nindices); 1684 assert(nindices <= candidatelist->ncandidates); 1685 1686 /* only keep the first nindices candidates and free the remaining ones */ 1687 for( i = nindices; i < candidatelist->ncandidates; i++ ) 1688 { 1689 CANDIDATE* cand = candidatelist->candidates[i]; 1690 if( cand != NULL ) 1691 { 1692 SCIP_CALL( candidateFree(scip, &cand) ); 1693 candidatelist->candidates[i] = NULL; 1694 } 1695 } 1696 candidatelist->ncandidates = nindices; 1697 1698 return SCIP_OKAY; 1699 } 1700 1701 /** all domain reductions found through cutoff of branches */ 1702 typedef struct 1703 { 1704 SCIP_Real* lowerbounds; /**< The new lower bounds found for each variable in the problem. */ 1705 SCIP_Real* upperbounds; /**< The new upper bounds found for each variable in the problem. */ 1706 SCIP_Shortbool* baselpviolated; /**< Indicates whether the base lp solution violates the new bounds of a var.*/ 1707 int nviolatedvars; /**< Tracks the number of vars that have a violated (by the base lp) new lower 1708 * or upper bound. */ 1709 int nchangedvars; /**< Tracks the number of vars, that have a changed domain. (a change on both, 1710 * upper and lower bound, counts as one.) */ 1711 int nsimplebounds; /**< number of changed bounds resulting from infeasible child nodes */ 1712 #ifdef SCIP_STATISTIC 1713 int* lowerboundnproofs; /**< The number of nodes needed to prove the lower bound for each variable. */ 1714 int* upperboundnproofs; /**< The number of nodes needed to prove the upper bound for each variable. */ 1715 #endif 1716 } DOMAINREDUCTIONS; 1717 1718 /** allocate the struct on the buffer and initialize it with the default values */ 1719 static 1720 SCIP_RETCODE domainReductionsCreate( 1721 SCIP* scip, /**< SCIP data structure */ 1722 DOMAINREDUCTIONS** domreds /**< The struct that has to be allocated and initialized. */ 1723 ) 1724 { 1725 SCIP_VAR** vars; 1726 int ntotalvars; 1727 int v; 1728 1729 assert(scip != NULL); 1730 assert(domreds != NULL); 1731 1732 /* The arrays saves the data for all variables in the problem via the ProbIndex. See SCIPvarGetProbindex() */ 1733 vars = SCIPgetVars(scip); 1734 ntotalvars = SCIPgetNVars(scip); 1735 1736 /* Allocate the struct and the contained arrays; initialize flags to FALSE */ 1737 SCIP_CALL( SCIPallocBuffer(scip, domreds) ); 1738 SCIP_CALL( SCIPallocBufferArray(scip, &(*domreds)->lowerbounds, ntotalvars) ); 1739 SCIP_CALL( SCIPallocBufferArray(scip, &(*domreds)->upperbounds, ntotalvars) ); 1740 SCIP_CALL( SCIPallocClearBufferArray(scip, &(*domreds)->baselpviolated, ntotalvars) ); 1741 #ifdef SCIP_STATISTIC 1742 SCIP_CALL( SCIPallocClearBufferArray(scip, &(*domreds)->lowerboundnproofs, ntotalvars) ); 1743 SCIP_CALL( SCIPallocClearBufferArray(scip, &(*domreds)->upperboundnproofs, ntotalvars) ); 1744 #endif 1745 1746 for( v = 0; v < ntotalvars; ++v ) 1747 { 1748 (*domreds)->lowerbounds[v] = SCIPvarGetLbLocal(vars[v]); 1749 (*domreds)->upperbounds[v] = SCIPvarGetUbLocal(vars[v]); 1750 } 1751 1752 /* At the start we have no domain reductions for any variable. */ 1753 (*domreds)->nviolatedvars = 0; 1754 (*domreds)->nchangedvars = 0; 1755 (*domreds)->nsimplebounds = 0; 1756 1757 return SCIP_OKAY; 1758 } 1759 1760 /** frees the given DOMAINREDUCTIONS and all contained Arrays in the opposite order of allocation */ 1761 static 1762 void domainReductionsFree( 1763 SCIP* scip, /**< SCIP data structure */ 1764 DOMAINREDUCTIONS** domreds /**< Pointer to the struct to be freed. */ 1765 ) 1766 { 1767 assert(scip != NULL); 1768 assert(domreds != NULL); 1769 1770 #ifdef SCIP_STATISTIC 1771 SCIPfreeBufferArray(scip, &(*domreds)->upperboundnproofs); 1772 SCIPfreeBufferArray(scip, &(*domreds)->lowerboundnproofs); 1773 #endif 1774 SCIPfreeBufferArray(scip, &(*domreds)->baselpviolated); 1775 SCIPfreeBufferArray(scip, &(*domreds)->upperbounds); 1776 SCIPfreeBufferArray(scip, &(*domreds)->lowerbounds); 1777 SCIPfreeBuffer(scip, domreds); 1778 } 1779 1780 /** information about the current status of the branching */ 1781 typedef struct 1782 { 1783 SCIP_Bool addedbinconss; /**< were binary constraints added? */ 1784 SCIP_Bool depthtoosmall; /**< was the remaining depth too small to branch on? */ 1785 SCIP_Bool lperror; /**< did an error occur while solving an LP */ 1786 SCIP_Bool cutoff; /**< was the current node cut off? */ 1787 SCIP_Bool domredcutoff; /**< was the current node cut off due to domain reductions? */ 1788 SCIP_Bool domred; /**< were domain reductions added due to information obtained through 1789 * branching? */ 1790 SCIP_Bool limitreached; /**< was a limit (time, node, user, ...) reached? */ 1791 SCIP_Bool maxnconsreached; /**< was the max number of constraints (bin conss and dom red) reached? */ 1792 } STATUS; 1793 1794 /** Allocates the status on the buffer memory and initializes it with default values. */ 1795 static 1796 SCIP_RETCODE statusCreate( 1797 SCIP* scip, /**< SCIP data structure */ 1798 STATUS** status /**< the status to be allocated */ 1799 ) 1800 { 1801 assert(scip != NULL); 1802 assert(status != NULL); 1803 1804 SCIP_CALL( SCIPallocBuffer(scip, status) ); 1805 1806 (*status)->addedbinconss = FALSE; 1807 (*status)->depthtoosmall = FALSE; 1808 (*status)->lperror = FALSE; 1809 (*status)->cutoff = FALSE; 1810 (*status)->domred = FALSE; 1811 (*status)->domredcutoff = FALSE; 1812 (*status)->limitreached = FALSE; 1813 (*status)->maxnconsreached = FALSE; 1814 1815 return SCIP_OKAY; 1816 } 1817 1818 /** frees the allocated buffer memory of the status */ 1819 static 1820 void statusFree( 1821 SCIP* scip, /**< SCIP data structure */ 1822 STATUS** status /**< the status to be freed */ 1823 ) 1824 { 1825 assert(scip != NULL); 1826 assert(status != NULL); 1827 SCIPfreeBuffer(scip, status); 1828 } 1829 1830 /** container struct to keep the calculated score for each variable */ 1831 typedef struct 1832 { 1833 SCIP_Real* scores; /**< the scores for each problem variable */ 1834 SCIP_Real* downgains; /**< the downgains for each problem variable */ 1835 SCIP_Real* upgains; /**< the upgains for each problem variable */ 1836 CANDIDATE** bestsortedcands; /**< array containing the best sorted variable indices w.r.t. their score */ 1837 int nbestsortedcands; /**< number of elements in bestsortedcands */ 1838 SCIP_Real scoresum; /**< sum of set scores */ 1839 int nsetscores; /**< number of set scores */ 1840 } SCORECONTAINER; 1841 1842 /** resets the array containing the sorted indices w.r.t. their score. */ 1843 static 1844 void scoreContainterResetBestSortedCands( 1845 SCORECONTAINER* scorecontainer /**< the score container to reset */ 1846 ) 1847 { 1848 assert(scorecontainer != NULL); 1849 1850 BMSclearMemoryArray(scorecontainer->bestsortedcands, scorecontainer->nbestsortedcands); 1851 } 1852 1853 /** allocates the score container and inits it with default values */ 1854 static 1855 SCIP_RETCODE scoreContainerCreate( 1856 SCIP* scip, /**< SCIP data structure */ 1857 SCORECONTAINER** scorecontainer, /**< pointer to the score container to init */ 1858 CONFIGURATION* config /**< config struct with the user configuration */ 1859 ) 1860 { 1861 int ntotalvars; 1862 int ncands = config->maxncands; 1863 int i; 1864 1865 assert(scip != NULL); 1866 assert(scorecontainer != NULL); 1867 assert(config != NULL); 1868 1869 /* the container saves the score for all variables in the problem via the ProbIndex, see SCIPvarGetProbindex() */ 1870 ntotalvars = SCIPgetNVars(scip); 1871 1872 if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) < ncands ) 1873 ncands = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 1874 1875 SCIP_CALL( SCIPallocBuffer(scip, scorecontainer) ); 1876 SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->scores, ntotalvars) ); 1877 SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->downgains, ntotalvars) ); 1878 SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->upgains, ntotalvars) ); 1879 SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->bestsortedcands, ncands) ); 1880 1881 (*scorecontainer)->nbestsortedcands = ncands; 1882 (*scorecontainer)->scoresum = 0.0; 1883 (*scorecontainer)->nsetscores = 0; 1884 1885 scoreContainterResetBestSortedCands(*scorecontainer); 1886 1887 /* init the scores to something negative, as scores are always non negative */ 1888 for( i = 0; i < ntotalvars; i++ ) 1889 { 1890 (*scorecontainer)->scores[i] = -1.0; 1891 (*scorecontainer)->downgains[i] = -1.0; 1892 (*scorecontainer)->upgains[i] = -1.0; 1893 } 1894 1895 return SCIP_OKAY; 1896 } 1897 1898 /** Finds the insertion index for the given score in the candidate list. The score of each candidate is taken from the 1899 * scorecontainer. The first elements of the candidate list have to be sorted, as this method uses binary search to find 1900 * the correct insertion point 1901 */ 1902 static 1903 int findInsertionPoint( 1904 SCIP* scip, /**< SCIP data structure */ 1905 SCORECONTAINER* scorecontainer, /**< container with all the scores for each candidate */ 1906 SCIP_Real scoretoinsert, /**< score to find the insertion index for */ 1907 CANDIDATE** candidates, /**< candidate list where the first nsorted elements are sorted (w.r.t. their 1908 * score) */ 1909 int ncandidates /**< number of elements in candidates to consider, starting from 0 */ 1910 ) 1911 { 1912 int left = 0; 1913 int right = ncandidates - 1; 1914 1915 assert(scip != NULL); 1916 assert(scorecontainer != NULL); 1917 assert(candidates != NULL); 1918 assert(ncandidates >= 0); 1919 1920 while( left <= right ) 1921 { 1922 int mid = left + ((right - left) / 2); 1923 SCIP_Real midscore = -SCIPinfinity(scip); 1924 CANDIDATE *midcand = candidates[mid]; 1925 1926 if( midcand != NULL) 1927 { 1928 SCIP_VAR* midvar; 1929 int midindex; 1930 1931 midvar = midcand->branchvar; 1932 midindex = SCIPvarGetProbindex(midvar); 1933 midscore = scorecontainer->scores[midindex]; 1934 } 1935 1936 if( SCIPisGT(scip, scoretoinsert, midscore) ) 1937 right = mid - 1; 1938 else 1939 left = mid + 1; 1940 } 1941 1942 return right + 1; 1943 } 1944 1945 /** Inserts the given probindex into the sorted array in the container, moving all indices after it to the right. Then 1946 * returns the element that does not fit into the array any longer. */ 1947 static 1948 CANDIDATE* scoreContainerUpdateSortOrder( 1949 SCORECONTAINER* scorecontainer, /**< container to insert the index into */ 1950 CANDIDATE* candidate, /**< the probindex of a variable to store */ 1951 int insertpoint /**< point to store the index at */ 1952 ) 1953 { 1954 int i; 1955 CANDIDATE* movecand = candidate; 1956 1957 assert(scorecontainer != NULL); 1958 assert(candidate != NULL); 1959 assert(insertpoint >= 0); 1960 1961 for( i = insertpoint; i < scorecontainer->nbestsortedcands; i++ ) 1962 { 1963 CANDIDATE* oldcand = scorecontainer->bestsortedcands[i]; 1964 scorecontainer->bestsortedcands[i] = movecand; 1965 movecand = oldcand; 1966 } 1967 1968 return movecand; 1969 } 1970 1971 /** sets the score for the variable in the score container */ 1972 static 1973 SCIP_RETCODE scoreContainerSetScore( 1974 SCIP* scip, /**< SCIP data structure */ 1975 SCORECONTAINER* scorecontainer, /**< the container to write into */ 1976 CANDIDATE* cand, /**< candidate to add the score for */ 1977 SCIP_Real score, /**< score to add */ 1978 SCIP_Real downgain, /**< LP gain in down child */ 1979 SCIP_Real upgain /**< LP gain in up child */ 1980 ) 1981 { 1982 CANDIDATE* droppedcandidate; 1983 int probindex; 1984 int insertpoint; 1985 1986 assert(scip != NULL); 1987 assert(scorecontainer != NULL); 1988 assert(cand != NULL); 1989 assert(SCIPisGE(scip, score, -0.2)); 1990 1991 probindex = SCIPvarGetProbindex(cand->branchvar); 1992 assert(probindex >= 0); 1993 1994 if( scorecontainer->scores[probindex] < -0.5 ) 1995 { 1996 ++scorecontainer->nsetscores; 1997 scorecontainer->scoresum += score; 1998 } 1999 else 2000 { 2001 scorecontainer->scoresum += (score - scorecontainer->scores[probindex]); 2002 } 2003 2004 scorecontainer->scores[probindex] = score; 2005 scorecontainer->downgains[probindex] = downgain; 2006 scorecontainer->upgains[probindex] = upgain; 2007 2008 /* find the point in the sorted array where the new score should be inserted */ 2009 insertpoint = findInsertionPoint(scip, scorecontainer, score, scorecontainer->bestsortedcands, 2010 scorecontainer->nbestsortedcands); 2011 2012 /* insert the current variable (cand) at the position calculated above, returning the candidate that 2013 * was removed at the end of the list; this candidate can be the given candidate for the case that the score does not 2014 * belong to the best ones */ 2015 droppedcandidate = scoreContainerUpdateSortOrder(scorecontainer, cand, insertpoint); 2016 2017 /* remove the warm start info from the dropped candidate */ 2018 if( droppedcandidate != NULL ) 2019 { 2020 SCIP_CALL( candidateFreeWarmStartInfo(scip, droppedcandidate) ); 2021 } 2022 2023 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Stored score <%.9g> for var <%s>.\n", score, SCIPvarGetName(cand->branchvar)); 2024 2025 return SCIP_OKAY; 2026 } 2027 2028 /** Frees the score container and all of its contained arrays. */ 2029 static 2030 SCIP_RETCODE scoreContainerFree( 2031 SCIP* scip, /**< SCIP data structure */ 2032 SCORECONTAINER** scorecontainer /**< score container to free */ 2033 ) 2034 { 2035 assert(scip != NULL); 2036 assert(scorecontainer != NULL); 2037 2038 /* don't free the candidates inside the cands array, as those are handled by the candidate list */ 2039 SCIPfreeBufferArray(scip, &(*scorecontainer)->bestsortedcands); 2040 SCIPfreeBufferArray(scip, &(*scorecontainer)->upgains); 2041 SCIPfreeBufferArray(scip, &(*scorecontainer)->downgains); 2042 SCIPfreeBufferArray(scip, &(*scorecontainer)->scores); 2043 SCIPfreeBuffer(scip, scorecontainer); 2044 2045 return SCIP_OKAY; 2046 } 2047 2048 /* 2049 * Local methods for the logic 2050 */ 2051 2052 /** branches recursively on all given candidates */ 2053 static 2054 SCIP_RETCODE selectVarRecursive( 2055 SCIP* scip, /**< SCIP data structure */ 2056 STATUS* status, /**< current status */ 2057 PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */ 2058 CONFIGURATION* config, /**< the configuration of the branching rule */ 2059 SCIP_SOL* baselpsol, /**< base lp solution */ 2060 DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found */ 2061 BINCONSDATA* binconsdata, /**< container collecting all binary constraints */ 2062 CANDIDATELIST* candidatelist, /**< list of candidates to branch on */ 2063 BRANCHINGDECISION* decision, /**< struct to store the final decision */ 2064 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores */ 2065 LEVEL2DATA* level2data, /**< level 2 LP results data */ 2066 int recursiondepth, /**< remaining recursion depth */ 2067 SCIP_Real lpobjval, /**< LP objective value of current probing node*/ 2068 SCIP_Real baselpobjval, /**< LP objective value of focus node (not probing) */ 2069 SCIP_Longint* niterations, /**< pointer to store the total number of iterations for this variable */ 2070 int* ndeepestcutoffs, /**< pointer to store the total number of cutoffs on the deepest level */ 2071 SCIP_Real* bestgain, /**< pointer to store the best gain found with these candidates */ 2072 SCIP_Real* totalgains, /**< pointer to store the sum over all gains that are valid in both children */ 2073 int* ntotalgains, /**< pointer to store the number of gains summed in totalgains */ 2074 int* ndeepestnodes /**< pointer to store the number of nodes processed in the deepest level */ 2075 #ifdef SCIP_STATISTIC 2076 ,STATISTICS* statistics /**< general statistical data */ 2077 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 2078 ,SCIP_Real* firstscoreptr /**< pointer to store score of first candidate, or NULL */ 2079 ,SCIP_Real* bestscoreptr /**< pointer to store best score, or NULL */ 2080 #endif 2081 ); 2082 2083 /** Adds the given lower bound to the DOMAINREDUCTIONS struct. */ 2084 static 2085 void addLowerBound( 2086 SCIP* scip, /**< SCIP data structure */ 2087 SCIP_VAR* var, /**< The variable the bound should be added for. */ 2088 SCIP_Real lowerbound, /**< The new lower bound for the variable. */ 2089 SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain 2090 * reduction is violated by it. */ 2091 SCIP_Bool simplechange, /**< does the change result from an infeasible child node? */ 2092 DOMAINREDUCTIONS* domainreductions /**< The struct the domain reduction should be added to. */ 2093 #ifdef SCIP_STATISTIC 2094 ,int nproofnodes /**< The number of nodes needed to prove the new lower bound. */ 2095 ,int force /**< should the number of proof nodes be added even if the bound is known already? */ 2096 #endif 2097 ) 2098 { 2099 int varindex; 2100 SCIP_Real basesolutionval; 2101 2102 assert(scip != NULL); 2103 assert(var != NULL); 2104 assert(baselpsol != NULL); 2105 assert(domainreductions != NULL); 2106 #ifdef SCIP_STATISTIC 2107 assert(nproofnodes >= 0); 2108 #endif 2109 2110 /* The arrays inside DOMAINREDUCTIONS are indexed via the problem index. */ 2111 varindex = SCIPvarGetProbindex(var); 2112 2113 lowerbound = SCIPadjustedVarLb(scip, var, lowerbound); 2114 2115 if( SCIPisLT(scip, domainreductions->lowerbounds[varindex], lowerbound) ) 2116 { 2117 /* the new lower bound is stronger (greater) than the old one, 2118 * so we update the bound and number of proof nodes */ 2119 domainreductions->lowerbounds[varindex] = lowerbound; 2120 domainreductions->nchangedvars++; 2121 if( simplechange ) 2122 domainreductions->nsimplebounds++; 2123 #ifdef SCIP_STATISTIC 2124 domainreductions->lowerboundnproofs[varindex] = nproofnodes; 2125 } 2126 else 2127 { 2128 /* if the given lower bound is equal to the old one we take the smaller number of proof nodes */ 2129 if( SCIPisEQ(scip, domainreductions->lowerbounds[varindex], lowerbound) && 2130 (force || domainreductions->lowerboundnproofs[varindex] > nproofnodes) ) 2131 domainreductions->lowerboundnproofs[varindex] = nproofnodes; 2132 #endif 2133 } 2134 2135 /* we get the solution value to check whether the domain reduction is violated in the base LP */ 2136 basesolutionval = SCIPgetSolVal(scip, baselpsol, var); 2137 2138 /* in case the new lower bound is greater than the base solution val and the base solution val is not violated by a 2139 * previously found bound, we increment the nviolatedvars counter and set the baselpviolated flag */ 2140 if( SCIPisFeasGT(scip, domainreductions->lowerbounds[varindex], basesolutionval) 2141 && !domainreductions->baselpviolated[varindex] ) 2142 { 2143 domainreductions->baselpviolated[varindex] = TRUE; 2144 domainreductions->nviolatedvars++; 2145 } 2146 } 2147 2148 /** Adds the given upper bound to the DOMAINREDUCTIONS struct. */ 2149 static 2150 void addUpperBound( 2151 SCIP* scip, /**< SCIP data structure */ 2152 SCIP_VAR* var, /**< The variable the bound should be added for. */ 2153 SCIP_Real upperbound, /**< The new upper bound for the variable. */ 2154 SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain 2155 * reduction is violated by it. */ 2156 SCIP_Bool simplechange, /**< does the change result from an infeasible child node? */ 2157 DOMAINREDUCTIONS* domainreductions /**< The struct the domain reduction should be added to. */ 2158 #ifdef SCIP_STATISTIC 2159 ,int nproofnodes /**< The number of nodes needed to prove the new lower bound. */ 2160 ,int force /**< should the number of proof nodes be added even if the bound is known already? */ 2161 #endif 2162 ) 2163 { 2164 int varindex; 2165 SCIP_Real basesolutionval; 2166 2167 assert(scip != NULL); 2168 assert(var != NULL); 2169 assert(baselpsol != NULL); 2170 assert(domainreductions != NULL); 2171 #ifdef SCIP_STATISTIC 2172 assert(nproofnodes >= 0); 2173 #endif 2174 2175 /* The arrays inside DOMAINREDUCTIONS are indexed via the problem index. */ 2176 varindex = SCIPvarGetProbindex(var); 2177 2178 upperbound = SCIPadjustedVarUb(scip, var, upperbound); 2179 2180 if( SCIPisLE(scip, domainreductions->upperbounds[varindex], upperbound) ) 2181 { 2182 #ifdef SCIP_STATISTIC 2183 /* if the given upper bound is equal to the old one we take the smaller number of proof nodes */ 2184 if( SCIPisEQ(scip, domainreductions->upperbounds[varindex], upperbound) && 2185 (force || domainreductions->upperboundnproofs[varindex] > nproofnodes) ) 2186 domainreductions->upperboundnproofs[varindex] = nproofnodes; 2187 #endif 2188 } 2189 else 2190 { 2191 /* the new upper bound is stronger (smaller) than the old one, 2192 * so we update the bound and number of proof nodes */ 2193 domainreductions->upperbounds[varindex] = upperbound; 2194 domainreductions->nchangedvars++; 2195 if( simplechange ) 2196 domainreductions->nsimplebounds++; 2197 #ifdef SCIP_STATISTIC 2198 domainreductions->upperboundnproofs[varindex] = nproofnodes; 2199 #endif 2200 } 2201 2202 /* We get the solution value to check whether the domain reduction is violated in the base LP */ 2203 basesolutionval = SCIPgetSolVal(scip, baselpsol, var); 2204 2205 /* In case the new upper bound is smaller than the base solution val and the base solution val is not violated by a 2206 * previously found bound, we increment the nviolatedvars counter and set the baselpviolated flag. */ 2207 if( SCIPisFeasLT(scip, domainreductions->upperbounds[varindex], basesolutionval) 2208 && !domainreductions->baselpviolated[varindex] ) 2209 { 2210 domainreductions->baselpviolated[varindex] = TRUE; 2211 domainreductions->nviolatedvars++; 2212 } 2213 } 2214 2215 /** apply the domain reductions from a single struct to another one; this may be used in case one of the two child 2216 * problems of a variable is infeasible 2217 */ 2218 static 2219 void applySingleDeeperDomainReductions( 2220 SCIP* scip, /**< SCIP data structure */ 2221 SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain 2222 * reduction is violated by it. */ 2223 int maxstoredomreds, /**< maximum number of domain reductions to store */ 2224 DOMAINREDUCTIONS* targetdomreds, /**< The target that should be filled with the merged data. */ 2225 DOMAINREDUCTIONS* domreds /**< source domain reductions */ 2226 ) 2227 { 2228 SCIP_VAR** vars; 2229 int nvars; 2230 int i; 2231 2232 assert(scip != NULL); 2233 assert(baselpsol != NULL); 2234 assert(targetdomreds != NULL); 2235 assert(domreds != NULL); 2236 2237 /* as the bounds are tracked for all vars we have to iterate over all vars */ 2238 vars = SCIPgetVars(scip); 2239 nvars = SCIPgetNVars(scip); 2240 2241 assert(vars != NULL); 2242 assert(nvars > 0); 2243 2244 for( i = 0; i < nvars; i++ ) 2245 { 2246 if( targetdomreds->nviolatedvars >= maxstoredomreds ) 2247 return; 2248 2249 #ifdef SCIP_STATISTIC 2250 /* adjust the proof nodes */ 2251 addLowerBound(scip, vars[i], domreds->lowerbounds[i], baselpsol, TRUE, targetdomreds, 2252 domreds->lowerboundnproofs[i], FALSE); 2253 #else 2254 addLowerBound(scip, vars[i], domreds->lowerbounds[i], baselpsol, TRUE, targetdomreds); 2255 #endif 2256 2257 if( targetdomreds->nviolatedvars >= maxstoredomreds ) 2258 return; 2259 2260 #ifdef SCIP_STATISTIC 2261 addUpperBound(scip, vars[i], domreds->upperbounds[i], baselpsol, TRUE, targetdomreds, 2262 domreds->upperboundnproofs[i], FALSE); 2263 #else 2264 addUpperBound(scip, vars[i], domreds->upperbounds[i], baselpsol, TRUE, targetdomreds); 2265 #endif 2266 } 2267 } 2268 2269 /** 2270 * merges the domain reduction data from the two given branching children data into the target parent data 2271 */ 2272 static 2273 void applyDeeperDomainReductions( 2274 SCIP* scip, /**< SCIP data structure */ 2275 SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain 2276 * reduction is violated by it. */ 2277 int maxstoredomreds, /**< maximum number of domain reductions to store */ 2278 DOMAINREDUCTIONS* targetdomreds, /**< The target that should be filled with the merged data. */ 2279 DOMAINREDUCTIONS* downdomreds, /**< One of the source DOMAINREDUCTIONS. */ 2280 DOMAINREDUCTIONS* updomreds /**< The other source DOMAINREDUCTIONS. */ 2281 ) 2282 { 2283 SCIP_VAR** vars; 2284 int nvars; 2285 int i; 2286 2287 assert(scip != NULL); 2288 assert(baselpsol != NULL); 2289 assert(targetdomreds != NULL); 2290 assert(downdomreds != NULL); 2291 assert(updomreds != NULL); 2292 2293 /* as the bounds are tracked for all vars we have to iterate over all vars */ 2294 vars = SCIPgetVars(scip); 2295 nvars = SCIPgetNVars(scip); 2296 2297 assert(vars != NULL); 2298 assert(nvars > 0); 2299 2300 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Combining domain reductions from up and down child.\n"); 2301 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Previous number of changed variable domains: %d\n", 2302 targetdomreds->nchangedvars); 2303 2304 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Number of changed variable domains in up child: %d\n", 2305 updomreds->nchangedvars); 2306 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Number of changed variable domains in down child: %d\n", 2307 downdomreds->nchangedvars); 2308 2309 for( i = 0; i < nvars; i++ ) 2310 { 2311 SCIP_Real newlowerbound; 2312 SCIP_Real newupperbound; 2313 2314 assert(vars[i] != NULL); 2315 2316 if( targetdomreds->nviolatedvars >= maxstoredomreds ) 2317 return; 2318 2319 /* the MIN of both lower bounds represents a valid lower bound at the parent node */ 2320 newlowerbound = MIN(downdomreds->lowerbounds[i], updomreds->lowerbounds[i]); 2321 2322 /* This MIN can now be added via the default add method */ 2323 #ifdef SCIP_STATISTIC 2324 addLowerBound(scip, vars[i], newlowerbound, baselpsol, FALSE, targetdomreds, 2325 MIN(4, downdomreds->lowerboundnproofs[i] + updomreds->lowerboundnproofs[i] + 2), FALSE); 2326 #else 2327 addLowerBound(scip, vars[i], newlowerbound, baselpsol, FALSE, targetdomreds); 2328 #endif 2329 2330 if( targetdomreds->nviolatedvars >= maxstoredomreds ) 2331 return; 2332 2333 /* the MAX of both upper bounds represents a valid upper bound at the parent node */ 2334 newupperbound = MAX(downdomreds->upperbounds[i], updomreds->upperbounds[i]); 2335 2336 /* This MAX can now be added via the default add method */ 2337 #ifdef SCIP_STATISTIC 2338 addUpperBound(scip, vars[i], newupperbound, baselpsol, FALSE, targetdomreds, 2339 MIN(4, downdomreds->upperboundnproofs[i] + updomreds->upperboundnproofs[i] + 2), FALSE); 2340 #else 2341 addUpperBound(scip, vars[i], newupperbound, baselpsol, FALSE, targetdomreds); 2342 #endif 2343 } 2344 2345 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Subsequent number of changed variable domains: %d\n", 2346 targetdomreds->nchangedvars); 2347 } 2348 2349 /** Applies the domain reductions to the current node. */ 2350 static 2351 SCIP_RETCODE applyDomainReductions( 2352 SCIP* scip, /**< SCIP data structure */ 2353 CONFIGURATION* config, /**< the configuration of the branching rule */ 2354 SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain 2355 * reduction is violated by it. */ 2356 DOMAINREDUCTIONS* domreds, /**< The domain reductions that should be applied to the current node. */ 2357 SCIP_Bool* domredcutoff, /**< pointer to store whether a cutoff was found due to domain reductions */ 2358 SCIP_Bool* domred /**< pointer to store whether a domain change was added */ 2359 #ifdef SCIP_STATISTIC 2360 ,STATISTICS* statistics /**< The statistics container. */ 2361 #endif 2362 ) 2363 { 2364 int i; 2365 SCIP_VAR** probvars; 2366 int nprobvars; 2367 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2368 int nboundsadded = 0; 2369 int nboundsaddedvio = 0; 2370 #endif 2371 2372 assert(scip != NULL); 2373 assert(baselpsol != NULL); 2374 assert(domreds != NULL); 2375 assert(domredcutoff != NULL); 2376 assert(domred != NULL); 2377 #ifdef SCIP_STATISTIC 2378 assert(statistics != NULL); 2379 #endif 2380 2381 /* initially we have no cutoff */ 2382 *domredcutoff = FALSE; 2383 2384 /* as the bounds are tracked for all vars we have to iterate over all vars */ 2385 probvars = SCIPgetVars(scip); 2386 nprobvars = SCIPgetNVars(scip); 2387 2388 assert(probvars != NULL); 2389 assert(nprobvars > 0); 2390 2391 if( config->prefersimplebounds && domreds->nsimplebounds == 0 ) 2392 return SCIP_OKAY; 2393 2394 for( i = 0; i < nprobvars && !(*domredcutoff); i++ ) 2395 { 2396 SCIP_VAR* var; 2397 SCIP_Real proposedbound; 2398 SCIP_Real baselpval; 2399 #ifdef SCIP_DEBUG 2400 SCIP_Real oldbound; 2401 #endif 2402 SCIP_Bool infeasible; 2403 SCIP_Bool tightened; 2404 2405 var = probvars[i]; 2406 2407 assert(var != NULL); 2408 2409 baselpval = SCIPgetSolVal(scip, baselpsol, var); 2410 2411 if( SCIPisGT(scip, domreds->lowerbounds[i], SCIPvarGetLbLocal(var)) ) 2412 { 2413 /* apply lower bound */ 2414 #ifdef SCIP_DEBUG 2415 oldbound = SCIPvarGetLbLocal(var); 2416 #endif 2417 proposedbound = domreds->lowerbounds[i]; 2418 2419 if( config->onlyvioldomreds && SCIPisGE(scip, baselpval, proposedbound) ) 2420 continue; 2421 2422 /* add the new bound */ 2423 SCIP_CALL( SCIPtightenVarLb(scip, var, proposedbound, TRUE, &infeasible, &tightened) ); 2424 2425 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2426 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Variable <%s>, old lower bound <%g>, proposed lower bound <%g>, new " 2427 "lower bound <%g>\n", SCIPvarGetName(var), oldbound, proposedbound, SCIPvarGetLbLocal(var)); 2428 #endif 2429 2430 if( infeasible ) 2431 { 2432 /* the domain reduction may result in an empty model (ub < lb) */ 2433 *domredcutoff = TRUE; 2434 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The domain reduction of variable <%s> resulted in an empty " 2435 "model.\n", SCIPvarGetName(var)); 2436 } 2437 else if( tightened ) 2438 { 2439 /* the lb is now strictly greater than before */ 2440 *domred = TRUE; 2441 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2442 nboundsadded++; 2443 #endif 2444 #ifdef SCIP_STATISTIC 2445 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The lower bound of variable <%s> was successfully tightened (%d).\n", 2446 SCIPvarGetName(var), domreds->lowerboundnproofs[i]); 2447 statistics->ndomredproofnodes += domreds->lowerboundnproofs[i]; 2448 #endif 2449 2450 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2451 if( SCIPisLT(scip, baselpval, SCIPvarGetLbLocal(var)) ) 2452 { 2453 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The lower bound of variable <%s> is violated by the base lp " 2454 "value <%g>.\n", SCIPvarGetName(var), baselpval); 2455 2456 nboundsaddedvio++; 2457 } 2458 #endif 2459 } 2460 } 2461 2462 if( SCIPisLT(scip, domreds->upperbounds[i], SCIPvarGetUbLocal(var)) ) 2463 { 2464 /* apply upper bound */ 2465 #ifdef SCIP_DEBUG 2466 oldbound = SCIPvarGetUbLocal(var); 2467 #endif 2468 proposedbound = domreds->upperbounds[i]; 2469 2470 if( config->onlyvioldomreds && SCIPisLE(scip, baselpval, proposedbound) ) 2471 continue; 2472 2473 /* add the new bound */ 2474 SCIP_CALL( SCIPtightenVarUb(scip, var, proposedbound, TRUE, &infeasible, &tightened) ); 2475 2476 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2477 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Variable <%s>, old upper bound <%g>, proposed upper bound <%g>, new " 2478 "upper bound <%g>\n", SCIPvarGetName(var), oldbound, proposedbound, SCIPvarGetUbLocal(var)); 2479 #endif 2480 2481 if( infeasible ) 2482 { 2483 /* the domain reduction may result in an empty model (ub < lb) */ 2484 *domredcutoff = TRUE; 2485 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The domain reduction of variable <%s> resulted in an empty " 2486 "model.\n", SCIPvarGetName(var)); 2487 } 2488 else if( tightened ) 2489 { 2490 /* the ub is now strictly smaller than before */ 2491 *domred = TRUE; 2492 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2493 nboundsadded++; 2494 #endif 2495 #ifdef SCIP_STATISTIC 2496 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The upper bound of variable <%s> was successfully tightened (%d).\n", 2497 SCIPvarGetName(var), domreds->upperboundnproofs[i]); 2498 statistics->ndomredproofnodes += domreds->upperboundnproofs[i]; 2499 #endif 2500 2501 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 2502 if( SCIPisGT(scip, baselpval, SCIPvarGetUbLocal(var)) ) 2503 { 2504 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The upper bound of variable <%s> is violated by the base lp " 2505 "value <%g>.\n", SCIPvarGetName(var), baselpval); 2506 2507 nboundsaddedvio++; 2508 } 2509 #endif 2510 } 2511 } 2512 } 2513 2514 #ifdef SCIP_STATISTIC 2515 statistics->ndomred += nboundsadded; 2516 statistics->ndomredvio += nboundsaddedvio; 2517 #endif 2518 2519 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Truly changed <%d> domains of the problem, <%d> of them are violated by the " 2520 "base lp.\n", nboundsadded, nboundsaddedvio); 2521 return SCIP_OKAY; 2522 } 2523 2524 /** Copies the current LP solution into the given pointer. Needs to be freed after usage! */ 2525 static 2526 SCIP_RETCODE copyCurrentSolution( 2527 SCIP* scip, /**< SCIP data structure */ 2528 SCIP_SOL** lpsol /**< pointer to store the solution into */ 2529 ) 2530 { 2531 assert(scip != NULL); 2532 assert(lpsol != NULL); 2533 2534 /* create temporary solution */ 2535 SCIP_CALL( SCIPcreateLPSol(scip, lpsol, NULL) ); 2536 2537 /* unlink the solution, so that newly solved lps don't have any influence on our copy */ 2538 SCIP_CALL( SCIPunlinkSol(scip, *lpsol) ); 2539 2540 return SCIP_OKAY; 2541 } 2542 2543 /** Executes the branching on a given variable with a given value. */ 2544 static 2545 SCIP_RETCODE branchOnVar( 2546 SCIP* scip /**< SCIP data structure */, 2547 CONFIGURATION* config, /**< config struct with the user configuration */ 2548 BRANCHINGDECISION* decision /**< the decision with all the needed data */ 2549 ) 2550 { 2551 SCIP_VAR* bestvar; 2552 SCIP_Real bestval; 2553 SCIP_NODE* downchild = NULL; 2554 SCIP_NODE* upchild = NULL; 2555 2556 assert(scip != NULL); 2557 assert(decision != NULL); 2558 assert(config != NULL); 2559 2560 bestvar = decision->branchvar; 2561 bestval = decision->branchval; 2562 assert(bestvar != NULL); 2563 2564 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Effective branching on var <%s> with value <%g(%g)>. Old domain: [%g..%g].\n", 2565 SCIPvarGetName(bestvar), bestval, SCIPgetSolVal(scip, NULL, bestvar), SCIPvarGetLbLocal(bestvar), SCIPvarGetUbLocal(bestvar)); 2566 2567 assert(!SCIPisIntegral(scip, bestval)); 2568 2569 /* branch on the given variable */ 2570 assert(SCIPisLT(scip, SCIPvarGetLbLocal(bestvar), bestval)); 2571 assert(SCIPisLT(scip, bestval, SCIPvarGetUbLocal(bestvar))); 2572 SCIP_CALL( SCIPbranchVarVal(scip, bestvar, bestval, &downchild, NULL, &upchild) ); 2573 2574 SCIPdebugMsg(scip, "down child (node %" SCIP_LONGINT_FORMAT "): branching bound change <%s> <= %g\n", 2575 SCIPnodeGetNumber(downchild), SCIPvarGetName(bestvar), SCIPfeasFloor(scip, bestval)); 2576 SCIPdebugMsg(scip, "up child (node %" SCIP_LONGINT_FORMAT "): branching bound change <%s> >= %g\n", 2577 SCIPnodeGetNumber(upchild), SCIPvarGetName(bestvar), SCIPfeasCeil(scip, bestval)); 2578 2579 assert(downchild != NULL); 2580 assert(upchild != NULL); 2581 2582 /* update the lower bounds in the children; we must not do this if columns are missing in the LP 2583 * (e.g., because we are doing branch-and-price) or the problem should be solved exactly */ 2584 if( SCIPallColsInLP(scip) && !SCIPisExactSolve(scip) ) 2585 { 2586 SCIP_Real bestdown = decision->downdb; 2587 SCIP_Bool bestdownvalid = decision->downdbvalid; 2588 SCIP_Real bestup = decision->updb; 2589 SCIP_Bool bestupvalid = decision->updbvalid; 2590 SCIP_Real provedbound = decision->proveddb; 2591 2592 /* update the lower bound for the LPs for further children of both created nodes */ 2593 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) ); 2594 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) ); 2595 2596 if( decision->boundsvalid && config->applychildbounds ) 2597 { 2598 SCIP_VAR** vars; 2599 int nvars; 2600 int i; 2601 2602 assert(decision->downlowerbounds != NULL); 2603 assert(decision->downupperbounds != NULL); 2604 assert(decision->uplowerbounds != NULL); 2605 assert(decision->upupperbounds != NULL); 2606 2607 nvars = SCIPgetNVars(scip); 2608 vars = SCIPgetVars(scip); 2609 2610 assert(nvars == decision->boundssize); 2611 2612 for( i = 0; i < nvars; i++ ) 2613 { 2614 SCIP_VAR* var = vars[i]; 2615 SCIP_Real currentlb; 2616 SCIP_Real currentub; 2617 SCIP_Real newlb = decision->downlowerbounds[i]; 2618 SCIP_Real newub = decision->downupperbounds[i]; 2619 assert(var != NULL); 2620 2621 currentlb = SCIPvarGetLbLocal(var); 2622 currentub = SCIPvarGetUbLocal(var); 2623 2624 /* update the lower bound of the lower child in case it is better than the current one */ 2625 if( SCIPisGT(scip, newlb, currentlb) ) 2626 { 2627 SCIP_CALL( SCIPchgVarLbNode(scip, downchild, var, newlb) ); 2628 2629 SCIPdebugMsg(scip, "down child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> >= %g\n", 2630 SCIPnodeGetNumber(downchild), SCIPvarGetName(var), newlb); 2631 } 2632 2633 /* update the upper bound of the lower child in case it is better than the current one AND it is not the 2634 * branching variable, as its upper bound is already updated 2635 */ 2636 if( SCIPisLT(scip, newub, currentub) && var != bestvar ) 2637 { 2638 SCIP_CALL( SCIPchgVarUbNode(scip, downchild, var, newub) ); 2639 2640 SCIPdebugMsg(scip, "down child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> <= %g\n", 2641 SCIPnodeGetNumber(downchild), SCIPvarGetName(var), newub); 2642 } 2643 2644 newlb = decision->uplowerbounds[i]; 2645 newub = decision->upupperbounds[i]; 2646 2647 /* update the lower bound of the upper child in case it is better than the current one AND it is not the 2648 * branching variable, as its lower bound is already updated 2649 */ 2650 if( SCIPisGT(scip, newlb, currentlb) && var != bestvar) 2651 { 2652 SCIP_CALL( SCIPchgVarLbNode(scip, upchild, var, newlb) ); 2653 2654 SCIPdebugMsg(scip, "up child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> >= %g\n", 2655 SCIPnodeGetNumber(upchild), SCIPvarGetName(var), newlb); 2656 } 2657 2658 /* update the upper bound of the upper child in case it is better than the current one */ 2659 if( SCIPisLT(scip, newub, currentub) ) 2660 { 2661 SCIP_CALL( SCIPchgVarUbNode(scip, upchild, var, newub) ); 2662 2663 SCIPdebugMsg(scip, "up child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> <= %g\n", 2664 SCIPnodeGetNumber(upchild), SCIPvarGetName(var), newub); 2665 } 2666 } 2667 } 2668 } 2669 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, " -> down child's lowerbound: %.9g, estimate: %.9g\n", 2670 SCIPnodeGetLowerbound(downchild), SCIPnodeGetEstimate(downchild)); 2671 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, " -> up child's lowerbound: %.9g, estimate: %.9g\n", 2672 SCIPnodeGetLowerbound(upchild), SCIPnodeGetEstimate(upchild)); 2673 2674 return SCIP_OKAY; 2675 } 2676 2677 /** Get the number of iterations the last LP needed */ 2678 static 2679 SCIP_RETCODE getNIterationsLastLP( 2680 SCIP* scip, /**< SCIP data structure */ 2681 SCIP_Longint* iterations /**< pointer to store the number of iterations */ 2682 ) 2683 { 2684 SCIP_LPI* lpi; 2685 int tmpiter; 2686 2687 assert(scip != NULL); 2688 assert(iterations != NULL); 2689 2690 /* get the LP interface of the last solved LP */ 2691 SCIP_CALL( SCIPgetLPI(scip, &lpi) ); 2692 2693 /* get the number of iterations from the interface */ 2694 SCIP_CALL( SCIPlpiGetIterations(lpi, &tmpiter) ); 2695 2696 *iterations = (SCIP_Longint)tmpiter; 2697 2698 return SCIP_OKAY; 2699 } 2700 2701 /** Creates a new probing node with a new bound for the given candidate and solves the corresponding LP. */ 2702 static 2703 SCIP_RETCODE executeBranching( 2704 SCIP* scip, /**< SCIP data structure */ 2705 CONFIGURATION* config, /**< configuration to control the behavior */ 2706 SCIP_Bool downbranching, /**< the branching direction */ 2707 CANDIDATE* candidate, /**< the candidate to branch on */ 2708 BRANCHINGRESULTDATA* resultdata, /**< pointer to the result data which gets filled with the status */ 2709 SCIP_SOL* baselpsol, /**< the base lp solution */ 2710 DOMAINREDUCTIONS* domreds, /**< struct to store the domain reduction found during propagation */ 2711 STATUS* status /**< status will contain updated lperror and limit fields */ 2712 ) 2713 { 2714 SCIP_Real oldupperbound; 2715 SCIP_Real oldlowerbound; 2716 SCIP_Real newbound; 2717 SCIP_LPSOLSTAT solstat; 2718 SCIP_VAR* branchvar; 2719 SCIP_Real branchval; 2720 2721 assert(scip != NULL); 2722 assert(candidate != NULL); 2723 assert(resultdata != NULL); 2724 assert(status != NULL); 2725 assert(config != NULL); 2726 assert(status != NULL); 2727 2728 branchvar = candidate->branchvar; 2729 branchval = candidate->branchval; 2730 2731 assert(branchvar != NULL); 2732 assert(!SCIPisFeasIntegral(scip, branchval)); 2733 2734 if( downbranching ) 2735 { 2736 /* round the given value down, so that it can be used as the new upper bound */ 2737 newbound = SCIPfeasFloor(scip, branchval); 2738 } 2739 else 2740 { 2741 /* round the given value up, so that it can be used as the new lower bound */ 2742 newbound = SCIPfeasCeil(scip, branchval); 2743 } 2744 2745 oldupperbound = SCIPvarGetUbLocal(branchvar); 2746 oldlowerbound = SCIPvarGetLbLocal(branchvar); 2747 2748 #ifdef SCIP_DEBUG 2749 if( downbranching ) 2750 { 2751 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "DownBranching: Var=<%s>, Proposed upper bound=<%g>, " 2752 "old bounds=[<%g>..<%g>], new bounds=[<%g>..<%g>]\n", SCIPvarGetName(branchvar), newbound, oldlowerbound, 2753 oldupperbound, oldlowerbound, newbound); 2754 } 2755 else 2756 { 2757 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "UpBranching: Var=<%s>, Proposed lower bound=<%g>, " 2758 "old bounds=[<%g>..<%g>], new bounds=[<%g>..<%g>]\n", SCIPvarGetName(branchvar), newbound, oldlowerbound, 2759 oldupperbound, newbound, oldupperbound); 2760 } 2761 #endif 2762 2763 if( (downbranching && newbound < oldlowerbound - 0.5) 2764 || (!downbranching && newbound > oldupperbound + 0.5) ) 2765 { 2766 /* if lb > ub we can cutoff this node */ 2767 resultdata->cutoff = TRUE; 2768 2769 return SCIP_OKAY; 2770 } 2771 2772 assert(!resultdata->cutoff); 2773 2774 SCIP_CALL( SCIPnewProbingNode(scip) ); 2775 2776 if( downbranching ) 2777 { 2778 /* down branching preparations */ 2779 if( SCIPisFeasLT(scip, newbound, oldupperbound) ) 2780 { 2781 /* If the new upper bound is smaller than the old upper bound and also 2782 * greater than (or equal to) the old lower bound, we set the new upper bound. 2783 * oldLowerBound <= newUpperBound < oldUpperBound */ 2784 SCIP_CALL( SCIPchgVarUbProbing(scip, branchvar, newbound) ); 2785 } 2786 } 2787 else 2788 { 2789 /* up branching preparations */ 2790 if( SCIPisFeasGT(scip, newbound, oldlowerbound) ) 2791 { 2792 /* If the new lower bound is greater than the old lower bound and also 2793 * smaller than (or equal to) the old upper bound, we set the new lower bound. 2794 * oldLowerBound < newLowerBound <= oldUpperBound 2795 */ 2796 SCIP_CALL( SCIPchgVarLbProbing(scip, branchvar, newbound) ); 2797 } 2798 } 2799 2800 /* restore the stored LP data (e.g., the basis) from a filtering run */ 2801 if( candidateHasWarmStartInfo(candidate, downbranching) ) 2802 { 2803 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Restoring lp information for %s branch of variable <%s>\n", 2804 downbranching ? "down" : "up", SCIPvarGetName(branchvar)); 2805 SCIP_CALL( candidateLoadWarmStartInfo(scip, candidate, downbranching) ); 2806 } 2807 2808 /* apply domain propagation */ 2809 if( config->propagate ) 2810 { 2811 SCIP_Longint ndomredsfound = 0; 2812 2813 SCIP_CALL( SCIPpropagateProbing(scip, config->maxproprounds, &resultdata->cutoff, &ndomredsfound) ); 2814 2815 if( ndomredsfound > 0 ) 2816 { 2817 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Found %" SCIP_LONGINT_FORMAT " domain reductions via propagation.\n", ndomredsfound); 2818 2819 /* domreds != NULL iff config->usedomainreduction */ 2820 if( domreds != NULL ) 2821 { 2822 int i; 2823 SCIP_VAR** problemvars = SCIPgetVars(scip); 2824 int nproblemvars = SCIPgetNVars(scip); 2825 2826 assert(problemvars != NULL); 2827 2828 assert(config->usedomainreduction); 2829 2830 for( i = 0; i < nproblemvars; i++ ) 2831 { 2832 SCIP_Real lowerbound; 2833 SCIP_Real upperbound; 2834 SCIP_VAR* var = problemvars[i]; 2835 assert(var != NULL); 2836 2837 lowerbound = SCIPvarGetLbLocal(var); 2838 upperbound = SCIPvarGetUbLocal(var); 2839 #ifdef SCIP_STATISTIC 2840 addLowerBound(scip, var, lowerbound, baselpsol, FALSE, domreds, 0, FALSE); 2841 addUpperBound(scip, var, upperbound, baselpsol, FALSE, domreds, 0, FALSE); 2842 #else 2843 addLowerBound(scip, var, lowerbound, baselpsol, FALSE, domreds); 2844 addUpperBound(scip, var, upperbound, baselpsol, FALSE, domreds); 2845 #endif 2846 } 2847 } 2848 } 2849 } 2850 2851 if( !resultdata->cutoff ) 2852 { 2853 /* solve the prepared probing LP */ 2854 SCIP_CALL( SCIPsolveProbingLP(scip, -1, &status->lperror, &resultdata->cutoff) ); 2855 2856 /* store the number of iterations needed */ 2857 SCIP_CALL( getNIterationsLastLP(scip, &resultdata->niterations) ); 2858 2859 solstat = SCIPgetLPSolstat(scip); 2860 assert(solstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY); 2861 2862 /* for us an error occurred, if an error during the solving occurred or the lp could not be solved but was not 2863 * cutoff */ 2864 status->lperror = status->lperror || (solstat == SCIP_LPSOLSTAT_NOTSOLVED && resultdata->cutoff == FALSE); 2865 2866 /* if we seem to have reached a {time, iteration}-limit or the user cancelled the execution, we want to stop 2867 * further calculations and instead return the current calculation state */ 2868 status->limitreached = (solstat == SCIP_LPSOLSTAT_ITERLIMIT) || (solstat == SCIP_LPSOLSTAT_TIMELIMIT); 2869 2870 if( resultdata->cutoff ) 2871 { 2872 resultdata->objval = SCIPinfinity(scip); 2873 resultdata->dualbound = SCIPinfinity(scip); 2874 resultdata->dualboundvalid = TRUE; 2875 } 2876 else if( !status->limitreached && !status->lperror ) 2877 { 2878 SCIP_Bool foundsol = FALSE; 2879 2880 SCIP_CALL( SCIPtryStrongbranchLPSol(scip, &foundsol, &resultdata->cutoff) ); 2881 2882 /* if we have no error, we save the new objective value and the cutoff decision in the resultdata */ 2883 resultdata->objval = SCIPgetLPObjval(scip); 2884 resultdata->dualbound = SCIPgetLPObjval(scip); 2885 resultdata->dualboundvalid = TRUE; 2886 resultdata->cutoff = resultdata->cutoff || SCIPisGE(scip, resultdata->objval, SCIPgetCutoffbound(scip)); 2887 2888 assert(solstat != SCIP_LPSOLSTAT_INFEASIBLE || resultdata->cutoff); 2889 } 2890 } 2891 2892 return SCIP_OKAY; 2893 } 2894 2895 /** Creates a logic or constraint based on the given 'consvars'. This array has to consist of the negated 2896 * versions of the variables present on a cutoff "path" (path means all variables from the root directly 2897 * to the cutoff node). 2898 * Let x_1, ..., x_n be the variables on a path to a cutoff with the branchings x_i <= 1 for all i. 2899 * Summed up the constraints would look like x_1 + ... x_n <= n-1. 2900 * Let y_i = 1 - x_i. Then we have y_1 + ... + y_n >= 1 which is a logic or constraint. 2901 */ 2902 static 2903 SCIP_RETCODE createBinaryConstraint( 2904 SCIP* scip, /**< SCIP data structure */ 2905 CONFIGURATION* config, /**< configuration containing flags changing the behavior */ 2906 SCIP_CONS** constraint, /**< pointer to store the created constraint in */ 2907 char* constraintname, /**< name of the new constraint */ 2908 SCIP_VAR** consvars, /**< array containing the negated binary vars */ 2909 int nconsvars /**< the number of elements in 'consvars' */ 2910 ) 2911 { 2912 SCIP_Bool initial; 2913 SCIP_Bool separate; 2914 SCIP_Bool removable; 2915 SCIP_Bool enforce = FALSE; 2916 SCIP_Bool check = FALSE; 2917 SCIP_Bool propagate = TRUE; 2918 SCIP_Bool local = TRUE; 2919 SCIP_Bool modifiable = FALSE; 2920 SCIP_Bool dynamic = FALSE; 2921 SCIP_Bool stickingatnode = FALSE; 2922 2923 assert(scip != NULL); 2924 assert(config != NULL); 2925 assert(constraint != NULL); 2926 assert(constraintname != NULL); 2927 assert(consvars != NULL); 2928 assert(nconsvars > 0); 2929 2930 initial = (config->addbinconsrow == 2); 2931 separate = (config->addbinconsrow == 1); 2932 removable = (config->addbinconsrow == 1); 2933 2934 /* creating a logic or constraint based on the list of vars in 'consvars'. 2935 * A logic or constraints looks like that: y_1 + ... + y_n >= 1. 2936 */ 2937 SCIP_CALL( SCIPcreateConsLogicor(scip, constraint, constraintname, nconsvars, consvars, initial, separate, enforce, 2938 check, propagate, local, modifiable, dynamic, removable, stickingatnode) ); 2939 return SCIP_OKAY; 2940 } 2941 2942 /** 2943 * Create a name for the binary constraint. 2944 */ 2945 static 2946 void createBinaryConstraintName( 2947 SCIP_VAR** binaryvars, /**< the variables contained in the constraint */ 2948 int nbinaryvars, /**< the number of elements in 'binaryvars' */ 2949 char* constraintname /**< the char pointer to store the name in */ 2950 ) 2951 { 2952 int i; 2953 2954 assert(binaryvars != NULL); 2955 assert(nbinaryvars > 0); 2956 assert(constraintname != NULL); 2957 assert(binaryvars[0] != NULL); 2958 2959 (void) SCIPsnprintf(constraintname, SCIP_MAXSTRLEN, "lookahead_bin_%s", SCIPvarGetName(binaryvars[0])); 2960 2961 for( i = 1; i < nbinaryvars; i++ ) 2962 { 2963 size_t oldlen; 2964 SCIP_VAR* var = binaryvars[i]; 2965 assert(var != NULL); 2966 2967 oldlen = strlen(constraintname); 2968 (void) strncat(constraintname, "_", SCIP_MAXSTRLEN-oldlen); 2969 (void) strncat(constraintname, SCIPvarGetName(var), SCIP_MAXSTRLEN-oldlen-1); 2970 } 2971 } 2972 2973 /** 2974 * Add the constraints found during the lookahead branching. 2975 * The implicit binary bounds were found when two or more consecutive branchings of binary variables were cutoff. Then these 2976 * branching constraints can be combined into a single 'binary constraint'. 2977 */ 2978 static 2979 SCIP_RETCODE addBinaryConstraint( 2980 SCIP* scip, /**< SCIP data structure */ 2981 CONFIGURATION* config, /**< the configuration of the branching rule */ 2982 BINCONSDATA* binconsdata, /**< collected binary constraints */ 2983 SCIP_SOL* baselpsol /**< the original lp solution, used to check the violation of the constraint */ 2984 #ifdef SCIP_STATISTIC 2985 ,STATISTICS* statistics /**< statistics data */ 2986 #endif 2987 ) 2988 { 2989 assert(scip != NULL); 2990 assert(config != NULL); 2991 assert(binconsdata != NULL); 2992 assert(baselpsol != NULL); 2993 assert(binconsdata->binaryvars != NULL); 2994 assert(binconsdata->binaryvars->nbinaryvars > 0); 2995 2996 /* if we only have one var for the constraint, we can ignore it as it is already added as a domain reduction. */ 2997 if( binconsdata->binaryvars->nbinaryvars > 1 ) 2998 { 2999 int i; 3000 SCIP_VAR** negatedvars; 3001 SCIP_Real lhssum = 0.0; 3002 SCIP_Bool violated; 3003 3004 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Adding binary constraint for <%i> vars.\n", 3005 binconsdata->binaryvars->nbinaryvars); 3006 3007 SCIP_CALL( SCIPallocBufferArray(scip, &negatedvars, binconsdata->binaryvars->nbinaryvars) ); 3008 3009 for( i = 0; i < binconsdata->binaryvars->nbinaryvars; i++ ) 3010 { 3011 SCIP_VAR* var = binconsdata->binaryvars->binaryvars[i]; 3012 assert(var != NULL); 3013 assert(SCIPvarIsBinary(var)); 3014 3015 SCIP_CALL( SCIPgetNegatedVar(scip, var, &negatedvars[i]) ); 3016 lhssum += SCIPgetSolVal(scip, baselpsol, negatedvars[i]); 3017 } 3018 3019 violated = (lhssum < 1); 3020 3021 if( config->addnonviocons || violated ) 3022 { 3023 SCIP_CALL( constraintListAppend(scip, binconsdata->conslist, negatedvars, 3024 binconsdata->binaryvars->nbinaryvars, violated) ); 3025 3026 /* the constraint we will be building is a logic or: we have a list of binary variables that were 3027 * cutoff while we branched on with >= 1. So we have the constraint: x_1 + ... + x_n <= n-1. 3028 * Let y = (1-x), then we have an equivalent formulation: y_1 + ... + y_n >= 1. If the base lp 3029 * is violating this constraint we count this for our number of violated constraints and bounds. */ 3030 if( violated ) 3031 binconsdata->conslist->nviolatedcons++; 3032 } 3033 3034 SCIPfreeBufferArray(scip, &negatedvars); 3035 } 3036 #ifdef SCIP_STATISTIC 3037 else 3038 { 3039 assert(statistics != NULL); 3040 statistics->ndomredcons++; 3041 } 3042 #endif 3043 3044 return SCIP_OKAY; 3045 } 3046 3047 /** applies the binary constraints to the original problem. */ 3048 static 3049 SCIP_RETCODE applyBinaryConstraints( 3050 SCIP* scip, /**< SCIP data structure */ 3051 SCIP_NODE* basenode, /**< original branching node */ 3052 CONSTRAINTLIST* conslist, /**< list of constraints to be added */ 3053 CONFIGURATION* config, /**< the configuration of the branching rule */ 3054 SCIP_Bool* consadded, /**< pointer to store whether at least one constraint was added */ 3055 SCIP_Bool* cutoff, /**< pointer to store whether the original problem was made infeasible */ 3056 SCIP_Bool* boundchange /**< pointer to store whether a bound change has been applied by adding the 3057 * constraint as a clique */ 3058 #ifdef SCIP_STATISTIC 3059 ,STATISTICS* statistics /**< statistics data */ 3060 #endif 3061 ) 3062 { 3063 int nconsadded = 0; 3064 int i; 3065 #ifdef SCIP_STATISTIC 3066 int nvioconsadded = 0; 3067 3068 assert(statistics != NULL); 3069 #endif 3070 assert(basenode != NULL); 3071 assert(conslist != NULL); 3072 assert(config != NULL); 3073 assert(consadded != NULL); 3074 assert(cutoff != NULL); 3075 assert(boundchange != NULL); 3076 3077 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "processing %d binary constraints.\n", conslist->nelements); 3078 3079 if( conslist->nelements == 0 ) 3080 return SCIP_OKAY; 3081 3082 for( i = 0; i < conslist->nelements; i++ ) 3083 { 3084 SCIP_VAR** vars = conslist->consvars[i]; 3085 int nvars = conslist->nconsvars[i]; 3086 int v; 3087 #ifdef SCIP_STATISTIC 3088 SCIP_Bool violated = conslist->violated[i]; 3089 #endif 3090 3091 assert(vars != NULL); 3092 3093 for( v = 0; v < nvars; ++v ) 3094 { 3095 assert(vars[v] != NULL); 3096 assert(SCIPvarIsBinary(vars[v])); 3097 3098 if( SCIPvarGetLbLocal(vars[v]) > 0.5 ) 3099 break; 3100 } 3101 3102 /* no variable is fixed to 1 yet, so constraint is not redundant */ 3103 if( v == nvars ) 3104 { 3105 SCIP_CONS* constraint; 3106 char constraintname[SCIP_MAXSTRLEN]; 3107 3108 /* create a name for the new constraint */ 3109 createBinaryConstraintName(vars, nvars, constraintname); 3110 /* create the constraint with the freshly created name */ 3111 SCIP_CALL( createBinaryConstraint(scip, config, &constraint, constraintname, vars, nvars) ); 3112 3113 #ifdef PRINTNODECONS 3114 SCIPinfoMessage(scip, NULL, "Created constraint:\n"); 3115 SCIP_CALL( SCIPprintCons(scip, constraint, NULL) ); 3116 SCIPinfoMessage(scip, NULL, "\n"); 3117 #endif 3118 /* add the constraint to the given node */ 3119 SCIP_CALL( SCIPaddConsNode(scip, basenode, constraint, NULL) ); 3120 3121 nconsadded++; 3122 3123 #ifdef SCIP_STATISTIC 3124 if( violated ) 3125 nvioconsadded++; 3126 #endif 3127 3128 /* release the constraint, as it is no longer needed */ 3129 SCIP_CALL( SCIPreleaseCons(scip, &constraint) ); 3130 3131 /* a 2-variable logicor constraint can be expressend as a clique on the negated variables; 3132 * add it to the clique table if we are at the root node */ 3133 if( nvars == 2 && config->addclique && SCIPgetNNodes(scip) == 1 ) 3134 { 3135 SCIP_Bool* values; 3136 SCIP_Bool infeasible; 3137 int nbdchgs; 3138 3139 SCIP_CALL( SCIPallocClearBufferArray(scip, &values, nvars) ); 3140 3141 /* a two-variable logicor constraint x + y >= 1 yields the implication x == 0 -> y == 1, and is represented 3142 * by the clique inequality ~x + ~y <= 1 3143 */ 3144 SCIP_CALL( SCIPaddClique(scip, vars, values, nvars, FALSE, &infeasible, &nbdchgs) ); 3145 3146 #ifdef SCIP_STATISTIC 3147 statistics->ncliquesadded++; 3148 #endif 3149 3150 if( infeasible ) 3151 *cutoff = TRUE; 3152 3153 if( nbdchgs > 0 ) 3154 *boundchange = TRUE; 3155 3156 SCIPfreeBufferArray(scip, &values); 3157 } 3158 } 3159 } 3160 3161 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "added %d/%d binary constraints.\n", nconsadded, conslist->nelements); 3162 3163 if( nconsadded > 0 ) 3164 { 3165 *consadded = TRUE; 3166 3167 #ifdef SCIP_STATISTIC 3168 statistics->nbinconst += nconsadded; 3169 statistics->nbinconstvio += nvioconsadded; 3170 #endif 3171 } 3172 3173 return SCIP_OKAY; 3174 } 3175 3176 /** checks whether the given bounds are still the bounds of the given variable */ 3177 static 3178 SCIP_Bool areBoundsChanged( 3179 SCIP* scip, /**< SCIP data structure */ 3180 SCIP_VAR* var, /**< variable to check the bounds of */ 3181 SCIP_Real lowerbound, /**< reference lower bound */ 3182 SCIP_Real upperbound /**< reference upper bound */ 3183 ) 3184 { 3185 assert(scip != NULL); 3186 assert(var != NULL); 3187 assert(SCIPisFeasIntegral(scip, lowerbound)); 3188 assert(SCIPisFeasIntegral(scip, upperbound)); 3189 assert(!SCIPisEQ(scip, lowerbound, upperbound)); 3190 assert(SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS); 3191 3192 /* due to roundings the value might have changed slightly without an actual influence on the integral value */ 3193 return SCIPvarGetLbLocal(var) > lowerbound + 0.5 || SCIPvarGetUbLocal(var) < upperbound - 0.5; 3194 } 3195 3196 /** Checks whether the branching rule should continue or terminate with the currently gathered data */ 3197 static 3198 SCIP_Bool isBranchFurther( 3199 STATUS* status, /**< current status */ 3200 SCIP_Bool checkdomreds /**< should domain reductions be checked? */ 3201 ) 3202 { 3203 assert(status != NULL); 3204 3205 return !status->lperror && !status->cutoff && !status->limitreached 3206 && !status->maxnconsreached && (!checkdomreds || !status->domred); 3207 } 3208 3209 /** Checks whether the branching rule should continue or terminate with the currently gathered data. Additionally decrements 3210 * the given loopcounter. This is needed to better emulate the behavior of FSB by LAB with a depth of 1. */ 3211 static 3212 SCIP_Bool isBranchFurtherLoopDecrement( 3213 STATUS* status, /**< current status */ 3214 int* loopcounter /**< the counter to decrement */ 3215 ) 3216 { 3217 SCIP_Bool branchfurther; 3218 3219 assert(status != NULL); 3220 assert(loopcounter != NULL); 3221 3222 branchfurther = isBranchFurther(status, FALSE); 3223 3224 if( !branchfurther ) 3225 (*loopcounter)--; 3226 3227 return branchfurther; 3228 } 3229 3230 /** determines whether the previous LAB result of a variable should be reused */ 3231 static 3232 SCIP_Bool isUseOldBranching( 3233 SCIP* scip, /**< SCIP data structure */ 3234 PERSISTENTDATA* persistent, /**< data storage over multiple calls to the rule */ 3235 CONFIGURATION* config, /**< the configuration of the branching rule */ 3236 SCIP_VAR* branchvar /**< variable to check */ 3237 ) 3238 { 3239 assert(scip != NULL); 3240 assert(config != NULL); 3241 assert(branchvar != NULL); 3242 3243 /* an old branching can be reused, if we are still at the same node and just a few LPs were solved in between */ 3244 if( config->inscoring ) 3245 { 3246 return SCIPgetVarStrongbranchNode(scip, branchvar) == SCIPgetNNodes(scip) 3247 && SCIPgetVarStrongbranchLPAge(scip, branchvar) < config->reevalagefsb; 3248 } 3249 else 3250 { 3251 return persistent->lastbranchid[SCIPvarGetProbindex(branchvar)] == SCIPgetNNodes(scip) 3252 && SCIPgetNLPs(scip) - persistent->lastbranchnlps[SCIPvarGetProbindex(branchvar)] < config->reevalage; 3253 } 3254 } 3255 3256 /** retrieves previous LAB result for the given variable */ 3257 static 3258 SCIP_RETCODE getOldBranching( 3259 SCIP* scip, /**< SCIP data structure */ 3260 PERSISTENTDATA* persistent, /**< data storage over multiple calls to the rule */ 3261 CONFIGURATION* config, /**< the configuration of the branching rule */ 3262 SCIP_VAR* branchvar, /**< variable to get previous results for */ 3263 BRANCHINGRESULTDATA* downbranchingresult,/**< pointer to store the previous down result in */ 3264 BRANCHINGRESULTDATA* upbranchingresult, /**< pointer to store the previous up result in */ 3265 SCIP_Real* oldlpobjval /**< pointer to store the previous base lp objval in */ 3266 ) 3267 { 3268 assert(scip != NULL); 3269 assert(persistent != NULL); 3270 assert(branchvar != NULL); 3271 assert(downbranchingresult != NULL); 3272 assert(upbranchingresult != NULL); 3273 assert(oldlpobjval != NULL); 3274 3275 if( config->inscoring ) 3276 { 3277 SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchvar, &downbranchingresult->dualbound, &upbranchingresult->dualbound, 3278 &downbranchingresult->dualboundvalid, &upbranchingresult->dualboundvalid, NULL, oldlpobjval) ); 3279 downbranchingresult->objval = downbranchingresult->dualbound; 3280 upbranchingresult->objval = upbranchingresult->dualbound; 3281 } 3282 else 3283 { 3284 int varindex = SCIPvarGetProbindex(branchvar); 3285 3286 branchingResultDataCopy(persistent->lastbranchdownres[varindex], downbranchingresult); 3287 branchingResultDataCopy(persistent->lastbranchupres[varindex], upbranchingresult); 3288 *oldlpobjval = persistent->lastbranchlpobjval[varindex]; 3289 } 3290 3291 #ifdef SCIP_DEBUG 3292 { 3293 SCIP_Real downgain; 3294 SCIP_Real upgain; 3295 3296 downgain = MAX(downbranchingresult->dualbound - *oldlpobjval, 0); 3297 upgain = MAX(upbranchingresult->dualbound - *oldlpobjval, 0); 3298 3299 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Lookahead branching on variable <%s> already performed (lpage=%" 3300 SCIP_LONGINT_FORMAT ", down=%.9g (%+g), up=%.9g (%+g))\n", SCIPvarGetName(branchvar), 3301 SCIPgetNLPs(scip) - persistent->lastbranchnlps[SCIPvarGetProbindex(branchvar)], 3302 downbranchingresult->dualbound, downgain, upbranchingresult->dualbound, upgain); 3303 } 3304 #endif 3305 3306 return SCIP_OKAY; 3307 } 3308 3309 /** stores the LAB result for use in a later call to the branching rule */ 3310 static 3311 SCIP_RETCODE updateOldBranching( 3312 SCIP* scip, /**< SCIP data structure */ 3313 PERSISTENTDATA* persistent, /**< data storage over multiple calls to the rule */ 3314 CONFIGURATION* config, /**< the configuration of the branching rule */ 3315 SCIP_VAR* branchvar, /**< variable to store previous results for */ 3316 SCIP_Real branchval, /**< the value of branchvar */ 3317 BRANCHINGRESULTDATA* downbranchingresult,/**< down branching result to store */ 3318 BRANCHINGRESULTDATA* upbranchingresult, /**< up branching result to store */ 3319 SCIP_Real lpobjval /**< base lp obj val */ 3320 ) 3321 { 3322 assert(scip != NULL); 3323 assert(persistent != NULL); 3324 assert(branchvar != NULL); 3325 assert(downbranchingresult != NULL); 3326 assert(upbranchingresult != NULL); 3327 3328 if( config->inscoring ) 3329 { 3330 SCIP_Longint niterations = downbranchingresult->niterations + upbranchingresult->niterations; 3331 3332 SCIP_CALL( SCIPsetVarStrongbranchData(scip, branchvar, lpobjval, branchval, downbranchingresult->dualbound, 3333 upbranchingresult->dualbound, downbranchingresult->dualboundvalid, upbranchingresult->dualboundvalid, niterations, 3334 INT_MAX) ); 3335 } 3336 else 3337 { 3338 int varindex = SCIPvarGetProbindex(branchvar); 3339 3340 branchingResultDataCopy(downbranchingresult, persistent->lastbranchdownres[varindex]); 3341 branchingResultDataCopy(upbranchingresult, persistent->lastbranchupres[varindex]); 3342 persistent->lastbranchlpobjval[varindex] = lpobjval; 3343 persistent->lastbranchid[varindex] = SCIPgetNNodes(scip); 3344 persistent->lastbranchnlps[varindex] = SCIPgetNLPs(scip); 3345 } 3346 3347 return SCIP_OKAY; 3348 } 3349 3350 /** calculates the FSB scores for the given candidates */ 3351 static 3352 SCIP_RETCODE getFSBResult( 3353 SCIP* scip, /**< SCIP data structure */ 3354 STATUS* status, /**< current status */ 3355 PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */ 3356 CONFIGURATION* config, /**< the configuration of the branching rule */ 3357 SCIP_SOL* baselpsol, /**< base lp solution */ 3358 DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */ 3359 BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */ 3360 CANDIDATELIST* candidatelist, /**< list containing all candidates to consider */ 3361 BRANCHINGDECISION* decision, /**< struct to store the final decision */ 3362 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */ 3363 LEVEL2DATA* level2data, /**< level 2 LP results data */ 3364 SCIP_Real lpobjval /**< base LP objective value */ 3365 #ifdef SCIP_STATISTIC 3366 ,STATISTICS* statistics /**< general statistical data */ 3367 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 3368 #endif 3369 ) 3370 { 3371 assert(scip != NULL); 3372 assert(config != NULL); 3373 assert(candidatelist != NULL); 3374 assert(status != NULL); 3375 assert(scorecontainer != NULL); 3376 assert(SCIPinProbing(scip)); 3377 assert(SCIPgetProbingDepth(scip) >= 0 && SCIPgetProbingDepth(scip) < config->recursiondepth); 3378 3379 /* inform configuration that we are in scoring mode now */ 3380 config->inscoring = TRUE; 3381 3382 #ifdef SCIP_STATISTIC 3383 SCIP_CALL( selectVarRecursive(scip, status, persistent, config, baselpsol, domainreductions, 3384 binconsdata, candidatelist, decision, scorecontainer, level2data, 1, 3385 lpobjval, lpobjval, NULL, NULL, NULL, NULL, NULL, NULL, 3386 statistics, localstats, NULL, NULL) ); 3387 #else 3388 SCIP_CALL( selectVarRecursive(scip, status, persistent, config, baselpsol, domainreductions, 3389 binconsdata, candidatelist, decision, scorecontainer, level2data, 1, 3390 lpobjval, lpobjval, NULL, NULL, NULL, NULL, NULL, NULL) ); 3391 #endif 3392 3393 /* inform configuration that we leave scoring mode now */ 3394 config->inscoring = FALSE; 3395 3396 return SCIP_OKAY; 3397 } 3398 3399 #ifdef SCIP_DEBUG 3400 /** prints the given candidate list */ 3401 static 3402 void printCandidates( 3403 SCIP* scip, /**< SCIP data structure */ 3404 SCIP_VERBLEVEL lvl, /**< verbosity level to print the list in */ 3405 CANDIDATELIST* candidatelist /**< the list to be printed */ 3406 ) 3407 { 3408 int ncands; 3409 int i; 3410 3411 assert(scip != NULL); 3412 assert(candidatelist != NULL); 3413 3414 ncands = candidatelist->ncandidates; 3415 3416 LABdebugMessagePrint(scip, lvl, "["); 3417 3418 for( i = 0; i < ncands; i++ ) 3419 { 3420 CANDIDATE* cand = candidatelist->candidates[i]; 3421 3422 assert(cand != NULL); 3423 assert(cand->branchvar != NULL); 3424 3425 LABdebugMessagePrint(scip, lvl, "%s", SCIPvarGetName(cand->branchvar)); 3426 if(i != ncands-1) 3427 { 3428 LABdebugMessagePrint(scip, lvl, ", "); 3429 } 3430 } 3431 LABdebugMessagePrint(scip, lvl, "]\n"); 3432 } 3433 #endif 3434 3435 /** calculates the score based on the down and up branching result */ 3436 static 3437 SCIP_Real calculateScoreFromResult( 3438 SCIP* scip, /**< SCIP data structure */ 3439 SCIP_VAR* branchvar, /**< variable to get the score for */ 3440 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3441 BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */ 3442 SCIP_Real lpobjval /**< objective value to get difference to as gain */ 3443 ) 3444 { 3445 SCIP_Real score; 3446 SCIP_Real downgain = SCIPsumepsilon(scip); 3447 SCIP_Real upgain = SCIPsumepsilon(scip); 3448 3449 assert(scip != NULL); 3450 assert(branchvar != NULL); 3451 assert(downbranchingresult != NULL); 3452 assert(upbranchingresult != NULL); 3453 3454 /* the gain is the difference of the dualbound of a child and the reference objective value; 3455 * by bounding it by zero we are safe from numerical troubles 3456 */ 3457 if( !downbranchingresult->cutoff ) 3458 downgain = MAX(downgain, downbranchingresult->dualbound - lpobjval); 3459 if( !upbranchingresult->cutoff ) 3460 upgain = MAX(upgain, upbranchingresult->dualbound - lpobjval); 3461 3462 downgain = 100.0 * downgain; 3463 upgain = 100.0 * upgain; 3464 3465 /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat 3466 * realistic gain for the infeasible child; 3467 * if both children are infeasible we just reset the initial zero values again 3468 */ 3469 if( downbranchingresult->cutoff ) 3470 downgain = 2 * upgain; 3471 if( upbranchingresult->cutoff ) 3472 upgain = 2 * downgain; 3473 3474 score = SCIPgetBranchScore(scip, branchvar, downgain, upgain); 3475 3476 return score; 3477 } 3478 3479 /** calculates the score based on the down and up branching result */ 3480 static 3481 SCIP_Real calculateScoreFromResult2( 3482 SCIP* scip, /**< SCIP data structure */ 3483 SCIP_VAR* branchvar, /**< variable to get the score for */ 3484 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3485 BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */ 3486 SCIP_Real lpobjval /**< objective value to get difference to as gain */ 3487 ) 3488 { 3489 SCIP_Real lpscore; 3490 SCIP_Real dbscore; 3491 SCIP_Real score; 3492 SCIP_Real downgain = SCIPsumepsilon(scip); 3493 SCIP_Real upgain = SCIPsumepsilon(scip); 3494 3495 assert(scip != NULL); 3496 assert(branchvar != NULL); 3497 assert(downbranchingresult != NULL); 3498 assert(upbranchingresult != NULL); 3499 3500 /* the gain is the difference of the dualbound of a child and the reference objective value; 3501 * by bounding it by zero we are safe from numerical troubles 3502 */ 3503 if( !downbranchingresult->cutoff ) 3504 downgain = MAX(downgain, downbranchingresult->objval - lpobjval); 3505 if( !upbranchingresult->cutoff ) 3506 upgain = MAX(upgain, upbranchingresult->objval - lpobjval); 3507 3508 downgain = 100.0 * downgain; 3509 upgain = 100.0 * upgain; 3510 3511 /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat 3512 * realistic gain for the infeasible child; 3513 * if both children are infeasible we just reset the initial zero values again 3514 */ 3515 if( downbranchingresult->cutoff ) 3516 downgain = 2 * upgain; 3517 if( upbranchingresult->cutoff ) 3518 upgain = 2 * downgain; 3519 3520 lpscore = SCIPgetBranchScore(scip, branchvar, downgain, upgain); 3521 3522 /* the gain is the difference of the dualbound of a child and the reference objective value; 3523 * by bounding it by zero we are safe from numerical troubles 3524 */ 3525 if( !downbranchingresult->cutoff ) 3526 downgain = MAX(SCIPsumepsilon(scip), downbranchingresult->dualbound - lpobjval); /*lint !e666*/ 3527 if( !upbranchingresult->cutoff ) 3528 upgain = MAX(SCIPsumepsilon(scip), upbranchingresult->dualbound - lpobjval); /*lint !e666*/ 3529 3530 downgain = 100.0 * downgain; 3531 upgain = 100.0 * upgain; 3532 3533 /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat 3534 * realistic gain for the infeasible child; 3535 * if both children are infeasible we just reset the initial zero values again 3536 */ 3537 if( downbranchingresult->cutoff ) 3538 downgain = 2 * upgain; 3539 if( upbranchingresult->cutoff ) 3540 upgain = 2 * downgain; 3541 3542 dbscore = SCIPgetBranchScore(scip, branchvar, downgain, upgain); 3543 3544 score = SCIPgetBranchScore(scip, branchvar, lpscore, dbscore); 3545 3546 return score; 3547 } 3548 3549 /** calculates the score based on the down and up branching scores */ 3550 static 3551 SCIP_Real calculateScoreFromDeeperscore( 3552 SCIP* scip, /**< SCIP data structure */ 3553 SCIP_VAR* branchvar, /**< variable to get the score for */ 3554 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3555 BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */ 3556 ) 3557 { 3558 SCIP_Real score; 3559 SCIP_Real downscore; 3560 SCIP_Real upscore; 3561 3562 assert(scip != NULL); 3563 assert(branchvar != NULL); 3564 assert(downbranchingresult != NULL); 3565 assert(upbranchingresult != NULL); 3566 3567 assert(downbranchingresult->deeperscore >= -0.2 || downbranchingresult->cutoff || SCIPisStopped(scip)); 3568 assert(upbranchingresult->deeperscore >= -0.2 || upbranchingresult->cutoff || SCIPisStopped(scip)); 3569 3570 downscore = sqrt(downbranchingresult->deeperscore); 3571 upscore = sqrt(upbranchingresult->deeperscore); 3572 3573 downscore = MAX(downscore, SCIPsumepsilon(scip)); /*lint !e666*/ 3574 upscore = MAX(upscore, SCIPsumepsilon(scip)); /*lint !e666*/ 3575 3576 if( downbranchingresult->cutoff ) 3577 downscore = 2 * upscore; 3578 if( upbranchingresult->cutoff ) 3579 upscore = 2 * downscore; 3580 3581 score = SCIPgetBranchScore(scip, branchvar, downscore, upscore); 3582 3583 return score; 3584 } 3585 3586 /** calculates the score based on the down and up branching scores */ 3587 static 3588 SCIP_Real calculateScoreFromDeeperscoreAndCutoffs( 3589 SCIP* scip, /**< SCIP data structure */ 3590 SCIP_VAR* branchvar, /**< variable to get the score for */ 3591 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3592 BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */ 3593 ) 3594 { 3595 SCIP_Real score; 3596 SCIP_Real downscore; 3597 SCIP_Real upscore; 3598 SCIP_Real totaldowngains; 3599 SCIP_Real totalupgains; 3600 SCIP_Real nlowestlevelcutoffs; 3601 int ntotaldowngains; 3602 int ntotalupgains; 3603 3604 assert(scip != NULL); 3605 assert(branchvar != NULL); 3606 assert(downbranchingresult != NULL); 3607 assert(upbranchingresult != NULL); 3608 3609 assert(downbranchingresult->deeperscore >= -0.2 || downbranchingresult->cutoff || SCIPisStopped(scip)); 3610 assert(upbranchingresult->deeperscore >= -0.2 || upbranchingresult->cutoff || SCIPisStopped(scip)); 3611 3612 nlowestlevelcutoffs = (1.0 * downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs)/(MAX(1,downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes)); 3613 totaldowngains = downbranchingresult->totalgains; 3614 totalupgains = upbranchingresult->totalgains; 3615 ntotaldowngains = MAX(1, downbranchingresult->ntotalgains); 3616 ntotalupgains = MAX(1, upbranchingresult->ntotalgains); 3617 3618 downscore = sqrt(downbranchingresult->deeperscore); 3619 upscore = sqrt(upbranchingresult->deeperscore); 3620 3621 downscore = MAX(downscore, SCIPsumepsilon(scip)); /*lint !e666*/ 3622 upscore = MAX(upscore, SCIPsumepsilon(scip)); /*lint !e666*/ 3623 3624 if( downbranchingresult->cutoff ) 3625 downscore = 2 * upscore; 3626 if( upbranchingresult->cutoff ) 3627 upscore = 2 * downscore; 3628 3629 score = SCIPgetBranchScore(scip, branchvar, downscore, upscore); 3630 3631 downscore = sqrt(totaldowngains/ntotaldowngains); 3632 upscore = sqrt(totalupgains/ntotalupgains); 3633 3634 downscore = MAX(downscore, SCIPsumepsilon(scip)); /*lint !e666*/ 3635 upscore = MAX(upscore, SCIPsumepsilon(scip)); /*lint !e666*/ 3636 3637 score += SCIPgetBranchScore(scip, branchvar, downscore, upscore)*nlowestlevelcutoffs; 3638 3639 return score; 3640 } 3641 3642 /** calculates the combined gain, weighted with parameters given by the user configuration */ 3643 static 3644 SCIP_Real calculateWeightedGain( 3645 SCIP* scip, /**< SCIP data structure */ 3646 CONFIGURATION* config, /**< LAB configuration */ 3647 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3648 BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */ 3649 SCIP_Real lpobjval /**< objective value to get difference to as gain */ 3650 ) 3651 { 3652 SCIP_Real downgain = 0.0; 3653 SCIP_Real upgain = 0.0; 3654 3655 assert(config != NULL); 3656 assert(downbranchingresult != NULL); 3657 assert(upbranchingresult != NULL); 3658 3659 /* the gain is the difference of the dualbound of a child and the reference objective value; 3660 * by bounding it by zero we are safe from numerical troubles 3661 */ 3662 if( !downbranchingresult->cutoff ) 3663 downgain = MAX(0, downbranchingresult->dualbound - lpobjval); 3664 if( !upbranchingresult->cutoff ) 3665 upgain = MAX(0, upbranchingresult->dualbound - lpobjval); 3666 3667 if( config->scoringfunction == 's' ) 3668 { 3669 if( downbranchingresult->cutoff ) 3670 downgain = SCIPinfinity(scip); 3671 if( upbranchingresult->cutoff ) 3672 upgain = SCIPinfinity(scip); 3673 } 3674 else 3675 { 3676 /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat 3677 * realistic gain for the infeasible child; 3678 * if both children are infeasible we just reset the initial zero values again 3679 */ 3680 if( downbranchingresult->cutoff ) 3681 downgain = upgain; 3682 if( upbranchingresult->cutoff ) 3683 upgain = downgain; 3684 } 3685 3686 return config->minweight * MIN(downgain, upgain) + (1.0 - config->minweight) * MAX(downgain, upgain); 3687 } 3688 3689 /** calculates the score as mentioned in the lookahead branching paper by Glankwamdee and Linderoth; 3690 * their score scales the number of cutoffs on the last layer of a 2-level temporary branching tree with the average gain of 3691 * every last level problem; together with the best gain for each branch of a variable we get the final score 3692 */ 3693 static 3694 SCIP_Real calculateScaledCutoffScore( 3695 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3696 BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */ 3697 ) 3698 { 3699 SCIP_Real bestdowngain; 3700 SCIP_Real bestupgain; 3701 SCIP_Real totaldowngains; 3702 SCIP_Real totalupgains; 3703 int nlowestlevelcutoffs; 3704 int ntotaldowngains; 3705 int ntotalupgains; 3706 3707 assert(downbranchingresult != NULL); 3708 assert(upbranchingresult != NULL); 3709 3710 nlowestlevelcutoffs = downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs; 3711 bestdowngain = downbranchingresult->bestgain; 3712 bestupgain = upbranchingresult->bestgain; 3713 totaldowngains = downbranchingresult->totalgains; 3714 totalupgains = upbranchingresult->totalgains; 3715 ntotaldowngains = MAX(1, downbranchingresult->ntotalgains); 3716 ntotalupgains = MAX(1, upbranchingresult->ntotalgains); 3717 3718 return bestdowngain + bestupgain + (totaldowngains/ntotaldowngains + totalupgains/ntotalupgains)*nlowestlevelcutoffs; 3719 } 3720 3721 /** calculates the score as mentioned in the lookahead branching paper by Glankwamdee and Linderoth; 3722 * their score scales the number of cutoffs on the last layer of a 2-level temporary branching tree with the average gain of 3723 * every last level problem; together with the best gain for each branch of a variable we get the final score 3724 */ 3725 static 3726 SCIP_Real calculateWeightedCutoffScore( 3727 CONFIGURATION* config, /**< LAB configuration */ 3728 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3729 BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */ 3730 ) 3731 { 3732 SCIP_Real bestdowngain; 3733 SCIP_Real bestupgain; 3734 SCIP_Real totaldowngains; 3735 SCIP_Real totalupgains; 3736 SCIP_Real nlowestlevelcutoffs; 3737 int ntotaldowngains; 3738 int ntotalupgains; 3739 3740 assert(downbranchingresult != NULL); 3741 assert(upbranchingresult != NULL); 3742 3743 nlowestlevelcutoffs = (1.0 * downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs)/(downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes); 3744 bestdowngain = downbranchingresult->bestgain; 3745 bestupgain = upbranchingresult->bestgain; 3746 totaldowngains = downbranchingresult->totalgains; 3747 totalupgains = upbranchingresult->totalgains; 3748 ntotaldowngains = MAX(1, downbranchingresult->ntotalgains); 3749 ntotalupgains = MAX(1, upbranchingresult->ntotalgains); 3750 3751 return config->minweight*MIN(bestdowngain, bestupgain) + (1.0 - config->minweight)*MAX(bestdowngain, bestupgain) + (totaldowngains/ntotaldowngains + totalupgains/ntotalupgains)*nlowestlevelcutoffs; 3752 } 3753 3754 static 3755 SCIP_Real calculateCutoffScore( 3756 SCIP* scip, /**< SCIP data structure */ 3757 SCIP_VAR* branchvar, /**< variable to get the score for */ 3758 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3759 BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */ 3760 SCIP_Real lpobjval /**< objective value to get difference to as gain */ 3761 ) 3762 { 3763 SCIP_Real score; 3764 SCIP_Real downgain = SCIPsumepsilon(scip); 3765 SCIP_Real upgain = SCIPsumepsilon(scip); 3766 SCIP_Real gap; 3767 int nlowestlevelcutoffs; 3768 3769 assert(downbranchingresult != NULL); 3770 assert(upbranchingresult != NULL); 3771 3772 nlowestlevelcutoffs = 0; 3773 3774 /* the gain is the difference of the dualbound of a child and the reference objective value; 3775 * by bounding it by zero we are safe from numerical troubles 3776 */ 3777 if( !downbranchingresult->cutoff ) 3778 { 3779 nlowestlevelcutoffs += downbranchingresult->ndeepestcutoffs; 3780 downgain = MAX(downgain, downbranchingresult->dualbound - lpobjval); 3781 } 3782 if( !upbranchingresult->cutoff ) 3783 { 3784 nlowestlevelcutoffs += upbranchingresult->ndeepestcutoffs; 3785 upgain = MAX(upgain, upbranchingresult->dualbound - lpobjval); 3786 } 3787 3788 /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat 3789 * realistic gain for the infeasible child; 3790 * if both children are infeasible we just reset the initial zero values again 3791 */ 3792 if( downbranchingresult->cutoff ) 3793 { 3794 nlowestlevelcutoffs += 2 * SCIPgetNPseudoBranchCands(scip); 3795 downgain = 2 * upgain; 3796 } 3797 if( upbranchingresult->cutoff ) 3798 { 3799 nlowestlevelcutoffs += 2 * SCIPgetNPseudoBranchCands(scip); 3800 upgain = 2 * downgain; 3801 } 3802 3803 gap = SCIPgetCutoffbound(scip) - lpobjval; 3804 3805 downgain = downgain/gap; 3806 upgain = upgain/gap; 3807 3808 score = 1.0 * nlowestlevelcutoffs + SCIPgetBranchScore(scip, branchvar, downgain, upgain); 3809 3810 return score; 3811 } 3812 3813 static 3814 SCIP_Real calculateRelCutoffScore( 3815 SCIP* scip, /**< SCIP data structure */ 3816 SCIP_VAR* branchvar, /**< variable to get the score for */ 3817 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3818 BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */ 3819 SCIP_Real lpobjval /**< objective value to get difference to as gain */ 3820 ) 3821 { 3822 SCIP_Real score; 3823 SCIP_Real downgain = SCIPsumepsilon(scip); 3824 SCIP_Real upgain = SCIPsumepsilon(scip); 3825 SCIP_Real gap; 3826 int factor; 3827 SCIP_Real nlowestlevelcutoffs; 3828 3829 assert(downbranchingresult != NULL); 3830 assert(upbranchingresult != NULL); 3831 3832 assert(downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes > 0 || (downbranchingresult->cutoff && upbranchingresult->cutoff)); 3833 3834 nlowestlevelcutoffs = (1.0 * downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs)/(1 + downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes); 3835 3836 factor = SCIPgetNPseudoBranchCands(scip); 3837 if( factor > SCIPgetNLPRows(scip) ) 3838 factor = SCIPgetNLPRows(scip); 3839 factor = factor * factor; 3840 3841 /* the gain is the difference of the dualbound of a child and the reference objective value; 3842 * by bounding it by zero we are safe from numerical troubles 3843 */ 3844 if( !downbranchingresult->cutoff ) 3845 { 3846 downgain = MAX(downgain, downbranchingresult->dualbound - lpobjval); 3847 } 3848 if( !upbranchingresult->cutoff ) 3849 { 3850 upgain = MAX(upgain, upbranchingresult->dualbound - lpobjval); 3851 } 3852 3853 /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat 3854 * realistic gain for the infeasible child; 3855 * if both children are infeasible we just reset the initial zero values again 3856 */ 3857 if( downbranchingresult->cutoff ) 3858 { 3859 downgain = 2 * upgain; 3860 } 3861 if( upbranchingresult->cutoff ) 3862 { 3863 upgain = 2 * downgain; 3864 } 3865 3866 gap = SCIPgetCutoffbound(scip) - lpobjval; 3867 3868 downgain = downgain/gap; 3869 upgain = upgain/gap; 3870 3871 score = factor * nlowestlevelcutoffs + SCIPgetBranchScore(scip, branchvar, downgain, upgain); 3872 3873 return score; 3874 } 3875 3876 /** scoring method that selects an actual scoring method based on the user configuration */ 3877 static 3878 SCIP_Real calculateScore( 3879 SCIP* scip, /**< SCIP data structure */ 3880 CONFIGURATION* config, /**< LAB configuration */ 3881 SCIP_VAR* branchvar, /**< variable to get the score for */ 3882 BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */ 3883 BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */ 3884 SCIP_Real lpobjval, /**< objective value to get difference to as gain */ 3885 SCIP_Real baselpobjval /**< base objective value to get difference to as gain */ 3886 ) 3887 { 3888 SCIP_Real score; 3889 char scoringfunction; 3890 3891 assert(scip != NULL); 3892 assert(config != NULL); 3893 assert(branchvar != NULL); 3894 assert(downbranchingresult != NULL); 3895 assert(upbranchingresult != NULL); 3896 3897 if( config->inscoring ) 3898 scoringfunction = config->scoringscoringfunction; 3899 else if( SCIPgetProbingDepth(scip) > 0 ) 3900 scoringfunction = config->deeperscoringfunction; 3901 else 3902 scoringfunction = config->scoringfunction; 3903 3904 switch( scoringfunction ) 3905 { 3906 case 's': 3907 score = calculateScaledCutoffScore(downbranchingresult, upbranchingresult); 3908 break; 3909 case 'w': 3910 score = calculateWeightedCutoffScore(config, downbranchingresult, upbranchingresult); 3911 break; 3912 case 'f': 3913 score = calculateWeightedGain(scip, config, downbranchingresult, upbranchingresult, baselpobjval); 3914 break; 3915 case 'p': 3916 score = calculateScoreFromDeeperscore(scip, branchvar, downbranchingresult, upbranchingresult); 3917 break; 3918 case 'a': 3919 score = calculateScoreFromDeeperscoreAndCutoffs(scip, branchvar, downbranchingresult, upbranchingresult); 3920 break; 3921 case 'l': 3922 score = calculateScoreFromResult2(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval); 3923 break; 3924 case 'c': 3925 score = calculateCutoffScore(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval); 3926 break; 3927 case 'r': 3928 score = calculateRelCutoffScore(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval); 3929 break; 3930 case 'x': 3931 score = calculateScoreFromResult(scip, branchvar, downbranchingresult, upbranchingresult, baselpobjval); 3932 break; 3933 default: 3934 assert(scoringfunction == 'd'); 3935 score = calculateScoreFromResult(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval); 3936 } 3937 3938 return score; 3939 } 3940 3941 /** calculates the score based on the pseudocosts of the given variable */ 3942 static 3943 SCIP_Real calculateScoreFromPseudocosts( 3944 SCIP* scip, /**< SCIP data structure */ 3945 CANDIDATE* lpcand /**< candidate to get the score for */ 3946 ) 3947 { 3948 SCIP_Real downpseudocost; 3949 SCIP_Real uppseudocost; 3950 SCIP_Real score; 3951 3952 assert(scip != NULL); 3953 assert(lpcand != NULL); 3954 3955 downpseudocost = SCIPgetVarPseudocostVal(scip, lpcand->branchvar, 0-lpcand->fracval); 3956 uppseudocost = SCIPgetVarPseudocostVal(scip, lpcand->branchvar, 1-lpcand->fracval); 3957 3958 score = SCIPgetBranchScore(scip, lpcand->branchvar, downpseudocost, uppseudocost); 3959 3960 return score; 3961 } 3962 3963 #ifdef SCIP_DEBUG 3964 /** prints the names of the candidates of the given candidate list with their corresponding scores */ 3965 static 3966 void printCandidateList( 3967 SCIP* scip, /**< SCIP data structure */ 3968 CANDIDATELIST* candidatelist, /**< list to be printed */ 3969 SCORECONTAINER* scorecontainer /**< container with all scores */ 3970 ) 3971 { 3972 int i; 3973 3974 assert(scip != NULL); 3975 assert(candidatelist != NULL); 3976 assert(scorecontainer != NULL); 3977 3978 for( i = 0; i < candidatelist->ncandidates; i++ ) 3979 { 3980 SCIP_VAR* var = candidatelist->candidates[i]->branchvar; 3981 SCIP_Real score = scorecontainer->scores[SCIPvarGetProbindex(var)]; 3982 3983 assert(var != NULL); 3984 3985 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, " Index %2i: Var %s Score %.9g\n", i, SCIPvarGetName(var), score); 3986 } 3987 } 3988 #endif 3989 3990 /** sorts the best candidates (w.r.t. the score in the container) of the candidate list to the front of the list */ 3991 static 3992 void sortFirstCandidatesByScore( 3993 SCIP* scip, /**< SCIP data structure */ 3994 CANDIDATELIST* candidatelist, /**< candidates to be sorted */ 3995 SCORECONTAINER* scorecontainer, /**< container with the scores for each candidate */ 3996 int nbestcandidates /**< number of candidates that should be kept sorted at the start of the list*/ 3997 ) 3998 { 3999 int i; 4000 4001 assert(scip != NULL); 4002 assert(candidatelist != NULL); 4003 assert(scorecontainer != NULL); 4004 assert(candidatelist->ncandidates > 0); 4005 assert(nbestcandidates <= candidatelist->ncandidates); 4006 4007 for( i = 1; i < candidatelist->ncandidates; i++ ) 4008 { 4009 CANDIDATE* movecand = candidatelist->candidates[i]; 4010 int moveprobindex; 4011 SCIP_Real movescore; 4012 int nsorted; 4013 int insertionindex; 4014 assert(movecand != NULL); 4015 4016 moveprobindex = SCIPvarGetProbindex(movecand->branchvar); 4017 movescore = scorecontainer->scores[moveprobindex]; 4018 4019 /* the length of the sorted portion of the array, starting at 0 */ 4020 nsorted = MIN(i, nbestcandidates); 4021 4022 insertionindex = findInsertionPoint(scip, scorecontainer, movescore, candidatelist->candidates, nsorted); 4023 4024 assert(insertionindex <= nsorted); 4025 4026 /* if no change has to be made, skip the reordering; 4027 * if the insertionindex lies after the sorted block, skip the reordering 4028 */ 4029 if( insertionindex != i && insertionindex < nsorted ) 4030 { 4031 int j; 4032 CANDIDATE* reordercand = movecand; 4033 4034 /* move everything inside the sorted block one place further */ 4035 for( j = insertionindex; j < nsorted; j++ ) 4036 { 4037 CANDIDATE* oldcand = candidatelist->candidates[j]; 4038 assert(oldcand != NULL); 4039 4040 candidatelist->candidates[j] = reordercand; 4041 reordercand = oldcand; 4042 } 4043 /* the dropped element gets placed in the position of the actually moved element */ 4044 candidatelist->candidates[i] = reordercand; 4045 } 4046 } 4047 4048 #ifdef SCIP_DEBUG 4049 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "All %i candidates, with the first %i candidates sorted by their FSB score:" 4050 "\n", candidatelist->ncandidates, nbestcandidates); 4051 printCandidateList(scip, candidatelist, scorecontainer); 4052 #endif 4053 } 4054 4055 /** checks whether the given candidates is reliable, so that its pseudocosts may be used */ 4056 static 4057 SCIP_Bool isCandidateReliable( 4058 SCIP* scip, /**< SCIP data structure */ 4059 SCIP_VAR* branchvar /**< var to check for reliability */ 4060 ) 4061 { 4062 SCIP_Real size; 4063 SCIP_Real downsize; 4064 SCIP_Real upsize; 4065 SCIP_Real reliable = 5; 4066 4067 assert(scip != NULL); 4068 assert(branchvar != NULL); 4069 4070 downsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchvar, SCIP_BRANCHDIR_DOWNWARDS); 4071 upsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchvar, SCIP_BRANCHDIR_UPWARDS); 4072 size = MIN(downsize, upsize); 4073 4074 return size >= reliable; 4075 } 4076 4077 /** checks whether the current problem is feasible or cutoff */ 4078 static 4079 SCIP_Bool isCurrentNodeCutoff( 4080 SCIP* scip /**< SCIP data structure */ 4081 ) 4082 { 4083 assert(scip != NULL); 4084 4085 return (SCIPgetCutoffdepth(scip) <= SCIPgetDepth(scip)); 4086 } 4087 4088 /** Ensures that the scores are present in the scorecontainer for each of the candidates to consider */ 4089 static 4090 SCIP_RETCODE ensureScoresPresent( 4091 SCIP* scip, /**< SCIP data structure */ 4092 STATUS* status, /**< current status */ 4093 PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */ 4094 CONFIGURATION* config, /**< the configuration of the branching rule */ 4095 SCIP_SOL* baselpsol, /**< base lp solution */ 4096 DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */ 4097 BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */ 4098 CANDIDATELIST* allcandidates, /**< list containing all candidates to consider */ 4099 BRANCHINGDECISION* decision, /**< struct to store the final decision */ 4100 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */ 4101 LEVEL2DATA* level2data, /**< level 2 LP results data */ 4102 SCIP_Real lpobjval /**< base LP objective value */ 4103 #ifdef SCIP_STATISTIC 4104 ,STATISTICS* statistics /**< general statistical data */ 4105 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 4106 #endif 4107 ) 4108 { 4109 int i; 4110 int nunscoredcandidates = 0; 4111 int* candidateunscored; 4112 4113 assert(scip != NULL); 4114 assert(config != NULL); 4115 assert(status != NULL); 4116 assert(allcandidates != NULL); 4117 assert(scorecontainer != NULL); 4118 assert(allcandidates->candidates != NULL || allcandidates->ncandidates == 0); 4119 4120 SCIP_CALL( SCIPallocBufferArray(scip, &candidateunscored, allcandidates->ncandidates) ); 4121 4122 /* filter the candidates based on the presence of a score in the 'scorecontainer'. Only those without a score need a 4123 * new one. 4124 */ 4125 for( i = 0; i < allcandidates->ncandidates; i++ ) 4126 { 4127 CANDIDATE* lpcand = allcandidates->candidates[i]; 4128 SCIP_VAR* branchvar = lpcand->branchvar; 4129 int probindex = SCIPvarGetProbindex(branchvar); 4130 SCIP_Real knownscore = scorecontainer->scores[probindex]; 4131 4132 assert(lpcand != NULL); 4133 assert(branchvar != NULL); 4134 4135 if( SCIPisLT(scip, knownscore, 0.0) ) 4136 { 4137 if( config->abbrevpseudo && isCandidateReliable(scip, branchvar) ) 4138 { 4139 SCIP_Real score = calculateScoreFromPseudocosts(scip, lpcand); 4140 SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, lpcand, score, 0.0, 0.0) ); 4141 } 4142 else if( config->level2avgscore && SCIPgetProbingDepth(scip) > 0 ) 4143 { 4144 assert(scorecontainer->nsetscores > 0); 4145 SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, lpcand, 4146 scorecontainer->scoresum / scorecontainer->nsetscores, 0.0, 0.0) ); 4147 } 4148 else if( config->level2zeroscore && SCIPgetProbingDepth(scip) > 0 ) 4149 { 4150 assert(scorecontainer->nsetscores > 0); 4151 SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, lpcand, 4152 -0.1, 0.0, 0.0) ); 4153 } 4154 else 4155 { 4156 /* score is unknown and needs to be calculated */ 4157 candidateunscored[nunscoredcandidates] = i; 4158 nunscoredcandidates++; 4159 } 4160 } 4161 } 4162 4163 if( nunscoredcandidates > 0 ) 4164 { 4165 CANDIDATELIST* unscoredcandidates; 4166 4167 /* allocate the list of candidates without any score (gets updated further on) */ 4168 SCIP_CALL( candidateListCreate(scip, &unscoredcandidates, nunscoredcandidates) ); 4169 4170 /* move the unscored candidates to the temp list */ 4171 for( i = 0; i < nunscoredcandidates; i++ ) 4172 { 4173 int candindex = candidateunscored[i]; 4174 4175 assert(allcandidates->candidates[candindex] != NULL); 4176 4177 unscoredcandidates->candidates[i] = allcandidates->candidates[candindex]; 4178 } 4179 4180 #ifdef SCIP_DEBUG 4181 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Of the given %i candidates, %i have no score: ", 4182 allcandidates->ncandidates, nunscoredcandidates); 4183 printCandidates(scip, SCIP_VERBLEVEL_HIGH, unscoredcandidates); 4184 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Calculating the FSB result to get a score for the remaining " 4185 "candidates.\n"); 4186 #endif 4187 4188 /* Calculate all remaining FSB scores and collect the scores in the container */; 4189 #ifdef SCIP_STATISTIC 4190 SCIP_CALL( getFSBResult(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, unscoredcandidates, 4191 decision, scorecontainer, level2data, lpobjval, statistics, localstats) ); 4192 #else 4193 SCIP_CALL( getFSBResult(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, unscoredcandidates, 4194 decision, scorecontainer, level2data, lpobjval) ); 4195 #endif 4196 4197 /* move the now scored candidates back to the original list */ 4198 for( i = 0; i < nunscoredcandidates; i++ ) 4199 { 4200 assert(allcandidates->candidates[candidateunscored[i]] == unscoredcandidates->candidates[i]); 4201 4202 assert(unscoredcandidates->candidates[i] != NULL); 4203 unscoredcandidates->candidates[i] = NULL; 4204 } 4205 4206 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Calculated the scores for the remaining candidates\n"); 4207 4208 SCIP_CALL( candidateListFree(scip, &unscoredcandidates) ); 4209 } 4210 4211 /* reset the best sorted indices, as those are only valid on the FSB run already completed */ 4212 scoreContainterResetBestSortedCands(scorecontainer); 4213 4214 SCIPfreeBufferArray(scip, &candidateunscored); 4215 4216 return SCIP_OKAY; 4217 } 4218 4219 /** Get the candidates to temporarily branch on. In the LAB case this is the complete list of possible candidates. In the 4220 * ALAB case only the 'best' candidates are returned. */ 4221 static 4222 SCIP_RETCODE filterCandidates( 4223 SCIP* scip, /**< SCIP data structure */ 4224 STATUS* status, /**< current status */ 4225 PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */ 4226 CONFIGURATION* config, /**< the configuration of the branching rule */ 4227 SCIP_SOL* baselpsol, /**< base lp solution */ 4228 DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */ 4229 BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */ 4230 CANDIDATELIST* candidatelist, /**< list of candidates to branch on */ 4231 BRANCHINGDECISION* decision, /**< struct to store the final decision */ 4232 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */ 4233 LEVEL2DATA* level2data, /**< level 2 LP results data */ 4234 SCIP_Real lpobjval /**< base LP objective value */ 4235 #ifdef SCIP_STATISTIC 4236 ,STATISTICS* statistics /**< general statistical data */ 4237 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 4238 #endif 4239 ) 4240 { 4241 assert(scip != NULL); 4242 assert(config != NULL); 4243 assert(status != NULL); 4244 assert(candidatelist != NULL); 4245 assert(SCIPinProbing(scip)); 4246 4247 /* abbreviated LAB: only use the "best" candidates */ 4248 if( config->abbreviated ) 4249 { 4250 assert(scorecontainer != NULL); 4251 4252 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Getting the best (at most) %i of the given %i candidates: ", 4253 config->maxncands, candidatelist->ncandidates); 4254 #ifdef SCIP_DEBUG 4255 printCandidates(scip, SCIP_VERBLEVEL_HIGH, candidatelist); 4256 #endif 4257 4258 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "%s", "Ensuring that all candidates have a score.\n"); 4259 #ifdef SCIP_STATISTIC 4260 SCIP_CALL( ensureScoresPresent(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, candidatelist, 4261 decision, scorecontainer, level2data, lpobjval, statistics, localstats) ); 4262 #else 4263 SCIP_CALL( ensureScoresPresent(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, candidatelist, 4264 decision, scorecontainer, level2data, lpobjval) ); 4265 #endif 4266 4267 /* if we didn't find any domreds or constraints during the FSB scoring, we branch on */ 4268 if( isBranchFurther(status, SCIPgetProbingDepth(scip) == 0) ) 4269 { 4270 int nusedcands; 4271 int i; 4272 4273 if( SCIPgetProbingDepth(scip) == 0 || config->maxndeepercands == 0 ) 4274 nusedcands = MIN(config->maxncands, candidatelist->ncandidates); 4275 else 4276 nusedcands = MIN(config->maxndeepercands, candidatelist->ncandidates); 4277 4278 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "%s", "Filter the candidates by their score.\n"); 4279 4280 sortFirstCandidatesByScore(scip, candidatelist, scorecontainer, nusedcands); 4281 4282 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Best candidate according to FSB scores: <%s>\n", 4283 SCIPvarGetName(candidatelist->candidates[0]->branchvar)); 4284 4285 if( config->worsefactor >= 0 ) 4286 { 4287 for( i = 1; i < nusedcands; ++i ) 4288 { 4289 if( scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)] > 4290 config->worsefactor * scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)] ) 4291 break; 4292 } 4293 nusedcands = i; 4294 } 4295 4296 if( config->filterbymaxgain && SCIPgetProbingDepth(scip) == 0 ) 4297 { 4298 SCIP_Real maxgain; 4299 SCIP_Real bestmaxgain = MAX(scorecontainer->downgains[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)], 4300 scorecontainer->upgains[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)]); /*lint !e666*/ 4301 4302 if( bestmaxgain == 0.0 ) 4303 nusedcands = 1; 4304 else 4305 { 4306 for( i = nusedcands - 1; i >= 1; --i ) 4307 { 4308 maxgain = MAX(scorecontainer->downgains[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)], 4309 scorecontainer->upgains[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)]); /*lint !e666*/ 4310 4311 if( SCIPisSumLE(scip, maxgain / bestmaxgain, 1.0) ) 4312 { 4313 --nusedcands; 4314 4315 if( i < nusedcands ) 4316 { 4317 CANDIDATE* tmp = candidatelist->candidates[i]; 4318 candidatelist->candidates[i] = candidatelist->candidates[nusedcands]; 4319 candidatelist->candidates[nusedcands] = tmp; 4320 } 4321 } 4322 } 4323 } 4324 } 4325 4326 if( SCIPgetProbingDepth(scip) > 0 && scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)] > -0.05) 4327 { 4328 for( i = 1; i < nusedcands; ++i ) 4329 { 4330 if( scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)] < -0.05 ) 4331 break; 4332 } 4333 nusedcands = i; 4334 } 4335 4336 SCIP_CALL( candidateListKeep(scip, candidatelist, nusedcands) ); 4337 } 4338 #ifdef SCIP_DEBUG 4339 else 4340 { 4341 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Strong Branching would have stopped.\n"); 4342 } 4343 #endif 4344 4345 if( isCurrentNodeCutoff(scip) ) 4346 status->cutoff = TRUE; 4347 } 4348 else 4349 { 4350 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Getting the branching candidates by selecting all candidates.\n"); 4351 } 4352 4353 return SCIP_OKAY; 4354 } 4355 4356 /** Executes the general branching on a variable in a given direction (up/down) and repeats the algorithm from the new node */ 4357 static 4358 SCIP_RETCODE executeBranchingRecursive( 4359 SCIP* scip, /**< SCIP data structure */ 4360 STATUS* status, /**< current status */ 4361 CONFIGURATION* config, /**< the configuration of the branching rule */ 4362 SCIP_SOL* baselpsol, /**< the base lp solution */ 4363 CANDIDATE* candidate, /**< candidate to branch on */ 4364 SCIP_Real localbaselpsolval, /**< the objective value of the current temporary problem */ 4365 SCIP_Real baselpobjval, /**< LP objective value of focus node (not probing) */ 4366 int recursiondepth, /**< remaining recursion depth */ 4367 DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */ 4368 BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */ 4369 LEVEL2DATA* level2data, /**< level 2 LP results data */ 4370 BRANCHINGRESULTDATA* branchingresult, /**< container to store the result of the branching in */ 4371 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */ 4372 SCIP_Bool downbranching /**< should we branch up or down in here? */ 4373 #ifdef SCIP_STATISTIC 4374 ,STATISTICS* statistics /**< general statistical data */ 4375 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 4376 #endif 4377 ) 4378 { 4379 int probingdepth; 4380 SCIP_VAR* branchvar; 4381 SCIP_Real branchvalfrac; 4382 SCIP_Real branchval; 4383 SCIP_Bool varisbinary; 4384 SCIP_Bool solvedlp = TRUE; 4385 4386 assert(scip != NULL); 4387 assert(status != NULL); 4388 assert(config != NULL); 4389 assert(candidate != NULL); 4390 assert(branchingresult != NULL); 4391 4392 branchvar = candidate->branchvar; 4393 branchvalfrac = candidate->fracval; 4394 branchval = candidate->branchval; 4395 4396 assert(branchvar != NULL); 4397 4398 probingdepth = SCIPgetProbingDepth(scip); 4399 varisbinary = SCIPvarIsBinary(branchvar); 4400 4401 if( binconsdata != NULL && varisbinary ) 4402 { 4403 if( downbranching ) 4404 { 4405 /* In case that the branch variable is binary, add the negated var to the list. 4406 * This list is used to generate a set packing constraint for cutoff branches which were reached by only using 4407 * binary variables. 4408 * DownBranching on a binary variable x means: x <= 0 4409 * When this cutoff occurs we have that: x >= 1 <=> 1-x <= 0 4410 */ 4411 SCIP_VAR* negbranchvar; 4412 4413 SCIP_CALL( SCIPgetNegatedVar(scip, branchvar, &negbranchvar) ); 4414 4415 assert(negbranchvar != NULL); 4416 4417 binaryVarListAppend(scip, binconsdata->binaryvars, negbranchvar); 4418 } 4419 else 4420 { 4421 /* In case that the branch variable is binary, add the var to the list. 4422 * This list is used to generate a set packing constraint for cutoff branches which were reached by only using 4423 * binary variables. 4424 * UpBranching on a binary variable x means: x >= 1 4425 * When this cutoff occurs we have that: x <= 0 4426 */ 4427 binaryVarListAppend(scip, binconsdata->binaryvars, branchvar); 4428 } 4429 } 4430 4431 if( level2data != NULL ) 4432 { 4433 SCIP_Real newbound = downbranching ? SCIPfeasFloor(scip, branchval) : SCIPfeasCeil(scip, branchval); 4434 4435 if( SCIPgetProbingDepth(scip) == 0 ) 4436 { 4437 assert(SCIPvarGetProbindex(branchvar) >= 0); 4438 level2data->branchvar1 = (unsigned int) SCIPvarGetProbindex(branchvar); 4439 level2data->branchdir1 = !downbranching; 4440 level2data->branchval1 = newbound; 4441 } 4442 else 4443 { 4444 LEVEL2RESULT* result; 4445 4446 assert(SCIPgetProbingDepth(scip) == 1); 4447 assert(SCIPvarGetProbindex(branchvar) >= 0); 4448 4449 level2data->branchvar2 = (unsigned int) SCIPvarGetProbindex(branchvar); 4450 level2data->branchdir2 = !downbranching; 4451 level2data->branchval2 = newbound; 4452 4453 SCIP_CALL( level2dataGetResult(scip, level2data, &result) ); 4454 4455 /* we already processed a similar level 2 node */ 4456 if( result != NULL ) 4457 { 4458 solvedlp = FALSE; 4459 #ifdef SCIP_STATISTIC 4460 statistics->nduplicatelps[probingdepth]++; 4461 #endif 4462 branchingresult->objval = result->lpobjval; 4463 branchingresult->dualbound = result->lpobjval; 4464 branchingresult->dualboundvalid = result->valid; 4465 branchingresult->cutoff = result->cutoff; 4466 branchingresult->niterations = 0; 4467 4468 if( !branchingresult->cutoff && branchingresult->dualboundvalid 4469 && SCIPisGE(scip, branchingresult->objval, SCIPgetCutoffbound(scip)) ) 4470 branchingresult->cutoff = TRUE; 4471 4472 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, 4473 "Use old %s branching result on var <%s> with 'val > %g' and bounds [<%g>..<%g>]: objval <%.9g>, cutoff <%d> " 4474 "(the parent objval was <%.9g>)\n", 4475 downbranching ? "down" : "up", SCIPvarGetName(branchvar), branchval, SCIPvarGetLbLocal(branchvar), 4476 SCIPvarGetUbLocal(branchvar), branchingresult->objval, branchingresult->cutoff, localbaselpsolval); 4477 } 4478 } 4479 } 4480 4481 if( solvedlp ) 4482 { 4483 SCIP_CALL( executeBranching(scip, config, downbranching, candidate, branchingresult, baselpsol, domainreductions, 4484 status) ); 4485 4486 assert(SCIPgetProbingDepth(scip) == 1 || SCIPgetProbingDepth(scip) == 2); 4487 4488 if( level2data != NULL && SCIPgetProbingDepth(scip) == 2) 4489 { 4490 SCIP_Bool duplicate; 4491 4492 SCIP_CALL( level2dataStoreResult(scip, level2data, branchingresult->objval, branchingresult->cutoff, branchingresult->dualboundvalid, &duplicate) ); 4493 assert(!duplicate); 4494 } 4495 4496 #ifdef SCIP_STATISTIC 4497 statistics->nlpssolved[probingdepth]++; 4498 statistics->nlpiterations[probingdepth] += branchingresult->niterations; 4499 4500 if( config->inscoring ) 4501 { 4502 statistics->nlpssolvedfsb[probingdepth]++; 4503 statistics->nlpiterationsfsb[probingdepth] += branchingresult->niterations; 4504 } 4505 #endif 4506 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Solving the LP took %" SCIP_LONGINT_FORMAT " iterations (status %d).\n", 4507 branchingresult->niterations, SCIPgetLPSolstat(scip)); 4508 4509 #ifdef SCIP_DEBUG 4510 if( status->lperror ) 4511 { 4512 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The LP could not be solved.\n"); 4513 } 4514 else if( branchingresult->cutoff ) 4515 { 4516 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The solved LP was infeasible and as such is cutoff\n"); 4517 } 4518 else 4519 { 4520 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The solved LP was feasible and has an objval <%.9g> (the parent objval was " 4521 "<%.9g>)\n", branchingresult->objval, localbaselpsolval); 4522 } 4523 #endif 4524 } 4525 4526 if( !branchingresult->cutoff && !status->lperror && !status->limitreached ) 4527 { 4528 SCIP_Real localgain; 4529 4530 localgain = MAX(0, branchingresult->objval - localbaselpsolval); 4531 4532 /* update pseudo costs */ 4533 if( downbranching ) 4534 { 4535 SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, 0.0 - branchvalfrac, localgain, 1.0) ); 4536 } 4537 else 4538 { 4539 SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, 1.0 - branchvalfrac, localgain, 1.0) ); 4540 } 4541 } 4542 4543 if( solvedlp && !branchingresult->cutoff && !status->lperror && !status->limitreached ) 4544 { 4545 /* store the warm start information in the candidate, so that it can be reused in a later branching */ 4546 if( config->reusebasis && config->inscoring ) 4547 { 4548 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Storing warm start information for %s branching on var <%s>\n", 4549 downbranching ? "down" : "up", SCIPvarGetName(branchvar)); 4550 4551 SCIP_CALL( candidateStoreWarmStartInfo(scip, candidate, downbranching) ); 4552 } 4553 4554 if( recursiondepth > 1 && !config->inscoring ) 4555 { 4556 CANDIDATELIST* candidatelist; 4557 4558 SCIP_CALL( candidateListGetAllFractionalCandidates(scip, &candidatelist) ); 4559 assert(candidatelist != NULL); 4560 4561 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "%sbranching has <%i> candidates.\n", downbranching ? "Down" : "Up", 4562 candidatelist->ncandidates); 4563 4564 if( candidatelist->ncandidates > 0 ) 4565 { 4566 BRANCHINGDECISION* deeperdecision; 4567 STATUS* deeperstatus; 4568 PERSISTENTDATA* deeperpersistent = NULL; 4569 SCIP_Real deeperlpobjval = branchingresult->objval; 4570 #ifdef SCIP_STATISTIC 4571 LOCALSTATISTICS* deeperlocalstats; 4572 4573 SCIP_CALL( localStatisticsAllocate(scip, &deeperlocalstats) ); 4574 #endif 4575 SCIP_CALL( statusCreate(scip, &deeperstatus) ); 4576 4577 SCIP_CALL( branchingDecisionCreate(scip, &deeperdecision) ); 4578 4579 #ifdef SCIP_STATISTIC 4580 SCIP_CALL( filterCandidates(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions, binconsdata, candidatelist, 4581 deeperdecision, scorecontainer, level2data, deeperlpobjval, 4582 statistics, localstats) ); 4583 #else 4584 SCIP_CALL( filterCandidates(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions, binconsdata, candidatelist, 4585 deeperdecision, scorecontainer, level2data, deeperlpobjval) ); 4586 #endif 4587 if( deeperstatus->lperror ) 4588 { 4589 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "ignoring lperror in filtering call...\n"); 4590 deeperstatus->lperror = FALSE; 4591 } 4592 if( deeperstatus->cutoff ) 4593 { 4594 branchingresult->ndeepestnodes += 2; 4595 branchingresult->ndeepestcutoffs += 2; 4596 } 4597 4598 /* the status may have changed because of FSB to get the best candidates */ 4599 if( isBranchFurther(deeperstatus, FALSE) ) 4600 { 4601 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Now the objval is <%.9g>\n", branchingresult->objval); 4602 4603 #ifdef SCIP_STATISTIC 4604 deeperlocalstats->ncutoffproofnodes = 0; 4605 SCIP_CALL( selectVarRecursive(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions, 4606 binconsdata, candidatelist, deeperdecision, scorecontainer, level2data, recursiondepth - 1, 4607 deeperlpobjval, baselpobjval, &branchingresult->niterations, &branchingresult->ndeepestcutoffs, 4608 &branchingresult->bestgain, &branchingresult->totalgains, &branchingresult->ntotalgains, 4609 &branchingresult->ndeepestnodes, 4610 statistics, deeperlocalstats, NULL, NULL) ); 4611 #else 4612 SCIP_CALL( selectVarRecursive(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions, 4613 binconsdata, candidatelist, deeperdecision, scorecontainer, level2data, recursiondepth - 1, 4614 deeperlpobjval, baselpobjval, &branchingresult->niterations, &branchingresult->ndeepestcutoffs, 4615 &branchingresult->bestgain, &branchingresult->totalgains, &branchingresult->ntotalgains, 4616 &branchingresult->ndeepestnodes) ); 4617 #endif 4618 4619 assert(deeperstatus->cutoff || deeperstatus->domred || deeperstatus->lperror 4620 || branchingresult->ndeepestnodes == 8 4621 || branchingresult->ndeepestnodes == 2 * candidatelist->ncandidates 4622 || SCIPisStopped(scip)); 4623 4624 /* the proved dual bound of the deeper branching cannot be less than the current dual bound, as every deeper 4625 * node has more/tighter constraints and as such cannot be better than the base LP. */ 4626 assert(SCIPisGE(scip, deeperdecision->proveddb, branchingresult->dualbound)); 4627 branchingresult->dualbound = deeperdecision->proveddb; 4628 branchingresult->deeperscore = deeperdecision->score; 4629 branchingresult->dualboundvalid = TRUE; 4630 } 4631 #ifdef SCIP_STATISTIC 4632 else 4633 { 4634 assert(SCIPgetProbingDepth(scip) == probingdepth + 1); 4635 4636 statistics->stopafterfsb[probingdepth+1]++; 4637 4638 if( deeperstatus->cutoff ) 4639 { 4640 statistics->cutoffafterfsb[probingdepth+1]++; 4641 } 4642 else if( deeperstatus->domred ) 4643 { 4644 statistics->domredafterfsb[probingdepth+1]++; 4645 } 4646 } 4647 #endif 4648 /* deeperstatus->cutoff is TRUE, if any up/down child pair of the up child were cutoff */ 4649 if( deeperstatus->cutoff ) 4650 { 4651 branchingresult->cutoff = TRUE; 4652 #ifdef SCIP_STATISTIC 4653 localstats->ncutoffproofnodes += deeperlocalstats->ncutoffproofnodes; 4654 #endif 4655 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Both deeper children were cutoff, so the %s branch is " 4656 "cutoff\n", downbranching ? "down" : "up"); 4657 } 4658 4659 branchingDecisionFree(scip, &deeperdecision); 4660 statusFree(scip, &deeperstatus); 4661 #ifdef SCIP_STATISTIC 4662 localStatisticsFree(scip, &deeperlocalstats); 4663 #endif 4664 } 4665 else 4666 { 4667 branchingresult->deeperscore = (branchingresult->dualbound - baselpobjval) * (branchingresult->dualbound - baselpobjval) * 10; 4668 } 4669 SCIP_CALL( candidateListFree(scip, &candidatelist) ); 4670 } 4671 } 4672 4673 if( recursiondepth == 1 && !config->inscoring ) 4674 { 4675 branchingresult->ndeepestnodes++; 4676 /* this is a cutoff on the lowest tree level */ 4677 if( branchingresult->cutoff ) 4678 { 4679 branchingresult->ndeepestcutoffs++; 4680 } 4681 } 4682 4683 if( binconsdata != NULL && varisbinary ) 4684 { 4685 /* the current branching child is infeasible and we only branched on binary variables in lookahead branching */ 4686 if( solvedlp && branchingresult->cutoff && !status->lperror && SCIPallColsInLP(scip) 4687 && binconsdata->binaryvars->nbinaryvars == (probingdepth + 1) ) 4688 { 4689 #ifdef SCIP_STATISTIC 4690 SCIP_CALL( addBinaryConstraint(scip, config, binconsdata, baselpsol, statistics) ); 4691 #else 4692 SCIP_CALL( addBinaryConstraint(scip, config, binconsdata, baselpsol) ); 4693 #endif 4694 } 4695 4696 binaryVarListDrop(binconsdata->binaryvars); 4697 } 4698 4699 /* reset the probing depth to undo the previous branching */ 4700 SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) ); 4701 4702 return SCIP_OKAY; 4703 } 4704 4705 /** branches recursively on all given candidates */ 4706 static 4707 SCIP_RETCODE selectVarRecursive( 4708 SCIP* scip, /**< SCIP data structure */ 4709 STATUS* status, /**< current status */ 4710 PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */ 4711 CONFIGURATION* config, /**< the configuration of the branching rule */ 4712 SCIP_SOL* baselpsol, /**< base lp solution */ 4713 DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */ 4714 BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */ 4715 CANDIDATELIST* candidatelist, /**< list of candidates to branch on */ 4716 BRANCHINGDECISION* decision, /**< struct to store the final decision */ 4717 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */ 4718 LEVEL2DATA* level2data, /**< level 2 LP results data */ 4719 int recursiondepth, /**< remaining recursion depth */ 4720 SCIP_Real lpobjval, /**< LP objective value of current probing node*/ 4721 SCIP_Real baselpobjval, /**< LP objective value of focus node (not probing) */ 4722 SCIP_Longint* niterations, /**< pointer to store the total number of iterations for this variable; or NULL*/ 4723 int* ndeepestcutoffs, /**< pointer to store the total number of cutoffs on the deepest level; or NULL */ 4724 SCIP_Real* bestgain, /**< pointer to store the best gain found with these candidates; or NULL */ 4725 SCIP_Real* totalgains, /**< pointer to store the sum over all gains that are valid in both children; 4726 * or NULL, if bestgain == NULL */ 4727 int* ntotalgains, /**< pointer to store the number of gains summed in totalgains; 4728 * or NULL, if bestgain == NULL */ 4729 int* ndeepestnodes /**< pointer to store the number of nodes processed in the deepest level */ 4730 #ifdef SCIP_STATISTIC 4731 ,STATISTICS* statistics /**< general statistical data */ 4732 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 4733 ,SCIP_Real* firstscoreptr /**< pointer to store score of first candidate, or NULL */ 4734 ,SCIP_Real* bestscoreptr /**< pointer to store best score, or NULL */ 4735 #endif 4736 ) 4737 { 4738 BRANCHINGRESULTDATA* downbranchingresult = NULL; 4739 BRANCHINGRESULTDATA* upbranchingresult = NULL; 4740 BRANCHINGRESULTDATA* bestdownbranchingresult = NULL; 4741 BRANCHINGRESULTDATA* bestupbranchingresult = NULL; 4742 SCIP_LPI* lpi; 4743 SCIP_Real bestscore = -SCIPinfinity(scip); 4744 SCIP_Real bestscorelowerbound; 4745 SCIP_Real bestscoreupperbound; 4746 SCIP_Real bestscoringlpobjval = -SCIPinfinity(scip); 4747 int start = 0; 4748 int i; 4749 int c; 4750 int nlpcands; 4751 int probingdepth; 4752 SCIP_Bool stopafterinfeasible = FALSE; 4753 4754 assert(scip != NULL); 4755 assert(status != NULL); 4756 assert(config != NULL); 4757 assert(!config->usedomainreduction || domainreductions != NULL); 4758 assert(candidatelist != NULL); 4759 assert(candidatelist->ncandidates > 0); 4760 assert(decision != NULL); 4761 assert(recursiondepth >= 1); 4762 #ifdef SCIP_STATISTIC 4763 assert(statistics != NULL); 4764 4765 if( firstscoreptr != NULL ) 4766 *firstscoreptr = -1.0; 4767 if( bestscoreptr != NULL ) 4768 *bestscoreptr = -1.0; 4769 #endif 4770 4771 nlpcands = candidatelist->ncandidates; 4772 probingdepth = SCIPgetProbingDepth(scip); 4773 assert(probingdepth >= 0 && probingdepth < config->recursiondepth); 4774 4775 if( persistent != NULL && (!config->abbreviated || config->inscoring) && probingdepth == 0 ) 4776 start = persistent->restartindex; 4777 4778 /* init default decision */ 4779 decision->branchvar = candidatelist->candidates[0]->branchvar; 4780 decision->branchval = candidatelist->candidates[0]->branchval; 4781 decision->downdb = lpobjval; 4782 decision->downdbvalid = TRUE; 4783 decision->updb = lpobjval; 4784 decision->updbvalid = TRUE; 4785 decision->proveddb = lpobjval; 4786 decision->score = 0.0; 4787 4788 bestscorelowerbound = SCIPvarGetLbLocal(decision->branchvar); 4789 bestscoreupperbound = SCIPvarGetUbLocal(decision->branchvar); 4790 4791 SCIP_CALL( branchingResultDataCreate(scip, &downbranchingresult) ); 4792 SCIP_CALL( branchingResultDataCreate(scip, &upbranchingresult) ); 4793 4794 SCIP_CALL( branchingResultDataCreate(scip, &bestdownbranchingresult) ); 4795 SCIP_CALL( branchingResultDataCreate(scip, &bestupbranchingresult) ); 4796 4797 assert(downbranchingresult != NULL); 4798 assert(upbranchingresult != NULL); 4799 4800 if( config->inscoring ) 4801 { 4802 SCIP_CALL( SCIPgetBoolParam(scip, "branching/forceallchildren", &stopafterinfeasible) ); 4803 stopafterinfeasible = !stopafterinfeasible; 4804 } 4805 4806 SCIP_CALL( SCIPgetLPI(scip, &lpi) ); 4807 4808 #ifdef SCIP_DEBUG 4809 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Started selectVarRecursive with <%i> candidates: ", nlpcands); 4810 printCandidates(scip, SCIP_VERBLEVEL_HIGH, candidatelist); 4811 #endif 4812 4813 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Starting loop from index %d\n", start); 4814 4815 /* iterate over all current branching candidates and evaluate their two potential child nodes by: 4816 * - potentially applying domain propagation at each node before 4817 * - solving the LP at the nodes to obtain a dual bound 4818 * - potentially evaluating branching candidates at the potential child node again by applying this method recursively 4819 * 4820 * some improvements of the general scheme: 4821 * - results obtained for a candidate in a previous lookahead branching call at this node may be re-used 4822 * - while i counts the number of candidates evaluated in this call, we do not always start at the front 4823 * of the candidate array, but rather store at which index we stopped last time (e.g., because a domain reduction was 4824 * found and applied) and start from that index next time. Even though the set of branching candidates is probably different 4825 * it is often reasonably close and we avoid evaluating the same variables again and again. 4826 */ 4827 for( i = 0, c = start; 4828 isBranchFurtherLoopDecrement(status, &c) && i < nlpcands && !SCIPisStopped(scip); i++, c++) 4829 { 4830 DOMAINREDUCTIONS* downdomainreductions = NULL; 4831 DOMAINREDUCTIONS* updomainreductions = NULL; 4832 SCIP_Bool useoldbranching = FALSE; 4833 SCIP_Real oldlpobjval = -SCIPinfinity(scip); 4834 CANDIDATE* candidate; 4835 SCIP_VAR* branchvar; 4836 SCIP_Real branchval; 4837 SCIP_Real branchlb; 4838 SCIP_Real branchub; 4839 4840 c = c % nlpcands; 4841 4842 candidate = candidatelist->candidates[c]; 4843 4844 assert(candidate != NULL); 4845 4846 branchvar = candidate->branchvar; 4847 branchval = candidate->branchval; 4848 4849 assert(branchvar != NULL); 4850 4851 branchlb = SCIPvarGetLbLocal(branchvar); 4852 branchub = SCIPvarGetUbLocal(branchvar); 4853 4854 if( SCIPisEQ(scip, branchlb, branchub) ) 4855 { 4856 /* if both bounds are equal the variable is fixed and we cannot branch 4857 * this may happen if domain propagation on other candidates finds better bounds for the current candidate 4858 */ 4859 status->domred = TRUE; 4860 #ifdef SCIP_STATISTIC 4861 statistics->npropdomred[probingdepth]++; 4862 #endif 4863 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Domain Propagation changed the bounds of a branching candidate." 4864 "\n"); 4865 continue; 4866 } 4867 4868 /* @todo apply already found domainreductions for this candidate? */ 4869 4870 #ifdef SCIP_STATISTIC 4871 /* Reset the cutoffproofnodes, as the number of proof nodes from previous branching vars (which where not 4872 * cutoff, as we didn't break the loop) is not relevant for the min total sum of proof nodes. 4873 */ 4874 localstats->ncutoffproofnodes = 0; 4875 #endif 4876 4877 branchingResultDataInit(scip, downbranchingresult); 4878 branchingResultDataInit(scip, upbranchingresult); 4879 4880 /* use old lookahead branching result, if last call on this variable is not too long ago */ 4881 if( persistent != NULL && (config->inscoring || probingdepth == 0) && isUseOldBranching(scip, persistent, config, branchvar) ) 4882 { 4883 SCIP_CALL( getOldBranching(scip, persistent, config, branchvar, downbranchingresult, upbranchingresult, 4884 &oldlpobjval) ); 4885 useoldbranching = TRUE; 4886 #ifdef SCIP_STATISTIC 4887 if( config->inscoring ) 4888 statistics->noldbranchusedfsb[probingdepth]++; 4889 else 4890 statistics->noldbranchused[probingdepth]++; 4891 #endif 4892 } 4893 else 4894 { 4895 SCIP_Bool down; 4896 int k; 4897 4898 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, "Started branching on var <%s> with val <%g> and bounds " 4899 "[<%g>..<%g>]\n", SCIPvarGetName(branchvar), branchval, SCIPvarGetLbLocal(branchvar), 4900 SCIPvarGetUbLocal(branchvar)); 4901 4902 if( config->usedomainreduction ) 4903 { 4904 SCIP_CALL( domainReductionsCreate(scip, &downdomainreductions) ); 4905 SCIP_CALL( domainReductionsCreate(scip, &updomainreductions) ); 4906 } 4907 4908 down = SCIPisStrongbranchDownFirst(scip, branchvar); 4909 4910 /* @todo break if result is infeasible (probably only in first layer)? */ 4911 for( k = 0; k < 2; ++k ) 4912 { 4913 DOMAINREDUCTIONS* localdomainreductions; 4914 BRANCHINGRESULTDATA* localbranchingresult; 4915 BRANCHINGRESULTDATA* otherbranchingresult; 4916 4917 localdomainreductions = down ? downdomainreductions : updomainreductions; 4918 localbranchingresult = down ? downbranchingresult : upbranchingresult; 4919 otherbranchingresult = down ? upbranchingresult : downbranchingresult; 4920 4921 #ifdef SCIP_STATISTIC 4922 SCIP_CALL( executeBranchingRecursive(scip, status, config, baselpsol, candidate, lpobjval, baselpobjval, 4923 recursiondepth, localdomainreductions, binconsdata, level2data, localbranchingresult, scorecontainer, 4924 down, statistics, localstats) ); 4925 #else 4926 4927 SCIP_CALL( executeBranchingRecursive(scip, status, config, baselpsol, candidate, lpobjval, baselpobjval, 4928 recursiondepth, localdomainreductions, binconsdata, level2data, localbranchingresult, scorecontainer, 4929 down) ); 4930 #endif 4931 4932 /* check whether a new solutions rendered the previous child infeasible */ 4933 if( SCIPallColsInLP(scip) && !otherbranchingresult->cutoff ) 4934 { 4935 if( k == 1 && SCIPisGE(scip, otherbranchingresult->dualbound, SCIPgetCutoffbound(scip)) ) 4936 { 4937 otherbranchingresult->cutoff = TRUE; 4938 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, 4939 "The %s branching changed the cutoffbound and rendered the %s branching result infeasible.\n", 4940 down ? "down" : "up", down ? "up" : "down"); 4941 } 4942 } 4943 if( stopafterinfeasible && k == 0 && localbranchingresult->cutoff ) 4944 break; 4945 4946 /* the second iteration of the loop should branch in the other direction */ 4947 down = !down; 4948 } 4949 4950 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u), up=%.9g " 4951 "(gain=%.9g, valid=%u, inf=%u)\n", downbranchingresult->dualbound, 4952 downbranchingresult->dualbound - lpobjval, downbranchingresult->dualboundvalid, 4953 downbranchingresult->cutoff, upbranchingresult->dualbound, upbranchingresult->dualbound - lpobjval, 4954 upbranchingresult->dualboundvalid, upbranchingresult->cutoff); 4955 4956 if( niterations != NULL ) 4957 *niterations += downbranchingresult->niterations + upbranchingresult->niterations; 4958 4959 /* store results of branching call */ 4960 if( persistent != NULL && !upbranchingresult->cutoff && !downbranchingresult->cutoff && (config->inscoring || probingdepth == 0) ) 4961 { 4962 SCIP_CALL( updateOldBranching(scip, persistent, config, branchvar, branchval, downbranchingresult, 4963 upbranchingresult, lpobjval) ); 4964 } 4965 } 4966 4967 if( ndeepestcutoffs != NULL ) 4968 *ndeepestcutoffs += downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs; 4969 4970 if( ndeepestnodes != NULL ) 4971 *ndeepestnodes += downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes; 4972 4973 if( !status->lperror && !status->limitreached ) 4974 { 4975 SCIP_Real scoringlpobjval = useoldbranching ? oldlpobjval : lpobjval; 4976 SCIP_Real score = calculateScore(scip, config, branchvar, downbranchingresult, upbranchingresult, 4977 scoringlpobjval, baselpobjval); 4978 4979 #ifdef SCIP_STATISTIC 4980 if( i == 0 && firstscoreptr != NULL ) 4981 *firstscoreptr = score; 4982 #endif 4983 4984 if( bestgain != NULL && !config->inscoring && SCIPgetProbingDepth(scip) == 1 && !useoldbranching ) 4985 { 4986 assert(totalgains != NULL); 4987 assert(ntotalgains != NULL); 4988 4989 *bestgain = MAX(*bestgain, score); 4990 4991 if( !downbranchingresult->cutoff && !upbranchingresult->cutoff ) 4992 { 4993 (*totalgains) += score; 4994 (*ntotalgains)++; 4995 } 4996 } 4997 4998 /* both child nodes are infeasible -> the current node is infeasible */ 4999 if( SCIPallColsInLP(scip) && upbranchingresult->cutoff && downbranchingresult->cutoff ) 5000 { 5001 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> variable <%s> is infeasible in both directions\n", 5002 SCIPvarGetName(branchvar)); 5003 5004 /* this cutoff may be transferred to a higher level as a domain reduction/valid bound */ 5005 status->cutoff = TRUE; 5006 #ifdef SCIP_STATISTIC 5007 statistics->nfullcutoffs[probingdepth]++; 5008 localstats->ncutoffproofnodes += 2; 5009 #endif 5010 } 5011 /* up child is infeasible */ 5012 else if( SCIPallColsInLP(scip) && upbranchingresult->cutoff ) 5013 { 5014 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> variable <%s> is infeasible in upward branch\n", 5015 SCIPvarGetName(branchvar)); 5016 5017 /* apply down branching bound change at current node if we proved that this node is really infeasible and 5018 * parameters are set accordingly 5019 */ 5020 if( config->usedomainreduction && !useoldbranching ) 5021 { 5022 #ifdef SCIP_STATISTIC 5023 assert(localstats->ncutoffproofnodes == 0 || localstats->ncutoffproofnodes == 2); 5024 addUpperBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions, 5025 2 + localstats->ncutoffproofnodes, TRUE); 5026 #else 5027 addUpperBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions); 5028 #endif 5029 } 5030 5031 /* the proved bound is given by the bound of the down child alone */ 5032 if( downbranchingresult->dualboundvalid ) 5033 { 5034 decision->proveddb = MAX(decision->proveddb, downbranchingresult->dualbound); 5035 } 5036 5037 #ifdef SCIP_STATISTIC 5038 statistics->nsinglecutoffs[probingdepth]++; 5039 #endif 5040 } 5041 /* down child is infeasible */ 5042 else if( SCIPallColsInLP(scip) && downbranchingresult->cutoff ) 5043 { 5044 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> variable <%s> is infeasible in downward branch\n", 5045 SCIPvarGetName(branchvar)); 5046 5047 /* apply up branching bound change at current node if we proved that this node is really infeasible and 5048 * parameters are set accordingly 5049 */ 5050 if( config->usedomainreduction && !useoldbranching ) 5051 { 5052 #ifdef SCIP_STATISTIC 5053 assert(localstats->ncutoffproofnodes == 0 || localstats->ncutoffproofnodes == 2); 5054 addLowerBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions, 5055 2 + localstats->ncutoffproofnodes, TRUE); 5056 #else 5057 addLowerBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions); 5058 #endif 5059 } 5060 5061 /* the proved bound is given by the bound of the up child alone */ 5062 if( upbranchingresult->dualboundvalid ) 5063 { 5064 decision->proveddb = MAX(decision->proveddb, upbranchingresult->dualbound); 5065 } 5066 5067 #ifdef SCIP_STATISTIC 5068 statistics->nsinglecutoffs[probingdepth]++; 5069 #endif 5070 } 5071 /* "normal" case: both child nodes are LP-feasible */ 5072 else 5073 { 5074 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Neither branch is cut off and no limit reached.\n"); 5075 5076 /* the proved dual bound is the minimum of the dual bounds of both child nodes */ 5077 if( upbranchingresult->dualboundvalid && downbranchingresult->dualboundvalid ) 5078 { 5079 decision->proveddb = MAX(decision->proveddb, MIN(upbranchingresult->dualbound, 5080 downbranchingresult->dualbound)); 5081 } 5082 } 5083 5084 /* merge domain changes from the two child nodes */ 5085 if( updomainreductions != NULL && config->usedomainreduction && SCIPallColsInLP(scip) ) 5086 { 5087 int maxstoredomreds = INT_MAX; 5088 5089 assert(downdomainreductions != NULL); 5090 5091 if( config->enforcemaxdomreds && config->maxnviolateddomreds > 0) 5092 maxstoredomreds = config->maxnviolateddomreds; 5093 5094 if( !upbranchingresult->cutoff && !downbranchingresult->cutoff && config->mergedomainreductions ) 5095 applyDeeperDomainReductions(scip, baselpsol, maxstoredomreds, domainreductions, downdomainreductions, 5096 updomainreductions); 5097 else if( upbranchingresult->cutoff && !downbranchingresult->cutoff ) 5098 applySingleDeeperDomainReductions(scip, baselpsol, maxstoredomreds, domainreductions, downdomainreductions); 5099 else if( downbranchingresult->cutoff && !upbranchingresult->cutoff ) 5100 applySingleDeeperDomainReductions(scip, baselpsol, maxstoredomreds, domainreductions, updomainreductions); 5101 } 5102 5103 if( config->updatebranchingresults && bestscore > -1.0 && 5104 (SCIPisGT(scip, decision->proveddb, bestdownbranchingresult->dualbound) 5105 || SCIPisGT(scip, decision->proveddb, bestupbranchingresult->dualbound)) ) 5106 { 5107 SCIP_Real newscore; 5108 5109 bestdownbranchingresult->dualbound = MAX(bestdownbranchingresult->dualbound, decision->proveddb); 5110 bestupbranchingresult->dualbound = MAX(bestupbranchingresult->dualbound, decision->proveddb); 5111 5112 newscore = calculateScore(scip, config, decision->branchvar, bestdownbranchingresult, bestupbranchingresult, 5113 bestscoringlpobjval, baselpobjval); 5114 5115 if( newscore > bestscore ) 5116 { 5117 bestscore = newscore; 5118 5119 #ifdef SCIP_STATISTIC 5120 if( bestscoreptr != NULL ) 5121 *bestscoreptr = newscore; 5122 #endif 5123 decision->score = newscore; 5124 decision->downdb = bestdownbranchingresult->dualbound; 5125 decision->updb = bestupbranchingresult->dualbound; 5126 } 5127 } 5128 5129 /* the current candidate variable has a better score than the best candidate investigated so far */ 5130 if( SCIPisRelGT(scip, score, bestscore) ) 5131 { 5132 int nvars = SCIPgetNVars(scip); 5133 5134 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Old best var <%s> with bounds [<%g>..<%g>] and score %.9g\n", 5135 SCIPvarGetName(decision->branchvar), bestscorelowerbound, bestscoreupperbound, bestscore); 5136 5137 bestscore = score; 5138 5139 #ifdef SCIP_STATISTIC 5140 if( bestscoreptr != NULL ) 5141 *bestscoreptr = score; 5142 #endif 5143 decision->branchvar = candidate->branchvar; 5144 decision->branchval = candidate->branchval; 5145 decision->downdb = downbranchingresult->dualbound; 5146 decision->downdbvalid = downbranchingresult->dualboundvalid; 5147 decision->updb = upbranchingresult->dualbound; 5148 decision->updbvalid = upbranchingresult->dualboundvalid; 5149 decision->score = score; 5150 5151 branchingResultDataCopy(downbranchingresult, bestdownbranchingresult); 5152 branchingResultDataCopy(upbranchingresult, bestupbranchingresult); 5153 5154 /* store domain reductions found at the child nodes */ 5155 if( !config->inscoring && updomainreductions != NULL ) 5156 { 5157 assert(downdomainreductions != NULL); 5158 5159 SCIP_CALL( branchingDecisionEnsureBoundArraysSize(scip, decision, nvars) ); 5160 5161 BMScopyMemoryArray(decision->uplowerbounds, updomainreductions->lowerbounds, nvars); 5162 BMScopyMemoryArray(decision->upupperbounds, updomainreductions->upperbounds, nvars); 5163 BMScopyMemoryArray(decision->downlowerbounds, downdomainreductions->lowerbounds, nvars); 5164 BMScopyMemoryArray(decision->downupperbounds, downdomainreductions->upperbounds, nvars); 5165 decision->boundsvalid = TRUE; 5166 } 5167 else 5168 { 5169 decision->boundsvalid = FALSE; 5170 } 5171 5172 bestscorelowerbound = branchlb; 5173 bestscoreupperbound = branchub; 5174 bestscoringlpobjval = scoringlpobjval; 5175 assert(!SCIPisEQ(scip, bestscorelowerbound, bestscoreupperbound)); 5176 5177 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "New best var <%s> with bounds [<%g>..<%g>] and score %.9g\n", 5178 SCIPvarGetName(decision->branchvar), bestscorelowerbound, bestscoreupperbound, bestscore); 5179 } 5180 5181 #ifdef SCIP_DEBUG 5182 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> cand %d/%d var <%s> (solval=%.9g, downgain=%.9g->%.9g, upgain=%.9g->%.9g," 5183 " score=%.9g) -- best: <%s> (%.9g)\n", c, nlpcands, SCIPvarGetName(branchvar), branchval, 5184 MAX(downbranchingresult->objval - scoringlpobjval, 0), MAX(downbranchingresult->dualbound - scoringlpobjval, 0), 5185 MAX(upbranchingresult->objval - scoringlpobjval, 0), MAX(upbranchingresult->dualbound - scoringlpobjval, 0), 5186 score, SCIPvarGetName(decision->branchvar), bestscore); 5187 #endif 5188 5189 if( config->inscoring ) 5190 { 5191 assert(scorecontainer != NULL); 5192 /* only for abbreviated lookahead branching: we are in the FSB filtering step and store the score for this 5193 * variable and the warm starting basis to reuse it in the subsequent lookahead evaluation of the best 5194 * candidates 5195 */ 5196 SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, candidate, score, 5197 downbranchingresult->dualbound - scoringlpobjval, upbranchingresult->dualbound - scoringlpobjval) ); 5198 } 5199 5200 if( probingdepth == 0 && (binconsdata != NULL || domainreductions != NULL) && !useoldbranching 5201 && (config->maxnviolatedcons >= 0 || config->maxnviolatedbincons >= 0 || config->maxnviolateddomreds >= 0 ) ) 5202 { 5203 int nbincons = 0; 5204 int ndomreds = 0; 5205 5206 if( binconsdata != NULL ) 5207 { 5208 assert(binconsdata != NULL); /* for lint */ 5209 nbincons = binconsdata->conslist->nviolatedcons; 5210 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Found %d binary constraints (%d violated by the LP solution)\n", 5211 binconsdata->conslist->nelements, nbincons); 5212 5213 if( (config->maxnviolatedbincons > 0) && (nbincons >= config->maxnviolatedbincons) ) 5214 { 5215 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The max number of violated binary constraints <%i> is " 5216 "exceeded.\n", config->maxnviolatedbincons); 5217 status->maxnconsreached = TRUE; 5218 } 5219 } 5220 5221 if( domainreductions != NULL ) 5222 { 5223 assert(domainreductions != NULL); /* for lint */ 5224 ndomreds = domainreductions->nviolatedvars; 5225 if( config->prefersimplebounds && ndomreds > domainreductions->nsimplebounds ) 5226 ndomreds = domainreductions->nsimplebounds; 5227 5228 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Found %d bound changes (%d violated by the LP solution)\n", 5229 domainreductions->nchangedvars, ndomreds); 5230 5231 if( (config->maxnviolateddomreds > 0) && (ndomreds >= config->maxnviolateddomreds) ) 5232 { 5233 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The max number of violated bound changes <%i> is " 5234 "exceeded.\n", config->maxnviolateddomreds); 5235 status->maxnconsreached = TRUE; 5236 } 5237 } 5238 5239 if( config->maxnviolatedcons > 0 && (nbincons + ndomreds >= config->maxnviolatedcons) ) 5240 { 5241 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The max number of violated binary constraints and bound " 5242 "changes <%d> is exceeded.\n", config->maxnviolatedcons); 5243 status->maxnconsreached = TRUE; 5244 } 5245 } 5246 } 5247 5248 if( !(status->domred && decision->branchvar == candidate->branchvar) && areBoundsChanged(scip, decision->branchvar, bestscorelowerbound, bestscoreupperbound) ) 5249 { 5250 /* in case the bounds of the current highest scored solution have changed due to domain propagation during 5251 * the lookahead branching we can/should not branch on this variable but instead report the domain 5252 * reduction */ 5253 status->domred = TRUE; 5254 #ifdef SCIP_STATISTIC 5255 statistics->npropdomred[probingdepth]++; 5256 #endif 5257 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Domain Propagation changed the bounds of a branching candidate." 5258 "\n"); 5259 } 5260 5261 /* free domain reductions */ 5262 if( updomainreductions != NULL ) 5263 { 5264 assert(downdomainreductions != NULL); 5265 5266 domainReductionsFree(scip, &updomainreductions); 5267 domainReductionsFree(scip, &downdomainreductions); 5268 } 5269 } 5270 5271 branchingResultDataFree(scip, &bestupbranchingresult); 5272 branchingResultDataFree(scip, &bestdownbranchingresult); 5273 5274 branchingResultDataFree(scip, &upbranchingresult); 5275 branchingResultDataFree(scip, &downbranchingresult); 5276 5277 if( persistent != NULL && (!config->abbreviated || config->inscoring) && probingdepth == 0 ) 5278 { 5279 persistent->restartindex = c; 5280 } 5281 5282 return SCIP_OKAY; 5283 } 5284 5285 /** checks whether the current decision should be stored. This is the case if we found domain reductions 5286 * or constraints that will be applied, but none of them cuts off the current LP solution. 5287 * Then our current decision still holds true for the next call and can be reused without further calculations 5288 */ 5289 static 5290 SCIP_Bool isStoreDecision( 5291 CONFIGURATION* config, /**< the configuration of the branching rule */ 5292 BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */ 5293 DOMAINREDUCTIONS* domainreductions /**< container collecting all domain reductions found; or NULL */ 5294 ) 5295 { 5296 assert(config != NULL); 5297 5298 if( !config->storeunviolatedsol ) 5299 return FALSE; 5300 5301 /* there are violating binary constraints */ 5302 if( binconsdata != NULL && binconsdata->conslist->nviolatedcons > 0 ) 5303 return FALSE; 5304 5305 /* there are violating domain changes */ 5306 if( domainreductions != NULL && domainreductions->nviolatedvars > 0 ) 5307 return FALSE; 5308 5309 /* return TRUE if there is at least one domain change or binary constraint */ 5310 return (domainreductions != NULL && domainreductions->nchangedvars > 0) 5311 || (binconsdata != NULL && binconsdata->conslist->nelements > 0); 5312 } 5313 5314 /** starting point to obtain a branching decision via LAB/ALAB. */ 5315 static 5316 SCIP_RETCODE selectVarStart( 5317 SCIP* scip, /**< SCIP data structure */ 5318 CONFIGURATION* config, /**< the configuration of the branching rule */ 5319 PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */ 5320 STATUS* status, /**< current status */ 5321 BRANCHINGDECISION* decision, /**< struct to store the final decision */ 5322 SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */ 5323 CANDIDATELIST* candidatelist /**< list of candidates to branch on */ 5324 #ifdef SCIP_STATISTIC 5325 ,STATISTICS* statistics /**< general statistical data */ 5326 ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */ 5327 #endif 5328 ) 5329 { 5330 int recursiondepth; 5331 DOMAINREDUCTIONS* domainreductions = NULL; 5332 BINCONSDATA* binconsdata = NULL; 5333 LEVEL2DATA* level2data = NULL; 5334 SCIP_SOL* baselpsol = NULL; 5335 SCIP_Real lpobjval; 5336 #ifdef SCIP_STATISTIC 5337 SCIP_Real firstscore = -1.0; 5338 SCIP_Real bestscore = -1.0; 5339 int chosencandnr = -1; 5340 SCIP_Bool performedlab = FALSE; 5341 #endif 5342 5343 assert(scip != NULL); 5344 assert(config != NULL); 5345 assert(status != NULL); 5346 assert(decision != NULL); 5347 assert(candidatelist != NULL); 5348 #ifdef SCIP_STATISTIC 5349 assert(statistics != NULL); 5350 #endif 5351 5352 recursiondepth = config->recursiondepth; 5353 lpobjval = SCIPgetLPObjval(scip); 5354 5355 assert(recursiondepth > 0); 5356 5357 if( SCIP_MAXTREEDEPTH <= (SCIPgetDepth(scip) + recursiondepth) ) 5358 { 5359 /* we need at least 'recursiondepth' space for the branching */ 5360 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Cannot perform probing in selectVarRecursive, depth limit reached. " 5361 "Current:<%i>, Max:<%i>\n", SCIP_MAXTREEDEPTH, SCIPgetDepth(scip) + recursiondepth); 5362 status->depthtoosmall = TRUE; 5363 #ifdef SCIP_STATISTIC 5364 statistics->ndepthreached++; 5365 #endif 5366 return SCIP_OKAY; 5367 } 5368 5369 assert(!config->inscoring); 5370 5371 if( candidatelist->ncandidates == 1 ) 5372 { 5373 decision->branchvar = candidatelist->candidates[0]->branchvar; 5374 decision->branchval = candidatelist->candidates[0]->branchval; 5375 decision->downdb = lpobjval; 5376 decision->downdbvalid = TRUE; 5377 decision->updb = lpobjval; 5378 decision->updbvalid = TRUE; 5379 decision->proveddb = lpobjval; 5380 5381 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Only one candidate (<%s>) is given. This one is chosen without " 5382 "calculations.\n", SCIPvarGetName(decision->branchvar)); 5383 5384 #ifdef SCIP_STATISTIC 5385 statistics->nsinglecandidate++; 5386 #endif 5387 return SCIP_OKAY; 5388 } 5389 assert(!SCIPinProbing(scip)); 5390 5391 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The objective value of the base lp is <%.9g>\n", lpobjval); 5392 5393 if( config->usedomainreduction || config->usebincons ) 5394 { 5395 /* we have to copy the current solution before getting the candidates, as we possibly solve some LPs during 5396 * the getter and as such would get a wrong LP copied */ 5397 SCIP_CALL( copyCurrentSolution(scip, &baselpsol) ); 5398 } 5399 5400 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "About to start probing.\n"); 5401 SCIP_CALL( SCIPstartStrongbranch(scip, TRUE) ); 5402 SCIPenableVarHistory(scip); 5403 5404 /* create the binary constraint data */ 5405 if( config->usebincons ) 5406 { 5407 SCIP_CALL( binConsDataCreate(scip, &binconsdata, recursiondepth, 5408 (int)SCIPceil(scip, 0.5*candidatelist->ncandidates)) ); 5409 } 5410 5411 /* collect domain reductions in FSB scoring or LAB branching */ 5412 if( config->usedomainreduction ) 5413 { 5414 SCIP_CALL( domainReductionsCreate(scip, &domainreductions) ); 5415 } 5416 5417 #ifdef SCIP_STATISTIC 5418 SCIP_CALL( filterCandidates(scip, status, persistent, config, baselpsol, domainreductions, NULL, candidatelist, 5419 decision, scorecontainer, level2data, lpobjval, 5420 statistics, localstats) ); 5421 #else 5422 SCIP_CALL( filterCandidates(scip, status, persistent, config, baselpsol, domainreductions, NULL, candidatelist, 5423 decision, scorecontainer, level2data, lpobjval) ); 5424 #endif 5425 5426 if( candidatelist->ncandidates == 1 ) 5427 { 5428 decision->branchvar = candidatelist->candidates[0]->branchvar; 5429 decision->branchval = candidatelist->candidates[0]->branchval; 5430 decision->downdb = lpobjval; 5431 decision->downdbvalid = TRUE; 5432 decision->updb = lpobjval; 5433 decision->updbvalid = TRUE; 5434 decision->proveddb = lpobjval; 5435 5436 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Only one candidate (<%s>) is given. This one is chosen without " 5437 "calculations.\n", SCIPvarGetName(decision->branchvar)); 5438 5439 #ifdef SCIP_STATISTIC 5440 statistics->nsingleafterfilter++; 5441 #endif 5442 goto TERMINATE; 5443 } 5444 5445 /* the status may have changed because of FSB to get the best candidates 5446 * if that is the case, we already changed the base node and should start again */ 5447 if( isBranchFurther(status, TRUE) && candidatelist->ncandidates > 1 ) 5448 { 5449 assert(candidatelist->ncandidates > 0); 5450 5451 SCIPstatistic(performedlab = TRUE); 5452 5453 /* we do not need the level 2 data for FSB scoring, so we do not need to create it before */ 5454 if( recursiondepth == 2 && config->uselevel2data ) 5455 { 5456 SCIP_CALL( level2dataCreate(scip, &level2data) ); 5457 } 5458 5459 #ifdef SCIP_STATISTIC 5460 SCIP_CALL( selectVarRecursive(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, candidatelist, 5461 decision, scorecontainer, level2data, recursiondepth, lpobjval, lpobjval, NULL, NULL, NULL, NULL, NULL, NULL, 5462 statistics, localstats, &firstscore, &bestscore) ); 5463 #else 5464 SCIP_CALL( selectVarRecursive(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, candidatelist, 5465 decision, scorecontainer, level2data, recursiondepth, lpobjval, lpobjval, NULL, NULL, NULL, NULL, NULL, NULL) ); 5466 #endif 5467 5468 if( level2data != NULL ) 5469 { 5470 level2dataFree(scip, &level2data); 5471 } 5472 5473 /* only unviolating constraints and domain changes: store branching decision */ 5474 if( persistent != NULL && !status->lperror && isStoreDecision(config, binconsdata, domainreductions) ) 5475 { 5476 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "store decision: lpiters=%lld, cand <%s>[%g,%g - %g]\n", 5477 SCIPgetNNodeLPIterations(scip), SCIPvarGetName(decision->branchvar), 5478 SCIPvarGetLbLocal(decision->branchvar), SCIPvarGetUbLocal(decision->branchvar), 5479 SCIPgetSolVal(scip, NULL, decision->branchvar)); 5480 5481 persistent->oldntotalnodes = SCIPgetNTotalNodes(scip); 5482 persistent->oldnnodelpiterations = SCIPgetNNodeLPIterations(scip); 5483 persistent->oldnnodelps = SCIPgetNNodeLPs(scip) + SCIPgetNNodeZeroIterationLPs(scip); 5484 branchingDecisionCopy(decision, persistent->olddecision); 5485 } 5486 5487 #ifdef SCIP_STATISTIC 5488 if( config->abbreviated && !status->cutoff && !status->maxnconsreached 5489 && !status->addedbinconss && !status->domred) 5490 { 5491 if( candidatelist->ncandidates > 0 ) 5492 { 5493 assert(candidatelist->ncandidates <= statistics->maxnbestcands); 5494 5495 /* find the "FSB-index" of the decision */ 5496 for( chosencandnr = 0; chosencandnr < candidatelist->ncandidates; ++chosencandnr ) 5497 { 5498 if( decision->branchvar == candidatelist->candidates[chosencandnr]->branchvar ) 5499 { 5500 break; 5501 } 5502 } 5503 assert(chosencandnr < candidatelist->ncandidates); 5504 } 5505 } 5506 } 5507 else 5508 { 5509 int probingdepth = 0; 5510 if( SCIPinProbing(scip) ) 5511 probingdepth = SCIPgetProbingDepth(scip); 5512 statistics->stopafterfsb[probingdepth]++; 5513 5514 if( status->cutoff ) 5515 { 5516 statistics->cutoffafterfsb[probingdepth]++; 5517 } 5518 else if( status->maxnconsreached ) 5519 { 5520 statistics->domredafterfsb[probingdepth]++; 5521 } 5522 #endif 5523 } 5524 5525 TERMINATE: 5526 SCIP_CALL( SCIPendStrongbranch(scip) ); 5527 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Ended probing.\n"); 5528 5529 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Applying found data to the base node.\n"); 5530 5531 /* apply domain reductions */ 5532 if( domainreductions != NULL ) 5533 { 5534 assert(config->usedomainreduction); 5535 5536 if( !status->cutoff ) 5537 { 5538 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Applying domain reductions to the base node.\n"); 5539 #ifdef SCIP_STATISTIC 5540 SCIP_CALL( applyDomainReductions(scip, config, baselpsol, domainreductions, &status->domredcutoff, 5541 &status->domred, statistics) ); 5542 #else 5543 SCIP_CALL( applyDomainReductions(scip, config, baselpsol, domainreductions, &status->domredcutoff, 5544 &status->domred) ); 5545 #endif 5546 } 5547 domainReductionsFree(scip, &domainreductions); 5548 } 5549 5550 /* apply binary constraints */ 5551 if( binconsdata != NULL ) 5552 { 5553 assert(config->usebincons); 5554 assert(binconsdata->binaryvars->nbinaryvars == 0); 5555 5556 if( !status->cutoff ) 5557 { 5558 SCIP_NODE* basenode = SCIPgetCurrentNode(scip); 5559 5560 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Applying %d binary constraints to the base node.\n", binconsdata->conslist->nelements); 5561 #ifdef SCIP_STATISTIC 5562 SCIP_CALL( applyBinaryConstraints(scip, basenode, binconsdata->conslist, config, 5563 &status->addedbinconss, &status->cutoff, &status->domred, statistics) ); 5564 #else 5565 SCIP_CALL( applyBinaryConstraints(scip, basenode, binconsdata->conslist, config, 5566 &status->addedbinconss, &status->cutoff, &status->domred) ); 5567 #endif 5568 } 5569 else 5570 { 5571 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Discarding %d binary constraints because the base node is cut off.\n", binconsdata->conslist->nelements); 5572 } 5573 binConsDataFree(scip, &binconsdata); 5574 } 5575 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Applied found data to the base node.\n"); 5576 5577 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC) 5578 if( config->abbreviated ) 5579 { 5580 if( status->domred ) 5581 { 5582 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Lookahead Branching has added domain reductions. LAB restarts.\n"); 5583 5584 #ifdef SCIP_STATISTIC 5585 if( candidatelist->ncandidates == 1 ) 5586 statistics->nsingleafterfilter--; 5587 #endif 5588 } 5589 else if( status->addedbinconss ) 5590 { 5591 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Lookahead Branching has added binary constraints. LAB restarts.\n"); 5592 5593 #ifdef SCIP_STATISTIC 5594 if( candidatelist->ncandidates == 1 ) 5595 statistics->nsingleafterfilter--; 5596 #endif 5597 } 5598 else if( status->cutoff ) 5599 { 5600 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Lookahead Branching cut this node off.\n"); 5601 } 5602 else if( candidatelist->ncandidates > 0 ) 5603 { 5604 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Strong Branching would branch on variable <%s>\n", 5605 SCIPvarGetName(candidatelist->candidates[0]->branchvar)); 5606 5607 if( isBranchFurther(status, FALSE) && branchingDecisionIsValid(decision) ) 5608 { 5609 #ifdef SCIP_STATISTIC 5610 if( chosencandnr >= 0 ) 5611 { 5612 ++statistics->chosenfsbcand[chosencandnr]; 5613 5614 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "node %lld chose candidate %d score %16.9g vs %16.9g FSB: %16.9g vs %16.9g\n", 5615 SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), chosencandnr, 5616 scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[chosencandnr]->branchvar)], 5617 scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)], 5618 bestscore, firstscore); 5619 } 5620 else 5621 assert(!performedlab); 5622 #endif 5623 5624 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Lookahead Branching branches on variable <%s>\n", 5625 SCIPvarGetName(decision->branchvar)); 5626 } 5627 } 5628 else 5629 { 5630 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Something unexpected happened."); 5631 SCIPABORT(); 5632 } 5633 } 5634 #endif 5635 5636 if( baselpsol != NULL ) 5637 { 5638 SCIP_CALL( SCIPfreeSol(scip, &baselpsol) ); 5639 } 5640 5641 return SCIP_OKAY; 5642 } 5643 5644 /** 5645 * We can use the previous result, stored in the branchruledata, if the branchingvariable (as an indicator) is set and 5646 * the current lp solution is equal to the previous lp solution. 5647 * 5648 * @return \ref TRUE, if we can branch on the previous decision, \ref FALSE, else. 5649 */ 5650 static 5651 SCIP_Bool isUsePreviousResult( 5652 SCIP* scip, /**< SCIP data structure */ 5653 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 5654 ) 5655 { 5656 PERSISTENTDATA* persistent; 5657 5658 assert(scip != NULL); 5659 assert(branchruledata != NULL); 5660 5661 persistent = branchruledata->persistent; 5662 assert(persistent != NULL); 5663 5664 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "check if previous result should be used: valid=%d, "\ 5665 "nodes=%lld (old=%lld), iterations=%lld (old=%lld), lps=%lld (old=%lld)\n", 5666 branchingDecisionIsValid(persistent->olddecision), 5667 SCIPgetNTotalNodes(scip), persistent->oldntotalnodes, 5668 SCIPgetNNodeLPIterations(scip), persistent->oldnnodelpiterations, 5669 SCIPgetNNodeLPs(scip) + SCIPgetNNodeZeroIterationLPs(scip), persistent->oldnnodelps); 5670 5671 return branchingDecisionIsValid(persistent->olddecision) 5672 && (persistent->oldntotalnodes == SCIPgetNTotalNodes(scip)) 5673 && (persistent->oldnnodelpiterations == SCIPgetNNodeLPIterations(scip)) 5674 && (persistent->oldnnodelps == SCIPgetNNodeLPs(scip) + SCIPgetNNodeZeroIterationLPs(scip)); 5675 } 5676 5677 /** 5678 * Uses the results from the previous run saved in the branchruledata to branch. 5679 * This is the case, if in the previous run only non-violating constraints were added. In that case we can use the 5680 * branching decision we would have made then. 5681 * If everything worked, the result pointer contains SCIP_BRANCHED. 5682 * 5683 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 5684 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 5685 */ 5686 static 5687 SCIP_RETCODE usePreviousResult( 5688 SCIP* scip, /**< SCIP data structure */ 5689 SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */ 5690 SCIP_RESULT* result /**< the pointer to the branching result */ 5691 ) 5692 { 5693 assert(scip != NULL); 5694 assert(branchruledata != NULL); 5695 assert(result != NULL); 5696 assert(branchruledata->config != NULL); 5697 assert(branchruledata->persistent != NULL); 5698 assert(branchruledata->persistent->olddecision != NULL); 5699 5700 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Branching based on previous solution.\n"); 5701 5702 /* execute the actual branching */ 5703 SCIP_CALL( branchOnVar(scip, branchruledata->config, branchruledata->persistent->olddecision) ); 5704 *result = SCIP_BRANCHED; 5705 5706 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: Branched based on previous solution. Variable <%s>\n", 5707 SCIPvarGetName(branchruledata->persistent->olddecision->branchvar)); 5708 5709 /* reset the var pointer, as this is our indicator whether we should branch on prev data in the next call */ 5710 branchruledata->persistent->olddecision->branchvar = NULL; 5711 5712 return SCIP_OKAY; 5713 } 5714 5715 /** free persistent data structure */ 5716 static 5717 SCIP_RETCODE freePersistent( 5718 SCIP* scip, /**< SCIP data structure */ 5719 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 5720 ) 5721 { 5722 PERSISTENTDATA* persistent; 5723 int nvars; 5724 int i; 5725 5726 assert(scip != NULL); 5727 assert(branchruledata != NULL); 5728 5729 persistent = branchruledata->persistent; 5730 assert(persistent != NULL); 5731 5732 nvars = persistent->nvars; 5733 5734 for( i = nvars - 1; i >= 0; i--) 5735 { 5736 assert(persistent->lastbranchdownres[i] != NULL); 5737 assert(persistent->lastbranchupres[i] != NULL); 5738 5739 SCIPfreeBlockMemory(scip, &persistent->lastbranchdownres[i]); /*lint !e866*/ 5740 SCIPfreeBlockMemory(scip, &persistent->lastbranchupres[i]); /*lint !e866*/ 5741 } 5742 5743 SCIPfreeBlockMemory(scip, &branchruledata->persistent->olddecision); 5744 5745 assert(persistent->lastbranchlpobjval != NULL); 5746 assert(persistent->lastbranchdownres != NULL); 5747 assert(persistent->lastbranchupres != NULL); 5748 assert(persistent->lastbranchnlps != NULL); 5749 assert(persistent->lastbranchid != NULL); 5750 5751 SCIPfreeBlockMemoryArray(scip, &persistent->lastbranchlpobjval, nvars); 5752 SCIPfreeBlockMemoryArray(scip, &persistent->lastbranchdownres, nvars); 5753 SCIPfreeBlockMemoryArray(scip, &persistent->lastbranchupres, nvars); 5754 SCIPfreeBlockMemoryArray(scip, &persistent->lastbranchnlps, nvars); 5755 SCIPfreeBlockMemoryArray(scip, &persistent->lastbranchid, nvars); 5756 5757 branchruledata->isinitialized = FALSE; 5758 5759 return SCIP_OKAY; 5760 } 5761 5762 /** initializes the branchruledata and the contained structs */ 5763 static 5764 SCIP_RETCODE initBranchruleData( 5765 SCIP* scip, /**< SCIP data structure */ 5766 SCIP_BRANCHRULEDATA* branchruledata /**< the branch rule data to initialize */ 5767 ) 5768 { 5769 int nvars; 5770 int i; 5771 5772 assert(scip != NULL); 5773 assert(branchruledata != NULL); 5774 5775 /* the branching rule data is already initialized and no new variables have been added in the meantime */ 5776 if( branchruledata->isinitialized && 5777 (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) == branchruledata->persistent->nvars) ) 5778 return SCIP_OKAY; 5779 5780 if( branchruledata->isinitialized ) 5781 { 5782 SCIP_CALL( freePersistent(scip, branchruledata) ); 5783 } 5784 5785 /* The variables given by the SCIPgetVars() array are sorted with the binaries at first and the integer variables 5786 * directly afterwards. With the SCIPvarGetProbindex() method we can access the index of a given variable in the 5787 * SCIPgetVars() array and as such we can use it to access our arrays which should only contain binary and integer 5788 * variables. 5789 */ 5790 nvars = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip); 5791 5792 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->persistent->lastbranchid, nvars) ); 5793 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->persistent->lastbranchnlps, nvars) ); 5794 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->persistent->lastbranchupres, nvars) ); 5795 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->persistent->lastbranchdownres, nvars) ); 5796 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->persistent->lastbranchlpobjval, nvars) ); 5797 branchruledata->persistent->nvars = nvars; 5798 branchruledata->persistent->oldntotalnodes = -1; 5799 branchruledata->persistent->oldnnodelpiterations = -1; 5800 branchruledata->persistent->oldnnodelps = -1; 5801 5802 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata->persistent->olddecision) ); 5803 branchingDecisionInit(scip, branchruledata->persistent->olddecision); 5804 5805 for( i = 0; i < nvars; i++ ) 5806 { 5807 branchruledata->persistent->lastbranchid[i] = -1; 5808 branchruledata->persistent->lastbranchnlps[i] = 0; 5809 5810 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata->persistent->lastbranchupres[i]) ); /*lint !e866*/ 5811 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata->persistent->lastbranchdownres[i]) ); /*lint !e866*/ 5812 } 5813 5814 branchruledata->isinitialized = TRUE; 5815 5816 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Initialized the branchruledata\n"); 5817 5818 return SCIP_OKAY; 5819 } 5820 5821 /* 5822 * Callback methods of branching rule 5823 */ 5824 5825 /** copy method for branchrule plugins (called when SCIP copies plugins) */ 5826 static 5827 SCIP_DECL_BRANCHCOPY(branchCopyLookahead) 5828 { /*lint --e{715}*/ 5829 assert(scip != NULL); 5830 assert(branchrule != NULL); 5831 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 5832 5833 return SCIP_OKAY; 5834 } 5835 5836 /** destructor of branching rule to free user data (called when SCIP is exiting) */ 5837 static 5838 SCIP_DECL_BRANCHFREE(branchFreeLookahead) 5839 { /*lint --e{715}*/ 5840 SCIP_BRANCHRULEDATA* branchruledata; 5841 5842 branchruledata = SCIPbranchruleGetData(branchrule); 5843 assert(branchruledata != NULL); 5844 assert(branchruledata->config != NULL); 5845 assert(branchruledata->persistent != NULL); 5846 5847 SCIPfreeBlockMemory(scip, &branchruledata->persistent); 5848 SCIPfreeBlockMemory(scip, &branchruledata->config); 5849 SCIPfreeBlockMemory(scip, &branchruledata); 5850 SCIPbranchruleSetData(branchrule, NULL); 5851 5852 return SCIP_OKAY; 5853 } 5854 5855 /** initialization method of branching rule (called after problem was transformed) */ 5856 static 5857 SCIP_DECL_BRANCHINIT(branchInitLookahead) 5858 { /*lint --e{715}*/ 5859 SCIP_BRANCHRULEDATA* branchruledata; 5860 5861 assert(scip != NULL); 5862 assert(branchrule != NULL); 5863 5864 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Entering branchInitLookahead\n"); 5865 5866 branchruledata = SCIPbranchruleGetData(branchrule); 5867 assert(branchruledata != NULL); 5868 assert(branchruledata->persistent != NULL); 5869 5870 branchruledata->persistent->restartindex = 0; 5871 5872 #ifdef SCIP_STATISTIC 5873 { 5874 int recursiondepth; 5875 int maxncands; 5876 5877 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Allocating space for the statistics struct.\n"); 5878 5879 recursiondepth = branchruledata->config->recursiondepth; 5880 maxncands = branchruledata->config->maxncands; 5881 maxncands = MIN(maxncands, SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)); 5882 5883 SCIP_CALL( SCIPallocMemory(scip, &branchruledata->statistics) ); 5884 /* RESULT enum is 1 based, so use MAXRESULT + 1 as array size with unused 0 element */ 5885 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nresults, MAXRESULT + 1) ); 5886 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nsinglecutoffs, recursiondepth) ); 5887 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nfullcutoffs, recursiondepth) ); 5888 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nlpssolved, recursiondepth) ); 5889 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nlpssolvedfsb, recursiondepth) ); 5890 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nlpiterations, recursiondepth) ); 5891 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nlpiterationsfsb, recursiondepth) ); 5892 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->nduplicatelps, recursiondepth) ); 5893 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->npropdomred, recursiondepth) ); 5894 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->noldbranchused, recursiondepth) ); 5895 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->noldbranchusedfsb, recursiondepth) ); 5896 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->chosenfsbcand, maxncands) ); 5897 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->domredafterfsb, recursiondepth) ); 5898 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->cutoffafterfsb, recursiondepth) ); 5899 SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->statistics->stopafterfsb, recursiondepth) ); 5900 5901 branchruledata->statistics->recursiondepth = recursiondepth; 5902 branchruledata->statistics->maxnbestcands = maxncands; 5903 5904 statisticsInit(branchruledata->statistics); 5905 } 5906 #endif 5907 5908 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Leaving branchInitLookahead\n"); 5909 5910 return SCIP_OKAY; 5911 } 5912 5913 5914 /** deinitialization method of branching rule (called before transformed problem is freed) */ 5915 static 5916 SCIP_DECL_BRANCHEXIT(branchExitLookahead) 5917 { /*lint --e{715}*/ 5918 #ifdef SCIP_STATISTIC 5919 SCIP_BRANCHRULEDATA* branchruledata; 5920 STATISTICS* statistics; 5921 5922 branchruledata = SCIPbranchruleGetData(branchrule); 5923 assert(branchruledata != NULL); 5924 5925 statistics = branchruledata->statistics; 5926 assert(statistics != NULL); 5927 5928 statisticsPrint(scip, statistics); 5929 5930 SCIPfreeMemoryArray(scip, &statistics->stopafterfsb); 5931 SCIPfreeMemoryArray(scip, &statistics->cutoffafterfsb); 5932 SCIPfreeMemoryArray(scip, &statistics->domredafterfsb); 5933 SCIPfreeMemoryArray(scip, &statistics->chosenfsbcand); 5934 SCIPfreeMemoryArray(scip, &statistics->noldbranchusedfsb); 5935 SCIPfreeMemoryArray(scip, &statistics->noldbranchused); 5936 SCIPfreeMemoryArray(scip, &statistics->npropdomred); 5937 SCIPfreeMemoryArray(scip, &statistics->nlpiterationsfsb); 5938 SCIPfreeMemoryArray(scip, &statistics->nlpiterations); 5939 SCIPfreeMemoryArray(scip, &statistics->nduplicatelps); 5940 SCIPfreeMemoryArray(scip, &statistics->nlpssolvedfsb); 5941 SCIPfreeMemoryArray(scip, &statistics->nlpssolved); 5942 SCIPfreeMemoryArray(scip, &statistics->nfullcutoffs); 5943 SCIPfreeMemoryArray(scip, &statistics->nsinglecutoffs); 5944 SCIPfreeMemoryArray(scip, &statistics->nresults); 5945 SCIPfreeMemory(scip, &statistics); 5946 #endif 5947 5948 return SCIP_OKAY; 5949 } 5950 5951 /** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */ 5952 static 5953 SCIP_DECL_BRANCHEXITSOL(branchExitSolLookahead) 5954 { /*lint --e{715}*/ 5955 SCIP_BRANCHRULEDATA* branchruledata; 5956 5957 branchruledata = SCIPbranchruleGetData(branchrule); 5958 assert(branchruledata != NULL); 5959 5960 if( branchruledata->isinitialized ) 5961 { 5962 SCIP_CALL( freePersistent(scip, branchruledata) ); 5963 } 5964 5965 return SCIP_OKAY; 5966 } 5967 5968 /** branching execution method for fractional LP solutions */ 5969 static 5970 SCIP_DECL_BRANCHEXECLP(branchExeclpLookahead) 5971 { /*lint --e{715}*/ 5972 SCIP_BRANCHRULEDATA* branchruledata; 5973 CONFIGURATION* config; 5974 SCIP_Bool userusebincons; 5975 5976 assert(branchrule != NULL); 5977 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0); 5978 assert(scip != NULL); 5979 assert(result != NULL); 5980 5981 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Entering branchExeclpLookahead at node %lld.\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip))); 5982 5983 branchruledata = SCIPbranchruleGetData(branchrule); 5984 assert(branchruledata != NULL); 5985 5986 config = branchruledata->config; 5987 5988 /* we are only allowed to add binary constraints, if the corresponding flag is given */ 5989 userusebincons = config->usebincons; 5990 config->usebincons = config->usebincons && allowaddcons; 5991 5992 SCIP_CALL( initBranchruleData(scip, branchruledata) ); 5993 5994 if( config->storeunviolatedsol 5995 && isUsePreviousResult(scip, branchruledata) ) 5996 { 5997 /* in case we stopped the previous run without a branching decision, we have stored the decision and execute it 5998 * now */ 5999 SCIP_CALL( usePreviousResult(scip, branchruledata, result) ); 6000 6001 #ifdef SCIP_STATISTIC 6002 branchruledata->statistics->noldcandidate++; 6003 #endif 6004 } 6005 else 6006 { 6007 BRANCHINGDECISION* decision; 6008 SCORECONTAINER* scorecontainer = NULL; 6009 CANDIDATELIST* candidatelist; 6010 STATUS* status; 6011 #ifdef SCIP_STATISTIC 6012 LOCALSTATISTICS* localstats; 6013 #endif 6014 6015 /* create a struct to store the algorithm status */ 6016 SCIP_CALL( statusCreate(scip, &status) ); 6017 6018 /* create a struct to store the branching decision (in case there is one) */ 6019 SCIP_CALL( branchingDecisionCreate(scip, &decision) ); 6020 if( config->abbreviated ) 6021 { 6022 /* allocate and init the container used to store the FSB scores, later used to filter the candidates */ 6023 SCIP_CALL( scoreContainerCreate(scip, &scorecontainer, config) ); 6024 } 6025 6026 SCIP_CALL( candidateListGetAllFractionalCandidates(scip, &candidatelist) ); 6027 6028 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The base lp has <%i> variables with fractional value.\n", 6029 candidatelist->ncandidates); 6030 6031 /* execute the main logic */ 6032 #ifdef SCIP_STATISTIC 6033 /* create a struct to store the statistics needed for this single run */ 6034 SCIP_CALL( localStatisticsAllocate(scip, &localstats) ); 6035 SCIP_CALL( selectVarStart(scip, config, branchruledata->persistent, status, decision, 6036 scorecontainer, candidatelist, branchruledata->statistics, localstats) ); 6037 #else 6038 SCIP_CALL( selectVarStart(scip, config, branchruledata->persistent, status, decision, 6039 scorecontainer, candidatelist) ); 6040 #endif 6041 6042 if( status->cutoff || status->domredcutoff ) 6043 { 6044 *result = SCIP_CUTOFF; 6045 #ifdef SCIP_STATISTIC 6046 branchruledata->statistics->ncutoffproofnodes += localstats->ncutoffproofnodes; 6047 #endif 6048 } 6049 else if( status->addedbinconss ) 6050 { 6051 *result = SCIP_CONSADDED; 6052 } 6053 else if( status->domred ) 6054 { 6055 *result = SCIP_REDUCEDDOM; 6056 } 6057 else if( status->lperror ) 6058 { 6059 #ifdef SCIP_STATISTIC 6060 ++branchruledata->statistics->nlperrorcalls; 6061 #endif 6062 if( !branchingDecisionIsValid(decision) ) 6063 { 6064 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "LP error with no valid candidate: select first candidate variable\n"); 6065 6066 assert(candidatelist->ncandidates > 0); 6067 decision->branchvar = candidatelist->candidates[0]->branchvar; 6068 decision->branchval = candidatelist->candidates[0]->branchval; 6069 } 6070 } 6071 else if( status->maxnconsreached ) 6072 { 6073 /* this case may occure if the domain reductions that reached the limit were already applied via domain 6074 * propagation 6075 */ 6076 *result = SCIP_REDUCEDDOM; 6077 } 6078 #ifdef SCIP_STATISTIC 6079 else if( status->limitreached ) 6080 { 6081 ++branchruledata->statistics->nlimitcalls; 6082 } 6083 #endif 6084 6085 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Result before branching is %s\n", getStatusString(*result)); 6086 6087 if( *result != SCIP_CUTOFF /* a variable could not be branched in any direction or any of the calculated domain 6088 * reductions was infeasible */ 6089 && *result != SCIP_REDUCEDDOM /* the domain of a variable was reduced by evaluating the calculated cutoffs */ 6090 && *result != SCIP_CONSADDED /* implicit binary constraints were already added */ 6091 && !status->depthtoosmall /* branching depth wasn't high enough */ 6092 && branchingDecisionIsValid(decision) 6093 /*&& (0 <= bestcand && bestcand < nlpcands)*/ /* no valid candidate index could be found */ 6094 ) 6095 { 6096 LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> %d candidates, selected variable <%s> (solval=%g, down=%.9g, " 6097 "up=%.9g)\n", candidatelist->ncandidates, SCIPvarGetName(decision->branchvar), decision->branchval, 6098 decision->downdb, decision->updb); 6099 6100 /* execute the branching as a result of the branching logic */ 6101 SCIP_CALL( branchOnVar(scip, config, decision) ); 6102 6103 *result = SCIP_BRANCHED; 6104 } 6105 6106 #ifdef SCIP_DEBUG 6107 LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Result after branching is %s\n", getStatusString(*result)); 6108 6109 if( *result == SCIP_BRANCHED ) 6110 { 6111 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: Finished LookaheadBranching by branching.\n"); 6112 } 6113 else if( *result == SCIP_REDUCEDDOM ) 6114 { 6115 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: Finished LookaheadBranching by reducing domains.\n"); 6116 } 6117 else if( *result == SCIP_CUTOFF ) 6118 { 6119 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: Finished LookaheadBranching by cutting off, as the current " 6120 "problem is infeasible.\n"); 6121 } 6122 else if( *result == SCIP_CONSADDED ) 6123 { 6124 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: Finished LookaheadBranching by adding constraints.\n"); 6125 } 6126 else if( status->depthtoosmall ) 6127 { 6128 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: The remaining tree depth did not allow for multi level " 6129 "lookahead branching.\n"); 6130 } 6131 else 6132 { 6133 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Result: Could not find any variable to branch on.\n"); 6134 } 6135 #endif 6136 6137 #ifdef SCIP_STATISTIC 6138 localStatisticsFree(scip, &localstats); 6139 #endif 6140 SCIP_CALL( candidateListFree(scip, &candidatelist) ); 6141 6142 /* scorecontainer != NULL iff branchruledata->config->abbreviated == TRUE */ 6143 if( scorecontainer != NULL ) 6144 { 6145 SCIP_CALL( scoreContainerFree(scip, &scorecontainer) ); 6146 } 6147 branchingDecisionFree(scip, &decision); 6148 statusFree(scip, &status); 6149 } 6150 6151 #ifdef SCIP_STATISTIC 6152 assert(*result >= 1); 6153 assert(*result <= MAXRESULT); 6154 branchruledata->statistics->ntotalresults++; 6155 branchruledata->statistics->nresults[*result]++; 6156 6157 if( config->abbreviated ) 6158 { 6159 int sum; 6160 int i; 6161 6162 sum = branchruledata->statistics->nsinglecandidate + branchruledata->statistics->nsingleafterfilter 6163 + branchruledata->statistics->noldcandidate + branchruledata->statistics->nlperrorcalls 6164 + branchruledata->statistics->nlimitcalls; 6165 6166 for( i = 0; i < branchruledata->statistics->maxnbestcands; i++ ) 6167 { 6168 sum += branchruledata->statistics->chosenfsbcand[i]; 6169 } 6170 if( sum != branchruledata->statistics->nresults[SCIP_BRANCHED] ) 6171 { 6172 printf("branched = %d != sum = %d (%d/%d/%d/%d/%d)\n", 6173 branchruledata->statistics->nresults[SCIP_BRANCHED], sum, 6174 branchruledata->statistics->nsinglecandidate, branchruledata->statistics->nsingleafterfilter, 6175 branchruledata->statistics->noldcandidate, 6176 branchruledata->statistics->nlperrorcalls, branchruledata->statistics->nlimitcalls); 6177 assert(SCIPisStopped(scip)); 6178 } 6179 assert(sum == branchruledata->statistics->nresults[SCIP_BRANCHED]); 6180 } 6181 6182 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "#### ncutoffproofnodes: %d ndomredproofnodes: %d\n", 6183 branchruledata->statistics->ncutoffproofnodes, branchruledata->statistics->ndomredproofnodes); 6184 #endif 6185 6186 config->usebincons = userusebincons; 6187 6188 LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Exiting branchExeclpLookahead.\n"); 6189 return SCIP_OKAY; 6190 } 6191 6192 /* 6193 * branching rule specific interface methods 6194 */ 6195 6196 /** creates the lookahead branching rule and includes it in SCIP */ 6197 SCIP_RETCODE SCIPincludeBranchruleLookahead( 6198 SCIP* scip /**< SCIP data structure */ 6199 ) 6200 { 6201 SCIP_BRANCHRULEDATA* branchruledata; 6202 SCIP_BRANCHRULE* branchrule; 6203 6204 /* create lookahead branching rule data */ 6205 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) ); 6206 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata->config) ); 6207 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata->persistent) ); 6208 branchruledata->persistent->restartindex = 0; 6209 branchruledata->isinitialized = FALSE; 6210 branchruledata->config->inscoring = FALSE; 6211 6212 /* include branching rule */ 6213 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, 6214 BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) ); 6215 6216 assert(branchrule != NULL); 6217 6218 /* set non fundamental callbacks via setter functions */ 6219 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyLookahead) ); 6220 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeLookahead) ); 6221 SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitLookahead) ); 6222 SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitLookahead) ); 6223 SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitSolLookahead) ); 6224 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpLookahead) ); 6225 6226 /* add lookahead branching rule parameters */ 6227 SCIP_CALL( SCIPaddBoolParam(scip, 6228 "branching/lookahead/useimpliedbincons", 6229 "should binary constraints be collected and applied?", 6230 &branchruledata->config->usebincons, TRUE, DEFAULT_USEBINARYCONSTRAINTS, NULL, NULL) ); 6231 SCIP_CALL( SCIPaddIntParam(scip, 6232 "branching/lookahead/addbinconsrow", 6233 "should binary constraints be added as rows to the base LP? (0: no, 1: separate, 2: as initial rows)", 6234 &branchruledata->config->addbinconsrow, TRUE, DEFAULT_ADDBINCONSROW, 0, 2, NULL, NULL) ); 6235 SCIP_CALL( SCIPaddIntParam(scip, "branching/lookahead/maxnviolatedcons", 6236 "how many constraints that are violated by the base lp solution should be gathered until the rule is stopped and "\ 6237 "they are added? [0 for unrestricted]", 6238 &branchruledata->config->maxnviolatedcons, TRUE, DEFAULT_MAXNVIOLATEDCONS, 0, INT_MAX, NULL, NULL) ); 6239 SCIP_CALL( SCIPaddIntParam(scip, "branching/lookahead/maxnviolatedbincons", 6240 "how many binary constraints that are violated by the base lp solution should be gathered until the rule is "\ 6241 "stopped and they are added? [0 for unrestricted]", 6242 &branchruledata->config->maxnviolatedbincons, TRUE, DEFAULT_MAXNVIOLATEDBINCONS, 0, INT_MAX, NULL, NULL) ); 6243 SCIP_CALL( SCIPaddIntParam(scip, "branching/lookahead/maxnviolateddomreds", 6244 "how many domain reductions that are violated by the base lp solution should be gathered until the rule is "\ 6245 "stopped and they are added? [0 for unrestricted]", 6246 &branchruledata->config->maxnviolateddomreds, TRUE, DEFAULT_MAXNVIOLATEDDOMREDS, 0, INT_MAX, NULL, NULL) ); 6247 SCIP_CALL( SCIPaddLongintParam(scip, 6248 "branching/lookahead/reevalage", 6249 "max number of LPs solved after which a previous prob branching results are recalculated", 6250 &branchruledata->config->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 6251 SCIP_CALL( SCIPaddLongintParam(scip, 6252 "branching/lookahead/reevalagefsb", 6253 "max number of LPs solved after which a previous FSB scoring results are recalculated", 6254 &branchruledata->config->reevalagefsb, TRUE, DEFAULT_REEVALAGEFSB, 0LL, SCIP_LONGINT_MAX, NULL, NULL) ); 6255 SCIP_CALL( SCIPaddIntParam(scip, "branching/lookahead/recursiondepth", 6256 "the max depth of LAB.", 6257 &branchruledata->config->recursiondepth, TRUE, DEFAULT_RECURSIONDEPTH, 1, INT_MAX, NULL, NULL) ); 6258 SCIP_CALL( SCIPaddBoolParam(scip, 6259 "branching/lookahead/usedomainreduction", 6260 "should domain reductions be collected and applied?", 6261 &branchruledata->config->usedomainreduction, TRUE, DEFAULT_USEDOMAINREDUCTION, NULL, NULL) ); 6262 SCIP_CALL( SCIPaddBoolParam(scip, 6263 "branching/lookahead/mergedomainreductions", 6264 "should domain reductions of feasible siblings should be merged?", 6265 &branchruledata->config->mergedomainreductions, TRUE, DEFAULT_MERGEDOMAINREDUCTIONS, NULL, NULL) ); 6266 SCIP_CALL( SCIPaddBoolParam(scip, 6267 "branching/lookahead/prefersimplebounds", 6268 "should domain reductions only be applied if there are simple bound changes?", 6269 &branchruledata->config->prefersimplebounds, TRUE, DEFAULT_PREFERSIMPLEBOUNDS, NULL, NULL) ); 6270 SCIP_CALL( SCIPaddBoolParam(scip, 6271 "branching/lookahead/onlyvioldomreds", 6272 "should only domain reductions that violate the LP solution be applied?", 6273 &branchruledata->config->onlyvioldomreds, TRUE, DEFAULT_ONLYVIOLDOMREDS, NULL, NULL) ); 6274 SCIP_CALL( SCIPaddBoolParam(scip, 6275 "branching/lookahead/addnonviocons", 6276 "should binary constraints, that are not violated by the base LP, be collected and added?", 6277 &branchruledata->config->addnonviocons, TRUE, DEFAULT_ADDNONVIOCONS, NULL, NULL) ); 6278 SCIP_CALL( SCIPaddBoolParam(scip, 6279 "branching/lookahead/abbreviated", 6280 "toggles the abbreviated LAB.", 6281 &branchruledata->config->abbreviated, TRUE, DEFAULT_ABBREVIATED, NULL, NULL) ); 6282 SCIP_CALL( SCIPaddIntParam(scip, "branching/lookahead/maxncands", 6283 "if abbreviated: The max number of candidates to consider at the node.", 6284 &branchruledata->config->maxncands, TRUE, DEFAULT_MAXNCANDS, 1, INT_MAX, NULL, NULL) ); 6285 SCIP_CALL( SCIPaddIntParam(scip, "branching/lookahead/maxndeepercands", 6286 "if abbreviated: The max number of candidates to consider per deeper node.", 6287 &branchruledata->config->maxndeepercands, TRUE, DEFAULT_MAXNDEEPERCANDS, 0, INT_MAX, NULL, NULL) ); 6288 SCIP_CALL( SCIPaddBoolParam(scip, 6289 "branching/lookahead/reusebasis", 6290 "if abbreviated: Should the information gathered to obtain the best candidates be reused?", 6291 &branchruledata->config->reusebasis, TRUE, DEFAULT_REUSEBASIS, NULL, NULL) ); 6292 SCIP_CALL( SCIPaddBoolParam(scip, 6293 "branching/lookahead/storeunviolatedsol", 6294 "if only non violating constraints are added, should the branching decision be stored till the next call?", 6295 &branchruledata->config->storeunviolatedsol, TRUE, DEFAULT_STOREUNVIOLATEDSOL, NULL, NULL) ); 6296 SCIP_CALL( SCIPaddBoolParam(scip, 6297 "branching/lookahead/abbrevpseudo", 6298 "if abbreviated: Use pseudo costs to estimate the score of a candidate.", 6299 &branchruledata->config->abbrevpseudo, TRUE, DEFAULT_ABBREVPSEUDO, NULL, NULL) ); 6300 SCIP_CALL( SCIPaddBoolParam(scip, 6301 "branching/lookahead/level2avgscore", 6302 "should the average score be used for uninitialized scores in level 2?", 6303 &branchruledata->config->level2avgscore, TRUE, DEFAULT_LEVEL2AVGSCORE, NULL, NULL) ); 6304 SCIP_CALL( SCIPaddBoolParam(scip, 6305 "branching/lookahead/level2zeroscore", 6306 "should uninitialized scores in level 2 be set to 0?", 6307 &branchruledata->config->level2zeroscore, TRUE, DEFAULT_LEVEL2ZEROSCORE, NULL, NULL) ); 6308 SCIP_CALL( SCIPaddBoolParam(scip, 6309 "branching/lookahead/addclique", 6310 "add binary constraints with two variables found at the root node also as a clique", 6311 &branchruledata->config->addclique, TRUE, DEFAULT_ADDCLIQUE, NULL, NULL) ); 6312 SCIP_CALL( SCIPaddBoolParam(scip, 6313 "branching/lookahead/propagate", 6314 "should domain propagation be executed before each temporary node is solved?", 6315 &branchruledata->config->propagate, TRUE, DEFAULT_PROPAGATE, NULL, NULL) ); 6316 SCIP_CALL( SCIPaddBoolParam(scip, 6317 "branching/lookahead/uselevel2data", 6318 "should branching data generated at depth level 2 be stored for re-using it?", 6319 &branchruledata->config->uselevel2data, TRUE, DEFAULT_USELEVEL2DATA, NULL, NULL) ); 6320 SCIP_CALL( SCIPaddBoolParam(scip, 6321 "branching/lookahead/applychildbounds", 6322 "should bounds known for child nodes be applied?", 6323 &branchruledata->config->applychildbounds, TRUE, DEFAULT_APPLYCHILDBOUNDS, NULL, NULL) ); 6324 SCIP_CALL( SCIPaddBoolParam(scip, 6325 "branching/lookahead/enforcemaxdomreds", 6326 "should the maximum number of domain reductions maxnviolateddomreds be enforced?", 6327 &branchruledata->config->enforcemaxdomreds, TRUE, DEFAULT_ENFORCEMAXDOMREDS, NULL, NULL) ); 6328 SCIP_CALL( SCIPaddBoolParam(scip, 6329 "branching/lookahead/updatebranchingresults", 6330 "should branching results (and scores) be updated w.r.t. proven dual bounds?", 6331 &branchruledata->config->updatebranchingresults, TRUE, DEFAULT_UPDATEBRANCHINGRESULTS, NULL, NULL) ); 6332 SCIP_CALL( SCIPaddIntParam(scip, 6333 "branching/lookahead/maxproprounds", 6334 "maximum number of propagation rounds to perform at each temporary node (-1: unlimited, 0: SCIP default)", 6335 &branchruledata->config->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) ); 6336 SCIP_CALL( SCIPaddCharParam(scip, 6337 "branching/lookahead/scoringfunction", 6338 "scoring function to be used at the base level", 6339 &branchruledata->config->scoringfunction, TRUE, DEFAULT_SCORINGFUNCTION, "dfswplcra", NULL, NULL) ); 6340 SCIP_CALL( SCIPaddCharParam(scip, 6341 "branching/lookahead/deeperscoringfunction", 6342 "scoring function to be used at deeper levels", 6343 &branchruledata->config->deeperscoringfunction, TRUE, DEFAULT_DEEPERSCORINGFUNCTION, "dfswlcrx", NULL, NULL) ); 6344 SCIP_CALL( SCIPaddCharParam(scip, 6345 "branching/lookahead/scoringscoringfunction", 6346 "scoring function to be used during FSB scoring", 6347 &branchruledata->config->scoringscoringfunction, TRUE, DEFAULT_SCORINGSCORINGFUNCTION, "dfswlcr", NULL, NULL) ); 6348 SCIP_CALL( SCIPaddRealParam(scip, 6349 "branching/lookahead/minweight", 6350 "if scoringfunction is 's', this value is used to weight the min of the gains of two child problems in the convex combination", 6351 &branchruledata->config->minweight, TRUE, DEFAULT_MINWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) ); 6352 SCIP_CALL( SCIPaddRealParam(scip, 6353 "branching/lookahead/worsefactor", 6354 "if the FSB score is of a candidate is worse than the best by this factor, skip this candidate (-1: disable)", 6355 &branchruledata->config->worsefactor, TRUE, DEFAULT_WORSEFACTOR, -1.0, SCIP_REAL_MAX, NULL, NULL) ); 6356 SCIP_CALL( SCIPaddBoolParam(scip, 6357 "branching/lookahead/filterbymaxgain", 6358 "should lookahead branching only be applied if the max gain in level 1 is not uniquely that of the best candidate?", 6359 &branchruledata->config->filterbymaxgain, TRUE, DEFAULT_FILTERBYMAXGAIN, NULL, NULL) ); 6360 6361 return SCIP_OKAY; 6362 } 6363