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
158 if( maxindex < branchruledata->memsize )
163 assert(newsize > branchruledata->memsize);
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;
249 assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
255 branchruledata->currentlbs[varindex] = lblocal;
256 branchruledata->currentubs[varindex] = ublocal;
290 *variance =
SQR(varub - varlb);
292 *variance =
SQR(varub - varlb + 1.0) - 1.0;
294 *mean = (varub + varlb) * .5;
321 std = sqrt(variance);
336 SCIPdebugMsg(
scip,
" Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean,
std);
343 else if( normvalue > 0 )
347 erfresult =
SCIPerf(normvalue);
348 return erfresult / 2.0 + 0.5;
354 erfresult =
SCIPerf(-normvalue);
356 return 0.5 - erfresult / 2.0;
375 int rowinfinitiesdown,
379 SCIP_Real rowprobability;
408 SCIP_Real minprobability;
409 SCIP_Real maxprobability;
411 minprobability =
MIN(rhsprob, lhsprob);
412 maxprobability =
MAX(lhsprob, rhsprob);
413 rowprobability = minprobability / maxprobability;
416 rowprobability =
MIN(rhsprob, lhsprob);
419 SCIPdebugMsg(
scip,
" Row %s, mean %g, sigma2 %g, LHS %g, RHS %g has probability %g to be satisfied\n",
424 return rowprobability;
443 int* rowinfinitiesdown,
468 *rowinfinitiesdown = 0;
469 *rowinfinitiesup = 0;
472 for(
c = 0;
c < nrowvals; ++
c )
478 SCIP_Real squarecoeff;
479 SCIP_Real varvariance;
497 if( branchruledata->currentlbs[varindex] ==
SCIP_INVALID )
515 ++(*rowinfinitiesdown);
517 ++(*rowinfinitiesup);
526 ++(*rowinfinitiesdown);
528 ++(*rowinfinitiesup);
534 *mu += colval * varmean;
537 squarecoeff =
SQR(colval);
538 *sigma2 += squarecoeff * varvariance;
552 SCIP_Real currentprob,
554 SCIP_Real newprobdown,
556 SCIP_Real* downscore,
573 *upscore = 1.0 - newprobup;
575 *downscore = 1.0 - newprobdown;
581 *upscore = currentprob - newprobup;
582 if(
SCIPisGT(
scip, currentprob - newprobdown, *downscore) )
583 *downscore = currentprob - newprobdown;
589 *upscore = newprobup;
591 *downscore = newprobdown;
611 SCIPerrorMessage(
" ERROR! No branching scheme selected! Exiting method.\n");
626 SCIP_Real* downscore,
635 SCIP_Real squaredbounddiff;
638 SCIP_Real squaredbounddiffup;
639 SCIP_Real squaredbounddiffdown;
640 SCIP_Real currentmean;
647 SCIP_Bool onlyactiverows;
669 squaredbounddiff = 0.0;
676 squaredbounddiffup = 0.0;
681 squaredbounddiffdown = 0.0;
689 onlyactiverows = branchruledata->onlyactiverows;
692 for(
i = 0;
i < ncolrows; ++
i )
695 SCIP_Real changedrowmean;
697 SCIP_Real rowvariance;
698 SCIP_Real changedrowvariance;
699 SCIP_Real currentrowprob;
700 SCIP_Real newrowprobup;
701 SCIP_Real newrowprobdown;
702 SCIP_Real squaredcoeff;
704 int rowinfinitiesdown;
725 rowCalculateGauss(
scip, branchruledata, row, &branchruledata->rowmeans[rowpos], &branchruledata->rowvariances[rowpos],
726 &branchruledata->rowinfinitiesdown[rowpos], &branchruledata->rowinfinitiesup[rowpos]);
730 rowmean = branchruledata->rowmeans[rowpos];
731 rowvariance = branchruledata->rowvariances[rowpos];
732 rowinfinitiesdown = branchruledata->rowinfinitiesdown[rowpos];
733 rowinfinitiesup = branchruledata->rowinfinitiesdown[rowpos];
737 rowinfinitiesdown, rowinfinitiesup);
740 squaredcoeff =
SQR(rowval);
747 int rowinftiesdownafterbranch;
748 int rowinftiesupafterbranch;
751 changedrowmean = rowmean + rowval * (meanup - currentmean);
752 changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffup - squaredbounddiff);
753 changedrowvariance =
MAX(0.0, changedrowvariance);
755 rowinftiesdownafterbranch = rowinfinitiesdown;
756 rowinftiesupafterbranch = rowinfinitiesup;
760 rowinftiesupafterbranch--;
762 rowinftiesdownafterbranch--;
764 assert(rowinftiesupafterbranch >= 0);
765 assert(rowinftiesdownafterbranch >= 0);
767 rowinftiesupafterbranch);
770 newrowprobup = currentrowprob;
775 int rowinftiesdownafterbranch;
776 int rowinftiesupafterbranch;
778 changedrowmean = rowmean + rowval * (meandown - currentmean);
779 changedrowvariance = rowvariance + squaredcoeff * (squaredbounddiffdown - squaredbounddiff);
780 changedrowvariance =
MAX(0.0, changedrowvariance);
782 rowinftiesdownafterbranch = rowinfinitiesdown;
783 rowinftiesupafterbranch = rowinfinitiesup;
787 rowinftiesupafterbranch -= 1;
789 rowinftiesdownafterbranch -= 1;
791 assert(rowinftiesdownafterbranch >= 0);
792 assert(rowinftiesupafterbranch >= 0);
794 rowinftiesupafterbranch);
797 newrowprobdown = currentrowprob;
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",
805 *upscore, *downscore);
818 assert(branchruledata->memsize == 0 || branchruledata->rowmeans !=
NULL);
819 assert(branchruledata->memsize >= 0);
821 if( branchruledata->memsize > 0 )
834 branchruledata->memsize = 0;
853 assert(-1 <= varindex && varindex < branchruledata->varpossmemsize);
858 varpos = branchruledata->varposs[varindex];
859 assert(varpos < branchruledata->nupdatedvars);
864 assert(branchruledata->updatedvars[varpos] ==
var);
871 if( branchruledata->currentlbs[varindex] ==
SCIP_INVALID )
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];
902 assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
903 assert(varpos == branchruledata->varposs[varindex]);
905 branchruledata->varposs[varindex] = -1;
906 branchruledata->nupdatedvars--;
924 SCIP_Real oldvariance;
925 SCIP_Real newvariance;
949 oldlb = branchruledata->currentlbs[varindex];
950 oldub = branchruledata->currentubs[varindex];
974 for(
r = 0;
r < ncolrows; ++
r )
988 SCIP_Real coeffsquared;
994 coeffsquared =
SQR(coeff);
997 branchruledata->rowmeans[rowpos] += coeff * (newmean - oldmean);
998 branchruledata->rowvariances[rowpos] += coeffsquared * (newvariance - oldvariance);
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);
1028 assert(branchruledata->rowinfinitiesup[rowpos] >= 0);
1081 if( branchruledata->varfilterposs !=
NULL)
1091 for( v = 0; v <
nvars; ++v )
1135 SCIP_Real bestscore;
1159 if( branchruledata->memsize == 0 )
1176 while( branchruledata->nupdatedvars > 0 )
1197 SCIP_Real downscore;
1210 assert(0 <= varindex && varindex < branchruledata->varpossmemsize);
1220 if( branchruledata->currentlbs[varindex] ==
SCIP_INVALID )
1230 &upscore, &downscore, branchruledata->scoreparam) );
1233 if( branchruledata->usescipscore )
1240 if( score > bestscore )
1245 if( upscore > downscore )
1254 if( upscore > bestscore && upscore > downscore )
1256 bestscore = upscore;
1260 else if( downscore > bestscore )
1262 bestscore = downscore;
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",
1357 eventExecDistribution, eventhdlrdata) );
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