Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

methods for branching and inference history

Author
Tobias Achterberg

Definition in file history.c.

#include <assert.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/history.h"
#include "scip/pub_misc.h"
#include "scip/pub_history.h"
#include "scip/pub_message.h"
#include "scip/struct_history.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPhistoryCreate (SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
 
void SCIPhistoryFree (SCIP_HISTORY **history, BMS_BLKMEM *blkmem)
 
void SCIPhistoryReset (SCIP_HISTORY *history)
 
void SCIPhistoryUnite (SCIP_HISTORY *history, SCIP_HISTORY *addhistory, SCIP_Bool switcheddirs)
 
void SCIPhistoryUpdatePseudocost (SCIP_HISTORY *history, SCIP_SET *set, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
 
SCIP_BRANCHDIR SCIPbranchdirOpposite (SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetPseudocost (SCIP_HISTORY *history, SCIP_Real solvaldelta)
 
SCIP_Real SCIPhistoryGetPseudocostVariance (SCIP_HISTORY *history, SCIP_BRANCHDIR direction)
 
SCIP_Real SCIPhistoryGetPseudocostCount (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Bool SCIPhistoryIsPseudocostEmpty (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
void SCIPhistoryIncVSIDS (SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
 
void SCIPhistoryScaleVSIDS (SCIP_HISTORY *history, SCIP_Real scalar)
 
SCIP_Real SCIPhistoryGetVSIDS (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
void SCIPhistoryIncNActiveConflicts (SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real length)
 
SCIP_Longint SCIPhistoryGetNActiveConflicts (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetAvgConflictlength (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
void SCIPhistoryIncNBranchings (SCIP_HISTORY *history, SCIP_BRANCHDIR dir, int depth)
 
void SCIPhistoryIncInferenceSum (SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
 
void SCIPhistoryIncCutoffSum (SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real weight)
 
SCIP_Longint SCIPhistoryGetNBranchings (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetInferenceSum (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetAvgInferences (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetCutoffSum (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetAvgCutoffs (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Real SCIPhistoryGetAvgBranchdepth (SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
 
SCIP_Bool SCIPhistoryIsRatioValid (SCIP_HISTORY *history)
 
SCIP_Real SCIPhistoryGetLastRatio (SCIP_HISTORY *history)
 
SCIP_Real SCIPhistoryGetLastBalance (SCIP_HISTORY *history)
 
void SCIPhistorySetRatioHistory (SCIP_HISTORY *history, SCIP_Bool valid, SCIP_Real ratio, SCIP_Real balance)
 
Value based history

Value based history methods

SCIP_RETCODE SCIPvaluehistoryCreate (SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
 
void SCIPvaluehistoryFree (SCIP_VALUEHISTORY **valuehistory, BMS_BLKMEM *blkmem)
 
SCIP_RETCODE SCIPvaluehistoryFind (SCIP_VALUEHISTORY *valuehistory, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Real value, SCIP_HISTORY **history)
 
void SCIPvaluehistoryScaleVSIDS (SCIP_VALUEHISTORY *valuehistory, SCIP_Real scalar)
 
int SCIPvaluehistoryGetNValues (SCIP_VALUEHISTORY *valuehistory)
 
SCIP_HISTORY ** SCIPvaluehistoryGetHistories (SCIP_VALUEHISTORY *valuehistory)
 
SCIP_RealSCIPvaluehistoryGetValues (SCIP_VALUEHISTORY *valuehistory)
 

Function Documentation

◆ SCIPhistoryCreate()

SCIP_RETCODE SCIPhistoryCreate ( SCIP_HISTORY **  history,
BMS_BLKMEM blkmem 
)

creates an empty history entry

Parameters
historypointer to store branching and inference history
blkmemblock memory

Definition at line 51 of file history.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPhistoryReset().

Referenced by SCIPreoptUpdateVarHistory(), SCIPstatCreate(), SCIPvaluehistoryFind(), and varCreate().

◆ SCIPhistoryFree()

void SCIPhistoryFree ( SCIP_HISTORY **  history,
BMS_BLKMEM blkmem 
)

frees a history entry

Parameters
historypointer to branching and inference history
blkmemblock memory

Definition at line 66 of file history.c.

References BMSfreeBlockMemory, and NULL.

Referenced by SCIPstatFree(), SCIPvaluehistoryFree(), and varFree().

◆ SCIPhistoryReset()

◆ SCIPhistoryUnite()

void SCIPhistoryUnite ( SCIP_HISTORY history,
SCIP_HISTORY addhistory,
SCIP_Bool  switcheddirs 
)

unites two history entries by adding the values of the second one to the first one

Parameters
historybranching and inference history
addhistoryhistory values to add to history
switcheddirsshould the history entries be united with switched directories

Definition at line 110 of file history.c.

References SCIP_History::branchdepthsum, SCIP_History::conflengthsum, SCIP_History::cutoffsum, SCIP_History::inferencesum, MAX, SCIP_History::nactiveconflicts, SCIP_History::nbranchings, NULL, SCIP_History::pscostcount, SCIP_History::pscostvariance, SCIP_History::pscostweightedmean, SCIP_Real, and SCIP_History::vsids.

Referenced by SCIPreoptUpdateVarHistory(), SCIPvarAggregate(), SCIPvarMergeHistories(), SCIPvarSetHistory(), and SCIPvarTransform().

◆ SCIPhistoryUpdatePseudocost()

void SCIPhistoryUpdatePseudocost ( SCIP_HISTORY history,
SCIP_SET set,
SCIP_Real  solvaldelta,
SCIP_Real  objdelta,
SCIP_Real  weight 
)

updates the pseudo costs for a change of "solvaldelta" in the variable's LP solution value and a change of "objdelta" in the LP's objective value

Parameters
historybranching and inference history
setglobal SCIP settings
solvaldeltadifference of variable's new LP value - old LP value
objdeltadifference of new LP's objective value - old LP's objective value
weightweight of this update in pseudo cost sum (added to pscostcount)

Definition at line 171 of file history.c.

References eps, MAX, NULL, SCIP_History::pscostcount, SCIP_History::pscostvariance, SCIP_History::pscostweightedmean, REALABS, SCIP_Real, SCIPsetDebugMsg, SCIPsetIsInfinity(), SCIPsetIsNegative(), SCIPsetIsPositive(), SCIPsetPseudocostdelta(), and SCIPsetPseudocosteps().

Referenced by SCIPvarUpdatePseudocost().

◆ SCIPbranchdirOpposite()

◆ SCIPhistoryGetPseudocost()

SCIP_Real SCIPhistoryGetPseudocost ( SCIP_HISTORY history,
SCIP_Real  solvaldelta 
)

returns the expected dual gain for moving the corresponding variable by "solvaldelta"

Parameters
historybranching and inference history
solvaldeltadifference of variable's new LP value - old LP value

Definition at line 439 of file history.c.

References NULL, SCIP_History::pscostcount, and SCIP_History::pscostweightedmean.

Referenced by SCIPgetAvgPseudocost(), SCIPgetAvgPseudocostCurrentRun(), SCIPgetAvgPseudocostScore(), SCIPgetAvgPseudocostScoreCurrentRun(), SCIPprintBranchingStatistics(), SCIPvarGetPseudocost(), and SCIPvarGetPseudocostCurrentRun().

◆ SCIPhistoryGetPseudocostVariance()

SCIP_Real SCIPhistoryGetPseudocostVariance ( SCIP_HISTORY history,
SCIP_BRANCHDIR  direction 
)

returns the variance of pseudo costs about the mean.

Parameters
historybranching and inference history
directiondirection of variable: 1 for upwards history, 0 for downwards history

Definition at line 453 of file history.c.

References NULL, SCIP_History::pscostcount, SCIP_History::pscostvariance, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, and SCIP_Real.

Referenced by SCIPgetPseudocostVariance(), SCIPprintBranchingStatistics(), and SCIPvarGetPseudocostVariance().

◆ SCIPhistoryGetPseudocostCount()

SCIP_Real SCIPhistoryGetPseudocostCount ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

returns the (possible fractional) number of (partial) pseudo cost updates performed on this pseudo cost entry in the given branching direction

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 477 of file history.c.

References NULL, SCIP_History::pscostcount, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPgetAvgPseudocostCount(), SCIPgetAvgPseudocostCountCurrentRun(), SCIPgetPseudocostCount(), SCIPprintBranchingStatistics(), SCIPvarGetPseudocost(), SCIPvarGetPseudocostCount(), SCIPvarGetPseudocostCountCurrentRun(), and SCIPvarGetPseudocostCurrentRun().

◆ SCIPhistoryIsPseudocostEmpty()

SCIP_Bool SCIPhistoryIsPseudocostEmpty ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

returns whether the pseudo cost entry is empty in the given branching direction (whether no value was added yet)

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 490 of file history.c.

References NULL, SCIP_History::pscostcount, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

◆ SCIPhistoryIncVSIDS()

void SCIPhistoryIncVSIDS ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir,
SCIP_Real  weight 
)

increases the conflict score of the history entry by the given weight

Parameters
historybranching and inference history
dirbranching direction
weightweight of this update in conflict score

Definition at line 503 of file history.c.

References NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, and SCIP_History::vsids.

Referenced by incVSIDS(), and SCIPvarIncVSIDS().

◆ SCIPhistoryScaleVSIDS()

void SCIPhistoryScaleVSIDS ( SCIP_HISTORY history,
SCIP_Real  scalar 
)

scales the conflict score values with the given scalar

Parameters
historybranching and inference history
scalarscalar to multiply the conflict scores with

Definition at line 517 of file history.c.

References NULL, and SCIP_History::vsids.

Referenced by SCIPconflictInit(), SCIPvaluehistoryScaleVSIDS(), and SCIPvarScaleVSIDS().

◆ SCIPhistoryGetVSIDS()

SCIP_Real SCIPhistoryGetVSIDS ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

gets the conflict score of the history entry

Parameters
historybranching and inference history
dirbranching direction

Definition at line 529 of file history.c.

References NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, and SCIP_History::vsids.

Referenced by checkValueScore(), SCIPgetAvgConflictScore(), SCIPgetAvgConflictScoreCurrentRun(), SCIPvarGetVSIDS(), SCIPvarGetVSIDS_rec(), SCIPvarGetVSIDSCurrentRun(), and SCIPvarIncVSIDS().

◆ SCIPhistoryIncNActiveConflicts()

void SCIPhistoryIncNActiveConflicts ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir,
SCIP_Real  length 
)

increases the number of active conflicts by one and the overall length of the history entry by the given weight

Parameters
historybranching and inference history
dirbranching direction
lengthlength of the conflict

Definition at line 542 of file history.c.

References SCIP_History::conflengthsum, SCIP_History::nactiveconflicts, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPvarIncNActiveConflicts(), and updateStatistics().

◆ SCIPhistoryGetNActiveConflicts()

SCIP_Longint SCIPhistoryGetNActiveConflicts ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

gets the number of active conflicts of the history entry

Parameters
historybranching and inference history
dirbranching direction

Definition at line 558 of file history.c.

References SCIP_History::nactiveconflicts, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPvarGetNActiveConflicts(), and SCIPvarGetNActiveConflictsCurrentRun().

◆ SCIPhistoryGetAvgConflictlength()

SCIP_Real SCIPhistoryGetAvgConflictlength ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

gets the average conflict length of the history entry

Parameters
historybranching and inference history
dirbranching direction

Definition at line 571 of file history.c.

References SCIP_History::conflengthsum, SCIP_History::nactiveconflicts, NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, and SCIP_Real.

Referenced by SCIPgetAvgConflictlengthScore(), SCIPgetAvgConflictlengthScoreCurrentRun(), SCIPvarGetAvgConflictlength(), and SCIPvarGetAvgConflictlengthCurrentRun().

◆ SCIPhistoryIncNBranchings()

void SCIPhistoryIncNBranchings ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir,
int  depth 
)

increases the number of branchings counter

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)
depthdepth at which the bound change took place

Definition at line 584 of file history.c.

References SCIP_History::branchdepthsum, SCIP_History::nbranchings, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPreoptMergeVarHistory(), and SCIPvarIncNBranchings().

◆ SCIPhistoryIncInferenceSum()

void SCIPhistoryIncInferenceSum ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir,
SCIP_Real  weight 
)

increases the number of inferences counter by a certain value

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)
weightweight of this update in inference score

Definition at line 600 of file history.c.

References SCIP_History::inferencesum, SCIP_History::nbranchings, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPreoptMergeVarHistory(), and SCIPvarIncInferenceSum().

◆ SCIPhistoryIncCutoffSum()

void SCIPhistoryIncCutoffSum ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir,
SCIP_Real  weight 
)

increases the number of cutoffs counter

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)
weightweight of this update in cutoff score

Definition at line 616 of file history.c.

References SCIP_History::cutoffsum, SCIP_History::nbranchings, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPreoptMergeVarHistory(), and SCIPvarIncCutoffSum().

◆ SCIPhistoryGetNBranchings()

SCIP_Longint SCIPhistoryGetNBranchings ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

get number of branchings counter

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 632 of file history.c.

References SCIP_History::nbranchings, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPprintBranchingStatistics(), SCIPvarGetAvgCutoffs(), SCIPvarGetAvgCutoffsCurrentRun(), SCIPvarGetAvgInferences(), SCIPvarGetAvgInferencesCurrentRun(), SCIPvarGetNBranchings(), and SCIPvarGetNBranchingsCurrentRun().

◆ SCIPhistoryGetInferenceSum()

SCIP_Real SCIPhistoryGetInferenceSum ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

get number of inferences counter

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 645 of file history.c.

References SCIP_History::inferencesum, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by SCIPprintBranchingStatistics(), SCIPvarGetInferenceSum(), and SCIPvarGetInferenceSumCurrentRun().

◆ SCIPhistoryGetAvgInferences()

SCIP_Real SCIPhistoryGetAvgInferences ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

◆ SCIPhistoryGetCutoffSum()

SCIP_Real SCIPhistoryGetCutoffSum ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

get number of cutoffs counter

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 671 of file history.c.

References SCIP_History::cutoffsum, NULL, SCIP_BRANCHDIR_DOWNWARDS, and SCIP_BRANCHDIR_UPWARDS.

Referenced by checkValueScore(), SCIPprintBranchingStatistics(), SCIPvarGetCutoffSum(), and SCIPvarGetCutoffSumCurrentRun().

◆ SCIPhistoryGetAvgCutoffs()

SCIP_Real SCIPhistoryGetAvgCutoffs ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

returns the average number of cutoffs per branching

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 684 of file history.c.

References SCIP_History::cutoffsum, SCIP_History::nbranchings, NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, and SCIP_Real.

Referenced by SCIPgetAvgCutoffs(), SCIPgetAvgCutoffScore(), SCIPgetAvgCutoffScoreCurrentRun(), SCIPgetAvgCutoffsCurrentRun(), SCIPreoptMergeVarHistory(), SCIPvarGetAvgCutoffs(), and SCIPvarGetAvgCutoffsCurrentRun().

◆ SCIPhistoryGetAvgBranchdepth()

SCIP_Real SCIPhistoryGetAvgBranchdepth ( SCIP_HISTORY history,
SCIP_BRANCHDIR  dir 
)

returns the average depth of bound changes due to branching

Parameters
historybranching and inference history
dirbranching direction (downwards, or upwards)

Definition at line 697 of file history.c.

References SCIP_History::branchdepthsum, SCIP_History::nbranchings, NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, and SCIP_Real.

Referenced by SCIPvarGetAvgBranchdepth(), and SCIPvarGetAvgBranchdepthCurrentRun().

◆ SCIPhistoryIsRatioValid()

SCIP_Bool SCIPhistoryIsRatioValid ( SCIP_HISTORY history)

returns true if the given history contains a valid ratio

Parameters
historybranching and inference history

Definition at line 710 of file history.c.

References NULL, and SCIP_History::ratiovalid.

Referenced by computeVarRatio().

◆ SCIPhistoryGetLastRatio()

SCIP_Real SCIPhistoryGetLastRatio ( SCIP_HISTORY history)

returns the most recent ratio computed given the variable history

Parameters
historybranching and inference history

Definition at line 720 of file history.c.

References NULL, SCIP_History::ratio, and SCIP_History::ratiovalid.

Referenced by computeVarRatio().

◆ SCIPhistoryGetLastBalance()

SCIP_Real SCIPhistoryGetLastBalance ( SCIP_HISTORY history)

returns the most recent value of r/l used to compute this variable's ratio

Parameters
historybranching and inference history

Definition at line 731 of file history.c.

References SCIP_History::balance, NULL, and SCIP_History::ratiovalid.

Referenced by computeVarRatio().

◆ SCIPhistorySetRatioHistory()

void SCIPhistorySetRatioHistory ( SCIP_HISTORY history,
SCIP_Bool  valid,
SCIP_Real  ratio,
SCIP_Real  balance 
)

sets the ratio history for a particular variable

Parameters
historybranching and inference history
validTrue iff the ratio computed is valid
ratioRatio of the characteristic polynomial with gains (1, rightgain/leftgain)
balanceThe value of rightgain/leftgain

Definition at line 742 of file history.c.

References SCIP_History::balance, NULL, SCIP_History::ratio, and SCIP_History::ratiovalid.

Referenced by computeVarRatio().