Detailed Description
generalized reliable pseudo costs branching rule
- probing is executed until depth 10 and afterwards with stepsize 5 by that all pseudocost scores and inference informations are updated otherwise the variable with best score is branched on
- NEW! probing is done according to reliability values per candidate depending on tree size and probing rounds
- the node is reevaluated immediately if MAXBDCHGS occur during probing
Definition in file branch_relpsprob.c.
#include <assert.h>
#include <string.h>
#include "branch_relpsprob.h"
#include "relax_gcg.h"
#include "cons_integralorig.h"
#include "pricer_gcg.h"
#include "gcg.h"
#include "scip/nodesel_estimate.h"
#include "scip/nodesel_hybridestim.h"
#include "scip/nodesel_restartdfs.h"
#include "scip/branch_allfullstrong.h"
#include "scip/branch_fullstrong.h"
#include "scip/branch_inference.h"
#include "scip/branch_mostinf.h"
#include "scip/branch_leastinf.h"
#include "scip/branch_pscost.h"
#include "scip/branch_random.h"
#include "scip/branch_relpscost.h"
#include "scip/nodesel_bfs.h"
#include "scip/nodesel_dfs.h"
Go to the source code of this file.
Data Structures | |
struct | SCIP_BranchruleData |
struct | BdchgData |
Macros | |
#define | BRANCHRULE_NAME "relpsprob" |
#define | BRANCHRULE_DESC "generalized reliability branching using probing" |
#define | BRANCHRULE_PRIORITY -100 |
#define | BRANCHRULE_MAXDEPTH -1 |
#define | BRANCHRULE_MAXBOUNDDIST 1.0 |
#define | DEFAULT_CONFLICTWEIGHT 0.01 |
#define | DEFAULT_CONFLENGTHWEIGHT 0.0001 |
#define | DEFAULT_INFERENCEWEIGHT 0.1 |
#define | DEFAULT_CUTOFFWEIGHT 0.0001 |
#define | DEFAULT_PSCOSTWEIGHT 1.0 |
#define | DEFAULT_MINRELIABLE 1.0 |
#define | DEFAULT_MAXRELIABLE 8.0 |
#define | DEFAULT_ITERQUOT 0.5 |
#define | DEFAULT_ITEROFS 100000 |
#define | DEFAULT_MAXLOOKAHEAD 8 |
#define | DEFAULT_INITCAND 100 |
#define | DEFAULT_MAXBDCHGS 20 |
#define | DEFAULT_MINBDCHGS 1 |
#define | DEFAULT_USELP TRUE |
#define | DEFAULT_RELIABILITY 0.8 |
#define | HASHSIZE_VARS 131101 |
Typedefs | |
typedef struct BdchgData | BDCHGDATA |
Functions | |
static SCIP_RETCODE | createBdchgData (SCIP *scip, BDCHGDATA **bdchgdata, SCIP_VAR **vars, int nvars) |
static SCIP_RETCODE | freeBdchgData (SCIP *scip, BDCHGDATA *bdchgdata) |
static SCIP_RETCODE | addBdchg (SCIP *scip, BDCHGDATA *bdchgdata, SCIP_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool infrounding, int *nbdchgs, SCIP_Bool *infeasible) |
static SCIP_RETCODE | applyBdchgs (SCIP *scip, BDCHGDATA *bdchgdata, SCIP_NODE *node) |
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 frac) |
static SCIP_RETCODE | calculateBounds (SCIP *scip, SCIP_VAR *branchvar, SCIP_Real *downlb, SCIP_Real *downub, SCIP_Real *uplb, SCIP_Real *upub) |
static SCIP_RETCODE | applyProbing (SCIP *scip, SCIP_VAR **vars, int nvars, SCIP_VAR *probingvar, SCIP_Bool probingdir, SCIP_Bool solvelp, SCIP_Longint *nlpiterations, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff) |
static SCIP_RETCODE | getVarProbingbranch (SCIP *scip, SCIP_VAR *probingvar, BDCHGDATA *bdchgdata, SCIP_Bool solvelp, SCIP_Longint *nlpiterations, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *lperror, int *nbdchgs) |
static SCIP_RETCODE | addBranchcandsToData (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, int nbranchcands) |
static SCIP_RETCODE | incNVarBranchings (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var) |
static SCIP_RETCODE | incNVarProbings (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var) |
static SCIP_RETCODE | execRelpsprob (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, int nbranchcands, int nvars, SCIP_RESULT *result, SCIP_VAR **branchvar) |
static | SCIP_DECL_BRANCHFREE (branchFreeRelpsprob) |
static | SCIP_DECL_BRANCHINITSOL (branchInitsolRelpsprob) |
static | SCIP_DECL_BRANCHEXITSOL (branchExitsolRelpsprob) |
SCIP_RETCODE | SCIPincludeBranchruleRelpsprob (SCIP *scip) |
SCIP_RETCODE | SCIPgetRelpsprobBranchVar (SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, int nbranchcands, int nvars, SCIP_RESULT *result, SCIP_VAR **branchvar) |
Macro Definition Documentation
◆ BRANCHRULE_NAME
#define BRANCHRULE_NAME "relpsprob" |
Definition at line 69 of file branch_relpsprob.c.
◆ BRANCHRULE_DESC
#define BRANCHRULE_DESC "generalized reliability branching using probing" |
Definition at line 70 of file branch_relpsprob.c.
◆ BRANCHRULE_PRIORITY
#define BRANCHRULE_PRIORITY -100 |
Definition at line 71 of file branch_relpsprob.c.
◆ BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 72 of file branch_relpsprob.c.
◆ BRANCHRULE_MAXBOUNDDIST
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 73 of file branch_relpsprob.c.
◆ DEFAULT_CONFLICTWEIGHT
#define DEFAULT_CONFLICTWEIGHT 0.01 |
weight in score calculations for conflict score
Definition at line 75 of file branch_relpsprob.c.
◆ DEFAULT_CONFLENGTHWEIGHT
#define DEFAULT_CONFLENGTHWEIGHT 0.0001 |
weight in score calculations for conflict length score
Definition at line 76 of file branch_relpsprob.c.
◆ DEFAULT_INFERENCEWEIGHT
#define DEFAULT_INFERENCEWEIGHT 0.1 |
weight in score calculations for inference score
Definition at line 77 of file branch_relpsprob.c.
◆ DEFAULT_CUTOFFWEIGHT
#define DEFAULT_CUTOFFWEIGHT 0.0001 |
weight in score calculations for cutoff score
Definition at line 78 of file branch_relpsprob.c.
◆ DEFAULT_PSCOSTWEIGHT
#define DEFAULT_PSCOSTWEIGHT 1.0 |
weight in score calculations for pseudo cost score
Definition at line 79 of file branch_relpsprob.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 80 of file branch_relpsprob.c.
◆ DEFAULT_MAXRELIABLE
#define DEFAULT_MAXRELIABLE 8.0 |
maximal value for minimum pseudo cost size to regard pseudo cost value as reliable
Definition at line 81 of file branch_relpsprob.c.
◆ DEFAULT_ITERQUOT
#define DEFAULT_ITERQUOT 0.5 |
maximal fraction of branching LP iterations compared to normal iters
Definition at line 82 of file branch_relpsprob.c.
◆ DEFAULT_ITEROFS
#define DEFAULT_ITEROFS 100000 |
additional number of allowed LP iterations
Definition at line 83 of file branch_relpsprob.c.
◆ DEFAULT_MAXLOOKAHEAD
#define DEFAULT_MAXLOOKAHEAD 8 |
maximal number of further variables evaluated without better score
Definition at line 84 of file branch_relpsprob.c.
◆ DEFAULT_INITCAND
#define DEFAULT_INITCAND 100 |
maximal number of candidates initialized with strong branching per node
Definition at line 85 of file branch_relpsprob.c.
◆ DEFAULT_MAXBDCHGS
#define DEFAULT_MAXBDCHGS 20 |
maximal number of bound tightenings before the node is immediately reevaluated (-1: unlimited)
Definition at line 86 of file branch_relpsprob.c.
◆ DEFAULT_MINBDCHGS
#define DEFAULT_MINBDCHGS 1 |
minimal number of bound tightenings before the node is reevaluated
Definition at line 87 of file branch_relpsprob.c.
◆ DEFAULT_USELP
#define DEFAULT_USELP TRUE |
shall the lp be solved during probing?
Definition at line 88 of file branch_relpsprob.c.
◆ DEFAULT_RELIABILITY
#define DEFAULT_RELIABILITY 0.8 |
reliability value for probing
Definition at line 89 of file branch_relpsprob.c.
◆ HASHSIZE_VARS
#define HASHSIZE_VARS 131101 |
minimal size of hash table in bdchgdata
Definition at line 91 of file branch_relpsprob.c.
Typedef Documentation
◆ BDCHGDATA
Definition at line 135 of file branch_relpsprob.c.
Function Documentation
◆ createBdchgData()
|
static |
creates bound change data structure: all variables are put into a hashmap and arrays containig current lower and upper bounds are created
- Parameters
-
scip SCIP data structure bdchgdata bound change data to be allocated vars array of variables to be watched nvars number of variables to be watched
Definition at line 146 of file branch_relpsprob.c.
References HASHSIZE_VARS, and BdchgData::nvars.
Referenced by execRelpsprob().
◆ freeBdchgData()
|
static |
method to free bound change data strucutre
- Parameters
-
scip SCIP data structure bdchgdata bound change data to be allocated
Definition at line 186 of file branch_relpsprob.c.
References BdchgData::infroundings, BdchgData::lbchgs, BdchgData::ubchgs, and BdchgData::varhashmap.
Referenced by execRelpsprob().
◆ addBdchg()
|
static |
adds given variable and bound change to hashmap and bound change arrays
- Parameters
-
scip SCIP data structure bdchgdata structure to keep bound chage data var variable to store bound change newbound new bound for given variable boundtype lower or upper bound change infrounding is the bdchg valid due to an infeasible rounding of the given var nbdchgs total number of bound changes occured so far infeasible pointer to store whether bound change makes the node infeasible
Definition at line 211 of file branch_relpsprob.c.
References BdchgData::infroundings, BdchgData::lbchgs, BdchgData::nvars, BdchgData::ubchgs, and BdchgData::varhashmap.
Referenced by getVarProbingbranch().
◆ applyBdchgs()
|
static |
applies bound changes stored in bound change arrays
- Parameters
-
scip SCIP data structure bdchgdata structure containing bound changes for almost all variables node node for which bound changes are applied, NULL for curnode
Definition at line 296 of file branch_relpsprob.c.
References BdchgData::lbchgs, BdchgData::nvars, BdchgData::ubchgs, and BdchgData::varhashmap.
Referenced by execRelpsprob().
◆ 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 pscostscore pscost score of current variable avgpscostscore average pscost score frac fractional value of variable in current solution
Definition at line 357 of file branch_relpsprob.c.
Referenced by execRelpsprob().
◆ calculateBounds()
|
static |
- Parameters
-
scip SCIP data structure branchvar branching variable downlb lower bound of variable in down branch downub upper bound of variable in down branch uplb lower bound of variable in up branch upub upper bound of variable in up branch
Definition at line 396 of file branch_relpsprob.c.
Referenced by applyProbing(), and getVarProbingbranch().
◆ applyProbing()
|
static |
applies probing of a single variable in the given direction, and stores evaluation in given arrays
- Parameters
-
scip SCIP data structure vars problem variables nvars number of problem variables probingvar variable to perform probing on probingdir value to fix probing variable to solvelp value to decide whether pricing loop shall be performed nlpiterations pointer to store the number of used LP iterations proplbs array to store lower bounds after full propagation propubs array to store upper bounds after full propagation lpobjvalue pointer to store the lp obj value if lp was solved lpsolved pointer to store whether the lp was solved lperror pointer to store whether an unresolved LP error occured or the solving process should be stopped (e.g., due to a time limit) cutoff pointer to store whether the probing direction is infeasible
Definition at line 474 of file branch_relpsprob.c.
References calculateBounds(), GCGgetMasterprob(), GCGrelaxEndProbing(), GCGrelaxNewProbingnodeMaster(), GCGrelaxNewProbingnodeOrig(), GCGrelaxPerformProbingWithPricing(), GCGrelaxStartProbing(), and BdchgData::nvars.
Referenced by getVarProbingbranch().
◆ getVarProbingbranch()
|
static |
gets generalized strong branching information on problem variable
- Parameters
-
scip SCIP data structure probingvar variable to get strong probing branching values for bdchgdata structure containing bound changes for almost all variables solvelp value to decide whether pricing loop shall be performed nlpiterations pointert to stroe the number of used LP iterations down stores dual bound after branching column down up stores dual bound after branching column up downvalid stores whether the returned down value is a valid dual bound, or NULL; otherwise, it can only be used as an estimate value upvalid stores whether the returned up value is a valid dual bound, or NULL; otherwise, it can only be used as an estimate value downinf pointer to store whether the downwards branch is infeasible, or NULL upinf pointer to store whether the upwards branch is infeasible, or NULL lperror pointer to store whether an unresolved LP error occured or the solving process should be stopped (e.g., due to a time limit) nbdchgs pointer to store number of total bound changes
Definition at line 596 of file branch_relpsprob.c.
References addBdchg(), applyProbing(), calculateBounds(), and BdchgData::nvars.
Referenced by execRelpsprob().
◆ addBranchcandsToData()
|
static |
adds branching candidates to branchruledata to collect infos about it
- Parameters
-
scip SCIP data structure branchrule branching rule branchcands branching candidates nbranchcands number of branching candidates
Definition at line 838 of file branch_relpsprob.c.
References HASHSIZE_VARS, and BdchgData::nvars.
Referenced by execRelpsprob().
◆ incNVarBranchings()
|
static |
increases number of branchings that took place on the given variable
- Parameters
-
scip SCIP data structure branchrule branching rule var variable to increase number of branchings on
Definition at line 915 of file branch_relpsprob.c.
Referenced by execRelpsprob().
◆ incNVarProbings()
|
static |
increases number of probings that took place on the given variable
- Parameters
-
scip SCIP data structure branchrule branching rule var variable to increase number of branchings on
Definition at line 944 of file branch_relpsprob.c.
Referenced by execRelpsprob().
◆ execRelpsprob()
|
static |
execute generalized reliability pseudo cost probing branching
- Parameters
-
scip SCIP data structure branchrule branching rule branchcands branching candidates branchcandssol solution value for the branching candidates nbranchcands number of branching candidates nvars number of variables to be watched be bdchgdata result pointer to the result of the execution branchvar pointer to the variable to branch on
Definition at line 974 of file branch_relpsprob.c.
References addBranchcandsToData(), applyBdchgs(), calcScore(), createBdchgData(), freeBdchgData(), GCGgetMasterprob(), getVarProbingbranch(), incNVarBranchings(), incNVarProbings(), and BdchgData::nvars.
Referenced by SCIPgetRelpsprobBranchVar().
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 1373 of file branch_relpsprob.c.
◆ SCIP_DECL_BRANCHINITSOL()
|
static |
solving process initialization method of branching rule (called when branch and bound process is about to begin)
Definition at line 1391 of file branch_relpsprob.c.
◆ SCIP_DECL_BRANCHEXITSOL()
|
static |
solving process deinitialization method of branching rule (called before branch and bound process data is freed)
Definition at line 1418 of file branch_relpsprob.c.
◆ SCIPincludeBranchruleRelpsprob()
SCIP_RETCODE SCIPincludeBranchruleRelpsprob | ( | SCIP * | scip | ) |
creates the reliable pseudo cost braching rule and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 1451 of file branch_relpsprob.c.
References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_CONFLENGTHWEIGHT, DEFAULT_CONFLICTWEIGHT, DEFAULT_CUTOFFWEIGHT, DEFAULT_INFERENCEWEIGHT, DEFAULT_INITCAND, DEFAULT_ITEROFS, DEFAULT_ITERQUOT, DEFAULT_MAXBDCHGS, DEFAULT_MAXLOOKAHEAD, DEFAULT_MAXRELIABLE, DEFAULT_MINBDCHGS, DEFAULT_MINRELIABLE, DEFAULT_PSCOSTWEIGHT, DEFAULT_RELIABILITY, DEFAULT_USELP, GCGconsIntegralorigAddBranchrule(), and GCGmasterGetOrigprob().
Referenced by GCGincludeMasterPlugins().
◆ SCIPgetRelpsprobBranchVar()
SCIP_RETCODE SCIPgetRelpsprobBranchVar | ( | SCIP * | scip, |
SCIP_VAR ** | branchcands, | ||
SCIP_Real * | branchcandssol, | ||
int | nbranchcands, | ||
int | nvars, | ||
SCIP_RESULT * | result, | ||
SCIP_VAR ** | branchvar | ||
) |
execution reliability pseudo cost probing branching with the given branching candidates
- Parameters
-
scip SCIP data structure branchcands brancing candidates branchcandssol solution value for the branching candidates nbranchcands number of branching candidates nvars number of variables to be watched by bdchgdata result pointer to the result of the execution branchvar pointer to the variable to branch on
Definition at line 1545 of file branch_relpsprob.c.
References BRANCHRULE_NAME, execRelpsprob(), GCGmasterGetOrigprob(), and BdchgData::nvars.
Referenced by branchExtern().