probability based branching rule based on an article by J. Pryor and J.W. Chinneck
The distribution branching rule selects a variable based on its impact on row activity distributions. More formally, let \( a(x) = a_1 x_1 + \dots + a_n x_n \leq b \) be a row of the LP. Let further \( l_i, u_i \in R\) denote the (finite) lower and upper bound, respectively, of the \( i \)-th variable \(x_i\). Viewing every variable \(x_i \) as (continuously) uniformly distributed within its bounds, we can approximately understand the row activity \(a(x)\) as a Gaussian random variate with mean value \( \mu = E[a(x)] = \sum_i a_i\frac{l_i + u_i}{2}\) and variance \( \sigma^2 = \sum_i a_i^2 \sigma_i^2 \), with \( \sigma_i^2 = \frac{(u_i - l_i)^2}{12}\) for continuous and \( \sigma_i^2 = \frac{(u_i - l_i + 1)^2 - 1}{12}\) for discrete variables. With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution of the standard normal distribution: \( P(a(x) \leq b) = \Phi(\frac{b - \mu}{\sigma})\).
The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering the variable contribution to the sums described above. In order to keep the tree size small, variables are preferred which decrease the probability to satisfy a row because it is more likely to create infeasible subproblems.
The selection of the branching variable is subject to the parameter scoreparam
. For both branching directions, an individual score is calculated. Available options for scoring methods are:
If the parameter usescipscore
is set to TRUE, a single branching score is calculated from the respective up and down scores as defined by the SCIP branching score function (see advanced branching parameter scorefunc
), otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned higher branching priority.
The original idea of probability based branching schemes appeared in:
J. Pryor and J.W. Chinneck:
Faster Integer-Feasibility in Mixed-Integer Linear Programs by Branching to Force Change
Computers and Operations Research, vol. 38, 2011, p. 1143–1152
(Paper: PDF).
Definition in file branch_distribution.c.
#include "scip/branch_distribution.h"
#include "scip/pub_branch.h"
#include "scip/pub_event.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_message.h"
#include "scip/scip_mem.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include <string.h>
#include <math.h>
Go to the source code of this file.
Macros | |
#define | BRANCHRULE_NAME "distribution" |
#define | BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities" |
#define | BRANCHRULE_PRIORITY 0 |
#define | BRANCHRULE_MAXDEPTH -1 |
#define | BRANCHRULE_MAXBOUNDDIST 1.0 |
#define | SCOREPARAM_VALUES "dhlvw" |
#define | DEFAULT_SCOREPARAM 'v' |
#define | DEFAULT_PRIORITY 2.0 |
#define | DEFAULT_ONLYACTIVEROWS FALSE |
#define | DEFAULT_USEWEIGHTEDSCORE FALSE |
#define | EVENTHDLR_NAME "eventhdlr_distribution" |
#define | EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED |
#define BRANCHRULE_NAME "distribution" |
Definition at line 93 of file branch_distribution.c.
#define BRANCHRULE_DESC "branching rule based on variable influence on cumulative normal distribution of row activities" |
Definition at line 94 of file branch_distribution.c.
#define BRANCHRULE_PRIORITY 0 |
Definition at line 95 of file branch_distribution.c.
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 96 of file branch_distribution.c.
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 97 of file branch_distribution.c.
#define SCOREPARAM_VALUES "dhlvw" |
Definition at line 99 of file branch_distribution.c.
Referenced by SCIP_DECL_HEUREXEC(), and SCIPincludeBranchruleDistribution().
#define DEFAULT_SCOREPARAM 'v' |
Definition at line 100 of file branch_distribution.c.
Referenced by SCIPincludeBranchruleDistribution(), and SCIPincludeHeurDistributiondiving().
#define DEFAULT_PRIORITY 2.0 |
Definition at line 101 of file branch_distribution.c.
Referenced by SCIP_DECL_BRANCHEXECLP().
#define DEFAULT_ONLYACTIVEROWS FALSE |
should only rows which are active at the current node be considered?
Definition at line 102 of file branch_distribution.c.
Referenced by SCIPincludeBranchruleDistribution(), and SCIPincludeSepaCGMIP().
#define DEFAULT_USEWEIGHTEDSCORE FALSE |
should the branching score weigh up- and down-scores of a variable
Definition at line 103 of file branch_distribution.c.
Referenced by SCIPincludeBranchruleDistribution().
#define EVENTHDLR_NAME "eventhdlr_distribution" |
event handler name
Definition at line 106 of file branch_distribution.c.
Referenced by COLORprobAddVarForStableSet(), executeLNSHeuristic(), getNNodesBelowIncumbent(), getNRank1Nodes(), includeEventHdlrSync(), SCIP_DECL_DISPOUTPUT(), SCIP_DECL_EVENTCOPY(), SCIP_DECL_EVENTCOPY(), SCIP_DECL_EVENTCOPY(), SCIP_DECL_EVENTCOPY(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXIT(), SCIP_DECL_EVENTEXITSOL(), SCIP_DECL_EVENTEXITSOL(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTFREE(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINIT(), SCIP_DECL_EVENTINITSOL(), SCIP_DECL_EVENTINITSOL(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIP_DECL_TABLEOUTPUT(), SCIPactivateShadowTree(), SCIPapplyProximity(), SCIPconflictstoreCreate(), SCIPcreateProbColoring(), SCIPeventGlobalbndClearBoundChanges(), SCIPeventGlobalbndDisableBoundStorage(), SCIPeventGlobalbndEnableBoundStorage(), SCIPeventGlobalbndGetBoundChanges(), SCIPgetShadowTree(), SCIPgetTreesizeEstimation(), SCIPincludeBranchruleDistribution(), SCIPincludeConshdlrAnd(), SCIPincludeConshdlrBounddisjunction(), SCIPincludeConshdlrCardinality(), SCIPincludeConshdlrCumulative(), SCIPincludeConshdlrKnapsack(), SCIPincludeConshdlrLinear(), SCIPincludeConshdlrLinking(), SCIPincludeConshdlrLogicor(), SCIPincludeConshdlrOr(), SCIPincludeConshdlrRpa(), SCIPincludeConshdlrSetppc(), SCIPincludeConshdlrSOS1(), SCIPincludeConshdlrSOS2(), SCIPincludeConshdlrVarbound(), SCIPincludeConshdlrXor(), SCIPincludeEventHdlrBestsol(), SCIPincludeEventHdlrBoundwriting(), SCIPincludeEventHdlrEstim(), SCIPincludeEventHdlrGlobalbnd(), SCIPincludeEventHdlrLPsol(), SCIPincludeEventHdlrNewsol(), SCIPincludeEventHdlrShadowTree(), SCIPincludeEventHdlrSofttimelimit(), SCIPincludeEventHdlrSolvingphase(), SCIPincludeHeurDistributiondiving(), SCIPincludeHeurNlpdiving(), SCIPincludeHeurShiftandpropagate(), SCIPincludeOrbitopalReduction(), SCIPincludePropGenvbounds(), SCIPincludePropPseudoobj(), SCIPincludePropVbounds(), SCIPincludeSepaIntobj(), SCIPnlpCreate(), SCIPnlpInclude(), SCIPprobdataCreate(), SCIPreoptCreate(), setupAndSolve(), setupAndSolve(), setupAndSolveSubscip(), setupAndSolveSubscipCrossover(), setupAndSolveSubscipLocalbranching(), setupAndSolveSubscipTrustregion(), solveSubscipLpface(), wrapperDins(), and wrapperRins().
#define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED |
the event tyoe to be handled by this event handler
Definition at line 107 of file branch_distribution.c.
Referenced by branchruledataEnsureArraySize(), heurdataEnsureArraySize(), heurdataFreeArrays(), and SCIP_DECL_BRANCHEXITSOL().
|
static |
ensure that maxindex + 1 rows can be represented in data arrays; memory gets reallocated with 10% extra space to save some time for future allocations
scip | SCIP data structure |
branchruledata | branchruledata |
maxindex | row index at hand (size must be at least this large) |
Definition at line 148 of file branch_distribution.c.
References assert(), EVENT_DISTRIBUTION, NULL, nvars, r, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallocBlockMemoryArray, SCIPcatchVarEvent(), SCIPfeasCeil(), SCIPgetNVars(), SCIPgetStage(), SCIPgetVars(), SCIPreallocBlockMemoryArray, SCIPvarGetProbindex(), SCIPvarIsActive(), and vars.
Referenced by calcBranchScore(), SCIP_DECL_BRANCHEXECLP(), and varProcessBoundChanges().
|
static |
scip | SCIP data structure |
branchruledata | branchrule data |
var | the variable to update current bounds |
Definition at line 236 of file branch_distribution.c.
References assert(), NULL, SCIP_Real, SCIPisFeasLE(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), and var.
Referenced by rowCalculateGauss(), SCIP_DECL_BRANCHEXECLP(), and varProcessBoundChanges().
|
static |
calculates the initial mean and variance of the row activity normal distribution.
The mean value \( \mu \) is given by \( \mu = \sum_i=1^n c_i * (lb_i +ub_i) / 2 \) where \(n \) is the number of variables, and \( c_i, lb_i, ub_i \) are the variable coefficient and bounds, respectively. With the same notation, the variance \( \sigma^2 \) is given by \( \sigma^2 = \sum_i=1^n c_i^2 * \sigma^2_i \), with the variance being \( \sigma^2_i = ((ub_i - lb_i + 1)^2 - 1) / 12 \) for integer variables and \( \sigma^2_i = (ub_i - lb_i)^2 / 12 \) for continuous variables.
scip | SCIP data structure |
branchruledata | the branching rule data |
row | the row for which the gaussian normal distribution has to be calculated |
mu | pointer to store the mean value of the gaussian normal distribution |
sigma2 | pointer to store the variance value of the gaussian normal distribution |
rowinfinitiesdown | pointer to store the number of variables with infinite bounds to DECREASE activity |
rowinfinitiesup | pointer to store the number of variables with infinite bounds to INCREASE activity |
Definition at line 437 of file branch_distribution.c.
References assert(), branchruledataUpdateCurrentBounds(), c, NULL, SCIP_INVALID, SCIP_Real, SCIPcolGetVar(), SCIPdebug, SCIPdebugMsg, SCIPisFeasLE(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPvarCalcDistributionParameters(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbLocal(), and SQR.
Referenced by calcBranchScore().
|
static |
calculate the branching score of a variable, depending on the chosen score parameter
scip | current SCIP |
branchruledata | branch rule data |
var | candidate variable |
lpsolval | current fractional LP-relaxation solution value |
upscore | pointer to store the variable score when branching on it in upward direction |
downscore | pointer to store the variable score when branching on it in downward direction |
scoreparam | the score parameter of this branching rule |
Definition at line 620 of file branch_distribution.c.
References assert(), branchruledataEnsureArraySize(), i, MAX, NULL, rowCalculateGauss(), SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetRowLPFeasibility(), SCIPisFeasLT(), SCIPisInfinity(), SCIPisIntegral(), SCIPisNegative(), SCIPisSumPositive(), SCIProwCalcProbability(), SCIProwGetIndex(), SCIProwGetName(), SCIPupdateDistributionScore(), SCIPvarCalcDistributionParameters(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbLocal(), SQR, and var.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
free branchrule data
scip | SCIP data structure |
branchruledata | branching rule data |
Definition at line 813 of file branch_distribution.c.
References assert(), NULL, and SCIPfreeBlockMemoryArray.
Referenced by SCIP_DECL_BRANCHEXITSOL(), and SCIP_DECL_BRANCHFREE().
|
static |
add variable to the bound change event queue; skipped if variable is already in there, or if variable has no row currently watched
branchruledata | branchrule data |
var | the variable whose bound changes need to be processed |
Definition at line 842 of file branch_distribution.c.
References assert(), NULL, SCIP_INVALID, SCIPvarGetProbindex(), and var.
Referenced by SCIP_DECL_EVENTEXEC().
|
static |
returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL
branchruledata | branchrule data |
Definition at line 884 of file branch_distribution.c.
References assert(), NULL, SCIPvarGetProbindex(), and var.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
process a variable from the queue of changed variables
scip | SCIP data structure |
branchruledata | branchrule data |
var | the variable whose bound changes need to be processed |
Definition at line 913 of file branch_distribution.c.
References assert(), branchruledataEnsureArraySize(), branchruledataUpdateCurrentBounds(), MAX, NULL, r, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisInfinity(), SCIProwGetIndex(), SCIPvarCalcDistributionParameters(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbLocal(), SQR, and var.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
destructor of event handler to free user data (called when SCIP is exiting)
Definition at line 1040 of file branch_distribution.c.
References assert(), NULL, SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrSetData(), and SCIPfreeBlockMemory.
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 1059 of file branch_distribution.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPincludeBranchruleDistribution().
|
static |
solving process deinitialization method of branching rule (called before branch and bound process data is freed)
Definition at line 1070 of file branch_distribution.c.
References assert(), BRANCHRULE_NAME, branchruledataFreeArrays(), EVENT_DISTRIBUTION, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPdropVarEvent(), SCIPgetNVars(), SCIPgetVars(), and vars.
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 1105 of file branch_distribution.c.
References assert(), BRANCHRULE_NAME, branchruledataFreeArrays(), NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchruleSetData(), and SCIPfreeBlockMemory.
|
static |
branching execution method for fractional LP solutions
Definition at line 1125 of file branch_distribution.c.
References assert(), bestcand, BRANCHRULE_NAME, branchruledataEnsureArraySize(), branchruledataPopBoundChangeVar(), branchruledataUpdateCurrentBounds(), c, calcBranchScore(), DEFAULT_PRIORITY, lpcands, lpcandssol, nlpcands, nlprows, NULL, result, SCIP_BRANCHDIR_AUTO, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchVar(), SCIPchgChildPrio(), SCIPdebugMsg, SCIPgetBranchScore(), SCIPgetLPBranchCands(), SCIPgetNActivePricers(), SCIPgetNLPRows(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetSol(), SCIPvarGetUbLocal(), TRUE, and varProcessBoundChanges().
|
static |
event execution method of distribution branching which handles bound change events of variables
Definition at line 1303 of file branch_distribution.c.
References assert(), branchruledataAddBoundChangeVar(), NULL, SCIP_OKAY, SCIPeventGetVar(), SCIPeventhdlrGetData(), and var.