branch_inference.c
Go to the documentation of this file.
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61 #define DEFAULT_RELIABLESCORE 0.001 /**< score which is seen to be reliable for a branching decision */
62 #define DEFAULT_FRACTIONALS TRUE /**< should branching on LP solution be restricted to the fractional variables? */
63 #define DEFAULT_USEWEIGHTEDSUM TRUE /**< should a weighted sum of inference, conflict and cutoff weights be used? */
77 SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */
78 SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */
83 /** evaluate the given candidate with the given score against the currently best know candidate, tiebreaking included */
93 SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */
113 /* the candidate has the same score as the best known candidate; therefore we use a second and third
116 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
118 * - if the absolute values of the objective coefficient are equal the variable index is used to define a
121 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
122 * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
124 * starting a probing mode might already change the order of these arrays. To be independent of that
125 * the selection should be unique. Otherwise, to selection process can get influenced by starting a
128 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
137 /** evaluate the given candidate with the given score against the currently best know candidate */
155 /* the score of the candidate is better than the currently best know candidate, so it should be the first candidate in bestcands and nbestcands should be set to 1*/
165 /* the score of the candidate is comparable to the currently known best, so we add it to bestcands and increase nbestcands by 1*/
171 /** choose a singular best candidate from bestcands and move it to the beginning of the candidate array */
188 /* the candidate has the same score as the best known candidate; therefore we use a second and third
191 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
193 * - if the absolute values of the objective coefficient are equal the variable index is used to define a
196 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
197 * performance too much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
199 * starting a probing mode might already change the order of these arrays. To be independent of that
200 * the selection should be unique. Otherwise, to selection process can get influenced by starting a
203 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(bestcands[0]) < SCIPvarGetIndex(bestcands[c])) ) /*lint !e777*/
210 /** check if the score for the given domain value and variable domain value is better than the current best know one */
221 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
231 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
237 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
252 /** return an aggregated score for the given variable using the conflict score and cutoff score */
269 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
275 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
283 /** return an aggregated score for the given variable using the conflict score and cutoff score */
291 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
329 checkValueScore(value, histories[v], SCIP_BRANCHDIR_DOWNWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
332 checkValueScore(value, histories[v], SCIP_BRANCHDIR_UPWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
366 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
380 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
383 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
387 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, nbestcands);
403 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
423 /* check if conflict score, inferences, and cutoff score should be used in combination; otherwise just use
444 /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and
448 selectBestCands(scip, bestcands, candsols, nbestcands, 0.0, inferenceweight, cutoffweight, reliablescore,
455 selectBestCands(scip, cands, candsols, ncands, conflictweight, inferenceweight, cutoffweight, reliablescore,
463 selectBestCands(scip, cands, candsols, ncands, 0.0, inferenceweight, cutoffweight, reliablescore,
466 /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and
507 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, conflict=%g cutoff=%g, inference=%g)\n",
508 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
510 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
515 SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) );
542 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
574 /* check if the weighted sum between the average inferences and conflict score should be used */
586 bestvaluescore = getValueScore(cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir);
588 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
592 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
609 valuescore = getValueScore(cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir);
612 evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir);
615 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
619 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
622 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
626 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
654 /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be
660 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
664 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
673 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
674 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
675 bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/
676 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
728 SCIPdebugMsg(scip, "branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint);
828 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) );
834 branchruledata->useweightedsum, result, branchruledata->conflictprio, branchruledata->cutoffprio) );
881 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
897 &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
901 &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
static void checkValueScore(SCIP_Real value, SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *bestscore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
Definition: branch_inference.c:212
SCIP_RETCODE SCIPincludeBranchruleInference(SCIP *scip)
Definition: branch_inference.c:870
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1840
static SCIP_RETCODE performBranchingSol(SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result, int conflictprio, int cutoffprio)
Definition: branch_inference.c:394
public methods for SCIP parameter handling
public methods for branching and inference history structure
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip_var.c:9787
Definition: struct_scip.h:59
public methods for memory management
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4843
SCIP_VALUEHISTORY * SCIPvarGetValuehistory(SCIP_VAR *var)
Definition: var.c:18352
Definition: struct_var.h:198
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
static SCIP_DECL_BRANCHCOPY(branchCopyInference)
Definition: branch_inference.c:752
static void selectBestCands(SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_VAR **bestcands, int *nbestcands)
Definition: branch_inference.c:340
public methods for problem variables
SCIP_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:520
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:107
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4887
static void evaluateValueCand(SCIP_VAR *cand, SCIP_Real score, SCIP_Real branchpoint, SCIP_BRANCHDIR branchdir, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestbranchpoint, SCIP_BRANCHDIR *bestbranchdir)
Definition: branch_inference.c:85
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:502
public methods for SCIP variables
static SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
Definition: branch_inference.c:814
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, 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: scip_param.c:74
Definition: struct_history.h:54
Definition: struct_tree.h:132
public methods for numerical tolerances
static SCIP_Real getAggrScore(SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore)
Definition: branch_inference.c:254
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
static void evaluateAggrCand(SCIP *scip, SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval, SCIP_VAR **bestcands, int *nbestcands)
Definition: branch_inference.c:139
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:351
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
Definition: type_result.h:35
static SCIP_DECL_BRANCHFREE(branchFreeInference)
Definition: branch_inference.c:766
Definition: struct_history.h:36
Definition: type_retcode.h:33
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1117
Definition: type_result.h:42
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
Definition: struct_branch.h:69
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1850
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:938
SCIP_Real SCIPhistoryGetCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:662
Definition: type_history.h:34
public methods for branching rule plugins and branching
static SCIP_Real getValueScore(SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
Definition: branch_inference.c:285
Definition: type_history.h:35
SCIP_Real * SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:371
static SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
Definition: branch_inference.c:780
public methods for message output
SCIP_HISTORY ** SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:361
static void tiebreakAggrCand(SCIP_VAR **bestcands, int nbestcands)
Definition: branch_inference.c:173
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1962
inference history branching rule
public methods for message handling
static SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
Definition: branch_inference.c:841
Definition: type_result.h:45
static SCIP_RETCODE performBranchingNoSol(SCIP *scip, SCIP_VAR **cands, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result)
Definition: branch_inference.c:534
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9470
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, 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: scip_param.c:130
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9238