branch_allfullstrong.c
Go to the documentation of this file.
30 * The all variables full strong branching rule applies strong branching to every non-fixed variable
32 * which will cause the highest gain of the dual bound in the created sub-tree among all branching variables.
34 * For calculating the gain, a look-ahead is performed by solving the child node LPs which will result
37 * For a more mathematical description and a comparison between the strong branching rule and other branching rules
47 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
117 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
120 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
134 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
135 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
147 SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, pseudocandscopy, branchruledata->skipdown, branchruledata->skipup, npseudocands,
148 npriopseudocands, &bestpseudocand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
164 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>[%g,%g] (solval=%g, down=%g, up=%g, score=%g)\n",
165 npseudocands, bestpseudocand, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLPSol(var),
174 SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
184 SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
289 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
292 * @note The variables in the lpcands array must have a fractional value in the current LP solution
336 /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
341 /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
402 integral ? "integral" : "fractional", SCIPvarGetName(pseudocands[c]), SCIPvarGetLbLocal(pseudocands[c]),
411 skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
416 skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
430 "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
440 assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, cutoffbound));
486 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(pseudocands[c]));
501 SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(pseudocands[c]));
570 SCIPdebugMsg(scip, " -> var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
601 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
Definition: type_result.h:42
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
public methods for branch and bound tree
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
Definition: struct_scip.h:68
public methods for memory management
static SCIP_DECL_BRANCHEXECPS(branchExecpsAllfullstrong)
Definition: branch_allfullstrong.c:266
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
Definition: struct_var.h:207
static SCIP_DECL_BRANCHINIT(branchInitAllfullstrong)
Definition: branch_allfullstrong.c:236
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
Definition: scip_solvingstats.c:4385
Definition: type_message.h:54
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:872
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
public methods for problem variables
public methods for branching rules
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
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
public methods for SCIP variables
SCIP_RETCODE SCIPgetVarStrongbranchInt(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Bool idempotent, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip_var.c:3662
Definition: struct_tree.h:141
SCIP_RETCODE SCIPincludeBranchruleAllfullstrong(SCIP *scip)
Definition: branch_allfullstrong.c:586
public methods for numerical tolerances
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
public methods for querying solving statistics
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8780
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
public methods for the branch-and-bound tree
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
static SCIP_DECL_BRANCHFREE(branchFreeAllfullstrong)
Definition: branch_allfullstrong.c:218
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
static SCIP_RETCODE branch(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
Definition: branch_allfullstrong.c:87
Definition: type_retcode.h:42
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
static SCIP_DECL_BRANCHEXECLP(branchExeclpAllfullstrong)
Definition: branch_allfullstrong.c:250
Definition: type_result.h:51
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
Definition: struct_branch.h:78
Definition: type_lp.h:43
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip_var.c:2686
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip_prob.c:3765
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Bool idempotent, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip_var.c:2919
static SCIP_DECL_BRANCHCOPY(branchCopyAllfullstrong)
Definition: branch_allfullstrong.c:204
public methods for the LP relaxation, rows and columns
all variables full strong LP branching rule
public methods for branching rule plugins and branching
general public methods
public methods for message output
Definition: type_result.h:52
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
public methods for message handling
Definition: type_result.h:54
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIP_RETCODE SCIPselectVarPseudoStrongBranching(SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, int *bestpseudocand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
Definition: branch_allfullstrong.c:294
Definition: objbenders.h:43
public methods for global and local (sub)problems
Definition: type_result.h:48
memory allocation routines