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

#define	DEFAULT_CONFLICTPRIO 1

#define	DEFAULT_CUTOFFPRIO 1

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 scip, SCIP_VAR cand, SCIP_Real score, SCIP_Real val, SCIP_VAR *bestcand, SCIP_Real bestscore, SCIP_Real bestval, SCIP_VAR bestcands, int nbestcands)

static void	tiebreakAggrCand (SCIP_VAR **bestcands, int nbestcands)

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_VAR var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real branchpoint, SCIP_BRANCHDIR *branchdir)

static void	selectBestCands (SCIP scip, SCIP_VAR cands, SCIP_Real candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_VAR *bestcands, int nbestcands)

static SCIP_RETCODE	performBranchingSol (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, int conflictprio, int cutoffprio)

static SCIP_RETCODE	performBranchingNoSol (SCIP scip, SCIP_VAR cands, 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 54 of file branch_inference.c.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeBranchruleInference().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC "inference history branching"

Definition at line 55 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY 1000

Definition at line 56 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH -1

Definition at line 57 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST 1.0

Definition at line 58 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 67 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 68 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 69 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 70 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 71 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 72 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CONFLICTPRIO

#define DEFAULT_CONFLICTPRIO 1

priority value for using conflict weights in lex. order

Definition at line 74 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CUTOFFPRIO

#define DEFAULT_CUTOFFPRIO 1

priority value for using cutoff weights in lex. order

Definition at line 75 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, tiebreaking included

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

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

Referenced by performBranchingNoSol().

◆ evaluateAggrCand()

static void evaluateAggrCand	(	SCIP *	scip,
		SCIP_VAR *	cand,
		SCIP_Real	score,
		SCIP_Real	val,
		SCIP_VAR **	bestcand,
		SCIP_Real *	bestscore,
		SCIP_Real *	bestval,
		SCIP_VAR **	bestcands,
		int *	nbestcands
	)

static

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

TODO: consider a weaker comparison of some kind

Parameters

scip	SCIP data structure
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
bestcands	buffer array to return selected candidates
nbestcands	pointer to return number of selected candidates

Definition at line 148 of file branch_inference.c.

References SCIPisEQ().

Referenced by performBranchingNoSol(), and selectBestCands().

◆ tiebreakAggrCand()

static void tiebreakAggrCand	(	SCIP_VAR **	bestcands,
		int	nbestcands
	)

static

choose a singular best candidate from bestcands and move it to the beginning of the candidate array

Parameters

bestcands	buffer array to return selected candidates
nbestcands	number of selected candidates

Definition at line 182 of file branch_inference.c.

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

Referenced by performBranchingSol().

◆ 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 221 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 263 of file branch_inference.c.

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

Referenced by performBranchingNoSol(), and selectBestCands().

◆ getValueScore()

static SCIP_Real getValueScore	(	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

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 294 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 performBranchingNoSol().

◆ selectBestCands()

static void selectBestCands	(	SCIP *	scip,
		SCIP_VAR **	cands,
		SCIP_Real *	candsols,
		int	ncands,
		SCIP_Real	conflictweight,
		SCIP_Real	inferenceweight,
		SCIP_Real	cutoffweight,
		SCIP_Real	reliablescore,
		SCIP_VAR **	bestcands,
		int *	nbestcands
	)

static

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
bestcands	buffer array to return selected candidates
nbestcands	pointer to return number of selected candidates

Definition at line 349 of file branch_inference.c.

References evaluateAggrCand(), getAggrScore(), NULL, SCIP_Real, SCIP_UNKNOWN, SCIPdebugMsg, SCIPgetVarSol(), SCIPvarGetBranchPriority(), and SCIPvarGetName().

Referenced by performBranchingSol().

◆ performBranchingSol()

static SCIP_RETCODE performBranchingSol	(	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,
		int	conflictprio,
		int	cutoffprio
	)

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, ...)
conflictprio	priority value for using conflict weights in lex. order
cutoffprio	priority value for using conflict weights in lex. order

Definition at line 403 of file branch_inference.c.

References FALSE, NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_UNKNOWN, SCIPallocClearBufferArray, SCIPbranchVarVal(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBranchingPoint(), SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), selectBestCands(), and tiebreakAggrCand().

Referenced by SCIP_DECL_BRANCHEXECEXT().

◆ performBranchingNoSol()

static SCIP_RETCODE performBranchingNoSol	(	SCIP *	scip,
		SCIP_VAR **	cands,
		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
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 543 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, SCIPallocBufferArray, SCIPbranchVar(), SCIPcalcChildEstimate(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateChild(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by 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 761 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 775 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 789 of file branch_inference.c.

References NULL, performBranchingNoSol(), 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 823 of file branch_inference.c.

References NULL, performBranchingSol(), 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 850 of file branch_inference.c.

References NULL, performBranchingNoSol(), 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

◆ DEFAULT_CONFLICTPRIO

◆ DEFAULT_CUTOFFPRIO

Function Documentation

◆ evaluateValueCand()

◆ evaluateAggrCand()

◆ tiebreakAggrCand()

◆ checkValueScore()

◆ getAggrScore()

◆ getValueScore()

◆ selectBestCands()

◆ performBranchingSol()

◆ performBranchingNoSol()

◆ SCIP_DECL_BRANCHCOPY()

◆ SCIP_DECL_BRANCHFREE()

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHEXECEXT()

◆ SCIP_DECL_BRANCHEXECPS()