Scippy

SCIP

Solving Constraint Integer Programs

event_estim.c File Reference

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)
 

Typedefs

typedef enum RestartPolicy RESTARTPOLICY
 
typedef struct DoubleExpSmooth DOUBLEEXPSMOOTH
 
typedef struct TimeSeries TIMESERIES
 
typedef struct TreeData TREEDATA
 
typedef enum TsPos TSPOS
 
typedef struct SCIP_RegForest SCIP_REGFOREST
 
typedef struct TreeProfileStats TREEPROFILESTATS
 
typedef struct TreeProfile TREEPROFILE
 
typedef struct SubtreeSumGap SUBTREESUMGAP
 
typedef struct NodeInfo NODEINFO
 

Enumerations

enum  RestartPolicy {
  RESTARTPOLICY_NEVER = 0,
  RESTARTPOLICY_ALWAYS = 1,
  RESTARTPOLICY_ESTIMATION = 2,
  RESTARTPOLICY_COMPLETION = 3
}
 
enum  TsPos {
  TSPOS_NONE = -1,
  TSPOS_GAP = 0,
  TSPOS_TREEWEIGHT = 1,
  TSPOS_LFREQ = 2,
  TSPOS_SSG = 3,
  TSPOS_OPEN = 4
}
 

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, DECL_TIMESERIESUPDATE((*timeseriesupdate)))
 
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 char * 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 82 of file event_estim.c.

◆ EVENTHDLR_DESC

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

Definition at line 83 of file event_estim.c.

◆ EVENTTYPE_ESTIM

#define EVENTTYPE_ESTIM   (SCIP_EVENTTYPE_NODEDELETE | SCIP_EVENTTYPE_NODEBRANCHED)

Definition at line 84 of file event_estim.c.

◆ RESTARTPOLICY_CHAR_NEVER

#define RESTARTPOLICY_CHAR_NEVER   'n'

Definition at line 101 of file event_estim.c.

Referenced by getRestartPolicy().

◆ RESTARTPOLICY_CHAR_ALWAYS

#define RESTARTPOLICY_CHAR_ALWAYS   'a'

Definition at line 102 of file event_estim.c.

Referenced by getRestartPolicy().

◆ RESTARTPOLICY_CHAR_COMPLETION

#define RESTARTPOLICY_CHAR_COMPLETION   'c'

Definition at line 103 of file event_estim.c.

Referenced by getRestartPolicy().

◆ RESTARTPOLICY_CHAR_ESTIMATION

#define RESTARTPOLICY_CHAR_ESTIMATION   'e'

Definition at line 104 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 106 of file event_estim.c.

Referenced by doubleExpSmoothInit().

◆ TABLE_NAME

#define TABLE_NAME   "estim"

Definition at line 109 of file event_estim.c.

◆ TABLE_DESC

#define TABLE_DESC   "tree size estimations statistics table"

Definition at line 110 of file event_estim.c.

◆ TABLE_POSITION

#define TABLE_POSITION   18500

the position of the statistics table

Definition at line 111 of file event_estim.c.

◆ 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 112 of file event_estim.c.

◆ DISP_NAME

#define DISP_NAME   "completed"

Definition at line 115 of file event_estim.c.

◆ DISP_DESC

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

Definition at line 116 of file event_estim.c.

◆ DISP_HEADER

#define DISP_HEADER   "compl."

Definition at line 117 of file event_estim.c.

◆ DISP_WIDTH

#define DISP_WIDTH   8

the width of the display column

Definition at line 118 of file event_estim.c.

◆ DISP_PRIORITY

#define DISP_PRIORITY   110000

the priority of the display column

Definition at line 119 of file event_estim.c.

◆ DISP_POSITION

#define DISP_POSITION   30100

the relative position of the display column

Definition at line 120 of file event_estim.c.

◆ 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 121 of file event_estim.c.

◆ INITIALSIZE

#define INITIALSIZE   100

Definition at line 124 of file event_estim.c.

Referenced by 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.

◆ ESTIMMETHOD_WBE

#define ESTIMMETHOD_WBE   'b'

weighted backtrack estimation

Definition at line 158 of file event_estim.c.

◆ ESTIMMETHOD_ENSMBL

#define ESTIMMETHOD_ENSMBL   'e'

estimation based on an ensemble of the individual estimations

Definition at line 159 of file event_estim.c.

◆ ESTIMMETHOD_GAP

#define ESTIMMETHOD_GAP   'g'

estimation based on double exponential smoothing for open nodes

Definition at line 160 of file event_estim.c.

◆ ESTIMMETHOD_LFREQ

#define ESTIMMETHOD_LFREQ   'l'

estimation based on double exponential smoothing for leaf frequency

Definition at line 161 of file event_estim.c.

◆ ESTIMMETHOD_OPEN

#define ESTIMMETHOD_OPEN   'o'

estimation based on double exponential smoothing for open nodes

Definition at line 162 of file event_estim.c.

◆ 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.

◆ ESTIMMETHOD_TPROF

#define ESTIMMETHOD_TPROF   't'

estimation based on tree profile method

Definition at line 164 of file event_estim.c.

◆ ESTIMMETHOD_TREEWEIGHT

#define ESTIMMETHOD_TREEWEIGHT   'w'

estimation based on double exponential smoothing for tree weight

Definition at line 165 of file event_estim.c.

◆ ESTIMMETHODS

#define ESTIMMETHODS   "bceglostw"

Definition at line 167 of file event_estim.c.

◆ 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

◆ 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.

◆ 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.

◆ DEFAULT_REGFORESTFILENAME

#define DEFAULT_REGFORESTFILENAME   "-"

default file name of user regression forest in RFCSV format

Definition at line 245 of file event_estim.c.

◆ 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.

◆ 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.

◆ DEFAULT_COMPLETIONTYPE

#define DEFAULT_COMPLETIONTYPE   COMPLETIONTYPE_AUTO

default computation of search tree completion

Definition at line 248 of file event_estim.c.

◆ 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.

◆ DEFAULT_TREEPROFILE_ENABLED

#define DEFAULT_TREEPROFILE_ENABLED   FALSE

Should the event handler collect data?

Definition at line 254 of file event_estim.c.

◆ DEFAULT_TREEPROFILE_MINNODESPERDEPTH

#define DEFAULT_TREEPROFILE_MINNODESPERDEPTH   20.0

minimum average number of nodes at each depth before producing estimations

Definition at line 255 of file event_estim.c.

◆ DEFAULT_RESTARTPOLICY

#define DEFAULT_RESTARTPOLICY   'e'

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

Definition at line 256 of file event_estim.c.

◆ DEFAULT_RESTARTLIMIT

#define DEFAULT_RESTARTLIMIT   1

default restart limit

Definition at line 257 of file event_estim.c.

◆ DEFAULT_MINNODES

#define DEFAULT_MINNODES   1000L

minimum number of nodes before restart

Definition at line 258 of file event_estim.c.

◆ DEFAULT_COUNTONLYLEAVES

#define DEFAULT_COUNTONLYLEAVES   FALSE

should only leaves count for the minnodes parameter?

Definition at line 259 of file event_estim.c.

◆ 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 260 of file event_estim.c.

◆ DEFAULT_RESTARTNONLINEAR

#define DEFAULT_RESTARTNONLINEAR   FALSE

whether to apply a restart when nonlinear constraints are present

Definition at line 261 of file event_estim.c.

◆ DEFAULT_RESTARTACTPRICERS

#define DEFAULT_RESTARTACTPRICERS   FALSE

whether to apply a restart when active pricers are used

Definition at line 262 of file event_estim.c.

◆ DEFAULT_HITCOUNTERLIM

#define DEFAULT_HITCOUNTERLIM   50

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

Definition at line 263 of file event_estim.c.

◆ 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 264 of file event_estim.c.

◆ DEFAULT_SSG_NMINNODESLASTSPLIT

#define DEFAULT_SSG_NMINNODESLASTSPLIT   0L

minimum number of nodes to process between two consecutive SSG splits

Definition at line 267 of file event_estim.c.

◆ DEFAULT_SHOWSTATS

#define DEFAULT_SHOWSTATS   FALSE

should statistics be shown at the end?

Definition at line 268 of file event_estim.c.

◆ DECL_TIMESERIESUPDATE

#define DECL_TIMESERIESUPDATE (   x)
Value:
SCIP* scip, \
TIMESERIES* ts, \
TREEDATA* treedata, \
SCIP_Real* value \
)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_VAR ** x
Definition: circlepacking.c:63
#define SCIP_Real
Definition: def.h:186

update callback of time series

Definition at line 334 of file event_estim.c.

Referenced by getEstimCompletion().

Typedef Documentation

◆ RESTARTPOLICY

Definition at line 99 of file event_estim.c.

◆ 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

regression forest data structure

Definition at line 216 of file event_estim.c.

◆ 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 306 of file event_estim.c.

◆ NODEINFO

typedef struct NodeInfo NODEINFO

Definition at line 368 of file event_estim.c.

Enumeration Type Documentation

◆ 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 91 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()

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

convert number to string and treat SCIP_INVALID as '-'

Parameters
numnumber to convert to string
bufstring buffer
digitsnumber of decimal digits

Definition at line 387 of file event_estim.c.

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

Referenced by printReport().

◆ SCIPregForestFree()

static void SCIPregForestFree ( SCIP_REGFOREST **  regforest)
static

free a regression forest data structure

Parameters
regforestregression forest data structure

Definition at line 405 of file event_estim.c.

Referenced by real2String(), and SCIPregForestFromFile().

◆ SCIPregForestPredict()

static SCIP_Real SCIPregForestPredict ( SCIP_REGFOREST regforest,
SCIP_Real datapoint 
)
static

make a prediction with regression forest

Parameters
regforestregression forest data structure
datapointa data point that matches the dimension of this regression forest

Definition at line 427 of file event_estim.c.

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

Referenced by getSearchCompletion().

◆ SCIPregForestFromFile()

static 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
regforestregression forest data structure
filenamename of file with the regression forest data

Definition at line 474 of file event_estim.c.

References BMSallocMemory, BMSallocMemoryArray, BMSclearMemory, SCIP_RegForest::child, SCIP_RegForest::dim, FALSE, isEqualTreeProfileStats(), 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 SCIPregForestPredict().

◆ isEqualTreeProfileStats()

static SCIP_Bool isEqualTreeProfileStats ( TREEPROFILESTATS stats,
TREEPROFILESTATS other 
)
static

compare two tree profile statistics for equality

Parameters
statsfirst tree profile statistics
otherother tree profile statistics

Definition at line 611 of file event_estim.c.

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

Referenced by predictTotalSizeTreeProfile(), and SCIPregForestFromFile().

◆ copyTreeProfileStats()

static void copyTreeProfileStats ( TREEPROFILESTATS dest,
TREEPROFILESTATS src 
)
static

copy source tree profile into destination

Parameters
destdestination tree profile statistics
srcsource tree profile statistics

Definition at line 627 of file event_estim.c.

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

Referenced by isEqualTreeProfileStats(), and predictTotalSizeTreeProfile().

◆ resetTreeProfileStats()

static void resetTreeProfileStats ( TREEPROFILESTATS treeprofilestats)
static

reset tree profile statistics

Parameters
treeprofilestatstree profile statistics

Definition at line 643 of file event_estim.c.

Referenced by copyTreeProfileStats(), and createTreeProfile().

◆ extendMemoryTreeProfile()

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

extend tree profile to deeper tree

Parameters
scipSCIP data structure
treeprofiletree profile data structure
mindepthminimum depth that the tree profile should hold

Definition at line 655 of file event_estim.c.

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

Referenced by createTreeProfile(), and updateTreeProfile().

◆ createTreeProfile()

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

create a tree profile

Parameters
scipSCIP data structure
treeprofilepointer to store tree profile data structure

Definition at line 690 of file event_estim.c.

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

Referenced by extendMemoryTreeProfile().

◆ freeTreeProfile()

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

free a tree profile

Parameters
scipSCIP data structure
treeprofilepointer to tree profile data structure

Definition at line 714 of file event_estim.c.

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

Referenced by createTreeProfile().

◆ updateTreeProfile()

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

update tree profile

Parameters
scipSCIP data structure
treeprofiletree profile data structure
nodenode that should be added to the profile

Definition at line 734 of file event_estim.c.

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

Referenced by freeTreeProfile().

◆ predictTotalSizeTreeProfile()

static 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
scipSCIP data structure
treeprofiletree profile data structure
minnodesperdepthminimum number of average nodes per depth to make a prediction

Definition at line 803 of file event_estim.c.

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

Referenced by printReport(), and updateTreeProfile().

◆ subtreeSumGapDelSubtrees()

static void subtreeSumGapDelSubtrees ( SCIP scip,
SUBTREESUMGAP ssg 
)
static

clean subtrees stored as priority queues

Parameters
scipSCIP data structure
ssgsubtree sum gap data structure

Definition at line 875 of file event_estim.c.

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

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

◆ subtreeSumGapReset()

◆ subtreeSumGapCreate()

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

create a subtree sum gap

Parameters
scipSCIP data structure
ssgpointer to store subtree sum gap data structure

Definition at line 939 of file event_estim.c.

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

Referenced by createTreeData(), and subtreeSumGapReset().

◆ subtreeSumGapFree()

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

free a subtree sum gap

Parameters
scipSCIP data structure
ssgpointer to store subtree sum gap data structure

Definition at line 962 of file event_estim.c.

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

Referenced by freeTreeData(), and subtreeSumGapCreate().

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compareNodeInfos  )
static

compare two node infos by comparing their lower bound

Definition at line 985 of file event_estim.c.

Referenced by subtreeSumGapFree().

◆ SCIP_DECL_PQUEUEELEMCHGPOS()

static SCIP_DECL_PQUEUEELEMCHGPOS ( elemChgPosNodeInfo  )
static

position change callback of element in priority queue

Definition at line 1000 of file event_estim.c.

◆ subtreeSumGapStoreNode()

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

◆ subtreeSumGapSplit()

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

split the open nodes of the current tree

Parameters
scipSCIP data structure
ssgsubtree sum gap data structure
addfocusnodeshould the focus node be a subtree, too?

Definition at line 1059 of file event_estim.c.

References calcGap(), DoubleExpSmooth::n, nnodes, SubtreeSumGap::nodes2info, SubtreeSumGap::nsubtrees, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocClearBlockMemoryArray, SCIPdebugMsg, SCIPgetFocusNode(), SCIPgetOpenNodesData(), SCIPhashmapRemoveAll(), SubtreeSumGap::subtreepqueues, subtreeSumGapDelSubtrees(), and subtreeSumGapStoreNode().

Referenced by subtreeSumGapStoreNode(), and subtreeSumGapUpdate().

◆ calcGap()

static SCIP_Real calcGap ( SCIP scip,
SCIP_Real  lowerbound 
)
static

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

Parameters
scipSCIP data structure
lowerboundlower bound value

Definition at line 1127 of file event_estim.c.

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

Referenced by subtreeSumGapComputeFromScratchEfficiently(), subtreeSumGapInsertChildren(), subtreeSumGapRemoveNode(), and subtreeSumGapSplit().

◆ subtreeSumGapRemoveNode()

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

◆ subtreeSumGapInsertChildren()

◆ subtreeSumGapComputeFromScratchEfficiently()

static 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
scipSCIP data structure
ssgsubtree sum gap data structure
updatescalingshould the scaling factor be updated?

Definition at line 1396 of file event_estim.c.

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

Referenced by subtreeSumGapInsertChildren(), and subtreeSumGapUpdate().

◆ subtreeSumGapUpdate()

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

◆ resetTreeData()

static SCIP_RETCODE resetTreeData ( SCIP scip,
TREEDATA treedata 
)
static

reset tree data

Parameters
scipSCIP data structure
treedatatree data

Definition at line 1535 of file event_estim.c.

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

Referenced by createTreeData(), and subtreeSumGapUpdate().

◆ createTreeData()

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

create tree data structure

Parameters
scipSCIP data structure
treedatapointer to store tree data

Definition at line 1555 of file event_estim.c.

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

Referenced by resetTreeData().

◆ freeTreeData()

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

free tree data structure

Parameters
scipSCIP data structure
treedatapointer to tree data

Definition at line 1574 of file event_estim.c.

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

Referenced by createTreeData().

◆ updateTreeData()

static 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
scipSCIP data structure
treedatatree data
nodethe corresponding node
nchildrenthe number of children

Definition at line 1592 of file event_estim.c.

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

Referenced by freeTreeData().

◆ treeDataGetWbe()

static SCIP_Real treeDataGetWbe ( TREEDATA treedata)
static

get weighted backtrack estimation from this tree data

Parameters
treedatatree data

Definition at line 1628 of file event_estim.c.

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

◆ doubleExpSmoothReset()

static void doubleExpSmoothReset ( DOUBLEEXPSMOOTH des,
SCIP_Real  initialvalue 
)
static

reset double exponential smoothing

Parameters
desdouble exponential smoothing data structure
initialvaluethe initial value

Definition at line 1667 of file event_estim.c.

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

◆ doubleExpSmoothInit()

static void doubleExpSmoothInit ( DOUBLEEXPSMOOTH des,
SCIP_Real  x1 
)
static

initialize a double exponential smoothing data structure

Parameters
desdouble exponential smoothing data structure
x1the first sample value

Definition at line 1680 of file event_estim.c.

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

Referenced by doubleExpSmoothReset(), and doubleExpSmoothUpdate().

◆ doubleExpSmoothUpdate()

static void doubleExpSmoothUpdate ( DOUBLEEXPSMOOTH des,
SCIP_Real  xnew 
)
static

update a double exponential smoothing data structure

Parameters
desdouble exponential smoothing data structure
xnewnew sample value

Definition at line 1698 of file event_estim.c.

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

Referenced by doubleExpSmoothInit(), and timeSeriesUpdate().

◆ doubleExpSmoothGetTrend()

static SCIP_Real doubleExpSmoothGetTrend ( DOUBLEEXPSMOOTH des)
static

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

Parameters
desdouble exponential smoothing data structure

Definition at line 1720 of file event_estim.c.

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

◆ timeSeriesReset()

static void timeSeriesReset ( TIMESERIES timeseries)
static

reset time series

Parameters
timeseriespointer to store time series

Definition at line 1734 of file event_estim.c.

Referenced by resetTimeSeries(), and timeSeriesCreate().

◆ timeSeriesCreate()

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

create a time series object

Parameters
scipSCIP data structure
timeseriespointer to store time series
namename of this time series
targetvaluetarget value of this time series
initialvaluethe initial value of time series
alphaalpha parameter (level weight) for double exponential smoothing
betabeta parameter (level weight) for double exponential smoothing

Definition at line 1749 of file event_estim.c.

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

Referenced by includeTimeseries().

◆ timeSeriesFree()

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

free a time series

Parameters
scipSCIP data structure
timeseriespointer to time series

Definition at line 1798 of file event_estim.c.

References BMSfreeMemoryArray, NULL, SCIP_Real, SCIPfreeMemory, SCIPfreeMemoryArray, and timeSeriesGetValue().

Referenced by freeTimeSeries(), and timeSeriesCreate().

◆ timeSeriesGetValue()

static SCIP_Real timeSeriesGetValue ( TIMESERIES timeseries)
static

get current value of time series

Parameters
timeseriestime series

Definition at line 1818 of file event_estim.c.

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

◆ timeSeriesGetTargetValue()

static SCIP_Real timeSeriesGetTargetValue ( TIMESERIES timeseries)
static

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

Parameters
timeseriestime series

Definition at line 1829 of file event_estim.c.

Referenced by timeSeriesEstimate().

◆ timeSeriesGetResolution()

static int timeSeriesGetResolution ( TIMESERIES timeseries)
static

get resolution of time series

Parameters
timeseriestime series

Definition at line 1838 of file event_estim.c.

Referenced by printReport(), and timeSeriesEstimate().

◆ timeSeriesEstimate()

static SCIP_Real timeSeriesEstimate ( TIMESERIES timeseries,
TREEDATA treedata 
)
static

estimate tree size at which time series reaches target value

Parameters
timeseriestime series
treedatatree data for fallback estimation

Definition at line 1847 of file event_estim.c.

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

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

◆ timeSeriesUpdateSmoothEstimation()

static void timeSeriesUpdateSmoothEstimation ( TIMESERIES timeseries,
SCIP_Real  estimation 
)
static

update time series smoothened estimation

Parameters
timeseriestime series
estimationestimation value

Definition at line 1886 of file event_estim.c.

References SCIP_INVALID, SCIP_Real, SESCOEFF, TimeSeries::smoothestimation, and timeSeriesGetSmoothEstimation().

Referenced by timeSeriesEstimate(), and timeSeriesUpdate().

◆ timeSeriesGetSmoothEstimation()

static SCIP_Real timeSeriesGetSmoothEstimation ( TIMESERIES timeseries)
static

get smooth estimation of time series

Parameters
timeseriestime series

Definition at line 1902 of file event_estim.c.

Referenced by printReport(), and timeSeriesUpdateSmoothEstimation().

◆ timeSeriesResample()

static void timeSeriesResample ( TIMESERIES timeseries)
static

resample to lower resolution

Parameters
timeseriestime series

Definition at line 1911 of file event_estim.c.

Referenced by timeSeriesUpdate().

◆ timeSeriesUpdate()

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

◆ timeSeriesGetName()

static char* timeSeriesGetName ( TIMESERIES timeseries)
static

get name of time series

Parameters
timeseriestime series

Definition at line 1987 of file event_estim.c.

Referenced by printReport(), timeSeriesUpdate(), and updateTimeseries().

◆ resetTimeSeries()

static void resetTimeSeries ( SCIP_EVENTHDLRDATA eventhdlrdata)
static

reset all time series

Parameters
eventhdlrdataevent handler data

Definition at line 1996 of file event_estim.c.

References freeTimeSeries(), NULL, timeSeriesReset(), and TimeSeries::useleafts.

◆ freeTimeSeries()

static void freeTimeSeries ( SCIP scip,
SCIP_EVENTHDLRDATA eventhdlrdata 
)
static

free all time series

Parameters
scipSCIP data structure
eventhdlrdataevent handler data

Definition at line 2019 of file event_estim.c.

References getEnsembleEstimation(), NTIMESERIES, NULL, SCIP_Real, and timeSeriesFree().

Referenced by resetTimeSeries().

◆ getEnsembleEstimation()

static 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
eventhdlrdataevent handler data

Definition at line 2041 of file event_estim.c.

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

Referenced by freeTimeSeries().

◆ getSearchCompletion()

◆ getEstimCompletion()

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

tree size estimation based on search tree completion

Parameters
scipSCIP data structure
eventhdlrdataevent handler data
estimpointer to store the estimation value

Definition at line 2222 of file event_estim.c.

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

Referenced by getSearchCompletion().

◆ DECL_TIMESERIESUPDATE() [1/5]

static DECL_TIMESERIESUPDATE ( timeseriesUpdateGap  )
static

update callback at nodes

Definition at line 2244 of file event_estim.c.

◆ DECL_TIMESERIESUPDATE() [2/5]

static DECL_TIMESERIESUPDATE ( timeseriesUpdateTreeWeight  )
static

update callback at nodes

Definition at line 2285 of file event_estim.c.

◆ DECL_TIMESERIESUPDATE() [3/5]

static DECL_TIMESERIESUPDATE ( timeseriesUpdateLeafFreq  )
static

update callback at nodes

Definition at line 2294 of file event_estim.c.

◆ DECL_TIMESERIESUPDATE() [4/5]

static DECL_TIMESERIESUPDATE ( timeseriesUpdateSsg  )
static

update callback at nodes

Definition at line 2306 of file event_estim.c.

References TreeData::nvisited.

◆ DECL_TIMESERIESUPDATE() [5/5]

static DECL_TIMESERIESUPDATE ( timeseriesUpdateOpenNodes  )
static

update callback at nodes

Definition at line 2318 of file event_estim.c.

◆ includeTimeseries()

static SCIP_RETCODE includeTimeseries ( SCIP scip,
SCIP_EVENTHDLRDATA eventhdlrdata 
)
static

include time series to forecast into event handler

Parameters
scipSCIP data structure
eventhdlrdataevent handler data

Definition at line 2330 of file event_estim.c.

References 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, getRestartPolicy(), NULL, SCIP_CALL, SCIP_OKAY, timeSeriesCreate(), TSPOS_GAP, TSPOS_LFREQ, TSPOS_OPEN, TSPOS_SSG, and TSPOS_TREEWEIGHT.

◆ getRestartPolicy()

static RESTARTPOLICY getRestartPolicy ( SCIP_EVENTHDLRDATA eventhdlrdata)
static

◆ isRestartApplicable()

static SCIP_Bool isRestartApplicable ( SCIP scip,
SCIP_EVENTHDLRDATA eventhdlrdata 
)
static

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

Parameters
scipSCIP data structure
eventhdlrdataevent handler data

Definition at line 2387 of file event_estim.c.

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

Referenced by getRestartPolicy().

◆ shouldApplyRestartCompletion()

static SCIP_Bool shouldApplyRestartCompletion ( SCIP scip,
SCIP_EVENTHDLRDATA eventhdlrdata 
)
static

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

Parameters
scipSCIP data structure
eventhdlrdataevent handler data

Definition at line 2420 of file event_estim.c.

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

Referenced by isRestartApplicable(), and shouldApplyRestart().

◆ shouldApplyRestartEstimation()

static SCIP_Bool shouldApplyRestartEstimation ( SCIP scip,
SCIP_EVENTHDLRDATA eventhdlrdata 
)
static

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

Parameters
scipSCIP data structure
eventhdlrdataevent handler data

Definition at line 2446 of file event_estim.c.

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

Referenced by shouldApplyRestart(), and shouldApplyRestartCompletion().

◆ shouldApplyRestart()

static SCIP_Bool shouldApplyRestart ( SCIP scip,
SCIP_EVENTHDLRDATA eventhdlrdata 
)
static

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

Parameters
scipSCIP data structure
eventhdlrdataevent handler data

Definition at line 2483 of file event_estim.c.

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

Referenced by shouldApplyRestartEstimation().

◆ updateTimeseries()

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

update all time series

Parameters
scipSCIP data structure
eventhdlrdataevent handler data
treedatatree data
isleafare we at a leaf node?

Definition at line 2513 of file event_estim.c.

References NTIMESERIES, NULL, printReport(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, timeSeriesGetName(), timeSeriesGetValue(), and timeSeriesUpdate().

Referenced by shouldApplyRestart().

◆ printReport()

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

◆ SCIP_DECL_EVENTCOPY()

static SCIP_DECL_EVENTCOPY ( eventCopyEstim  )
static

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

Definition at line 2629 of file event_estim.c.

Referenced by printReport().

◆ SCIP_DECL_EVENTFREE()

static SCIP_DECL_EVENTFREE ( eventFreeEstim  )
static

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

Definition at line 2640 of file event_estim.c.

◆ SCIP_DECL_EVENTINIT()

static SCIP_DECL_EVENTINIT ( eventInitEstim  )
static

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

Definition at line 2658 of file event_estim.c.

◆ SCIP_DECL_EVENTEXIT()

static SCIP_DECL_EVENTEXIT ( eventExitEstim  )
static

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

Definition at line 2679 of file event_estim.c.

◆ SCIP_DECL_EVENTINITSOL()

static 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 2693 of file event_estim.c.

◆ SCIP_DECL_EVENTEXITSOL()

static SCIP_DECL_EVENTEXITSOL ( eventExitsolEstim  )
static

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

Definition at line 2723 of file event_estim.c.

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecEstim  )
static

execution method of event handler

Definition at line 2740 of file event_estim.c.

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputEstim  )
static

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

Definition at line 2843 of file event_estim.c.

◆ SCIP_DECL_DISPOUTPUT()

static SCIP_DECL_DISPOUTPUT ( dispOutputCompleted  )
static

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

Definition at line 2863 of file event_estim.c.

◆ SCIPincludeEventHdlrEstim()

SCIP_RETCODE SCIPincludeEventHdlrEstim ( SCIP scip)

creates event handler for tree size estimation

Parameters
scipSCIP data structure

Definition at line 2893 of file event_estim.c.

Referenced by SCIPincludeDefaultPlugins().

◆ SCIPgetTreesizeEstimation()

SCIP_Real SCIPgetTreesizeEstimation ( SCIP scip)

return an estimation of the final tree size

Parameters
scipSCIP data structure

Definition at line 3021 of file event_estim.c.

Referenced by printReport(), and shouldApplyRestartEstimation().