scip_branch.c
Go to the documentation of this file.
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67 * @note method has all branching rule callbacks as arguments and is thus changed every time a new
68 * callback is added in future releases; consider using SCIPincludeBranchruleBasic() and setter functions
76 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
77 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
80 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
84 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
85 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
86 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
87 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */
88 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
94 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchrule", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
112/** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL.
113 * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(),
114 * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(),
121 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
129 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
130 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
138 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchruleBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
147 SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, maxdepth,
163 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
166 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
182 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
198 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
214 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
227 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
230 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
243 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
246 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
259 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
262 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecLp", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
275 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
278 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecExt", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
291 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
294 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecPs", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
355/** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
370/** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
385/** gets branching candidates for LP solution branching (fractional variables) along with solution values,
386 * fractionalities, and number of branching candidates; The number of branching candidates does NOT
387 * account for fractional implicit integer variables which should not be used for branching decisions.
389 * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
391 * branching rules should always select the branching candidate among the first npriolpcands of the candidate
394 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
405 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
406 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
408 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
409 int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */
412 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
414 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
426/** gets number of branching candidates for LP solution branching (number of fractional variables)
428 * @return the number of branching candidates for LP solution branching (number of fractional variables).
442 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
444 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
456 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates\n", retcode);
480 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
482 if( SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_OPTIMAL && SCIPlpGetSolstat(scip->lp) != SCIP_LPSOLSTAT_UNBOUNDEDRAY )
494 SCIPerrorMessage("Error <%d> during computation of the number of LP branching candidates with maximal priority\n", retcode);
502/** gets external branching candidates along with solution values, scores, and number of branching candidates;
504 * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
507 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
515 * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
520 SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */
521 SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */
522 SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */
524 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
525 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
526 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
527 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
533 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
535 SCIP_CALL( SCIPbranchcandGetExternCands(scip->branchcand, externcands, externcandssol, externcandsscore, nexterncands,
556 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
576 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
596 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
616 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
623 * @return the number of implicit integer external branching candidates with maximal branch priority.
636 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
656 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchConts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
661/** insert variable, its score and its solution value into the external branching candidate storage
662 * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon
664 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
682 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
702 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
707/** checks whether the given variable is contained in the candidate storage for external branching
709 * @return whether the given variable is contained in the candidate storage for external branching.
724 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcontainsExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
729/** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
731 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
742 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
744 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
747 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
769 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
774/** gets number of branching candidates with maximal branch priority for pseudo solution branching
776 * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
788 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
793/** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
795 * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
806 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
811/** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
813 * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
824 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
829/** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
831 * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
842 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
863 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
870/** calculates the branching score out of the gain predictions for a branching with arbitrary many children
872 * @return the branching score out of the gain predictions for a branching with arbitrary many children.
886 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScoreMultiple", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
910 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchingPoint", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
917/** calculates the node selection priority for moving the given variable's LP value to the given target value;
920 * @return the node selection priority for moving the given variable's LP value to the given target value.
930 SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
936 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcNodeselPriority", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
940 return SCIPtreeCalcNodeselPriority(scip->tree, scip->set, scip->stat, var, branchdir, targetvalue);
943/** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
946 * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
960 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcChildEstimate", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
967/** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree
970 * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after
1000 * = parentestimate - min{f_b * pscdown_b, (1-f_b) * pscup_b} + (targetvalue-oldvalue)*{pscdown_b or pscup_b}
1004 estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol) - MIN(pscdown, pscup);
1016 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1028 SCIP_Real estimate /**< estimate for(transformed) objective value of best feasible solution in subtree */
1033 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1035 SCIP_CALL( SCIPnodeCreateChild(node, scip->mem->probmem, scip->set, scip->stat, scip->tree, nodeselprio, estimate) );
1049 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1060 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1062 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1065 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVar", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1082 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1083 scip->lp, scip->branchcand, scip->eventqueue, var, SCIP_INVALID, downchild, eqchild, upchild) );
1088/** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created
1090 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1107 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarHole", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1111 SCIP_CALL( SCIPtreeBranchVarHole(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1112 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, left, right, downchild, upchild) );
1118 * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds;
1125 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1137 SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1139 SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1142 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarVal", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1146 /* A continuous variable will be fixed if SCIPisRelEQ(lb,ub) is true. Otherwise, the given branching value should be
1147 * 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
1148 * 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
1149 * branching value that is at least eps away from both bounds. However, if the variable bounds are below/above
1154 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1155 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1164 SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1172 * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
1174 * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
1175 * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
1176 * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
1177 * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance
1179 * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
1180 * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
1182 * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
1183 * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
1184 * results in a ternary branching where the branching variable is mostly fixed in the middle child.
1185 * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
1188 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1202 SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
1206 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarValNary", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1213 SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1214 (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1223 SCIP_CALL( SCIPtreeBranchVarNary(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1224 scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, val, n, minwidth, widthfactor, nchildren) );
1229/** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
1230 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
1231 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
1233 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1246 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1248 SCIP_CALL( SCIPbranchExecLP(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1249 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1255/** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN
1257 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1270 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchExtern", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1272 SCIP_CALL( SCIPbranchExecExtern(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1273 scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1279/** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN
1281 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1294 SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchPseudo", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1296 SCIP_CALL( SCIPbranchExecPseudo(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1297 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:2203
methods for debugging
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:272
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:208
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:256
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:304
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:160
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:123
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:288
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:176
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:240
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:192
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:341
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:71
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:224
SCIP_RETCODE SCIPsetBranchruleMaxbounddist(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: scip_branch.c:371
SCIP_RETCODE SCIPsetBranchruleMaxdepth(SCIP *scip, SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: scip_branch.c:356
int SCIPgetNPrioExternBranchConts(SCIP *scip)
Definition: scip_branch.c:650
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:518
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:927
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:672
int SCIPgetNPrioPseudoBranchInts(SCIP *scip)
Definition: scip_branch.c:820
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:904
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:954
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:978
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:802
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1265
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:1196
int SCIPgetNPrioPseudoBranchImpls(SCIP *scip)
Definition: scip_branch.c:838
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1133
SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1098
int SCIPgetNPrioPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:784
int SCIPgetNPrioExternBranchInts(SCIP *scip)
Definition: scip_branch.c:610
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:402
int SCIPgetNPrioExternBranchBins(SCIP *scip)
Definition: scip_branch.c:590
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1057
int SCIPgetNPrioExternBranchCands(SCIP *scip)
Definition: scip_branch.c:570
int SCIPgetNPrioExternBranchImpls(SCIP *scip)
Definition: scip_branch.c:630
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1241
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:740
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:879
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1024
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:856
SCIP_RETCODE SCIPbranchPseudo(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1289
SCIP_Bool SCIPcontainsExternBranchCand(SCIP *scip, SCIP_VAR *var)
Definition: scip_branch.c:716
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:5827
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:5969
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:5496
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:1040
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: tree.c:5287
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5437
internal methods for branch and bound tree
SCIP_Real SCIPvarGetPseudocost(SCIP_VAR *var, SCIP_STAT *stat, SCIP_Real solvaldelta)
Definition: var.c:14504
internal methods for problem variables