54#define BRANCHRULE_NAME "inference"
55#define BRANCHRULE_DESC "inference history branching"
56#define BRANCHRULE_PRIORITY 1000
57#define BRANCHRULE_MAXDEPTH -1
58#define BRANCHRULE_MAXBOUNDDIST 1.0
67#define DEFAULT_CONFLICTWEIGHT 1000.0
68#define DEFAULT_CUTOFFWEIGHT 1.0
69#define DEFAULT_INFERENCEWEIGHT 1.0
70#define DEFAULT_RELIABLESCORE 0.001
71#define DEFAULT_FRACTIONALS TRUE
72#define DEFAULT_USEWEIGHTEDSUM TRUE
74#define DEFAULT_CONFLICTPRIO 1
75#define DEFAULT_CUTOFFPRIO 1
80struct SCIP_BranchruleData
106 if( *bestscore < score )
111 *bestbranchpoint = branchpoint;
112 *bestbranchdir = branchdir;
114 else if( (*bestscore) == score )
140 *bestbranchpoint = branchpoint;
141 *bestbranchdir = branchdir;
162 if( *bestscore < score )
175 bestcands[*nbestcands] = cand;
189 for(
c = 0;
c < nbestcands; ++
c )
214 bestcands[0] = bestcands[
c];
243 if( conflictscore < reliablescore )
247 if( cutoffscore < reliablescore )
251 score = conflictweight * conflictscore + cutoffweight * cutoffscore;
253 if( score > *bestscore )
255 (*bestscore) = score;
256 (*branchpoint) = value;
281 if( conflictscore < reliablescore )
285 if( cutoffscore < reliablescore )
289 return (conflictweight * conflictscore + inferenceweight * cutoffscore);
312 if( valuehistory !=
NULL )
323 for( v = 0; v < nvalues; ++v )
367 bestaggrcand = cands[0];
370 bestval = candsols[0];
371 bestcands[0] = cands[0];
375 bestaggrscore =
getAggrScore(
scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
377 for(
c = 1;
c < ncands; ++
c )
389 aggrscore =
getAggrScore(
scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
396 evaluateAggrCand(
scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, nbestcands);
434 if( useweightedsum ==
FALSE )
438 conflictweight = 0.0;
439 inferenceweight = 1.0;
447 if( conflictprio > cutoffprio )
451 bestcands, &nbestcands);
457 selectBestCands(
scip, bestcands, candsols, nbestcands, 0.0, inferenceweight, cutoffweight, reliablescore,
458 bestcands, &nbestcands);
461 else if( conflictprio == cutoffprio )
464 selectBestCands(
scip, cands, candsols, ncands, conflictweight, inferenceweight, cutoffweight, reliablescore,
465 bestcands, &nbestcands);
469 assert(conflictprio < cutoffprio);
472 selectBestCands(
scip, cands, candsols, ncands, 0.0, inferenceweight, cutoffweight, reliablescore,
473 bestcands, &nbestcands);
480 selectBestCands(
scip, bestcands, candsols, nbestcands, conflictweight, 0.0, 0.0, reliablescore,
481 bestcands, &nbestcands);
485 assert(nbestcands == 0 || bestcands[0] !=
NULL);
496 bestaggrcand = bestcands[0];
500 for(
c = 0;
c < ncands; ++
c )
502 if( bestaggrcand == cands[
c] )
504 bestval = candsols[
c];
516 SCIPdebugMsg(
scip,
" -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, conflict=%g cutoff=%g, inference=%g)\n",
526 if( downchild !=
NULL || eqchild !=
NULL || upchild !=
NULL )
570 bestvaluescore = 0.0;
571 bestvaluecand =
NULL;
587 bestaggrcand = cands[0];
588 bestvaluecand = cands[0];
594 bestvaluescore =
getValueScore(cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir);
595 SCIPdebugMsg(
scip,
"current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
600 bestaggrscore =
getAggrScore(
scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
602 for(
c = 1;
c < ncands; ++
c )
617 valuescore =
getValueScore(cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir);
620 evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir);
622 SCIPdebugMsg(
scip,
"current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
627 aggrscore =
getAggrScore(
scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
634 evaluateAggrCand(
scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
641 bestaggrcand = cands[0];
649 for(
c = 1;
c < ncands; ++
c )
665 if( aggrscore < reliablescore )
672 evaluateAggrCand(
scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
681 SCIPdebugMsg(
scip,
" -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
708 downub = bestbranchpoint;
709 uplb = bestbranchpoint + 1.0;
714 downub = bestbranchpoint - 1.0;
715 uplb = bestbranchpoint;
740 if( downchild !=
NULL || eqchild !=
NULL || upchild !=
NULL )
800 if( branchruledata->fractionals )
813 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
814 branchruledata->useweightedsum,
result) );
841 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
842 branchruledata->useweightedsum,
result, branchruledata->conflictprio, branchruledata->cutoffprio) );
866 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
867 branchruledata->useweightedsum,
result) );
903 "branching/inference/conflictweight",
904 "weight in score calculations for conflict score",
907 "branching/inference/inferenceweight",
908 "weight in score calculations for inference score",
911 "branching/inference/cutoffweight",
912 "weight in score calculations for cutoff score",
915 "branching/inference/fractionals",
916 "should branching on LP solution be restricted to the fractional variables?",
919 "branching/inference/useweightedsum",
920 "should a weighted sum of inference, conflict and cutoff weights be used?",
924 "branching/inference/reliablescore",
925 "weight in score calculations for conflict score",
929 "branching/inference/conflictprio",
930 "priority value for using conflict weights in lex. order",
933 "branching/inference/cutoffprio",
934 "priority value for using cutoff weights in lex. order",
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
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)
static void tiebreakAggrCand(SCIP_VAR **bestcands, int nbestcands)
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)
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)
#define DEFAULT_CONFLICTPRIO
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)
#define DEFAULT_INFERENCEWEIGHT
static SCIP_Real getAggrScore(SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore)
#define DEFAULT_USEWEIGHTEDSUM
#define DEFAULT_CONFLICTWEIGHT
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)
#define DEFAULT_FRACTIONALS
#define DEFAULT_CUTOFFWEIGHT
static SCIP_Real getValueScore(SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
#define DEFAULT_RELIABLESCORE
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)
#define DEFAULT_CUTOFFPRIO
inference history branching rule
SCIP_RETCODE SCIPincludeBranchruleInference(SCIP *scip)
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)
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)
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)
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPvarGetIndex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPvarGetBranchPriority(SCIP_VAR *var)
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
SCIP_VALUEHISTORY * SCIPvarGetValuehistory(SCIP_VAR *var)
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
SCIP_HISTORY ** SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY *valuehistory)
SCIP_Real * SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY *valuehistory)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_Real SCIPhistoryGetCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
SCIP_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
public methods for branching rules
public methods for branching and inference history structure
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for SCIP variables
#define SCIP_DECL_BRANCHEXECPS(x)
#define SCIP_DECL_BRANCHEXECLP(x)
#define SCIP_DECL_BRANCHEXECEXT(x)
#define SCIP_DECL_BRANCHCOPY(x)
#define SCIP_DECL_BRANCHFREE(x)
struct SCIP_Branchrule SCIP_BRANCHRULE
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
struct SCIP_History SCIP_HISTORY
@ SCIP_BRANCHDIR_DOWNWARDS
struct SCIP_ValueHistory SCIP_VALUEHISTORY
enum SCIP_BranchDir SCIP_BRANCHDIR
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_Node SCIP_NODE