branch.c
Go to the documentation of this file.
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
216 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
218 SCIPsetDebugMsg(set, "calculating LP branching candidates: validlp=%" SCIP_LONGINT_FORMAT ", lpcount=%" SCIP_LONGINT_FORMAT "\n",
253 /* construct the LP branching candidate set, moving the candidates with maximal priority to the front */
278 /* LP branching candidates are fractional binary and integer variables; implicit variables are kept at the end
285 /* ignore fixed variables (due to numerics, it is possible, that the LP solution of a fixed integer variable
294 /* The fractionality should not be smaller than -feastol, however, if the primsol is large enough
295 * and close to an integer, fixed precision floating point arithmetic might give us values slightly
296 * smaller than -feastol. Originally, the "frac >= -feastol"-check was within SCIPsetIsFeasFracIntegral(),
297 * however, we relaxed it to "frac >= -2*feastol" and have the stricter check here for small-enough primsols.
379 SCIPsetDebugMsg(set, " -> candidate %d: var=<%s>, sol=%g, frac=%g, prio=%d (max: %d) -> pos %d\n",
380 branchcand->nlpcands, SCIPvarGetName(var), primsol, frac, branchpriority, branchcand->lpmaxpriority,
385 /* in debug mode we assert that the variables are positioned correctly (binaries and integers first,
390 assert(c >= branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) != SCIP_VARTYPE_IMPLINT);
391 assert(c < branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) == SCIP_VARTYPE_IMPLINT);
399 SCIPsetDebugMsg(set, " -> %d fractional variables (%d of maximal priority)\n", branchcand->nlpcands, branchcand->npriolpcands);
411 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
412 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
414 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
415 int* nfracimplvars /**< pointer to store the number of implicit fractional variables, or NULL */
431 *npriolpcands = (set->branch_preferbinary && branchcand->npriolpbins > 0 ? branchcand->npriolpbins
442 SCIP_VAR*** externcands, /**< pointer to store the array of external branching candidates, or NULL */
443 SCIP_Real** externcandssol, /**< pointer to store the array of external candidate solution values, or NULL */
444 SCIP_Real** externcandsscore, /**< pointer to store the array of external candidate scores, or NULL */
445 int* nexterncands, /**< pointer to store the number of external branching candidates, or NULL */
446 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
447 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
448 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
449 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
546 /** gets number of implicit integer external branching candidates with maximal branch priority */
563 return branchcand->nprioexterncands - branchcand->nprioexternbins - branchcand->nprioexternints - branchcand->nprioexternimpls;
566 /** insert variable, its score and its solution value into the external branching candidate storage
567 * the absolute difference of the current lower and upper bounds of the variable must be at least epsilon
583 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); /* the variable should not be fixed yet */
584 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || !SCIPsetIsEQ(set, SCIPsetCeil(set, SCIPvarGetLbLocal(var)), SCIPsetFloor(set, SCIPvarGetUbLocal(var)))); /* a discrete variable should also not be fixed, even after rounding bounds to integral values */
585 assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR || !SCIPsetIsEQ(set, SCIPvarGetMultaggrLbLocal(var, set), SCIPvarGetMultaggrUbLocal(var, set))); /* also the current bounds of a multi-aggregated variable should not be fixed yet */
595 SCIPsetDebugMsg(set, "inserting external candidate <%s> of type %d and priority %d into candidate set (maxprio: %d), score = %g, solval = %g\n",
598 /* insert the variable into externcands, making sure, that the highest priority candidates are at the front
622 * slot (binaries first, integers next, implicit integers next, continuous last) and increase the number
628 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexterncands];
629 branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexterncands];
634 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER || vartype == SCIP_VARTYPE_IMPLINT )
636 if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls )
639 branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
641 branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
643 branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
645 insertpos = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
670 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexternbins];
671 branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexternbins];
686 SCIPsetDebugMsg(set, " -> inserted at position %d (nprioexterncands=%d)\n", insertpos, branchcand->nprioexterncands);
688 assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
689 assert(0 <= branchcand->nprioexternbins && branchcand->nprioexternbins <= branchcand->nprioexterncands);
690 assert(0 <= branchcand->nprioexternints && branchcand->nprioexternints <= branchcand->nprioexterncands);
691 assert(0 <= branchcand->nprioexternimpls && branchcand->nprioexternimpls <= branchcand->nprioexterncands);
711 /** checks whether the given variable is contained in the candidate storage for external branching */
727 /* look for the variable in the externcands, using the fact, that the highest priority candidates are at the front
732 /* the branching priority of the variable is higher than the maximal priority contained in the array;
743 * look for it in the correct slot (binaries first, integers next, implicit integers next, continuous last)
765 if( branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + i] == var )
771 for( i = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
777 /* the branching priority of the variable is lower than the maximal priority contained in the array;
792 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
794 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
814 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
845 *npriopseudocands = (set->branch_preferbinary && branchcand->npriopseudobins > 0 ? branchcand->npriopseudobins
861 /** gets number of branching candidates with maximal branch priority for pseudo solution branching */
871 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching */
881 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching */
891 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching */
898 return branchcand->npriopseudocands - branchcand->npriopseudobins - branchcand->npriopseudoints;
901 /** insert pseudocand at given position, or to the first positions of the maximal priority candidates, using the
922 SCIPdebugMessage("inserting pseudo candidate <%s> of type %d and priority %d into candidate set at position %d (maxprio: %d)\n",
925 /* insert the variable into pseudocands, making sure, that the highest priority candidates are at the front
948 * slot (binaries first, integers next, implicit integers last) and increase the number of maximal priority candidates
984 SCIPdebugMessage(" -> inserted at position %d (npriopseudocands=%d)\n", insertpos, branchcand->npriopseudocands);
986 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
987 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
988 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
991 /** sorts the pseudo branching candidates, such that the candidates of maximal priority are at the front,
1003 assert(branchcand->npriopseudocands == 0); /* is only be called after removal of last maximal candidate */
1020 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1021 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1022 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1047 /* Note that the branching priority of the variable to be removed is not necessarily equal to pseudomaxpriority, since
1048 * the status of the variable might have changed, leading to a change in the branching priority. Moreover, if the
1049 * variable was part of an aggregation, even other variables might at this point have different priorities. */
1050 SCIPdebugMessage("removing pseudo candidate <%s> of type %d and priority %d at %d from candidate set (maxprio: %d)\n",
1054 /* delete the variable from pseudocands, making sure, that the highest priority candidates are at the front
1078 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
1107 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1108 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1109 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1111 /* if all maximal priority candidates were removed, resort the array s.t. the new maximal priority candidates
1145 if( (SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN)
1149 /* variable is neither continuous nor fixed and has non-empty domain: make sure it is member of the pseudo branching candidate list */
1168 /* variable is continuous or fixed or has empty domain: make sure it is not member of the pseudo branching candidate list */
1175 /** updates branching priority of the given variable and update the pseudo candidate array if needed */
1195 /* if the variable currently belongs to the priority set or the new branching priority is larger than the current one,
1206 /* if the variable is not part of the pseudo branching candidate array, check if it is a pseudo branching candidate
1228 return strcmp(SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem1), SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem2));
1241 SCIP_CALL( SCIPsetBranchrulePriority(scip, (SCIP_BRANCHRULE*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
1258 SCIPsetDebugMsg(set, "including branching rule %s in subscip %p\n", SCIPbranchruleGetName(branchrule), (void*)set->scip);
1275 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
1276 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
1283 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1284 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1285 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
1286 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1287 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
1335 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level, up to which branching rule <%s> should be used (-1 for no limit)", name);
1340 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching rule (0.0: only on current best node, 1.0: on all nodes)");
1357 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
1358 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
1365 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1366 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1367 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
1368 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1369 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
1377 SCIP_CALL_FINALLY( doBranchruleCreate(branchrule, set, messagehdlr, blkmem, name, desc, priority, maxdepth,
1378 maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol, branchexeclp,
1563 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1565 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1569 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1604 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from LP solution branching\n",
1610 SCIPerrorMessage("branching rule <%s> added a constraint in LP solution branching without permission\n",
1671 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1673 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1677 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1712 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from external solution branching\n",
1718 SCIPerrorMessage("branching rule <%s> added a constraint in external solution branching without permission\n",
1775 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1777 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1781 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1813 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from pseudo solution branching\n",
1819 SCIPerrorMessage("branching rule <%s> added a constraint in pseudo solution branching without permission\n",
1872 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
1916 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
1927 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
1940 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
1951 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
1962 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
2014 /** gets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
2024 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
2036 /** gets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
2046 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
2060 SCIP_BRANCHRULE* branchrule, /**< the branching rule for which all clocks should be enabled or disabled */
2140 /** gets the total number of constraints, the branching rule added to the respective local nodes (not counting constraints
2212 /* disregard near zero score differences between variables and consider the branching factor for them */
2249 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children */
2263 /* search for the two minimal gains in the child list and use these to calculate the branching score */
2283 * if this value is at infinity, then 0.0 projected onto the bounds and then moved inside the interval is used
2285 * for a continuous variable, the parameter branching/clamp defines how far a branching point need to be from the bounds of a variable
2286 * the latter is only applied if no point has been suggested, or the suggested point is not inside the variable's interval
2344 /* if the value in the LP or pseudosolution is large (here 1e+12), use 0.0 (will be projected onto bounds below) */
2347 else if( SCIPtreeHasCurrentNodeLP(tree) && set->branch_midpull > 0.0 && !SCIPsetIsInfinity(set, -lb) && !SCIPsetIsInfinity(set, ub) )
2356 * that is, if there has been already one or several branchings on this variable, then give more emphasis on LP solution
2375 /* make sure branchpoint is on interval, below we make sure that it is within bounds for continuous vars */
2410 /* if one bound is missing, we are temporarily guessing the other one, so we can apply the clamp below */
2457 /* if selected branching point is close to 0.0 and bounds are away from 0.0, it often makes sense to branch exactly on 0.0 */
2458 if( SCIPsetIsFeasZero(set, branchpoint) && SCIPsetIsFeasNegative(set, lb) && SCIPsetIsFeasPositive(set, ub) )
2469 /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2473 * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better?
2495 /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2499 * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better? */
2510 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
2511 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
2512 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
2544 SCIPsetDebugMsg(set, "branching on LP solution with %d (+%d) fractional (+implicit fractional) variables (%d of maximal priority)\n",
2552 /* if there is a non-fixed variable with higher priority than the maximal priority of the fractional candidates,
2557 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2567 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2569 SCIP_CALL( SCIPbranchruleExecLPSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2581 /* no branching method succeeded in choosing a branching: just branch on the first fractional variable with maximal
2606 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2615 /** calls branching rules to branch on an external solution; if no external branching candidates exist, the result is SCIP_DIDNOTRUN */
2637 assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
2642 SCIPsetDebugMsg(set, "branching on external solution with %d branching candidates (%d of maximal priority)\n",
2649 /* if there is a non-fixed variable with higher priority than the maximal priority of the external candidates,
2654 /* @todo: adjust this, that also LP branching might be called, if lpmaxpriority != externmaxpriority.
2657 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2667 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2669 SCIP_CALL( SCIPbranchruleExecExternSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2681 /* if all branching rules did nothing, then they should also not have cleared all branching candidates */
2684 /* no branching method succeeded in choosing a branching: just branch on the first branching candidates with maximal
2685 * priority, and out of these on the one with maximal branch factor, and out of these on the one with largest domain
2703 if( SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(cand)) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(cand)) )
2709 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) || (priority == bestpriority && factor == bestfactor && domain > bestdomain) ) /*lint !e777*/
2722 assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2724 assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2727 SCIPsetDebugMsg(set, "no branching method succeeded; fallback selected to branch on variable <%s> with bounds [%g, %g] on value %g\n",
2730 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, val,
2735 /* if the bounds are too close, it may happen that we cannot branch but rather fix the variable */
2746 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN */
2768 SCIPsetDebugMsg(set, "branching on pseudo solution with %d unfixed variables\n", branchcand->npseudocands);
2780 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2782 SCIP_CALL( SCIPbranchruleExecPseudoSol(set->branchrules[i], set, stat, tree, cutoffbound, allowaddcons, result) );
2794 /* no branching method succeeded in choosing a branching: just branch on the first unfixed variable with maximal
2817 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
SCIP_Longint SCIPbranchruleGetNConssFound(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2143
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:325
int SCIPbranchcandGetNPrioExternBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:527
SCIP_Longint SCIPbranchruleGetNLPCalls(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2091
Definition: type_result.h:33
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
internal methods for managing events
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6038
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:5416
void SCIPbranchruleSetCopy(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: branch.c:1870
internal methods for branch and bound tree
Definition: type_var.h:40
SCIP_Longint SCIPbranchruleGetNChildren(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2163
SCIP_RETCODE SCIPbranchruleExitsol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1510
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
internal methods for clocks and timing issues
int SCIPbranchcandGetNPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:852
SCIP_EXPORT SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:17822
void SCIPbranchruleSetFree(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: branch.c:1881
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPbranchcandCreate(SCIP_BRANCHCAND **branchcand)
Definition: branch.c:134
Definition: struct_var.h:198
SCIP_Real SCIPbranchruleGetMaxbounddist(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2037
int SCIPbranchcandGetNPrioExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:517
SCIP_Real SCIPbranchGetScore(SCIP_SET *set, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: branch.c:2190
Definition: struct_sepastore.h:39
SCIP_Bool SCIPsetIsFeasIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6521
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:2747
int SCIPbranchcandGetNPrioPseudoImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:892
Definition: struct_message.h:36
Definition: type_var.h:53
internal methods for branching rules and branching candidate storage
void SCIPbranchcandClearExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:697
Definition: struct_prob.h:39
SCIP_RETCODE SCIPbranchruleInitsol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1486
Definition: type_result.h:40
static SCIP_RETCODE ensureLpcandsSize(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, int num)
Definition: branch.c:56
internal methods for handling parameter settings
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:251
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7440
static SCIP_RETCODE ensureExterncandsSize(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, int num)
Definition: branch.c:104
int SCIPbranchcandGetExternMaxPrio(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:497
SCIP_RETCODE SCIPbranchruleExecLPSol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_SEPASTORE *sepastore, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:1534
int SCIPbranchcandGetNPrioExternInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:537
internal methods for LP management
SCIP_Bool SCIPsetIsFeasFracIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6532
int SCIPbranchcandGetNPrioPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:862
Definition: heur_padm.c:125
Definition: type_retcode.h:44
SCIP_RETCODE SCIPbranchruleExecPseudoSol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:1748
Definition: struct_lp.h:126
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6074
Definition: struct_set.h:61
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:2514
int SCIPbranchcandGetNExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:507
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6020
SCIP_RETCODE SCIPbranchcandAddExternCand(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: branch.c:569
SCIP_RETCODE SCIPvarChgBranchPriority(SCIP_VAR *var, int branchpriority)
Definition: var.c:11455
Definition: type_clock.h:34
SCIP_EXPORT SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:13021
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
SCIP_Longint SCIPbranchruleGetNExternCalls(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2101
Definition: type_result.h:35
internal methods for storing and manipulating the main problem
SCIP_Real SCIPbranchGetBranchingPoint(SCIP_SET *set, SCIP_TREE *tree, SCIP_VAR *var, SCIP_Real suggestion)
Definition: branch.c:2288
Definition: type_retcode.h:42
SCIP_EXPORT int SCIPvarGetBranchPriority(SCIP_VAR *var)
Definition: var.c:17834
SCIP_RETCODE SCIPbranchruleExit(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1456
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1091
SCIP_Bool SCIPbranchruleIsInitialized(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2173
SCIP_RETCODE SCIPbranchcandGetPseudoCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_PROB *prob, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: branch.c:788
Definition: type_var.h:42
void SCIPbranchruleSetInit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: branch.c:1892
Definition: type_var.h:44
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 SCIPbranchcandGetNPrioLPCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:487
SCIP_Bool SCIPsetIsRelGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6923
Definition: type_retcode.h:33
static SCIP_RETCODE branchcandCalcLPCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: branch.c:204
SCIP_Longint SCIPbranchruleGetNCutsFound(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2131
internal methods for global SCIP settings
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6466
Definition: type_result.h:42
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2949
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6002
SCIP_Bool SCIPbranchcandContainsExternCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:712
internal methods for storing separated cuts
int SCIPbranchruleGetPriority(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1991
Definition: struct_branch.h:69
int SCIPbranchcandGetLPMaxPrio(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:477
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6422
Definition: type_lp.h:34
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:161
void SCIPbranchruleSetMaxdepth(SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: branch.c:2025
internal methods for problem variables
void SCIPbranchruleSetExecLp(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: branch.c:1938
void SCIPbranchruleSetPriority(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, int priority)
Definition: branch.c:2001
int SCIPbranchcandGetNPrioExternConts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:557
Definition: type_var.h:55
Definition: type_var.h:54
Definition: type_var.h:46
void SCIPbranchruleEnableOrDisableClocks(SCIP_BRANCHRULE *branchrule, SCIP_Bool enable)
Definition: branch.c:2059
SCIP_Real SCIPbranchruleGetSetupTime(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2071
SCIP_Bool SCIPsetIsRelLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6879
Definition: struct_reopt.h:130
Definition: type_var.h:41
Definition: type_var.h:45
SCIP_Longint SCIPbranchruleGetNDomredsFound(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2153
SCIP_Real SCIPbranchGetScoreMultiple(SCIP_SET *set, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: branch.c:2250
SCIP_RETCODE SCIPbranchcandUpdateVar(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var)
Definition: branch.c:1136
void SCIPbranchruleSetExecPs(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: branch.c:1960
SCIP_RETCODE SCIPbranchruleExecExternSol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_SEPASTORE *sepastore, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:1641
void SCIPbranchcandInvalidate(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:193
SCIP_RETCODE SCIPbranchcandFree(SCIP_BRANCHCAND **branchcand)
Definition: branch.c:174
void SCIPbranchruleSetInitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: branch.c:1914
Definition: type_lp.h:36
SCIP_Longint SCIPbranchruleGetNCutoffs(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2121
void SCIPbranchruleSetExecExt(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: branch.c:1949
const char * SCIPbranchruleGetDesc(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1981
internal methods for main solving loop and node processing
Definition: struct_lp.h:259
void SCIPbranchruleSetExitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: branch.c:1925
SCIP_Real SCIPbranchruleGetTime(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2081
SCIP_RETCODE SCIPbranchruleInit(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1412
SCIP_RETCODE SCIPbranchruleCopyInclude(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1247
int SCIPbranchcandGetNPrioPseudoBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:872
static SCIP_RETCODE doBranchruleCreate(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:1267
Definition: type_result.h:43
static void branchcandSortPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:995
internal methods for problem statistics
datastructures for branching rules and branching candidate storage
SCIP_RETCODE SCIPbranchruleFree(SCIP_BRANCHRULE **branchrule, SCIP_SET *set)
Definition: branch.c:1385
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6499
SCIP_Longint SCIPbranchruleGetNPseudoCalls(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2111
void SCIPbranchruleSetMaxbounddist(SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: branch.c:2047
void SCIPbranchruleSetExit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: branch.c:1903
static void branchcandRemovePseudoCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:1034
static void branchcandInsertPseudoCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var, int insertpos)
Definition: branch.c:905
SCIP_RETCODE SCIPbranchcandRemoveVar(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:1119
SCIP_Real SCIPvarGetMultaggrUbLocal(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:8304
Definition: type_result.h:45
int SCIPbranchcandGetNPrioPseudoInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:882
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7233
Definition: struct_stat.h:50
Definition: struct_tree.h:175
common defines and data types used in all packages of SCIP
int SCIPbranchruleGetMaxdepth(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2015
Definition: struct_event.h:214
SCIP_RETCODE SCIPsetAddRealParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:2997
Definition: objbenders.h:33
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:2616
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
Definition: type_var.h:43
Definition: struct_branch.h:37
SCIP_Real SCIPvarGetMultaggrLbLocal(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:8238
Definition: type_result.h:39
SCIP callable library.
SCIP_Bool SCIPsetIsFeasNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6510
SCIP_RETCODE SCIPbranchcandUpdateVarBranchPriority(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var, int branchpriority)
Definition: branch.c:1176
int SCIPbranchcandGetNPrioExternImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:547
static SCIP_RETCODE ensurePseudocandsSize(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, int num)
Definition: branch.c:81
memory allocation routines
Definition: type_var.h:58