branch_relpscost.c File Reference

Detailed Description

reliable pseudo costs branching rule

Author

Tobias Achterberg

Timo Berthold

Gerald Gamrath

Definition in file branch_relpscost.c.

#include <assert.h>
#include <string.h>
#include "scip/branch_relpscost.h"

Go to the source code of this file.

Macros
#define	BRANCHRULE_NAME   "relpscost"
#define	BRANCHRULE_DESC   "reliability branching on pseudo cost values"
#define	BRANCHRULE_PRIORITY   10000
#define	BRANCHRULE_MAXDEPTH   -1
#define	BRANCHRULE_MAXBOUNDDIST   1.0
#define	DEFAULT_CONFLICTWEIGHT   0.01
#define	DEFAULT_CONFLENGTHWEIGHT   0.0
#define	DEFAULT_INFERENCEWEIGHT   0.0001
#define	DEFAULT_CUTOFFWEIGHT   0.0001
#define	DEFAULT_PSCOSTWEIGHT   1.0
#define	DEFAULT_MINRELIABLE   1.0
#define	DEFAULT_MAXRELIABLE   5.0
#define	DEFAULT_SBITERQUOT   0.5
#define	DEFAULT_SBITEROFS   100000
#define	DEFAULT_MAXLOOKAHEAD   9
#define	DEFAULT_INITCAND   100
#define	DEFAULT_INITITER   0
#define	DEFAULT_MAXBDCHGS   5
#define	DEFAULT_MAXPROPROUNDS   -2
#define	DEFAULT_PROBINGBOUNDS   TRUE

Functions
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	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_RESULT *result)
static	SCIP_DECL_BRANCHCOPY (branchCopyRelpscost)
static	SCIP_DECL_BRANCHFREE (branchFreeRelpscost)
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_RESULT *result)

Macro Definition Documentation

#define BRANCHRULE_NAME   "relpscost"

Definition at line 31 of file branch_relpscost.c.

Referenced by applyBdchgs(), SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECLP(), SCIPexecRelpscostBranching(), and SCIPincludeBranchruleRelpscost().

#define BRANCHRULE_DESC   "reliability branching on pseudo cost values"

Definition at line 32 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define BRANCHRULE_PRIORITY   10000

Definition at line 33 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 34 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 35 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_CONFLICTWEIGHT   0.01

weight in score calculations for conflict score

Definition at line 37 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_CONFLENGTHWEIGHT   0.0

weight in score calculations for conflict length score

Definition at line 38 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_INFERENCEWEIGHT   0.0001

weight in score calculations for inference score

Definition at line 39 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_CUTOFFWEIGHT   0.0001

weight in score calculations for cutoff score

Definition at line 40 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_PSCOSTWEIGHT   1.0

weight in score calculations for pseudo cost score

Definition at line 41 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 42 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 43 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 44 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_SBITEROFS   100000

additional number of allowed strong branching LP iterations

Definition at line 45 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

#define DEFAULT_MAXLOOKAHEAD   9

maximal number of further variables evaluated without better score

Definition at line 46 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 47 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 48 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 49 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 50 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 52 of file branch_relpscost.c.

Referenced by SCIPincludeBranchruleRelpscost().

Function Documentation

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

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 85 of file branch_relpscost.c.

References MIN, NULL, SCIP_Real, and SCIPfeastol().

Referenced by execRelpscost().

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

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 121 of file branch_relpscost.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPreallocBufferArray.

Referenced by execRelpscost().

static void freeBdchgs ( SCIP *  scip, int **  bdchginds, SCIP_BOUNDTYPE **  bdchgtypes, SCIP_Real **  bdchgbounds, int *  nbdchgs  )

static

frees 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

Definition at line 154 of file branch_relpscost.c.

References NULL, and SCIPfreeBufferArrayNull.

Referenced by execRelpscost().

static SCIP_RETCODE applyBdchgs ( SCIP *  scip, SCIP_VAR **  vars, int *  bdchginds, SCIP_BOUNDTYPE *  bdchgtypes, SCIP_Real *  bdchgbounds, int  nbdchgs, SCIP_RESULT *  result  )

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 175 of file branch_relpscost.c.

References BRANCHRULE_NAME, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMessage, SCIPfindBranchrule(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by execRelpscost().

static SCIP_RETCODE execRelpscost ( SCIP *  scip, SCIP_BRANCHRULE *  branchrule, SCIP_Bool  allowaddcons, SCIP_VAR **  branchcands, SCIP_Real *  branchcandssol, SCIP_Real *  branchcandsfrac, int  nbranchcands, SCIP_RESULT *  result  )

static

execute reliability pseudo cost branching

Parameters

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
result	pointer to the result of the execution

Definition at line 252 of file branch_relpscost.c.

References addBdchg(), applyBdchgs(), 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_CONSADDED, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_INVALID, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchVar(), SCIPdebugMessage, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetAvgConflictlengthScore(), SCIPgetAvgConflictScore(), SCIPgetAvgCutoffScore(), SCIPgetAvgInferenceScore(), SCIPgetAvgPseudocostScore(), SCIPgetBestSol(), SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNDualResolveLPIterations(), SCIPgetNDualResolveLPs(), SCIPgetNNodeInitLPIterations(), SCIPgetNNodeInitLPs(), SCIPgetNNodeLPIterations(), SCIPgetNNodes(), SCIPgetNRootStrongbranchLPIterations(), SCIPgetNStrongbranchLPIterations(), SCIPgetNVars(), SCIPgetVarAvgCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictlengthScore(), SCIPgetVarConflictScore(), SCIPgetVarPseudocostCountCurrentRun(), SCIPgetVarPseudocostCurrentRun(), SCIPgetVarPseudocostScore(), SCIPgetVarPseudocostScoreCurrentRun(), SCIPgetVars(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchLast(), SCIPgetVarStrongbranchNode(), SCIPgetVarStrongbranchWithPropagation(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasIntegral(), SCIPisGE(), SCIPisGT(), SCIPisLPSolBasic(), SCIPisLT(), SCIPisStopped(), SCIPisSumGE(), SCIPisSumGT(), SCIPnodeGetLowerbound(), SCIPstartStrongbranch(), SCIPupdateNodeLowerbound(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIPexecRelpscostBranching().

static SCIP_DECL_BRANCHCOPY ( branchCopyRelpscost  )

static

copy method for branchrule plugins (called when SCIP copies plugins)

Definition at line 978 of file branch_relpscost.c.

References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleRelpscost().

static SCIP_DECL_BRANCHFREE ( branchFreeRelpscost  )

static

destructor of branching rule to free user data (called when SCIP is exiting)

Definition at line 992 of file branch_relpscost.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeMemory.

static SCIP_DECL_BRANCHEXECLP ( branchExeclpRelpscost  )

static

branching execution method for fractional LP solutions

Definition at line 1007 of file branch_relpscost.c.

References BRANCHRULE_NAME, execRelpscost(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetName(), SCIPdebugMessage, SCIPduplicateBufferArray, SCIPfreeBufferArray, and SCIPgetLPBranchCands().

SCIP_RETCODE SCIPincludeBranchruleRelpscost

(

SCIP *

scip

)

creates the reliable pseudo cost branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1051 of file branch_relpscost.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_CONFLENGTHWEIGHT, DEFAULT_CONFLICTWEIGHT, DEFAULT_CUTOFFWEIGHT, DEFAULT_INFERENCEWEIGHT, DEFAULT_INITCAND, DEFAULT_INITITER, DEFAULT_MAXBDCHGS, DEFAULT_MAXLOOKAHEAD, DEFAULT_MAXPROPROUNDS, DEFAULT_MAXRELIABLE, DEFAULT_MINRELIABLE, DEFAULT_PROBINGBOUNDS, DEFAULT_PSCOSTWEIGHT, DEFAULT_SBITEROFS, DEFAULT_SBITERQUOT, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleFree(), and TRUE.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPexecRelpscostBranching	(	SCIP *	scip,
		SCIP_Bool	allowaddcons,
		SCIP_VAR **	branchcands,
		SCIP_Real *	branchcandssol,
		SCIP_Real *	branchcandsfrac,
		int	nbranchcands,
		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
result	pointer to the result of the execution

Definition at line 1139 of file branch_relpscost.c.

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