Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

inference history branching rule

Author
Tobias Achterberg
Timo Berthold
Stefan Heinz

Definition in file branch_inference.c.

#include "scip/branch_inference.h"
#include "scip/pub_branch.h"
#include "scip/pub_history.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_message.h"
#include "scip/scip_mem.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_var.h"
#include <string.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
 
#define DEFAULT_CONFLICTPRIO   1
 
#define DEFAULT_CUTOFFPRIO   1
 

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 *scip, SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval, SCIP_VAR **bestcands, int *nbestcands)
 
static void tiebreakAggrCand (SCIP_VAR **bestcands, int nbestcands)
 
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_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
 
static void selectBestCands (SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_VAR **bestcands, int *nbestcands)
 
static SCIP_RETCODE performBranchingSol (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, int conflictprio, int cutoffprio)
 
static SCIP_RETCODE performBranchingNoSol (SCIP *scip, SCIP_VAR **cands, 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

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "inference"

Definition at line 54 of file branch_inference.c.

Referenced by SCIP_DECL_BRANCHCOPY(), and SCIPincludeBranchruleInference().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "inference history branching"

Definition at line 55 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   1000

Definition at line 56 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 57 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 58 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CONFLICTWEIGHT

#define DEFAULT_CONFLICTWEIGHT   1000.0

weight in score calculations for conflict score

Definition at line 67 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CUTOFFWEIGHT

#define DEFAULT_CUTOFFWEIGHT   1.0

weight in score calculations for cutoff score

Definition at line 68 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_INFERENCEWEIGHT

#define DEFAULT_INFERENCEWEIGHT   1.0

weight in score calculations for inference score

Definition at line 69 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_RELIABLESCORE

#define DEFAULT_RELIABLESCORE   0.001

score which is seen to be reliable for a branching decision

Definition at line 70 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_FRACTIONALS

#define DEFAULT_FRACTIONALS   TRUE

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

Definition at line 71 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_USEWEIGHTEDSUM

#define DEFAULT_USEWEIGHTEDSUM   TRUE

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

Definition at line 72 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CONFLICTPRIO

#define DEFAULT_CONFLICTPRIO   1

priority value for using conflict weights in lex. order

Definition at line 74 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

◆ DEFAULT_CUTOFFPRIO

#define DEFAULT_CUTOFFPRIO   1

priority value for using cutoff weights in lex. order

Definition at line 75 of file branch_inference.c.

Referenced by SCIPincludeBranchruleInference().

Function Documentation

◆ evaluateValueCand()

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, tiebreaking included

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 94 of file branch_inference.c.

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

Referenced by performBranchingNoSol().

◆ evaluateAggrCand()

static void evaluateAggrCand ( SCIP scip,
SCIP_VAR cand,
SCIP_Real  score,
SCIP_Real  val,
SCIP_VAR **  bestcand,
SCIP_Real bestscore,
SCIP_Real bestval,
SCIP_VAR **  bestcands,
int *  nbestcands 
)
static

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

Parameters
scipSCIP data structure
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
bestcandsbuffer array to return selected candidates
nbestcandspointer to return number of selected candidates

Definition at line 148 of file branch_inference.c.

References SCIPisEQ().

Referenced by performBranchingNoSol(), and selectBestCands().

◆ tiebreakAggrCand()

static void tiebreakAggrCand ( SCIP_VAR **  bestcands,
int  nbestcands 
)
static

choose a singular best candidate from bestcands and move it to the beginning of the candidate array

Parameters
bestcandsbuffer array to return selected candidates
nbestcandsnumber of selected candidates

Definition at line 182 of file branch_inference.c.

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

Referenced by performBranchingSol().

◆ checkValueScore()

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 221 of file branch_inference.c.

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

Referenced by getValueScore().

◆ getAggrScore()

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 263 of file branch_inference.c.

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

Referenced by performBranchingNoSol(), and selectBestCands().

◆ getValueScore()

static SCIP_Real getValueScore ( 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
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 294 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 performBranchingNoSol().

◆ selectBestCands()

static void selectBestCands ( SCIP scip,
SCIP_VAR **  cands,
SCIP_Real candsols,
int  ncands,
SCIP_Real  conflictweight,
SCIP_Real  inferenceweight,
SCIP_Real  cutoffweight,
SCIP_Real  reliablescore,
SCIP_VAR **  bestcands,
int *  nbestcands 
)
static
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
bestcandsbuffer array to return selected candidates
nbestcandspointer to return number of selected candidates

Definition at line 349 of file branch_inference.c.

References evaluateAggrCand(), getAggrScore(), NULL, SCIP_Real, SCIP_UNKNOWN, SCIPdebugMsg, SCIPgetVarSol(), SCIPvarGetBranchPriority(), and SCIPvarGetName().

Referenced by performBranchingSol().

◆ performBranchingSol()

static SCIP_RETCODE performBranchingSol ( 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,
int  conflictprio,
int  cutoffprio 
)
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, ...)
conflictpriopriority value for using conflict weights in lex. order
cutoffpriopriority value for using conflict weights in lex. order

Definition at line 403 of file branch_inference.c.

References FALSE, NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_UNKNOWN, SCIPallocClearBufferArray, SCIPbranchVarVal(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBranchingPoint(), SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), selectBestCands(), and tiebreakAggrCand().

Referenced by SCIP_DECL_BRANCHEXECEXT().

◆ performBranchingNoSol()

static SCIP_RETCODE performBranchingNoSol ( SCIP scip,
SCIP_VAR **  cands,
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
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 543 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, SCIPallocBufferArray, SCIPbranchVar(), SCIPcalcChildEstimate(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPcreateChild(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarAvgInferenceCutoffScore(), SCIPgetVarAvgInferenceScore(), SCIPgetVarConflictScore(), SCIPgetVarSol(), SCIPisEQ(), SCIPvarGetBranchPriority(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_BRANCHEXECLP(), and SCIP_DECL_BRANCHEXECPS().

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyInference  )
static

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

Definition at line 760 of file branch_inference.c.

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

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeInference  )
static

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

Definition at line 774 of file branch_inference.c.

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

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpInference  )
static

branching execution method for fractional LP solutions

Definition at line 788 of file branch_inference.c.

References NULL, performBranchingNoSol(), SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMsg, SCIPgetLPBranchCands(), and SCIPgetPseudoBranchCands().

◆ SCIP_DECL_BRANCHEXECEXT()

static SCIP_DECL_BRANCHEXECEXT ( branchExecextInference  )
static

branching execution method for external candidates

Definition at line 822 of file branch_inference.c.

References NULL, performBranchingSol(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbranchruleGetData(), SCIPdebugMsg, and SCIPgetExternBranchCands().

◆ SCIP_DECL_BRANCHEXECPS()

static SCIP_DECL_BRANCHEXECPS ( branchExecpsInference  )
static

branching execution method for not completely fixed pseudo solutions

Definition at line 849 of file branch_inference.c.

References NULL, performBranchingNoSol(), SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPdebugMsg, and SCIPgetPseudoBranchCands().