Detailed Description
all variables full strong LP branching rule
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" |
Definition at line 68 of file branch_allfullstrong.c.
Referenced by branch(), SCIP_DECL_BRANCHCOPY(), SCIPincludeBranchruleAllfullstrong(), and SCIPselectVarPseudoStrongBranching().
◆ BRANCHRULE_DESC
#define BRANCHRULE_DESC "all variables full strong branching" |
Definition at line 69 of file branch_allfullstrong.c.
Referenced by SCIPincludeBranchruleAllfullstrong().
◆ BRANCHRULE_PRIORITY
#define BRANCHRULE_PRIORITY -1000 |
Definition at line 70 of file branch_allfullstrong.c.
Referenced by SCIPincludeBranchruleAllfullstrong().
◆ BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 71 of file branch_allfullstrong.c.
Referenced by SCIPincludeBranchruleAllfullstrong().
◆ BRANCHRULE_MAXBOUNDDIST
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 72 of file branch_allfullstrong.c.
Referenced by SCIPincludeBranchruleAllfullstrong().
Function Documentation
◆ branch()
|
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 87 of file branch_allfullstrong.c.
References BMSclearMemoryArray, BRANCHRULE_NAME, MAX, 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(), SCIPgetNVars(), SCIPgetPseudoBranchCands(), SCIPisExactSolve(), SCIPisLT(), SCIPnodeGetLowerbound(), SCIPselectVarPseudoStrongBranching(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), and SCIPvarGetUbLocal().
Referenced by enforceConstraint(), enforceSolution(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().
◆ SCIP_DECL_BRANCHCOPY()
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 204 of file branch_allfullstrong.c.
References BRANCHRULE_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetName(), and SCIPincludeBranchruleAllfullstrong().
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 218 of file branch_allfullstrong.c.
References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.
◆ SCIP_DECL_BRANCHINIT()
|
static |
initialization method of branching rule (called after problem was transformed)
Definition at line 236 of file branch_allfullstrong.c.
References SCIP_OKAY, and SCIPbranchruleGetData().
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 250 of file branch_allfullstrong.c.
References branch(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and SCIPdebugMsg.
◆ SCIP_DECL_BRANCHEXECPS()
|
static |
branching execution method for not completely fixed pseudo solutions
Definition at line 266 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 294 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()
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 586 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().