Detailed Description

full strong LP branching rule

Author: Tobias Achterberg

The full strong branching rule applies strong branching to every fractional variable of the LP solution 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_fullstrong.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeBranchruleFullstrong (SCIP *scip)

SCIP_RETCODE	SCIPselectVarStrongBranching (SCIP scip, SCIP_VAR lpcands, SCIP_Real lpcandssol, SCIP_Real lpcandsfrac, SCIP_Bool skipdown, SCIP_Bool skipup, int nlpcands, int npriolpcands, int ncomplete, int start, SCIP_Bool allowaddcons, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int bestcand, SCIP_Real bestdown, SCIP_Real bestup, SCIP_Real bestscore, SCIP_Bool bestdownvalid, SCIP_Bool bestupvalid, SCIP_Real provedbound, SCIP_RESULT result)

Function Documentation

SCIP_RETCODE SCIPincludeBranchruleFullstrong ( SCIP * scip )

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

Parameters

scip	SCIP data structure

Definition at line 643 of file branch_fullstrong.c.

References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_FORCESTRONGBRANCH, DEFAULT_MAXPROPROUNDS, DEFAULT_PROBINGBOUNDS, DEFAULT_REEVALAGE, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPallocMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExit(), SCIPsetBranchruleFree(), SCIPsetBranchruleInit(), and TRUE.

Referenced by SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPselectVarStrongBranching	(	SCIP *	scip,
		SCIP_VAR **	lpcands,
		SCIP_Real *	lpcandssol,
		SCIP_Real *	lpcandsfrac,
		SCIP_Bool *	skipdown,
		SCIP_Bool *	skipup,
		int	nlpcands,
		int	npriolpcands,
		int	ncomplete,
		int *	start,
		SCIP_Bool	allowaddcons,
		int	maxproprounds,
		SCIP_Bool	probingbounds,
		SCIP_Bool	forcestrongbranch,
		int *	bestcand,
		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
lpcands	branching candidates
lpcandssol	solution values of the branching candidates
lpcandsfrac	fractional values of the branching candidates
skipdown	should down branchings be skipped?
skipup	should up branchings be skipped?
nlpcands	number of branching candidates
npriolpcands	number of priority branching candidates
ncomplete	number of branching candidates without skip
start	starting index in lpcands
allowaddcons	is the branching rule allowed to add constraints?
maxproprounds	maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)
probingbounds	should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?
forcestrongbranch	should strong branching be applied even if there is just a single candidate?
bestcand	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 148 of file branch_fullstrong.c.

References BRANCHRULE_NAME, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DECL_BRANCHEXECLP(), SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPdebugMessage, SCIPendStrongbranch(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfindBranchrule(), SCIPfreeBufferArray, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetVars(), SCIPgetVarStrongbranchFrac(), SCIPgetVarStrongbranchLast(), SCIPgetVarStrongbranchLPAge(), SCIPgetVarStrongbranchNode(), SCIPgetVarStrongbranchWithPropagation(), SCIPinfinity(), SCIPisExactSolve(), SCIPisFeasZero(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPprintDisplayLine(), SCIPstartStrongbranch(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_BRANCHEXECLP().

SCIP

Detailed Description

Functions

Function Documentation