branch_allfullstrong.h File Reference

Detailed Description

all variables full strong LP branching rule

Author

Tobias Achterberg

The all variables full strong branching rule applies strong branching to every non-fixed variable at the current node of the branch-and-bound search. The rule selects the candidate which will cause the highest gain of the dual bound in the created sub-tree among all branching variables.

For calculating the gain, a look-ahead is performed by solving the child node LPs which will result from branching on a variable.

For a more mathematical description and a comparison between the strong branching rule and other branching rules in SCIP, we refer to

Tobias Achterberg
Constraint Integer Programming
PhD Thesis, Technische Universität Berlin, 2007

Definition in file branch_allfullstrong.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPselectVarPseudoStrongBranching (SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, SCIP_Bool allowaddcons, int *bestpseudocand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
SCIP_RETCODE	SCIPincludeBranchruleAllfullstrong (SCIP *scip)

Function Documentation

SCIP_RETCODE SCIPselectVarPseudoStrongBranching	(	SCIP *	scip,
		SCIP_VAR **	pseudocands,
		SCIP_Bool *	skipdown,
		SCIP_Bool *	skipup,
		int	npseudocands,
		int	npriopseudocands,
		SCIP_Bool	allowaddcons,
		int *	bestpseudocand,
		SCIP_Real *	bestdown,
		SCIP_Real *	bestup,
		SCIP_Real *	bestscore,
		SCIP_Bool *	bestdownvalid,
		SCIP_Bool *	bestupvalid,
		SCIP_Real *	provedbound,
		SCIP_RESULT *	result
	)

Selects a variable from a set of candidates by strong branching

Returns

SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.

Note

The variables in the lpcands array must have a fractional value in the current LP solution

Parameters

scip	original SCIP data structure
pseudocands	branching candidates
skipdown	should down branchings be skipped?
skipup	should up branchings be skipped?
npseudocands	number of branching candidates
npriopseudocands	number of priority branching candidates
allowaddcons	is the branching rule allowed to add constraints?
bestpseudocand	best candidate for branching
bestdown	objective value of the down branch for bestcand
bestup	objective value of the up branch for bestcand
bestscore	score for bestcand
bestdownvalid	is bestdown a valid dual bound for the down branch?
bestupvalid	is bestup a valid dual bound for the up branch?
provedbound	proved dual bound for current subtree
result	result pointer

Definition at line 268 of file branch_allfullstrong.c.

References BRANCHRULE_NAME, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPbranchruleGetData(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPdebugMessage, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfindBranchrule(), SCIPfixVar(), SCIPgetBranchScore(), SCIPgetBranchScoreMultiple(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchInt(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasIntegral(), SCIPisGE(), SCIPprintDisplayLine(), SCIPstartStrongbranch(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsInLP(), SCIPverbMessage(), and TRUE.

Referenced by branch(), and SCIP_DECL_BRANCHEXECLP().

SCIP_RETCODE SCIPincludeBranchruleAllfullstrong

(

SCIP *

scip

)

creates the all variables full strong LP branching rule and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 571 of file branch_allfullstrong.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecPs(), SCIPsetBranchruleFree(), and SCIPsetBranchruleInit().

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeDefaultPlugins().