Scippy

SCIP

Solving Constraint Integer Programs

branch_inference.c File Reference

Detailed Description

inference history branching rule

Author
Tobias Achterberg
Timo Berthold
Stefan Heinz

Definition in file branch_inference.c.

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

Go to the source code of this file.

Macros

Branching rule properties
#define BRANCHRULE_NAME   "inference"
 
#define BRANCHRULE_DESC   "inference history branching"
 
#define BRANCHRULE_PRIORITY   1000
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
Default parameter values
#define DEFAULT_CONFLICTWEIGHT   1000.0
 
#define DEFAULT_CUTOFFWEIGHT   1.0
 
#define DEFAULT_INFERENCEWEIGHT   1.0
 
#define DEFAULT_RELIABLESCORE   0.001
 
#define DEFAULT_FRACTIONALS   TRUE
 
#define DEFAULT_USEWEIGHTEDSUM   TRUE
 

Functions

static void evaluateValueCand (SCIP_VAR *cand, SCIP_Real score, SCIP_Real branchpoint, SCIP_BRANCHDIR branchdir, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestbranchpoint, SCIP_BRANCHDIR *bestbranchdir)
 
static void evaluateAggrCand (SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval)
 
static void checkValueScore (SCIP_Real value, SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *bestscore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
 
static SCIP_Real getAggrScore (SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore)
 
static SCIP_Real getValueScore (SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
 
static SCIP_RETCODE performBranching (SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result)
 
static SCIP_DECL_BRANCHCOPY (branchCopyInference)
 
static SCIP_DECL_BRANCHFREE (branchFreeInference)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpInference)
 
static SCIP_DECL_BRANCHEXECEXT (branchExecextInference)
 
static SCIP_DECL_BRANCHEXECPS (branchExecpsInference)
 
SCIP_RETCODE SCIPincludeBranchruleInference (SCIP *scip)
 

Macro Definition Documentation

#define BRANCHRULE_NAME   "inference"

Definition at line 36 of file branch_inference.c.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeBranchruleInference().

#define BRANCHRULE_DESC   "inference history branching"

Definition at line 37 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define BRANCHRULE_PRIORITY   1000

Definition at line 38 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 39 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 40 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_CONFLICTWEIGHT   1000.0

weight in score calculations for conflict score

Definition at line 49 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_CUTOFFWEIGHT   1.0

weight in score calculations for cutoff score

Definition at line 50 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_INFERENCEWEIGHT   1.0

weight in score calculations for inference score

Definition at line 51 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_RELIABLESCORE   0.001

score which is seen to be reliable for a branching decision

Definition at line 52 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_FRACTIONALS   TRUE

should branching on LP solution be restricted to the fractional variables?

Definition at line 53 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

#define DEFAULT_USEWEIGHTEDSUM   TRUE

should a weighted sum of inference, conflict and cutoff weights be used?

Definition at line 54 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

Function Documentation

static void evaluateValueCand ( SCIP_VAR cand,
SCIP_Real  score,
SCIP_Real  branchpoint,
SCIP_BRANCHDIR  branchdir,
SCIP_VAR **  bestcand,
SCIP_Real bestscore,
SCIP_Real bestbranchpoint,
SCIP_BRANCHDIR bestbranchdir 
)
static

evaluate the given candidate with the given score against the currently best know candidate

Parameters
candcandidate to be checked
scorescore of the candidate
branchpointpotential branching point
branchdirpotential branching direction
bestcandpointer to the currently best candidate
bestscorepointer to the score of the currently best candidate
bestbranchpointpointer to store the (best) branching point
bestbranchdirpointer to store the branching direction relative to the branching point

Definition at line 71 of file branch_inference.c.

References REALABS, SCIP_Real, SCIPvarGetIndex(), and SCIPvarGetObj().

Referenced by performBranching().

static void evaluateAggrCand ( SCIP_VAR cand,
SCIP_Real  score,
SCIP_Real  val,
SCIP_VAR **  bestcand,
SCIP_Real bestscore,
SCIP_Real bestval 
)
static

evaluate the given candidate with the given score against the currently best know candidate

Parameters
candcandidate to be checked
scorescore of the candidate
valsolution value of the candidate
bestcandpointer to the currently best candidate
bestscorepointer to the score of the currently best candidate
bestvalpointer to the solution value of the currently best candidate

Definition at line 125 of file branch_inference.c.

References REALABS, SCIP_Real, SCIPvarGetIndex(), and SCIPvarGetObj().

Referenced by performBranching().

static void checkValueScore ( SCIP_Real  value,
SCIP_HISTORY history,
SCIP_BRANCHDIR  dir,
SCIP_Real  conflictweight,
SCIP_Real  cutoffweight,
SCIP_Real  reliablescore,
SCIP_Real bestscore,
SCIP_Real branchpoint,
SCIP_BRANCHDIR branchdir 
)
static

check if the score for the given domain value and variable domain value is better than the current best know one

Parameters
valuedomain value
historyvariable history for given donain value
dirbranching direction
conflictweightweight in score calculations for conflict score
cutoffweightweight in score calculations for cutoff score
reliablescorescore which is seen to be reliable for a branching decision
bestscorepointer to store the best score
branchpointpointer to store the (best) branching point
branchdirpointer to store the branching direction relative to the branching point

Definition at line 175 of file branch_inference.c.

References SCIP_Real, SCIPhistoryGetCutoffSum(), and SCIPhistoryGetVSIDS().

Referenced by getValueScore().

static SCIP_Real getAggrScore ( SCIP scip,
SCIP_VAR var,
SCIP_Real  conflictweight,
SCIP_Real  inferenceweight,
SCIP_Real  cutoffweight,
SCIP_Real  reliablescore 
)
static

return an aggregated score for the given variable using the conflict score and cutoff score

Parameters
scipSCIP data structure
varproblem variable
conflictweightweight in score calculations for conflict score
inferenceweightweight in score calculations for inference score
cutoffweightweight in score calculations for cutoff score
reliablescorescore which is seen to be reliable for a branching decision

Definition at line 217 of file branch_inference.c.

References SCIP_Real, SCIPgetVarAvgInferenceCutoffScore(), and SCIPgetVarConflictScore().

Referenced by performBranching().

static SCIP_Real getValueScore ( SCIP scip,
SCIP_VAR var,
SCIP_Real  conflictweight,
SCIP_Real  cutoffweight,
SCIP_Real  reliablescore,
SCIP_Real branchpoint,
SCIP_BRANCHDIR branchdir 
)
static

return an aggregated score for the given variable using the conflict score and cutoff score

Parameters
scipSCIP data structure
varproblem variable
conflictweightweight in score calculations for conflict score
cutoffweightweight in score calculations for cutoff score
reliablescorescore which is seen to be reliable for a branching decision
branchpointpointer to store the branching point
branchdirpointer to store the branching direction relative to the branching point

Definition at line 248 of file branch_inference.c.

References checkValueScore(), NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_Real, SCIP_UNKNOWN, SCIPvaluehistoryGetHistories(), SCIPvaluehistoryGetNValues(), SCIPvaluehistoryGetValues(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and SCIPvarGetValuehistory().

Referenced by performBranching().

static SCIP_RETCODE performBranching ( SCIP scip,
SCIP_VAR **  cands,
SCIP_Real candsols,
int  ncands,
SCIP_Real  conflictweight,
SCIP_Real  inferenceweight,
SCIP_Real  cutoffweight,
SCIP_Real  reliablescore,
SCIP_Bool  useweightedsum,
SCIP_RESULT result 
)
static

selects a variable out of the given candidate array and performs the branching

Parameters
scipSCIP data structure
candscandidate array
candsolsarray of candidate solution values, or NULL
ncandsnumber of candidates
conflictweightweight in score calculations for conflict score
inferenceweightweight in score calculations for inference score
cutoffweightweight in score calculations for cutoff score
reliablescorescore which is seen to be reliable for a branching decision
useweightedsumshould a weighted sum of inference, conflict and cutoff weights be used?
resultbuffer to store result (branched, reduced domain, ...)

Definition at line 306 of file branch_inference.c.

References evaluateAggrCand(), evaluateValueCand(), getAggrScore(), getValueScore(), NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_UNKNOWN, SCIPbranchVar(), SCIPbranchVarVal(), SCIPcalcChildEstimate(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateChild(), SCIPdebugMessage, SCIPgetBranchingPoint(), SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_BRANCHEXECEXT(), SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

static SCIP_DECL_BRANCHCOPY ( branchCopyInference  )
static

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

Definition at line 536 of file branch_inference.c.

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

static SCIP_DECL_BRANCHFREE ( branchFreeInference  )
static

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

Definition at line 550 of file branch_inference.c.

References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeMemory.

static SCIP_DECL_BRANCHEXECLP ( branchExeclpInference  )
static

branching execution method for fractional LP solutions

Definition at line 564 of file branch_inference.c.

References NULL, performBranching(), SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMessage, SCIPgetLPBranchCands(), and SCIPgetPseudoBranchCands().

static SCIP_DECL_BRANCHEXECEXT ( branchExecextInference  )
static

branching execution method for external candidates

Definition at line 598 of file branch_inference.c.

References NULL, performBranching(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetData(), SCIPdebugMessage, and SCIPgetExternBranchCands().

static SCIP_DECL_BRANCHEXECPS ( branchExecpsInference  )
static

branching execution method for not completely fixed pseudo solutions

Definition at line 625 of file branch_inference.c.

References NULL, performBranching(), SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMessage, and SCIPgetPseudoBranchCands().