1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */ 7 /* fuer Informationstechnik Berlin */ 8 /* */ 9 /* SCIP is distributed under the terms of the ZIB Academic License. */ 10 /* */ 11 /* You should have received a copy of the ZIB Academic License */ 12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file scip_branch.h 17 * @ingroup PUBLICCOREAPI 18 * @brief public methods for branching rule plugins and branching 19 * @author Tobias Achterberg 20 * @author Timo Berthold 21 * @author Thorsten Koch 22 * @author Alexander Martin 23 * @author Marc Pfetsch 24 * @author Kati Wolter 25 * @author Gregor Hendel 26 * @author Leona Gottwald 27 */ 28 29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 30 31 #ifndef __SCIP_SCIP_BRANCH_H__ 32 #define __SCIP_SCIP_BRANCH_H__ 33 34 35 #include "scip/def.h" 36 #include "scip/type_branch.h" 37 #include "scip/type_history.h" 38 #include "scip/type_result.h" 39 #include "scip/type_retcode.h" 40 #include "scip/type_scip.h" 41 #include "scip/type_tree.h" 42 #include "scip/type_var.h" 43 44 #ifdef __cplusplus 45 extern "C" { 46 #endif 47 48 /**@addtogroup PublicBranchRuleMethods 49 * 50 * @{ 51 */ 52 53 /** creates a branching rule and includes it in SCIP 54 * 55 * @note method has all branching rule callbacks as arguments and is thus changed every time a new 56 * callback is added in future releases; consider using SCIPincludeBranchruleBasic() and setter functions 57 * if you seek for a method which is less likely to change in future releases 58 */ 59 SCIP_EXPORT 60 SCIP_RETCODE SCIPincludeBranchrule( 61 SCIP* scip, /**< SCIP data structure */ 62 const char* name, /**< name of branching rule */ 63 const char* desc, /**< description of branching rule */ 64 int priority, /**< priority of the branching rule */ 65 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */ 66 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound 67 * compared to best node's dual bound for applying branching rule 68 * (0.0: only on current best node, 1.0: on all nodes) */ 69 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */ 70 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */ 71 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */ 72 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */ 73 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */ 74 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */ 75 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */ 76 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */ 77 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */ 78 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 79 ); 80 81 /** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL. 82 * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(), 83 * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(), 84 * SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecExt(), and SCIPsetBranchruleExecPs(). 85 * 86 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead 87 */ 88 SCIP_EXPORT 89 SCIP_RETCODE SCIPincludeBranchruleBasic( 90 SCIP* scip, /**< SCIP data structure */ 91 SCIP_BRANCHRULE** branchruleptr, /**< pointer to branching rule, or NULL */ 92 const char* name, /**< name of branching rule */ 93 const char* desc, /**< description of branching rule */ 94 int priority, /**< priority of the branching rule */ 95 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */ 96 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound 97 * compared to best node's dual bound for applying branching rule 98 * (0.0: only on current best node, 1.0: on all nodes) */ 99 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */ 100 ); 101 102 /** sets copy method of branching rule */ 103 SCIP_EXPORT 104 SCIP_RETCODE SCIPsetBranchruleCopy( 105 SCIP* scip, /**< SCIP data structure */ 106 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 107 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */ 108 ); 109 110 /** sets destructor method of branching rule */ 111 SCIP_EXPORT 112 SCIP_RETCODE SCIPsetBranchruleFree( 113 SCIP* scip, /**< SCIP data structure */ 114 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 115 SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */ 116 ); 117 118 /** sets initialization method of branching rule */ 119 SCIP_EXPORT 120 SCIP_RETCODE SCIPsetBranchruleInit( 121 SCIP* scip, /**< SCIP data structure */ 122 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 123 SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */ 124 ); 125 126 /** sets deinitialization method of branching rule */ 127 SCIP_EXPORT 128 SCIP_RETCODE SCIPsetBranchruleExit( 129 SCIP* scip, /**< SCIP data structure */ 130 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 131 SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */ 132 ); 133 134 /** sets solving process initialization method of branching rule */ 135 SCIP_EXPORT 136 SCIP_RETCODE SCIPsetBranchruleInitsol( 137 SCIP* scip, /**< SCIP data structure */ 138 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 139 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */ 140 ); 141 142 /** sets solving process deinitialization method of branching rule */ 143 SCIP_EXPORT 144 SCIP_RETCODE SCIPsetBranchruleExitsol( 145 SCIP* scip, /**< SCIP data structure */ 146 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 147 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */ 148 ); 149 150 /** sets branching execution method for fractional LP solutions */ 151 SCIP_EXPORT 152 SCIP_RETCODE SCIPsetBranchruleExecLp( 153 SCIP* scip, /**< SCIP data structure */ 154 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 155 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */ 156 ); 157 158 /** sets branching execution method for external candidates */ 159 SCIP_EXPORT 160 SCIP_RETCODE SCIPsetBranchruleExecExt( 161 SCIP* scip, /**< SCIP data structure */ 162 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 163 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */ 164 ); 165 166 /** sets branching execution method for not completely fixed pseudo solutions */ 167 SCIP_EXPORT 168 SCIP_RETCODE SCIPsetBranchruleExecPs( 169 SCIP* scip, /**< SCIP data structure */ 170 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 171 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */ 172 ); 173 174 /** returns the branching rule of the given name, or NULL if not existing */ 175 SCIP_EXPORT 176 SCIP_BRANCHRULE* SCIPfindBranchrule( 177 SCIP* scip, /**< SCIP data structure */ 178 const char* name /**< name of branching rule */ 179 ); 180 181 /** returns the array of currently available branching rules */ 182 SCIP_EXPORT 183 SCIP_BRANCHRULE** SCIPgetBranchrules( 184 SCIP* scip /**< SCIP data structure */ 185 ); 186 187 /** returns the number of currently available branching rules */ 188 SCIP_EXPORT 189 int SCIPgetNBranchrules( 190 SCIP* scip /**< SCIP data structure */ 191 ); 192 193 /** sets the priority of a branching rule */ 194 SCIP_EXPORT 195 SCIP_RETCODE SCIPsetBranchrulePriority( 196 SCIP* scip, /**< SCIP data structure */ 197 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 198 int priority /**< new priority of the branching rule */ 199 ); 200 201 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */ 202 SCIP_EXPORT 203 SCIP_RETCODE SCIPsetBranchruleMaxdepth( 204 SCIP* scip, /**< SCIP data structure */ 205 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 206 int maxdepth /**< new maxdepth of the branching rule */ 207 ); 208 209 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */ 210 SCIP_EXPORT 211 SCIP_RETCODE SCIPsetBranchruleMaxbounddist( 212 SCIP* scip, /**< SCIP data structure */ 213 SCIP_BRANCHRULE* branchrule, /**< branching rule */ 214 SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */ 215 ); 216 217 /** @} */ 218 219 /**@addtogroup PublicBranchingMethods 220 * 221 * @{ 222 */ 223 224 /** gets branching candidates for LP solution branching (fractional variables) along with solution values, 225 * fractionalities, and number of branching candidates; The number of branching candidates does NOT 226 * account for fractional implicit integer variables which should not be used for branching decisions. 227 * 228 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1 229 * 230 * branching rules should always select the branching candidate among the first npriolpcands of the candidate 231 * list 232 * 233 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 234 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 235 * 236 * @pre This method can be called if @p scip is in one of the following stages: 237 * - \ref SCIP_STAGE_SOLVING 238 * 239 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 240 */ 241 SCIP_EXPORT 242 SCIP_RETCODE SCIPgetLPBranchCands( 243 SCIP* scip, /**< SCIP data structure */ 244 SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */ 245 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */ 246 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */ 247 int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */ 248 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */ 249 int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */ 250 ); 251 252 /** gets number of branching candidates for LP solution branching (number of fractional variables) 253 * 254 * @return the number of branching candidates for LP solution branching (number of fractional variables). 255 * 256 * @pre This method can be called if @p scip is in one of the following stages: 257 * - \ref SCIP_STAGE_SOLVING 258 * 259 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 260 */ 261 SCIP_EXPORT 262 int SCIPgetNLPBranchCands( 263 SCIP* scip /**< SCIP data structure */ 264 ); 265 266 /** gets number of branching candidates with maximal priority for LP solution branching 267 * 268 * @return the number of branching candidates with maximal priority for LP solution branching. 269 * 270 * @pre This method can be called if @p scip is in one of the following stages: 271 * - \ref SCIP_STAGE_SOLVING 272 * 273 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 274 */ 275 SCIP_EXPORT 276 int SCIPgetNPrioLPBranchCands( 277 SCIP* scip /**< SCIP data structure */ 278 ); 279 280 /** gets external branching candidates along with solution values, scores, and number of branching candidates; 281 * these branching candidates can be used by relaxations or nonlinear constraint handlers; 282 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate 283 * list 284 * 285 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 286 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 287 * 288 * @pre This method can be called if @p scip is in one of the following stages: 289 * - \ref SCIP_STAGE_SOLVING 290 * 291 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 292 * 293 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and 294 * continuous last. 295 */ 296 SCIP_EXPORT 297 SCIP_RETCODE SCIPgetExternBranchCands( 298 SCIP* scip, /**< SCIP data structure */ 299 SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */ 300 SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */ 301 SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */ 302 int* nexterncands, /**< pointer to store the number of extern branching candidates, or NULL */ 303 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */ 304 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */ 305 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */ 306 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority, 307 * or NULL */ 308 ); 309 310 /** gets number of external branching candidates 311 * 312 * @return the number of external branching candidates. 313 * 314 * @pre This method can be called if @p scip is in one of the following stages: 315 * - \ref SCIP_STAGE_SOLVING 316 * 317 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 318 */ 319 SCIP_EXPORT 320 int SCIPgetNExternBranchCands( 321 SCIP* scip /**< SCIP data structure */ 322 ); 323 324 /** gets number of external branching candidates with maximal branch priority 325 * 326 * @return the number of external branching candidates with maximal branch priority. 327 * 328 * @pre This method can be called if @p scip is in one of the following stages: 329 * - \ref SCIP_STAGE_SOLVING 330 * 331 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 332 */ 333 SCIP_EXPORT 334 int SCIPgetNPrioExternBranchCands( 335 SCIP* scip /**< SCIP data structure */ 336 ); 337 338 /** gets number of binary external branching candidates with maximal branch priority 339 * 340 * @return the number of binary external branching candidates with maximal branch priority. 341 * 342 * @pre This method can be called if @p scip is in one of the following stages: 343 * - \ref SCIP_STAGE_SOLVING 344 * 345 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 346 */ 347 SCIP_EXPORT 348 int SCIPgetNPrioExternBranchBins( 349 SCIP* scip /**< SCIP data structure */ 350 ); 351 352 /** gets number of integer external branching candidates with maximal branch priority 353 * 354 * @return the number of integer external branching candidates with maximal branch priority. 355 * 356 * @pre This method can be called if @p scip is in one of the following stages: 357 * - \ref SCIP_STAGE_SOLVING 358 * 359 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 360 */ 361 SCIP_EXPORT 362 int SCIPgetNPrioExternBranchInts( 363 SCIP* scip /**< SCIP data structure */ 364 ); 365 366 /** gets number of implicit integer external branching candidates with maximal branch priority 367 * 368 * @return the number of implicit integer external branching candidates with maximal branch priority. 369 * 370 * @pre This method can be called if @p scip is in one of the following stages: 371 * - \ref SCIP_STAGE_SOLVING 372 * 373 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 374 */ 375 SCIP_EXPORT 376 int SCIPgetNPrioExternBranchImpls( 377 SCIP* scip /**< SCIP data structure */ 378 ); 379 380 /** gets number of continuous external branching candidates with maximal branch priority 381 * 382 * @return the number of continuous external branching candidates with maximal branch priority. 383 * 384 * @pre This method can be called if @p scip is in one of the following stages: 385 * - \ref SCIP_STAGE_SOLVING 386 * 387 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 388 */ 389 SCIP_EXPORT 390 int SCIPgetNPrioExternBranchConts( 391 SCIP* scip /**< SCIP data structure */ 392 ); 393 394 /** insert variable, its score and its solution value into the external branching candidate storage 395 * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon 396 * 397 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 398 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 399 * 400 * @pre This method can be called if @p scip is in one of the following stages: 401 * - \ref SCIP_STAGE_SOLVING 402 * 403 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 404 */ 405 SCIP_EXPORT 406 SCIP_RETCODE SCIPaddExternBranchCand( 407 SCIP* scip, /**< SCIP data structure */ 408 SCIP_VAR* var, /**< variable to insert */ 409 SCIP_Real score, /**< score of external candidate, e.g. infeasibility */ 410 SCIP_Real solval /**< value of the variable in the current solution */ 411 ); 412 413 /** removes all external candidates from the storage for external branching 414 * 415 * @pre This method can be called if @p scip is in one of the following stages: 416 * - \ref SCIP_STAGE_SOLVING 417 * 418 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 419 */ 420 SCIP_EXPORT 421 void SCIPclearExternBranchCands( 422 SCIP* scip /**< SCIP data structure */ 423 ); 424 425 /** checks whether the given variable is contained in the candidate storage for external branching 426 * 427 * @return whether the given variable is contained in the candidate storage for external branching. 428 * 429 * @pre This method can be called if @p scip is in one of the following stages: 430 * - \ref SCIP_STAGE_SOLVING 431 * 432 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 433 */ 434 SCIP_EXPORT 435 SCIP_Bool SCIPcontainsExternBranchCand( 436 SCIP* scip, /**< SCIP data structure */ 437 SCIP_VAR* var /**< variable to look for */ 438 ); 439 440 /** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates 441 * 442 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 443 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 444 * 445 * @pre This method can be called if @p scip is in one of the following stages: 446 * - \ref SCIP_STAGE_PRESOLVING 447 * - \ref SCIP_STAGE_SOLVING 448 * 449 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 450 */ 451 SCIP_EXPORT 452 SCIP_RETCODE SCIPgetPseudoBranchCands( 453 SCIP* scip, /**< SCIP data structure */ 454 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */ 455 int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */ 456 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */ 457 ); 458 459 /** gets number of branching candidates for pseudo solution branching (non-fixed variables) 460 * 461 * @return the number branching candidates for pseudo solution branching (non-fixed variables). 462 * 463 * @pre This method can be called if @p scip is in one of the following stages: 464 * - \ref SCIP_STAGE_PRESOLVING 465 * - \ref SCIP_STAGE_SOLVING 466 * 467 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 468 */ 469 SCIP_EXPORT 470 int SCIPgetNPseudoBranchCands( 471 SCIP* scip /**< SCIP data structure */ 472 ); 473 474 /** gets number of branching candidates with maximal branch priority for pseudo solution branching 475 * 476 * @return the number of branching candidates with maximal branch priority for pseudo solution branching. 477 * 478 * @pre This method can be called if @p scip is in one of the following stages: 479 * - \ref SCIP_STAGE_PRESOLVING 480 * - \ref SCIP_STAGE_SOLVING 481 * 482 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 483 */ 484 SCIP_EXPORT 485 int SCIPgetNPrioPseudoBranchCands( 486 SCIP* scip /**< SCIP data structure */ 487 ); 488 489 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching 490 * 491 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching. 492 * 493 * @pre This method can be called if @p scip is in one of the following stages: 494 * - \ref SCIP_STAGE_SOLVING 495 * 496 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 497 */ 498 SCIP_EXPORT 499 int SCIPgetNPrioPseudoBranchBins( 500 SCIP* scip /**< SCIP data structure */ 501 ); 502 503 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching 504 * 505 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching. 506 * 507 * @pre This method can be called if @p scip is in one of the following stages: 508 * - \ref SCIP_STAGE_SOLVING 509 * 510 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 511 */ 512 SCIP_EXPORT 513 int SCIPgetNPrioPseudoBranchInts( 514 SCIP* scip /**< SCIP data structure */ 515 ); 516 517 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching 518 * 519 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching. 520 * 521 * @pre This method can be called if @p scip is in one of the following stages: 522 * - \ref SCIP_STAGE_SOLVING 523 * 524 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 525 */ 526 SCIP_EXPORT 527 int SCIPgetNPrioPseudoBranchImpls( 528 SCIP* scip /**< SCIP data structure */ 529 ); 530 531 /** calculates the branching score out of the gain predictions for a binary branching 532 * 533 * @return the branching score out of the gain predictions for a binary branching. 534 * 535 * @pre This method can be called if @p scip is in one of the following stages: 536 * - \ref SCIP_STAGE_SOLVING 537 * 538 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 539 */ 540 SCIP_EXPORT 541 SCIP_Real SCIPgetBranchScore( 542 SCIP* scip, /**< SCIP data structure */ 543 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 544 SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */ 545 SCIP_Real upgain /**< prediction of objective gain for rounding upwards */ 546 ); 547 548 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children 549 * 550 * @return the branching score out of the gain predictions for a branching with arbitrary many children. 551 * 552 * @pre This method can be called if @p scip is in one of the following stages: 553 * - \ref SCIP_STAGE_SOLVING 554 * 555 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 556 */ 557 SCIP_EXPORT 558 SCIP_Real SCIPgetBranchScoreMultiple( 559 SCIP* scip, /**< SCIP data structure */ 560 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */ 561 int nchildren, /**< number of children that the branching will create */ 562 SCIP_Real* gains /**< prediction of objective gain for each child */ 563 ); 564 565 /** computes a branching point for a continuous or discrete variable 566 * 567 * @see SCIPbranchGetBranchingPoint 568 * 569 * @return the branching point for a continuous or discrete variable. 570 * 571 * @pre This method can be called if @p scip is in one of the following stages: 572 * - \ref SCIP_STAGE_SOLVING 573 * 574 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 575 */ 576 SCIP_EXPORT 577 SCIP_Real SCIPgetBranchingPoint( 578 SCIP* scip, /**< SCIP data structure */ 579 SCIP_VAR* var, /**< variable, of which the branching point should be computed */ 580 SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */ 581 ); 582 583 /** calculates the node selection priority for moving the given variable's LP value to the given target value; 584 * this node selection priority can be given to the SCIPcreateChild() call 585 * 586 * @return the node selection priority for moving the given variable's LP value to the given target value. 587 * 588 * @pre This method can be called if @p scip is in one of the following stages: 589 * - \ref SCIP_STAGE_SOLVING 590 * 591 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 592 */ 593 SCIP_EXPORT 594 SCIP_Real SCIPcalcNodeselPriority( 595 SCIP* scip, /**< SCIP data structure */ 596 SCIP_VAR* var, /**< variable on which the branching is applied */ 597 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed; 598 * fixed should only be used, when both bounds changed 599 */ 600 SCIP_Real targetvalue /**< new value of the variable in the child node */ 601 ); 602 603 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given 604 * branching; this estimate can be given to the SCIPcreateChild() call 605 * 606 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given 607 * branching. 608 * 609 * @pre This method can be called if @p scip is in one of the following stages: 610 * - \ref SCIP_STAGE_SOLVING 611 * 612 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 613 */ 614 SCIP_EXPORT 615 SCIP_Real SCIPcalcChildEstimate( 616 SCIP* scip, /**< SCIP data structure */ 617 SCIP_VAR* var, /**< variable on which the branching is applied */ 618 SCIP_Real targetvalue /**< new value of the variable in the child node */ 619 ); 620 621 /** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree 622 * after applying the given branching 623 * 624 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after 625 * applying the given branching. 626 * 627 * @pre This method can be called if @p scip is in one of the following stages: 628 * - \ref SCIP_STAGE_SOLVING 629 * 630 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 631 */ 632 SCIP_EXPORT 633 SCIP_Real SCIPcalcChildEstimateIncrease( 634 SCIP* scip, /**< SCIP data structure */ 635 SCIP_VAR* var, /**< variable on which the branching is applied */ 636 SCIP_Real varsol, /**< solution value of variable */ 637 SCIP_Real targetvalue /**< new value of the variable in the child node */ 638 ); 639 640 /** creates a child node of the focus node 641 * 642 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 643 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 644 * 645 * @pre This method can be called if @p scip is in one of the following stages: 646 * - \ref SCIP_STAGE_SOLVING 647 * 648 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 649 */ 650 SCIP_EXPORT 651 SCIP_RETCODE SCIPcreateChild( 652 SCIP* scip, /**< SCIP data structure */ 653 SCIP_NODE** node, /**< pointer to node data structure */ 654 SCIP_Real nodeselprio, /**< node selection priority of new node */ 655 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */ 656 ); 657 658 /** branches on a non-continuous variable v using the current LP or pseudo solution; 659 * if solution value x' is fractional, two child nodes will be created 660 * (x <= floor(x'), x >= ceil(x')), 661 * if solution value is integral, the x' is equal to lower or upper bound of the branching 662 * variable and the bounds of v are finite, then two child nodes will be created 663 * (x <= x'', x >= x''+1 with x'' = floor((lb + ub)/2)), 664 * otherwise (up to) three child nodes will be created 665 * (x <= x'-1, x == x', x >= x'+1) 666 * 667 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 668 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 669 * 670 * @pre This method can be called if @p scip is in one of the following stages: 671 * - \ref SCIP_STAGE_SOLVING 672 * 673 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 674 */ 675 SCIP_EXPORT 676 SCIP_RETCODE SCIPbranchVar( 677 SCIP* scip, /**< SCIP data structure */ 678 SCIP_VAR* var, /**< variable to branch on */ 679 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */ 680 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */ 681 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */ 682 ); 683 684 /** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created 685 * 686 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 687 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 688 * 689 * @pre This method can be called if @p scip is in one of the following stages: 690 * - \ref SCIP_STAGE_SOLVING 691 * 692 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 693 */ 694 SCIP_EXPORT 695 SCIP_RETCODE SCIPbranchVarHole( 696 SCIP* scip, /**< SCIP data structure */ 697 SCIP_VAR* var, /**< variable to branch on */ 698 SCIP_Real left, /**< left side of the domain hole */ 699 SCIP_Real right, /**< right side of the domain hole */ 700 SCIP_NODE** downchild, /**< pointer to return the left child (x <= left), or NULL */ 701 SCIP_NODE** upchild /**< pointer to return the right child (x >= right), or NULL */ 702 ); 703 704 /** branches on a variable x using a given value x'; 705 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds; 706 * two child nodes (x <= x', x >= x') are created; 707 * for integer variables, if solution value x' is fractional, two child nodes are created 708 * (x <= floor(x'), x >= ceil(x')), 709 * if x' is integral, three child nodes are created 710 * (x <= x'-1, x == x', x >= x'+1) 711 * 712 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 713 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 714 * 715 * @pre This method can be called if @p scip is in one of the following stages: 716 * - \ref SCIP_STAGE_SOLVING 717 * 718 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 719 */ 720 SCIP_EXPORT 721 SCIP_RETCODE SCIPbranchVarVal( 722 SCIP* scip, /**< SCIP data structure */ 723 SCIP_VAR* var, /**< variable to branch on */ 724 SCIP_Real val, /**< value to branch on */ 725 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */ 726 SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */ 727 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */ 728 ); 729 730 /** n-ary branching on a variable x using a given value 731 * 732 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value. 733 * The branching value is selected as in SCIPbranchVarVal(). 734 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes. 735 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created. 736 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created. 737 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance 738 * from the first nodes. 739 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value. 740 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes. 741 * 742 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value 743 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3 744 * results in a ternary branching where the branching variable is mostly fixed in the middle child. 745 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width 746 * (except for one child if the branching value is not in the middle). 747 * 748 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 749 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 750 * 751 * @pre This method can be called if @p scip is in one of the following stages: 752 * - \ref SCIP_STAGE_SOLVING 753 * 754 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 755 */ 756 SCIP_EXPORT 757 SCIP_RETCODE SCIPbranchVarValNary( 758 SCIP* scip, /**< SCIP data structure */ 759 SCIP_VAR* var, /**< variable to branch on */ 760 SCIP_Real val, /**< value to branch on */ 761 int n, /**< attempted number of children to be created, must be >= 2 */ 762 SCIP_Real minwidth, /**< minimal domain width in children */ 763 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */ 764 int* nchildren /**< pointer to store number of created children, or NULL */ 765 ); 766 767 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN; 768 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional 769 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority 770 * 771 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 772 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 773 * 774 * @pre This method can be called if @p scip is in one of the following stages: 775 * - \ref SCIP_STAGE_SOLVING 776 * 777 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 778 */ 779 SCIP_EXPORT 780 SCIP_RETCODE SCIPbranchLP( 781 SCIP* scip, /**< SCIP data structure */ 782 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 783 ); 784 785 /** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN 786 * 787 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 788 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 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 SCIP_EXPORT 796 SCIP_RETCODE SCIPbranchExtern( 797 SCIP* scip, /**< SCIP data structure */ 798 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 799 ); 800 801 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN 802 * 803 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 804 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 805 * 806 * @pre This method can be called if @p scip is in one of the following stages: 807 * - \ref SCIP_STAGE_SOLVING 808 * 809 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages. 810 */ 811 SCIP_EXPORT 812 SCIP_RETCODE SCIPbranchPseudo( 813 SCIP* scip, /**< SCIP data structure */ 814 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */ 815 ); 816 817 /**@} */ 818 819 #ifdef __cplusplus 820 } 821 #endif 822 823 #endif 824