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