Detailed Description

methods and files provided by the default branching rules of SCIP

A detailed description what a branching rule does and how to add a branching rule to SCIP can be found here.

Modules
	Inclusion methods
	methods to include specific branching rules into SCIP

Functions
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_Real	SCIProwCalcProbability (SCIP scip, SCIP_ROW row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)

SCIP_RETCODE	SCIPupdateDistributionScore (SCIP scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real upscore, SCIP_Real *downscore, char scoreparam)

SCIP_RETCODE	SCIPselectVarStrongBranching (SCIP scip, SCIP_VAR lpcands, SCIP_Real lpcandssol, SCIP_Real lpcandsfrac, SCIP_Bool skipdown, SCIP_Bool skipup, int nlpcands, int npriolpcands, int ncomplete, int start, SCIP_Bool allowaddcons, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int bestcand, SCIP_Real bestdown, SCIP_Real bestup, SCIP_Real bestscore, SCIP_Bool bestdownvalid, SCIP_Bool bestupvalid, SCIP_Real provedbound, SCIP_RESULT result)

SCIP_RETCODE	SCIPselectBranchVarPscost (SCIP scip, SCIP_VAR branchcands, SCIP_Real branchcandssol, SCIP_Real branchcandsscore, int nbranchcands, SCIP_VAR var, SCIP_Real brpoint)

SCIP_RETCODE	SCIPexecRelpscostBranching (SCIP scip, SCIP_Bool allowaddcons, SCIP_VAR branchcands, SCIP_Real branchcandssol, SCIP_Real branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT result)

Files
file	branch_allfullstrong.h
	all variables full strong LP branching rule

file	branch_cloud.h
	cloud branching rule

file	branch_distribution.c
	probability based branching rule based on an article by J. Pryor and J.W. Chinneck

file	branch_distribution.h
	probability based branching rule based on an article by J. Pryor and J.W. Chinneck

file	branch_fullstrong.h
	full strong LP branching rule

file	branch_inference.h
	inference history branching rule

file	branch_leastinf.h
	least infeasible LP branching rule

file	branch_mostinf.h
	most infeasible LP branching rule

file	branch_multaggr.h
	fullstrong branching on fractional and multi-aggregated variables

file	branch_nodereopt.h
	nodereopt branching rule

file	branch_pscost.h
	pseudo costs branching rule

file	branch_random.h
	random variable branching rule

file	branch_relpscost.h
	reliable pseudo costs branching rule

file	branch_ryanfoster.c
	Ryan/Foster branching rule.

Function Documentation

◆ SCIPvarCalcDistributionParameters()

void SCIPvarCalcDistributionParameters	(	SCIP *	scip,
		SCIP_Real	varlb,
		SCIP_Real	varub,
		SCIP_VARTYPE	vartype,
		SCIP_Real *	mean,
		SCIP_Real *	variance
	)

calculate the variable's distribution parameters (mean and variance) for the bounds specified in the arguments. special treatment of infinite bounds necessary

Parameters

scip	SCIP data structure
varlb	variable lower bound
varub	variable upper bound
vartype	type of the variable
mean	pointer to store mean value
variance	pointer to store the variance of the variable uniform distribution

Definition at line 235 of file branch_distribution.c.

References NULL, SCIP_VARTYPE_CONTINUOUS, SCIPisInfinity(), SCIPisNegative(), and SQUARED.

Referenced by calcBranchScore(), rowCalculateGauss(), and varProcessBoundChanges().

◆ SCIPcalcCumulativeDistribution()

SCIP_Real SCIPcalcCumulativeDistribution	(	SCIP *	scip,
		SCIP_Real	mean,
		SCIP_Real	variance,
		SCIP_Real	value
	)

calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed random variable x takes a value between -infinity and parameter value.

The distribution is given by the respective mean and deviation. This implementation uses the error function erf().

calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed random variable x takes a value between -infinity and parameter value.

The distribution is given by the respective mean and deviation. This implementation uses the error function SCIPerf().

Parameters

scip	current SCIP
mean	the mean value of the distribution
variance	the square of the deviation of the distribution
value	the upper limit of the calculated distribution integral

Definition at line 280 of file branch_distribution.c.

References SCIP_Real, SCIPdebugMsg, SCIPerf(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisNegative(), sqrt(), and SQRTOFTWO.

Referenced by SCIProwCalcProbability().

◆ SCIProwCalcProbability()

SCIP_Real SCIProwCalcProbability	(	SCIP *	scip,
		SCIP_ROW *	row,
		SCIP_Real	mu,
		SCIP_Real	sigma2,
		int	rowinfinitiesdown,
		int	rowinfinitiesup
	)

calculates the probability of satisfying an LP-row under the assumption of uniformly distributed variable values.

For inequalities, we use the cumulative distribution function of the standard normal distribution PHI(rhs - mu/sqrt(sigma2)) to calculate the probability for a right hand side row with mean activity mu and variance sigma2 to be satisfied. Similarly, 1 - PHI(lhs - mu/sqrt(sigma2)) is the probability to satisfy a left hand side row. For equations (lhs==rhs), we use the centeredness measure p = min(PHI(lhs'), 1-PHI(lhs'))/max(PHI(lhs'), 1 - PHI(lhs')), where lhs' = lhs - mu / sqrt(sigma2).

Parameters

scip	current scip
row	the row
mu	the mean value of the row distribution
sigma2	the variance of the row distribution
rowinfinitiesdown	the number of variables with infinite bounds to DECREASE activity
rowinfinitiesup	the number of variables with infinite bounds to INCREASE activity

Definition at line 344 of file branch_distribution.c.

References MAX, MIN, NULL, SCIP_Real, SCIPcalcCumulativeDistribution(), SCIPdebug, SCIPdebugMsg, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetLhs(), SCIProwGetName(), and SCIProwGetRhs().

Referenced by calcBranchScore().

◆ SCIPupdateDistributionScore()

SCIP_RETCODE SCIPupdateDistributionScore	(	SCIP *	scip,
		SCIP_Real	currentprob,
		SCIP_Real	newprobup,
		SCIP_Real	newprobdown,
		SCIP_Real *	upscore,
		SCIP_Real *	downscore,
		char	scoreparam
	)

update the up- and downscore of a single variable after calculating the impact of branching on a particular row, depending on the chosen score parameter

Parameters

scip	current SCIP pointer
currentprob	the current probability
newprobup	the new probability if branched upwards
newprobdown	the new probability if branched downwards
upscore	pointer to store the new score for branching up
downscore	pointer to store the new score for branching down
scoreparam	parameter to determine the way the score is calculated

Definition at line 524 of file branch_distribution.c.

References NULL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPerrorMessage, SCIPisFeasGE(), SCIPisFeasLE(), SCIPisGT(), and SCIPisLT().

Referenced by calcBranchScore().

◆ SCIPselectVarStrongBranching()

SCIP_RETCODE SCIPselectVarStrongBranching	(	SCIP *	scip,
		SCIP_VAR **	lpcands,
		SCIP_Real *	lpcandssol,
		SCIP_Real *	lpcandsfrac,
		SCIP_Bool *	skipdown,
		SCIP_Bool *	skipup,
		int	nlpcands,
		int	npriolpcands,
		int	ncomplete,
		int *	start,
		SCIP_Bool	allowaddcons,
		int	maxproprounds,
		SCIP_Bool	probingbounds,
		SCIP_Bool	forcestrongbranch,
		int *	bestcand,
		SCIP_Real *	bestdown,
		SCIP_Real *	bestup,
		SCIP_Real *	bestscore,
		SCIP_Bool *	bestdownvalid,
		SCIP_Bool *	bestupvalid,
		SCIP_Real *	provedbound,
		SCIP_RESULT *	result
	)

Selects a variable from a set of candidates by strong branching

Returns: SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.

Note: The variables in the lpcands array must have a fractional value in the current LP solution

Parameters

scip	original SCIP data structure
lpcands	branching candidates
lpcandssol	solution values of the branching candidates
lpcandsfrac	fractional values of the branching candidates
skipdown	should down branchings be skipped?
skipup	should up branchings be skipped?
nlpcands	number of branching candidates
npriolpcands	number of priority branching candidates
ncomplete	number of branching candidates without skip
start	starting index in lpcands
allowaddcons	is the branching rule allowed to add constraints?
maxproprounds	maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)
probingbounds	should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?
forcestrongbranch	should strong branching be applied even if there is just a single candidate?
bestcand	best candidate for branching
bestdown	objective value of the down branch for bestcand
bestup	objective value of the up branch for bestcand
bestscore	score for bestcand
bestdownvalid	is bestdown a valid dual bound for the down branch?
bestupvalid	is bestup a valid dual bound for the up branch?
provedbound	proved dual bound for current subtree
result	result pointer

Definition at line 149 of file branch_fullstrong.c.

References BRANCHRULE_NAME, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DECL_BRANCHEXECLP(), SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPdebug, SCIPdebugMsg, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfindBranchrule(), SCIPfreeBufferArray, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetVars(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchLast(), SCIPgetVarStrongbranchLPAge(), SCIPgetVarStrongbranchNode(), SCIPgetVarStrongbranchWithPropagation(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasZero(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPprintDisplayLine(), SCIPstartStrongbranch(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ SCIPselectBranchVarPscost()

SCIP_RETCODE SCIPselectBranchVarPscost	(	SCIP *	scip,
		SCIP_VAR **	branchcands,
		SCIP_Real *	branchcandssol,
		SCIP_Real *	branchcandsscore,
		int	nbranchcands,
		SCIP_VAR **	var,
		SCIP_Real *	brpoint
	)

selects a branching variable, due to pseudo cost, from the given candidate array and returns this variable together with a branching point

Parameters

scip	SCIP data structure
branchcands	branching candidates
branchcandssol	solution value for the branching candidates
branchcandsscore	array of candidate scores
nbranchcands	number of branching candidates
var	pointer to store the variable to branch on, or NULL if none
brpoint	pointer to store the branching point for the branching variable, will be fractional for a discrete variable

Definition at line 806 of file branch_pscost.c.

References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfindBranchrule(), and selectBranchVar().

◆ SCIPexecRelpscostBranching()

SCIP_RETCODE SCIPexecRelpscostBranching	(	SCIP *	scip,
		SCIP_Bool	allowaddcons,
		SCIP_VAR **	branchcands,
		SCIP_Real *	branchcandssol,
		SCIP_Real *	branchcandsfrac,
		int	nbranchcands,
		SCIP_Bool	executebranching,
		SCIP_RESULT *	result
	)

execution reliability pseudo cost branching with the given branching candidates

Parameters

scip	SCIP data structure
allowaddcons	is the branching rule allowed to add constraints to the current node in order to cut off the current solution instead of creating a branching?
branchcands	branching candidates
branchcandssol	solution value for the branching candidates
branchcandsfrac	fractional part of the branching candidates
nbranchcands	number of branching candidates
executebranching	perform a branching step after probing
result	pointer to the result of the execution

Definition at line 1719 of file branch_relpscost.c.

References BRANCHRULE_NAME, execRelpscost(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfindBranchrule().

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIPincludeBranchruleRelpscost().

SCIP

Detailed Description

Modules

Functions

Files

Function Documentation

◆ SCIPvarCalcDistributionParameters()

◆ SCIPcalcCumulativeDistribution()

◆ SCIProwCalcProbability()

◆ SCIPupdateDistributionScore()

◆ SCIPselectVarStrongBranching()

◆ SCIPselectBranchVarPscost()

◆ SCIPexecRelpscostBranching()