branch_distribution.c
Go to the documentation of this file.
31 * The distribution branching rule selects a variable based on its impact on row activity distributions. More formally,
32 * let \f$ a(x) = a_1 x_1 + \dots + a_n x_n \leq b \f$ be a row of the LP. Let further \f$ l_i, u_i \in R\f$ denote the
34 * Viewing every variable \f$x_i \f$ as (continuously) uniformly distributed within its bounds, we can approximately
35 * understand the row activity \f$a(x)\f$ as a Gaussian random variate with mean value \f$ \mu = E[a(x)] = \sum_i a_i\frac{l_i + u_i}{2}\f$
36 * and variance \f$ \sigma^2 = \sum_i a_i^2 \sigma_i^2 \f$, with \f$ \sigma_i^2 = \frac{(u_i - l_i)^2}{12}\f$ for
38 * With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution
41 * The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering
46 * The selection of the branching variable is subject to the parameter @p scoreparam. For both branching directions,
48 * - @b d: select a branching variable with largest difference in satisfaction probability after branching
51 * - @b v: highest number of votes for lowering row probability for all rows a variable appears in.
52 * - @b w: highest number of votes for increasing row probability for all rows a variable appears in.
54 * If the parameter @p usescipscore is set to @a TRUE, a single branching score is calculated from the respective
55 * up and down scores as defined by the SCIP branching score function (see advanced branching parameter @p scorefunc),
56 * otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned
67/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
94#define BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities"
102#define DEFAULT_ONLYACTIVEROWS FALSE /**< should only rows which are active at the current node be considered? */
103#define DEFAULT_USEWEIGHTEDSCORE FALSE /**< should the branching score weigh up- and down-scores of a variable */
107#define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED /**< the event tyoe to be handled by this event handler */
122 int* rowinfinitiesdown; /**< count the number of variables with infinite bounds which allow for always
124 int* rowinfinitiesup; /**< count the number of variables with infinite bounds which allow for always
132 SCIP_Bool onlyactiverows; /**< should only rows which are active at the current node be considered? */
138 SCIP_BRANCHRULEDATA* branchruledata; /**< the branching rule data to access distribution arrays */
145/** ensure that maxindex + 1 rows can be represented in data arrays; memory gets reallocated with 10% extra space
202 SCIP_CALL( SCIPcatchVarEvent(scip, vars[v], EVENT_DISTRIBUTION, branchruledata->eventhdlr, NULL, &(branchruledata->varfilterposs[v])) );
213 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesdown, branchruledata->memsize, newsize) );
214 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowinfinitiesup, branchruledata->memsize, newsize) );
215 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowmeans, branchruledata->memsize, newsize) );
216 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->rowvariances, branchruledata->memsize, newsize) );
219 /* loop over extended arrays and invalidate data to trigger initialization of this row when necessary */
259/** calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments.
288 /* if the variable is continuous, we assume a continuous uniform distribution, otherwise a discrete one */
300/** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
333 /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
336 SCIPdebugMsg(scip, " Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
338 /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate
339 * the normvalue and use the oddness of the SCIPerf()-function; special treatment for values close to zero.
367 * For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')),
375 int rowinfinitiesdown, /**< the number of variables with infinite bounds to DECREASE activity */
391 /* use the cumulative distribution if the row contains no variable to repair every infeasibility */
395 /* use the cumulative distribution if the row contains no variable to repair every infeasibility
404 /* use centeredness measure for equations; for inequalities, the minimum of the two probabilities is the
419 SCIPdebugMsg(scip, " Row %s, mean %g, sigma2 %g, LHS %g, RHS %g has probability %g to be satisfied\n",
430 * \f$n \f$ is the number of variables, and \f$ c_i, lb_i, ub_i \f$ are the variable coefficient and
442 SCIP_Real* sigma2, /**< pointer to store the variance value of the gaussian normal distribution */
443 int* rowinfinitiesdown, /**< pointer to store the number of variables with infinite bounds to DECREASE activity */
444 int* rowinfinitiesup /**< pointer to store the number of variables with infinite bounds to INCREASE activity */
494 assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
511 /* an infinite upper bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
520 /* an infinite lower bound gives the row an infinite maximum activity or minimum activity, if the coefficient is
531 SCIPvarCalcDistributionParameters(scip, colvarlb, colvarub, SCIPvarGetType(colvar), &varmean, &varvariance);
533 /* actual values are updated; the contribution of the variable to mu is the arithmetic mean of its bounds */
536 /* the variance contribution of a variable is c^2 * (u - l)^2 / 12.0 for continuous and c^2 * ((u - l + 1)^2 - 1) / 12.0 for integer */
544 SCIPdebugMsg(scip, " Row %s has a mean value of %g at a sigma2 of %g \n", SCIProwGetName(row), *mu, *sigma2);
547/** update the up- and downscore of a single variable after calculating the impact of branching on a
625 SCIP_Real* upscore, /**< pointer to store the variable score when branching on it in upward direction */
626 SCIP_Real* downscore, /**< pointer to store the variable score when branching on it in downward direction */
647 SCIP_Bool onlyactiverows; /* should only rows which are active at the current node be considered? */
670 SCIPvarCalcDistributionParameters(scip, varlb, varub, vartype, ¤tmean, &squaredbounddiff);
683 SCIPvarCalcDistributionParameters(scip, varlb, newub, vartype, &meandown, &squaredbounddiffdown);
725 rowCalculateGauss(scip, branchruledata, row, &branchruledata->rowmeans[rowpos], &branchruledata->rowvariances[rowpos],
742 /* first, get the probability change for the row if the variable is branched on upwards. The probability
766 newrowprobup = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
793 newrowprobdown = SCIProwCalcProbability(scip, row, changedrowmean, changedrowvariance, rowinftiesdownafterbranch,
800 SCIP_CALL( SCIPupdateDistributionScore(scip, currentrowprob, newrowprobup, newrowprobdown, upscore, downscore, scoreparam) );
802 SCIPdebugMsg(scip, " Variable %s changes probability of row %s from %g to %g (branch up) or %g;\n",
838/** add variable to the bound change event queue; skipped if variable is already in there, or if variable has
870 assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID)); /*lint !e777*/
882/** returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL */
935 /* skip event execution if SCIP is in Probing mode because these bound changes will be undone anyway before branching
952 /* skip update if the variable has never been subject of previously calculated row activities */
1068/** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1080 /* drop variable events at the end of branch and bound process (cannot be used after restarts, anyway) */
1093 SCIP_CALL( SCIPdropVarEvent(scip, vars[v], EVENT_DISTRIBUTION, branchruledata->eventhdlr, NULL, branchruledata->varfilterposs[v]) );
1157 /* if branching rule data arrays were not initialized before (usually the first call of the branching execution),
1190 /* invalidate the current row distribution data which is initialized on the fly when looping over the candidates */
1206 /* in debug mode, ensure that all bound process events which occurred in the mean time have been captured
1213 assert((branchruledata->currentlbs[varindex] == SCIP_INVALID) == (branchruledata->currentubs[varindex] == SCIP_INVALID));
1228 /* loop over candidate rows and determine the candidate up- and down- branching score w.r.t. the score parameter */
1232 /* if weighted scoring is enabled, use the branching score method of SCIP to weigh up and down score */
1268 SCIPdebugMsg(scip, " Candidate %s has score down %g and up %g \n", SCIPvarGetName(lpcand), downscore, upscore);
1269 SCIPdebugMsg(scip, " Best candidate: %s, score %g, direction %d\n", SCIPvarGetName(bestcand), bestscore, bestbranchdir);
1275 SCIPdebugMsg(scip, " Branching on variable %s with bounds [%g, %g] and solution value <%g>\n", SCIPvarGetName(bestcand),
1301/** event execution method of distribution branching which handles bound change events of variables */
1316 /* add the variable to the queue of unprocessed variables; method itself ensures that every variable is added at most once */
1362 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH,
1373 "the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w') ",
static SCIP_DECL_BRANCHCOPY(branchCopyDistribution)
Definition: branch_distribution.c:1059
static SCIP_DECL_BRANCHEXECLP(branchExeclpDistribution)
Definition: branch_distribution.c:1125
static SCIP_RETCODE calcBranchScore(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
Definition: branch_distribution.c:620
static SCIP_DECL_EVENTEXEC(eventExecDistribution)
Definition: branch_distribution.c:1303
static SCIP_DECL_BRANCHFREE(branchFreeDistribution)
Definition: branch_distribution.c:1105
static void rowCalculateGauss(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
Definition: branch_distribution.c:437
static SCIP_VAR * branchruledataPopBoundChangeVar(SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_distribution.c:884
static SCIP_RETCODE branchruledataEnsureArraySize(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, int maxindex)
Definition: branch_distribution.c:148
static void branchruledataFreeArrays(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_distribution.c:813
static SCIP_DECL_EVENTFREE(eventFreeDistribution)
Definition: branch_distribution.c:1040
static SCIP_RETCODE varProcessBoundChanges(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
Definition: branch_distribution.c:913
static SCIP_DECL_BRANCHEXITSOL(branchExitsolDistribution)
Definition: branch_distribution.c:1070
static void branchruledataUpdateCurrentBounds(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
Definition: branch_distribution.c:236
static void branchruledataAddBoundChangeVar(SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
Definition: branch_distribution.c:842
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)
Definition: branch_distribution.c:550
SCIP_Real SCIProwCalcProbability(SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
Definition: branch_distribution.c:370
void SCIPvarCalcDistributionParameters(SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
Definition: branch_distribution.c:261
SCIP_Real SCIPcalcCumulativeDistribution(SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
Definition: branch_distribution.c:306
SCIP_RETCODE SCIPincludeBranchruleDistribution(SCIP *scip)
Definition: branch_distribution.c:1328
SCIP_RETCODE SCIPchgChildPrio(SCIP *scip, SCIP_NODE *child, SCIP_Real priority)
Definition: scip_prob.c:3791
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)
Definition: scip_param.c:167
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:57
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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:116
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:233
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:849
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:334
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:344
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:150
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2010
SCIP_Bool SCIPisSumPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:756
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:869
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
Definition: objbenders.h:44
Definition: pqueue.h:38
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
general public methods
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
Definition: struct_branch.h:79
Definition: struct_lp.h:136
Definition: struct_event.h:205
Definition: struct_tree.h:142
Definition: struct_lp.h:202
Definition: struct_var.h:208
Definition: struct_scip.h:70