branch_allfullstrong.c 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.c.

#include "blockmemshell/memory.h"
#include "scip/branch_allfullstrong.h"
#include "scip/pub_branch.h"
#include "scip/pub_message.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_exact.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_prob.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	BRANCHRULE_NAME   "allfullstrong"
#define	BRANCHRULE_DESC   "all variables full strong branching"
#define	BRANCHRULE_PRIORITY   -1000
#define	BRANCHRULE_MAXDEPTH   -1
#define	BRANCHRULE_MAXBOUNDDIST   1.0

Functions
static SCIP_RETCODE	branch (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_RESULT *result)
static	SCIP_DECL_BRANCHCOPY (branchCopyAllfullstrong)
static	SCIP_DECL_BRANCHFREE (branchFreeAllfullstrong)
static	SCIP_DECL_BRANCHINIT (branchInitAllfullstrong)
static	SCIP_DECL_BRANCHEXECLP (branchExeclpAllfullstrong)
static	SCIP_DECL_BRANCHEXECPS (branchExecpsAllfullstrong)
SCIP_RETCODE	SCIPselectVarPseudoStrongBranching (SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, 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)

Macro Definition Documentation

BRANCHRULE_NAME

#define BRANCHRULE_NAME   "allfullstrong"

Definition at line 69 of file branch_allfullstrong.c.

BRANCHRULE_DESC

#define BRANCHRULE_DESC   "all variables full strong branching"

Definition at line 70 of file branch_allfullstrong.c.

BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   -1000

Definition at line 71 of file branch_allfullstrong.c.

BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 72 of file branch_allfullstrong.c.

BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 73 of file branch_allfullstrong.c.

Function Documentation

branch()

static SCIP_RETCODE branch ( SCIP *  scip, SCIP_BRANCHRULE *  branchrule, SCIP_RESULT *  result  )

static

performs the all fullstrong branching

Parameters

scip	SCIP data structure
branchrule	branching rule
result	pointer to store the result of the callback method

Definition at line 88 of file branch_allfullstrong.c.

References BMSclearMemoryArray, BRANCHRULE_NAME, NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPallColsInLP(), SCIPallocBlockMemoryArray, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchVarVal(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLocalLowerbound(), SCIPgetNVars(), SCIPgetPseudoBranchCands(), SCIPisExact(), SCIPisLT(), SCIPnodeGetLowerbound(), SCIPselectVarPseudoStrongBranching(), SCIPupdateLocalLowerbound(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by enforceConstraint(), enforceSolution(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyAllfullstrong  )

static

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

Definition at line 206 of file branch_allfullstrong.c.

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

SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeAllfullstrong  )

static

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

Definition at line 220 of file branch_allfullstrong.c.

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

SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitAllfullstrong  )

static

initialization method of branching rule (called after problem was transformed)

Definition at line 238 of file branch_allfullstrong.c.

References SCIP_OKAY, and SCIPbranchruleGetData().

SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpAllfullstrong  )

static

branching execution method for fractional LP solutions

Definition at line 252 of file branch_allfullstrong.c.

References branch(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and SCIPdebugMsg.

SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsAllfullstrong  )

static

branching execution method for not completely fixed pseudo solutions

Definition at line 268 of file branch_allfullstrong.c.

References branch(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPdebugMsg, and SCIPhasCurrentNodeLP().

SCIPselectVarPseudoStrongBranching()

SCIP_RETCODE SCIPselectVarPseudoStrongBranching	(	SCIP *	scip,
		SCIP_VAR **	pseudocands,
		SCIP_Bool *	skipdown,
		SCIP_Bool *	skipup,
		int	npseudocands,
		int	npriopseudocands,
		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
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 296 of file branch_allfullstrong.c.

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

Referenced by branch(), and SCIP_DECL_BRANCHEXECLP().

SCIPincludeBranchruleAllfullstrong()

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 587 of file branch_allfullstrong.c.

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

Referenced by SCIP_DECL_BRANCHCOPY(), SCIPincludeColoringPlugins(), and SCIPincludeDefaultPlugins().