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 scip_branch.c 26 * @ingroup OTHER_CFILES 27 * @brief public methods for branching rule plugins and branching 28 * @author Tobias Achterberg 29 * @author Timo Berthold 30 * @author Gerald Gamrath 31 * @author Leona Gottwald 32 * @author Stefan Heinz 33 * @author Gregor Hendel 34 * @author Thorsten Koch 35 * @author Alexander Martin 36 * @author Marc Pfetsch 37 * @author Michael Winkler 38 * @author Kati Wolter 39 * 40 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE 41 */ 42 43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 44 45 #include "scip/branch.h" 46 #include "scip/debug.h" 47 #include "scip/lp.h" 48 #include "scip/pub_message.h" 49 #include "scip/pub_var.h" 50 #include "scip/var.h" 51 #include "scip/scip_branch.h" 52 #include "scip/scip_numerics.h" 53 #include "scip/set.h" 54 #include "scip/struct_mem.h" 55 #include "scip/struct_primal.h" 56 #include "scip/struct_scip.h" 57 #include "scip/struct_set.h" 58 #include "scip/struct_var.h" 59 #include "scip/tree.h" 60 61 62 /** creates a branching rule and includes it in SCIP 63 * 64 * @note method has all branching rule callbacks as arguments and is thus changed every time a new 65 * callback is added in future releases; consider using SCIPincludeBranchruleBasic() and setter functions 66 * if you seek for a method which is less likely to change in future releases 67 */ 68 SCIP_RETCODE SCIPincludeBranchrule( 69 SCIP* scip, /**< SCIP data structure */ 70 const char* name, /**< name of branching rule */ 71 const char* desc, /**< description of branching rule */ 72 int priority, /**< priority of the branching rule */ 73 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */ 74 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound 75 * compared to best node's dual bound for applying branching rule 76 * (0.0: only on current best node, 1.0: on all nodes) */ 77 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */ 78 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */ 79 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */ 80 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */ 81 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */ 82 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */ 83 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */ 84 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */ 85 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */ 86 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 87 ) 88 { 89 SCIP_BRANCHRULE* branchrule; 90 91 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchrule", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 92 93 /* check whether branching rule is already present */ 94 if( SCIPfindBranchrule(scip, name) != NULL ) 95 { 96 SCIPerrorMessage("branching rule <%s> already included.\n", name); 97 return SCIP_INVALIDDATA; 98 } 99 100 SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem, 101 name, desc, priority, maxdepth, 102 maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol, 103 branchexeclp, branchexecext, branchexecps, branchruledata) ); 104 SCIP_CALL( SCIPsetIncludeBranchrule(scip->set, branchrule) ); 105 106 return SCIP_OKAY; 107 } 108 109 /** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL. 110 * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(), 111 * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(), 112 * SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecExt(), and SCIPsetBranchruleExecPs(). 113 * 114 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead 115 */ 116 SCIP_RETCODE SCIPincludeBranchruleBasic( 117 SCIP* scip, /**< SCIP data structure */ 118 SCIP_BRANCHRULE** branchruleptr, /**< pointer to branching rule, or NULL */ 119 const char* name, /**< name of branching rule */ 120 const char* desc, /**< description of branching rule */ 121 int priority, /**< priority of the branching rule */ 122 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */ 123 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound 124 * compared to best node's dual bound for applying branching rule 125 * (0.0: only on current best node, 1.0: on all nodes) */ 126 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 127 ) 128 { 129 SCIP_BRANCHRULE* branchrule; 130 131 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchruleBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 132 133 /* check whether branching rule is already present */ 134 if( SCIPfindBranchrule(scip, name) != NULL ) 135 { 136 SCIPerrorMessage("branching rule <%s> already included.\n", name); 137 return SCIP_INVALIDDATA; 138 } 139 140 SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, maxdepth, 141 maxbounddist, NULL, NULL, NULL, NULL, NULL, NULL, 142 NULL, NULL, NULL, branchruledata) ); 143 144 SCIP_CALL( SCIPsetIncludeBranchrule(scip->set, branchrule) ); 145 146 if( branchruleptr != NULL ) 147 *branchruleptr = branchrule; 148 149 return SCIP_OKAY; 150 } 151 152 /** sets copy method of branching rule */ 153 SCIP_RETCODE SCIPsetBranchruleCopy( 154 SCIP* scip, /**< SCIP data structure */ 155 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 156 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */ 157 ) 158 { 159 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 160 161 assert(branchrule != NULL); 162 163 SCIPbranchruleSetCopy(branchrule, branchcopy); 164 165 return SCIP_OKAY; 166 } 167 168 /** sets destructor method of branching rule */ 169 SCIP_RETCODE SCIPsetBranchruleFree( 170 SCIP* scip, /**< SCIP data structure */ 171 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 172 SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */ 173 ) 174 { 175 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 176 177 assert(branchrule != NULL); 178 179 SCIPbranchruleSetFree(branchrule, branchfree); 180 181 return SCIP_OKAY; 182 } 183 184 /** sets initialization method of branching rule */ 185 SCIP_RETCODE SCIPsetBranchruleInit( 186 SCIP* scip, /**< SCIP data structure */ 187 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 188 SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */ 189 ) 190 { 191 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 192 193 assert(branchrule != NULL); 194 195 SCIPbranchruleSetInit(branchrule, branchinit); 196 197 return SCIP_OKAY; 198 } 199 200 /** sets deinitialization method of branching rule */ 201 SCIP_RETCODE SCIPsetBranchruleExit( 202 SCIP* scip, /**< SCIP data structure */ 203 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 204 SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */ 205 ) 206 { 207 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 208 209 assert(branchrule != NULL); 210 211 SCIPbranchruleSetExit(branchrule, branchexit); 212 213 return SCIP_OKAY; 214 } 215 216 /** sets solving process initialization method of branching rule */ 217 SCIP_RETCODE SCIPsetBranchruleInitsol( 218 SCIP* scip, /**< SCIP data structure */ 219 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 220 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */ 221 ) 222 { 223 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 224 225 assert(branchrule != NULL); 226 227 SCIPbranchruleSetInitsol(branchrule, branchinitsol); 228 229 return SCIP_OKAY; 230 } 231 232 /** sets solving process deinitialization method of branching rule */ 233 SCIP_RETCODE SCIPsetBranchruleExitsol( 234 SCIP* scip, /**< SCIP data structure */ 235 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 236 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */ 237 ) 238 { 239 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 240 241 assert(branchrule != NULL); 242 243 SCIPbranchruleSetExitsol(branchrule, branchexitsol); 244 245 return SCIP_OKAY; 246 } 247 248 /** sets branching execution method for fractional LP solutions */ 249 SCIP_RETCODE SCIPsetBranchruleExecLp( 250 SCIP* scip, /**< SCIP data structure */ 251 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 252 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */ 253 ) 254 { 255 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecLp", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 256 257 assert(branchrule != NULL); 258 259 SCIPbranchruleSetExecLp(branchrule, branchexeclp); 260 261 return SCIP_OKAY; 262 } 263 264 /** sets branching execution method for external candidates */ 265 SCIP_RETCODE SCIPsetBranchruleExecExt( 266 SCIP* scip, /**< SCIP data structure */ 267 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 268 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */ 269 ) 270 { 271 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecExt", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 272 273 assert(branchrule != NULL); 274 275 SCIPbranchruleSetExecExt(branchrule, branchexecext); 276 277 return SCIP_OKAY; 278 } 279 280 /** sets branching execution method for not completely fixed pseudo solutions */ 281 SCIP_RETCODE SCIPsetBranchruleExecPs( 282 SCIP* scip, /**< SCIP data structure */ 283 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 284 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */ 285 ) 286 { 287 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecPs", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) ); 288 289 assert(branchrule != NULL); 290 291 SCIPbranchruleSetExecPs(branchrule, branchexecps); 292 293 return SCIP_OKAY; 294 } 295 296 /** returns the branching rule of the given name, or NULL if not existing */ 297 SCIP_BRANCHRULE* SCIPfindBranchrule( 298 SCIP* scip, /**< SCIP data structure */ 299 const char* name /**< name of branching rule */ 300 ) 301 { 302 assert(scip != NULL); 303 assert(scip->set != NULL); 304 assert(name != NULL); 305 306 SCIPsetSortBranchrules(scip->set); 307 308 return SCIPsetFindBranchrule(scip->set, name); 309 } 310 311 /** returns the array of currently available branching rules */ 312 SCIP_BRANCHRULE** SCIPgetBranchrules( 313 SCIP* scip /**< SCIP data structure */ 314 ) 315 { 316 assert(scip != NULL); 317 assert(scip->set != NULL); 318 319 return scip->set->branchrules; 320 } 321 322 /** returns the number of currently available branching rules */ 323 int SCIPgetNBranchrules( 324 SCIP* scip /**< SCIP data structure */ 325 ) 326 { 327 assert(scip != NULL); 328 assert(scip->set != NULL); 329 330 return scip->set->nbranchrules; 331 } 332 333 /** sets the priority of a branching rule */ 334 SCIP_RETCODE SCIPsetBranchrulePriority( 335 SCIP* scip, /**< SCIP data structure */ 336 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 337 int priority /**< new priority of the branching rule */ 338 ) 339 { 340 assert(scip != NULL); 341 assert(scip->set != NULL); 342 343 SCIPbranchruleSetPriority(branchrule, scip->set, priority); 344 345 return SCIP_OKAY; 346 } 347 348 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */ 349 SCIP_RETCODE SCIPsetBranchruleMaxdepth( 350 SCIP* scip, /**< SCIP data structure */ 351 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 352 int maxdepth /**< new maxdepth of the branching rule */ 353 ) 354 { 355 assert(scip != NULL); 356 assert(scip->set != NULL); 357 358 SCIPbranchruleSetMaxdepth(branchrule, maxdepth); 359 360 return SCIP_OKAY; 361 } 362 363 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */ 364 SCIP_RETCODE SCIPsetBranchruleMaxbounddist( 365 SCIP* scip, /**< SCIP data structure */ 366 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 367 SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */ 368 ) 369 { 370 assert(scip != NULL); 371 assert(scip->set != NULL); 372 373 SCIPbranchruleSetMaxbounddist(branchrule, maxbounddist); 374 375 return SCIP_OKAY; 376 } 377 378 /** gets branching candidates for LP solution branching (fractional variables) along with solution values, 379 * fractionalities, and number of branching candidates; The number of branching candidates does NOT 380 * account for fractional implicit integer variables which should not be used for branching decisions. 381 * 382 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1 383 * 384 * branching rules should always select the branching candidate among the first npriolpcands of the candidate 385 * list 386 * 387 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 388 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 389 * 390 * @pre This method can be called if @p scip is in one of the following stages: 391 * - \ref SCIP_STAGE_SOLVING 392 * 393 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 394 */ 395 SCIP_RETCODE SCIPgetLPBranchCands( 396 SCIP* scip, /**< SCIP data structure */ 397 SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */ 398 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */ 399 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */ 400 int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */ 401 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */ 402 int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */ 403 ) 404 { 405 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 406 407 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 408 { 409 SCIPerrorMessage("LP not solved to optimality - solstat=%d\n", SCIPlpGetSolstat(scip->lp)); 410 return SCIP_INVALIDDATA; 411 } 412 413 SCIP_CALL( SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp, 414 lpcands, lpcandssol, lpcandsfrac, nlpcands, npriolpcands, nfracimplvars) ); 415 416 return SCIP_OKAY; 417 } 418 419 /** gets number of branching candidates for LP solution branching (number of fractional variables) 420 * 421 * @return the number of branching candidates for LP solution branching (number of fractional variables). 422 * 423 * @pre This method can be called if @p scip is in one of the following stages: 424 * - \ref SCIP_STAGE_SOLVING 425 * 426 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 427 */ 428 int SCIPgetNLPBranchCands( 429 SCIP* scip /**< SCIP data structure */ 430 ) 431 { 432 SCIP_RETCODE retcode; 433 int nlpcands; 434 435 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 436 437 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 438 { 439 SCIPerrorMessage("LP not solved to optimality\n"); 440 SCIPABORT(); 441 return 0; /*lint !e527*/ 442 } 443 444 retcode = SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp, 445 NULL, NULL, NULL, &nlpcands, NULL, NULL); 446 447 if( retcode != SCIP_OKAY ) 448 { 449 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates\n", retcode); 450 SCIPABORT(); 451 return 0; /*lint !e527*/ 452 } 453 454 return nlpcands; 455 } 456 457 /** gets number of branching candidates with maximal priority for LP solution branching 458 * 459 * @return the number of branching candidates with maximal priority for LP solution branching. 460 * 461 * @pre This method can be called if @p scip is in one of the following stages: 462 * - \ref SCIP_STAGE_SOLVING 463 * 464 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 465 */ 466 int SCIPgetNPrioLPBranchCands( 467 SCIP* scip /**< SCIP data structure */ 468 ) 469 { 470 SCIP_RETCODE retcode; 471 int npriolpcands; 472 473 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 474 475 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY ) 476 { 477 SCIPerrorMessage("LP not solved to optimality\n"); 478 SCIPABORT(); 479 return 0; /*lint !e527*/ 480 } 481 482 retcode = SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp, 483 NULL, NULL, NULL, NULL, &npriolpcands, NULL); 484 485 if( retcode != SCIP_OKAY ) 486 { 487 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates with maximal priority\n", retcode); 488 SCIPABORT(); 489 return 0; /*lint !e527*/ 490 } 491 492 return npriolpcands; 493 } 494 495 /** gets external branching candidates along with solution values, scores, and number of branching candidates; 496 * these branching candidates can be used by relaxations or nonlinear constraint handlers; 497 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate 498 * list 499 * 500 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 501 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 502 * 503 * @pre This method can be called if @p scip is in one of the following stages: 504 * - \ref SCIP_STAGE_SOLVING 505 * 506 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 507 * 508 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and 509 * continuous last. 510 */ 511 SCIP_RETCODE SCIPgetExternBranchCands( 512 SCIP* scip, /**< SCIP data structure */ 513 SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */ 514 SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */ 515 SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */ 516 int* nexterncands, /**< pointer to store the number of extern branching candidates, or NULL */ 517 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */ 518 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */ 519 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */ 520 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority, 521 * or NULL */ 522 ) 523 { 524 assert(scip != NULL); 525 526 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 527 528 SCIP_CALL( SCIPbranchcandGetExternCands(scip->branchcand, externcands, externcandssol, externcandsscore, nexterncands, 529 nprioexterncands, nprioexternbins, nprioexternints, nprioexternimpls) ); 530 531 return SCIP_OKAY; 532 } 533 534 /** gets number of external branching candidates 535 * 536 * @return the number of external branching candidates. 537 * 538 * @pre This method can be called if @p scip is in one of the following stages: 539 * - \ref SCIP_STAGE_SOLVING 540 * 541 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 542 */ 543 int SCIPgetNExternBranchCands( 544 SCIP* scip /**< SCIP data structure */ 545 ) 546 { 547 assert(scip != NULL); 548 549 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 550 551 return SCIPbranchcandGetNExternCands(scip->branchcand); 552 } 553 554 /** gets number of external branching candidates with maximal branch priority 555 * 556 * @return the number of external branching candidates with maximal branch priority. 557 * 558 * @pre This method can be called if @p scip is in one of the following stages: 559 * - \ref SCIP_STAGE_SOLVING 560 * 561 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 562 */ 563 int SCIPgetNPrioExternBranchCands( 564 SCIP* scip /**< SCIP data structure */ 565 ) 566 { 567 assert(scip != NULL); 568 569 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 570 571 return SCIPbranchcandGetNPrioExternCands(scip->branchcand); 572 } 573 574 /** gets number of binary external branching candidates with maximal branch priority 575 * 576 * @return the number of binary external branching candidates with maximal branch priority. 577 * 578 * @pre This method can be called if @p scip is in one of the following stages: 579 * - \ref SCIP_STAGE_SOLVING 580 * 581 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 582 */ 583 int SCIPgetNPrioExternBranchBins( 584 SCIP* scip /**< SCIP data structure */ 585 ) 586 { 587 assert(scip != NULL); 588 589 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 590 591 return SCIPbranchcandGetNPrioExternBins(scip->branchcand); 592 } 593 594 /** gets number of integer external branching candidates with maximal branch priority 595 * 596 * @return the number of integer external branching candidates with maximal branch priority. 597 * 598 * @pre This method can be called if @p scip is in one of the following stages: 599 * - \ref SCIP_STAGE_SOLVING 600 * 601 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 602 */ 603 int SCIPgetNPrioExternBranchInts( 604 SCIP* scip /**< SCIP data structure */ 605 ) 606 { 607 assert(scip != NULL); 608 609 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 610 611 return SCIPbranchcandGetNPrioExternInts(scip->branchcand); 612 } 613 614 /** gets number of implicit integer external branching candidates with maximal branch priority 615 * 616 * @return the number of implicit integer external branching candidates with maximal branch priority. 617 * 618 * @pre This method can be called if @p scip is in one of the following stages: 619 * - \ref SCIP_STAGE_SOLVING 620 * 621 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 622 */ 623 int SCIPgetNPrioExternBranchImpls( 624 SCIP* scip /**< SCIP data structure */ 625 ) 626 { 627 assert(scip != NULL); 628 629 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 630 631 return SCIPbranchcandGetNPrioExternImpls(scip->branchcand); 632 } 633 634 /** gets number of continuous external branching candidates with maximal branch priority 635 * 636 * @return the number of continuous external branching candidates with maximal branch priority. 637 * 638 * @pre This method can be called if @p scip is in one of the following stages: 639 * - \ref SCIP_STAGE_SOLVING 640 * 641 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 642 */ 643 int SCIPgetNPrioExternBranchConts( 644 SCIP* scip /**< SCIP data structure */ 645 ) 646 { 647 assert(scip != NULL); 648 649 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchConts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 650 651 return SCIPbranchcandGetNPrioExternConts(scip->branchcand); 652 } 653 654 /** insert variable, its score and its solution value into the external branching candidate storage 655 * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon 656 * 657 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 658 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 659 * 660 * @pre This method can be called if @p scip is in one of the following stages: 661 * - \ref SCIP_STAGE_SOLVING 662 * 663 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 664 */ 665 SCIP_RETCODE SCIPaddExternBranchCand( 666 SCIP* scip, /**< SCIP data structure */ 667 SCIP_VAR* var, /**< variable to insert */ 668 SCIP_Real score, /**< score of external candidate, e.g. infeasibility */ 669 SCIP_Real solval /**< value of the variable in the current solution */ 670 ) 671 { 672 assert(scip != NULL); 673 assert(var->scip == scip); 674 675 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 676 677 SCIP_CALL( SCIPbranchcandAddExternCand(scip->branchcand, scip->set, var, score, solval) ); 678 679 return SCIP_OKAY; 680 } 681 682 /** removes all external candidates from the storage for external branching 683 * 684 * @pre This method can be called if @p scip is in one of the following stages: 685 * - \ref SCIP_STAGE_SOLVING 686 * 687 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 688 */ 689 void SCIPclearExternBranchCands( 690 SCIP* scip /**< SCIP data structure */ 691 ) 692 { 693 assert(scip != NULL); 694 695 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 696 697 SCIPbranchcandClearExternCands(scip->branchcand); 698 } 699 700 /** checks whether the given variable is contained in the candidate storage for external branching 701 * 702 * @return whether the given variable is contained in the candidate storage for external branching. 703 * 704 * @pre This method can be called if @p scip is in one of the following stages: 705 * - \ref SCIP_STAGE_SOLVING 706 * 707 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 708 */ 709 SCIP_Bool SCIPcontainsExternBranchCand( 710 SCIP* scip, /**< SCIP data structure */ 711 SCIP_VAR* var /**< variable to look for */ 712 ) 713 { 714 assert(scip != NULL); 715 assert(var->scip == scip); 716 717 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcontainsExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 718 719 return SCIPbranchcandContainsExternCand(scip->branchcand, var); 720 } 721 722 /** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates 723 * 724 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 725 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 726 * 727 * @pre This method can be called if @p scip is in one of the following stages: 728 * - \ref SCIP_STAGE_PRESOLVING 729 * - \ref SCIP_STAGE_SOLVING 730 * 731 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 732 */ 733 SCIP_RETCODE SCIPgetPseudoBranchCands( 734 SCIP* scip, /**< SCIP data structure */ 735 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */ 736 int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */ 737 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */ 738 ) 739 { 740 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 741 742 SCIP_CALL( SCIPbranchcandGetPseudoCands(scip->branchcand, scip->set, scip->transprob, 743 pseudocands, npseudocands, npriopseudocands) ); 744 745 return SCIP_OKAY; 746 } 747 748 /** gets number of branching candidates for pseudo solution branching (non-fixed variables) 749 * 750 * @return the number branching candidates for pseudo solution branching (non-fixed variables). 751 * 752 * @pre This method can be called if @p scip is in one of the following stages: 753 * - \ref SCIP_STAGE_PRESOLVING 754 * - \ref SCIP_STAGE_SOLVING 755 * 756 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 757 */ 758 int SCIPgetNPseudoBranchCands( 759 SCIP* scip /**< SCIP data structure */ 760 ) 761 { 762 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 763 764 return SCIPbranchcandGetNPseudoCands(scip->branchcand); 765 } 766 767 /** gets number of branching candidates with maximal branch priority for pseudo solution branching 768 * 769 * @return the number of branching candidates with maximal branch priority for pseudo solution branching. 770 * 771 * @pre This method can be called if @p scip is in one of the following stages: 772 * - \ref SCIP_STAGE_PRESOLVING 773 * - \ref SCIP_STAGE_SOLVING 774 * 775 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 776 */ 777 int SCIPgetNPrioPseudoBranchCands( 778 SCIP* scip /**< SCIP data structure */ 779 ) 780 { 781 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 782 783 return SCIPbranchcandGetNPrioPseudoCands(scip->branchcand); 784 } 785 786 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching 787 * 788 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching. 789 * 790 * @pre This method can be called if @p scip is in one of the following stages: 791 * - \ref SCIP_STAGE_SOLVING 792 * 793 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 794 */ 795 int SCIPgetNPrioPseudoBranchBins( 796 SCIP* scip /**< SCIP data structure */ 797 ) 798 { 799 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 800 801 return SCIPbranchcandGetNPrioPseudoBins(scip->branchcand); 802 } 803 804 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching 805 * 806 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching. 807 * 808 * @pre This method can be called if @p scip is in one of the following stages: 809 * - \ref SCIP_STAGE_SOLVING 810 * 811 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 812 */ 813 int SCIPgetNPrioPseudoBranchInts( 814 SCIP* scip /**< SCIP data structure */ 815 ) 816 { 817 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 818 819 return SCIPbranchcandGetNPrioPseudoInts(scip->branchcand); 820 } 821 822 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching 823 * 824 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching. 825 * 826 * @pre This method can be called if @p scip is in one of the following stages: 827 * - \ref SCIP_STAGE_SOLVING 828 * 829 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 830 */ 831 int SCIPgetNPrioPseudoBranchImpls( 832 SCIP* scip /**< SCIP data structure */ 833 ) 834 { 835 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 836 837 return SCIPbranchcandGetNPrioPseudoImpls(scip->branchcand); 838 } 839 840 /** calculates the branching score out of the gain predictions for a binary branching 841 * 842 * @return the branching score out of the gain predictions for a binary branching. 843 * 844 * @pre This method can be called if @p scip is in one of the following stages: 845 * - \ref SCIP_STAGE_SOLVING 846 * 847 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 848 */ 849 SCIP_Real SCIPgetBranchScore( 850 SCIP* scip, /**< SCIP data structure */ 851 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 852 SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */ 853 SCIP_Real upgain /**< prediction of objective gain for rounding upwards */ 854 ) 855 { 856 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 857 858 assert( var == NULL || var->scip == scip ); 859 860 return SCIPbranchGetScore(scip->set, var, downgain, upgain); 861 } 862 863 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children 864 * 865 * @return the branching score out of the gain predictions for a branching with arbitrary many children. 866 * 867 * @pre This method can be called if @p scip is in one of the following stages: 868 * - \ref SCIP_STAGE_SOLVING 869 * 870 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 871 */ 872 SCIP_Real SCIPgetBranchScoreMultiple( 873 SCIP* scip, /**< SCIP data structure */ 874 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 875 int nchildren, /**< number of children that the branching will create */ 876 SCIP_Real* gains /**< prediction of objective gain for each child */ 877 ) 878 { 879 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScoreMultiple", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 880 881 assert( var->scip == scip ); 882 883 return SCIPbranchGetScoreMultiple(scip->set, var, nchildren, gains); 884 } 885 886 /** computes a branching point for a continuous or discrete variable 887 * 888 * @see SCIPbranchGetBranchingPoint 889 * 890 * @return the branching point for a continuous or discrete variable. 891 * 892 * @pre This method can be called if @p scip is in one of the following stages: 893 * - \ref SCIP_STAGE_SOLVING 894 * 895 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 896 */ 897 SCIP_Real SCIPgetBranchingPoint( 898 SCIP* scip, /**< SCIP data structure */ 899 SCIP_VAR* var, /**< variable, of which the branching point should be computed */ 900 SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */ 901 ) 902 { 903 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchingPoint", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 904 905 assert( var->scip == scip ); 906 907 return SCIPbranchGetBranchingPoint(scip->set, scip->tree, var, suggestion); 908 } 909 910 /** calculates the node selection priority for moving the given variable's LP value to the given target value; 911 * this node selection priority can be given to the SCIPcreateChild() call 912 * 913 * @return the node selection priority for moving the given variable's LP value to the given target value. 914 * 915 * @pre This method can be called if @p scip is in one of the following stages: 916 * - \ref SCIP_STAGE_SOLVING 917 * 918 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 919 */ 920 SCIP_Real SCIPcalcNodeselPriority( 921 SCIP* scip, /**< SCIP data structure */ 922 SCIP_VAR* var, /**< variable on which the branching is applied */ 923 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed; 924 * fixed should only be used, when both bounds changed 925 */ 926 SCIP_Real targetvalue /**< new value of the variable in the child node */ 927 ) 928 { 929 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcNodeselPriority", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 930 931 assert( var->scip == scip ); 932 933 return SCIPtreeCalcNodeselPriority(scip->tree, scip->set, scip->stat, var, branchdir, targetvalue); 934 } 935 936 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given 937 * branching; this estimate can be given to the SCIPcreateChild() call 938 * 939 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given 940 * branching. 941 * 942 * @pre This method can be called if @p scip is in one of the following stages: 943 * - \ref SCIP_STAGE_SOLVING 944 * 945 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 946 */ 947 SCIP_Real SCIPcalcChildEstimate( 948 SCIP* scip, /**< SCIP data structure */ 949 SCIP_VAR* var, /**< variable on which the branching is applied */ 950 SCIP_Real targetvalue /**< new value of the variable in the child node */ 951 ) 952 { 953 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcChildEstimate", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 954 955 assert( var->scip == scip ); 956 957 return SCIPtreeCalcChildEstimate(scip->tree, scip->set, scip->stat, var, targetvalue); 958 } 959 960 /** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree 961 * after applying the given branching 962 * 963 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after 964 * applying the given branching. 965 * 966 * @pre This method can be called if @p scip is in one of the following stages: 967 * - \ref SCIP_STAGE_SOLVING 968 * 969 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 970 */ 971 SCIP_Real SCIPcalcChildEstimateIncrease( 972 SCIP* scip, /**< SCIP data structure */ 973 SCIP_VAR* var, /**< variable on which the branching is applied */ 974 SCIP_Real varsol, /**< solution value of variable */ 975 SCIP_Real targetvalue /**< new value of the variable in the child node */ 976 ) 977 { 978 SCIP_Real estimateinc; 979 980 assert(scip != NULL); 981 assert(var != NULL); 982 983 /* compute increase above parent node's (i.e., focus node's) estimate value */ 984 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 985 estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol); 986 else 987 { 988 SCIP_Real pscdown; 989 SCIP_Real pscup; 990 991 /* calculate estimate based on pseudo costs: 992 * estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j}) 993 * = parentestimate - min{f_b * pscdown_b, (1-f_b) * pscup_b} + (targetvalue-oldvalue)*{pscdown_b or pscup_b} 994 */ 995 pscdown = SCIPvarGetPseudocost(var, scip->stat, SCIPsetFeasFloor(scip->set, varsol) - varsol); 996 pscup = SCIPvarGetPseudocost(var, scip->stat, SCIPsetFeasCeil(scip->set, varsol) - varsol); 997 estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol) - MIN(pscdown, pscup); 998 } 999 1000 /* due to rounding errors estimateinc might be slightly negative */ 1001 if( estimateinc > 0.0 ) 1002 estimateinc = 0.0; 1003 1004 return estimateinc; 1005 } 1006 1007 /** creates a child node of the focus node 1008 * 1009 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1010 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1011 * 1012 * @pre This method can be called if @p scip is in one of the following stages: 1013 * - \ref SCIP_STAGE_SOLVING 1014 * 1015 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1016 */ 1017 SCIP_RETCODE SCIPcreateChild( 1018 SCIP* scip, /**< SCIP data structure */ 1019 SCIP_NODE** node, /**< pointer to node data structure */ 1020 SCIP_Real nodeselprio, /**< node selection priority of new node */ 1021 SCIP_Real estimate /**< estimate for(transformed) objective value of best feasible solution in subtree */ 1022 ) 1023 { 1024 assert(node != NULL); 1025 1026 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1027 1028 SCIP_CALL( SCIPnodeCreateChild(node, scip->mem->probmem, scip->set, scip->stat, scip->tree, nodeselprio, estimate) ); 1029 1030 return SCIP_OKAY; 1031 } 1032 1033 /** branches on a non-continuous variable v using the current LP or pseudo solution; 1034 * if solution value x' is fractional, two child nodes will be created 1035 * (x <= floor(x'), x >= ceil(x')), 1036 * if solution value is integral, the x' is equal to lower or upper bound of the branching 1037 * variable and the bounds of v are finite, then two child nodes will be created 1038 * (x <= x'', x >= x''+1 with x'' = floor((lb + ub)/2)), 1039 * otherwise (up to) three child nodes will be created 1040 * (x <= x'-1, x == x', x >= x'+1) 1041 * 1042 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1043 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1044 * 1045 * @pre This method can be called if @p scip is in one of the following stages: 1046 * - \ref SCIP_STAGE_SOLVING 1047 * 1048 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1049 */ 1050 SCIP_RETCODE SCIPbranchVar( 1051 SCIP* scip, /**< SCIP data structure */ 1052 SCIP_VAR* var, /**< variable to branch on */ 1053 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */ 1054 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */ 1055 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */ 1056 ) 1057 { 1058 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVar", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1059 1060 assert( var->scip == scip ); 1061 1062 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS ) 1063 { 1064 SCIPerrorMessage("cannot branch on continuous variable <%s>\n", SCIPvarGetName(var)); 1065 return SCIP_INVALIDDATA; 1066 } 1067 1068 if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 1069 { 1070 SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n", 1071 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 1072 return SCIP_INVALIDDATA; 1073 } 1074 1075 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob, 1076 scip->lp, scip->branchcand, scip->eventqueue, var, SCIP_INVALID, downchild, eqchild, upchild) ); 1077 1078 return SCIP_OKAY; 1079 } 1080 1081 /** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created 1082 * 1083 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1084 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1085 * 1086 * @pre This method can be called if @p scip is in one of the following stages: 1087 * - \ref SCIP_STAGE_SOLVING 1088 * 1089 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1090 */ 1091 SCIP_RETCODE SCIPbranchVarHole( 1092 SCIP* scip, /**< SCIP data structure */ 1093 SCIP_VAR* var, /**< variable to branch on */ 1094 SCIP_Real left, /**< left side of the domain hole */ 1095 SCIP_Real right, /**< right side of the domain hole */ 1096 SCIP_NODE** downchild, /**< pointer to return the left child (x <= left), or NULL */ 1097 SCIP_NODE** upchild /**< pointer to return the right child (x >= right), or NULL */ 1098 ) 1099 { 1100 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarHole", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1101 1102 assert( var->scip == scip ); 1103 1104 SCIP_CALL( SCIPtreeBranchVarHole(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 1105 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, left, right, downchild, upchild) ); 1106 1107 return SCIP_OKAY; 1108 } 1109 1110 /** branches on a variable x using a given value x'; 1111 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds; 1112 * two child nodes (x <= x', x >= x') are created; 1113 * for integer variables, if solution value x' is fractional, two child nodes are created 1114 * (x <= floor(x'), x >= ceil(x')), 1115 * if x' is integral, three child nodes are created 1116 * (x <= x'-1, x == x', x >= x'+1) 1117 * 1118 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1119 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1120 * 1121 * @pre This method can be called if @p scip is in one of the following stages: 1122 * - \ref SCIP_STAGE_SOLVING 1123 * 1124 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1125 */ 1126 SCIP_RETCODE SCIPbranchVarVal( 1127 SCIP* scip, /**< SCIP data structure */ 1128 SCIP_VAR* var, /**< variable to branch on */ 1129 SCIP_Real val, /**< value to branch on */ 1130 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */ 1131 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */ 1132 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */ 1133 ) 1134 { 1135 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarVal", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1136 1137 assert( var->scip == scip ); 1138 1139 /* A continuous variable will be fixed if SCIPisRelEQ(lb,ub) is true. Otherwise, the given branching value should be 1140 * such that its value is not equal to one of the bounds. We assert this by requiring that it is at least eps/2 away 1141 * from each bound. The 2.1 is there, because ub-lb may be in (eps, 2*eps], in which case there is no way to choose a 1142 * branching value that is at least eps away from both bounds. However, if the variable bounds are below/above 1143 * -/+infinity * 2.1, then SCIPisLT will give an assert, so we omit the check in this case. 1144 */ 1145 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || 1146 SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) || 1147 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) || 1148 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) ); 1149 1150 if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 1151 { 1152 SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n", 1153 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 1154 return SCIP_INVALIDDATA; 1155 } 1156 1157 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob, 1158 scip->lp, scip->branchcand, scip->eventqueue, var, val, downchild, eqchild, upchild) ); 1159 1160 return SCIP_OKAY; 1161 } 1162 1163 /** n-ary branching on a variable x using a given value 1164 * 1165 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value. 1166 * The branching value is selected as in SCIPbranchVarVal(). 1167 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes. 1168 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created. 1169 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created. 1170 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance 1171 * from the first nodes. 1172 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value. 1173 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes. 1174 * 1175 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value 1176 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3 1177 * results in a ternary branching where the branching variable is mostly fixed in the middle child. 1178 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width 1179 * (except for one child if the branching value is not in the middle). 1180 * 1181 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1182 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1183 * 1184 * @pre This method can be called if @p scip is in one of the following stages: 1185 * - \ref SCIP_STAGE_SOLVING 1186 * 1187 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1188 */ 1189 SCIP_RETCODE SCIPbranchVarValNary( 1190 SCIP* scip, /**< SCIP data structure */ 1191 SCIP_VAR* var, /**< variable to branch on */ 1192 SCIP_Real val, /**< value to branch on */ 1193 int n, /**< attempted number of children to be created, must be >= 2 */ 1194 SCIP_Real minwidth, /**< minimal domain width in children */ 1195 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */ 1196 int* nchildren /**< pointer to store number of created children, or NULL */ 1197 ) 1198 { 1199 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarValNary", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1200 1201 assert( var->scip == scip ); 1202 1203 /* see comment in SCIPbranchVarVal */ 1204 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS || 1205 SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) || 1206 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) || 1207 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) ); 1208 1209 if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ) 1210 { 1211 SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n", 1212 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)); 1213 return SCIP_INVALIDDATA; 1214 } 1215 1216 SCIP_CALL( SCIPtreeBranchVarNary(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, 1217 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, val, n, minwidth, widthfactor, nchildren) ); 1218 1219 return SCIP_OKAY; 1220 } 1221 1222 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN; 1223 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional 1224 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority 1225 * 1226 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1227 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1228 * 1229 * @pre This method can be called if @p scip is in one of the following stages: 1230 * - \ref SCIP_STAGE_SOLVING 1231 * 1232 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1233 */ 1234 SCIP_RETCODE SCIPbranchLP( 1235 SCIP* scip, /**< SCIP data structure */ 1236 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 1237 ) 1238 { 1239 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1240 1241 SCIP_CALL( SCIPbranchExecLP(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob, 1242 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound, 1243 TRUE, result) ); 1244 1245 return SCIP_OKAY; 1246 } 1247 1248 /** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN 1249 * 1250 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1251 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1252 * 1253 * @pre This method can be called if @p scip is in one of the following stages: 1254 * - \ref SCIP_STAGE_SOLVING 1255 * 1256 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1257 */ 1258 SCIP_RETCODE SCIPbranchExtern( 1259 SCIP* scip, /**< SCIP data structure */ 1260 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 1261 ) 1262 { 1263 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchExtern", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1264 1265 SCIP_CALL( SCIPbranchExecExtern(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob, 1266 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound, 1267 TRUE, result) ); 1268 1269 return SCIP_OKAY; 1270 } 1271 1272 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN 1273 * 1274 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 1275 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 1276 * 1277 * @pre This method can be called if @p scip is in one of the following stages: 1278 * - \ref SCIP_STAGE_SOLVING 1279 * 1280 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 1281 */ 1282 SCIP_RETCODE SCIPbranchPseudo( 1283 SCIP* scip, /**< SCIP data structure */ 1284 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 1285 ) 1286 { 1287 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchPseudo", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) ); 1288 1289 SCIP_CALL( SCIPbranchExecPseudo(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob, 1290 scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound, TRUE, result) ); 1291 1292 return SCIP_OKAY; 1293 } 1294