Scippy

SCIP

Solving Constraint Integer Programs

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_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"

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "all variables full strong branching"

Definition at line 60 of file branch_allfullstrong.c.

Referenced by SCIPincludeBranchruleAllfullstrong().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   -1000

Definition at line 61 of file branch_allfullstrong.c.

Referenced by SCIPincludeBranchruleAllfullstrong().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 62 of file branch_allfullstrong.c.

Referenced by SCIPincludeBranchruleAllfullstrong().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 63 of file branch_allfullstrong.c.

Referenced by SCIPincludeBranchruleAllfullstrong().

Function Documentation

◆ branch()

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyAllfullstrong  )
static

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

Definition at line 195 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 209 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 227 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 241 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 257 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
sciporiginal SCIP data structure
pseudocandsbranching candidates
skipdownshould down branchings be skipped?
skipupshould up branchings be skipped?
npseudocandsnumber of branching candidates
npriopseudocandsnumber of priority branching candidates
bestpseudocandbest candidate for branching
bestdownobjective value of the down branch for bestcand
bestupobjective value of the up branch for bestcand
bestscorescore for bestcand
bestdownvalidis bestdown a valid dual bound for the down branch?
bestupvalidis bestup a valid dual bound for the up branch?
provedboundproved dual bound for current subtree
resultresult pointer

Definition at line 285 of file branch_allfullstrong.c.

References BRANCHRULE_NAME, FALSE, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, 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(), SCIPisExactSolve(), SCIPisFeasIntegral(), SCIPisGE(), SCIPprintDisplayLine(), SCIPstartStrongbranch(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsInLP(), SCIPverbMessage(), and TRUE.

Referenced by branch(), and SCIP_DECL_BRANCHEXECLP().

◆ SCIPincludeBranchruleAllfullstrong()