SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
reliable pseudo costs branching rule
Definition in file branch_relpscost.c.
#include <assert.h>#include <string.h>#include "scip/branch_relpscost.h"#include "scip/cons_and.h"#include "scip/pub_misc.h"Go to the source code of this file.
Functions | |
| static SCIP_RETCODE | binvarGetActiveProbindex (SCIP *scip, SCIP_VAR *var, int *probindex) |
| 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 pscostscore, SCIP_Real avgpscostscore, SCIP_Real nlscore, SCIP_Real frac) |
| 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 | execRelpscost (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Bool allowaddcons, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, 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_Bool allowaddcons, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result) |
| #define BRANCHRULE_NAME "relpscost" |
Definition at line 32 of file branch_relpscost.c.
Referenced by applyBdchgs(), SCIPexecRelpscostBranching(), and SCIPincludeBranchruleRelpscost().
| #define BRANCHRULE_DESC "reliability branching on pseudo cost values" |
Definition at line 33 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define BRANCHRULE_PRIORITY 10000 |
Definition at line 34 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define BRANCHRULE_MAXDEPTH -1 |
Definition at line 35 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 36 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_CONFLICTWEIGHT 0.01 |
weight in score calculations for conflict score
Definition at line 38 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_CONFLENGTHWEIGHT 0.0 |
weight in score calculations for conflict length score
Definition at line 39 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_INFERENCEWEIGHT 0.0001 |
weight in score calculations for inference score
Definition at line 40 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_CUTOFFWEIGHT 0.0001 |
weight in score calculations for cutoff score
Definition at line 41 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_PSCOSTWEIGHT 1.0 |
weight in score calculations for pseudo cost score
Definition at line 42 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_NLSCOREWEIGHT 0.1 |
weight in score calculations for nlcount score
Definition at line 43 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_MINRELIABLE 1.0 |
minimal value for minimum pseudo cost size to regard pseudo cost value as reliable
Definition at line 44 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_MAXRELIABLE 5.0 |
maximal value for minimum pseudo cost size to regard pseudo cost value as reliable
Definition at line 45 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_SBITERQUOT 0.5 |
maximal fraction of strong branching LP iterations compared to normal iterations
Definition at line 46 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_SBITEROFS 100000 |
additional number of allowed strong branching LP iterations
Definition at line 47 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_MAXLOOKAHEAD 9 |
maximal number of further variables evaluated without better score
Definition at line 48 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_INITCAND 100 |
maximal number of candidates initialized with strong branching per node
Definition at line 49 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_INITITER 0 |
iteration limit for strong branching initialization of pseudo cost entries (0: auto)
Definition at line 50 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_MAXBDCHGS 5 |
maximal number of bound tightenings before the node is reevaluated (-1: unlimited)
Definition at line 51 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #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 52 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_PROBINGBOUNDS TRUE |
should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?
Definition at line 55 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_USERELERRORFORRELIABILITY FALSE |
should reliability be based on relative errors?
Definition at line 58 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_LOWERRORTOL 0.05 |
lowest tolerance beneath which relative errors are reliable
Definition at line 59 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_HIGHERRORTOL 1.0 |
highest tolerance beneath which relative errors are reliable
Definition at line 60 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_USEHYPTESTFORRELIABILITY FALSE |
should the strong branching decision be based on a hypothesis test?
Definition at line 61 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_USEDYNAMICCONFIDENCE FALSE |
should the confidence level be adjusted dynamically?
Definition at line 62 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_STORESEMIINITCOSTS FALSE |
should strong branching result be considered for pseudo costs if the other direction was infeasible?
Definition at line 63 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_USESBLOCALINFO FALSE |
should the scoring function use only local cutoff and inference information obtained for strong branching candidates?
Definition at line 64 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_CONFIDENCELEVEL 2 |
The confidence level for statistical methods, between 0 (Min) and 4 (Max).
Definition at line 65 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #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 66 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_STARTRANDSEED 5 |
start random seed for random number generation
Definition at line 69 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_RANDINITORDER FALSE |
should slight perturbation of scores be used to break ties in the prior scores?
Definition at line 70 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #define DEFAULT_USESMALLWEIGHTSITLIM FALSE |
should smaller weights be used for pseudo cost updates after hitting the LP iteration limit?
Definition at line 71 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
| #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 72 of file branch_relpscost.c.
Referenced by SCIPincludeBranchruleRelpscost().
|
static |
return probindex of variable or corresponding active variable (if negated or aggregated) or -1 (if multiaggregated)
| scip | SCIP data structure |
| var | binary variable |
| probindex | buffer to store probindex |
Definition at line 122 of file branch_relpscost.c.
References countNonlinearities(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_FIXED, SCIPgetBinvarRepresentative(), SCIPvarGetNegationVar(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarIsActive(), SCIPvarIsBinary(), and SCIPvarIsNegated().
Referenced by countNonlinearities().
|
static |
counts number of nonlinear constraints in which each variable appears
| 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 156 of file branch_relpscost.c.
References binvarGetActiveProbindex(), BMSclearMemoryArray, branchruledataEnsureNlcount(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_FIXED, SCIPconshdlrGetConss(), SCIPconshdlrGetNActiveConss(), SCIPfindConshdlr(), SCIPgetNLPVarsNonlinearity(), SCIPgetNNLPVars(), SCIPgetNVarsAnd(), SCIPgetResultantAnd(), SCIPgetVarsAnd(), SCIPgetVarsData(), SCIPisNLPConstructed(), and SCIPvarGetStatus().
Referenced by binvarGetActiveProbindex(), and branchruledataEnsureNlcount().
|
static |
| scip | SCIP data structure |
| branchruledata | branching rule data |
Definition at line 239 of file branch_relpscost.c.
References BMSclearMemoryArray, calcNlscore(), countNonlinearities(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNVars(), and SCIPreallocBlockMemoryArray.
Referenced by countNonlinearities(), and execRelpscost().
calculates nlscore value between 0 and 1
| scip | SCIP data structure |
| nlcount | array to store count values |
| nlcountmax | maximum value in nlcount array |
| probindex | index of branching candidate |
Definition at line 286 of file branch_relpscost.c.
References calcScore(), NULL, SCIP_Real, and SCIPgetNVars().
Referenced by branchruledataEnsureNlcount(), and execRelpscost().
|
static |
calculates an overall score value for the given individual score values
| 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 |
| 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 |
Definition at line 313 of file branch_relpscost.c.
References addBdchg(), MIN, NULL, SCIP_Real, SCIPfeastol(), SCIPgetNInfeasibleLeaves(), and SCIPgetNObjlimLeaves().
Referenced by calcNlscore(), and execRelpscost().
|
static |
adds given index and direction to bound change arrays
| 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 359 of file branch_relpscost.c.
References bound, freeBdchgs(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPreallocBufferArray.
Referenced by calcScore(), and execRelpscost().
|
static |
frees bound change arrays
| 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 392 of file branch_relpscost.c.
References applyBdchgs(), NULL, and SCIPfreeBufferArrayNull.
Referenced by addBdchg(), and execRelpscost().
|
static |
applies bound changes stored in bound change arrays
| 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 413 of file branch_relpscost.c.
References BRANCHRULE_NAME, execRelpscost(), 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(), and freeBdchgs().
|
static |
execute reliability pseudo cost branching
| scip | SCIP data structure |
| branchrule | branching rule |
| 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 |
| executebranch | execute a branching step or run probing only |
| result | pointer to the result of the execution |
Definition at line 490 of file branch_relpscost.c.
References addBdchg(), applyBdchgs(), branchruledataEnsureNlcount(), calcNlscore(), calcScore(), FALSE, freeBdchgs(), MAX, MIN, 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_DECL_BRANCHCOPY(), SCIP_DIDNOTRUN, SCIP_INVALID, SCIP_Longint, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchVarVal(), SCIPdebug, SCIPdebugMsg, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetAvgConflictlengthScore(), SCIPgetAvgConflictScore(), SCIPgetAvgCutoffScore(), SCIPgetAvgInferenceScore(), SCIPgetAvgPseudocostScore(), SCIPgetBestSol(), SCIPgetBranchScore(), SCIPgetCurrentNode(), SCIPgetCutoffbound(), SCIPgetLastStrongbranchLPSolStat(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodeLPIterations(), SCIPgetNNodes(), SCIPgetNodeLowerbound(), SCIPgetNRootStrongbranchLPIterations(), SCIPgetNStrongbranchLPIterations(), SCIPgetNVars(), SCIPgetVarAvgCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictlengthScore(), SCIPgetVarConflictScore(), SCIPgetVarPseudocostCountCurrentRun(), SCIPgetVarPseudocostCurrentRun(), SCIPgetVarPseudocostScore(), SCIPgetVarPseudocostScoreCurrentRun(), SCIPgetVars(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchLast(), SCIPgetVarStrongbranchNode(), SCIPgetVarStrongbranchWithPropagation(), SCIPhasCurrentNodeLP(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasIntegral(), SCIPisGE(), SCIPisGT(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisStopped(), SCIPisSumGE(), SCIPisSumGT(), SCIPisVarPscostRelerrorReliable(), SCIPnodeGetLowerbound(), SCIPpscostThresholdProbabilityTest(), SCIPrandomGetReal(), SCIPsignificantVarPscostDifference(), SCIPsolGetIndex(), SCIPstartStrongbranch(), SCIPupdateNodeLowerbound(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), SCIPverbMessage(), and TRUE.
Referenced by applyBdchgs(), and SCIPexecRelpscostBranching().
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 1459 of file branch_relpscost.c.
Referenced by execRelpscost().
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 1473 of file branch_relpscost.c.
|
static |
solving process initialization method of branching rule (called when branch and bound process is about to begin)
Definition at line 1488 of file branch_relpscost.c.
|
static |
solving process deinitialization method of branching rule (called before branch and bound process data is freed)
Definition at line 1509 of file branch_relpscost.c.
|
static |
branching execution method for fractional LP solutions
Definition at line 1526 of file branch_relpscost.c.