SCIP
Solving Constraint Integer Programs
branch_relpscost.c File Reference
Detailed Description
reliable pseudo costs branching rule
Definition in file branch_relpscost.c.
#include "blockmemshell/memory.h"#include "scip/branch_relpscost.h"#include "scip/treemodel.h"#include "scip/cons_and.h"#include "scip/pub_branch.h"#include "scip/pub_cons.h"#include "scip/scip_exact.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_sol.h"#include "scip/pub_tree.h"#include "scip/pub_var.h"#include "scip/scip_branch.h"#include "scip/scip_cons.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_nlp.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_randnumgen.h"#include "scip/scip_sol.h"#include "scip/scip_solvingstats.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"#include "scip/prop_symmetry.h"#include "scip/symmetry.h"#include <string.h>Go to the source code of this file.
Functions | |
| static SCIP_RETCODE | initOrbits (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata) |
| static SCIP_RETCODE | filterSymmetricVariables (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR **origbranchcands, SCIP_Real *origbranchcandssol, SCIP_Real *origbranchcandsfrac, int norigbranchcands, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int *branchorbitidx, int *nbranchcands) |
| static SCIP_RETCODE | SCIPupdateVarPseudocostSymmetric (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *branchvar, int *branchorbitidx, int branchvaridx, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight) |
| static SCIP_RETCODE | countNonlinearities (SCIP *scip, int *nlcount, int nlcountsize, int *nlcountmax) |
| static SCIP_RETCODE | branchruledataEnsureNlcount (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata) |
| static SCIP_Real | calcNlscore (SCIP *scip, int *nlcount, int nlcountmax, int probindex) |
| static SCIP_Real | calcScore (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real conflictscore, SCIP_Real avgconflictscore, SCIP_Real conflengthscore, SCIP_Real avgconflengthscore, SCIP_Real inferencescore, SCIP_Real avginferencescore, SCIP_Real cutoffscore, SCIP_Real avgcutoffscore, SCIP_Real gmieffscore, SCIP_Real lastgmieffscore, SCIP_Real pscostscore, SCIP_Real avgpscostscore, SCIP_Real nlscore, SCIP_Real frac, SCIP_Real degeneracyfactor) |
| static SCIP_RETCODE | addBdchg (SCIP *scip, int **bdchginds, SCIP_BOUNDTYPE **bdchgtypes, SCIP_Real **bdchgbounds, int *nbdchgs, int ind, SCIP_BOUNDTYPE type, SCIP_Real bound) |
| static void | freeBdchgs (SCIP *scip, int **bdchginds, SCIP_BOUNDTYPE **bdchgtypes, SCIP_Real **bdchgbounds, int *nbdchgs) |
| static SCIP_RETCODE | applyBdchgs (SCIP *scip, SCIP_VAR **vars, int *bdchginds, SCIP_BOUNDTYPE *bdchgtypes, SCIP_Real *bdchgbounds, int nbdchgs, SCIP_RESULT *result) |
| static SCIP_RETCODE | updateMinMaxMeanGain (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real downgain, SCIP_Real upgain) |
| static SCIP_Real | strongBranchingDepth (SCIP_Real gap, SCIP_Real maxmeangain) |
| static SCIP_Real | strongBranchingTreeSize (SCIP_Real estimatedepth) |
| static SCIP_Real | cdfProbability (SCIP_Real rate, SCIP_Real zeroprob, SCIP_Real proposedgain, SCIP_Real mingain, SCIP_Real logmeangain, SCIP_Real logstdevgain, int distributioncdf) |
| static SCIP_Real | expectedTreeSize (SCIP *scip, SCIP_Real gap, SCIP_Real zeroprob, SCIP_Real currentdepth, SCIP_Real lambda, SCIP_Real mingain, SCIP_Real logmeangain, SCIP_Real logstdevgain, int distributioncdf) |
| static SCIP_Bool | continueStrongBranchingLookahead (SCIP *scip, int candidx, int ninitcands, SCIP_Real lookahead, SCIP_Real maxlookahead, int nbdchgs, int nbdconflicts, int maxbdchgs, SCIP_Longint maxnsblpiterations) |
| static SCIP_Bool | continueStrongBranchingTreeSizeEstimation (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real lookahead, SCIP_Real maxlookahead) |
| static SCIP_Bool | needsStrongBranching (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *branchcand, SCIP_Real branchcandfrac, SCIP_VAR *bestpscand, SCIP_Real bestpscandfrac, SCIP_Real reliable, SCIP_Real relerrorthreshold, SCIP_CONFIDENCELEVEL clevel, SCIP_Bool useancpscost) |
| static SCIP_RETCODE | execRelpscost (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int *branchorbitidx, int nbranchcands, SCIP_Bool executebranch, SCIP_RESULT *result) |
| static | SCIP_DECL_BRANCHCOPY (branchCopyRelpscost) |
| static | SCIP_DECL_BRANCHFREE (branchFreeRelpscost) |
| static | SCIP_DECL_BRANCHINITSOL (branchInitsolRelpscost) |
| static | SCIP_DECL_BRANCHEXITSOL (branchExitsolRelpscost) |
| static | SCIP_DECL_BRANCHEXECLP (branchExeclpRelpscost) |
| SCIP_RETCODE | SCIPincludeBranchruleRelpscost (SCIP *scip) |
| SCIP_RETCODE | SCIPexecRelpscostBranching (SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result) |
Macro Definition Documentation
◆ BRANCHRULE_NAME
| #define BRANCHRULE_NAME "relpscost" |
Definition at line 69 of file branch_relpscost.c.
◆ BRANCHRULE_DESC
| #define BRANCHRULE_DESC "reliability branching on pseudo cost values" |
Definition at line 70 of file branch_relpscost.c.
◆ BRANCHRULE_PRIORITY
| #define BRANCHRULE_PRIORITY 10000 |
Definition at line 71 of file branch_relpscost.c.
◆ BRANCHRULE_MAXDEPTH
| #define BRANCHRULE_MAXDEPTH -1 |
Definition at line 72 of file branch_relpscost.c.
◆ BRANCHRULE_MAXBOUNDDIST
| #define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 73 of file branch_relpscost.c.
◆ DEFAULT_CONFLICTWEIGHT
| #define DEFAULT_CONFLICTWEIGHT 0.01 |
weight in score calculations for conflict score
Definition at line 75 of file branch_relpscost.c.
◆ DEFAULT_CONFLENGTHWEIGHT
| #define DEFAULT_CONFLENGTHWEIGHT 0.0 |
weight in score calculations for conflict length score
Definition at line 76 of file branch_relpscost.c.
◆ DEFAULT_INFERENCEWEIGHT
| #define DEFAULT_INFERENCEWEIGHT 0.0001 |
weight in score calculations for inference score
Definition at line 77 of file branch_relpscost.c.
◆ DEFAULT_CUTOFFWEIGHT
| #define DEFAULT_CUTOFFWEIGHT 0.0001 |
weight in score calculations for cutoff score
Definition at line 78 of file branch_relpscost.c.
◆ DEFAULT_GMIAVGEFFWEIGHT
| #define DEFAULT_GMIAVGEFFWEIGHT 0.0 |
weight in score calculations of average GMI cut normed efficacies
Definition at line 79 of file branch_relpscost.c.
◆ DEFAULT_GMILASTEFFWEIGHT
| #define DEFAULT_GMILASTEFFWEIGHT 0.00001 |
weight in score calculations of last GMI cut normed efficacy
Definition at line 80 of file branch_relpscost.c.
◆ DEFAULT_PSCOSTWEIGHT
| #define DEFAULT_PSCOSTWEIGHT 1.0 |
weight in score calculations for pseudo cost score
Definition at line 81 of file branch_relpscost.c.
◆ DEFAULT_NLSCOREWEIGHT
| #define DEFAULT_NLSCOREWEIGHT 0.1 |
weight in score calculations for nlcount score
Definition at line 82 of file branch_relpscost.c.
◆ DEFAULT_MINRELIABLE
| #define DEFAULT_MINRELIABLE 1.0 |
minimal value for minimum pseudo cost size to regard pseudo cost value as reliable
Definition at line 83 of file branch_relpscost.c.
◆ DEFAULT_MAXRELIABLE
| #define DEFAULT_MAXRELIABLE 5.0 |
maximal value for minimum pseudo cost size to regard pseudo cost value as reliable
Definition at line 84 of file branch_relpscost.c.
◆ DEFAULT_SBITERQUOT
| #define DEFAULT_SBITERQUOT 0.5 |
maximal fraction of strong branching LP iterations compared to normal iterations
Definition at line 85 of file branch_relpscost.c.
◆ DEFAULT_DYNAMICLOOKAHEADQUOT
| #define DEFAULT_DYNAMICLOOKAHEADQUOT 0.6 |
apply dynamic lookahead after this fraction maxlookahead is reached
Definition at line 86 of file branch_relpscost.c.
◆ DEFAULT_SBITEROFS
| #define DEFAULT_SBITEROFS 100000 |
additional number of allowed strong branching LP iterations
Definition at line 87 of file branch_relpscost.c.
◆ DEFAULT_MAXLOOKAHEAD
| #define DEFAULT_MAXLOOKAHEAD 9 |
maximal number of further variables evaluated without better score
Definition at line 88 of file branch_relpscost.c.
◆ DEFAULT_INITCAND
| #define DEFAULT_INITCAND 100 |
maximal number of candidates initialized with strong branching per node
Definition at line 89 of file branch_relpscost.c.
◆ DEFAULT_INITITER
| #define DEFAULT_INITITER 0 |
iteration limit for strong branching initialization of pseudo cost entries (0: auto)
Definition at line 90 of file branch_relpscost.c.
◆ DEFAULT_MAXBDCHGS
| #define DEFAULT_MAXBDCHGS 5 |
maximal number of bound tightenings before the node is reevaluated (-1: unlimited)
Definition at line 91 of file branch_relpscost.c.
◆ DEFAULT_MAXPROPROUNDS
| #define DEFAULT_MAXPROPROUNDS -2 |
maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)
Definition at line 93 of file branch_relpscost.c.
◆ DEFAULT_PROBINGBOUNDS
| #define DEFAULT_PROBINGBOUNDS TRUE |
should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?
Definition at line 95 of file branch_relpscost.c.
◆ DEFAULT_USERELERRORFORRELIABILITY
| #define DEFAULT_USERELERRORFORRELIABILITY FALSE |
should reliability be based on relative errors?
Definition at line 96 of file branch_relpscost.c.
◆ DEFAULT_LOWERRORTOL
| #define DEFAULT_LOWERRORTOL 0.05 |
lowest tolerance beneath which relative errors are reliable
Definition at line 97 of file branch_relpscost.c.
◆ DEFAULT_HIGHERRORTOL
| #define DEFAULT_HIGHERRORTOL 1.0 |
highest tolerance beneath which relative errors are reliable
Definition at line 98 of file branch_relpscost.c.
◆ DEFAULT_USEHYPTESTFORRELIABILITY
| #define DEFAULT_USEHYPTESTFORRELIABILITY FALSE |
should the strong branching decision be based on a hypothesis test?
Definition at line 99 of file branch_relpscost.c.
◆ DEFAULT_USEDYNAMICCONFIDENCE
| #define DEFAULT_USEDYNAMICCONFIDENCE FALSE |
should the confidence level be adjusted dynamically?
Definition at line 100 of file branch_relpscost.c.
◆ DEFAULT_STORESEMIINITCOSTS
| #define DEFAULT_STORESEMIINITCOSTS FALSE |
should strong branching result be considered for pseudo costs if the other direction was infeasible?
Definition at line 101 of file branch_relpscost.c.
◆ DEFAULT_USESBLOCALINFO
| #define DEFAULT_USESBLOCALINFO FALSE |
should the scoring function use only local cutoff and inference information obtained for strong branching candidates?
Definition at line 102 of file branch_relpscost.c.
◆ DEFAULT_CONFIDENCELEVEL
| #define DEFAULT_CONFIDENCELEVEL 2 |
The confidence level for statistical methods, between 0 (Min) and 4 (Max).
Definition at line 103 of file branch_relpscost.c.
◆ DEFAULT_SKIPBADINITCANDS
| #define DEFAULT_SKIPBADINITCANDS TRUE |
should branching rule skip candidates that have a low probability to be better than the best strong-branching or pseudo-candidate?
Definition at line 105 of file branch_relpscost.c.
◆ DEFAULT_STARTRANDSEED
| #define DEFAULT_STARTRANDSEED 5 |
start random seed for random number generation
Definition at line 106 of file branch_relpscost.c.
◆ DEFAULT_DYNAMICLOOKAHEAD
| #define DEFAULT_DYNAMICLOOKAHEAD FALSE |
should we use a dynamic lookahead based on a tree size estimation of further strong branchings?
Definition at line 107 of file branch_relpscost.c.
◆ DEFAULT_MINSAMPLESIZE
| #define DEFAULT_MINSAMPLESIZE 10 |
minimum sample size to estimate the tree size for dynamic lookahead
Definition at line 108 of file branch_relpscost.c.
◆ DEFAULT_DYNAMICLOOKDISTRIBUTION
| #define DEFAULT_DYNAMICLOOKDISTRIBUTION 1 |
which distribution should be used for dynamic lookahead? 0=exponential, 1=Pareto, 2=log-normal
Definition at line 109 of file branch_relpscost.c.
◆ DEFAULT_RANDINITORDER
| #define DEFAULT_RANDINITORDER FALSE |
should slight perturbation of scores be used to break ties in the prior scores?
Definition at line 110 of file branch_relpscost.c.
◆ DEFAULT_USESMALLWEIGHTSITLIM
| #define DEFAULT_USESMALLWEIGHTSITLIM FALSE |
should smaller weights be used for pseudo cost updates after hitting the LP iteration limit?
Definition at line 111 of file branch_relpscost.c.
◆ DEFAULT_DYNAMICWEIGHTS
| #define DEFAULT_DYNAMICWEIGHTS TRUE |
should the weights of the branching rule be adjusted dynamically during solving based infeasible and objective leaf counters?
Definition at line 113 of file branch_relpscost.c.
◆ DEFAULT_DEGENERACYAWARE
| #define DEFAULT_DEGENERACYAWARE 1 |
should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always)
Definition at line 114 of file branch_relpscost.c.
◆ DEFAULT_FILTERCANDSSYM
| #define DEFAULT_FILTERCANDSSYM FALSE |
Use symmetry to filter branching candidates?
Definition at line 117 of file branch_relpscost.c.
◆ DEFAULT_TRANSSYMPSCOST
| #define DEFAULT_TRANSSYMPSCOST FALSE |
Transfer pscost information to symmetric variables if filtering is performed?
Definition at line 118 of file branch_relpscost.c.
◆ EXPONENTIALDISTRIBUTION
| #define EXPONENTIALDISTRIBUTION 0 |
Definition at line 121 of file branch_relpscost.c.
◆ PARETODISTRIBUTION
| #define PARETODISTRIBUTION 1 |
Definition at line 122 of file branch_relpscost.c.
◆ LOGNORMALDISTRIBUTION
| #define LOGNORMALDISTRIBUTION 2 |
Definition at line 123 of file branch_relpscost.c.
◆ GEOMMEANSHIFT
| #define GEOMMEANSHIFT 0.01 |
Definition at line 126 of file branch_relpscost.c.
◆ MAXGAINTHRESHOLD
| #define MAXGAINTHRESHOLD 1e15 |
Definition at line 128 of file branch_relpscost.c.
◆ MINGAINTHRESHOLD
| #define MINGAINTHRESHOLD 1e-5 |
Definition at line 130 of file branch_relpscost.c.
◆ BRANCHRULE_DISCOUNTFACTOR
| #define BRANCHRULE_DISCOUNTFACTOR 0.2 |
default discount factor for discounted pseudo costs.
Definition at line 133 of file branch_relpscost.c.
Function Documentation
◆ initOrbits()
|
static |
initialize orbits
- Parameters
-
scip SCIP data structure branchruledata branching rule data
Definition at line 217 of file branch_relpscost.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcomputeOrbitsComponentsSym(), SCIPgetNVars(), SCIPgetSymmetry(), and TRUE.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ filterSymmetricVariables()
|
static |
filter out symmetric variables from branching variables
- Parameters
-
scip SCIP data structure branchruledata branching rule data origbranchcands original branching candidates origbranchcandssol original solution value for the branching candidates origbranchcandsfrac original fractional part of the branching candidates norigbranchcands original number of branching candidates branchcands branching candidates branchcandssol solution value for the branching candidates branchcandsfrac fractional part of the branching candidates branchorbitidx array of indices of orbit of branching candidates nbranchcands pointer to store number of branching candidates
Definition at line 276 of file branch_relpscost.c.
References NULL, SCIP_OKAY, SCIPdebugMsg, and SCIPhashmapGetImageInt().
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ SCIPupdateVarPseudocostSymmetric()
|
static |
updates the pseudo costs of the given variable and all its symmetric variables
- Parameters
-
scip SCIP data structure branchruledata branching rule data branchvar branching variable candidate branchorbitidx array of orbit indices branchvaridx index of variable in branchorbitidx solvaldelta difference of variable's new LP value - old LP value objdelta difference of new LP's objective value - old LP's objective value weight weight in (0,1] of this update in pseudo cost sum
Definition at line 359 of file branch_relpscost.c.
References NULL, SCIP_Bool, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetLPSolVal(), SCIPboundchgGetNewbound(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPgetBoolParam(), SCIPgetFocusNode(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPupdateVarAncPseudocost(), SCIPupdateVarPseudocost(), SCIPvarIsActive(), and SCIPvarIsIntegral().
Referenced by execRelpscost().
◆ countNonlinearities()
|
static |
! [SnippetCodeStyleDeclaration] counts number of nonlinear constraints in which each variable appears
! [SnippetCodeStyleDeclaration]
! [SnippetCodeStyleIfFor]
! [SnippetCodeStyleIfFor]
- Parameters
-
scip SCIP data structure nlcount pointer to array for storing count values nlcountsize buffer for storing length of nlcount array nlcountmax buffer for storing maximum value in nlcount array
Definition at line 459 of file branch_relpscost.c.
References BMSclearMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPfindConshdlr(), SCIPgetNLPVarsNonlinearity(), SCIPgetNNLPVars(), SCIPgetNVarsAnd(), SCIPgetResultantAnd(), SCIPgetVarsAnd(), SCIPgetVarsData(), SCIPisNLPConstructed(), SCIPvarGetProbindex(), and SCIPvarGetProbvar().
Referenced by branchruledataEnsureNlcount().
◆ branchruledataEnsureNlcount()
|
static |
- Parameters
-
scip SCIP data structure branchruledata branching rule data
Definition at line 545 of file branch_relpscost.c.
References BMSclearMemoryArray, countNonlinearities(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNVars(), and SCIPreallocBlockMemoryArray.
Referenced by execRelpscost().
◆ calcNlscore()
calculates nlscore value between 0 and 1
- Parameters
-
scip SCIP data structure nlcount array to store count values nlcountmax maximum value in nlcount array probindex index of branching candidate
Definition at line 592 of file branch_relpscost.c.
References NULL, SCIP_Real, and SCIPgetNVars().
Referenced by execRelpscost().
◆ calcScore()
|
static |
calculates an overall score value for the given individual score values
- Parameters
-
scip SCIP data structure branchruledata branching rule data conflictscore conflict score of current variable avgconflictscore average conflict score conflengthscore conflict length score of current variable avgconflengthscore average conflict length score inferencescore inference score of current variable avginferencescore average inference score cutoffscore cutoff score of current variable avgcutoffscore average cutoff score gmieffscore normalized-eff of avg GMI cuts from row when var was frac and basic lastgmieffscore last normalized gmieffscore when var was frac and basic pscostscore pscost score of current variable avgpscostscore average pscost score nlscore nonlinear score of current variable between 0 and 1 frac fractional value of variable in current solution degeneracyfactor factor to apply because of degeneracy
Definition at line 619 of file branch_relpscost.c.
References MIN, NULL, SCIP_Real, SCIPfeastol(), SCIPgetNInfeasibleLeaves(), and SCIPgetNObjlimLeaves().
Referenced by execRelpscost().
◆ addBdchg()
|
static |
adds given index and direction to bound change arrays
- Parameters
-
scip SCIP data structure bdchginds pointer to bound change index array bdchgtypes pointer to bound change types array bdchgbounds pointer to bound change new bounds array nbdchgs pointer to number of bound changes ind index to store in bound change index array type type of the bound change to store in bound change type array bound new bound to store in bound change new bounds array
Definition at line 671 of file branch_relpscost.c.
References bound, NULL, SCIP_CALL, SCIP_OKAY, and SCIPreallocBufferArray.
Referenced by execRelpscost().
◆ freeBdchgs()
|
static |
! [SnippetCodeStyleStaticAsserts] frees bound change arrays
! [SnippetCodeStyleStaticAsserts]
- Parameters
-
scip SCIP data structure bdchginds pointer to bound change index array bdchgtypes pointer to bound change types array bdchgbounds pointer to bound change new bounds array nbdchgs pointer to number of bound changes
Definition at line 705 of file branch_relpscost.c.
References NULL, and SCIPfreeBufferArrayNull.
Referenced by execRelpscost().
◆ applyBdchgs()
|
static |
applies bound changes stored in bound change arrays
- Parameters
-
scip SCIP data structure vars problem variables bdchginds bound change index array bdchgtypes bound change types array bdchgbounds bound change new bound array nbdchgs number of bound changes result result pointer
Definition at line 728 of file branch_relpscost.c.
References BRANCHRULE_NAME, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMsg, SCIPfindBranchrule(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by execRelpscost().
◆ updateMinMaxMeanGain()
|
static |
Update the min/max gain, and the mean of all gains computed so far.
This mean is used in the definition of the exponential distribution.
- Parameters
-
scip SCIP data structure branchrule branching rule downgain gain for branching downwards upgain gain for branching upwards
Definition at line 808 of file branch_relpscost.c.
References GEOMMEANSHIFT, MAX, MAXGAINTHRESHOLD, MIN, MINGAINTHRESHOLD, NULL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetData(), SCIPdebugMsg, SCIPisGE(), and SCIPisRelGE().
Referenced by execRelpscost().
◆ strongBranchingDepth()
compute the depth of the tree with the assumption that left and right dual gains are equal
- Parameters
-
gap gap to be closed maxmeangain maximum mean gain of the branching candidates
Definition at line 866 of file branch_relpscost.c.
References MAX, MINGAINTHRESHOLD, and SCIP_Real.
Referenced by continueStrongBranchingTreeSizeEstimation().
◆ strongBranchingTreeSize()
compute the size of the tree with the assumption that left and right dual gains are equal
- Parameters
-
estimatedepth estimated depth of the tree
Definition at line 880 of file branch_relpscost.c.
Referenced by continueStrongBranchingTreeSizeEstimation(), and expectedTreeSize().
◆ cdfProbability()
|
static |
calculate the cumulative distribution function (CDF) value for a mixture of a Dirac at zero and a continuous distribution (depending on distributioncdf)
- Parameters
-
rate rate of the distribution zeroprob probability of zero gain proposedgain proposed gain mingain minimum gain logmeangain logarithm og mean gain logstdevgain logarithm of standard deviation of gain distributioncdf distribution type (PARETODISTRIBUTION, EXPONENTIALDISTRIBUTION, LOGNORMALDISTRIBUTION)
Definition at line 889 of file branch_relpscost.c.
References EXPONENTIALDISTRIBUTION, LOGNORMALDISTRIBUTION, and PARETODISTRIBUTION.
Referenced by expectedTreeSize().
◆ expectedTreeSize()
|
static |
calculate the expected size of a tree with one more iteration of strong branching
- Parameters
-
scip SCIP data structure gap gap to be closed zeroprob probability of zero gain currentdepth current depth of the tree lambda rate of the distribution mingain minimum gain logmeangain logarithm of mean gain logstdevgain logarithm of standard deviation of gain distributioncdf distribution type (PARETODISTRIBUTION, EXPONENTIALDISTRIBUTION, LOGNORMALDISTRIBUTION)
Definition at line 920 of file branch_relpscost.c.
References cdfProbability(), MINGAINTHRESHOLD, SCIP_Real, SCIPdebugMsg, SCIPinfinity(), and strongBranchingTreeSize().
Referenced by continueStrongBranchingTreeSizeEstimation().
◆ continueStrongBranchingLookahead()
|
static |
decide if we continue strong branching based based on lookahead
- Parameters
-
scip SCIP data structure candidx index of the branching candidate ninitcands number of initial candidates lookahead lookahead value maxlookahead maximum lookahead value nbdchgs number of bound changes found nbdconflicts number of bound conflicts found maxbdchgs maximal number of bound tightenings before the node is reevaluated maxnsblpiterations maximal number of strong branching LP iterations
Definition at line 1001 of file branch_relpscost.c.
References SCIPgetNStrongbranchLPIterations().
Referenced by execRelpscost().
◆ continueStrongBranchingTreeSizeEstimation()
|
static |
Decide if we continue strong branching based on the estimation of the tree size given the current gains.
- Parameters
-
scip SCIP data structure branchruledata branching rule data lookahead lookahead value maxlookahead maximum lookahead value
Definition at line 1019 of file branch_relpscost.c.
References expectedTreeSize(), EXPONENTIALDISTRIBUTION, FALSE, LOGNORMALDISTRIBUTION, PARETODISTRIBUTION, SCIP_Real, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetNodeLowerbound(), SCIPgetUpperbound(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), strongBranchingDepth(), strongBranchingTreeSize(), and TRUE.
Referenced by execRelpscost().
◆ needsStrongBranching()
|
static |
determine if strong branching is needed on the given candidate variable
- Parameters
-
scip SCIP data structure branchrule branching rule branchcand branching candidate branchcandfrac fractional part of the branching candidate bestpscand best candidate as per pscost score, must be present if usehyptestforreliability is used bestpscandfrac fractional part of the best candidate as per pscost score, must be present if usehyptestforreliability is used reliable size threshold for reliability relerrorthreshold relative error threshold for reliability clevel confidence level useancpscost check reliability for ancpscost as well
Definition at line 1111 of file branch_relpscost.c.
References FALSE, MIN, NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_Real, SCIPbranchruleGetData(), SCIPgetVarAncPseudocostCountCurrentRun(), SCIPgetVarPseudocostCountCurrentRun(), SCIPisVarPscostRelerrorReliable(), SCIPsignificantVarPscostDifference(), and TRUE.
Referenced by execRelpscost().
◆ execRelpscost()
|
static |
execute reliability pseudo cost branching
- Parameters
-
scip SCIP data structure branchrule branching rule branchcands branching candidates branchcandssol solution value for the branching candidates branchcandsfrac fractional part of the branching candidates branchorbitidx indices of orbit (or NULL) nbranchcands number of branching candidates executebranch execute a branching step or run probing only result pointer to the result of the execution
Definition at line 1174 of file branch_relpscost.c.
References addBdchg(), applyBdchgs(), branchruledataEnsureNlcount(), calcNlscore(), calcScore(), continueStrongBranchingLookahead(), continueStrongBranchingTreeSizeEstimation(), FALSE, freeBdchgs(), MAX, MIN, needsStrongBranching(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_CONFIDENCELEVEL_HIGH, SCIP_CONFIDENCELEVEL_LOW, SCIP_CONFIDENCELEVEL_MAX, SCIP_CONFIDENCELEVEL_MEDIUM, SCIP_CONFIDENCELEVEL_MIN, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_INVALID, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_UNUSED, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchVarVal(), SCIPdebug, SCIPdebugMsg, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfeasFrac(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetAvgConflictlengthScore(), SCIPgetAvgConflictScore(), SCIPgetAvgCutoffScore(), SCIPgetAvgDPseudocostScore(), SCIPgetAvgInferenceScore(), SCIPgetAvgPseudocostScore(), SCIPgetBestSol(), SCIPgetBoolParam(), SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLastStrongbranchLPSolStat(), SCIPgetLocalLowerbound(), SCIPgetLPDualDegeneracy(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodeLPIterations(), SCIPgetNNodes(), SCIPgetNodeLowerbound(), SCIPgetNRootStrongbranchLPIterations(), SCIPgetNStrongbranchLPIterations(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetVarAncPseudocostVal(), SCIPgetVarAvgCutoffScore(), SCIPgetVarAvgGMIScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictlengthScore(), SCIPgetVarConflictScore(), SCIPgetVarDPseudocostScore(), SCIPgetVarLastGMIScore(), SCIPgetVarPseudocostCountCurrentRun(), SCIPgetVarPseudocostCurrentRun(), SCIPgetVarPseudocostScore(), SCIPgetVarPseudocostScoreCurrentRun(), SCIPgetVarPseudocostVal(), SCIPgetVars(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchLast(), SCIPgetVarStrongbranchNode(), SCIPgetVarStrongbranchWithPropagation(), SCIPhasCurrentNodeLP(), SCIPinfinity(), SCIPisExact(), SCIPisFeasIntegral(), SCIPisGE(), SCIPisGT(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisStopped(), SCIPisSumGE(), SCIPisSumGT(), SCIPisZero(), SCIPnodeGetLowerbound(), SCIPpscostThresholdProbabilityTest(), SCIPrandomGetReal(), SCIPsignificantVarPscostDifference(), SCIPsolGetIndex(), SCIPstartStrongbranch(), SCIPtreemodelIsEnabled(), SCIPtreemodelSelectCandidate(), SCIPupdateLocalLowerbound(), SCIPupdateNodeLowerbound(), SCIPupdateVarPseudocostSymmetric(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), SCIPverbMessage(), TRUE, and updateMinMaxMeanGain().
Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIPexecRelpscostBranching().
◆ SCIP_DECL_BRANCHCOPY()
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 2343 of file branch_relpscost.c.
References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleRelpscost().
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 2357 of file branch_relpscost.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), SCIPfreeBlockMemory, and SCIPtreemodelFree().
◆ SCIP_DECL_BRANCHINITSOL()
|
static |
solving process initialization method of branching rule (called when branch and bound process is about to begin)
Definition at line 2375 of file branch_relpscost.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPcreateRandom(), and TRUE.
◆ SCIP_DECL_BRANCHEXITSOL()
|
static |
solving process deinitialization method of branching rule (called before branch and bound process data is freed)
Definition at line 2396 of file branch_relpscost.c.
References FALSE, NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPfreeBlockMemoryArrayNull, and SCIPfreeRandom().
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 2423 of file branch_relpscost.c.
References BRANCHRULE_NAME, execRelpscost(), filterSymmetricVariables(), initOrbits(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPgetLPBranchCands(), SCIPgetLPSolstat(), SCIPgetSubscipDepth(), SCIPinDive(), SCIPinfinity(), SCIPinProbing(), SCIPnodeGetNumber(), and TRUE.