Detailed Description

event handler for tree size estimation and restarts

This event handler plugin provides different methods for approximating the current fraction of the search that has already been completed and for estimating the total tree size at completion. It can trigger restarts of the current run if the current run seems hopeless.

For details about the available approximations of search completion, please see

Anderson, Hendel, Le Bodic, Pfetsch Estimating The Size of Branch-and-Bound Trees under preparation

This code is a largely enriched version of a code that was used for clairvoyant restarts, see

Anderson, Hendel, Le Bodic, Viernickel Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2018

Author: Gregor Hendel

Definition in file event_estim.c.

#include <string.h>
#include "blockmemshell/memory.h"
#include "scip/event_estim.h"
#include "scip/prop_symmetry.h"
#include "scip/pub_disp.h"
#include "scip/pub_event.h"
#include "scip/pub_fileio.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_tree.h"
#include "scip/scip_disp.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_table.h"
#include "scip/scip_timing.h"
#include "scip/scip_tree.h"
#include "scip/type_disp.h"
#include "scip/type_event.h"
#include "scip/type_message.h"
#include "scip/type_misc.h"
#include "scip/type_retcode.h"
#include "scip/type_stat.h"
#include "scip/type_table.h"

Go to the source code of this file.

Data Structures
struct	DoubleExpSmooth
struct	TreeProfileStats
struct	TreeProfile
struct	TreeData
struct	SubtreeSumGap
struct	TimeSeries
struct	NodeInfo
struct	SCIP_RegForest

Macros
#define	EVENTHDLR_NAME "estim"
#define	EVENTHDLR_DESC "event handler for tree size estimation and restarts"
#define	EVENTTYPE_ESTIM (SCIP_EVENTTYPE_NODEDELETE \| SCIP_EVENTTYPE_NODEBRANCHED)
#define	RESTARTPOLICY_CHAR_NEVER 'n'
#define	RESTARTPOLICY_CHAR_ALWAYS 'a'
#define	RESTARTPOLICY_CHAR_COMPLETION 'c'
#define	RESTARTPOLICY_CHAR_ESTIMATION 'e'
#define	DES_USETRENDINLEVEL TRUE
#define	TABLE_NAME "estim"
#define	TABLE_DESC "tree size estimations statistics table"
#define	TABLE_POSITION 18500
#define	TABLE_EARLIEST_STAGE SCIP_STAGE_INIT
#define	DISP_NAME "completed"
#define	DISP_DESC "completion of search in percent (based on tree size estimation)"
#define	DISP_HEADER "compl."
#define	DISP_WIDTH 8
#define	DISP_PRIORITY 110000
#define	DISP_POSITION 30100
#define	DISP_STRIPLINE TRUE
#define	INITIALSIZE 100
#define	SESCOEFF 0.75
#define	DES_ALPHA_TREEWEIGHT 0.65
#define	DES_BETA_TREEWEIGHT 0.15
#define	DES_ALPHA_GAP 0.6
#define	DES_BETA_GAP 0.15
#define	DES_ALPHA_LEAFFREQUENCY 0.3
#define	DES_BETA_LEAFFREQUENCY 0.33
#define	DES_ALPHA_SSG 0.6
#define	DES_BETA_SSG 0.15
#define	DES_ALPHA_OPENNODES 0.6
#define	DES_BETA_OPENNODES 0.15
#define	MAX_REGFORESTSIZE 10000000
#define	COMPLETIONTYPE_AUTO 'a'
#define	COMPLETIONTYPE_REGFOREST 'r'
#define	COMPLETIONTYPE_MONOREG 'm'
#define	COMPLETIONTYPE_TREEWEIGHT 'w'
#define	COMPLETIONTYPE_SSG 's'
#define	COMPLETIONTYPE_GAP 'g'
#define	ESTIMMETHOD_COMPL 'c'
#define	ESTIMMETHOD_WBE 'b'
#define	ESTIMMETHOD_ENSMBL 'e'
#define	ESTIMMETHOD_GAP 'g'
#define	ESTIMMETHOD_LFREQ 'l'
#define	ESTIMMETHOD_OPEN 'o'
#define	ESTIMMETHOD_SSG 's'
#define	ESTIMMETHOD_TPROF 't'
#define	ESTIMMETHOD_TREEWEIGHT 'w'
#define	ESTIMMETHODS "bceglostw"
#define	TREEPROFILE_MINSIZE 512
#define	SSG_STARTPRIMBOUND SCIP_INVALID
#define	NTIMESERIES 5
#define	DEFAULT_USELEAFTS TRUE
#define	DEFAULT_REPORTFREQ -1
#define	DEFAULT_REGFORESTFILENAME "-"
#define	DEFAULT_COEFMONOWEIGHT 0.3667
#define	DEFAULT_COEFMONOSSG 0.6333
#define	DEFAULT_COMPLETIONTYPE COMPLETIONTYPE_AUTO
#define	DEFAULT_ESTIMMETHOD ESTIMMETHOD_TREEWEIGHT
#define	DEFAULT_TREEPROFILE_ENABLED FALSE
#define	DEFAULT_TREEPROFILE_MINNODESPERDEPTH 20.0
#define	DEFAULT_RESTARTPOLICY 'e'
#define	DEFAULT_RESTARTLIMIT 1
#define	DEFAULT_MINNODES 1000L
#define	DEFAULT_COUNTONLYLEAVES FALSE
#define	DEFAULT_RESTARTFACTOR 50.0
#define	DEFAULT_RESTARTNONLINEAR FALSE
#define	DEFAULT_RESTARTACTPRICERS FALSE
#define	DEFAULT_HITCOUNTERLIM 50
#define	DEFAULT_SSG_NMAXSUBTREES -1
#define	DEFAULT_SSG_NMINNODESLASTSPLIT 0L
#define	DEFAULT_SHOWSTATS FALSE
#define	DECL_TIMESERIESUPDATE(x)

Functions
static char *	real2String (SCIP_Real num, char *buf, int digits)
static void	SCIPregForestFree (SCIP_REGFOREST **regforest)
static SCIP_Real	SCIPregForestPredict (SCIP_REGFOREST regforest, SCIP_Real datapoint)
static SCIP_RETCODE	SCIPregForestFromFile (SCIP_REGFOREST *regforest, const char filename)
static SCIP_Bool	isEqualTreeProfileStats (TREEPROFILESTATS stats, TREEPROFILESTATS other)
static void	copyTreeProfileStats (TREEPROFILESTATS dest, TREEPROFILESTATS src)
static void	resetTreeProfileStats (TREEPROFILESTATS *treeprofilestats)
static SCIP_RETCODE	extendMemoryTreeProfile (SCIP scip, TREEPROFILE treeprofile, int mindepth)
static SCIP_RETCODE	createTreeProfile (SCIP scip, TREEPROFILE *treeprofile)
static void	freeTreeProfile (SCIP scip, TREEPROFILE *treeprofile)
static SCIP_RETCODE	updateTreeProfile (SCIP scip, TREEPROFILE treeprofile, SCIP_NODE *node)
static SCIP_Real	predictTotalSizeTreeProfile (SCIP scip, TREEPROFILE treeprofile, SCIP_Real minnodesperdepth)
static void	subtreeSumGapDelSubtrees (SCIP scip, SUBTREESUMGAP ssg)
static SCIP_RETCODE	subtreeSumGapReset (SCIP scip, SUBTREESUMGAP ssg)
static SCIP_RETCODE	subtreeSumGapCreate (SCIP scip, SUBTREESUMGAP *ssg)
static void	subtreeSumGapFree (SCIP scip, SUBTREESUMGAP *ssg)
static	SCIP_DECL_SORTPTRCOMP (compareNodeInfos)
static	SCIP_DECL_PQUEUEELEMCHGPOS (elemChgPosNodeInfo)
static SCIP_RETCODE	subtreeSumGapStoreNode (SCIP scip, SUBTREESUMGAP ssg, SCIP_NODE *node, int subtreeidx)
static SCIP_RETCODE	subtreeSumGapSplit (SCIP scip, SUBTREESUMGAP ssg, SCIP_Bool addfocusnode)
static SCIP_Real	calcGap (SCIP *scip, SCIP_Real lowerbound)
static SCIP_RETCODE	subtreeSumGapRemoveNode (SCIP scip, SUBTREESUMGAP ssg, SCIP_NODE *node)
static SCIP_RETCODE	subtreeSumGapInsertChildren (SCIP scip, SUBTREESUMGAP ssg)
static SCIP_RETCODE	subtreeSumGapComputeFromScratchEfficiently (SCIP scip, SUBTREESUMGAP ssg, SCIP_Bool updatescaling)
static SCIP_RETCODE	subtreeSumGapUpdate (SCIP scip, SUBTREESUMGAP ssg, SCIP_NODE *node, int nchildren, SCIP_Longint nsolvednodes)
static SCIP_RETCODE	resetTreeData (SCIP scip, TREEDATA treedata)
static SCIP_RETCODE	createTreeData (SCIP scip, TREEDATA *treedata)
static void	freeTreeData (SCIP scip, TREEDATA *treedata)
static SCIP_RETCODE	updateTreeData (SCIP scip, TREEDATA treedata, SCIP_NODE *node, int nchildren)
static SCIP_Real	treeDataGetWbe (TREEDATA *treedata)
static void	doubleExpSmoothReset (DOUBLEEXPSMOOTH *des, SCIP_Real initialvalue)
static void	doubleExpSmoothInit (DOUBLEEXPSMOOTH *des, SCIP_Real x1)
static void	doubleExpSmoothUpdate (DOUBLEEXPSMOOTH *des, SCIP_Real xnew)
static SCIP_Real	doubleExpSmoothGetTrend (DOUBLEEXPSMOOTH *des)
static void	timeSeriesReset (TIMESERIES *timeseries)
static SCIP_RETCODE	timeSeriesCreate (SCIP scip, TIMESERIES timeseries, const char name, SCIP_Real targetvalue, SCIP_Real initialvalue, SCIP_Real alpha, SCIP_Real beta,)
static void	timeSeriesFree (SCIP scip, TIMESERIES *timeseries)
static SCIP_Real	timeSeriesGetValue (TIMESERIES *timeseries)
static SCIP_Real	timeSeriesGetTargetValue (TIMESERIES *timeseries)
static int	timeSeriesGetResolution (TIMESERIES *timeseries)
static SCIP_Real	timeSeriesEstimate (TIMESERIES timeseries, TREEDATA treedata)
static void	timeSeriesUpdateSmoothEstimation (TIMESERIES *timeseries, SCIP_Real estimation)
static SCIP_Real	timeSeriesGetSmoothEstimation (TIMESERIES *timeseries)
static void	timeSeriesResample (TIMESERIES *timeseries)
static SCIP_RETCODE	timeSeriesUpdate (SCIP scip, TIMESERIES timeseries, TREEDATA *treedata, SCIP_Bool isleaf)
static char *	timeSeriesGetName (TIMESERIES *timeseries)
static void	resetTimeSeries (SCIP_EVENTHDLRDATA *eventhdlrdata)
static void	freeTimeSeries (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata)
static SCIP_Real	getEnsembleEstimation (SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE	getSearchCompletion (SCIP_EVENTHDLRDATA eventhdlrdata, SCIP_Real completed)
static SCIP_RETCODE	getEstimCompletion (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata, SCIP_Real *estim)
static	DECL_TIMESERIESUPDATE (timeseriesUpdateGap)
static	DECL_TIMESERIESUPDATE (timeseriesUpdateTreeWeight)
static	DECL_TIMESERIESUPDATE (timeseriesUpdateLeafFreq)
static	DECL_TIMESERIESUPDATE (timeseriesUpdateSsg)
static	DECL_TIMESERIESUPDATE (timeseriesUpdateOpenNodes)
static SCIP_RETCODE	includeTimeseries (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata)
static RESTARTPOLICY	getRestartPolicy (SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool	isRestartApplicable (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata)
static SCIP_Bool	shouldApplyRestartCompletion (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata)
static SCIP_Bool	shouldApplyRestartEstimation (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata)
static SCIP_Bool	shouldApplyRestart (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata)
static SCIP_RETCODE	updateTimeseries (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata, TREEDATA *treedata, SCIP_Bool isleaf)
static void	printReport (SCIP scip, SCIP_EVENTHDLRDATA eventhdlrdata, char *strbuf, int reportnum)
static	SCIP_DECL_EVENTCOPY (eventCopyEstim)
static	SCIP_DECL_EVENTFREE (eventFreeEstim)
static	SCIP_DECL_EVENTINIT (eventInitEstim)
static	SCIP_DECL_EVENTEXIT (eventExitEstim)
static	SCIP_DECL_EVENTINITSOL (eventInitsolEstim)
static	SCIP_DECL_EVENTEXITSOL (eventExitsolEstim)
static	SCIP_DECL_EVENTEXEC (eventExecEstim)
static	SCIP_DECL_TABLEOUTPUT (tableOutputEstim)
static	SCIP_DECL_DISPOUTPUT (dispOutputCompleted)
SCIP_RETCODE	SCIPincludeEventHdlrEstim (SCIP *scip)
SCIP_Real	SCIPgetTreesizeEstimation (SCIP *scip)

Macro Definition Documentation

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "estim"

Definition at line 83 of file event_estim.c.

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "event handler for tree size estimation and restarts"

Definition at line 84 of file event_estim.c.

◆ EVENTTYPE_ESTIM

#define EVENTTYPE_ESTIM (SCIP_EVENTTYPE_NODEDELETE | SCIP_EVENTTYPE_NODEBRANCHED)

Definition at line 85 of file event_estim.c.

Referenced by SCIP_DECL_EVENTEXITSOL(), and SCIP_DECL_EVENTINITSOL().

◆ RESTARTPOLICY_CHAR_NEVER

#define RESTARTPOLICY_CHAR_NEVER 'n'

Definition at line 102 of file event_estim.c.

Referenced by getRestartPolicy().

◆ RESTARTPOLICY_CHAR_ALWAYS

#define RESTARTPOLICY_CHAR_ALWAYS 'a'

Definition at line 103 of file event_estim.c.

Referenced by getRestartPolicy().

◆ RESTARTPOLICY_CHAR_COMPLETION

#define RESTARTPOLICY_CHAR_COMPLETION 'c'

Definition at line 104 of file event_estim.c.

Referenced by getRestartPolicy().

◆ RESTARTPOLICY_CHAR_ESTIMATION

#define RESTARTPOLICY_CHAR_ESTIMATION 'e'

Definition at line 105 of file event_estim.c.

Referenced by getRestartPolicy().

◆ DES_USETRENDINLEVEL

#define DES_USETRENDINLEVEL TRUE

Should the trend be used in the level update?

Definition at line 107 of file event_estim.c.

Referenced by doubleExpSmoothInit().

◆ TABLE_NAME

#define TABLE_NAME "estim"

Definition at line 110 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ TABLE_DESC

#define TABLE_DESC "tree size estimations statistics table"

Definition at line 111 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ TABLE_POSITION

#define TABLE_POSITION 18500

the position of the statistics table

Definition at line 112 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ TABLE_EARLIEST_STAGE

#define TABLE_EARLIEST_STAGE SCIP_STAGE_INIT

output of the statistics table is only printed from this stage onwards

Definition at line 113 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DISP_NAME

#define DISP_NAME "completed"

Definition at line 116 of file event_estim.c.

Referenced by SCIP_DECL_DISPOUTPUT(), and SCIPincludeEventHdlrEstim().

◆ DISP_DESC

#define DISP_DESC "completion of search in percent (based on tree size estimation)"

Definition at line 117 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DISP_HEADER

#define DISP_HEADER "compl."

Definition at line 118 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DISP_WIDTH

#define DISP_WIDTH 8

the width of the display column

Definition at line 119 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DISP_PRIORITY

#define DISP_PRIORITY 110000

the priority of the display column

Definition at line 120 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DISP_POSITION

#define DISP_POSITION 30100

the relative position of the display column

Definition at line 121 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DISP_STRIPLINE

#define DISP_STRIPLINE TRUE

the default for whether the display column should be separated with a line from its right neighbor

Definition at line 122 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ INITIALSIZE

#define INITIALSIZE 100

Definition at line 124 of file event_estim.c.

Referenced by ensureMemorySize(), and subtreeSumGapCreate().

◆ SESCOEFF

#define SESCOEFF 0.75

coefficient of single exponential smoothing of estimation

Definition at line 125 of file event_estim.c.

Referenced by timeSeriesUpdateSmoothEstimation().

◆ DES_ALPHA_TREEWEIGHT

#define DES_ALPHA_TREEWEIGHT 0.65

Definition at line 128 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_BETA_TREEWEIGHT

#define DES_BETA_TREEWEIGHT 0.15

Definition at line 129 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_ALPHA_GAP

#define DES_ALPHA_GAP 0.6

Definition at line 131 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_BETA_GAP

#define DES_BETA_GAP 0.15

Definition at line 132 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_ALPHA_LEAFFREQUENCY

#define DES_ALPHA_LEAFFREQUENCY 0.3

Definition at line 134 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_BETA_LEAFFREQUENCY

#define DES_BETA_LEAFFREQUENCY 0.33

Definition at line 135 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_ALPHA_SSG

#define DES_ALPHA_SSG 0.6

Definition at line 137 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_BETA_SSG

#define DES_BETA_SSG 0.15

Definition at line 138 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_ALPHA_OPENNODES

#define DES_ALPHA_OPENNODES 0.6

Definition at line 140 of file event_estim.c.

Referenced by includeTimeseries().

◆ DES_BETA_OPENNODES

#define DES_BETA_OPENNODES 0.15

Definition at line 141 of file event_estim.c.

Referenced by includeTimeseries().

◆ MAX_REGFORESTSIZE

#define MAX_REGFORESTSIZE 10000000

size limit (number of nodes) for regression forest

Definition at line 143 of file event_estim.c.

Referenced by SCIPregForestFromFile().

◆ COMPLETIONTYPE_AUTO

#define COMPLETIONTYPE_AUTO 'a'

automatic (regression forest if available, else monotone regression on binary and SSG on nonbinary trees)

Definition at line 148 of file event_estim.c.

Referenced by getSearchCompletion().

◆ COMPLETIONTYPE_REGFOREST

#define COMPLETIONTYPE_REGFOREST 'r'

regression forest (must be provided by user)

Definition at line 149 of file event_estim.c.

Referenced by getSearchCompletion().

◆ COMPLETIONTYPE_MONOREG

#define COMPLETIONTYPE_MONOREG 'm'

monotone regression (using tree weight and SSG)

Definition at line 150 of file event_estim.c.

Referenced by getSearchCompletion().

◆ COMPLETIONTYPE_TREEWEIGHT

#define COMPLETIONTYPE_TREEWEIGHT 'w'

use tree weight value as approximation of search tree completion

Definition at line 151 of file event_estim.c.

Referenced by getSearchCompletion().

◆ COMPLETIONTYPE_SSG

#define COMPLETIONTYPE_SSG 's'

use SSG value as approximation of search tree completion

Definition at line 152 of file event_estim.c.

Referenced by getSearchCompletion().

◆ COMPLETIONTYPE_GAP

#define COMPLETIONTYPE_GAP 'g'

use gap value as approximation of search tree completion

Definition at line 153 of file event_estim.c.

Referenced by getSearchCompletion().

◆ ESTIMMETHOD_COMPL

#define ESTIMMETHOD_COMPL 'c'

estimation based on projection of current search completion

Definition at line 157 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_WBE

#define ESTIMMETHOD_WBE 'b'

weighted backtrack estimation

Definition at line 158 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_ENSMBL

#define ESTIMMETHOD_ENSMBL 'e'

estimation based on an ensemble of the individual estimations

Definition at line 159 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_GAP

#define ESTIMMETHOD_GAP 'g'

estimation based on double exponential smoothing for open nodes

Definition at line 160 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_LFREQ

#define ESTIMMETHOD_LFREQ 'l'

estimation based on double exponential smoothing for leaf frequency

Definition at line 161 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_OPEN

#define ESTIMMETHOD_OPEN 'o'

estimation based on double exponential smoothing for open nodes

Definition at line 162 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_SSG

#define ESTIMMETHOD_SSG 's'

estimation based on double exponential smoothing for sum of subtree gaps

Definition at line 163 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_TPROF

#define ESTIMMETHOD_TPROF 't'

estimation based on tree profile method

Definition at line 164 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHOD_TREEWEIGHT

#define ESTIMMETHOD_TREEWEIGHT 'w'

estimation based on double exponential smoothing for tree weight

Definition at line 165 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation().

◆ ESTIMMETHODS

#define ESTIMMETHODS "bceglostw"

Definition at line 167 of file event_estim.c.

Referenced by SCIPgetTreesizeEstimation(), and SCIPincludeEventHdlrEstim().

◆ TREEPROFILE_MINSIZE

#define TREEPROFILE_MINSIZE 512

minimum size (depth) that tree profile can hold

Definition at line 170 of file event_estim.c.

Referenced by createTreeProfile().

◆ SSG_STARTPRIMBOUND

#define SSG_STARTPRIMBOUND SCIP_INVALID

initial value of primal bound used within SSG

Definition at line 171 of file event_estim.c.

Referenced by getSearchCompletion(), and subtreeSumGapReset().

◆ NTIMESERIES

#define NTIMESERIES 5

Definition at line 200 of file event_estim.c.

Referenced by freeTimeSeries(), getEnsembleEstimation(), printReport(), resetTimeSeries(), and updateTimeseries().

◆ DEFAULT_USELEAFTS

#define DEFAULT_USELEAFTS TRUE

Use leaf nodes as basic observations for time series, or all nodes?

Definition at line 243 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_REPORTFREQ

#define DEFAULT_REPORTFREQ -1

report frequency on estimation: -1: never, 0: always, k >= 1: k times evenly during search

Definition at line 244 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_REGFORESTFILENAME

#define DEFAULT_REGFORESTFILENAME "-"

default file name of user regression forest in RFCSV format

Definition at line 245 of file event_estim.c.

Referenced by SCIP_DECL_EVENTINIT(), and SCIPincludeEventHdlrEstim().

◆ DEFAULT_COEFMONOWEIGHT

#define DEFAULT_COEFMONOWEIGHT 0.3667

coefficient of tree weight in monotone approximation of search completion

Definition at line 246 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_COEFMONOSSG

#define DEFAULT_COEFMONOSSG 0.6333

coefficient of 1 - SSG in monotone approximation of search completion

Definition at line 247 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_COMPLETIONTYPE

#define DEFAULT_COMPLETIONTYPE COMPLETIONTYPE_AUTO

default computation of search tree completion

Definition at line 248 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_ESTIMMETHOD

#define DEFAULT_ESTIMMETHOD ESTIMMETHOD_TREEWEIGHT

default tree size estimation method: (c)ompletion, (e)nsemble, time series forecasts on either (g)ap, (l)eaf frequency, (o)open nodes, tree (w)eight, (s)sg, or (t)ree profile or w(b)e

Definition at line 249 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_TREEPROFILE_ENABLED

#define DEFAULT_TREEPROFILE_ENABLED FALSE

Should the event handler collect data?

Definition at line 252 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_TREEPROFILE_MINNODESPERDEPTH

#define DEFAULT_TREEPROFILE_MINNODESPERDEPTH 20.0

minimum average number of nodes at each depth before producing estimations

Definition at line 253 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_RESTARTPOLICY

#define DEFAULT_RESTARTPOLICY 'e'

default restart policy: (a)lways, (c)ompletion, (e)stimation, (n)ever

Definition at line 254 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_RESTARTLIMIT

#define DEFAULT_RESTARTLIMIT 1

default restart limit

Definition at line 255 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES 1000L

◆ DEFAULT_COUNTONLYLEAVES

#define DEFAULT_COUNTONLYLEAVES FALSE

should only leaves count for the minnodes parameter?

Definition at line 257 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_RESTARTFACTOR

#define DEFAULT_RESTARTFACTOR 50.0

factor by which the estimated number of nodes should exceed the current number of nodes

Definition at line 258 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_RESTARTNONLINEAR

#define DEFAULT_RESTARTNONLINEAR FALSE

whether to apply a restart when nonlinear constraints are present

Definition at line 259 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_RESTARTACTPRICERS

#define DEFAULT_RESTARTACTPRICERS FALSE

whether to apply a restart when active pricers are used

Definition at line 260 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_HITCOUNTERLIM

#define DEFAULT_HITCOUNTERLIM 50

limit on the number of successive samples to really trigger a restart

Definition at line 261 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_SSG_NMAXSUBTREES

#define DEFAULT_SSG_NMAXSUBTREES -1

the maximum number of individual SSG subtrees; the old split is kept if a new split exceeds this number of subtrees ; -1: no limit

Definition at line 262 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_SSG_NMINNODESLASTSPLIT

#define DEFAULT_SSG_NMINNODESLASTSPLIT 0L

minimum number of nodes to process between two consecutive SSG splits

Definition at line 264 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DEFAULT_SHOWSTATS

#define DEFAULT_SHOWSTATS FALSE

should statistics be shown at the end?

Definition at line 265 of file event_estim.c.

Referenced by SCIPincludeEventHdlrEstim().

◆ DECL_TIMESERIESUPDATE

#define DECL_TIMESERIESUPDATE ( x )

Value:

SCIP_RETCODE x (\
SCIP*                 scip,                   \
TIMESERIES*           ts,                     \
TREEDATA*             treedata,               \
SCIP_Real*            value                   \
)

update callback of time series

Definition at line 331 of file event_estim.c.

Referenced by timeSeriesCreate().

Typedef Documentation

◆ RESTARTPOLICY

typedef enum RestartPolicy RESTARTPOLICY

Definition at line 100 of file event_estim.c.

◆ DOUBLEEXPSMOOTH

typedef struct DoubleExpSmooth DOUBLEEXPSMOOTH

Definition at line 184 of file event_estim.c.

◆ TIMESERIES

typedef struct TimeSeries TIMESERIES

time series data structure for leaf time series

These time series are the basic ingredient for tree size estimation via forecasting.

This general class represents concrete time series such as the closed gap, tree weight, and leaf frequency. Through callbacks for data (de-)initialization and value queries, it provides a common interface to which double exponential smoothing or window forecasts can be applied.

Definition at line 194 of file event_estim.c.

◆ TREEDATA

typedef struct TreeData TREEDATA

data structure for convenient access of tree information

Definition at line 197 of file event_estim.c.

◆ TSPOS

typedef enum TsPos TSPOS

Definition at line 213 of file event_estim.c.

◆ SCIP_REGFOREST

typedef struct SCIP_RegForest SCIP_REGFOREST

regression forest data structure

Definition at line 216 of file event_estim.c.

◆ TREEPROFILESTATS

typedef struct TreeProfileStats TREEPROFILESTATS

Definition at line 227 of file event_estim.c.

◆ TREEPROFILE

typedef struct TreeProfile TREEPROFILE

Definition at line 240 of file event_estim.c.

◆ SUBTREESUMGAP

typedef struct SubtreeSumGap SUBTREESUMGAP

Definition at line 303 of file event_estim.c.

◆ NODEINFO

typedef struct NodeInfo NODEINFO

Definition at line 365 of file event_estim.c.

Enumeration Type Documentation

◆ RestartPolicy

enum RestartPolicy

enumerator for available restart policies

Enumerator
RESTARTPOLICY_NEVER	never restart (disable this event handler)
RESTARTPOLICY_ALWAYS	always restart (can be fine tuned by using minimum number of nodes and restart limit)
RESTARTPOLICY_ESTIMATION	base restart on the estimation method
RESTARTPOLICY_COMPLETION	trigger restart based on search completion approximation

Definition at line 92 of file event_estim.c.

◆ TsPos

enum TsPos

time series position in event handler time series array

Enumerator
TSPOS_NONE	invalid array position
TSPOS_GAP	time series position of gap
TSPOS_TREEWEIGHT	time series position of tree weight
TSPOS_LFREQ	time series position of leaf frequency
TSPOS_SSG	time series position of SSG
TSPOS_OPEN	time series position of open nodes

Definition at line 203 of file event_estim.c.

Function Documentation

◆ real2String()

char * real2String	(	SCIP_Real	num,
		char *	buf,
		int	digits )

static

convert number to string and treat SCIP_INVALID as '-'

Parameters

num	number to convert to string
buf	string buffer
digits	number of decimal digits

Definition at line 384 of file event_estim.c.

References SCIP_INVALID, SCIP_MAXSTRLEN, SCIP_Real, and SCIPsnprintf().

Referenced by printReport().

◆ SCIPregForestFree()

void SCIPregForestFree ( SCIP_REGFOREST ** regforest )

static

free a regression forest data structure

Parameters

regforest regression forest data structure

Definition at line 402 of file event_estim.c.

References assert(), BMSfreeMemory, BMSfreeMemoryArrayNull, SCIP_RegForest::child, SCIP_RegForest::nbegin, NULL, SCIP_RegForest::splitidx, and SCIP_RegForest::value.

Referenced by SCIP_DECL_EVENTEXIT(), and SCIPregForestFromFile().

◆ SCIPregForestPredict()

SCIP_Real SCIPregForestPredict	(	SCIP_REGFOREST *	regforest,
		SCIP_Real *	datapoint )

static

make a prediction with regression forest

Parameters

regforest	regression forest data structure
datapoint	a data point that matches the dimension of this regression forest

Definition at line 424 of file event_estim.c.

References assert(), SCIP_RegForest::child, SCIP_RegForest::dim, SCIP_RegForest::nbegin, SCIP_RegForest::ntrees, NULL, SCIP_Real, SCIPdebugMessage, SCIP_RegForest::splitidx, and SCIP_RegForest::value.

Referenced by getSearchCompletion().

◆ SCIPregForestFromFile()

SCIP_RETCODE SCIPregForestFromFile	(	SCIP_REGFOREST **	regforest,
		const char *	filename )

static

read a regression forest from an rfcsv file

TODO improve this parser to better capture wrong user input, e.g., if the dimension is wrong

Parameters

regforest	regression forest data structure
filename	name of file with the regression forest data

Definition at line 471 of file event_estim.c.

References assert(), BMSallocMemory, BMSallocMemoryArray, BMSclearMemory, SCIP_RegForest::child, SCIP_RegForest::dim, FALSE, MAX_REGFORESTSIZE, SCIP_RegForest::nbegin, SCIP_RegForest::ntrees, NULL, SCIP_ALLOC_TERMINATE, SCIP_Bool, SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_NOFILE, SCIP_NOMEMORY, SCIP_OKAY, SCIPdebugMessage, SCIPerrorMessage, SCIPfclose(), SCIPfeof(), SCIPfgets(), SCIPfopen(), SCIPregForestFree(), SCIPsnprintf(), SCIPstrToRealValue(), SCIP_RegForest::size, SCIP_RegForest::splitidx, TRUE, and SCIP_RegForest::value.

Referenced by SCIP_DECL_EVENTINIT().

◆ isEqualTreeProfileStats()

SCIP_Bool isEqualTreeProfileStats	(	TREEPROFILESTATS *	stats,
		TREEPROFILESTATS *	other )

static

compare two tree profile statistics for equality

Parameters

stats	first tree profile statistics
other	other tree profile statistics

Definition at line 608 of file event_estim.c.

References assert(), TreeProfileStats::lastfulldepth, TreeProfileStats::maxdepth, TreeProfileStats::maxwaistdepth, TreeProfileStats::minwaistdepth, NULL, and SCIP_Bool.

Referenced by predictTotalSizeTreeProfile().

◆ copyTreeProfileStats()

void copyTreeProfileStats	(	TREEPROFILESTATS *	dest,
		TREEPROFILESTATS *	src )

static

copy source tree profile into destination

Parameters

dest	destination tree profile statistics
src	source tree profile statistics

Definition at line 624 of file event_estim.c.

References assert(), TreeProfileStats::lastfulldepth, TreeProfileStats::maxdepth, TreeProfileStats::maxwaistdepth, TreeProfileStats::minwaistdepth, and NULL.

Referenced by predictTotalSizeTreeProfile().

◆ resetTreeProfileStats()

void resetTreeProfileStats ( TREEPROFILESTATS * treeprofilestats )

static

reset tree profile statistics

Parameters

treeprofilestats tree profile statistics

Definition at line 640 of file event_estim.c.

References assert(), BMSclearMemory, and NULL.

Referenced by createTreeProfile().

◆ extendMemoryTreeProfile()

SCIP_RETCODE extendMemoryTreeProfile	(	SCIP *	scip,
		TREEPROFILE *	treeprofile,
		int	mindepth )

static

extend tree profile to deeper tree

Parameters

scip	SCIP data structure
treeprofile	tree profile data structure
mindepth	minimum depth that the tree profile should hold

Definition at line 652 of file event_estim.c.

References assert(), BMSclearMemoryArray, NULL, TreeProfile::profile, TreeProfile::profilesize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPallocClearMemoryArray, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.

Referenced by createTreeProfile(), and updateTreeProfile().

◆ createTreeProfile()

SCIP_RETCODE createTreeProfile	(	SCIP *	scip,
		TREEPROFILE **	treeprofile )

static

create a tree profile

Parameters

scip	SCIP data structure
treeprofile	pointer to store tree profile data structure

Definition at line 687 of file event_estim.c.

References assert(), extendMemoryTreeProfile(), NULL, resetTreeProfileStats(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and TREEPROFILE_MINSIZE.

Referenced by SCIP_DECL_EVENTINITSOL().

◆ freeTreeProfile()

void freeTreeProfile	(	SCIP *	scip,
		TREEPROFILE **	treeprofile )

static

free a tree profile

Parameters

scip	SCIP data structure
treeprofile	pointer to tree profile data structure

Definition at line 711 of file event_estim.c.

References assert(), NULL, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by SCIP_DECL_EVENTEXITSOL().

◆ updateTreeProfile()

SCIP_RETCODE updateTreeProfile	(	SCIP *	scip,
		TREEPROFILE *	treeprofile,
		SCIP_NODE *	node )

static

update tree profile

Parameters

scip	SCIP data structure
treeprofile	tree profile data structure
node	node that should be added to the profile

Definition at line 731 of file event_estim.c.

References assert(), extendMemoryTreeProfile(), TreeProfileStats::lastfulldepth, TreeProfileStats::maxdepth, TreeProfileStats::maxwaistdepth, TreeProfileStats::minwaistdepth, NULL, TreeProfile::profile, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPnodeGetDepth(), and TreeProfile::stats.

Referenced by SCIP_DECL_EVENTEXEC().

◆ predictTotalSizeTreeProfile()

SCIP_Real predictTotalSizeTreeProfile	(	SCIP *	scip,
		TREEPROFILE *	treeprofile,
		SCIP_Real	minnodesperdepth )

static

make a prediction of the total tree size based on the current tree profile

Parameters

scip	SCIP data structure
treeprofile	tree profile data structure
minnodesperdepth	minimum number of average nodes per depth to make a prediction

Definition at line 800 of file event_estim.c.

References assert(), copyTreeProfileStats(), isEqualTreeProfileStats(), TreeProfile::lastestimate, TreeProfile::lastestimatestats, TreeProfileStats::lastfulldepth, TreeProfileStats::maxdepth, TreeProfileStats::maxwaistdepth, TreeProfileStats::minwaistdepth, NULL, SCIP_Real, SCIPdebugMsg, SCIPgetNNodes(), and TreeProfile::stats.

Referenced by printReport(), and SCIPgetTreesizeEstimation().

◆ subtreeSumGapDelSubtrees()

void subtreeSumGapDelSubtrees	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg )

static

clean subtrees stored as priority queues

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure

Definition at line 872 of file event_estim.c.

References assert(), i, SubtreeSumGap::nsubtrees, NULL, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPpqueueElems(), SCIPpqueueFree(), SCIPpqueueNElems(), and SubtreeSumGap::subtreepqueues.

Referenced by subtreeSumGapFree(), subtreeSumGapReset(), and subtreeSumGapSplit().

◆ subtreeSumGapReset()

SCIP_RETCODE subtreeSumGapReset	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg )

static

reset subtree sum gap

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure

Definition at line 912 of file event_estim.c.

References assert(), SubtreeSumGap::nodelastsplit, SubtreeSumGap::nodes2info, SubtreeSumGap::nsubtrees, NULL, SubtreeSumGap::pblastsplit, SubtreeSumGap::scalingfactor, SCIP_CALL, SCIP_OKAY, SCIPhashmapRemoveAll(), SSG_STARTPRIMBOUND, SubtreeSumGap::subtreepqueues, subtreeSumGapDelSubtrees(), and SubtreeSumGap::value.

Referenced by resetTreeData(), and subtreeSumGapCreate().

◆ subtreeSumGapCreate()

SCIP_RETCODE subtreeSumGapCreate	(	SCIP *	scip,
		SUBTREESUMGAP **	ssg )

static

create a subtree sum gap

Parameters

scip	SCIP data structure
ssg	pointer to store subtree sum gap data structure

Definition at line 936 of file event_estim.c.

References assert(), INITIALSIZE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPblkmem(), SCIPhashmapCreate(), and subtreeSumGapReset().

Referenced by createTreeData().

◆ subtreeSumGapFree()

void subtreeSumGapFree	(	SCIP *	scip,
		SUBTREESUMGAP **	ssg )

static

free a subtree sum gap

Parameters

scip	SCIP data structure
ssg	pointer to store subtree sum gap data structure

Definition at line 959 of file event_estim.c.

References assert(), NULL, SCIPfreeMemory, SCIPhashmapFree(), and subtreeSumGapDelSubtrees().

Referenced by freeTreeData().

◆ SCIP_DECL_SORTPTRCOMP()

SCIP_DECL_SORTPTRCOMP ( compareNodeInfos )

static

compare two node infos by comparing their lower bound

Definition at line 982 of file event_estim.c.

References NodeInfo::lowerbound.

◆ SCIP_DECL_PQUEUEELEMCHGPOS()

SCIP_DECL_PQUEUEELEMCHGPOS ( elemChgPosNodeInfo )

static

position change callback of element in priority queue

Definition at line 997 of file event_estim.c.

References assert(), and NodeInfo::pos.

◆ subtreeSumGapStoreNode()

SCIP_RETCODE subtreeSumGapStoreNode	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg,
		SCIP_NODE *	node,
		int	subtreeidx )

static

store node in SSG data structure

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure
node	node that should be stored
subtreeidx	subtree index of that node

Definition at line 1007 of file event_estim.c.

References assert(), NodeInfo::lowerbound, NodeInfo::node, SubtreeSumGap::nodes2info, NULL, NodeInfo::pos, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPallocBlockMemory, SCIPdebugMsg, SCIPhashmapExists(), SCIPhashmapInsert(), SCIPnodeGetLowerbound(), SCIPnodeGetNumber(), SCIPpqueueCreate(), SCIPpqueueElems(), SCIPpqueueInsert(), SCIPpqueueNElems(), NodeInfo::subtreeidx, and SubtreeSumGap::subtreepqueues.

Referenced by subtreeSumGapInsertChildren(), and subtreeSumGapSplit().

◆ subtreeSumGapSplit()

SCIP_RETCODE subtreeSumGapSplit	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg,
		SCIP_Bool	addfocusnode )

static

split the open nodes of the current tree

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure
addfocusnode	should the focus node be a subtree, too?

Definition at line 1056 of file event_estim.c.

References assert(), nnodes, SubtreeSumGap::nodes2info, SubtreeSumGap::nsubtrees, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemoryArray, SCIPdebugMsg, SCIPgetFocusNode(), SCIPgetOpenNodesData(), SCIPhashmapRemoveAll(), SubtreeSumGap::subtreepqueues, subtreeSumGapDelSubtrees(), and subtreeSumGapStoreNode().

Referenced by subtreeSumGapUpdate().

◆ calcGap()

SCIP_Real calcGap	(	SCIP *	scip,
		SCIP_Real	lowerbound )

static

compute a gap between a lower bound and the current upper bound

Parameters

scip	SCIP data structure
lowerbound	lower bound value

Definition at line 1124 of file event_estim.c.

References MAX, MIN, REALABS, SCIP_Real, SCIPgetPrimalbound(), SCIPgetUpperbound(), SCIPisEQ(), SCIPisInfinity(), and SCIPretransformObj().

Referenced by subtreeSumGapComputeFromScratchEfficiently(), and subtreeSumGapRemoveNode().

◆ subtreeSumGapRemoveNode()

SCIP_RETCODE subtreeSumGapRemoveNode	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg,
		SCIP_NODE *	node )

static

remove node from the subtree sum gap (because it has been solved by branching or is a leaf)

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure
node	node that should be removed

Definition at line 1157 of file event_estim.c.

References assert(), calcGap(), NodeInfo::lowerbound, MIN, SubtreeSumGap::nodes2info, SubtreeSumGap::nsubtrees, NULL, NodeInfo::pos, SubtreeSumGap::scalingfactor, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPhashmapGetImage(), SCIPhashmapRemove(), SCIPinfinity(), SCIPisLE(), SCIPnodeGetNumber(), SCIPnodeGetParent(), SCIPpqueueDelPos(), SCIPpqueueElems(), SCIPpqueueFirst(), SCIPpqueueNElems(), NodeInfo::subtreeidx, SubtreeSumGap::subtreepqueues, and SubtreeSumGap::value.

Referenced by subtreeSumGapInsertChildren(), and subtreeSumGapUpdate().

◆ subtreeSumGapInsertChildren()

SCIP_RETCODE subtreeSumGapInsertChildren	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg )

static

insert children into subtree sum gap

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure

Definition at line 1228 of file event_estim.c.

References assert(), SubtreeSumGap::nodes2info, SubtreeSumGap::nsubtrees, NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, SCIPgetChildren(), SCIPgetFocusNode(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPnodeGetNumber(), SCIPnodeGetParent(), NodeInfo::subtreeidx, subtreeSumGapRemoveNode(), and subtreeSumGapStoreNode().

Referenced by subtreeSumGapUpdate().

◆ subtreeSumGapComputeFromScratchEfficiently()

SCIP_RETCODE subtreeSumGapComputeFromScratchEfficiently	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg,
		SCIP_Bool	updatescaling )

static

compute subtree sum gap from scratch efficiently (linear effort in the number of subtrees)

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure
updatescaling	should the scaling factor be updated?

Definition at line 1393 of file event_estim.c.

References assert(), calcGap(), NodeInfo::lowerbound, MAX, SubtreeSumGap::nsubtrees, NULL, SubtreeSumGap::scalingfactor, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPisInfinity(), SCIPpqueueFirst(), SubtreeSumGap::subtreepqueues, and SubtreeSumGap::value.

Referenced by subtreeSumGapUpdate().

◆ subtreeSumGapUpdate()

SCIP_RETCODE subtreeSumGapUpdate	(	SCIP *	scip,
		SUBTREESUMGAP *	ssg,
		SCIP_NODE *	node,
		int	nchildren,
		SCIP_Longint	nsolvednodes )

static

update the subtree sum gap after a node event (branching or deletion of a node)

Parameters

scip	SCIP data structure
ssg	subtree sum gap data structure
node	the corresponding node
nchildren	number of children
nsolvednodes	number of solved nodes so far, used as a time stamp

Definition at line 1450 of file event_estim.c.

References SubtreeSumGap::nmaxsubtrees, SubtreeSumGap::nminnodeslastsplit, SubtreeSumGap::nodelastsplit, SubtreeSumGap::nsubtrees, NULL, SubtreeSumGap::pblastsplit, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_STAGE_INITSOLVE, SCIP_STAGE_SOLVED, SCIPdebugMsg, SCIPgetFocusNode(), SCIPgetNChildren(), SCIPgetNLeaves(), SCIPgetNSiblings(), SCIPgetPrimalbound(), SCIPgetStage(), SCIPgetUpperbound(), SCIPisEQ(), SCIPisInfinity(), SCIPwasNodeLastBranchParent(), subtreeSumGapComputeFromScratchEfficiently(), subtreeSumGapInsertChildren(), subtreeSumGapRemoveNode(), subtreeSumGapSplit(), TRUE, and SubtreeSumGap::value.

Referenced by updateTreeData().

◆ resetTreeData()

SCIP_RETCODE resetTreeData	(	SCIP *	scip,
		TREEDATA *	treedata )

static

reset tree data

Parameters

scip	SCIP data structure
treedata	tree data

Definition at line 1529 of file event_estim.c.

References TreeData::ninner, TreeData::nleaves, TreeData::nnodes, TreeData::nopen, TreeData::nvisited, SCIP_CALL, SCIP_OKAY, TreeData::ssg, subtreeSumGapReset(), and TreeData::weight.

Referenced by createTreeData(), and SCIP_DECL_EVENTINITSOL().

◆ createTreeData()

SCIP_RETCODE createTreeData	(	SCIP *	scip,
		TREEDATA **	treedata )

static

create tree data structure

Parameters

scip	SCIP data structure
treedata	pointer to store tree data

Definition at line 1549 of file event_estim.c.

References assert(), NULL, resetTreeData(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and subtreeSumGapCreate().

Referenced by SCIPincludeEventHdlrEstim().

◆ freeTreeData()

void freeTreeData	(	SCIP *	scip,
		TREEDATA **	treedata )

static

free tree data structure

Parameters

scip	SCIP data structure
treedata	pointer to tree data

Definition at line 1568 of file event_estim.c.

References assert(), NULL, SCIPfreeMemory, and subtreeSumGapFree().

Referenced by SCIP_DECL_EVENTFREE(), and SCIPincludeEventHdlrEstim().

◆ updateTreeData()

SCIP_RETCODE updateTreeData	(	SCIP *	scip,
		TREEDATA *	treedata,
		SCIP_NODE *	node,
		int	nchildren )

static

update tree data structure after a node has been solved/is about to be deleted

Parameters

scip	SCIP data structure
treedata	tree data
node	the corresponding node
nchildren	the number of children

Definition at line 1586 of file event_estim.c.

References assert(), depth, TreeData::ninner, TreeData::nleaves, TreeData::nnodes, TreeData::nopen, NULL, TreeData::nvisited, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisInRestart(), SCIPnodeGetDepth(), TreeData::ssg, subtreeSumGapUpdate(), and TreeData::weight.

Referenced by SCIP_DECL_EVENTEXEC().

◆ treeDataGetWbe()

SCIP_Real treeDataGetWbe ( TREEDATA * treedata )

static

get weighted backtrack estimation from this tree data

Parameters

treedata tree data

Definition at line 1622 of file event_estim.c.

References TreeData::nleaves, SCIP_Real, and TreeData::weight.

Referenced by getEnsembleEstimation(), printReport(), and SCIPgetTreesizeEstimation().

◆ doubleExpSmoothReset()

void doubleExpSmoothReset	(	DOUBLEEXPSMOOTH *	des,
		SCIP_Real	initialvalue )

static

reset double exponential smoothing

Parameters

des	double exponential smoothing data structure
initialvalue	the initial value

Definition at line 1661 of file event_estim.c.

References DoubleExpSmooth::initialvalue, DoubleExpSmooth::level, DoubleExpSmooth::n, SCIP_INVALID, SCIP_Real, and DoubleExpSmooth::trend.

Referenced by timeSeriesResample(), and timeSeriesReset().

◆ doubleExpSmoothInit()

void doubleExpSmoothInit	(	DOUBLEEXPSMOOTH *	des,
		SCIP_Real	x1 )

static

initialize a double exponential smoothing data structure

Parameters

des	double exponential smoothing data structure
x1	the first sample value

Definition at line 1674 of file event_estim.c.

References assert(), DES_USETRENDINLEVEL, DoubleExpSmooth::initialvalue, DoubleExpSmooth::level, DoubleExpSmooth::n, NULL, SCIP_Real, DoubleExpSmooth::trend, and DoubleExpSmooth::usetrendinlevel.

Referenced by doubleExpSmoothUpdate().

◆ doubleExpSmoothUpdate()

void doubleExpSmoothUpdate	(	DOUBLEEXPSMOOTH *	des,
		SCIP_Real	xnew )

static

update a double exponential smoothing data structure

Parameters

des	double exponential smoothing data structure
xnew	new sample value

Definition at line 1692 of file event_estim.c.

References DoubleExpSmooth::alpha, DoubleExpSmooth::beta, doubleExpSmoothInit(), DoubleExpSmooth::level, DoubleExpSmooth::n, SCIP_Real, DoubleExpSmooth::trend, and DoubleExpSmooth::usetrendinlevel.

Referenced by timeSeriesResample(), and timeSeriesUpdate().

◆ doubleExpSmoothGetTrend()

SCIP_Real doubleExpSmoothGetTrend ( DOUBLEEXPSMOOTH * des )

static

get the current trend (slope) computed by this double exponential smoothing

Parameters

des	double exponential smoothing data structure

Definition at line 1714 of file event_estim.c.

References assert(), DoubleExpSmooth::n, NULL, SCIP_INVALID, SCIP_Real, and DoubleExpSmooth::trend.

Referenced by getSearchCompletion(), printReport(), and timeSeriesEstimate().

◆ timeSeriesReset()

void timeSeriesReset ( TIMESERIES * timeseries )

static

reset time series

Parameters

timeseries pointer to store time series

Definition at line 1728 of file event_estim.c.

References TimeSeries::currentvalue, TimeSeries::des, doubleExpSmoothReset(), TimeSeries::initialvalue, TimeSeries::nobs, TimeSeries::nvals, TimeSeries::resolution, SCIP_INVALID, and TimeSeries::smoothestimation.

Referenced by resetTimeSeries(), and timeSeriesCreate().

◆ timeSeriesCreate()

SCIP_RETCODE timeSeriesCreate	(	SCIP *	scip,
		TIMESERIES **	timeseries,
		const char *	name,
		SCIP_Real	targetvalue,
		SCIP_Real	initialvalue,
		SCIP_Real	alpha,
		SCIP_Real	beta )

static

create a time series object

Parameters

scip	SCIP data structure
timeseries	pointer to store time series
name	name of this time series
targetvalue	target value of this time series
initialvalue	the initial value of time series
alpha	alpha parameter (level weight) for double exponential smoothing
beta	beta parameter (level weight) for double exponential smoothing update callback at nodes, or NULL

Definition at line 1743 of file event_estim.c.

References alpha, DoubleExpSmooth::alpha, assert(), DoubleExpSmooth::beta, BMSduplicateMemoryArray, DECL_TIMESERIESUPDATE, TimeSeries::des, TimeSeries::estimation, TimeSeries::initialvalue, TimeSeries::name, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, SCIPdebugMsg, TimeSeries::targetvalue, timeSeriesReset(), TimeSeries::vals, and TimeSeries::valssize.

Referenced by includeTimeseries().

◆ timeSeriesFree()

void timeSeriesFree	(	SCIP *	scip,
		TIMESERIES **	timeseries )

static

free a time series

Parameters

scip	SCIP data structure
timeseries	pointer to time series

Definition at line 1792 of file event_estim.c.

References assert(), BMSfreeMemoryArray, NULL, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by freeTimeSeries().

◆ timeSeriesGetValue()

SCIP_Real timeSeriesGetValue ( TIMESERIES * timeseries )

static

get current value of time series

Parameters

timeseries time series

Definition at line 1812 of file event_estim.c.

References assert(), TimeSeries::currentvalue, NULL, and SCIP_Real.

Referenced by DECL_TIMESERIESUPDATE(), getSearchCompletion(), printReport(), timeSeriesEstimate(), and updateTimeseries().

◆ timeSeriesGetTargetValue()

SCIP_Real timeSeriesGetTargetValue ( TIMESERIES * timeseries )

static

get target value (which this time series reaches at the end of the solution process)

Parameters

timeseries time series

Definition at line 1823 of file event_estim.c.

References SCIP_Real, and TimeSeries::targetvalue.

Referenced by timeSeriesEstimate().

◆ timeSeriesGetResolution()

int timeSeriesGetResolution ( TIMESERIES * timeseries )

static

get resolution of time series

Parameters

timeseries time series

Definition at line 1832 of file event_estim.c.

References TimeSeries::resolution.

Referenced by printReport(), and timeSeriesEstimate().

◆ timeSeriesEstimate()

SCIP_Real timeSeriesEstimate	(	TIMESERIES *	timeseries,
		TREEDATA *	treedata )

static

estimate tree size at which time series reaches target value

Parameters

timeseries	time series
treedata	tree data for fallback estimation

Definition at line 1841 of file event_estim.c.

References TimeSeries::des, doubleExpSmoothGetTrend(), EPSZ, TreeData::nnodes, TimeSeries::nobs, TimeSeries::nvals, SCIP_Real, timeSeriesGetResolution(), timeSeriesGetTargetValue(), timeSeriesGetValue(), and TimeSeries::useleafts.

Referenced by getEnsembleEstimation(), printReport(), SCIPgetTreesizeEstimation(), and timeSeriesUpdate().

◆ timeSeriesUpdateSmoothEstimation()

void timeSeriesUpdateSmoothEstimation	(	TIMESERIES *	timeseries,
		SCIP_Real	estimation )

static

update time series smoothened estimation

Parameters

timeseries	time series
estimation	estimation value

Definition at line 1878 of file event_estim.c.

References SCIP_INVALID, SCIP_Real, SESCOEFF, and TimeSeries::smoothestimation.

Referenced by timeSeriesResample(), and timeSeriesUpdate().

◆ timeSeriesGetSmoothEstimation()

SCIP_Real timeSeriesGetSmoothEstimation ( TIMESERIES * timeseries )

static

get smooth estimation of time series

Parameters

timeseries time series

Definition at line 1894 of file event_estim.c.

References SCIP_Real, and TimeSeries::smoothestimation.

Referenced by printReport().

◆ timeSeriesResample()

void timeSeriesResample ( TIMESERIES * timeseries )

static

resample to lower resolution

Parameters

timeseries time series

Definition at line 1903 of file event_estim.c.

References assert(), TimeSeries::des, doubleExpSmoothReset(), doubleExpSmoothUpdate(), TimeSeries::estimation, i, TimeSeries::initialvalue, TimeSeries::nvals, TimeSeries::resolution, timeSeriesUpdateSmoothEstimation(), and TimeSeries::vals.

Referenced by timeSeriesUpdate().

◆ timeSeriesUpdate()

SCIP_RETCODE timeSeriesUpdate	(	SCIP *	scip,
		TIMESERIES *	timeseries,
		TREEDATA *	treedata,
		SCIP_Bool	isleaf )

static

update time series

Parameters

scip	SCIP data structure
timeseries	time series
treedata	tree data
isleaf	are we at a leaf node?

Definition at line 1930 of file event_estim.c.

References assert(), TimeSeries::currentvalue, TimeSeries::des, doubleExpSmoothUpdate(), TimeSeries::estimation, TimeSeries::nobs, NULL, TimeSeries::nvals, TimeSeries::resolution, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, timeSeriesEstimate(), timeSeriesResample(), timeSeriesUpdateSmoothEstimation(), TimeSeries::useleafts, TimeSeries::vals, and TimeSeries::valssize.

Referenced by updateTimeseries().

◆ timeSeriesGetName()

char * timeSeriesGetName ( TIMESERIES * timeseries )

static

get name of time series

Parameters

timeseries time series

Definition at line 1979 of file event_estim.c.

References TimeSeries::name.

Referenced by printReport(), and updateTimeseries().

◆ resetTimeSeries()

void resetTimeSeries ( SCIP_EVENTHDLRDATA * eventhdlrdata )

static

reset all time series

Parameters

eventhdlrdata event handler data

Definition at line 1988 of file event_estim.c.

References assert(), NTIMESERIES, NULL, timeSeriesReset(), and TimeSeries::useleafts.

Referenced by SCIP_DECL_EVENTINITSOL().

◆ freeTimeSeries()

void freeTimeSeries	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata )

static

free all time series

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 2011 of file event_estim.c.

References assert(), NTIMESERIES, NULL, and timeSeriesFree().

Referenced by SCIP_DECL_EVENTFREE().

◆ getEnsembleEstimation()

SCIP_Real getEnsembleEstimation ( SCIP_EVENTHDLRDATA * eventhdlrdata )

static

get ensemble tree size estimation as a combination of the individual time series estimations

the coefficients have been computed based on a nonlinear fit on a broad set of publicly available MIP instances; please refer to the publication at the top of this file for further details.

Parameters

eventhdlrdata event handler data

Definition at line 2033 of file event_estim.c.

References assert(), nnodes, TreeData::nnodes, NTIMESERIES, NULL, SCIP_Real, timeSeriesEstimate(), treeDataGetWbe(), TSPOS_GAP, TSPOS_LFREQ, TSPOS_OPEN, TSPOS_SSG, TSPOS_TREEWEIGHT, and TreeData::weight.

Referenced by SCIPgetTreesizeEstimation().

◆ getSearchCompletion()

SCIP_RETCODE getSearchCompletion	(	SCIP_EVENTHDLRDATA *	eventhdlrdata,
		SCIP_Real *	completed )

static

get approximation of search tree completion depending on the selected method

Parameters

eventhdlrdata	event handler data
completed	pointer to store the search tree completion

Definition at line 2128 of file event_estim.c.

References assert(), COMPLETIONTYPE_AUTO, COMPLETIONTYPE_GAP, COMPLETIONTYPE_MONOREG, COMPLETIONTYPE_REGFOREST, COMPLETIONTYPE_SSG, COMPLETIONTYPE_TREEWEIGHT, doubleExpSmoothGetTrend(), NULL, SubtreeSumGap::pblastsplit, SCIP_Bool, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPABORT, SCIPerrorMessage, SCIPregForestPredict(), TreeData::ssg, SSG_STARTPRIMBOUND, timeSeriesGetValue(), TSPOS_GAP, TSPOS_LFREQ, TSPOS_OPEN, TSPOS_SSG, TSPOS_TREEWEIGHT, SubtreeSumGap::value, and TreeData::weight.

Referenced by getEstimCompletion(), printReport(), SCIP_DECL_DISPOUTPUT(), and shouldApplyRestartCompletion().

◆ getEstimCompletion()

SCIP_RETCODE getEstimCompletion	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata,
		SCIP_Real *	estim )

static

tree size estimation based on search tree completion

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
estim	pointer to store the estimation value

Definition at line 2214 of file event_estim.c.

References getSearchCompletion(), MIN, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPgetNNodes().

Referenced by SCIPgetTreesizeEstimation().

◆ DECL_TIMESERIESUPDATE() [1/5]

DECL_TIMESERIESUPDATE ( timeseriesUpdateGap )

static

update callback at nodes

Definition at line 2236 of file event_estim.c.

References assert(), MAX, NULL, REALABS, SCIP_OKAY, SCIP_Real, SCIPgetDualbound(), SCIPgetPrimalbound(), SCIPisEQ(), SCIPisInfinity(), SCIPisInRestart(), and timeSeriesGetValue().

◆ DECL_TIMESERIESUPDATE() [2/5]

DECL_TIMESERIESUPDATE ( timeseriesUpdateTreeWeight )

static

update callback at nodes

Definition at line 2277 of file event_estim.c.

References SCIP_OKAY, SCIP_Real, and TreeData::weight.

◆ DECL_TIMESERIESUPDATE() [3/5]

DECL_TIMESERIESUPDATE ( timeseriesUpdateLeafFreq )

static

update callback at nodes

Definition at line 2286 of file event_estim.c.

References TreeData::nleaves, TreeData::nvisited, SCIP_OKAY, and SCIP_Real.

◆ DECL_TIMESERIESUPDATE() [4/5]

DECL_TIMESERIESUPDATE ( timeseriesUpdateSsg )

static

update callback at nodes

Definition at line 2298 of file event_estim.c.

References TreeData::nvisited, SCIP_OKAY, TreeData::ssg, and SubtreeSumGap::value.

◆ DECL_TIMESERIESUPDATE() [5/5]

DECL_TIMESERIESUPDATE ( timeseriesUpdateOpenNodes )

static

update callback at nodes

Definition at line 2310 of file event_estim.c.

References TreeData::nopen, TreeData::nvisited, SCIP_OKAY, and SCIP_Real.

◆ includeTimeseries()

SCIP_RETCODE includeTimeseries	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata )

static

include time series to forecast into event handler

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 2322 of file event_estim.c.

References assert(), DES_ALPHA_GAP, DES_ALPHA_LEAFFREQUENCY, DES_ALPHA_OPENNODES, DES_ALPHA_SSG, DES_ALPHA_TREEWEIGHT, DES_BETA_GAP, DES_BETA_LEAFFREQUENCY, DES_BETA_OPENNODES, DES_BETA_SSG, DES_BETA_TREEWEIGHT, NULL, SCIP_CALL, SCIP_OKAY, timeSeriesCreate(), TSPOS_GAP, TSPOS_LFREQ, TSPOS_OPEN, TSPOS_SSG, and TSPOS_TREEWEIGHT.

Referenced by SCIPincludeEventHdlrEstim().

◆ getRestartPolicy()

RESTARTPOLICY getRestartPolicy ( SCIP_EVENTHDLRDATA * eventhdlrdata )

static

get restartpolicy based on the value of the restart parameter

Parameters

eventhdlrdata event handler data

Definition at line 2355 of file event_estim.c.

References RESTARTPOLICY_ALWAYS, RESTARTPOLICY_CHAR_ALWAYS, RESTARTPOLICY_CHAR_COMPLETION, RESTARTPOLICY_CHAR_ESTIMATION, RESTARTPOLICY_CHAR_NEVER, RESTARTPOLICY_COMPLETION, RESTARTPOLICY_ESTIMATION, RESTARTPOLICY_NEVER, and SCIPerrorMessage.

Referenced by shouldApplyRestart().

◆ isRestartApplicable()

SCIP_Bool isRestartApplicable	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata )

static

check if a restart is applicable considering limit and threshold user parameters

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 2379 of file event_estim.c.

References FALSE, nnodes, SCIP_Bool, SCIP_Longint, SCIPgetNActivePricers(), SCIPgetNRootIntFixingsRun(), SCIPisNLPConstructed(), and TRUE.

Referenced by SCIP_DECL_EVENTEXEC().

◆ shouldApplyRestartCompletion()

SCIP_Bool shouldApplyRestartCompletion	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata )

static

should a restart be applied based on the value of the selected completion method?

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 2416 of file event_estim.c.

References FALSE, getSearchCompletion(), NULL, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPstatistic, SCIPverbMessage(), and TRUE.

Referenced by shouldApplyRestart().

◆ shouldApplyRestartEstimation()

SCIP_Bool shouldApplyRestartEstimation	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata )

static

should a restart be applied based on the value of the selected completion method?

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 2442 of file event_estim.c.

References FALSE, NULL, SCIP_Bool, SCIP_LONGINT_FORMAT, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPgetTreesizeEstimation(), SCIPstatistic, SCIPverbMessage(), and TRUE.

Referenced by shouldApplyRestart().

◆ shouldApplyRestart()

SCIP_Bool shouldApplyRestart	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata )

static

check if a restart should be performed based on the given restart policy

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data

Definition at line 2479 of file event_estim.c.

References FALSE, getRestartPolicy(), RESTARTPOLICY_ALWAYS, RESTARTPOLICY_COMPLETION, RESTARTPOLICY_ESTIMATION, RESTARTPOLICY_NEVER, SCIP_Bool, shouldApplyRestartCompletion(), shouldApplyRestartEstimation(), and TRUE.

Referenced by SCIP_DECL_EVENTEXEC().

◆ updateTimeseries()

SCIP_RETCODE updateTimeseries	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata,
		TREEDATA *	treedata,
		SCIP_Bool	isleaf )

static

update all time series

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
treedata	tree data
isleaf	are we at a leaf node?

Definition at line 2509 of file event_estim.c.

References assert(), NTIMESERIES, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPdebugMsg, timeSeriesGetName(), timeSeriesGetValue(), and timeSeriesUpdate().

Referenced by SCIP_DECL_EVENTEXEC().

◆ printReport()

void printReport	(	SCIP *	scip,
		SCIP_EVENTHDLRDATA *	eventhdlrdata,
		char *	strbuf,
		int	reportnum )

static

print a treesize estimation report into the string buffer

Parameters

scip	SCIP data structure
eventhdlrdata	event handler data
strbuf	string buffer
reportnum	report number, or 0 to omit number

Definition at line 2537 of file event_estim.c.

References TimeSeries::des, doubleExpSmoothGetTrend(), getSearchCompletion(), MAX, MIN, TreeData::ninner, TreeData::nleaves, TreeData::nnodes, TreeData::nopen, NTIMESERIES, TreeData::nvisited, predictTotalSizeTreeProfile(), real2String(), SCIP_CALL_ABORT, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_Real, SCIPgetSolvingTime(), SCIPgetTreesizeEstimation(), SCIPsnprintf(), timeSeriesEstimate(), timeSeriesGetName(), timeSeriesGetResolution(), timeSeriesGetSmoothEstimation(), timeSeriesGetValue(), treeDataGetWbe(), and TreeData::weight.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIP_DECL_TABLEOUTPUT().

◆ SCIP_DECL_EVENTCOPY()

SCIP_DECL_EVENTCOPY ( eventCopyEstim )

static

copy method for event handler plugins (called when SCIP copies plugins)

Definition at line 2623 of file event_estim.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPincludeEventHdlrEstim().

◆ SCIP_DECL_EVENTFREE()

SCIP_DECL_EVENTFREE ( eventFreeEstim )

static

destructor of event handler to free user data (called when SCIP is exiting)

Definition at line 2634 of file event_estim.c.

References assert(), freeTimeSeries(), freeTreeData(), NULL, SCIP_OKAY, SCIPeventhdlrGetData(), and SCIPfreeMemory.

◆ SCIP_DECL_EVENTINIT()

SCIP_DECL_EVENTINIT ( eventInitEstim )

static

initialization method of event handler (called after problem was transformed)

Definition at line 2652 of file event_estim.c.

References assert(), DEFAULT_REGFORESTFILENAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPeventhdlrGetData(), and SCIPregForestFromFile().

◆ SCIP_DECL_EVENTEXIT()

SCIP_DECL_EVENTEXIT ( eventExitEstim )

static

deinitialization method of event handler (called before transformed problem is freed)

Definition at line 2673 of file event_estim.c.

References assert(), NULL, SCIP_OKAY, SCIPeventhdlrGetData(), and SCIPregForestFree().

◆ SCIP_DECL_EVENTINITSOL()

SCIP_DECL_EVENTINITSOL ( eventInitsolEstim )

static

solving process initialization method of event handler (called when branch and bound process is about to begin)

Definition at line 2687 of file event_estim.c.

References assert(), createTreeProfile(), EVENTTYPE_ESTIM, NULL, resetTimeSeries(), resetTreeData(), SCIP_CALL, SCIP_OKAY, SCIPcatchEvent(), SCIPeventhdlrGetData(), and TRUE.

◆ SCIP_DECL_EVENTEXITSOL()

SCIP_DECL_EVENTEXITSOL ( eventExitsolEstim )

static

solving process deinitialization method of event handler (called before branch and bound process data is freed)

Definition at line 2717 of file event_estim.c.

References assert(), EVENTTYPE_ESTIM, freeTreeProfile(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdropEvent(), and SCIPeventhdlrGetData().

◆ SCIP_DECL_EVENTEXEC()

SCIP_DECL_EVENTEXEC ( eventExecEstim )

static

execution method of event handler

Definition at line 2734 of file event_estim.c.

References assert(), FALSE, isRestartApplicable(), NULL, printReport(), SCIP_CALL, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_EVENTTYPE_NODEDELETE, SCIP_MAXSTRLEN, SCIP_NODETYPE_CHILD, SCIP_NODETYPE_DEADEND, SCIP_NODETYPE_LEAF, SCIP_NODETYPE_SIBLING, SCIP_OKAY, SCIP_Real, SCIP_STATUS_UNKNOWN, SCIP_VERBLEVEL_HIGH, SCIPdebugMsg, SCIPeventGetNode(), SCIPeventGetType(), SCIPeventhdlrGetData(), SCIPfloor(), SCIPgetNChildren(), SCIPgetNRuns(), SCIPgetStatus(), SCIPisExact(), SCIPnodeGetType(), SCIPrestartSolve(), SCIPverbMessage(), SCIPwasNodeLastBranchParent(), shouldApplyRestart(), updateTimeseries(), updateTreeData(), updateTreeProfile(), and TreeData::weight.

◆ SCIP_DECL_TABLEOUTPUT()

SCIP_DECL_TABLEOUTPUT ( tableOutputEstim )

static

output method of statistics table to output file stream 'file'

Definition at line 2839 of file event_estim.c.

References assert(), EVENTHDLR_NAME, NULL, printReport(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIPeventhdlrGetData(), SCIPfindEventhdlr(), and SCIPinfoMessage().

◆ SCIP_DECL_DISPOUTPUT()

SCIP_DECL_DISPOUTPUT ( dispOutputCompleted )

static

output method of search tree completion display column to output file stream 'file'

Definition at line 2862 of file event_estim.c.

References assert(), DISP_NAME, EVENTHDLR_NAME, getSearchCompletion(), MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdispGetName(), SCIPeventhdlrGetData(), SCIPfindEventhdlr(), SCIPinfoMessage(), and TreeData::weight.

◆ SCIPincludeEventHdlrEstim()

SCIP_RETCODE SCIPincludeEventHdlrEstim ( SCIP * scip )

creates event handler for tree size estimation

Parameters

scip	SCIP data structure

Definition at line 2892 of file event_estim.c.

References assert(), BMSclearMemory, createTreeData(), DEFAULT_COEFMONOSSG, DEFAULT_COEFMONOWEIGHT, DEFAULT_COMPLETIONTYPE, DEFAULT_COUNTONLYLEAVES, DEFAULT_ESTIMMETHOD, DEFAULT_HITCOUNTERLIM, DEFAULT_MINNODES, DEFAULT_REGFORESTFILENAME, DEFAULT_REPORTFREQ, DEFAULT_RESTARTACTPRICERS, DEFAULT_RESTARTFACTOR, DEFAULT_RESTARTLIMIT, DEFAULT_RESTARTNONLINEAR, DEFAULT_RESTARTPOLICY, DEFAULT_SHOWSTATS, DEFAULT_SSG_NMAXSUBTREES, DEFAULT_SSG_NMINNODESLASTSPLIT, DEFAULT_TREEPROFILE_ENABLED, DEFAULT_TREEPROFILE_MINNODESPERDEPTH, DEFAULT_USELEAFTS, DISP_DESC, DISP_HEADER, DISP_NAME, DISP_POSITION, DISP_PRIORITY, DISP_STRIPLINE, DISP_WIDTH, ESTIMMETHODS, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, freeTreeData(), includeTimeseries(), NULL, SCIP_CALL, SCIP_CALL_TERMINATE, SCIP_DISPSTATUS_AUTO, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPaddStringParam(), SCIPallocMemory, SCIPfreeMemory, SCIPincludeDisp(), SCIPincludeEventhdlrBasic(), SCIPincludeTable(), SCIPsetEventhdlrCopy(), SCIPsetEventhdlrExit(), SCIPsetEventhdlrExitsol(), SCIPsetEventhdlrFree(), SCIPsetEventhdlrInit(), SCIPsetEventhdlrInitsol(), TABLE_DESC, TABLE_EARLIEST_STAGE, TABLE_NAME, TABLE_POSITION, and TRUE.

Referenced by SCIP_DECL_EVENTCOPY(), and SCIPincludeDefaultPlugins().

◆ SCIPgetTreesizeEstimation()

SCIP_Real SCIPgetTreesizeEstimation ( SCIP * scip )

return an estimation of the final tree size

Parameters

scip	SCIP data structure

Definition at line 3020 of file event_estim.c.

References assert(), ESTIMMETHOD_COMPL, ESTIMMETHOD_ENSMBL, ESTIMMETHOD_GAP, ESTIMMETHOD_LFREQ, ESTIMMETHOD_OPEN, ESTIMMETHOD_SSG, ESTIMMETHOD_TPROF, ESTIMMETHOD_TREEWEIGHT, ESTIMMETHOD_WBE, ESTIMMETHODS, EVENTHDLR_NAME, getEnsembleEstimation(), getEstimCompletion(), NULL, predictTotalSizeTreeProfile(), SCIP_CALL_ABORT, SCIP_Real, SCIPABORT, SCIPerrorMessage, SCIPeventhdlrGetData(), SCIPfindEventhdlr(), SCIPwarningMessage(), timeSeriesEstimate(), treeDataGetWbe(), TSPOS_GAP, TSPOS_LFREQ, TSPOS_NONE, TSPOS_OPEN, TSPOS_SSG, and TSPOS_TREEWEIGHT.

Referenced by printReport(), and shouldApplyRestartEstimation().

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ EVENTTYPE_ESTIM

◆ RESTARTPOLICY_CHAR_NEVER

◆ RESTARTPOLICY_CHAR_ALWAYS

◆ RESTARTPOLICY_CHAR_COMPLETION

◆ RESTARTPOLICY_CHAR_ESTIMATION

◆ DES_USETRENDINLEVEL

◆ TABLE_NAME

◆ TABLE_DESC

◆ TABLE_POSITION

◆ TABLE_EARLIEST_STAGE

◆ DISP_NAME

◆ DISP_DESC

◆ DISP_HEADER

◆ DISP_WIDTH

◆ DISP_PRIORITY

◆ DISP_POSITION

◆ DISP_STRIPLINE

◆ INITIALSIZE

◆ SESCOEFF

◆ DES_ALPHA_TREEWEIGHT

◆ DES_BETA_TREEWEIGHT

◆ DES_ALPHA_GAP

◆ DES_BETA_GAP

◆ DES_ALPHA_LEAFFREQUENCY

◆ DES_BETA_LEAFFREQUENCY

◆ DES_ALPHA_SSG

◆ DES_BETA_SSG

◆ DES_ALPHA_OPENNODES

◆ DES_BETA_OPENNODES

◆ MAX_REGFORESTSIZE

◆ COMPLETIONTYPE_AUTO

◆ COMPLETIONTYPE_REGFOREST

◆ COMPLETIONTYPE_MONOREG

◆ COMPLETIONTYPE_TREEWEIGHT

◆ COMPLETIONTYPE_SSG

◆ COMPLETIONTYPE_GAP

◆ ESTIMMETHOD_COMPL

◆ ESTIMMETHOD_WBE

◆ ESTIMMETHOD_ENSMBL

◆ ESTIMMETHOD_GAP

◆ ESTIMMETHOD_LFREQ

◆ ESTIMMETHOD_OPEN

◆ ESTIMMETHOD_SSG

◆ ESTIMMETHOD_TPROF

◆ ESTIMMETHOD_TREEWEIGHT

◆ ESTIMMETHODS

◆ TREEPROFILE_MINSIZE

◆ SSG_STARTPRIMBOUND

◆ NTIMESERIES

◆ DEFAULT_USELEAFTS

◆ DEFAULT_REPORTFREQ

◆ DEFAULT_REGFORESTFILENAME

◆ DEFAULT_COEFMONOWEIGHT

◆ DEFAULT_COEFMONOSSG

◆ DEFAULT_COMPLETIONTYPE

◆ DEFAULT_ESTIMMETHOD

◆ DEFAULT_TREEPROFILE_ENABLED

◆ DEFAULT_TREEPROFILE_MINNODESPERDEPTH

◆ DEFAULT_RESTARTPOLICY

◆ DEFAULT_RESTARTLIMIT

◆ DEFAULT_MINNODES

◆ DEFAULT_COUNTONLYLEAVES

◆ DEFAULT_RESTARTFACTOR

◆ DEFAULT_RESTARTNONLINEAR

◆ DEFAULT_RESTARTACTPRICERS

◆ DEFAULT_HITCOUNTERLIM

◆ DEFAULT_SSG_NMAXSUBTREES

◆ DEFAULT_SSG_NMINNODESLASTSPLIT

◆ DEFAULT_SHOWSTATS

◆ DECL_TIMESERIESUPDATE

Typedef Documentation

◆ RESTARTPOLICY

◆ DOUBLEEXPSMOOTH