Scippy

SCIP

Solving Constraint Integer Programs

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
scipSCIP data structure
varlbvariable lower bound
varubvariable upper bound
vartypetype of the variable
meanpointer to store mean value
variancepointer 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
scipcurrent SCIP
meanthe mean value of the distribution
variancethe square of the deviation of the distribution
valuethe 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
scipcurrent scip
rowthe row
muthe mean value of the row distribution
sigma2the variance of the row distribution
rowinfinitiesdownthe number of variables with infinite bounds to DECREASE activity
rowinfinitiesupthe 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
scipcurrent SCIP pointer
currentprobthe current probability
newprobupthe new probability if branched upwards
newprobdownthe new probability if branched downwards
upscorepointer to store the new score for branching up
downscorepointer to store the new score for branching down
scoreparamparameter 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
sciporiginal SCIP data structure
lpcandsbranching candidates
lpcandssolsolution values of the branching candidates
lpcandsfracfractional values of the branching candidates
skipdownshould down branchings be skipped?
skipupshould up branchings be skipped?
nlpcandsnumber of branching candidates
npriolpcandsnumber of priority branching candidates
ncompletenumber of branching candidates without skip
startstarting index in lpcands
allowaddconsis the branching rule allowed to add constraints?
maxproproundsmaximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)
probingboundsshould valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?
forcestrongbranchshould strong branching be applied even if there is just a single candidate?
bestcandbest candidate for branching
bestdownobjective value of the down branch for bestcand
bestupobjective value of the up branch for bestcand
bestscorescore for bestcand
bestdownvalidis bestdown a valid dual bound for the down branch?
bestupvalidis bestup a valid dual bound for the up branch?
provedboundproved dual bound for current subtree
resultresult 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
scipSCIP data structure
branchcandsbranching candidates
branchcandssolsolution value for the branching candidates
branchcandsscorearray of candidate scores
nbranchcandsnumber of branching candidates
varpointer to store the variable to branch on, or NULL if none
brpointpointer 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
scipSCIP data structure
allowaddconsis the branching rule allowed to add constraints to the current node in order to cut off the current solution instead of creating a branching?
branchcandsbranching candidates
branchcandssolsolution value for the branching candidates
branchcandsfracfractional part of the branching candidates
nbranchcandsnumber of branching candidates
executebranchingperform a branching step after probing
resultpointer 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().