scip_branch.h
Go to the documentation of this file.
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
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
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
69 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
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 */
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(),
86 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
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
107 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
139 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
147 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
155 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
163 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
171 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
201 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
209 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
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.
228 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
230 * branching rules should always select the branching candidate among the first npriolpcands of the candidate
233 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
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 */
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 */
252 /** gets number of branching candidates for LP solution branching (number of fractional variables)
254 * @return the number of branching candidates for LP solution branching (number of fractional variables).
280 /** gets external branching candidates along with solution values, scores, and number of branching candidates;
282 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
285 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
293 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
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 */
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,
368 * @return the number of implicit integer external branching candidates with maximal branch priority.
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
397 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
425 /** checks whether the given variable is contained in the candidate storage for external branching
427 * @return whether the given variable is contained in the candidate storage for external branching.
440 /** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
442 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
454 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
456 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
474 /** gets number of branching candidates with maximal branch priority for pseudo solution branching
476 * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
489 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
491 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
503 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
505 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
517 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
519 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
548 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children
550 * @return the branching score out of the gain predictions for a branching with arbitrary many children.
583 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
586 * @return the node selection priority for moving the given variable's LP value to the given target value.
597 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
603 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
606 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
621 /** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree
624 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after
642 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
655 SCIP_Real estimate /**< estimate for (transformed) objective value of best feasible solution in subtree */
667 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
679 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
684 /** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created
686 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
705 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds;
712 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
725 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
732 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
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
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.
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
748 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
763 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
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
771 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
785 /** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN
787 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
801 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN
803 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:325
SCIP_EXPORT SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_EXPORT SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:656
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
SCIP_EXPORT int SCIPgetNPrioExternBranchCands(SCIP *scip)
Definition: scip_branch.c:554
SCIP_EXPORT SCIP_Bool SCIPcontainsExternBranchCand(SCIP *scip, SCIP_VAR *var)
Definition: scip_branch.c:700
Definition: struct_scip.h:59
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleMaxdepth(SCIP *scip, SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: scip_branch.c:340
SCIP_EXPORT SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
SCIP_EXPORT SCIP_RETCODE SCIPbranchPseudo(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1273
SCIP_EXPORT int SCIPgetNPrioExternBranchConts(SCIP *scip)
Definition: scip_branch.c:634
Definition: struct_var.h:198
SCIP_EXPORT SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1249
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
SCIP_EXPORT int SCIPgetNPrioPseudoBranchInts(SCIP *scip)
Definition: scip_branch.c:804
SCIP_EXPORT SCIP_RETCODE SCIPbranchVarValNary(SCIP *scip, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: scip_branch.c:1180
SCIP_EXPORT SCIP_RETCODE SCIPincludeBranchrule(SCIP *scip, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_DECL_BRANCHCOPY((*branchcopy)), SCIP_DECL_BRANCHFREE((*branchfree)), SCIP_DECL_BRANCHINIT((*branchinit)), SCIP_DECL_BRANCHEXIT((*branchexit)), SCIP_DECL_BRANCHINITSOL((*branchinitsol)), SCIP_DECL_BRANCHEXITSOL((*branchexitsol)), SCIP_DECL_BRANCHEXECLP((*branchexeclp)), SCIP_DECL_BRANCHEXECEXT((*branchexecext)), SCIP_DECL_BRANCHEXECPS((*branchexecps)), SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:59
SCIP_EXPORT SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1117
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:107
SCIP_EXPORT SCIP_BRANCHRULE ** SCIPgetBranchrules(SCIP *scip)
Definition: scip_branch.c:303
type definitions for branching rules
Definition: struct_tree.h:132
SCIP_EXPORT SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
SCIP_EXPORT int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
SCIP_EXPORT SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:962
SCIP_EXPORT int SCIPgetNExternBranchCands(SCIP *scip)
Definition: scip_branch.c:534
SCIP_EXPORT SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
type definitions for SCIP's main datastructure
SCIP_EXPORT SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:911
SCIP_EXPORT SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:502
SCIP_EXPORT int SCIPgetNPrioPseudoBranchImpls(SCIP *scip)
Definition: scip_branch.c:822
SCIP_EXPORT SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1082
type definitions for problem variables
Definition: struct_branch.h:69
SCIP_EXPORT SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:863
SCIP_EXPORT SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
SCIP_EXPORT int SCIPgetNPrioExternBranchImpls(SCIP *scip)
Definition: scip_branch.c:614
SCIP_EXPORT int SCIPgetNPrioExternBranchInts(SCIP *scip)
Definition: scip_branch.c:594
type definitions for branch and bound tree
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:208
SCIP_EXPORT int SCIPgetNPrioPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:768
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
SCIP_EXPORT void SCIPclearExternBranchCands(SCIP *scip)
Definition: scip_branch.c:680
SCIP_EXPORT SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:938
SCIP_EXPORT int SCIPgetNPrioLPBranchCands(SCIP *scip)
Definition: scip_branch.c:457
result codes for SCIP callback methods
type definitions for branching and inference history
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:224
SCIP_EXPORT SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
SCIP_EXPORT int SCIPgetNPrioExternBranchBins(SCIP *scip)
Definition: scip_branch.c:574
SCIP_EXPORT SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1225
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
SCIP_EXPORT int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:786
SCIP_EXPORT SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:840
common defines and data types used in all packages of SCIP
Definition: objbenders.h:33
SCIP_EXPORT SCIP_RETCODE SCIPsetBranchruleMaxbounddist(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: scip_branch.c:355