Scippy

SCIP

Solving Constraint Integer Programs

branch_fullstrong.h File Reference

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 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
sciporiginal SCIP data structure
lpcandsbranching candidates
lpcandssolsolution values of the branching candidates
lpcandsfracfractional values of the branching candidates
skipdownshould down branchings be skipped?
skipupshould up branchings be skipped?
nlpcandsnumber of branching candidates
npriolpcandsnumber of priority branching candidates
ncompletenumber of branching candidates without skip
startstarting index in lpcands
allowaddconsis the branching rule allowed to add constraints?
maxproproundsmaximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)
probingboundsshould valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?
forcestrongbranchshould strong branching be applied even if there is just a single candidate?
bestcandbest 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 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().