branch_inference.c File Reference

Detailed Description

inference history branching rule

Author

Tobias Achterberg

Timo Berthold

Stefan Heinz

Definition in file branch_inference.c.

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

Go to the source code of this file.

Macros
Branching rule properties
#define	BRANCHRULE_NAME   "inference"
#define	BRANCHRULE_DESC   "inference history branching"
#define	BRANCHRULE_PRIORITY   1000
#define	BRANCHRULE_MAXDEPTH   -1
#define	BRANCHRULE_MAXBOUNDDIST   1.0
Default parameter values
#define	DEFAULT_CONFLICTWEIGHT   1000.0
#define	DEFAULT_CUTOFFWEIGHT   1.0
#define	DEFAULT_INFERENCEWEIGHT   1.0
#define	DEFAULT_RELIABLESCORE   0.001
#define	DEFAULT_FRACTIONALS   TRUE
#define	DEFAULT_USEWEIGHTEDSUM   TRUE

Functions
static void	evaluateValueCand (SCIP_VAR *cand, SCIP_Real score, SCIP_Real branchpoint, SCIP_BRANCHDIR branchdir, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestbranchpoint, SCIP_BRANCHDIR *bestbranchdir)
static void	evaluateAggrCand (SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval)
static void	checkValueScore (SCIP_Real value, SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *bestscore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
static SCIP_Real	getAggrScore (SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore)
static SCIP_Real	getValueScore (SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
static SCIP_RETCODE	performBranching (SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result)
static	SCIP_DECL_BRANCHCOPY (branchCopyInference)
static	SCIP_DECL_BRANCHFREE (branchFreeInference)
static	SCIP_DECL_BRANCHEXECLP (branchExeclpInference)
static	SCIP_DECL_BRANCHEXECEXT (branchExecextInference)
static	SCIP_DECL_BRANCHEXECPS (branchExecpsInference)
SCIP_RETCODE	SCIPincludeBranchruleInference (SCIP *scip)

Macro Definition Documentation

#define BRANCHRULE_NAME   "inference"

Definition at line 36 of file branch_inference.c.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeBranchruleInference().

#define BRANCHRULE_DESC   "inference history branching"

Definition at line 37 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define BRANCHRULE_PRIORITY   1000

Definition at line 38 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 39 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 40 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_CONFLICTWEIGHT   1000.0

weight in score calculations for conflict score

Definition at line 49 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_CUTOFFWEIGHT   1.0

weight in score calculations for cutoff score

Definition at line 50 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_INFERENCEWEIGHT   1.0

weight in score calculations for inference score

Definition at line 51 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_RELIABLESCORE   0.001

score which is seen to be reliable for a branching decision

Definition at line 52 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_FRACTIONALS   TRUE

should branching on LP solution be restricted to the fractional variables?

Definition at line 53 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_USEWEIGHTEDSUM   TRUE

should a weighted sum of inference, conflict and cutoff weights be used?

Definition at line 54 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

Function Documentation

static void evaluateValueCand ( SCIP_VAR *  cand, SCIP_Real  score, SCIP_Real  branchpoint, SCIP_BRANCHDIR  branchdir, SCIP_VAR **  bestcand, SCIP_Real *  bestscore, SCIP_Real *  bestbranchpoint, SCIP_BRANCHDIR *  bestbranchdir  )

static

evaluate the given candidate with the given score against the currently best know candidate

Parameters

cand	candidate to be checked
score	score of the candidate
branchpoint	potential branching point
branchdir	potential branching direction
bestcand	pointer to the currently best candidate
bestscore	pointer to the score of the currently best candidate
bestbranchpoint	pointer to store the (best) branching point
bestbranchdir	pointer to store the branching direction relative to the branching point

Definition at line 71 of file branch_inference.c.

References REALABS, SCIP_Real, SCIPvarGetIndex(), and SCIPvarGetObj().

Referenced by performBranching().

static void evaluateAggrCand ( SCIP_VAR *  cand, SCIP_Real  score, SCIP_Real  val, SCIP_VAR **  bestcand, SCIP_Real *  bestscore, SCIP_Real *  bestval  )

static

evaluate the given candidate with the given score against the currently best know candidate

Parameters

cand	candidate to be checked
score	score of the candidate
val	solution value of the candidate
bestcand	pointer to the currently best candidate
bestscore	pointer to the score of the currently best candidate
bestval	pointer to the solution value of the currently best candidate

Definition at line 125 of file branch_inference.c.

References REALABS, SCIP_Real, SCIPvarGetIndex(), and SCIPvarGetObj().

Referenced by performBranching().

static void checkValueScore ( SCIP_Real  value, SCIP_HISTORY *  history, SCIP_BRANCHDIR  dir, SCIP_Real  conflictweight, SCIP_Real  cutoffweight, SCIP_Real  reliablescore, SCIP_Real *  bestscore, SCIP_Real *  branchpoint, SCIP_BRANCHDIR *  branchdir  )

static

check if the score for the given domain value and variable domain value is better than the current best know one

Parameters

value	domain value
history	variable history for given donain value
dir	branching direction
conflictweight	weight in score calculations for conflict score
cutoffweight	weight in score calculations for cutoff score
reliablescore	score which is seen to be reliable for a branching decision
bestscore	pointer to store the best score
branchpoint	pointer to store the (best) branching point
branchdir	pointer to store the branching direction relative to the branching point

Definition at line 175 of file branch_inference.c.

References SCIP_Real, SCIPhistoryGetCutoffSum(), and SCIPhistoryGetVSIDS().

Referenced by getValueScore().

static SCIP_Real getAggrScore ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  conflictweight, SCIP_Real  inferenceweight, SCIP_Real  cutoffweight, SCIP_Real  reliablescore  )

static

return an aggregated score for the given variable using the conflict score and cutoff score

Parameters

scip	SCIP data structure
var	problem variable
conflictweight	weight in score calculations for conflict score
inferenceweight	weight in score calculations for inference score
cutoffweight	weight in score calculations for cutoff score
reliablescore	score which is seen to be reliable for a branching decision

Definition at line 217 of file branch_inference.c.

References SCIP_Real, SCIPgetVarAvgInferenceCutoffScore(), and SCIPgetVarConflictScore().

Referenced by performBranching().

static SCIP_Real getValueScore ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  conflictweight, SCIP_Real  cutoffweight, SCIP_Real  reliablescore, SCIP_Real *  branchpoint, SCIP_BRANCHDIR *  branchdir  )

static

return an aggregated score for the given variable using the conflict score and cutoff score

Parameters

scip	SCIP data structure
var	problem variable
conflictweight	weight in score calculations for conflict score
cutoffweight	weight in score calculations for cutoff score
reliablescore	score which is seen to be reliable for a branching decision
branchpoint	pointer to store the branching point
branchdir	pointer to store the branching direction relative to the branching point

Definition at line 248 of file branch_inference.c.

References checkValueScore(), NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_Real, SCIP_UNKNOWN, SCIPvaluehistoryGetHistories(), SCIPvaluehistoryGetNValues(), SCIPvaluehistoryGetValues(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and SCIPvarGetValuehistory().

Referenced by performBranching().

static SCIP_RETCODE performBranching ( SCIP *  scip, SCIP_VAR **  cands, SCIP_Real *  candsols, int  ncands, SCIP_Real  conflictweight, SCIP_Real  inferenceweight, SCIP_Real  cutoffweight, SCIP_Real  reliablescore, SCIP_Bool  useweightedsum, SCIP_RESULT *  result  )

static

selects a variable out of the given candidate array and performs the branching

Parameters

scip	SCIP data structure
cands	candidate array
candsols	array of candidate solution values, or NULL
ncands	number of candidates
conflictweight	weight in score calculations for conflict score
inferenceweight	weight in score calculations for inference score
cutoffweight	weight in score calculations for cutoff score
reliablescore	score which is seen to be reliable for a branching decision
useweightedsum	should a weighted sum of inference, conflict and cutoff weights be used?
result	buffer to store result (branched, reduced domain, ...)

Definition at line 306 of file branch_inference.c.

References evaluateAggrCand(), evaluateValueCand(), getAggrScore(), getValueScore(), NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_UNKNOWN, SCIPbranchVar(), SCIPbranchVarVal(), SCIPcalcChildEstimate(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateChild(), SCIPdebugMessage, SCIPgetBranchingPoint(), SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_BRANCHEXECEXT(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

static SCIP_DECL_BRANCHCOPY ( branchCopyInference  )

static

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

Definition at line 536 of file branch_inference.c.

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

static SCIP_DECL_BRANCHFREE ( branchFreeInference  )

static

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

Definition at line 550 of file branch_inference.c.

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

static SCIP_DECL_BRANCHEXECLP ( branchExeclpInference  )

static

branching execution method for fractional LP solutions

Definition at line 564 of file branch_inference.c.

References NULL, performBranching(), SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMessage, SCIPgetLPBranchCands(), and SCIPgetPseudoBranchCands().

static SCIP_DECL_BRANCHEXECEXT ( branchExecextInference  )

static

branching execution method for external candidates

Definition at line 598 of file branch_inference.c.

References NULL, performBranching(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetData(), SCIPdebugMessage, and SCIPgetExternBranchCands().

static SCIP_DECL_BRANCHEXECPS ( branchExecpsInference  )

static

branching execution method for not completely fixed pseudo solutions

Definition at line 625 of file branch_inference.c.

References NULL, performBranching(), SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMessage, and SCIPgetPseudoBranchCands().

SCIP_RETCODE SCIPincludeBranchruleInference

(

SCIP *

scip

)

creates the inference history branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 654 of file branch_inference.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_CONFLICTWEIGHT, DEFAULT_CUTOFFWEIGHT, DEFAULT_FRACTIONALS, DEFAULT_INFERENCEWEIGHT, DEFAULT_RELIABLESCORE, DEFAULT_USEWEIGHTEDSUM, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIP_REAL_MIN, SCIPaddBoolParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecExt(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecPs(), SCIPsetBranchruleFree(), and TRUE.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeDefaultPlugins().