Scippy

SCIP

Solving Constraint Integer Programs

branch_fullstrong.c File Reference

Detailed Description

full strong LP branching rule

Author
Tobias Achterberg
Gerald Gamrath

Definition in file branch_fullstrong.c.

#include <assert.h>
#include <string.h>
#include "scip/branch_fullstrong.h"

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "fullstrong"
 
#define BRANCHRULE_DESC   "full strong branching"
 
#define BRANCHRULE_PRIORITY   0
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define DEFAULT_REEVALAGE   10LL
 
#define DEFAULT_MAXPROPROUNDS   -2
 
#define DEFAULT_PROBINGBOUNDS   TRUE
 
#define DEFAULT_FORCESTRONGBRANCH   FALSE
 

Functions

static SCIP_DECL_BRANCHCOPY (branchCopyFullstrong)
 
static SCIP_DECL_BRANCHFREE (branchFreeFullstrong)
 
static SCIP_DECL_BRANCHINIT (branchInitFullstrong)
 
static SCIP_DECL_BRANCHEXIT (branchExitFullstrong)
 
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)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpFullstrong)
 
SCIP_RETCODE SCIPincludeBranchruleFullstrong (SCIP *scip)
 

Macro Definition Documentation

#define BRANCHRULE_NAME   "fullstrong"
#define BRANCHRULE_DESC   "full strong branching"

Definition at line 31 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define BRANCHRULE_PRIORITY   0

Definition at line 32 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 33 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 34 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define DEFAULT_REEVALAGE   10LL

number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node

Definition at line 36 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define DEFAULT_MAXPROPROUNDS   -2

maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)

Definition at line 39 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define DEFAULT_PROBINGBOUNDS   TRUE

should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?

Definition at line 42 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

#define DEFAULT_FORCESTRONGBRANCH   FALSE

should strong branching be applied even if there is just a single candidate?

Definition at line 45 of file branch_fullstrong.c.

Referenced by SCIPincludeBranchruleFullstrong().

Function Documentation

static SCIP_DECL_BRANCHCOPY ( branchCopyFullstrong  )
static

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

Definition at line 70 of file branch_fullstrong.c.

static SCIP_DECL_BRANCHFREE ( branchFreeFullstrong  )
static

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

Definition at line 84 of file branch_fullstrong.c.

static SCIP_DECL_BRANCHINIT ( branchInitFullstrong  )
static

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

Definition at line 104 of file branch_fullstrong.c.

static SCIP_DECL_BRANCHEXIT ( branchExitFullstrong  )
static

deinitialization method of branching rule (called before transformed problem is freed)

Definition at line 119 of file branch_fullstrong.c.

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().

static SCIP_DECL_BRANCHEXECLP ( branchExeclpFullstrong  )
static

branching execution method for fractional LP solutions

Definition at line 525 of file branch_fullstrong.c.

Referenced by SCIPselectVarStrongBranching().