Scippy

SCIP

Solving Constraint Integer Programs

branch_pscost.c File Reference

Detailed Description

pseudo costs branching rule

Author
Tobias Achterberg
Stefan Vigerske

Definition in file branch_pscost.c.

#include "blockmemshell/memory.h"
#include "scip/branch_pscost.h"
#include "scip/pub_branch.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.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   "pscost"
 
#define BRANCHRULE_DESC   "branching on pseudo cost values"
 
#define BRANCHRULE_PRIORITY   2000
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define BRANCHRULE_STRATEGIES   "dsuv"
 
#define BRANCHRULE_STRATEGY_DEFAULT   'u'
 
#define BRANCHRULE_SCOREMINWEIGHT_DEFAULT   0.8
 
#define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT   1.3
 
#define BRANCHRULE_SCORESUMWEIGHT_DEFAULT   0.1
 
#define BRANCHRULE_NCHILDREN_DEFAULT   2
 
#define BRANCHRULE_NARYMAXDEPTH_DEFAULT   -1
 
#define BRANCHRULE_NARYMINWIDTH_DEFAULT   0.001
 
#define BRANCHRULE_NARYWIDTHFAC_DEFAULT   2.0
 
#define BRANCHRULE_RANDSEED_DEFAULT   47
 
#define WEIGHTEDSCORING(data, min, max, sum)   ((data)->scoreminweight * (min) + (data)->scoremaxweight * (max) + (data)->scoresumweight * (sum))
 

Functions

static SCIP_RETCODE updateBestCandidate (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR **bestvar, SCIP_Real *bestbrpoint, SCIP_Real *bestscore, SCIP_Real *bestrndscore, SCIP_VAR *cand, SCIP_Real candscoremin, SCIP_Real candscoremax, SCIP_Real candscoresum, SCIP_Real candrndscore, SCIP_Real candsol)
 
static SCIP_RETCODE selectBranchVar (SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **cands, SCIP_Real *candssol, SCIP_Real *candsscore, int ncands, SCIP_VAR **brvar, SCIP_Real *brpoint)
 
static SCIP_DECL_BRANCHCOPY (branchCopyPscost)
 
static SCIP_DECL_BRANCHFREE (branchFreePscost)
 
static SCIP_DECL_BRANCHINIT (branchInitPscost)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpPscost)
 
static SCIP_DECL_BRANCHEXECEXT (branchExecextPscost)
 
SCIP_RETCODE SCIPincludeBranchrulePscost (SCIP *scip)
 
SCIP_RETCODE SCIPselectBranchVarPscost (SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsscore, int nbranchcands, SCIP_VAR **var, SCIP_Real *brpoint)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "pscost"

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "branching on pseudo cost values"

Definition at line 44 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   2000

Definition at line 45 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 46 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 47 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_STRATEGIES

#define BRANCHRULE_STRATEGIES   "dsuv"

possible pseudo cost multiplication strategies for branching on external candidates

Definition at line 49 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_STRATEGY_DEFAULT

#define BRANCHRULE_STRATEGY_DEFAULT   'u'

default pseudo cost multiplication strategy

Definition at line 50 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_SCOREMINWEIGHT_DEFAULT

#define BRANCHRULE_SCOREMINWEIGHT_DEFAULT   0.8

default weight for minimum of scores of a branching candidate

Definition at line 51 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_SCOREMAXWEIGHT_DEFAULT

#define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT   1.3

default weight for maximum of scores of a branching candidate

Definition at line 52 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_SCORESUMWEIGHT_DEFAULT

#define BRANCHRULE_SCORESUMWEIGHT_DEFAULT   0.1

default weight for sum of scores of a branching candidate

Definition at line 53 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_NCHILDREN_DEFAULT

#define BRANCHRULE_NCHILDREN_DEFAULT   2

default number of children in n-ary branching

Definition at line 54 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_NARYMAXDEPTH_DEFAULT

#define BRANCHRULE_NARYMAXDEPTH_DEFAULT   -1

default maximal depth where to do n-ary branching

Definition at line 55 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_NARYMINWIDTH_DEFAULT

#define BRANCHRULE_NARYMINWIDTH_DEFAULT   0.001

default minimal domain width in children when doing n-ary branching

Definition at line 56 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_NARYWIDTHFAC_DEFAULT

#define BRANCHRULE_NARYWIDTHFAC_DEFAULT   2.0

default factor of domain width in n-ary branching

Definition at line 57 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_RANDSEED_DEFAULT

#define BRANCHRULE_RANDSEED_DEFAULT   47

initial random seed

Definition at line 58 of file branch_pscost.c.

Referenced by SCIP_DECL_BRANCHINIT(), and SCIPincludeBranchrulePscost().

◆ WEIGHTEDSCORING

#define WEIGHTEDSCORING (   data,
  min,
  max,
  sum 
)    ((data)->scoreminweight * (min) + (data)->scoremaxweight * (max) + (data)->scoresumweight * (sum))

Definition at line 61 of file branch_pscost.c.

Referenced by updateBestCandidate().

Function Documentation

◆ updateBestCandidate()

static SCIP_RETCODE updateBestCandidate ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
SCIP_VAR **  bestvar,
SCIP_Real bestbrpoint,
SCIP_Real bestscore,
SCIP_Real bestrndscore,
SCIP_VAR cand,
SCIP_Real  candscoremin,
SCIP_Real  candscoremax,
SCIP_Real  candscoresum,
SCIP_Real  candrndscore,
SCIP_Real  candsol 
)
static

checks if a given branching candidate is better than a previous one and updates the best branching candidate accordingly

Parameters
scipSCIP data structure
branchruledatabranching rule data
bestvarbest branching candidate
bestbrpointbranching point for best branching candidate
bestscorescore of best branching candidate
bestrndscorerandom score of the best branching candidate
candbranching candidate to consider
candscoreminminimal score of branching candidate
candscoremaxmaximal score of branching candidate
candscoresumsum of scores of branching candidate
candrndscorerandom score of branching candidate
candsolproposed branching point of branching candidate

Definition at line 88 of file branch_pscost.c.

References FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_CONTINUOUS, SCIPABORT, SCIPadjustedVarLb(), SCIPadjustedVarUb(), SCIPcomputeVarLbLocal(), SCIPcomputeVarUbLocal(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetBranchingPoint(), SCIPgetBranchScore(), SCIPgetSolVal(), SCIPgetVarPseudocostVal(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisHugeValue(), SCIPisInfinity(), SCIPisIntegral(), SCIPisNegative(), SCIPisSumEQ(), SCIPisSumGT(), SCIPrandomGetReal(), SCIPrelDiff(), SCIPvarGetLbLocal(), SCIPvarGetMultaggrNVars(), SCIPvarGetMultaggrScalars(), SCIPvarGetMultaggrVars(), SCIPvarGetName(), SCIPvarGetProbvar(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsActive(), TRUE, and WEIGHTEDSCORING.

Referenced by selectBranchVar().

◆ selectBranchVar()

static SCIP_RETCODE selectBranchVar ( SCIP scip,
SCIP_BRANCHRULE branchrule,
SCIP_VAR **  cands,
SCIP_Real candssol,
SCIP_Real candsscore,
int  ncands,
SCIP_VAR **  brvar,
SCIP_Real brpoint 
)
static

selects the branching variable from given candidate array

Parameters
scipSCIP data structure
branchrulebranching rule
candsarray of branching candidates
candssolarray of candidate solution values
candsscorearray of candidate scores
ncandsthe number of candidates
brvarpointer to store the selected branching candidate or NULL if none
brpointpointer to store branching point of selected branching variable

Definition at line 441 of file branch_pscost.c.

References NULL, REALABS, SCIP_BRANCHERROR, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPduplicateBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPisEQ(), SCIPisInfinity(), SCIPrandomGetReal(), SCIPsortPtrInt(), SCIPvarCompare(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and updateBestCandidate().

Referenced by SCIP_DECL_BRANCHEXECEXT(), and SCIPselectBranchVarPscost().

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyPscost  )
static

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

Definition at line 551 of file branch_pscost.c.

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

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreePscost  )
static

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

Definition at line 565 of file branch_pscost.c.

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

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitPscost  )
static

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

Definition at line 585 of file branch_pscost.c.

References BRANCHRULE_RANDSEED_DEFAULT, NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPsetRandomSeed().

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpPscost  )
static

◆ SCIP_DECL_BRANCHEXECEXT()