Detailed Description

pseudo costs branching rule

Author: Tobias Achterberg; Stefan Vigerske

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

Definition at line 53 of file branch_pscost.c.

Referenced by SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECEXT(), SCIP_DECL_BRANCHEXECLP(), SCIPincludeBranchrulePscost(), and SCIPselectBranchVarPscost().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC "branching on pseudo cost values"

Definition at line 54 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY 2000

Definition at line 55 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH -1

Definition at line 56 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST 1.0

Definition at line 57 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 59 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_STRATEGY_DEFAULT

#define BRANCHRULE_STRATEGY_DEFAULT 'u'

default pseudo cost multiplication strategy

Definition at line 60 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 61 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 62 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 63 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 64 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 65 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 66 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 67 of file branch_pscost.c.

Referenced by SCIPincludeBranchrulePscost().

◆ BRANCHRULE_RANDSEED_DEFAULT

#define BRANCHRULE_RANDSEED_DEFAULT 47

initial random seed

Definition at line 68 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 71 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

scip	SCIP data structure
branchruledata	branching rule data
bestvar	best branching candidate
bestbrpoint	branching point for best branching candidate
bestscore	score of best branching candidate
bestrndscore	random score of the best branching candidate
cand	branching candidate to consider
candscoremin	minimal score of branching candidate
candscoremax	maximal score of branching candidate
candscoresum	sum of scores of branching candidate
candrndscore	random score of branching candidate
candsol	proposed branching point of branching candidate

Definition at line 98 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

scip	SCIP data structure
branchrule	branching rule
cands	array of branching candidates
candssol	array of candidate solution values
candsscore	array of candidate scores
ncands	the number of candidates
brvar	pointer to store the selected branching candidate or NULL if none
brpoint	pointer to store branching point of selected branching variable

Definition at line 451 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 561 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 575 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 595 of file branch_pscost.c.

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

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpPscost )

static

branching execution method for fractional LP solutions

Definition at line 610 of file branch_pscost.c.

References BRANCHRULE_NAME, NULL, REALABS, SCIP_BRANCHED, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetName(), SCIPbranchVar(), SCIPdebugMsg, SCIPgetLPBranchCands(), SCIPgetVarPseudocostScore(), SCIPinfinity(), SCIPisFeasIntegral(), SCIPisSumEQ(), SCIPisSumGT(), SCIPvarGetName(), SCIPvarGetRootSol(), SCIPvarGetSol(), and TRUE.

◆ SCIP_DECL_BRANCHEXECEXT()

static SCIP_DECL_BRANCHEXECEXT ( branchExecextPscost )

static

branching execution method for external candidates

Definition at line 668 of file branch_pscost.c.

References BRANCHRULE_NAME, NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPadjustedVarLb(), SCIPadjustedVarUb(), SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchVarValNary(), SCIPdebugMsg, SCIPgetCharParam(), SCIPgetCurrentNode(), SCIPgetExternBranchCands(), SCIPisEQ(), SCIPisInfinity(), SCIPnodeGetDepth(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetProbvar(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), and selectBranchVar().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BRANCHRULE_NAME

◆ BRANCHRULE_DESC

◆ BRANCHRULE_PRIORITY

◆ BRANCHRULE_MAXDEPTH

◆ BRANCHRULE_MAXBOUNDDIST

◆ BRANCHRULE_STRATEGIES

◆ BRANCHRULE_STRATEGY_DEFAULT

◆ BRANCHRULE_SCOREMINWEIGHT_DEFAULT

◆ BRANCHRULE_SCOREMAXWEIGHT_DEFAULT

◆ BRANCHRULE_SCORESUMWEIGHT_DEFAULT

◆ BRANCHRULE_NCHILDREN_DEFAULT

◆ BRANCHRULE_NARYMAXDEPTH_DEFAULT

◆ BRANCHRULE_NARYMINWIDTH_DEFAULT

◆ BRANCHRULE_NARYWIDTHFAC_DEFAULT

◆ BRANCHRULE_RANDSEED_DEFAULT

◆ WEIGHTEDSCORING

Function Documentation

◆ updateBestCandidate()

◆ selectBranchVar()

◆ SCIP_DECL_BRANCHCOPY()

◆ SCIP_DECL_BRANCHFREE()

◆ SCIP_DECL_BRANCHINIT()

◆ SCIP_DECL_BRANCHEXECLP()

◆ SCIP_DECL_BRANCHEXECEXT()