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? */
74 SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */
75 SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */
78 /** evaluate the given candidate with the given score against the currently best know candidate */
88 SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */
108 /* the candidate has the same score as the best known candidate; therefore we use a second and third
111 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
113 * - if the absolute values of the objective coefficient are equal the variable index is used to define a
116 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
117 * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
119 * starting a probing mode might already change the order of these arrays. To be independent of that
120 * the selection should be unique. Otherwise, to selection process can get influenced by starting a
123 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
132 /** evaluate the given candidate with the given score against the currently best know candidate */
159 /* the candidate has the same score as the best known candidate; therefore we use a second and third
162 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
164 * - if the absolute values of the objective coefficient are equal the variable index is used to define a
167 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
168 * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
170 * starting a probing mode might already change the order of these arrays. To be independent of that
171 * the selection should be unique. Otherwise, to selection process can get influenced by starting a
174 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
182 /** check if the score for the given domain value and variable domain value is better than the current best know one */
193 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
203 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
209 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
224 /** return an aggregated score for the given variable using the conflict score and cutoff score */
241 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
247 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
255 /** return an aggregated score for the given variable using the conflict score and cutoff score */
263 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
301 checkValueScore(value, histories[v], SCIP_BRANCHDIR_DOWNWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
304 checkValueScore(value, histories[v], SCIP_BRANCHDIR_UPWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
323 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
348 /* check if the weighted sum between the average inferences and conflict score should be used */
362 bestvaluescore = getValueScore(cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir);
364 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
371 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
391 valuescore = getValueScore(cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir);
394 evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir);
397 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
404 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
407 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
445 /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be
451 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
461 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
462 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
463 bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/
464 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
470 SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) );
520 SCIPdebugMsg(scip, "branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint);
621 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) );
674 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
690 &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
694 &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
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:184
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4847
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip_var.c:9723
public methods for SCIP parameter handling
public methods for branching and inference history structure
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
Definition: struct_scip.h:59
public methods for memory management
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
SCIP_EXPORT SCIP_VALUEHISTORY * SCIPvarGetValuehistory(SCIP_VAR *var)
Definition: var.c:18104
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
Definition: struct_var.h:198
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:545
public methods for problem variables
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_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1117
SCIP_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:520
public methods for branching rules
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:80
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
public methods for SCIP variables
static SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
Definition: branch_inference.c:607
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:226
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9174
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:351
Definition: type_result.h:35
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_EXPORT int SCIPvarGetBranchPriority(SCIP_VAR *var)
Definition: var.c:17834
static SCIP_DECL_BRANCHFREE(branchFreeInference)
Definition: branch_inference.c:559
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
Definition: struct_history.h:36
Definition: type_retcode.h:33
Definition: type_result.h:42
SCIP_RETCODE SCIPincludeBranchruleInference(SCIP *scip)
Definition: branch_inference.c:663
Definition: struct_branch.h:69
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
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_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:257
Definition: type_history.h:35
SCIP_Real * SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:371
static SCIP_RETCODE performBranching(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)
Definition: branch_inference.c:314
static SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
Definition: branch_inference.c:573
public methods for message output
SCIP_HISTORY ** SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:361
static void evaluateAggrCand(SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval)
Definition: branch_inference.c:134
inference history branching rule
public methods for message handling
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 SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
Definition: branch_inference.c:634
Definition: type_result.h:45
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9406
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4891
Definition: objbenders.h:33
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859