scip_branch.c
Go to the documentation of this file.
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
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
73 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
74 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
77 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
81 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
82 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
83 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
84 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */
85 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
91 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchrule", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
109/** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL.
110 * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(),
111 * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(),
114 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
122 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
123 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
131 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchruleBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
140 SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, maxdepth,
156 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
159 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
175 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
191 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
207 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
220 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
223 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
236 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
239 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
252 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
255 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecLp", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
268 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
271 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecExt", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
284 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
287 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecPs", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
348/** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
363/** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
378/** gets branching candidates for LP solution branching (fractional variables) along with solution values,
379 * fractionalities, and number of branching candidates; The number of branching candidates does NOT
380 * account for fractional implicit integer variables which should not be used for branching decisions.
382 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
384 * branching rules should always select the branching candidate among the first npriolpcands of the candidate
387 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
398 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
399 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
401 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
402 int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */
405 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
407 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
419/** gets number of branching candidates for LP solution branching (number of fractional variables)
421 * @return the number of branching candidates for LP solution branching (number of fractional variables).
435 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
437 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
449 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates\n", retcode);
473 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
475 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
487 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates with maximal priority\n", retcode);
495/** gets external branching candidates along with solution values, scores, and number of branching candidates;
497 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
500 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
508 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
513 SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */
514 SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */
515 SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */
517 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
518 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
519 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
520 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
526 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
528 SCIP_CALL( SCIPbranchcandGetExternCands(scip->branchcand, externcands, externcandssol, externcandsscore, nexterncands,
549 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
569 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
589 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
609 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
616 * @return the number of implicit integer external branching candidates with maximal branch priority.
629 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
649 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchConts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
654/** insert variable, its score and its solution value into the external branching candidate storage
655 * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon
657 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
675 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
695 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
700/** checks whether the given variable is contained in the candidate storage for external branching
702 * @return whether the given variable is contained in the candidate storage for external branching.
717 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcontainsExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
722/** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
724 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
735 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
737 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
740 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
762 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
767/** gets number of branching candidates with maximal branch priority for pseudo solution branching
769 * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
781 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
786/** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
788 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
799 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
804/** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
806 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
817 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
822/** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
824 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
835 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
856 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
863/** calculates the branching score out of the gain predictions for a branching with arbitrary many children
865 * @return the branching score out of the gain predictions for a branching with arbitrary many children.
879 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScoreMultiple", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
903 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchingPoint", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
910/** calculates the node selection priority for moving the given variable's LP value to the given target value;
913 * @return the node selection priority for moving the given variable's LP value to the given target value.
923 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
929 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcNodeselPriority", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
933 return SCIPtreeCalcNodeselPriority(scip->tree, scip->set, scip->stat, var, branchdir, targetvalue);
936/** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
939 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
953 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcChildEstimate", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
960/** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree
963 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after
993 * = parentestimate - min{f_b * pscdown_b, (1-f_b) * pscup_b} + (targetvalue-oldvalue)*{pscdown_b or pscup_b}
997 estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol) - MIN(pscdown, pscup);
1009 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1021 SCIP_Real estimate /**< estimate for(transformed) objective value of best feasible solution in subtree */
1026 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1028 SCIP_CALL( SCIPnodeCreateChild(node, scip->mem->probmem, scip->set, scip->stat, scip->tree, nodeselprio, estimate) );
1042 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1053 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1055 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1058 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVar", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1075 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1076 scip->lp, scip->branchcand, scip->eventqueue, var, SCIP_INVALID, downchild, eqchild, upchild) );
1081/** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created
1083 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1100 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarHole", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1104 SCIP_CALL( SCIPtreeBranchVarHole(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1105 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, left, right, downchild, upchild) );
1111 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds;
1118 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1130 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1132 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1135 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarVal", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1139 /* A continuous variable will be fixed if SCIPisRelEQ(lb,ub) is true. Otherwise, the given branching value should be
1140 * such that its value is not equal to one of the bounds. We assert this by requiring that it is at least eps/2 away
1141 * from each bound. The 2.1 is there, because ub-lb may be in (eps, 2*eps], in which case there is no way to choose a
1142 * branching value that is at least eps away from both bounds. However, if the variable bounds are below/above
1147 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1148 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1157 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1165 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
1167 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
1168 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
1169 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
1170 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance
1172 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
1173 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
1175 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
1176 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
1177 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
1178 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
1181 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1195 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
1199 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarValNary", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1206 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1207 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1216 SCIP_CALL( SCIPtreeBranchVarNary(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1217 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, val, n, minwidth, widthfactor, nchildren) );
1222/** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
1223 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
1224 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
1226 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1239 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1241 SCIP_CALL( SCIPbranchExecLP(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1242 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1248/** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN
1250 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1263 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchExtern", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1265 SCIP_CALL( SCIPbranchExecExtern(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1266 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1272/** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN
1274 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1287 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchPseudo", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1289 SCIP_CALL( SCIPbranchExecPseudo(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1290 scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound, TRUE, result) );
SCIP_RETCODE SCIPbranchcandGetLPCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: branch.c:405
int SCIPbranchcandGetNPrioPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:862
int SCIPbranchcandGetNExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:507
SCIP_Real SCIPbranchGetBranchingPoint(SCIP_SET *set, SCIP_TREE *tree, SCIP_VAR *var, SCIP_Real suggestion)
Definition: branch.c:2288
void SCIPbranchruleSetExit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: branch.c:1903
void SCIPbranchruleSetInitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: branch.c:1914
void SCIPbranchruleSetMaxdepth(SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: branch.c:2025
void SCIPbranchruleSetFree(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: branch.c:1881
SCIP_RETCODE SCIPbranchExecPseudo(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2769
void SCIPbranchruleSetInit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: branch.c:1892
SCIP_Real SCIPbranchGetScoreMultiple(SCIP_SET *set, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: branch.c:2250
int SCIPbranchcandGetNPrioExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:517
void SCIPbranchcandClearExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:697
int SCIPbranchcandGetNPrioExternBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:527
void SCIPbranchruleSetExecPs(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: branch.c:1960
int SCIPbranchcandGetNPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:852
int SCIPbranchcandGetNPrioPseudoBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:872
SCIP_RETCODE SCIPbranchcandGetExternCands(SCIP_BRANCHCAND *branchcand, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: branch.c:440
void SCIPbranchruleSetCopy(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: branch.c:1870
int SCIPbranchcandGetNPrioExternImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:547
SCIP_RETCODE SCIPbranchcandGetPseudoCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_PROB *prob, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: branch.c:788
SCIP_RETCODE SCIPbranchExecExtern(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2638
void SCIPbranchruleSetExecExt(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: branch.c:1949
int SCIPbranchcandGetNPrioExternInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:537
int SCIPbranchcandGetNPrioPseudoImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:892
SCIP_RETCODE SCIPbranchcandAddExternCand(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: branch.c:569
int SCIPbranchcandGetNPrioPseudoInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:882
void SCIPbranchruleSetMaxbounddist(SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: branch.c:2047
SCIP_RETCODE SCIPbranchExecLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2536
void SCIPbranchruleSetPriority(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, int priority)
Definition: branch.c:2001
void SCIPbranchruleSetExitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: branch.c:1925
SCIP_RETCODE SCIPbranchruleCreate(SCIP_BRANCHRULE **branchrule, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, 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: branch.c:1349
void SCIPbranchruleSetExecLp(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: branch.c:1938
int SCIPbranchcandGetNPrioExternConts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:557
SCIP_Real SCIPbranchGetScore(SCIP_SET *set, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: branch.c:2190
SCIP_Bool SCIPbranchcandContainsExternCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:712
internal methods for branching rules and branching candidate storage
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2208
methods for debugging
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:201
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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:116
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:233
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:334
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:68
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:217
SCIP_RETCODE SCIPsetBranchruleMaxbounddist(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: scip_branch.c:364
SCIP_RETCODE SCIPsetBranchruleMaxdepth(SCIP *scip, SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: scip_branch.c:349
int SCIPgetNPrioExternBranchConts(SCIP *scip)
Definition: scip_branch.c:643
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:511
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:920
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:665
int SCIPgetNPrioPseudoBranchInts(SCIP *scip)
Definition: scip_branch.c:813
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:897
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:947
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:971
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:795
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1258
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:1189
int SCIPgetNPrioPseudoBranchImpls(SCIP *scip)
Definition: scip_branch.c:831
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1126
SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1091
int SCIPgetNPrioPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:777
int SCIPgetNPrioExternBranchInts(SCIP *scip)
Definition: scip_branch.c:603
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
int SCIPgetNPrioExternBranchBins(SCIP *scip)
Definition: scip_branch.c:583
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
int SCIPgetNPrioExternBranchCands(SCIP *scip)
Definition: scip_branch.c:563
int SCIPgetNPrioExternBranchImpls(SCIP *scip)
Definition: scip_branch.c:623
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1234
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:872
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
SCIP_RETCODE SCIPbranchPseudo(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1282
SCIP_Bool SCIPcontainsExternBranchCand(SCIP *scip, SCIP_VAR *var)
Definition: scip_branch.c:709
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:1156
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
internal methods for LP management
Definition: objbenders.h:44
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
public methods for numerical tolerances
SCIP_RETCODE SCIPsetIncludeBranchrule(SCIP_SET *set, SCIP_BRANCHRULE *branchrule)
Definition: set.c:4861
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6221
SCIP_BRANCHRULE * SCIPsetFindBranchrule(SCIP_SET *set, const char *name)
Definition: set.c:4885
internal methods for global SCIP settings
Definition: struct_branch.h:79
Definition: struct_tree.h:142
Definition: struct_var.h:208
Definition: struct_scip.h:70
datastructures for block memory pools and memory buffers
datastructures for collecting primal CIP solutions and primal informations
SCIP main data structure.
datastructures for global SCIP settings
datastructures for problem variables
SCIP_RETCODE SCIPtreeBranchVarHole(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: tree.c:5809
SCIP_RETCODE SCIPtreeBranchVarNary(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: tree.c:5951
SCIP_RETCODE SCIPtreeBranchVar(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: tree.c:5478
SCIP_RETCODE SCIPnodeCreateChild(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: tree.c:1039
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: tree.c:5269
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5419
internal methods for branch and bound tree
SCIP_Real SCIPvarGetPseudocost(SCIP_VAR *var, SCIP_STAT *stat, SCIP_Real solvaldelta)
Definition: var.c:14477
internal methods for problem variables