/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
	/*                                                                           */
	/*                  This file is part of the program and library             */
	/*         SCIP --- Solving Constraint Integer Programs                      */
	/*                                                                           */
	/*    Copyright (C) 2002-2022 Konrad-Zuse-Zentrum                            */
	/*                            fuer Informationstechnik Berlin                */
	/*                                                                           */
	/*  SCIP is distributed under the terms of the ZIB Academic License.         */
	/*                                                                           */
	/*  You should have received a copy of the ZIB Academic License              */
	/*  along with SCIP; see the file COPYING. If not visit scipopt.org.         */
	/*                                                                           */
	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
	
	/**@file   event_estim.c
	 * @brief  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
	 */
	
	/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
	
	#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"
	
	#define EVENTHDLR_NAME         "estim"
	#define EVENTHDLR_DESC         "event handler for tree size estimation and restarts"
	#define EVENTTYPE_ESTIM      (SCIP_EVENTTYPE_NODEDELETE | SCIP_EVENTTYPE_NODEBRANCHED)
	
	/*
	 * Data structures
	 */
	
	/** enumerator for available restart policies */
	enum RestartPolicy
	{
	   RESTARTPOLICY_NEVER      = 0,             /**< never restart (disable this event handler) */
	   RESTARTPOLICY_ALWAYS     = 1,             /**< always restart (can be fine tuned by using minimum number of nodes and restart limit) */
	   RESTARTPOLICY_ESTIMATION = 2,             /**< base restart on the estimation method */
	   RESTARTPOLICY_COMPLETION = 3              /**< trigger restart based on search completion approximation */
	};
	
	typedef enum RestartPolicy RESTARTPOLICY;
	
	#define RESTARTPOLICY_CHAR_NEVER        'n'
	#define RESTARTPOLICY_CHAR_ALWAYS       'a'
	#define RESTARTPOLICY_CHAR_COMPLETION   'c'
	#define RESTARTPOLICY_CHAR_ESTIMATION   'e'
	
	#define DES_USETRENDINLEVEL              TRUE /**< Should the trend be used in the level update? */
	
	/* constants for the table estimation */
	#define TABLE_NAME              "estim"
	#define TABLE_DESC              "tree size estimations statistics table"
	#define TABLE_POSITION          18500           /**< the position of the statistics table */
	#define TABLE_EARLIEST_STAGE    SCIP_STAGE_INIT /**< output of the statistics table is only printed from this stage onwards */
	
	/* constants for the search completion display column */
	#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       /**< the width of the display column */
	#define DISP_PRIORITY           110000  /**< the priority of the display column */
	#define DISP_POSITION           30100   /**< the relative position of the display column */
	#define DISP_STRIPLINE          TRUE    /**< the default for whether the display column should be separated
	                                         *   with a line from its right neighbor */
	#define INITIALSIZE             100
	#define SESCOEFF                0.75    /**< coefficient of single exponential smoothing of estimation */
	
	/* double exponential smoothing parameters for different time series */
	#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               /**< size limit (number of nodes) for regression forest */
	
	
	
	/* computation of search completion */
	#define COMPLETIONTYPE_AUTO      'a'             /**< automatic (regression forest if available, else monotone regression on binary and SSG on nonbinary trees) */
	#define COMPLETIONTYPE_REGFOREST 'r'             /**< regression forest (must be provided by user) */
	#define COMPLETIONTYPE_MONOREG   'm'             /**< monotone regression (using tree weight and SSG) */
	#define COMPLETIONTYPE_TREEWEIGHT 'w'            /**< use tree weight value as approximation of search tree completion */
	#define COMPLETIONTYPE_SSG       's'             /**< use SSG value as approximation of search tree completion */
	#define COMPLETIONTYPE_GAP       'g'             /**< use gap value as approximation of search tree completion */
	
	
	/* tree size estimation method */
	#define ESTIMMETHOD_COMPL        'c'             /**< estimation based on projection of current search completion */
	#define ESTIMMETHOD_WBE          'b'             /**< weighted backtrack estimation */
	#define ESTIMMETHOD_ENSMBL       'e'             /**< estimation based on an ensemble of the individual estimations */
	#define ESTIMMETHOD_GAP          'g'             /**< estimation based on double exponential smoothing for open nodes */
	#define ESTIMMETHOD_LFREQ        'l'             /**< estimation based on double exponential smoothing for leaf frequency */
	#define ESTIMMETHOD_OPEN         'o'             /**< estimation based on double exponential smoothing for open nodes */
	#define ESTIMMETHOD_SSG          's'             /**< estimation based on double exponential smoothing for sum of subtree gaps */
	#define ESTIMMETHOD_TPROF        't'             /**< estimation based on tree profile method */
	#define ESTIMMETHOD_TREEWEIGHT   'w'             /**< estimation based on double exponential smoothing for tree weight */
	
	#define ESTIMMETHODS "bceglostw"
	
	/* constants and default values for treeprofile parameters */
	#define TREEPROFILE_MINSIZE    512                /**< minimum size (depth) that tree profile can hold */
	#define SSG_STARTPRIMBOUND  SCIP_INVALID          /**< initial value of primal bound used within SSG */
	
	/** double exponential smoothing data structure */
	struct DoubleExpSmooth
	{
	   SCIP_Real             alpha;              /**< level smoothing constant */
	   SCIP_Real             beta;               /**< trend smoothing constant */
	   SCIP_Real             level;              /**< estimation of the current level used for smoothing */
	   SCIP_Real             trend;              /**< estimation of the current trend (slope) */
	   SCIP_Real             initialvalue;       /**< the level value at 0 observations */
	   SCIP_Bool             usetrendinlevel;    /**< Should the trend be used in the level update? */
	   int                   n;                  /**< number of observations */
	};
	typedef struct DoubleExpSmooth DOUBLEEXPSMOOTH;
	
	/** 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.
	 */
	typedef struct TimeSeries TIMESERIES;
	
	/** data structure for convenient access of tree information */
	typedef struct TreeData TREEDATA;
	
	
	#define NTIMESERIES 5
	
	/** time series position in event handler time series array */
	enum TsPos
	{
	   TSPOS_NONE         = -1,                  /**< invalid array position */
	   TSPOS_GAP          =  0,                  /**< time series position of gap */
	   TSPOS_TREEWEIGHT   =  1,                  /**< time series position of tree weight */
	   TSPOS_LFREQ        =  2,                  /**< time series position of leaf frequency */
	   TSPOS_SSG          =  3,                  /**< time series position of SSG */
	   TSPOS_OPEN         =  4                   /**< time series position of open nodes */
	};
	
	typedef enum TsPos TSPOS;
	
	/** regression forest data structure */
	typedef struct SCIP_RegForest SCIP_REGFOREST;
	
	/** statistics collected from profile used for prediction */
	struct TreeProfileStats
	{
	   int                   maxdepth;           /**< maximum node depth encountered */
	   int                   lastfulldepth;      /**< deepest layer for which all nodes have been explored */
	   int                   minwaistdepth;      /**< minimum depth of the waist, i.e. the widest part of the tree */
	   int                   maxwaistdepth;      /**< maximum depth of the waist, i.e. the widest part of the tree */
	};
	
	typedef struct TreeProfileStats TREEPROFILESTATS;
	
	
	/** profile data structure for tree */
	struct TreeProfile
	{
	   SCIP_Longint*         profile;            /**< array to store the tree profile */
	   int                   profilesize;        /**< size of the profile array */
	   TREEPROFILESTATS      stats;              /**< statistics collected from profile used for prediction */
	   SCIP_Real             lastestimate;       /**< the last estimate predicted by predictTotalSizeTreeprofile() */
	   TREEPROFILESTATS      lastestimatestats;  /**< tree profile statistics at last estimation */
	};
	
	typedef struct TreeProfile TREEPROFILE;
	
	/* default values of user parameters */
	#define DEFAULT_USELEAFTS            TRUE    /**< Use leaf nodes as basic observations for time series, or all nodes? */
	#define DEFAULT_REPORTFREQ           -1      /**< report frequency on estimation: -1: never, 0: always, k >= 1: k times evenly during search */
	#define DEFAULT_REGFORESTFILENAME    "-"     /**< default file name of user regression forest in RFCSV format */
	#define DEFAULT_COEFMONOWEIGHT       0.3667  /**< coefficient of tree weight in monotone approximation of search completion */
	#define DEFAULT_COEFMONOSSG          0.6333  /**< coefficient of 1 - SSG in monotone approximation of search completion */
	#define DEFAULT_COMPLETIONTYPE       COMPLETIONTYPE_AUTO /**< default computation of search tree completion */
	#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 */
	#define DEFAULT_TREEPROFILE_ENABLED  FALSE   /**< Should the event handler collect data? */
	#define DEFAULT_TREEPROFILE_MINNODESPERDEPTH 20.0 /**< minimum average number of nodes at each depth before producing estimations */
	#define DEFAULT_RESTARTPOLICY        'e'     /**< default restart policy: (a)lways, (c)ompletion, (e)stimation, (n)ever */
	#define DEFAULT_RESTARTLIMIT          1      /**< default restart limit */
	#define DEFAULT_MINNODES             1000L   /**< minimum number of nodes before restart */
	#define DEFAULT_COUNTONLYLEAVES      FALSE   /**< should only leaves count for the minnodes parameter? */
	#define DEFAULT_RESTARTFACTOR        50.0    /**< factor by which the estimated number of nodes should exceed the current number of nodes */
	#define DEFAULT_RESTARTNONLINEAR     FALSE   /**< whether to apply a restart when nonlinear constraints are present */
	#define DEFAULT_RESTARTACTPRICERS    FALSE   /**< whether to apply a restart when active pricers are used */
	#define DEFAULT_HITCOUNTERLIM        50      /**< limit on the number of successive samples to really trigger a restart */
	#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 */
	#define DEFAULT_SSG_NMINNODESLASTSPLIT   0L  /**< minimum number of nodes to process between two consecutive SSG splits */
	
	/** event handler data */
	struct SCIP_EventhdlrData
	{
	   SCIP_REGFOREST*       regforest;          /**< regression forest data structure */
	   TIMESERIES*           timeseries[NTIMESERIES]; /**< array of time series slots */
	   TREEDATA*             treedata;           /**< tree data */
	   TREEPROFILE*          treeprofile;        /**< tree profile data structure */
	   char*                 regforestfilename;  /**< file name of user regression forest in RFCSV format */
	   SCIP_Real             restartfactor;      /**< factor by which the estimated number of nodes should exceed the current number of nodes */
	   SCIP_Real             weightlastreport;   /**< tree weight at which last report was printed */
	   SCIP_Real             treeprofile_minnodesperdepth;/**< minimum average number of nodes at each depth before producing estimations */
	   SCIP_Real             coefmonoweight;     /**< coefficient of tree weight in monotone approximation of search completion */
	   SCIP_Real             coefmonossg;        /**< coefficient of 1 - SSG in monotone approximation of search completion */
	   SCIP_Longint          minnodes;           /**< minimum number of nodes in a run before restart is triggered */
	   int                   restartlimit;       /**< How often should a restart be triggered? (-1 for no limit) */
	   int                   nrestartsperformed; /**< number of restarts performed so far */
	   int                   restarthitcounter;  /**< the number of successive samples that would trigger a restart */
	   int                   hitcounterlim;      /**< limit on the number of successive samples to really trigger a restart */
	   int                   nreports;           /**< the number of reports already printed */
	   int                   reportfreq;         /**< report frequency on estimation: -1: never, 0:always, k >= 1: k times evenly during search */
	   int                   lastrestartrun;     /**< the last run at which this event handler triggered restart */
	   char                  restartpolicyparam; /**< restart policy parameter */
	   char                  estimmethod;        /**< 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 */
	   char                  completiontypeparam;/**< approximation of search tree completion:
	                                              *   (a)uto, (g)ap, tree (w)eight, (m)onotone regression, (r)egression forest, (s)sg */
	   SCIP_Bool             countonlyleaves;    /**< Should only leaves count for the minnodes parameter? */
	   SCIP_Bool             useleafts;          /**< Use leaf nodes as basic observations for time series, or all nodes? */
	   SCIP_Bool             treeprofile_enabled;/**< Should the event handler collect treeprofile data? */
	   SCIP_Bool             treeisbinary;       /**< internal flag if all branching decisions produced 2 children */
	   SCIP_Bool             restartnonlinear;   /**< whether to apply a restart when nonlinear constraints are present */
	   SCIP_Bool             restartactpricers;  /**< whether to apply a restart when active pricers are used */
	};
	
	typedef struct SubtreeSumGap SUBTREESUMGAP;
	
	struct TreeData
	{
	   SCIP_Longint          nnodes;             /**< the total number of nodes */
	   SCIP_Longint          nopen;              /**< the current number of open nodes */
	   SCIP_Longint          ninner;             /**< the number of inner nodes */
	   SCIP_Longint          nleaves;            /**< the number of final leaf nodes */
	   SCIP_Longint          nvisited;           /**< the number of visited nodes */
	   long double           weight;             /**< the current tree weight (sum of leaf weights) */
	   SUBTREESUMGAP*        ssg;                /**< subtree sum gap data structure */
	};
	
	struct SubtreeSumGap
	{
	   SCIP_Real             value;              /**< the current subtree sum gap */
	   SCIP_HASHMAP*         nodes2info;         /**< map between nodes and their subtree indices */
	   SCIP_PQUEUE**         subtreepqueues;     /**< array of priority queues, one for each subtree */
	   SCIP_Real             scalingfactor;      /**< the current scaling factor */
	   SCIP_Real             pblastsplit;        /**< primal bound when last split occurred */
	   SCIP_Longint          nodelastsplit;      /**< last node at which a subtree split occurred */
	   SCIP_Longint          nminnodeslastsplit; /**< minimum number of nodes to process between two consecutive SSG splits */
	   int                   nmaxsubtrees;       /**< the maximum number of individual SSG subtrees; the old split is kept if
	                                               *  a new split exceeds this number of subtrees ; -1: no limit */
	   int                   nsubtrees;          /**< the current number n of subtrees labeled 0 .. n - 1 */
	};
	
	/** update callback of time series */
	#define DECL_TIMESERIESUPDATE(x) SCIP_RETCODE x (\
	   SCIP*                 scip,                   \
	   TIMESERIES*           ts,                     \
	   TREEDATA*             treedata,               \
	   SCIP_Real*            value                   \
	   )
	
	/** time series data structure for leaf time series */
	struct TimeSeries
	{
	   DOUBLEEXPSMOOTH       des;                /**< double exponential smoothing data structure */
	   char*                 name;               /**< name of this time series */
	   SCIP_Real*            vals;               /**< value array of this time series */
	   SCIP_Real*            estimation;         /**< array of estimations of this time series */
	   SCIP_Real             smoothestimation;   /**< smoothened estimation value */
	   SCIP_Real             targetvalue;        /**< target value of this time series */
	   SCIP_Real             currentvalue;       /**< current value of time series */
	   SCIP_Real             initialvalue;       /**< the initial value of time series */
	   SCIP_Longint          nobs;               /**< total number of observations */
	   int                   valssize;           /**< size of value array */
	   int                   nvals;              /**< number of values */
	   int                   resolution;         /**< current (inverse of) resolution */
	   SCIP_Bool             useleafts;          /**< Should this time series be recorded at leaf nodes, or at every node? */
	   DECL_TIMESERIESUPDATE((*timeseriesupdate));/**< update callback at nodes */
	};
	
	/** extended node information for SSG priority queue */
	struct NodeInfo
	{
	   SCIP_NODE*            node;               /**< search tree node */
	   SCIP_Real             lowerbound;         /**< lower bound of the node at insertion into priority queue */
	   int                   pos;                /**< position of this node in priority queue */
	   int                   subtreeidx;         /**< subtree index of this node */
	};
	typedef struct NodeInfo NODEINFO;
	
	struct SCIP_RegForest
	{
	   int                   ntrees;             /**< number of trees in this forest */
	   int                   dim;                /**< feature dimension */
	   int*                  nbegin;             /**< array of root node indices of each tree */
	   int*                  child;              /**< child index pair of each internal node, or (-1, -1) for leaves */
	   int*                  splitidx;           /**< data index for split at node, or -1 at a leaf */
	   SCIP_Real*            value;              /**< split position at internal nodes, prediction at leaves */
	   int                   size;               /**< length of node arrays */
	};
	
	/*
	 * Local methods
	 */
	
	/** convert number to string and treat SCIP_INVALID as '-' */
	static
	char* real2String(
	   SCIP_Real             num,                /**< number to convert to string */
	   char*                 buf,                /**< string buffer */
	   int                   digits              /**< number of decimal digits */
	   )
	{
	   if( num == SCIP_INVALID )/*lint !e777*/
	      (void) SCIPsnprintf(buf, 1, "-");
	   else if( num >= 1e+20 ) /*lint !e777*/
	      (void) SCIPsnprintf(buf, 3, "inf");
	   else
	      (void) SCIPsnprintf(buf, SCIP_MAXSTRLEN, "%10.*f", digits, num);
	
	   return buf;
	}
	
	/** free a regression forest data structure */
	static
	void SCIPregForestFree(
	   SCIP_REGFOREST**      regforest           /**< regression forest data structure */
	   )
	{
	   SCIP_REGFOREST* regforestptr;
	
	   assert(regforest != NULL);
	
	   if( *regforest == NULL )
	      return;
	   regforestptr = *regforest;
	
	   BMSfreeMemoryArrayNull(&regforestptr->nbegin);
	   BMSfreeMemoryArrayNull(&regforestptr->child);
	   BMSfreeMemoryArrayNull(&regforestptr->splitidx);
	   BMSfreeMemoryArrayNull(&regforestptr->value);
	
	   BMSfreeMemory(regforest);
	}
	
	/** make a prediction with regression forest */
	static
	SCIP_Real SCIPregForestPredict(
	   SCIP_REGFOREST*       regforest,          /**< regression forest data structure */
	   SCIP_Real*            datapoint           /**< a data point that matches the dimension of this regression forest */
	   )
	{
	   int treeidx;
	   SCIP_Real value = 0.0;
	
	   assert(regforest != NULL);
	   assert(datapoint != NULL);
	
	   SCIPdebugMessage("Start prediction method of regression forest\n");
	
	   /* loop through the trees */
	   for( treeidx = 0; treeidx < regforest->ntrees; ++treeidx )
	   {
	      int treepos = regforest->nbegin[treeidx];
	      int* childtree = &(regforest->child[2 * treepos]);
	      int* splitidxtree = &(regforest->splitidx[treepos]);
	      int pos = 0;
	      SCIP_Real* valuetree = &(regforest->value[treepos]);
	
	      SCIPdebugMessage("Tree %d at position %d\n", treeidx, treepos);
	
	      /* find the correct leaf */
	      while( splitidxtree[pos] != - 1 )
	      {
	         int goright;
	
	         assert(splitidxtree[pos] < regforest->dim);
	
	         goright = (datapoint[splitidxtree[pos]] > valuetree[pos]) ? 1 : 0;
	         pos = childtree[2 * pos + goright];
	      }
	
	      value += valuetree[pos];
	   }
	
	   /* return the average value that the trees predict */
	   return value / (SCIP_Real)(regforest->ntrees);
	}
	
	/** 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
	 */
	static
	SCIP_RETCODE SCIPregForestFromFile(
	   SCIP_REGFOREST**      regforest,          /**< regression forest data structure */
	   const char*           filename            /**< name of file with the regression forest data */
	   )
	{
	   SCIP_RETCODE retcode = SCIP_OKAY;
	   SCIP_FILE* file;
	   SCIP_REGFOREST* regforestptr;
	   char buffer[SCIP_MAXSTRLEN];
	   char firstlineformat[SCIP_MAXSTRLEN];
	   char dataformat[SCIP_MAXSTRLEN];
	   char valuestr[SCIP_MAXSTRLEN];
	   SCIP_Bool error = FALSE;
	   int ntrees;
	   int dim;
	   int size;
	   int sscanret;
	   int pos;
	   int treepos;
	
	   /* try to open file */
	   file = SCIPfopen(filename, "r");
	
	   if( file == NULL )
	      return SCIP_NOFILE;
	
	   /* parse read the first line that contains the number of trees, feature dimension, and total number of nodes */
	   (void) SCIPsnprintf(firstlineformat, SCIP_MAXSTRLEN, "### NTREES=%%10d FEATURE_DIM=%%10d LENGTH=%%10d\n");
	   if( SCIPfgets(buffer, (int) sizeof(buffer), file) == NULL )
	   {
	      error = TRUE;
	      SCIPerrorMessage("Could not read first line of regression file '%s'\n", filename);
	      goto CLOSEFILE;
	   }
	
	   /* coverity[secure_coding] */
	   sscanret = sscanf(buffer, firstlineformat, &ntrees, &dim, &size);
	
	   if( sscanret != 3 )
	   {
	      error = TRUE;
	      SCIPerrorMessage("Could not extract tree information from buffer line [%s]\n", buffer);
	      goto CLOSEFILE;
	   }
	
	   SCIPdebugMessage("Read ntrees=%d, dim=%d, size=%d (return value %d)\n", ntrees, dim, size, sscanret);
	
	   /* check if the tree is too big, or numbers are negative */
	   if( size > MAX_REGFORESTSIZE )
	   {
	      error = TRUE;
	      SCIPerrorMessage("Requested size %d exceeds size limit %d for regression trees", size, MAX_REGFORESTSIZE);
	      goto CLOSEFILE;
	   }
	
	   if( dim <= 0 || ntrees <= 0 || size <= 0 )
	   {
	      error = TRUE;
	      SCIPerrorMessage("Cannot create regression tree with negative size, dimension, or number of trees\n");
	      goto CLOSEFILE;
	   }
	
	   /* allocate memory in regression forest data structure */
	   SCIP_ALLOC_TERMINATE( retcode, BMSallocMemory(regforest), FREEFOREST );
	   BMSclearMemory(*regforest);
	   regforestptr = *regforest;
	
	   SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->nbegin, ntrees), FREEFOREST );
	   SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->child, 2 * size), FREEFOREST ); /*lint !e647*/
	   SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->splitidx, size), FREEFOREST );
	   SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->value, size), FREEFOREST );
	
	   regforestptr->dim = dim;
	   regforestptr->size = size;
	   regforestptr->ntrees = ntrees;
	
	   SCIPdebugMessage("Random Forest allocated\n");
	
	   /* loop through the rest of the file, which contains the comma separated node data */
	   (void) SCIPsnprintf(dataformat, SCIP_MAXSTRLEN, "%%10d,%%10d,%%10d,%%10d,%%%ds\n", SCIP_MAXSTRLEN);
	
	   pos = 0;
	   treepos = 0;
	   while( !SCIPfeof(file) && !error )
	   {
	      int node;
	      char* endptr;
	
	      /* get next line */
	      if( SCIPfgets(buffer, (int) sizeof(buffer), file) == NULL )
	         break;
	
	      sscanret = sscanf(buffer, dataformat,
	         &node,
	         &regforestptr->child[2 * pos],
	         &regforestptr->child[2 * pos + 1],
	         &regforestptr->splitidx[pos],
	         valuestr);
	
	      if( sscanret != 5 )
	      {
	         SCIPerrorMessage("Something wrong with line %d '%s'", pos + 1, buffer);
	         error = TRUE;
	      }
	
	      (void)SCIPstrToRealValue(valuestr, &regforestptr->value[pos], &endptr);
	
	      /* new root node - increase the tree index position */
	      if( node == 0 )
	      {
	         assert(treepos < regforestptr->ntrees);
	
	         regforestptr->nbegin[treepos++] = pos;
	      }
	
	      ++pos;
	   }
	
	   goto CLOSEFILE;
	
	/* insufficient memory for allocating regression forest */
	FREEFOREST:
	   assert(retcode == SCIP_NOMEMORY);
	   SCIPregForestFree(regforest);
	
	CLOSEFILE:
	   SCIPfclose(file);
	
	   if( error )
	      retcode = SCIP_INVALIDDATA;
	
	   return retcode;
	}
	
	/** compare two tree profile statistics for equality */
	static
	SCIP_Bool isEqualTreeProfileStats(
	   TREEPROFILESTATS*     stats,              /**< first tree profile statistics */
	   TREEPROFILESTATS*     other               /**< other tree profile statistics */
	   )
	{
	   assert(stats != NULL);
	   assert(other != NULL);
	
	   return  stats->maxdepth == other->maxdepth &&
	      stats->lastfulldepth == other->lastfulldepth &&
	      stats->minwaistdepth == other->minwaistdepth &&
	      stats->maxwaistdepth == other->maxwaistdepth;
	}
	
	/** copy source tree profile into destination */
	static
	void copyTreeProfileStats(
	   TREEPROFILESTATS*     dest,               /**< destination tree profile statistics */
	   TREEPROFILESTATS*     src                 /**< source tree profile statistics */
	   )
	{
	   assert(dest != NULL);
	   assert(src != NULL);
	
	   dest->maxdepth = src->maxdepth;
	   dest->lastfulldepth = src->lastfulldepth;
	   dest->minwaistdepth = src->minwaistdepth;
	   dest->maxwaistdepth = src->maxwaistdepth;
	}
	
	/** reset tree profile statistics */
	static
	void resetTreeProfileStats(
	   TREEPROFILESTATS*     treeprofilestats    /**< tree profile statistics */
	   )
	{
	   assert(treeprofilestats != NULL);
	
	   BMSclearMemory(treeprofilestats);
	}
	
	
	/** extend tree profile to deeper tree */
	static
	SCIP_RETCODE extendMemoryTreeProfile(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEPROFILE*          treeprofile,        /**< tree profile data structure */
	   int                   mindepth            /**< minimum depth that the tree profile should hold */
	   )
	{
	   if( mindepth < treeprofile->profilesize )
	      return SCIP_OKAY;
	
	   if( treeprofile->profile == NULL )
	   {
	      SCIP_CALL( SCIPallocClearMemoryArray(scip, &treeprofile->profile, mindepth) );
	      treeprofile->profilesize = mindepth;
	   }
	   else
	   {
	      int newsize;
	      int nnewelems;
	      SCIP_Longint* newprofile;
	
	      newsize = SCIPcalcMemGrowSize(scip, mindepth + 1);
	      nnewelems = newsize - treeprofile->profilesize;
	      assert(newsize > treeprofile->profilesize);
	
	      SCIP_CALL( SCIPreallocMemoryArray(scip, &treeprofile->profile, newsize) );
	      newprofile = &treeprofile->profile[treeprofile->profilesize];
	      BMSclearMemoryArray(newprofile, nnewelems);
	      treeprofile->profilesize = newsize;
	   }
	
	   return SCIP_OKAY;
	}
	
	/** create a tree profile */
	static
	SCIP_RETCODE createTreeProfile(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEPROFILE**         treeprofile         /**< pointer to store tree profile data structure */
	   )
	{
	   assert(scip != NULL);
	   assert(treeprofile != NULL);
	
	   SCIP_CALL( SCIPallocMemory(scip, treeprofile) );
	
	   (*treeprofile)->profile = NULL;
	   (*treeprofile)->profilesize = 0;
	   SCIP_CALL( extendMemoryTreeProfile(scip, *treeprofile, TREEPROFILE_MINSIZE) );
	
	   resetTreeProfileStats(&(*treeprofile)->stats);
	   resetTreeProfileStats(&(*treeprofile)->lastestimatestats);
	
	   (*treeprofile)->lastestimate = -1.0;
	
	   return SCIP_OKAY;
	}
	
	/** free a tree profile */
	static
	void freeTreeProfile(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEPROFILE**         treeprofile         /**< pointer to tree profile data structure */
	   )
	{
	   assert(scip != NULL);
	   assert(treeprofile != NULL);
	
	   if( *treeprofile == NULL )
	      return;
	
	   SCIPfreeMemoryArray(scip, &(*treeprofile)->profile);
	
	   SCIPfreeMemory(scip, treeprofile);
	
	   *treeprofile = NULL;
	}
	
	/** update tree profile */
	static
	SCIP_RETCODE updateTreeProfile(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEPROFILE*          treeprofile,        /**< tree profile data structure */
	   SCIP_NODE*            node                /**< node that should be added to the profile */
	   )
	{
	   int nodedepth;
	   SCIP_Longint nodedepthcnt;
	   SCIP_Longint maxnodes;
	
	   assert(scip != NULL);
	   assert(node != NULL);
	

	   if( treeprofile == NULL )

	      return SCIP_OKAY;
	
	   nodedepth = SCIPnodeGetDepth(node);
	   assert(nodedepth >= 0);
	   maxnodes = treeprofile->profile[treeprofile->stats.minwaistdepth];
	   assert(treeprofile->stats.minwaistdepth == treeprofile->stats.maxwaistdepth ||
	      maxnodes == treeprofile->profile[treeprofile->stats.maxwaistdepth]);
	
	   /* ensure that the memory can hold at least this depth */

	   SCIP_CALL( extendMemoryTreeProfile(scip, treeprofile, nodedepth) );
	

	   nodedepthcnt = ++treeprofile->profile[nodedepth];
	
	   /* Is this level fully explored? We assume binary branching. The first condition ensures that the bit shift operation
	    * of the second condition represents a feasible power of unsigned int. The largest power of 2 representable
	    * by unsigned int is 2^{8*sizeof(unsigned int) - 1}. */
	   /* coverity[overflow_before_widen] */

	   if( (unsigned int)nodedepth < 8*sizeof(unsigned int) && nodedepthcnt == (1U << nodedepth) )/*lint !e647*/
	   {
	      SCIPdebugMsg(scip, "Level %d fully explored: %" SCIP_LONGINT_FORMAT " nodes\n", nodedepth, nodedepthcnt);
	
	      treeprofile->stats.lastfulldepth = nodedepth;
	   }
	
	   /* update maximum depth */
	   if( treeprofile->stats.maxdepth < nodedepth )
	   {
	      treeprofile->stats.maxdepth = nodedepth;
	      SCIPdebugMsg(scip, "Maximum depth increased to %d\n", treeprofile->stats.maxdepth);
	   }
	
	   /* minimum and maximum waist now coincide */
	   if( nodedepthcnt > maxnodes )
	   {
	      treeprofile->stats.minwaistdepth = treeprofile->stats.maxwaistdepth = nodedepth;
	      SCIPdebugMsg(scip, "Updating depth of tree waist: %d (%" SCIP_LONGINT_FORMAT " nodes)\n",
	         treeprofile->stats.minwaistdepth, nodedepthcnt);
	   }
	   else if( nodedepthcnt == maxnodes )
	   {
	      /* enlarge the interval in which the waist lies */
	      if( treeprofile->stats.minwaistdepth > nodedepth )
	         treeprofile->stats.minwaistdepth = nodedepth;
	      else if( treeprofile->stats.maxwaistdepth < nodedepth )
	         treeprofile->stats.maxwaistdepth = nodedepth;
	   }
	   assert(treeprofile->stats.minwaistdepth <= treeprofile->stats.maxwaistdepth);
	
	   return SCIP_OKAY;
	}
	
	/** make a prediction of the total tree size based on the current tree profile */
	static
	SCIP_Real predictTotalSizeTreeProfile(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEPROFILE*          treeprofile,        /**< tree profile data structure */
	   SCIP_Real             minnodesperdepth    /**< minimum number of average nodes per depth to make a prediction */
	   )
	{
	   SCIP_Real estimate;
	   SCIP_Real growthfac;
	   int d;
	   int waist;
	
	   /* prediction is disabled */
	   if( treeprofile == NULL )
	      return -1.0;
	
	   /* two few nodes to make a prediction */
	   if( minnodesperdepth * treeprofile->stats.maxdepth > SCIPgetNNodes(scip) )
	      return -1.0;
	
	   /* reuse previous estimation if tree profile hasn't changed */
	   if( isEqualTreeProfileStats(&treeprofile->lastestimatestats, &treeprofile->stats) )
	   {
	      SCIPdebugMsg(scip, "Reusing previous estimation result %g\n", treeprofile->lastestimate);
	
	      return treeprofile->lastestimate;
	   }
	
	   /* compute the (depth of the) waist as convex combination between the minimum and maximum waist depths */
	   waist = (2 * treeprofile->stats.maxwaistdepth + treeprofile->stats.minwaistdepth) / 3;
	
	   growthfac = 2;
	   estimate = 1;
	
	   /* loop over all full levels */
	   for( d = 1; d < treeprofile->stats.lastfulldepth; ++d )
	   {
	      SCIP_Real gamma_d = 2.0;
	
	      estimate += growthfac;
	      growthfac *= gamma_d;
	   }
	
	   /* loop until the waist is reached */
	   for( ; d < waist; ++d )
	   {
	      SCIP_Real gamma_d = 2.0 - (d - treeprofile->stats.lastfulldepth + 1.0)/(waist - treeprofile->stats.lastfulldepth + 1.0);
	
	      assert(1.0 <= gamma_d && gamma_d <= 2.0);
	      estimate += growthfac;
	      growthfac *= gamma_d;
	   }
	
	   /* loop over the remaining levels */
	   for( ; d <= treeprofile->stats.maxdepth; ++d )
	   {
	      SCIP_Real gamma_d = (1.0 - (d - waist + 1.0)/(treeprofile->stats.maxdepth - waist + 1.0));
	      assert(0.0 <= gamma_d && gamma_d <= 1.0);
	
	      estimate += growthfac;
	      growthfac *= gamma_d;
	   }
	
	   /* copy tree profile statistics */
	   copyTreeProfileStats(&treeprofile->lastestimatestats, &treeprofile->stats);
	
	   treeprofile->lastestimate = estimate;
	
	   return estimate;
	}
	
	/** clean subtrees stored as priority queues */
	static
	void subtreeSumGapDelSubtrees(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg                 /**< subtree sum gap data structure */
	   )
	{
	   assert(ssg->nsubtrees <= 1 || ssg->subtreepqueues != NULL);
	
	   /* free all previous priority queues */
	   if( ssg->nsubtrees > 1 )
	   {
	      int s;
	
	      for( s = 0; s < ssg->nsubtrees; ++s )
	      {
	         int i;
	         SCIP_PQUEUE* pqueue = ssg->subtreepqueues[s];
	         NODEINFO** nodeinfos;
	
	         assert(pqueue != NULL);
	         nodeinfos = (NODEINFO**)SCIPpqueueElems(pqueue);
	
	         /* free all remaining elements in reverse order */
	         for( i = SCIPpqueueNElems(pqueue); --i >= 0; )
	         {
	            NODEINFO* nodeinfo = nodeinfos[i];
	            assert(nodeinfo != NULL);
	            SCIPfreeBlockMemory(scip, &nodeinfo);
	         }
	
	         SCIPpqueueFree(&pqueue);
	      }
	
	      SCIPfreeBlockMemoryArray(scip, &ssg->subtreepqueues, ssg->nsubtrees);
	   }
	
	   ssg->subtreepqueues = NULL;
	}
	
	/** reset subtree sum gap */
	static
	SCIP_RETCODE subtreeSumGapReset(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg                 /**< subtree sum gap data structure */
	   )
	{
	   assert(ssg != NULL);
	   assert(ssg->nodes2info != NULL);
	
	   SCIP_CALL( SCIPhashmapRemoveAll(ssg->nodes2info) );
	
	   subtreeSumGapDelSubtrees(scip, ssg);
	
	   ssg->value = 1.0;
	   ssg->scalingfactor = 1.0;
	   ssg->nsubtrees = 1;
	   ssg->subtreepqueues = NULL;
	   ssg->pblastsplit = SSG_STARTPRIMBOUND;
	   ssg->nodelastsplit = -1L;
	
	   return SCIP_OKAY;
	}
	
	/** create a subtree sum gap */
	static
	SCIP_RETCODE subtreeSumGapCreate(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP**       ssg                 /**< pointer to store subtree sum gap data structure */
	   )
	{
	   assert(scip != NULL);
	   assert(ssg != NULL);
	
	   /* allocate storage */
	   SCIP_CALL( SCIPallocMemory(scip, ssg) );
	   SCIP_CALL( SCIPhashmapCreate(&(*ssg)->nodes2info, SCIPblkmem(scip), INITIALSIZE) );
	
	   /* explicitly set this to skip removal of subtrees during reset */
	   (*ssg)->nsubtrees = 0;
	
	   /* reset ssg */
	   SCIP_CALL( subtreeSumGapReset(scip, *ssg) );
	
	   return SCIP_OKAY;
	}
	
	/** free a subtree sum gap */
	static
	void subtreeSumGapFree(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP**       ssg                 /**< pointer to store subtree sum gap data structure */
	   )
	{
	   assert(scip != NULL);
	
	   if( *ssg == NULL )
	      return;
	
	   if( (*ssg)->nodes2info != NULL )
	   {
	      SCIPhashmapFree(&(*ssg)->nodes2info);
	   }
	
	   /* delete all subtree data */
	   subtreeSumGapDelSubtrees(scip, *ssg);
	
	   SCIPfreeMemory(scip, ssg);
	}
	
	/** compare two node infos by comparing their lower bound */
	static
	SCIP_DECL_SORTPTRCOMP(compareNodeInfos)
	{
	   NODEINFO* nodeinfo1 = (NODEINFO*)elem1;
	   NODEINFO* nodeinfo2 = (NODEINFO*)elem2;
	
	   if( nodeinfo1->lowerbound < nodeinfo2->lowerbound )
	      return -1;
	   else if( nodeinfo1->lowerbound > nodeinfo2->lowerbound )
	      return 1;
	
	   return 0;
	}
	
	/** position change callback of element in priority queue */
	static
	SCIP_DECL_PQUEUEELEMCHGPOS(elemChgPosNodeInfo)
	{
	   NODEINFO* nodeinfo = (NODEINFO*)elem;
	
	   assert(oldpos == -1 || oldpos == nodeinfo->pos);
	   nodeinfo->pos = newpos;
	}
	
	/** store node in SSG data structure */
	static
	SCIP_RETCODE subtreeSumGapStoreNode(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg,                /**< subtree sum gap data structure */
	   SCIP_NODE*            node,               /**< node that should be stored */
	   int                   subtreeidx          /**< subtree index of that node */
	   )
	{
	   NODEINFO* nodeinfo;
	
	   assert(scip != NULL);
	   assert(ssg != NULL);
	   assert(node != NULL);
	
	   /* create a new node info */
	   SCIP_CALL( SCIPallocBlockMemory(scip, &nodeinfo) );
	
	   /* store node information in data structure and insert into priority queue */
	   nodeinfo->node = node;
	   nodeinfo->subtreeidx = subtreeidx;
	   nodeinfo->pos = -1;
	   nodeinfo->lowerbound = SCIPnodeGetLowerbound(node);
	
	   SCIPdebugMsg(scip, "Inserting label %d for node number %" SCIP_LONGINT_FORMAT " (%p)\n",
	      subtreeidx, SCIPnodeGetNumber(node), (void*)node);
	
	   assert(!SCIPhashmapExists(ssg->nodes2info, (void*)node));
	   /* store node information in Hash Map */
	   SCIP_CALL( SCIPhashmapInsert(ssg->nodes2info, (void*)node, (void*)nodeinfo) );
	
	   /* create the corresponding priority queue, if it does not exist yet */
	   assert(subtreeidx >= 0);
	   assert(subtreeidx < ssg->nsubtrees);
	
	   if( ssg->subtreepqueues[subtreeidx] == NULL )
	   {
	      SCIP_CALL( SCIPpqueueCreate(&ssg->subtreepqueues[subtreeidx], 5, 1.2, compareNodeInfos, elemChgPosNodeInfo) );
	   }
	
	   /* insert node and ensure that its position is up to date */
	   SCIP_CALL( SCIPpqueueInsert(ssg->subtreepqueues[subtreeidx], (void*)nodeinfo) );
	   assert(0 <= nodeinfo->pos);
	   assert(SCIPpqueueNElems(ssg->subtreepqueues[subtreeidx]) > nodeinfo->pos);
	   assert(SCIPpqueueElems(ssg->subtreepqueues[subtreeidx])[nodeinfo->pos] == (void*)nodeinfo);
	
	   return SCIP_OKAY;
	}
	
	/** split the open nodes of the current tree */
	static
	SCIP_RETCODE subtreeSumGapSplit(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg,                /**< subtree sum gap data structure */
	   SCIP_Bool             addfocusnode        /**< should the focus node be a subtree, too? */
	   )
	{
	   SCIP_NODE** opennodes[3];
	   int nopennodes[3];
	   int label;
	   int t;
	   int nnewsubtrees;
	
	   assert(scip != NULL);
	   assert(ssg != NULL);
	
	   /* query the open nodes of SCIP */
	   SCIP_CALL( SCIPgetOpenNodesData(scip, &opennodes[0], &opennodes[1], &opennodes[2], &nopennodes[0], &nopennodes[1], &nopennodes[2]) );
	
	   nnewsubtrees = nopennodes[0] + nopennodes[1] + nopennodes[2] + (addfocusnode ? 1 : 0);
	
	   /* clear hash map from entries */
	   SCIP_CALL( SCIPhashmapRemoveAll(ssg->nodes2info) );
	
	   /* delete all subtrees */
	   subtreeSumGapDelSubtrees(scip, ssg);
	
	   ssg->nsubtrees = nnewsubtrees;
	   SCIPdebugMsg(scip, "Splitting tree into %d subtrees\n", ssg->nsubtrees);
	
	   /* create priority queue array */
	   if( ssg->nsubtrees > 1 )
	   {
	      SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &ssg->subtreepqueues, ssg->nsubtrees) );
	   }
	   else
	   {
	      ssg->subtreepqueues = NULL;
	
	      return SCIP_OKAY;
	   }
	
	   /* loop over node types (leaves, siblings, children) */
	   label = 0;
	   for( t = 0; t < 3; ++t )
	   {
	      SCIP_NODE** nodes = opennodes[t];
	      int nnodes = nopennodes[t];
	      int n;
	
	      /* label each open node as new, separate subtree */
	      for( n = 0; n < nnodes; ++n )
	      {
	         SCIP_NODE* node = nodes[n];
	         SCIP_CALL( subtreeSumGapStoreNode(scip, ssg, node, label++) );
	      }
	   }
	
	   if( addfocusnode )
	   {
	      assert(SCIPgetFocusNode(scip) != NULL);
	      SCIP_CALL( subtreeSumGapStoreNode(scip, ssg, SCIPgetFocusNode(scip), label) );
	   }
	
	   return SCIP_OKAY;
	}
	
	/** compute a gap between a lower bound and the current upper bound */
	static
	SCIP_Real calcGap(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_Real             lowerbound          /**< lower bound value */
	   )
	{
	   SCIP_Real db;
	   SCIP_Real pb;
	   SCIP_Real abspb;
	   SCIP_Real absdb;
	   SCIP_Real gap;
	
	   if( SCIPisInfinity(scip, lowerbound) || lowerbound >= SCIPgetUpperbound(scip) )
	      return 0.0;
	
	   if( SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
	      return 1.0;
	
	   db = SCIPretransformObj(scip, lowerbound);
	   pb = SCIPgetPrimalbound(scip);
	
	   if( SCIPisEQ(scip, db, pb) )
	      return 0.0;
	
	   abspb = REALABS(pb);
	   absdb = REALABS(db);
	   gap = REALABS(pb - db)/MAX(abspb,absdb);
	   gap = MIN(gap, 1.0);
	
	   return gap;
	}
	
	/** remove node from the subtree sum gap (because it has been solved by branching or is a leaf) */
	static
	SCIP_RETCODE subtreeSumGapRemoveNode(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg,                /**< subtree sum gap data structure */
	   SCIP_NODE*            node                /**< node that should be removed */
	   )
	{
	   NODEINFO* nodeinfo;
	   int subtreeidx;
	   int pos;
	   SCIP_PQUEUE* pqueue;
	
	   if( ssg->nsubtrees <= 1 )
	      return SCIP_OKAY;
	
	   nodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void*)node);
	
	   /* it can happen that the node was not created via branching; search for the most recent ancestor in the queue */
	   if( nodeinfo == NULL )
	   {
	      do
	      {
	         node = SCIPnodeGetParent(node);
	      } while( node != NULL && (nodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void*)node)) == NULL);
	
	      /* no ancestor found */
	      if( nodeinfo == NULL )
	         return SCIP_OKAY;
	   }
	
	   /* get open nodes of this subtree stored as priority queue */
	   subtreeidx = nodeinfo->subtreeidx;
	   pqueue = ssg->subtreepqueues[subtreeidx];
	   assert(pqueue != NULL);
	
	   /* delete the element from the priority queue */
	   pos = nodeinfo->pos;
	   assert(pos >= 0);
	   assert(pos < SCIPpqueueNElems(pqueue));
	   assert(SCIPpqueueElems(pqueue)[pos] == (void *)nodeinfo);
	   SCIPpqueueDelPos(pqueue, pos);
	
	   /* update ssg if removed node was the lower bound defining node of its subtree */
	   if( pos == 0 )
	   {
	      NODEINFO* nodeinfofirst;
	      SCIP_Real oldgap;
	      SCIP_Real newgap;
	
	      oldgap = calcGap(scip, nodeinfo->lowerbound);
	      nodeinfofirst = (NODEINFO*)SCIPpqueueFirst(ssg->subtreepqueues[subtreeidx]);
	      assert(nodeinfofirst == NULL || subtreeidx == nodeinfofirst->subtreeidx);
	      newgap = calcGap(scip, nodeinfofirst != NULL ? nodeinfofirst->lowerbound : SCIPinfinity(scip) );
	
	      assert(SCIPisLE(scip, newgap, oldgap));
	
	      /* the SSG value is always up-to-date because it is recomputed when the primal bound changes */
	      ssg->value += ssg->scalingfactor * MIN(newgap - oldgap, 0.0);
	   }
	
	   SCIP_CALL( SCIPhashmapRemove(ssg->nodes2info, (void*)node) );
	
	   SCIPdebugMsg(scip, "Removed node %" SCIP_LONGINT_FORMAT " from open nodes of SSG\n",
	      SCIPnodeGetNumber(node));
	
	   SCIPfreeBlockMemory(scip, &nodeinfo);
	
	   return SCIP_OKAY;
	}
	
	/** insert children into subtree sum gap */
	static
	SCIP_RETCODE subtreeSumGapInsertChildren(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg                 /**< subtree sum gap data structure */
	   )
	{
	   int nchildren;
	   SCIP_NODE** children;
	   SCIP_NODE* focusnode;
	   SCIP_NODE* parentnode;
	   NODEINFO* parentnodeinfo;
	   int parentnodelabel;
	   int n;
	
	   assert(scip != NULL);
	   assert(ssg != NULL);
	
	   if( ssg->nsubtrees == 1 )
	      return SCIP_OKAY;
	
	   SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
	
	   if( nchildren == 0 )
	      return SCIP_OKAY;
	
	   focusnode = SCIPgetFocusNode(scip);
	
	   /* a rare case: the search has been stopped at some point, and the current focus node is the only descendant
	    * of its parent node
	    */
	   if( !SCIPhashmapExists(ssg->nodes2info, (void*)focusnode) )
	   {
	      parentnode = focusnode;
	      do
	      {
	         parentnode = SCIPnodeGetParent(parentnode);
	      } while( parentnode != NULL && !SCIPhashmapExists(ssg->nodes2info, (void *)parentnode));
	
	      assert(parentnode != NULL && SCIPhashmapExists(ssg->nodes2info, (void *)parentnode));
	   }
	   else
	      parentnode = focusnode;
	
	   parentnodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void *)parentnode);
	   parentnodelabel = parentnodeinfo->subtreeidx;
	
	   /* loop over children and insert the focus node label */
	   for( n = 0; n < nchildren; ++n )
	   {
	      assert(SCIPnodeGetParent(children[n]) == focusnode);
	
	      SCIPdebugMsg(scip,
	         "Inserting label %d for node number %" SCIP_LONGINT_FORMAT " (parent %" SCIP_LONGINT_FORMAT ")\n",
	         parentnodelabel, SCIPnodeGetNumber(children[n]), SCIPnodeGetNumber(parentnode));
	
	      SCIP_CALL( subtreeSumGapStoreNode(scip, ssg, children[n], parentnodelabel) );
	   }
	
	   /* remove focus node from hash map */
	   SCIP_CALL( subtreeSumGapRemoveNode(scip, ssg, parentnode) );
	
	   return SCIP_OKAY;
	}
	
	/* this function is inefficient because it loops over all open nodes, but can be used for debugging */
	#ifdef SCIP_DISABLED_CODE
	/** compute subtree sum gap from scratch (inefficiently because loop over all open nodes) */
	static
	SCIP_RETCODE subtreesumgapComputeFromScratch(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg,                /**< subtree sum gap data structure */
	   SCIP_Bool             updatescaling       /**< should the scaling factor be updated? */
	   )
	{
	   SCIP_Real* lowerbounds;
	   SCIP_NODE** opennodes[3];
	   SCIP_Real gapsum = 0;
	   SCIP_Real pb;
	   int nopennodes[3];
	   int l;
	   int t;
	
	   /* treat trivial cases: only 1 subtree, no incumbent solution */
	   if( SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
	   {
	      ssg->value = 1.0;
	
	      return SCIP_OKAY;
	   }
	
	   /* simply use normal gap in trivial case */
	   if( ssg->nsubtrees == 1 )
	   {
	      ssg->value = calcGap(scip, SCIPgetLowerbound(scip));
	
	      return SCIP_OKAY;
	   }
	
	    /* allocate temporary memory to store lower bound for every subtree    */
	   SCIP_CALL( SCIPallocBufferArray(scip, &lowerbounds, ssg->nsubtrees) );
	
	    /* initialize lower bounds as SCIPinfinity(scip) */
	   for( l = 0; l < ssg->nsubtrees; ++l )
	      lowerbounds[l] = SCIPinfinity(scip);
	
	    /* loop over children, siblings, and leaves to update subtree lower bounds */
	   SCIP_CALL( SCIPgetOpenNodesData(scip, &opennodes[0], &opennodes[1], &opennodes[2], &nopennodes[0], &nopennodes[1], &nopennodes[2]) );
	
	   /* loop over the three types leaves, siblings, leaves */
	   for( t = 0; t < 3; ++t )
	   {
	      int n;
	      /* loop over nodes of this type */
	      for( n = 0; n < nopennodes[t]; ++n )
	      {
	         SCIP_NODE* node = opennodes[t][n];
	         NODEINFO* nodeinfo;
	         SCIP_Real lowerbound;
	         int label;
	         nodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void *)node);
	         label = nodeinfo->subtreeidx;
	         lowerbound = nodeinfo->lowerbound;
	
	         assert(label >= 0 && label < ssg->nsubtrees);
	         lowerbounds[label] = MIN(lowerbounds[label], lowerbound);
	      }
	   }
	
	   /* compute subtree gaps in original space; sum them up */
	   pb = SCIPgetPrimalbound(scip);
	   for( l = 0; l < ssg->nsubtrees; ++l )
	   {
	      SCIP_Real subtreedualbound;
	      SCIP_Real subtreegap;
	      /* skip subtrees with infinite lower bound; they are empty and contribute 0.0 to the gap sum term */
	      if( SCIPisInfinity(scip, lowerbounds[l]) )
	         continue;
	
	      subtreedualbound = SCIPretransformObj(scip, lowerbounds[l]);
	
	      if( SCIPisEQ(scip, subtreedualbound, pb) )
	         continue;
	
	      subtreegap = REALABS(pb - subtreedualbound)/MAX(REALABS(pb),REALABS(subtreedualbound));
	      subtreegap = MIN(subtreegap, 1.0);
	
	      gapsum += subtreegap;
	   }
	
	   /* update the scaling factor by using the previous SSG value divided by the current gapsum */
	   if( updatescaling )
	   {
	      ssg->scalingfactor = ssg->value / MAX(gapsum, 1e-6);
	   }
	
	   /* update and store SSG value by considering scaling factor */
	   ssg->value = ssg->scalingfactor * gapsum;
	
	   SCIPfreeBufferArray(scip, &lowerbounds);
	
	   return SCIP_OKAY;
	}
	#endif
	
	/** compute subtree sum gap from scratch efficiently (linear effort in the number of subtrees) */
	static
	SCIP_RETCODE subtreeSumGapComputeFromScratchEfficiently(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg,                /**< subtree sum gap data structure */
	   SCIP_Bool             updatescaling       /**< should the scaling factor be updated? */
	   )
	{
	   SCIP_Real gapsum = 0.0;
	   int l;
	
	   /* treat trivial cases: only 1 subtree, no incumbent solution */
	   if( SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
	   {
	      ssg->value = 1.0;
	
	      return SCIP_OKAY;
	   }
	
	   if( ssg->nsubtrees == 1 )
	   {
	      ssg->value = calcGap(scip, SCIPgetLowerbound(scip));
	
	      return SCIP_OKAY;
	   }
	
	   /* compute subtree gaps in original space; sum them up */
	   for( l = 0; l < ssg->nsubtrees; ++l )
	   {
	      SCIP_Real subtreegap;
	      NODEINFO* nodeinfo;
	
	      assert(ssg->subtreepqueues[l] != NULL);
	
	      nodeinfo = (NODEINFO*)SCIPpqueueFirst(ssg->subtreepqueues[l]);
	
	      /* skip subtrees with infinite lower bound; they are empty and contribute 0.0 to the gap sum term */
	      if( nodeinfo == NULL || SCIPisInfinity(scip, nodeinfo->lowerbound) )
	         continue;
	
	      subtreegap = calcGap(scip, nodeinfo->lowerbound);
	
	      gapsum += subtreegap;
	   }
	
	   /* update the scaling factor by using the previous SSG value divided by the current gapsum */
	   if( updatescaling )
	   {
	      ssg->scalingfactor = ssg->value / MAX(gapsum, 1e-6);
	   }
	
	   /* update and store SSG value by considering scaling factor */
	   ssg->value = ssg->scalingfactor * gapsum;
	
	   return SCIP_OKAY;
	}
	
	/** update the subtree sum gap after a node event (branching or deletion of a node) */
	static
	SCIP_RETCODE subtreeSumGapUpdate(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SUBTREESUMGAP*        ssg,                /**< subtree sum gap data structure */
	   SCIP_NODE*            node,               /**< the corresponding node */
	   int                   nchildren,          /**< number of children */
	   SCIP_Longint          nsolvednodes        /**< number of solved nodes so far, used as a time stamp */
	   )
	{
	   SCIP_Bool updatescaling = FALSE;
	   SCIP_Bool insertchildren = (ssg->nsubtrees > 1 && nchildren > 0);
	
	   /* if the instance is solved or a node is cutoff at the initsolve stage or we are unbounded, the ssg is 0 */
	   if( SCIPgetStage(scip) == SCIP_STAGE_SOLVED || SCIPgetStage(scip) == SCIP_STAGE_INITSOLVE || SCIPisInfinity(scip, -SCIPgetUpperbound(scip)) )
	   {
	      ssg->value = 0.0;
	
	      return SCIP_OKAY;
	   }
	
	   /* make a new tree split if the primal bound has changed. */
	   if( ! SCIPisInfinity(scip, SCIPgetUpperbound(scip)) && ! SCIPisEQ(scip, SCIPgetPrimalbound(scip), ssg->pblastsplit) )
	   {
	      int nnewsubtrees;
	      SCIP_Bool addfocusnode;
	
	      addfocusnode = SCIPgetFocusNode(scip) != NULL && SCIPgetNChildren(scip) == 0 && !SCIPwasNodeLastBranchParent(scip, SCIPgetFocusNode(scip));
	      nnewsubtrees = SCIPgetNSiblings(scip) + SCIPgetNLeaves(scip) + SCIPgetNChildren(scip) + (addfocusnode ? 1 : 0);
	
	      /* check if number of new subtrees does not exceed maximum number of subtrees; always split if no split happened, yet */
	      if( ssg->nsubtrees <= 1 ||
	         ((ssg->nmaxsubtrees == -1 || nnewsubtrees <= ssg->nmaxsubtrees) &&
	            (nsolvednodes - ssg->nodelastsplit >= ssg->nminnodeslastsplit)) )
	      {
	         SCIP_CALL( subtreeSumGapSplit(scip, ssg, addfocusnode) );
	
	         /* remember time stamp */
	         ssg->nodelastsplit = nsolvednodes;
	      }
	      else
	      {
	         if( ssg->nmaxsubtrees != -1 && nnewsubtrees >= ssg->nmaxsubtrees )
	         {
	            SCIPdebugMsg(scip, "Keep split into %d subtrees because new split into %d subtrees exceeds limit %d\n",
	               ssg->nsubtrees, nnewsubtrees, ssg->nmaxsubtrees);
	         }
	         else
	         {
	            SCIPdebugMsg(scip, "Keep split into %d subtrees from %" SCIP_LONGINT_FORMAT " nodes ago\n",
	               ssg->nsubtrees, nsolvednodes - ssg->nodelastsplit);
	         }
	
	         /* no new split has happened; insert the new children to their SSG subtree */
	         if( insertchildren )
	         {
	            SCIP_CALL( subtreeSumGapInsertChildren(scip, ssg) );
	         }
	      }
	
	      ssg->pblastsplit = SCIPgetPrimalbound(scip);
	
	      updatescaling = TRUE;
	
	      /* compute the current SSG value from scratch */
	      SCIP_CALL( subtreeSumGapComputeFromScratchEfficiently(scip, ssg, updatescaling) );
	   }
	   /* otherwise, if new children have been created, label them */
	   else if( insertchildren )
	   {
	      SCIP_CALL( subtreeSumGapInsertChildren(scip, ssg) );
	   }
	
	   /* remove the node from the hash map if it is a leaf */
	   if( nchildren == 0 )
	   {
	      SCIP_CALL( subtreeSumGapRemoveNode(scip, ssg, node) );
	   }
	
	   return SCIP_OKAY;
	}
	
	/** reset tree data */
	static
	SCIP_RETCODE resetTreeData(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEDATA*             treedata            /**< tree data */
	   )
	{
	   /* simply set everything to 0 */
	   treedata->ninner = treedata->nleaves = treedata->nvisited = 0L;
	   treedata->weight = 0.0;
	
	   /* set up root node */
	   treedata->nnodes = 1;
	   treedata->nopen = 1;
	
	   SCIP_CALL( subtreeSumGapReset(scip, treedata->ssg) );
	
	   return SCIP_OKAY;
	}
	
	/** create tree data structure */
	static
	SCIP_RETCODE createTreeData(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEDATA**            treedata            /**< pointer to store tree data */
	   )
	{
	   assert(treedata != NULL);
	   assert(scip != NULL);
	
	   SCIP_CALL( SCIPallocMemory(scip, treedata) );
	
	   SCIP_CALL( subtreeSumGapCreate(scip, &(*treedata)->ssg) );
	
	   SCIP_CALL( resetTreeData(scip, *treedata) );
	
	   return SCIP_OKAY;
	}
	
	/** free tree data structure */
	static
	void freeTreeData(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEDATA**            treedata            /**< pointer to tree data */
	   )
	{
	   assert(scip != NULL);
	
	   if( *treedata == NULL )
	      return;
	
	   subtreeSumGapFree(scip, &(*treedata)->ssg);
	
	   SCIPfreeMemory(scip, treedata);
	   *treedata = NULL;
	}
	
	/** update tree data structure after a node has been solved/is about to be deleted */
	static
	SCIP_RETCODE updateTreeData(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TREEDATA*             treedata,           /**< tree data */
	   SCIP_NODE*            node,               /**< the corresponding node */
	   int                   nchildren           /**< the number of children */
	   )
	{
	   assert(node != NULL);
	
	   ++treedata->nvisited;
	   treedata->nopen--;
	
	   if( nchildren == 0 )
	   {
	      int depth = SCIPnodeGetDepth(node);
	      treedata->nleaves++;
	      treedata->weight += pow(0.5, (SCIP_Real)depth);
	   }
	   else
	   {
	      treedata->nnodes += nchildren;
	      treedata->nopen += nchildren;
	      ++treedata->ninner;
	   }
	
	   /* update the subtree sum gap */
	   if( ! SCIPisInRestart(scip) )
	   {
	      SCIP_CALL( subtreeSumGapUpdate(scip, treedata->ssg, node, nchildren, treedata->nvisited) );
	   }
	
	   return SCIP_OKAY;
	}
	
	/** get weighted backtrack estimation from this tree data */
	static
	SCIP_Real treeDataGetWbe(
	   TREEDATA*             treedata            /**< tree data */
	   )
	{
	   if( treedata->weight <= 0.0 || treedata->nleaves == 0 )
	      return -1.0;
	
	   return 2.0 * treedata->nleaves / (SCIP_Real)treedata->weight - 1.0;
	}
	
	#ifdef SCIP_DEBUG
	/* print method for tree data */
	static
	char* treeDataPrint(
	   TREEDATA*             treedata,           /**< tree data */
	   char*                 strbuf              /**< string buffer */
	   )
	{
	   (void )SCIPsnprintf(strbuf, SCIP_MAXSTRLEN,
	      "Tree Data: %" SCIP_LONGINT_FORMAT " nodes ("
	      "%" SCIP_LONGINT_FORMAT " visited, "
	      "%" SCIP_LONGINT_FORMAT " inner, "
	      "%" SCIP_LONGINT_FORMAT " leaves, "
	      "%" SCIP_LONGINT_FORMAT " open), "
	      "weight: %.4Lf, ssg %.4f",
	      treedata->nnodes,
	      treedata->nvisited,
	      treedata->ninner,
	      treedata->nleaves,
	      treedata->nopen,
	      treedata->weight,
	      treedata->ssg->value
	      );
	   return strbuf;
	}
	#endif
	
	/** reset double exponential smoothing */
	static
	void doubleExpSmoothReset(
	   DOUBLEEXPSMOOTH*      des,                /**< double exponential smoothing data structure */
	   SCIP_Real             initialvalue        /**< the initial value */
	   )
	{
	   des->n = 0;
	   des->level = SCIP_INVALID;
	   des->trend = SCIP_INVALID;
	   des->initialvalue = initialvalue;
	}
	
	/** initialize a double exponential smoothing data structure */
	static
	void doubleExpSmoothInit(
	   DOUBLEEXPSMOOTH*      des,                /**< double exponential smoothing data structure */
	   SCIP_Real             x1                  /**< the first sample value */
	   )
	{
	   assert(des != NULL);
	
	   des->n = 1;
	   des->level = x1;
	   des->trend = x1 - des->initialvalue;
	
	   des->usetrendinlevel = DES_USETRENDINLEVEL;
	
	   return;
	}
	
	/** update a double exponential smoothing data structure */
	static
	void doubleExpSmoothUpdate(
	   DOUBLEEXPSMOOTH*      des,                /**< double exponential smoothing data structure */
	   SCIP_Real             xnew                /**< new sample value */
	   )
	{
	   if( des->n == 0 )
	      doubleExpSmoothInit(des, xnew);
	   else
	   {
	      SCIP_Real newlevel;
	      SCIP_Real newtrend;
	
	      newlevel = des->alpha * xnew + (1.0 - des->alpha) * (des->level + des->usetrendinlevel ? des->trend : 0.0);
	      newtrend = des->beta * (newlevel - des->level) + (1.0 - des->beta) * des->trend;
	
	      des->level = newlevel;
	      des->trend = newtrend;
	   }
	}
	
	/** get the current trend (slope) computed by this double exponential smoothing */
	static
	SCIP_Real doubleExpSmoothGetTrend(
	   DOUBLEEXPSMOOTH*      des                 /**< double exponential smoothing data structure */
	   )
	{
	   assert(des != NULL);
	
	   if( des->n == 0 )
	      return SCIP_INVALID;
	
	   return des->trend;
	}
	
	/** reset time series */
	static
	void timeSeriesReset(
	   TIMESERIES*           timeseries          /**< pointer to store time series */
	   )
	{
	   timeseries->resolution = 1;
	   timeseries->nvals = 0;
	   timeseries->nobs = 0L;
	   timeseries->currentvalue = timeseries->initialvalue;
	   timeseries->smoothestimation = SCIP_INVALID;
	
	   doubleExpSmoothReset(&timeseries->des, timeseries->initialvalue);
	}
	
	/** create a time series object */
	static
	SCIP_RETCODE timeSeriesCreate(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TIMESERIES**          timeseries,         /**< pointer to store time series */
	   const char*           name,               /**< name of this time series */
	   SCIP_Real             targetvalue,        /**< target value of this time series */
	   SCIP_Real             initialvalue,       /**< the initial value of time series */
	   SCIP_Real             alpha,              /**< alpha parameter (level weight) for double exponential smoothing */
	   SCIP_Real             beta,               /**< beta parameter (level weight) for double exponential smoothing */
	   DECL_TIMESERIESUPDATE ((*timeseriesupdate)) /**< update callback at nodes, or NULL */
	   )
	{
	   TIMESERIES* timeseriesptr;
	   assert(scip != NULL);
	   assert(timeseries != NULL);
	   assert(name != NULL);
	   assert(alpha >= 0.0 && alpha <= 1);
	   assert(beta >= 0.0 && beta <= 1);
	
	   SCIP_CALL( SCIPallocMemory(scip, timeseries) );
	
	   timeseriesptr = *timeseries;
	   assert(timeseriesptr != NULL);
	
	   /* copy name */
	   SCIP_ALLOC( BMSduplicateMemoryArray(&timeseriesptr->name, name, strlen(name)+1) );
	
	   /* copy callbacks */
	   assert(timeseriesupdate != NULL);
	   timeseriesptr->timeseriesupdate = timeseriesupdate;
	
	   timeseriesptr->targetvalue = targetvalue;
	   timeseriesptr->valssize = 1024;
	   timeseriesptr->initialvalue = initialvalue;
	
	   SCIP_CALL( SCIPallocMemoryArray(scip, &timeseriesptr->vals, timeseriesptr->valssize) );
	   SCIP_CALL( SCIPallocMemoryArray(scip, &timeseriesptr->estimation, timeseriesptr->valssize) );
	
	   timeSeriesReset(timeseriesptr);
	
	   timeseriesptr->des.alpha = alpha;
	   timeseriesptr->des.beta = beta;
	
	   SCIPdebugMsg(scip, "Finished creation of time series '%s'\n", timeseriesptr->name);
	
	   return SCIP_OKAY;
	}
	
	/** free a time series */
	static
	void timeSeriesFree(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TIMESERIES**          timeseries          /**< pointer to time series */
	   )
	{
	   assert(scip != NULL);
	   assert(timeseries != NULL);
	
	   BMSfreeMemoryArray(&(*timeseries)->name);
	
	   SCIPfreeMemoryArray(scip, &(*timeseries)->vals);
	   SCIPfreeMemoryArray(scip, &(*timeseries)->estimation);
	
	   SCIPfreeMemory(scip, timeseries);
	
	   *timeseries = NULL;
	}
	
	/** get current value of time series */
	static
	SCIP_Real timeSeriesGetValue(
	   TIMESERIES*           timeseries          /**< time series */
	   )
	{
	   assert(timeseries != NULL);
	
	   return timeseries->currentvalue;
	}
	
	/** get target value (which this time series reaches at the end of the solution process) */
	static
	SCIP_Real timeSeriesGetTargetValue(
	   TIMESERIES*           timeseries          /**< time series */
	   )
	{
	   return timeseries->targetvalue;
	}
	
	/** get resolution of time series */
	static
	int timeSeriesGetResolution(
	   TIMESERIES*           timeseries          /**< time series */
	   )
	{
	   return timeseries->resolution;
	}
	
	/** estimate tree size at which time series reaches target value */
	static
	SCIP_Real timeSeriesEstimate(
	   TIMESERIES*           timeseries,         /**< time series */
	   TREEDATA*             treedata            /**< tree data for fallback estimation */
	   )
	{
	   SCIP_Real val;
	   SCIP_Real targetval;
	   SCIP_Real trend;
	   SCIP_Real estimated;
	   const SCIP_Real tolerance = 1e-6;
	
	   /* if no observations have been made yet, return infinity */
	   if( timeseries->nobs == 0L )
	      return -1.0;
	
	   val = timeSeriesGetValue(timeseries);
	   targetval = timeSeriesGetTargetValue(timeseries);
	
	   /* if the value has reached the target value already, return the number of observations */
	   if( EPSZ(val - targetval, tolerance) )
	      return treedata->nnodes;
	
	   trend = doubleExpSmoothGetTrend(&timeseries->des);
	
	   /* Get current value and trend. The linear trend estimation may point into the wrong direction
	    * In this case, we use the fallback mechanism that we will need twice as many nodes.
	    */
	   if( (targetval > val && trend < tolerance) || (targetval < val && trend > -tolerance) )
	   {
	      return 2.0 * treedata->nvisited;
	   }
	
	   /* compute after how many additional steps the current trend reaches the target value; multiply by resolution */
	   estimated = timeSeriesGetResolution(timeseries) * (timeseries->nvals + (targetval - val) / (SCIP_Real)trend);
	   return timeseries->useleafts ? 2.0 * estimated - 1.0 : estimated;
	}
	
	/** update time series smoothened estimation */
	static
	void timeSeriesUpdateSmoothEstimation(
	   TIMESERIES*           timeseries,         /**< time series */
	   SCIP_Real             estimation          /**< estimation value */
	   )
	{
	   if( timeseries->smoothestimation == SCIP_INVALID )/*lint !e777*/
	      timeseries->smoothestimation = estimation;
	   else
	   {
	      timeseries->smoothestimation *= (1.0 - SESCOEFF);
	      timeseries->smoothestimation += SESCOEFF * estimation;
	   }
	}
	
	/** get smooth estimation of time series */
	static
	SCIP_Real timeSeriesGetSmoothEstimation(
	   TIMESERIES*           timeseries          /**< time series */
	   )
	{
	   return timeseries->smoothestimation;
	}
	
	/** resample to lower resolution */
	static
	void timeSeriesResample(
	   TIMESERIES*           timeseries          /**< time series */
	   )
	{
	   DOUBLEEXPSMOOTH* des;
	   int i;
	
	   assert(timeseries->nvals % 2 == 0);
	
	   des = &timeseries->des;
	   doubleExpSmoothReset(des, timeseries->initialvalue);
	
	   /* compress vals array to store only every second entry */
	   for( i = 0; i < timeseries->nvals / 2; ++i )
	   {
	      timeseries->vals[i] = timeseries->vals[2 * i];
	      timeseries->estimation[i] = timeseries->estimation[2 * i];
	      doubleExpSmoothUpdate(des, timeseries->vals[i]);
	      timeSeriesUpdateSmoothEstimation(timeseries, timeseries->estimation[i]);
	   }
	
	   timeseries->resolution *= 2;
	   timeseries->nvals = timeseries->nvals / 2;
	}
	
	/** update time series */
	static
	SCIP_RETCODE timeSeriesUpdate(
	   SCIP*                 scip,               /**< SCIP data structure */
	   TIMESERIES*           timeseries,         /**< time series */
	   TREEDATA*             treedata,           /**< tree data */
	   SCIP_Bool             isleaf              /**< are we at a leaf node? */
	   )
	{
	   SCIP_Real value;
	
	   assert(scip != NULL);
	   assert(timeseries != NULL);
	   assert(treedata != NULL);
	
	   /* call update callback */
	   assert(timeseries->timeseriesupdate != NULL);
	   SCIP_CALL( timeseries->timeseriesupdate(scip, timeseries, treedata, &value) );
	
	   /* store the value as current value */
	   timeseries->currentvalue = value;
	
	   if( timeseries->useleafts && ! isleaf )
	      return SCIP_OKAY;
	
	   timeseries->nobs++;
	
	   /* if this is a leaf that matches the time series resolution, store the value */
	   if( timeseries->nobs % timeseries->resolution == 0 )
	   {
	      int tspos;
	      SCIP_Real estimate;
	
	      assert(timeseries->nvals < timeseries->valssize);
	      tspos = timeseries->nvals++;
	      timeseries->vals[tspos] = value;
	      doubleExpSmoothUpdate(&timeseries->des, value);
	      estimate = timeSeriesEstimate(timeseries, treedata);
	      timeseries->estimation[tspos] = estimate;
	      timeSeriesUpdateSmoothEstimation(timeseries, estimate);
	   }
	
	   /* if the time series has reached its capacity, resample and increase the resolution */
	   if( timeseries->nvals == timeseries->valssize )
	      timeSeriesResample(timeseries);
	
	   return SCIP_OKAY;
	}
	
	/** get name of time series */
	static
	char* timeSeriesGetName(
	   TIMESERIES*           timeseries          /**< time series */
	   )
	{
	   return timeseries->name;
	}
	
	/** reset all time series */
	static
	void resetTimeSeries(
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   TIMESERIES** tss = eventhdlrdata->timeseries;
	   int t;
	
	   /* loop over time series and reset them */
	   for( t = 0; t < NTIMESERIES; ++t )
	   {
	      assert(tss[t] != NULL);
	      timeSeriesReset(tss[t]);
	
	      tss[t]->useleafts = eventhdlrdata->useleafts;
	   }
	}
	
	/*
	 * Callback methods of event handler
	 */
	
	/** free all time series */
	static
	void freeTimeSeries(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   TIMESERIES** tss = eventhdlrdata->timeseries;
	   int t;
	
	   /* loop over time series and reset them */
	   for( t = 0; t < NTIMESERIES; ++t )
	   {
	      assert(tss[t] != NULL);
	      timeSeriesFree(scip, &tss[t]);
	   }
	}
	
	/** 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.
	 */
	static
	SCIP_Real getEnsembleEstimation(
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   TREEDATA* treedata;
	   SCIP_Real* coeffs;
	   SCIP_Real estim;
	   int t;
	
	   TSPOS tsposs[] = {
	      TSPOS_GAP,
	      TSPOS_TREEWEIGHT,
	      TSPOS_LFREQ,
	      TSPOS_SSG,
	      TSPOS_OPEN
	   };
	
	   /* coefficients for the early stage (tree weight <= 0.3) */
	   SCIP_Real coeffs_early[] = {
	      0.002, /* gap */
	      0.381, /* tree weight */
	      0.469, /* leaf-frequency */
	      0.292, /* SSG */
	      0.004  /* open-nodes */
	   };
	
	   /* coefficients for the intermediate stage (0.3 < tree weight <= 0.6) */
	   SCIP_Real coeffs_intermediate[] = {
	      0.011, /* gap */
	      0.193, /* tree weight */
	      0.351, /* leaf-frequency */
	      0.012, /* SSG */
	      0.051  /* open-nodes */
	   };
	
	   /* coefficients for the late stage (tree weight > 0.6) */
	   SCIP_Real coeffs_late[] = {
	      0.000, /* gap */
	      0.033, /* tree weight */
	      0.282, /* leaf-frequency */
	      0.003, /* SSG */
	      0.024  /* open-nodes */
	   };
	
	   assert(eventhdlrdata != NULL);
	   treedata = eventhdlrdata->treedata;
	
	   /* assign coeffs based on stage */
	   if( treedata->weight <= 0.3 )
	   {
	      estim = 0.0;
	      coeffs = coeffs_early;
	      /* ensure that coeffs and time series are still aligned */
	      assert(sizeof(coeffs_early)/sizeof(SCIP_Real) == NTIMESERIES); /*lint !e506*/
	   }
	   else if( treedata->weight <= 0.6 )
	   {
	      coeffs = coeffs_intermediate;
	      /* ensure that coeffs and time series are still aligned */
	      assert(sizeof(coeffs_intermediate)/sizeof(SCIP_Real) == NTIMESERIES); /*lint !e506*/
	
	      /* initialize by intermediate WBE coefficient */
	      estim = 0.156 * treeDataGetWbe(treedata);
	   }
	   else
	   {
	      coeffs = coeffs_late;
	      /* ensure that coeffs and time series are still aligned */
	      assert(sizeof(coeffs_late)/sizeof(SCIP_Real) == NTIMESERIES); /*lint !e506*/
	
	      /* initialize by late WBE coefficient */
	      estim = 0.579 * treeDataGetWbe(treedata);
	   }
	
	   /* combine estimation using the stage-dependent coefficients */
	   for( t = 0; t < NTIMESERIES; ++t )
	   {
	      SCIP_Real testim;
	      TSPOS tspos = tsposs[t];
	      testim = timeSeriesEstimate(eventhdlrdata->timeseries[tspos], treedata);
	
	      if( testim < 0.0 )
	         testim = treedata->nnodes;
	
	      estim += coeffs[t] * testim;
	   }
	
	   if( estim < treedata->nnodes )
	      return (SCIP_Real)treedata->nnodes;
	   else
	      return estim;
	}
	
	/** get approximation of search tree completion depending on the selected method */
	static
	SCIP_RETCODE getSearchCompletion(
	   SCIP_EVENTHDLRDATA*   eventhdlrdata,      /**< event handler data */
	   SCIP_Real*            completed           /**< pointer to store the search tree completion */
	   )
	{
	   SCIP_Real values[9];
	   TREEDATA* treedata;
	   char completiontype;
	
	   assert(eventhdlrdata != NULL);
	   treedata = eventhdlrdata->treedata;
	   completiontype = eventhdlrdata->completiontypeparam;
	
	   /* infer automatic completion type
	    *
	    *  use regression forest if available,
	    *  or
	    *  use monotone regression if both SSG and tree weight are meaningful;
	    *  or
	    *  use tree weight or SSG, depending which one is available,
	    *  or
	    *  use gap, which is always available
	    */
	   if( completiontype == COMPLETIONTYPE_AUTO )
	   {
	      SCIP_Bool useweight = eventhdlrdata->treeisbinary;
	      SCIP_Bool usessg = treedata->ssg->pblastsplit != SSG_STARTPRIMBOUND;/*lint !e777*/
	
	      if( eventhdlrdata->regforest != NULL )
	         completiontype = COMPLETIONTYPE_REGFOREST;
	      else if( useweight && usessg )
	         completiontype = COMPLETIONTYPE_MONOREG;
	      else if( useweight )
	         completiontype = COMPLETIONTYPE_TREEWEIGHT;
	      else if( usessg )
	         completiontype = COMPLETIONTYPE_SSG;
	      else
	         completiontype = COMPLETIONTYPE_GAP;
	   }
	
	   /* compute the search tree completion based on the selected method */
	   switch (completiontype)
	   {
	   /* use regression forest */
	   case COMPLETIONTYPE_REGFOREST:
	      values[0] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_TREEWEIGHT]);
	      values[1] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_TREEWEIGHT]->des);
	      values[2] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_SSG]);
	      values[3] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_SSG]->des);
	      values[4] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_LFREQ]);
	      values[5] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_LFREQ]->des);
	      values[6] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_GAP]);
	      values[7] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_GAP]->des);
	      values[8] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_OPEN]->des) < 0 ? 1.0 : 0.0;
	
	      *completed = SCIPregForestPredict(eventhdlrdata->regforest, values);
	      break;
	
	   /* interpolate between ssg and tree weight */
	   case COMPLETIONTYPE_MONOREG:
	      *completed = eventhdlrdata->coefmonoweight * (SCIP_Real)treedata->weight +
	         eventhdlrdata->coefmonossg * (1.0 - treedata->ssg->value);
	      break;
	
	   case COMPLETIONTYPE_TREEWEIGHT:
	      *completed = (SCIP_Real)treedata->weight;
	      break;
	
	   case COMPLETIONTYPE_GAP:
	      *completed = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_GAP]); /* gap is stored as 1 - gap */
	      break;
	
	   case COMPLETIONTYPE_SSG:
	      *completed = 1.0 - treedata->ssg->value; /* ssg is decreasing */
	      break;
	
	   default:
	      SCIPerrorMessage("Unsupported completion type '%c'\n", completiontype);
	      SCIPABORT();
	      return SCIP_PARAMETERWRONGVAL;
	   }
	   return SCIP_OKAY;
	}
	
	/** tree size estimation based on search tree completion */
	static
	SCIP_RETCODE getEstimCompletion(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata,      /**< event handler data */
	   SCIP_Real*            estim               /**< pointer to store the estimation value */
	   )
	{
	   SCIP_Real completed;
	
	   *estim = -1.0;
	
	   SCIP_CALL( getSearchCompletion(eventhdlrdata, &completed) );
	
	   completed = MIN(completed, 1.0);
	
	   if( completed > 0.0 )
	      *estim = SCIPgetNNodes(scip) / completed;
	
	   return SCIP_OKAY;
	}
	
	/** update callback at nodes */
	static
	DECL_TIMESERIESUPDATE(timeseriesUpdateGap)
	{ /*lint --e{715}*/
	   SCIP_Real primalbound;
	   SCIP_Real dualbound;
	
	   assert(scip != NULL);
	   assert(ts != NULL);
	   assert(value != NULL);
	
	   /* avoid to call SCIPgetDualbound during a restart where the queue is simply emptied */
	   if( SCIPisInRestart(scip) )
	   {
	      *value = timeSeriesGetValue(ts);
	
	      return SCIP_OKAY;
	   }
	
	   primalbound = SCIPgetPrimalbound(scip);
	   dualbound = SCIPgetDualbound(scip);
	   if( SCIPisInfinity(scip, REALABS(primalbound)) || SCIPisInfinity(scip, REALABS(dualbound)) )
	      *value = 0;
	   else if( SCIPisEQ(scip, primalbound, dualbound) )
	      *value = 1.0;
	   else
	   {
	      SCIP_Real abspb;
	      SCIP_Real absdb;
	
	      abspb = REALABS(primalbound);
	      absdb = REALABS(dualbound);
	      *value = 1.0 - REALABS(primalbound - dualbound)/MAX(abspb, absdb);
	   }
	
	   /* using this max, we set the closed gap to 0 in the case where the primal and dual bound differ in their sign */
	   *value = MAX(*value, 0.0);
	
	   return SCIP_OKAY;
	}
	
	/** update callback at nodes */
	static
	DECL_TIMESERIESUPDATE(timeseriesUpdateTreeWeight)
	{ /*lint --e{715}*/
	   *value = (SCIP_Real)treedata->weight;
	
	   return SCIP_OKAY;
	}
	
	/** update callback at nodes */
	static
	DECL_TIMESERIESUPDATE(timeseriesUpdateLeafFreq)
	{ /*lint --e{715}*/
	   if( treedata->nvisited == 0 )
	      *value = -0.5;
	   else
	      *value = (treedata->nleaves - 0.5)/(SCIP_Real)treedata->nvisited;
	
	   return SCIP_OKAY;
	}
	
	/** update callback at nodes */
	static
	DECL_TIMESERIESUPDATE(timeseriesUpdateSsg)
	{ /*lint --e{715}*/
	   if( treedata->nvisited == 0 )
	      *value = 1.0;
	   else
	      *value = treedata->ssg->value;
	
	   return SCIP_OKAY;
	}
	
	/** update callback at nodes */
	static
	DECL_TIMESERIESUPDATE(timeseriesUpdateOpenNodes)
	{ /*lint --e{715}*/
	   if( treedata->nvisited == 0 )
	      *value = 0.0;
	   else
	      *value = (SCIP_Real)treedata->nopen;
	
	   return SCIP_OKAY;
	}
	
	/** include time series to forecast into event handler */
	static
	SCIP_RETCODE includeTimeseries(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   assert(scip != NULL);
	   assert(eventhdlrdata != NULL);
	
	   /* include gap time series */
	   SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_GAP], "gap", 1.0, 0.0,
	            DES_ALPHA_GAP, DES_BETA_GAP, timeseriesUpdateGap) );
	
	   /* include tree weight time series */
	   SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_TREEWEIGHT], "tree-weight", 1.0, 0.0,
	            DES_ALPHA_TREEWEIGHT, DES_BETA_TREEWEIGHT, timeseriesUpdateTreeWeight) );
	
	   /* include leaf time series */
	   SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_LFREQ], "leaf-frequency", 0.5, -0.5,
	            DES_ALPHA_LEAFFREQUENCY, DES_BETA_LEAFFREQUENCY, timeseriesUpdateLeafFreq) );
	
	   /* include SSG time series */
	   SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_SSG], "ssg", 0.0, 1.0,
	            DES_ALPHA_SSG, DES_BETA_SSG, timeseriesUpdateSsg) );
	
	   /* include open nodes time series */
	   SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_OPEN], "open-nodes", 0.0, 0.0,
	            DES_ALPHA_OPENNODES, DES_BETA_OPENNODES, timeseriesUpdateOpenNodes) );
	
	   return SCIP_OKAY;
	}
	
	/** get restartpolicy based on the value of the restart parameter */
	static
	RESTARTPOLICY getRestartPolicy(
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   switch (eventhdlrdata->restartpolicyparam)
	   {
	   case RESTARTPOLICY_CHAR_ALWAYS:
	      return RESTARTPOLICY_ALWAYS;
	   case RESTARTPOLICY_CHAR_NEVER:
	      return RESTARTPOLICY_NEVER;
	   case RESTARTPOLICY_CHAR_COMPLETION:
	      return RESTARTPOLICY_COMPLETION;
	   case RESTARTPOLICY_CHAR_ESTIMATION:
	      return RESTARTPOLICY_ESTIMATION;
	   default:
	      SCIPerrorMessage("Unknown restart policy %c\n", eventhdlrdata->restartpolicyparam);
	      break;
	   }
	
	   return RESTARTPOLICY_NEVER;
	}
	
	/** check if a restart is applicable considering limit and threshold user parameters */
	static
	SCIP_Bool isRestartApplicable(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   SCIP_Longint nnodes;
	
	   /* check whether to apply restarts when there are active pricers available */
	   if( SCIPgetNActivePricers(scip) > 0 && ! eventhdlrdata->restartactpricers )
	      return FALSE;
	
	   /* check whether to apply a restart when nonlinear constraints are present */
	   if( SCIPisNLPConstructed(scip) && ! eventhdlrdata->restartnonlinear )
	      return FALSE;
	
	   /* check if max number of restarts has been reached */
	   if( eventhdlrdata->restartlimit != -1 && eventhdlrdata->nrestartsperformed >= eventhdlrdata->restartlimit )
	      return FALSE;
	
	   /* check if number of nodes exceeds the minimum number of nodes */
	   if( eventhdlrdata->countonlyleaves )
	      nnodes = eventhdlrdata->treedata->nleaves;
	   else
	      nnodes = eventhdlrdata->treedata->nvisited;
	
	   if( nnodes < eventhdlrdata->minnodes )
	      return FALSE;
	
	   return TRUE;
	}
	
	/** should a restart be applied based on the value of the selected completion method? */   /*lint --e{715}*/
	static
	SCIP_Bool shouldApplyRestartCompletion(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{  /*lint --e{715}*/
	   SCIP_Real completion;
	
	   SCIP_CALL_ABORT( getSearchCompletion(eventhdlrdata, &completion) );
	
	   /* if the estimation exceeds the current number of nodes by a dramatic factor, restart */
	   if( completion < 1.0 / eventhdlrdata->restartfactor )
	   {
	      SCIPstatistic(
	         SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
	            "Completion %.5f less than restart threshold %.5f\n",
	            completion, 1.0 / eventhdlrdata->restartfactor);
	      )
	
	      return TRUE;
	   }
	
	   return FALSE;
	}
	
	/** should a restart be applied based on the value of the selected completion method? */
	static
	SCIP_Bool shouldApplyRestartEstimation(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   SCIP_Real estimation;
	
	   estimation = SCIPgetTreesizeEstimation(scip);
	
	   if( estimation < 0.0 )
	   {
	      SCIPstatistic(
	         SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
	            "Estimation %g is still unavailable\n",
	            estimation);
	      )
	
	      return TRUE;
	   }
	
	   /* if the estimation exceeds the current number of nodes by a dramatic factor, restart */
	   if( estimation > eventhdlrdata->treedata->nnodes * eventhdlrdata->restartfactor )
	   {
	      SCIPstatistic(
	         SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL,
	            "Estimation %g exceeds number of estimation tree nodes %" SCIP_LONGINT_FORMAT " by a factor of %.1f\n",
	            estimation, eventhdlrdata->treedata->nnodes, estimation / eventhdlrdata->treedata->nnodes);
	      )
	
	      return TRUE;
	   }
	
	   return FALSE;
	}
	
	/** check if a restart should be performed based on the given restart policy */
	static
	SCIP_Bool shouldApplyRestart(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata       /**< event handler data */
	   )
	{
	   SCIP_Bool applyrestart = FALSE;
	
	   switch (getRestartPolicy(eventhdlrdata))
	   {
	   case RESTARTPOLICY_ALWAYS:
	      applyrestart = TRUE;
	      break;
	   case RESTARTPOLICY_NEVER:
	      applyrestart = FALSE;
	      break;
	   case RESTARTPOLICY_COMPLETION:
	      applyrestart = shouldApplyRestartCompletion(scip, eventhdlrdata);
	      break;
	   case RESTARTPOLICY_ESTIMATION:
	      applyrestart = shouldApplyRestartEstimation(scip, eventhdlrdata);
	      break;
	   default:
	      break;
	   }
	
	   return applyrestart;
	}
	
	/** update all time series */
	static
	SCIP_RETCODE updateTimeseries(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata,      /**< event handler data */
	   TREEDATA*             treedata,           /**< tree data */
	   SCIP_Bool             isleaf              /**< are we at a leaf node? */
	   )
	{
	   TIMESERIES** tss = eventhdlrdata->timeseries;
	   int t;
	
	   /* loop over time series */
	   for( t = 0; t < NTIMESERIES; ++t )
	   {
	      assert(tss[t] != NULL);
	      SCIP_CALL( timeSeriesUpdate(scip, tss[t], treedata, isleaf) );
	
	#ifdef SCIP_MORE_DEBUG
	      SCIPdebugMsg(scip,
	         "Update of time series '%s', current value %.4f (%" SCIP_LONGINT_FORMAT " observations)\n",
	         timeSeriesGetName(tss[t]), timeSeriesGetValue(tss[t]), tss[t]->nobs);
	#endif
	   }
	
	   return SCIP_OKAY;
	}
	
	/** print a treesize estimation report into the string buffer */
	static
	char* printReport(
	   SCIP*                 scip,               /**< SCIP data structure */
	   SCIP_EVENTHDLRDATA*   eventhdlrdata,      /**< event handler data */
	   char*                 strbuf,             /**< string buffer */
	   int                   reportnum           /**< report number, or 0 to omit number */
	   )
	{
	   TREEDATA* treedata = eventhdlrdata->treedata;
	   char* ptr = strbuf;
	   SCIP_Real completed;
	   SCIP_Real wbeestim;
	   char wbeestimstr[SCIP_MAXSTRLEN];
	   int t;
	
	   /* print report number */
	   if( reportnum > 0 )
	      ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "Report %d\nTime Elapsed: %.2f\n", reportnum, SCIPgetSolvingTime(scip));
	
	   ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
	            "Estim. Tree Size   :%11" SCIP_LONGINT_FORMAT "\n",
	            (SCIP_Longint)SCIPgetTreesizeEstimation(scip));
	
	   SCIP_CALL_ABORT( getSearchCompletion(eventhdlrdata, &completed) );
	
	   completed = MIN(1.0, completed);
	   completed = MAX(0.0, completed);
	
	   /* print tree data */
	   ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
	         "%-19s: %" SCIP_LONGINT_FORMAT " nodes ("
	         "%" SCIP_LONGINT_FORMAT " visited, "
	         "%" SCIP_LONGINT_FORMAT " internal, "
	         "%" SCIP_LONGINT_FORMAT " leaves, "
	         "%" SCIP_LONGINT_FORMAT " open), "
	         "weight: %.4Lf completed %.4f\n",
	         "Estimation Tree",
	         treedata->nnodes,
	         treedata->nvisited,
	         treedata->ninner,
	         treedata->nleaves,
	         treedata->nopen,
	         treedata->weight,
	         completed
	         );
	
	   /* print estimations */
	   ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "Estimations        : %10s %10s %10s %10s %10s",
	            "estim", "value", "trend", "resolution", "smooth");
	   ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "\n");
	
	   wbeestim = treeDataGetWbe(eventhdlrdata->treedata);
	   ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "  wbe              : %10s %10s %10s %10s %10s\n",
	            real2String(wbeestim, wbeestimstr, 0), "-", "-", "-", "-");
	
	   ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "  tree-profile     : %10.0f %10s %10s %10s %10s\n",
	            predictTotalSizeTreeProfile(scip, eventhdlrdata->treeprofile, eventhdlrdata->treeprofile_minnodesperdepth),
	            "-", "-", "-", "-");
	
	   /* print time series forecasts */
	   for( t = 0; t < NTIMESERIES; ++t )
	   {
	      SCIP_Real trend;
	      SCIP_Real smoothestim;
	      TIMESERIES* ts = eventhdlrdata->timeseries[t];
	      char trendstr[SCIP_MAXSTRLEN];
	      char smoothestimstr[SCIP_MAXSTRLEN];
	
	      trend = doubleExpSmoothGetTrend(&ts->des);
	      smoothestim = timeSeriesGetSmoothEstimation(ts);
	
	      ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "  %-17s: %10.0f %10.5f %10s %10d %10s\n",
	            timeSeriesGetName(ts),
	            timeSeriesEstimate(ts, eventhdlrdata->treedata),
	            timeSeriesGetValue(ts),
	            real2String(trend, trendstr, 5),
	            timeSeriesGetResolution(ts),
	            real2String(smoothestim, smoothestimstr, 0));
	   }
	
	   if( reportnum > 0 )
	      (void) SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "End of Report %d\n", reportnum);
	
	   return strbuf;
	}
	
	
	/** copy method for event handler plugins (called when SCIP copies plugins) */
	static
	SCIP_DECL_EVENTCOPY(eventCopyEstim)
	{  /*lint --e{715}*/
	   assert(scip != NULL);
	
	   SCIP_CALL( SCIPincludeEventHdlrEstim(scip) );
	
	   return SCIP_OKAY;
	}
	
	/** destructor of event handler to free user data (called when SCIP is exiting) */
	static
	SCIP_DECL_EVENTFREE(eventFreeEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   freeTreeData(scip, &eventhdlrdata->treedata);
	
	   freeTimeSeries(scip, eventhdlrdata);
	
	   SCIPfreeMemory(scip, &eventhdlrdata);
	
	   return SCIP_OKAY;
	}
	
	/** initialization method of event handler (called after problem was transformed) */
	static
	SCIP_DECL_EVENTINIT(eventInitEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   /* test if user specified a regression forest */
	   if( 0 != strncmp(eventhdlrdata->regforestfilename, DEFAULT_REGFORESTFILENAME, strlen(DEFAULT_REGFORESTFILENAME)) )
	   {
	      SCIP_CALL( SCIPregForestFromFile(&eventhdlrdata->regforest, eventhdlrdata->regforestfilename) );
	   }
	
	   eventhdlrdata->lastrestartrun = 0;
	   eventhdlrdata->nrestartsperformed = 0;
	
	   return SCIP_OKAY;
	}
	
	/** deinitialization method of event handler (called before transformed problem is freed) */
	static
	SCIP_DECL_EVENTEXIT(eventExitEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   SCIPregForestFree(&eventhdlrdata->regforest);
	
	   return SCIP_OKAY;
	}
	
	/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
	static
	SCIP_DECL_EVENTINITSOL(eventInitsolEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   eventhdlrdata->restarthitcounter = 0;
	   eventhdlrdata->weightlastreport = 0.0;
	   eventhdlrdata->nreports = 0;
	
	   /* reset tree data */
	   SCIP_CALL( resetTreeData(scip, eventhdlrdata->treedata) );
	
	   resetTimeSeries(eventhdlrdata);
	
	   SCIP_CALL( SCIPcatchEvent(scip, EVENTTYPE_ESTIM, eventhdlr, NULL, NULL) );
	
	   if( eventhdlrdata->treeprofile_enabled )
	   {
	      SCIP_CALL( createTreeProfile(scip, &eventhdlrdata->treeprofile) );
	   }
	
	   eventhdlrdata->treeisbinary = TRUE;
	
	   return SCIP_OKAY;
	}
	
	/** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
	static
	SCIP_DECL_EVENTEXITSOL(eventExitsolEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   if( eventhdlrdata->treeprofile != NULL )
	      freeTreeProfile(scip, &eventhdlrdata->treeprofile);
	
	   SCIP_CALL( SCIPdropEvent(scip, EVENTTYPE_ESTIM, eventhdlr, NULL, -1) );
	
	   return SCIP_OKAY;
	}
	
	/** execution method of event handler */
	static
	SCIP_DECL_EVENTEXEC(eventExecEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	   SCIP_Bool isleaf;
	   SCIP_EVENTTYPE eventtype;
	   TREEDATA* treedata;
	   char strbuf[SCIP_MAXSTRLEN];
	
	   assert(scip != NULL);
	   assert(eventhdlr != NULL);
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	   eventtype = SCIPeventGetType(event);
	   treedata = eventhdlrdata->treedata;
	
	   /* actual leaf nodes for our tree data are children/siblings/leaves or the focus node itself (deadend)
	    * if it has not been branched on
	    */
	   isleaf = (eventtype == SCIP_EVENTTYPE_NODEDELETE) &&
	      (SCIPnodeGetType(SCIPeventGetNode(event)) == SCIP_NODETYPE_CHILD ||
	         SCIPnodeGetType(SCIPeventGetNode(event)) == SCIP_NODETYPE_SIBLING ||
	         SCIPnodeGetType(SCIPeventGetNode(event)) == SCIP_NODETYPE_LEAF ||
	         (SCIPnodeGetType(SCIPeventGetNode(event)) == SCIP_NODETYPE_DEADEND && !SCIPwasNodeLastBranchParent(scip, SCIPeventGetNode(event))));
	
	   if( eventtype == SCIP_EVENTTYPE_NODEBRANCHED || isleaf )
	   {
	      SCIP_NODE* eventnode;
	      int nchildren = 0;
	
	      if( eventtype == SCIP_EVENTTYPE_NODEBRANCHED )
	      {
	         nchildren = SCIPgetNChildren(scip);
	
	         /* update whether the tree is still binary */
	         if( nchildren != 2 )
	            eventhdlrdata->treeisbinary = FALSE;
	      }
	
	      eventnode = SCIPeventGetNode(event);
	      SCIP_CALL( updateTreeData(scip, treedata, eventnode, nchildren) );
	      SCIP_CALL( updateTreeProfile(scip, eventhdlrdata->treeprofile, eventnode) );
	
	#ifdef SCIP_DEBUG
	      SCIPdebugMsg(scip, "%s\n", treeDataPrint(treedata, strbuf));
	#endif
	
	      SCIP_CALL( updateTimeseries(scip, eventhdlrdata, treedata, nchildren == 0) );
	
	      /* should a new report be printed? */
	      if( eventhdlrdata->reportfreq >= 0 && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN &&
	         (eventhdlrdata->reportfreq == 0
	         || treedata->weight >= eventhdlrdata->weightlastreport + 1.0 / (SCIP_Real)eventhdlrdata->reportfreq) )
	      {
	         SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s\n", printReport(scip, eventhdlrdata, strbuf, ++eventhdlrdata->nreports));
	
	         if( eventhdlrdata->reportfreq > 0 )
	            eventhdlrdata->weightlastreport = 1 / (SCIP_Real)eventhdlrdata->reportfreq * SCIPfloor(scip, ((SCIP_Real)treedata->weight * eventhdlrdata->reportfreq));
	         else
	            eventhdlrdata->weightlastreport = (SCIP_Real)treedata->weight;
	      }
	   }
	
	   /* if nodes have been pruned, things are progressing, don't restart right now */
	   if( isleaf )
	      return SCIP_OKAY;
	
	   /* check if all conditions are met such that the event handler should run */
	   if( ! isRestartApplicable(scip, eventhdlrdata) )
	      return SCIP_OKAY;
	
	   /* test if a restart should be applied */
	   if( shouldApplyRestart(scip, eventhdlrdata) )
	   {
	      eventhdlrdata->restarthitcounter++;
	
	      if( eventhdlrdata->restarthitcounter >= eventhdlrdata->hitcounterlim )
	      {
	         /* safe that we triggered a restart at this run */
	         if( SCIPgetNRuns(scip) > eventhdlrdata->lastrestartrun )
	         {
	            eventhdlrdata->nrestartsperformed++;
	
	            SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
	               "Restart triggered after %d consecutive estimations that the remaining tree will be large\n",
	               eventhdlrdata->restarthitcounter);
	         }
	
	         eventhdlrdata->lastrestartrun = SCIPgetNRuns(scip);
	
	         SCIP_CALL( SCIPrestartSolve(scip) );
	      }
	   }
	   else
	   {
	      eventhdlrdata->restarthitcounter = 0;
	   }
	
	   return SCIP_OKAY;
	}
	
	/** output method of statistics table to output file stream 'file' */
	static
	SCIP_DECL_TABLEOUTPUT(tableOutputEstim)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLR* eventhdlr;
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	   char strbuf[SCIP_MAXSTRLEN];
	
	   eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
	   assert(eventhdlr != NULL);
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   SCIPinfoMessage(scip, file, "%s", printReport(scip, eventhdlrdata, strbuf, 0));
	
	   return SCIP_OKAY;
	}
	
	/** output method of search tree completion display column to output file stream 'file' */
	static
	SCIP_DECL_DISPOUTPUT(dispOutputCompleted)
	{  /*lint --e{715}*/
	   SCIP_EVENTHDLR* eventhdlr;
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	   TREEDATA* treedata;
	   SCIP_Real completed;
	
	   assert(disp != NULL);
	   assert(strcmp(SCIPdispGetName(disp), DISP_NAME) == 0);
	   assert(scip != NULL);
	
	   eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
	   assert(eventhdlr != NULL);
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	   treedata = eventhdlrdata->treedata;
	
	   SCIP_CALL( getSearchCompletion(eventhdlrdata, &completed) );
	
	   completed = MIN(completed, 1.0);
	
	   if( treedata->weight >= 0.005 && completed > 0 )
	      SCIPinfoMessage(scip, file, "%7.2f%%", 100.0 * completed);
	   else
	      SCIPinfoMessage(scip, file, " unknown");
	
	   return SCIP_OKAY;
	}
	
	/** creates event handler for tree size estimation */
	SCIP_RETCODE SCIPincludeEventHdlrEstim(
	   SCIP*                 scip                /**< SCIP data structure */
	   )
	{
	   SCIP_RETCODE retcode;
	   SCIP_EVENTHDLRDATA* eventhdlrdata = NULL;
	   SCIP_EVENTHDLR* eventhdlr = NULL;
	
	   /* create estim event handler data */
	   SCIP_CALL( SCIPallocMemory(scip, &eventhdlrdata) );
	   BMSclearMemory(eventhdlrdata);
	
	   SCIP_CALL_TERMINATE( retcode, createTreeData(scip, &eventhdlrdata->treedata), TERMINATE );
	
	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
	         eventExecEstim, eventhdlrdata) );
	   assert(eventhdlr != NULL);
	
	   /* set non fundamental callbacks via setter functions */
	   SCIP_CALL( SCIPsetEventhdlrCopy(scip, eventhdlr, eventCopyEstim) );
	   SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeEstim) );
	   SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitEstim) );
	   SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitEstim) );
	   SCIP_CALL( SCIPsetEventhdlrInitsol(scip, eventhdlr, eventInitsolEstim) );
	   SCIP_CALL( SCIPsetEventhdlrExitsol(scip, eventhdlr, eventExitsolEstim) );
	
	   /* add estimation event handler parameters */
	   SCIP_CALL( SCIPaddCharParam(scip, "estimation/restarts/restartpolicy", "restart policy: (a)lways, (c)ompletion, (e)stimation, (n)ever",
	         &eventhdlrdata->restartpolicyparam, FALSE, DEFAULT_RESTARTPOLICY, "acen", NULL, NULL) );
	
	   SCIP_CALL( SCIPaddCharParam(scip, "estimation/method",
	            "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",
	         &eventhdlrdata->estimmethod, FALSE, DEFAULT_ESTIMMETHOD, ESTIMMETHODS, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddIntParam(scip, "estimation/restarts/restartlimit", "restart limit",
	         &eventhdlrdata->restartlimit, FALSE, DEFAULT_RESTARTLIMIT, -1, INT_MAX, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddLongintParam(scip, "estimation/restarts/minnodes", "minimum number of nodes before restart",
	         &eventhdlrdata->minnodes, FALSE, DEFAULT_MINNODES, -1L, SCIP_LONGINT_MAX, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddBoolParam(scip, "estimation/restarts/countonlyleaves", "should only leaves count for the minnodes parameter?",
	         &eventhdlrdata->countonlyleaves, DEFAULT_COUNTONLYLEAVES, FALSE, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddRealParam(scip, "estimation/restarts/restartfactor",
	         "factor by which the estimated number of nodes should exceed the current number of nodes",
	         &eventhdlrdata->restartfactor, FALSE, DEFAULT_RESTARTFACTOR, 1.0, SCIP_REAL_MAX, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddBoolParam(scip, "estimation/restarts/restartnonlinear",
	         "whether to apply a restart when nonlinear constraints are present",
	         &eventhdlrdata->restartnonlinear, FALSE, DEFAULT_RESTARTNONLINEAR, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddBoolParam(scip, "estimation/restarts/restartactpricers",
	         "whether to apply a restart when active pricers are used",
	         &eventhdlrdata->restartactpricers, FALSE, DEFAULT_RESTARTACTPRICERS, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddRealParam(scip, "estimation/coefmonoweight",
	         "coefficient of tree weight in monotone approximation of search completion",
	         &eventhdlrdata->coefmonoweight, FALSE, DEFAULT_COEFMONOWEIGHT, 0.0, 1.0, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddRealParam(scip, "estimation/coefmonossg",
	         "coefficient of 1 - SSG in monotone approximation of search completion",
	         &eventhdlrdata->coefmonossg, FALSE, DEFAULT_COEFMONOSSG, 0.0, 1.0, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddIntParam(scip, "estimation/restarts/hitcounterlim", "limit on the number of successive samples to really trigger a restart",
	         &eventhdlrdata->hitcounterlim, FALSE, DEFAULT_HITCOUNTERLIM, 1, INT_MAX, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddIntParam(scip, "estimation/reportfreq",
	         "report frequency on estimation: -1: never, 0:always, k >= 1: k times evenly during search",
	         &eventhdlrdata->reportfreq, TRUE, DEFAULT_REPORTFREQ, -1, INT_MAX / 2, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddStringParam(scip, "estimation/regforestfilename", "user regression forest in RFCSV format",
	         &eventhdlrdata->regforestfilename, FALSE, DEFAULT_REGFORESTFILENAME, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddCharParam(scip, "estimation/completiontype",
	         "approximation of search tree completion: (a)uto, (g)ap, tree (w)eight, (m)onotone regression, (r)egression forest, (s)sg",
	         &eventhdlrdata->completiontypeparam, FALSE, DEFAULT_COMPLETIONTYPE, "agmrsw", NULL, NULL) );
	
	   SCIP_CALL( SCIPaddBoolParam(scip, "estimation/treeprofile/enabled",
	         "should the event handler collect data?",
	         &eventhdlrdata->treeprofile_enabled, FALSE, DEFAULT_TREEPROFILE_ENABLED, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddRealParam(scip, "estimation/treeprofile/minnodesperdepth",
	         "minimum average number of nodes at each depth before producing estimations",
	         &eventhdlrdata->treeprofile_minnodesperdepth, FALSE, DEFAULT_TREEPROFILE_MINNODESPERDEPTH, 1.0, SCIP_REAL_MAX, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddBoolParam(scip, "estimation/useleafts",
	         "use leaf nodes as basic observations for time series, or all nodes?",
	         &eventhdlrdata->useleafts, TRUE, DEFAULT_USELEAFTS, NULL, NULL) );
	
	   /* SSG parameters */
	   SCIP_CALL( SCIPaddIntParam(scip, "estimation/ssg/nmaxsubtrees",
	         "the maximum number of individual SSG subtrees; -1: no limit",
	         &eventhdlrdata->treedata->ssg->nmaxsubtrees, FALSE, DEFAULT_SSG_NMAXSUBTREES, -1, INT_MAX / 2, NULL, NULL) );
	
	   SCIP_CALL( SCIPaddLongintParam(scip, "estimation/ssg/nminnodeslastsplit",
	         "minimum number of nodes to process between two consecutive SSG splits",
	         &eventhdlrdata->treedata->ssg->nminnodeslastsplit, FALSE, DEFAULT_SSG_NMINNODESLASTSPLIT, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
	
	   /* include statistics table */
	   SCIP_CALL( SCIPincludeTable(scip, TABLE_NAME, TABLE_DESC, TRUE,
	         NULL, NULL, NULL, NULL, NULL, NULL, tableOutputEstim,
	         NULL, TABLE_POSITION, TABLE_EARLIEST_STAGE) );
	
	   /* include time series into event handler */
	   SCIP_CALL( includeTimeseries(scip, eventhdlrdata) );
	
	   /* include display column */
	   SCIP_CALL( SCIPincludeDisp(scip, DISP_NAME, DISP_DESC, DISP_HEADER, SCIP_DISPSTATUS_AUTO,
	         NULL, NULL, NULL, NULL, NULL, NULL, dispOutputCompleted,
	         NULL, DISP_WIDTH, DISP_PRIORITY, DISP_POSITION, DISP_STRIPLINE) );
	
	/* cppcheck-suppress unusedLabel */
	TERMINATE:
	   if( retcode != SCIP_OKAY )
	   {
	      freeTreeData(scip, &eventhdlrdata->treedata);
	      SCIPfreeMemory(scip, &eventhdlrdata);
	   }
	
	   return retcode;
	}
	
	/** return an estimation of the final tree size */
	SCIP_Real SCIPgetTreesizeEstimation(
	   SCIP*                 scip                /**< SCIP data structure */
	   )
	{
	   SCIP_EVENTHDLR* eventhdlr;
	   SCIP_EVENTHDLRDATA* eventhdlrdata;
	   TSPOS tspos = TSPOS_NONE;
	   SCIP_Real estim;
	
	   assert(scip != NULL);
	
	   eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
	   if( eventhdlr == NULL )
	   {
	      SCIPwarningMessage(scip, "SCIPgetTreesizeEstimation() called, but event handler " EVENTHDLR_NAME " is missing.\n");
	      return -1.0;
	   }
	
	   eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
	   assert(eventhdlrdata != NULL);
	
	   switch (eventhdlrdata->estimmethod)
	   {
	   case ESTIMMETHOD_COMPL:
	      SCIP_CALL_ABORT( getEstimCompletion(scip, eventhdlrdata, &estim) );
	      return estim;
	
	   case ESTIMMETHOD_ENSMBL:
	      return getEnsembleEstimation(eventhdlrdata);
	
	   /* for the requested time series methods, we specify the array position */
	   case ESTIMMETHOD_GAP:
	      tspos = TSPOS_GAP;
	      break;
	
	   case ESTIMMETHOD_LFREQ:
	      tspos = TSPOS_LFREQ;
	      break;
	
	   case ESTIMMETHOD_OPEN:
	      tspos = TSPOS_OPEN;
	      break;
	
	   case ESTIMMETHOD_TREEWEIGHT:
	      tspos = TSPOS_TREEWEIGHT;
	      break;
	
	   case ESTIMMETHOD_SSG:
	      tspos = TSPOS_SSG;
	      break;
	
	   /* tree profile estimation */
	   case ESTIMMETHOD_TPROF:
	      return predictTotalSizeTreeProfile(scip, eventhdlrdata->treeprofile, eventhdlrdata->treeprofile_minnodesperdepth);
	
	   /* Weighted backtrack estimation */
	   case ESTIMMETHOD_WBE:
	      return treeDataGetWbe(eventhdlrdata->treedata);
	
	   default:
	      SCIPerrorMessage("Unknown estimation '%c' method specified, should be one of [%s]\n",
	         eventhdlrdata->estimmethod, ESTIMMETHODS);
	      SCIPABORT();
	      break;
	   }
	
	   assert(tspos != TSPOS_NONE);
	   return (tspos == TSPOS_NONE ? -1.0 : timeSeriesEstimate(eventhdlrdata->timeseries[tspos], eventhdlrdata->treedata));
	}