69#define _USE_MATH_DEFINES
93#define BRANCHRULE_NAME "distribution"
94#define BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities"
95#define BRANCHRULE_PRIORITY 0
96#define BRANCHRULE_MAXDEPTH -1
97#define BRANCHRULE_MAXBOUNDDIST 1.0
99#define SCOREPARAM_VALUES "dhlvw"
100#define DEFAULT_SCOREPARAM 'v'
101#define DEFAULT_PRIORITY 2.0
102#define DEFAULT_ONLYACTIVEROWS FALSE
103#define DEFAULT_USEWEIGHTEDSCORE FALSE
106#define EVENTHDLR_NAME "eventhdlr_distribution"
107#define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED
114struct SCIP_BranchruleData
119 SCIP_Real* rowvariances;
120 SCIP_Real* currentubs;
121 SCIP_Real* currentlbs;
122 int* rowinfinitiesdown;
124 int* rowinfinitiesup;
132 SCIP_Bool onlyactiverows;
133 SCIP_Bool usescipscore;
136struct SCIP_EventhdlrData
164 assert(branchruledata->memsize >= 0);
167 if( branchruledata->memsize == 0 )
192 branchruledata->varpossmemsize =
nvars;
193 branchruledata->nupdatedvars = 0;
196 for( v = 0; v <
nvars; ++v )
203 assert(branchruledata->varfilterposs[v] >= 0);
205 branchruledata->varposs[v] = -1;
206 branchruledata->updatedvars[v] =
NULL;
220 for(
r = branchruledata->memsize;
r <
newsize; ++
r )
224 branchruledata->rowinfinitiesdown[
r] = 0;
225 branchruledata->rowinfinitiesup[
r] = 0;
229 branchruledata->memsize =
newsize;
375 int rowinfinitiesdown,
419 SCIPdebugMsg(
scip,
" Row %s, mean %g, sigma2 %g, LHS %g, RHS %g has probability %g to be satisfied\n",
443 int* rowinfinitiesdown,
468 *rowinfinitiesdown = 0;
469 *rowinfinitiesup = 0;
515 ++(*rowinfinitiesdown);
517 ++(*rowinfinitiesup);
526 ++(*rowinfinitiesdown);
528 ++(*rowinfinitiesup);
611 SCIPerrorMessage(
" ERROR! No branching scheme selected! Exiting method.\n");
647 SCIP_Bool onlyactiverows;
689 onlyactiverows = branchruledata->onlyactiverows;
704 int rowinfinitiesdown;
726 &branchruledata->rowinfinitiesdown[
rowpos], &branchruledata->rowinfinitiesup[
rowpos]);
732 rowinfinitiesdown = branchruledata->rowinfinitiesdown[
rowpos];
733 rowinfinitiesup = branchruledata->rowinfinitiesdown[
rowpos];
737 rowinfinitiesdown, rowinfinitiesup);
802 SCIPdebugMsg(
scip,
" Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
804 SCIPdebugMsg(
scip,
" --> new variable score: %g (for branching up), %g (for branching down)\n",
818 assert(branchruledata->memsize == 0 || branchruledata->rowmeans !=
NULL);
819 assert(branchruledata->memsize >= 0);
821 if( branchruledata->memsize > 0 )
834 branchruledata->memsize = 0;
858 varpos = branchruledata->varposs[
varindex];
864 assert(branchruledata->updatedvars[varpos] ==
var);
875 assert(branchruledata->varpossmemsize > branchruledata->nupdatedvars);
876 varpos = branchruledata->nupdatedvars;
877 branchruledata->updatedvars[varpos] =
var;
878 branchruledata->varposs[
varindex] = varpos;
879 ++branchruledata->nupdatedvars;
892 assert(branchruledata->nupdatedvars >= 0);
895 if( branchruledata->nupdatedvars == 0 )
898 varpos = branchruledata->nupdatedvars - 1;
899 var = branchruledata->updatedvars[varpos];
905 branchruledata->varposs[
varindex] = -1;
906 branchruledata->nupdatedvars--;
999 branchruledata->rowvariances[
rowpos] =
MAX(0.0, branchruledata->rowvariances[
rowpos]);
1006 ++branchruledata->rowinfinitiesup[
rowpos];
1008 --branchruledata->rowinfinitiesup[
rowpos];
1011 ++branchruledata->rowinfinitiesdown[
rowpos];
1013 --branchruledata->rowinfinitiesdown[
rowpos];
1015 else if(
coeff < 0.0 )
1018 ++branchruledata->rowinfinitiesdown[
rowpos];
1020 --branchruledata->rowinfinitiesdown[
rowpos];
1023 ++branchruledata->rowinfinitiesup[
rowpos];
1025 --branchruledata->rowinfinitiesup[
rowpos];
1027 assert(branchruledata->rowinfinitiesdown[
rowpos] >= 0);
1081 if( branchruledata->varfilterposs !=
NULL)
1091 for( v = 0; v <
nvars; ++v )
1159 if( branchruledata->memsize == 0 )
1176 while( branchruledata->nupdatedvars > 0 )
1233 if( branchruledata->usescipscore )
1313 branchruledata = eventhdlrdata->branchruledata;
1337 branchruledata =
NULL;
1340 branchruledata->memsize = 0;
1341 branchruledata->rowmeans =
NULL;
1342 branchruledata->rowvariances =
NULL;
1343 branchruledata->rowinfinitiesdown =
NULL;
1344 branchruledata->rowinfinitiesup =
NULL;
1345 branchruledata->varfilterposs =
NULL;
1346 branchruledata->currentlbs =
NULL;
1347 branchruledata->currentubs =
NULL;
1350 eventhdlrdata =
NULL;
1352 eventhdlrdata->branchruledata = branchruledata;
1354 branchruledata->eventhdlr =
NULL;
1356 "event handler for dynamic acitivity distribution updating",
1373 "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w') ",
1377 "should only rows which are active at the current node be considered?",
1381 "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