Detailed Description

inference history branching rule

Author: Tobias Achterberg; Timo Berthold; Stefan Heinz

#include "scip/branch_inference.h"
#include "scip/pub_branch.h"
#include "scip/pub_history.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_message.h"
#include "scip/scip_mem.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_var.h"
#include <string.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

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME "inference"

Definition at line 44 of file branch_inference.c.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeBranchruleInference().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC "inference history branching"

Definition at line 45 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY 1000

Definition at line 46 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH -1

Definition at line 47 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST 1.0

Definition at line 48 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CONFLICTWEIGHT

#define DEFAULT_CONFLICTWEIGHT 1000.0

weight in score calculations for conflict score

Definition at line 57 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CUTOFFWEIGHT

#define DEFAULT_CUTOFFWEIGHT 1.0

weight in score calculations for cutoff score

Definition at line 58 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_INFERENCEWEIGHT

#define DEFAULT_INFERENCEWEIGHT 1.0

weight in score calculations for inference score

Definition at line 59 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_RELIABLESCORE

#define DEFAULT_RELIABLESCORE 0.001

score which is seen to be reliable for a branching decision

Definition at line 60 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_FRACTIONALS

#define DEFAULT_FRACTIONALS TRUE

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

Definition at line 61 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_USEWEIGHTEDSUM

#define DEFAULT_USEWEIGHTEDSUM TRUE

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

Definition at line 62 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

Function Documentation

◆ evaluateValueCand()

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 79 of file branch_inference.c.

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

Referenced by performBranching().

◆ evaluateAggrCand()

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 133 of file branch_inference.c.

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

Referenced by performBranching().

◆ checkValueScore()

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 183 of file branch_inference.c.

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

Referenced by getValueScore().

◆ getAggrScore()

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 225 of file branch_inference.c.

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

Referenced by performBranching().

◆ getValueScore()

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 256 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().

◆ 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 314 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(), SCIPdebugMsg, SCIPgetBranchingPoint(), SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

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

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyInference )

static

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

Definition at line 544 of file branch_inference.c.

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

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeInference )

static

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

Definition at line 558 of file branch_inference.c.

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

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpInference )

static

branching execution method for fractional LP solutions

Definition at line 572 of file branch_inference.c.

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

◆ SCIP_DECL_BRANCHEXECEXT()

static SCIP_DECL_BRANCHEXECEXT ( branchExecextInference )

static

branching execution method for external candidates

Definition at line 606 of file branch_inference.c.

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

◆ SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsInference )

static

branching execution method for not completely fixed pseudo solutions

Definition at line 633 of file branch_inference.c.

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

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BRANCHRULE_NAME

◆ BRANCHRULE_DESC

◆ BRANCHRULE_PRIORITY

◆ BRANCHRULE_MAXDEPTH

◆ BRANCHRULE_MAXBOUNDDIST

◆ DEFAULT_CONFLICTWEIGHT

◆ DEFAULT_CUTOFFWEIGHT

◆ DEFAULT_INFERENCEWEIGHT

◆ DEFAULT_RELIABLESCORE

◆ DEFAULT_FRACTIONALS

◆ DEFAULT_USEWEIGHTEDSUM

Function Documentation

◆ evaluateValueCand()

◆ evaluateAggrCand()

◆ checkValueScore()

◆ getAggrScore()

◆ getValueScore()

◆ performBranching()

◆ SCIP_DECL_BRANCHCOPY()

◆ SCIP_DECL_BRANCHFREE()

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHEXECEXT()

◆ SCIP_DECL_BRANCHEXECPS()