90#define BRANCHRULE_NAME "distribution"
91#define BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities"
92#define BRANCHRULE_PRIORITY 0
93#define BRANCHRULE_MAXDEPTH -1
94#define BRANCHRULE_MAXBOUNDDIST 1.0
96#define SCOREPARAM_VALUES "dhlvw"
97#define DEFAULT_SCOREPARAM 'v'
98#define DEFAULT_PRIORITY 2.0
99#define SQRTOFTWO 1.4142136
100#define SQUARED(x) ((x) * (x))
101#define DEFAULT_ONLYACTIVEROWS FALSE
102#define DEFAULT_USEWEIGHTEDSCORE FALSE
105#define EVENTHDLR_NAME "eventhdlr_distribution"
106#define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED
113struct SCIP_BranchruleData
118 SCIP_Real* rowvariances;
119 SCIP_Real* currentubs;
120 SCIP_Real* currentlbs;
121 int* rowinfinitiesdown;
123 int* rowinfinitiesup;
131 SCIP_Bool onlyactiverows;
132 SCIP_Bool usescipscore;
135struct SCIP_EventhdlrData
163 assert(branchruledata->memsize >= 0);
166 if( branchruledata->memsize == 0 )
191 branchruledata->varpossmemsize =
nvars;
192 branchruledata->nupdatedvars = 0;
195 for( v = 0; v <
nvars; ++v )
202 assert(branchruledata->varfilterposs[v] >= 0);
204 branchruledata->varposs[v] = -1;
205 branchruledata->updatedvars[v] =
NULL;
219 for(
r = branchruledata->memsize;
r <
newsize; ++
r )
223 branchruledata->rowinfinitiesdown[
r] = 0;
224 branchruledata->rowinfinitiesup[
r] = 0;
228 branchruledata->memsize =
newsize;
374 int rowinfinitiesdown,
418 SCIPdebugMsg(
scip,
" Row %s, mean %g, sigma2 %g, LHS %g, RHS %g has probability %g to be satisfied\n",
442 int* rowinfinitiesdown,
467 *rowinfinitiesdown = 0;
468 *rowinfinitiesup = 0;
514 ++(*rowinfinitiesdown);
516 ++(*rowinfinitiesup);
525 ++(*rowinfinitiesdown);
527 ++(*rowinfinitiesup);
610 SCIPerrorMessage(
" ERROR! No branching scheme selected! Exiting method.\n");
646 SCIP_Bool onlyactiverows;
688 onlyactiverows = branchruledata->onlyactiverows;
703 int rowinfinitiesdown;
725 &branchruledata->rowinfinitiesdown[
rowpos], &branchruledata->rowinfinitiesup[
rowpos]);
731 rowinfinitiesdown = branchruledata->rowinfinitiesdown[
rowpos];
732 rowinfinitiesup = branchruledata->rowinfinitiesdown[
rowpos];
736 rowinfinitiesdown, rowinfinitiesup);
801 SCIPdebugMsg(
scip,
" Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
803 SCIPdebugMsg(
scip,
" --> new variable score: %g (for branching up), %g (for branching down)\n",
817 assert(branchruledata->memsize == 0 || branchruledata->rowmeans !=
NULL);
818 assert(branchruledata->memsize >= 0);
820 if( branchruledata->memsize > 0 )
833 branchruledata->memsize = 0;
857 varpos = branchruledata->varposs[
varindex];
863 assert(branchruledata->updatedvars[varpos] ==
var);
874 assert(branchruledata->varpossmemsize > branchruledata->nupdatedvars);
875 varpos = branchruledata->nupdatedvars;
876 branchruledata->updatedvars[varpos] =
var;
877 branchruledata->varposs[
varindex] = varpos;
878 ++branchruledata->nupdatedvars;
891 assert(branchruledata->nupdatedvars >= 0);
894 if( branchruledata->nupdatedvars == 0 )
897 varpos = branchruledata->nupdatedvars - 1;
898 var = branchruledata->updatedvars[varpos];
904 branchruledata->varposs[
varindex] = -1;
905 branchruledata->nupdatedvars--;
998 branchruledata->rowvariances[
rowpos] =
MAX(0.0, branchruledata->rowvariances[
rowpos]);
1005 ++branchruledata->rowinfinitiesup[
rowpos];
1007 --branchruledata->rowinfinitiesup[
rowpos];
1010 ++branchruledata->rowinfinitiesdown[
rowpos];
1012 --branchruledata->rowinfinitiesdown[
rowpos];
1014 else if(
coeff < 0.0 )
1017 ++branchruledata->rowinfinitiesdown[
rowpos];
1019 --branchruledata->rowinfinitiesdown[
rowpos];
1022 ++branchruledata->rowinfinitiesup[
rowpos];
1024 --branchruledata->rowinfinitiesup[
rowpos];
1026 assert(branchruledata->rowinfinitiesdown[
rowpos] >= 0);
1080 if( branchruledata->varfilterposs !=
NULL)
1090 for( v = 0; v <
nvars; ++v )
1158 if( branchruledata->memsize == 0 )
1175 while( branchruledata->nupdatedvars > 0 )
1232 if( branchruledata->usescipscore )
1312 branchruledata = eventhdlrdata->branchruledata;
1336 branchruledata =
NULL;
1339 branchruledata->memsize = 0;
1340 branchruledata->rowmeans =
NULL;
1341 branchruledata->rowvariances =
NULL;
1342 branchruledata->rowinfinitiesdown =
NULL;
1343 branchruledata->rowinfinitiesup =
NULL;
1344 branchruledata->varfilterposs =
NULL;
1345 branchruledata->currentlbs =
NULL;
1346 branchruledata->currentubs =
NULL;
1349 eventhdlrdata =
NULL;
1351 eventhdlrdata->branchruledata = branchruledata;
1353 branchruledata->eventhdlr =
NULL;
1355 "event handler for dynamic acitivity distribution updating",
1372 "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w') ",
1376 "should only rows which are active at the current node be considered?",
1380 "should the branching score weigh up- and down-scores of a variable",
#define DEFAULT_SCOREPARAM
#define BRANCHRULE_PRIORITY
#define EVENT_DISTRIBUTION
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
#define SCOREPARAM_VALUES
static void rowCalculateGauss(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
static SCIP_VAR * branchruledataPopBoundChangeVar(SCIP_BRANCHRULEDATA *branchruledata)
static SCIP_RETCODE branchruledataEnsureArraySize(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, int maxindex)
static void branchruledataFreeArrays(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
static void branchruledataUpdateCurrentBounds(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define DEFAULT_ONLYACTIVEROWS
static void branchruledataAddBoundChangeVar(SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
#define DEFAULT_USEWEIGHTEDSCORE
probability based branching rule based on an article by J. Pryor and J.W. Chinneck
SCIP_RETCODE SCIPupdateDistributionScore(SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
SCIP_RETCODE SCIPchgChildPrio(SCIP *scip, SCIP_NODE *child, SCIP_Real priority)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, 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 SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
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_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
int SCIPcolGetNNonz(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr,)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
int SCIPgetNLPRows(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNActivePricers(SCIP *scip)
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
const char * SCIProwGetName(SCIP_ROW *row)
int SCIProwGetIndex(SCIP_ROW *row)
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPerf(SCIP_Real x)
assert(minobj< SCIPgetCutoffbound(scip))
public methods for branching rules
public methods for managing events
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
public methods for event handler plugins and event handlers
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
#define SCIP_DECL_BRANCHEXECLP(x)
#define SCIP_DECL_BRANCHCOPY(x)
#define SCIP_DECL_BRANCHFREE(x)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
#define SCIP_DECL_BRANCHEXITSOL(x)
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
#define SCIP_DECL_EVENTEXEC(x)
#define SCIP_DECL_EVENTFREE(x)
@ SCIP_BRANCHDIR_DOWNWARDS
enum SCIP_BranchDir SCIP_BRANCHDIR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS
enum SCIP_Vartype SCIP_VARTYPE