Scippy

SCIP

Solving Constraint Integer Programs

event_estim.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file event_estim.c
17  * @brief event handler for tree size estimation and restarts
18  *
19  * This event handler plugin provides different methods for approximating the current fraction of the search
20  * that has already been completed and for estimating the total tree size at completion.
21  * It can trigger restarts of the current run if the current run seems hopeless.
22  *
23  * For details about the available approximations of search completion, please see
24  *
25  * Anderson, Hendel, Le Bodic, Pfetsch
26  * Estimating The Size of Branch-and-Bound Trees
27  * under preparation
28  *
29  * This code is a largely enriched version of a code that was used for clairvoyant restarts, see
30  *
31  * Anderson, Hendel, Le Bodic, Viernickel
32  * Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation
33  * AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2018
34  *
35  * @author Gregor Hendel
36  */
37 
38 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 
40 #include <string.h>
41 #include "blockmemshell/memory.h"
42 #include "scip/event_estim.h"
43 #include "scip/prop_symmetry.h"
44 #include "scip/pub_disp.h"
45 #include "scip/pub_event.h"
46 #include "scip/pub_fileio.h"
47 #include "scip/pub_message.h"
48 #include "scip/pub_misc.h"
49 #include "scip/pub_tree.h"
50 #include "scip/scip_disp.h"
51 #include "scip/scip_event.h"
52 #include "scip/scip_general.h"
53 #include "scip/scip_mem.h"
54 #include "scip/scip_message.h"
55 #include "scip/scip_nlp.h"
56 #include "scip/scip_numerics.h"
57 #include "scip/scip_param.h"
58 #include "scip/scip_pricer.h"
59 #include "scip/scip_sol.h"
60 #include "scip/scip_solve.h"
61 #include "scip/scip_solvingstats.h"
62 #include "scip/scip_table.h"
63 #include "scip/scip_timing.h"
64 #include "scip/scip_tree.h"
65 #include "scip/type_disp.h"
66 #include "scip/type_event.h"
67 #include "scip/type_message.h"
68 #include "scip/type_misc.h"
69 #include "scip/type_retcode.h"
70 #include "scip/type_stat.h"
71 #include "scip/type_table.h"
72 
73 #define EVENTHDLR_NAME "estim"
74 #define EVENTHDLR_DESC "event handler for tree size estimation and restarts"
75 #define EVENTTYPE_ESTIM (SCIP_EVENTTYPE_NODEDELETE | SCIP_EVENTTYPE_NODEBRANCHED)
76 
77 /*
78  * Data structures
79  */
80 
81 /** enumerator for available restart policies */
83 {
84  RESTARTPOLICY_NEVER = 0, /**< never restart (disable this event handler) */
85  RESTARTPOLICY_ALWAYS = 1, /**< always restart (can be fine tuned by using minimum number of nodes and restart limit) */
86  RESTARTPOLICY_ESTIMATION = 2, /**< base restart on the estimation method */
87  RESTARTPOLICY_COMPLETION = 3 /**< trigger restart based on search completion approximation */
88 };
89 
91 
92 #define RESTARTPOLICY_CHAR_NEVER 'n'
93 #define RESTARTPOLICY_CHAR_ALWAYS 'a'
94 #define RESTARTPOLICY_CHAR_COMPLETION 'c'
95 #define RESTARTPOLICY_CHAR_ESTIMATION 'e'
96 
97 #define DES_USETRENDINLEVEL TRUE /**< Should the trend be used in the level update? */
98 
99 /* constants for the table estimation */
100 #define TABLE_NAME "estim"
101 #define TABLE_DESC "tree size estimations statistics table"
102 #define TABLE_POSITION 18500 /**< the position of the statistics table */
103 #define TABLE_EARLIEST_STAGE SCIP_STAGE_INIT /**< output of the statistics table is only printed from this stage onwards */
104 
105 /* constants for the search completion display column */
106 #define DISP_NAME "completed"
107 #define DISP_DESC "completion of search in percent (based on tree size estimation)"
108 #define DISP_HEADER "compl."
109 #define DISP_WIDTH 8 /**< the width of the display column */
110 #define DISP_PRIORITY 110000 /**< the priority of the display column */
111 #define DISP_POSITION 30100 /**< the relative position of the display column */
112 #define DISP_STRIPLINE TRUE /**< the default for whether the display column should be separated
113  * with a line from its right neighbor */
114 #define INITIALSIZE 100
115 #define SESCOEFF 0.75 /**< coefficient of single exponential smoothing of estimation */
117 /* double exponential smoothing parameters for different time series */
118 #define DES_ALPHA_TREEWEIGHT 0.65
119 #define DES_BETA_TREEWEIGHT 0.15
121 #define DES_ALPHA_GAP 0.6
122 #define DES_BETA_GAP 0.15
124 #define DES_ALPHA_LEAFFREQUENCY 0.3
125 #define DES_BETA_LEAFFREQUENCY 0.33
127 #define DES_ALPHA_SSG 0.6
128 #define DES_BETA_SSG 0.15
130 #define DES_ALPHA_OPENNODES 0.6
131 #define DES_BETA_OPENNODES 0.15
133 #define MAX_REGFORESTSIZE 10000000 /**< size limit (number of nodes) for regression forest */
135 
136 
137 /* computation of search completion */
138 #define COMPLETIONTYPE_AUTO 'a' /**< automatic (regression forest if available, else monotone regression on binary and SSG on nonbinary trees) */
139 #define COMPLETIONTYPE_REGFOREST 'r' /**< regression forest (must be provided by user) */
140 #define COMPLETIONTYPE_MONOREG 'm' /**< monotone regression (using tree weight and SSG) */
141 #define COMPLETIONTYPE_TREEWEIGHT 'w' /**< use tree weight value as approximation of search tree completion */
142 #define COMPLETIONTYPE_SSG 's' /**< use SSG value as approximation of search tree completion */
143 #define COMPLETIONTYPE_GAP 'g' /**< use gap value as approximation of search tree completion */
145 
146 /* tree size estimation method */
147 #define ESTIMMETHOD_COMPL 'c' /**< estimation based on projection of current search completion */
148 #define ESTIMMETHOD_WBE 'b' /**< weighted backtrack estimation */
149 #define ESTIMMETHOD_ENSMBL 'e' /**< estimation based on an ensemble of the individual estimations */
150 #define ESTIMMETHOD_GAP 'g' /**< estimation based on double exponential smoothing for open nodes */
151 #define ESTIMMETHOD_LFREQ 'l' /**< estimation based on double exponential smoothing for leaf frequency */
152 #define ESTIMMETHOD_OPEN 'o' /**< estimation based on double exponential smoothing for open nodes */
153 #define ESTIMMETHOD_SSG 's' /**< estimation based on double exponential smoothing for sum of subtree gaps */
154 #define ESTIMMETHOD_TPROF 't' /**< estimation based on tree profile method */
155 #define ESTIMMETHOD_TREEWEIGHT 'w' /**< estimation based on double exponential smoothing for tree weight */
157 #define ESTIMMETHODS "bceglostw"
159 /* constants and default values for treeprofile parameters */
160 #define TREEPROFILE_MINSIZE 512 /**< minimum size (depth) that tree profile can hold */
161 #define SSG_STARTPRIMBOUND SCIP_INVALID /**< initial value of primal bound used within SSG */
163 /** double exponential smoothing data structure */
164 struct DoubleExpSmooth
165 {
166  SCIP_Real alpha; /**< level smoothing constant */
167  SCIP_Real beta; /**< trend smoothing constant */
168  SCIP_Real level; /**< estimation of the current level used for smoothing */
169  SCIP_Real trend; /**< estimation of the current trend (slope) */
170  SCIP_Real initialvalue; /**< the level value at 0 observations */
171  SCIP_Bool usetrendinlevel; /**< Should the trend be used in the level update? */
172  int n; /**< number of observations */
173 };
174 typedef struct DoubleExpSmooth DOUBLEEXPSMOOTH;
176 /** time series data structure for leaf time series
177  *
178  * These time series are the basic ingredient for tree size estimation via forecasting.
179  *
180  * This general class represents concrete time series such as the closed gap, tree weight, and leaf frequency.
181  * Through callbacks for data (de-)initialization and value queries, it provides a common interface
182  * to which double exponential smoothing or window forecasts can be applied.
183  */
184 typedef struct TimeSeries TIMESERIES;
186 /** data structure for convenient access of tree information */
187 typedef struct TreeData TREEDATA;
189 
190 #define NTIMESERIES 5
192 /** time series position in event handler time series array */
193 enum TsPos
194 {
195  TSPOS_NONE = -1, /**< invalid array position */
196  TSPOS_GAP = 0, /**< time series position of gap */
197  TSPOS_TREEWEIGHT = 1, /**< time series position of tree weight */
198  TSPOS_LFREQ = 2, /**< time series position of leaf frequency */
199  TSPOS_SSG = 3, /**< time series position of SSG */
200  TSPOS_OPEN = 4 /**< time series position of open nodes */
201 };
202 
203 typedef enum TsPos TSPOS;
205 /** regression forest data structure */
206 typedef struct SCIP_RegForest SCIP_REGFOREST;
208 /** statistics collected from profile used for prediction */
209 struct TreeProfileStats
210 {
211  int maxdepth; /**< maximum node depth encountered */
212  int lastfulldepth; /**< deepest layer for which all nodes have been explored */
213  int minwaistdepth; /**< minimum depth of the waist, i.e. the widest part of the tree */
214  int maxwaistdepth; /**< maximum depth of the waist, i.e. the widest part of the tree */
215 };
216 
217 typedef struct TreeProfileStats TREEPROFILESTATS;
219 
220 /** profile data structure for tree */
221 struct TreeProfile
222 {
223  SCIP_Longint* profile; /**< array to store the tree profile */
224  int profilesize; /**< size of the profile array */
225  TREEPROFILESTATS stats; /**< statistics collected from profile used for prediction */
226  SCIP_Real lastestimate; /**< the last estimate predicted by predictTotalSizeTreeprofile() */
227  TREEPROFILESTATS lastestimatestats; /**< tree profile statistics at last estimation */
228 };
229 
230 typedef struct TreeProfile TREEPROFILE;
232 /* default values of user parameters */
233 #define DEFAULT_USELEAFTS TRUE /**< Use leaf nodes as basic observations for time series, or all nodes? */
234 #define DEFAULT_REPORTFREQ -1 /**< report frequency on estimation: -1: never, 0: always, k >= 1: k times evenly during search */
235 #define DEFAULT_REGFORESTFILENAME "-" /**< default file name of user regression forest in RFCSV format */
236 #define DEFAULT_COEFMONOWEIGHT 0.3667 /**< coefficient of tree weight in monotone approximation of search completion */
237 #define DEFAULT_COEFMONOSSG 0.6333 /**< coefficient of 1 - SSG in monotone approximation of search completion */
238 #define DEFAULT_COMPLETIONTYPE COMPLETIONTYPE_AUTO /**< default computation of search tree completion */
239 #define DEFAULT_ESTIMMETHOD ESTIMMETHOD_TREEWEIGHT /**< default tree size estimation method: (c)ompletion, (e)nsemble, time series forecasts on either
240  * (g)ap, (l)eaf frequency, (o)open nodes,
241  * tree (w)eight, (s)sg, or (t)ree profile or w(b)e */
242 #define DEFAULT_TREEPROFILE_ENABLED FALSE /**< Should the event handler collect data? */
243 #define DEFAULT_TREEPROFILE_MINNODESPERDEPTH 20.0 /**< minimum average number of nodes at each depth before producing estimations */
244 #define DEFAULT_RESTARTPOLICY 'e' /**< default restart policy: (a)lways, (c)ompletion, (e)stimation, (n)ever */
245 #define DEFAULT_RESTARTLIMIT 1 /**< default restart limit */
246 #define DEFAULT_MINNODES 1000L /**< minimum number of nodes before restart */
247 #define DEFAULT_COUNTONLYLEAVES FALSE /**< should only leaves count for the minnodes parameter? */
248 #define DEFAULT_RESTARTFACTOR 50.0 /**< factor by which the estimated number of nodes should exceed the current number of nodes */
249 #define DEFAULT_RESTARTNONLINEAR FALSE /**< whether to apply a restart when nonlinear constraints are present */
250 #define DEFAULT_RESTARTACTPRICERS FALSE /**< whether to apply a restart when active pricers are used */
251 #define DEFAULT_HITCOUNTERLIM 50 /**< limit on the number of successive samples to really trigger a restart */
252 #define DEFAULT_SSG_NMAXSUBTREES -1 /**< the maximum number of individual SSG subtrees; the old split is kept if
253  * a new split exceeds this number of subtrees ; -1: no limit */
254 #define DEFAULT_SSG_NMINNODESLASTSPLIT 0L /**< minimum number of nodes to process between two consecutive SSG splits */
256 /** event handler data */
257 struct SCIP_EventhdlrData
258 {
259  SCIP_REGFOREST* regforest; /**< regression forest data structure */
260  TIMESERIES* timeseries[NTIMESERIES]; /**< array of time series slots */
261  TREEDATA* treedata; /**< tree data */
262  TREEPROFILE* treeprofile; /**< tree profile data structure */
263  char* regforestfilename; /**< file name of user regression forest in RFCSV format */
264  SCIP_Real restartfactor; /**< factor by which the estimated number of nodes should exceed the current number of nodes */
265  SCIP_Real weightlastreport; /**< tree weight at which last report was printed */
266  SCIP_Real treeprofile_minnodesperdepth;/**< minimum average number of nodes at each depth before producing estimations */
267  SCIP_Real coefmonoweight; /**< coefficient of tree weight in monotone approximation of search completion */
268  SCIP_Real coefmonossg; /**< coefficient of 1 - SSG in monotone approximation of search completion */
269  SCIP_Longint minnodes; /**< minimum number of nodes in a run before restart is triggered */
270  int restartlimit; /**< How often should a restart be triggered? (-1 for no limit) */
271  int nrestartsperformed; /**< number of restarts performed so far */
272  int restarthitcounter; /**< the number of successive samples that would trigger a restart */
273  int hitcounterlim; /**< limit on the number of successive samples to really trigger a restart */
274  int nreports; /**< the number of reports already printed */
275  int reportfreq; /**< report frequency on estimation: -1: never, 0:always, k >= 1: k times evenly during search */
276  int lastrestartrun; /**< the last run at which this event handler triggered restart */
277  char restartpolicyparam; /**< restart policy parameter */
278  char estimmethod; /**< tree size estimation method: (c)ompletion, (e)nsemble, time series forecasts on either
279  * (g)ap, (l)eaf frequency, (o)open nodes,
280  * tree (w)eight, (s)sg, or (t)ree profile or w(b)e */
281  char completiontypeparam;/**< approximation of search tree completion:
282  * (a)uto, (g)ap, tree (w)eight, (m)onotone regression, (r)egression forest, (s)sg */
283  SCIP_Bool countonlyleaves; /**< Should only leaves count for the minnodes parameter? */
284  SCIP_Bool useleafts; /**< Use leaf nodes as basic observations for time series, or all nodes? */
285  SCIP_Bool treeprofile_enabled;/**< Should the event handler collect treeprofile data? */
286  SCIP_Bool treeisbinary; /**< internal flag if all branching decisions produced 2 children */
287  SCIP_Bool restartnonlinear; /**< whether to apply a restart when nonlinear constraints are present */
288  SCIP_Bool restartactpricers; /**< whether to apply a restart when active pricers are used */
289 };
290 
291 typedef struct SubtreeSumGap SUBTREESUMGAP;
292 
293 struct TreeData
294 {
295  SCIP_Longint nnodes; /**< the total number of nodes */
296  SCIP_Longint nopen; /**< the current number of open nodes */
297  SCIP_Longint ninner; /**< the number of inner nodes */
298  SCIP_Longint nleaves; /**< the number of final leaf nodes */
299  SCIP_Longint nvisited; /**< the number of visited nodes */
300  long double weight; /**< the current tree weight (sum of leaf weights) */
301  SUBTREESUMGAP* ssg; /**< subtree sum gap data structure */
302 };
305 {
306  SCIP_Real value; /**< the current subtree sum gap */
307  SCIP_HASHMAP* nodes2info; /**< map between nodes and their subtree indices */
308  SCIP_PQUEUE** subtreepqueues; /**< array of priority queues, one for each subtree */
309  SCIP_Real scalingfactor; /**< the current scaling factor */
310  SCIP_Real pblastsplit; /**< primal bound when last split occurred */
311  SCIP_Longint nodelastsplit; /**< last node at which a subtree split occurred */
312  SCIP_Longint nminnodeslastsplit; /**< minimum number of nodes to process between two consecutive SSG splits */
313  int nmaxsubtrees; /**< the maximum number of individual SSG subtrees; the old split is kept if
314  * a new split exceeds this number of subtrees ; -1: no limit */
315  int nsubtrees; /**< the current number n of subtrees labeled 0 .. n - 1 */
316 };
318 /** update callback of time series */
319 #define DECL_TIMESERIESUPDATE(x) SCIP_RETCODE x (\
320  SCIP* scip, \
321  TIMESERIES* ts, \
322  TREEDATA* treedata, \
323  SCIP_Real* value \
324  )
325 
326 /** time series data structure for leaf time series */
327 struct TimeSeries
328 {
329  DOUBLEEXPSMOOTH des; /**< double exponential smoothing data structure */
330  char* name; /**< name of this time series */
331  SCIP_Real* vals; /**< value array of this time series */
332  SCIP_Real* estimation; /**< array of estimations of this time series */
333  SCIP_Real smoothestimation; /**< smoothened estimation value */
334  SCIP_Real targetvalue; /**< target value of this time series */
335  SCIP_Real currentvalue; /**< current value of time series */
336  SCIP_Real initialvalue; /**< the initial value of time series */
337  SCIP_Longint nobs; /**< total number of observations */
338  int valssize; /**< size of value array */
339  int nvals; /**< number of values */
340  int resolution; /**< current (inverse of) resolution */
341  SCIP_Bool useleafts; /**< Should this time series be recorded at leaf nodes, or at every node? */
342  DECL_TIMESERIESUPDATE((*timeseriesupdate));/**< update callback at nodes */
343 };
345 /** extended node information for SSG priority queue */
346 struct NodeInfo
347 {
348  SCIP_NODE* node; /**< search tree node */
349  SCIP_Real lowerbound; /**< lower bound of the node at insertion into priority queue */
350  int pos; /**< position of this node in priority queue */
351  int subtreeidx; /**< subtree index of this node */
352 };
353 typedef struct NodeInfo NODEINFO;
356 {
357  int ntrees; /**< number of trees in this forest */
358  int dim; /**< feature dimension */
359  int* nbegin; /**< array of root node indices of each tree */
360  int* child; /**< child index pair of each internal node, or (-1, -1) for leaves */
361  int* splitidx; /**< data index for split at node, or -1 at a leaf */
362  SCIP_Real* value; /**< split position at internal nodes, prediction at leaves */
363  int size; /**< length of node arrays */
364 };
366 /*
367  * Local methods
368  */
369 
370 /** convert number to string and treat SCIP_INVALID as '-' */
371 static
372 char* real2String(
373  SCIP_Real num, /**< number to convert to string */
374  char* buf, /**< string buffer */
375  int digits /**< number of decimal digits */
376  )
377 {
378  if( num == SCIP_INVALID )/*lint !e777*/
379  (void) SCIPsnprintf(buf, 1, "-");
380  else if( num >= 1e+20 ) /*lint !e777*/
381  (void) SCIPsnprintf(buf, 3, "inf");
382  else
383  (void) SCIPsnprintf(buf, SCIP_MAXSTRLEN, "%10.*f", digits, num);
384 
385  return buf;
386 }
387 
388 /** free a regression forest data structure */
389 static
390 void SCIPregForestFree(
391  SCIP_REGFOREST** regforest /**< regression forest data structure */
392  )
393 {
394  SCIP_REGFOREST* regforestptr;
395 
396  assert(regforest != NULL);
397 
398  if( *regforest == NULL )
399  return;
400  regforestptr = *regforest;
401 
402  BMSfreeMemoryArrayNull(&regforestptr->nbegin);
403  BMSfreeMemoryArrayNull(&regforestptr->child);
404  BMSfreeMemoryArrayNull(&regforestptr->splitidx);
405  BMSfreeMemoryArrayNull(&regforestptr->value);
406 
407  BMSfreeMemory(regforest);
408 }
409 
410 /** make a prediction with regression forest */
411 static
413  SCIP_REGFOREST* regforest, /**< regression forest data structure */
414  SCIP_Real* datapoint /**< a data point that matches the dimension of this regression forest */
415  )
416 {
417  int treeidx;
418  SCIP_Real value = 0.0;
419 
420  assert(regforest != NULL);
421  assert(datapoint != NULL);
422 
423  SCIPdebugMessage("Start prediction method of regression forest\n");
424 
425  /* loop through the trees */
426  for( treeidx = 0; treeidx < regforest->ntrees; ++treeidx )
427  {
428  int treepos = regforest->nbegin[treeidx];
429  int* childtree = &(regforest->child[2 * treepos]);
430  int* splitidxtree = &(regforest->splitidx[treepos]);
431  int pos = 0;
432  SCIP_Real* valuetree = &(regforest->value[treepos]);
433 
434  SCIPdebugMessage("Tree %d at position %d\n", treeidx, treepos);
435 
436  /* find the correct leaf */
437  while( splitidxtree[pos] != - 1 )
438  {
439  int goright;
440 
441  assert(splitidxtree[pos] < regforest->dim);
442 
443  goright = (datapoint[splitidxtree[pos]] > valuetree[pos]) ? 1 : 0;
444  pos = childtree[2 * pos + goright];
445  }
446 
447  value += valuetree[pos];
448  }
449 
450  /* return the average value that the trees predict */
451  return value / (SCIP_Real)(regforest->ntrees);
452 }
453 
454 /** read a regression forest from an rfcsv file
455  *
456  * TODO improve this parser to better capture wrong user input, e.g., if the dimension is wrong
457  */
458 static
460  SCIP_REGFOREST** regforest, /**< regression forest data structure */
461  const char* filename /**< name of file with the regression forest data */
462  )
463 {
464  SCIP_RETCODE retcode = SCIP_OKAY;
465  SCIP_FILE* file;
466  SCIP_REGFOREST* regforestptr;
467  char buffer[SCIP_MAXSTRLEN];
468  char firstlineformat[SCIP_MAXSTRLEN];
469  char dataformat[SCIP_MAXSTRLEN];
470  char valuestr[SCIP_MAXSTRLEN];
471  SCIP_Bool error = FALSE;
472  int ntrees;
473  int dim;
474  int size;
475  int sscanret;
476  int pos;
477  int treepos;
478 
479  /* try to open file */
480  file = SCIPfopen(filename, "r");
481 
482  if( file == NULL )
483  return SCIP_NOFILE;
484 
485  /* parse read the first line that contains the number of trees, feature dimension, and total number of nodes */
486  (void) SCIPsnprintf(firstlineformat, SCIP_MAXSTRLEN, "### NTREES=%%10d FEATURE_DIM=%%10d LENGTH=%%10d\n");
487  if( SCIPfgets(buffer, (int) sizeof(buffer), file) == NULL )
488  {
489  error = TRUE;
490  SCIPerrorMessage("Could not read first line of regression file '%s'\n", filename);
491  goto CLOSEFILE;
492  }
493 
494  /* coverity[secure_coding] */
495  sscanret = sscanf(buffer, firstlineformat, &ntrees, &dim, &size);
496 
497  if( sscanret != 3 )
498  {
499  error = TRUE;
500  SCIPerrorMessage("Could not extract tree information from buffer line [%s]\n", buffer);
501  goto CLOSEFILE;
502  }
503 
504  SCIPdebugMessage("Read ntrees=%d, dim=%d, size=%d (return value %d)\n", ntrees, dim, size, sscanret);
505 
506  /* check if the tree is too big, or numbers are negative */
507  if( size > MAX_REGFORESTSIZE )
508  {
509  error = TRUE;
510  SCIPerrorMessage("Requested size %d exceeds size limit %d for regression trees", size, MAX_REGFORESTSIZE);
511  goto CLOSEFILE;
512  }
513 
514  if( dim <= 0 || ntrees <= 0 || size <= 0 )
515  {
516  error = TRUE;
517  SCIPerrorMessage("Cannot create regression tree with negative size, dimension, or number of trees\n");
518  goto CLOSEFILE;
519  }
520 
521  /* allocate memory in regression forest data structure */
522  SCIP_ALLOC_TERMINATE( retcode, BMSallocMemory(regforest), FREEFOREST );
523  BMSclearMemory(*regforest);
524  regforestptr = *regforest;
525 
526  SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->nbegin, ntrees), FREEFOREST );
527  SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->child, 2 * size), FREEFOREST ); /*lint !e647*/
528  SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->splitidx, size), FREEFOREST );
529  SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&regforestptr->value, size), FREEFOREST );
530 
531  regforestptr->dim = dim;
532  regforestptr->size = size;
533  regforestptr->ntrees = ntrees;
534 
535  SCIPdebugMessage("Random Forest allocated\n");
536 
537  /* loop through the rest of the file, which contains the comma separated node data */
538  (void) SCIPsnprintf(dataformat, SCIP_MAXSTRLEN, "%%10d,%%10d,%%10d,%%10d,%%%ds\n", SCIP_MAXSTRLEN);
539 
540  pos = 0;
541  treepos = 0;
542  while( !SCIPfeof(file) && !error )
543  {
544  int node;
545  char* endptr;
546 
547  /* get next line */
548  if( SCIPfgets(buffer, (int) sizeof(buffer), file) == NULL )
549  break;
550 
551  sscanret = sscanf(buffer, dataformat,
552  &node,
553  &regforestptr->child[2 * pos],
554  &regforestptr->child[2 * pos + 1],
555  &regforestptr->splitidx[pos],
556  valuestr);
557 
558  if( sscanret != 5 )
559  {
560  SCIPerrorMessage("Something wrong with line %d '%s'", pos + 1, buffer);
561  error = TRUE;
562  }
563 
564  (void)SCIPstrToRealValue(valuestr, &regforestptr->value[pos], &endptr);
565 
566  /* new root node - increase the tree index position */
567  if( node == 0 )
568  {
569  assert(treepos < regforestptr->ntrees);
570 
571  regforestptr->nbegin[treepos++] = pos;
572  }
573 
574  ++pos;
575  }
576 
577  goto CLOSEFILE;
578 
579 /* insufficient memory for allocating regression forest */
580 FREEFOREST:
581  assert(retcode == SCIP_NOMEMORY);
582  SCIPregForestFree(regforest);
583 
584 CLOSEFILE:
585  SCIPfclose(file);
586 
587  if( error )
588  retcode = SCIP_INVALIDDATA;
589 
590  return retcode;
591 }
592 
593 /** compare two tree profile statistics for equality */
594 static
596  TREEPROFILESTATS* stats, /**< first tree profile statistics */
597  TREEPROFILESTATS* other /**< other tree profile statistics */
598  )
599 {
600  assert(stats != NULL);
601  assert(other != NULL);
602 
603  return stats->maxdepth == other->maxdepth &&
604  stats->lastfulldepth == other->lastfulldepth &&
605  stats->minwaistdepth == other->minwaistdepth &&
606  stats->maxwaistdepth == other->maxwaistdepth;
607 }
608 
609 /** copy source tree profile into destination */
610 static
612  TREEPROFILESTATS* dest, /**< destination tree profile statistics */
613  TREEPROFILESTATS* src /**< source tree profile statistics */
614  )
615 {
616  assert(dest != NULL);
617  assert(src != NULL);
618 
619  dest->maxdepth = src->maxdepth;
620  dest->lastfulldepth = src->lastfulldepth;
621  dest->minwaistdepth = src->minwaistdepth;
622  dest->maxwaistdepth = src->maxwaistdepth;
623 }
624 
625 /** reset tree profile statistics */
626 static
628  TREEPROFILESTATS* treeprofilestats /**< tree profile statistics */
629  )
630 {
631  assert(treeprofilestats != NULL);
632 
633  BMSclearMemory(treeprofilestats);
634 }
635 
636 
637 /** extend tree profile to deeper tree */
638 static
640  SCIP* scip, /**< SCIP data structure */
641  TREEPROFILE* treeprofile, /**< tree profile data structure */
642  int mindepth /**< minimum depth that the tree profile should hold */
643  )
644 {
645  if( mindepth < treeprofile->profilesize )
646  return SCIP_OKAY;
647 
648  if( treeprofile->profile == NULL )
649  {
650  SCIP_CALL( SCIPallocClearMemoryArray(scip, &treeprofile->profile, mindepth) );
651  treeprofile->profilesize = mindepth;
652  }
653  else
654  {
655  int newsize;
656  int nnewelems;
657  SCIP_Longint* newprofile;
658 
659  newsize = SCIPcalcMemGrowSize(scip, mindepth + 1);
660  nnewelems = newsize - treeprofile->profilesize;
661  assert(newsize > treeprofile->profilesize);
662 
663  SCIP_CALL( SCIPreallocMemoryArray(scip, &treeprofile->profile, newsize) );
664  newprofile = &treeprofile->profile[treeprofile->profilesize];
665  BMSclearMemoryArray(newprofile, nnewelems);
666  treeprofile->profilesize = newsize;
667  }
668 
669  return SCIP_OKAY;
670 }
671 
672 /** create a tree profile */
673 static
675  SCIP* scip, /**< SCIP data structure */
676  TREEPROFILE** treeprofile /**< pointer to store tree profile data structure */
677  )
678 {
679  assert(scip != NULL);
680  assert(treeprofile != NULL);
681 
682  SCIP_CALL( SCIPallocMemory(scip, treeprofile) );
683 
684  (*treeprofile)->profile = NULL;
685  (*treeprofile)->profilesize = 0;
686  SCIP_CALL( extendMemoryTreeProfile(scip, *treeprofile, TREEPROFILE_MINSIZE) );
687 
688  resetTreeProfileStats(&(*treeprofile)->stats);
689  resetTreeProfileStats(&(*treeprofile)->lastestimatestats);
690 
691  (*treeprofile)->lastestimate = -1.0;
692 
693  return SCIP_OKAY;
694 }
695 
696 /** free a tree profile */
697 static
698 void freeTreeProfile(
699  SCIP* scip, /**< SCIP data structure */
700  TREEPROFILE** treeprofile /**< pointer to tree profile data structure */
701  )
702 {
703  assert(scip != NULL);
704  assert(treeprofile != NULL);
705 
706  if( *treeprofile == NULL )
707  return;
708 
709  SCIPfreeMemoryArray(scip, &(*treeprofile)->profile);
710 
711  SCIPfreeMemory(scip, treeprofile);
712 
713  *treeprofile = NULL;
714 }
715 
716 /** update tree profile */
717 static
719  SCIP* scip, /**< SCIP data structure */
720  TREEPROFILE* treeprofile, /**< tree profile data structure */
721  SCIP_NODE* node /**< node that should be added to the profile */
722  )
723 {
724  int nodedepth;
725  SCIP_Longint nodedepthcnt;
726  SCIP_Longint maxnodes;
727 
728  assert(scip != NULL);
729  assert(node != NULL);
730 
731  if( treeprofile == NULL )
732  return SCIP_OKAY;
733 
734  nodedepth = SCIPnodeGetDepth(node);
735  assert(nodedepth >= 0);
736  maxnodes = treeprofile->profile[treeprofile->stats.minwaistdepth];
737  assert(treeprofile->stats.minwaistdepth == treeprofile->stats.maxwaistdepth ||
738  maxnodes == treeprofile->profile[treeprofile->stats.maxwaistdepth]);
739 
740  /* ensure that the memory can hold at least this depth */
741  SCIP_CALL( extendMemoryTreeProfile(scip, treeprofile, nodedepth) );
742 
743  nodedepthcnt = ++treeprofile->profile[nodedepth];
744 
745  /* Is this level fully explored? We assume binary branching. The first condition ensures that the bit shift operation
746  * of the second condition represents a feasible power of unsigned int. The largest power of 2 representable
747  * by unsigned int is 2^{8*sizeof(unsigned int) - 1}. */
748  /* coverity[overflow_before_widen] */
749  if( (unsigned int)nodedepth < 8*sizeof(unsigned int) && nodedepthcnt == (1U << nodedepth) )/*lint !e647*/
750  {
751  SCIPdebugMsg(scip, "Level %d fully explored: %" SCIP_LONGINT_FORMAT " nodes\n", nodedepth, nodedepthcnt);
752 
753  treeprofile->stats.lastfulldepth = nodedepth;
754  }
755 
756  /* update maximum depth */
757  if( treeprofile->stats.maxdepth < nodedepth )
758  {
759  treeprofile->stats.maxdepth = nodedepth;
760  SCIPdebugMsg(scip, "Maximum depth increased to %d\n", treeprofile->stats.maxdepth);
761  }
762 
763  /* minimum and maximum waist now coincide */
764  if( nodedepthcnt > maxnodes )
765  {
766  treeprofile->stats.minwaistdepth = treeprofile->stats.maxwaistdepth = nodedepth;
767  SCIPdebugMsg(scip, "Updating depth of tree waist: %d (%" SCIP_LONGINT_FORMAT " nodes)\n",
768  treeprofile->stats.minwaistdepth, nodedepthcnt);
769  }
770  else if( nodedepthcnt == maxnodes )
771  {
772  /* enlarge the interval in which the waist lies */
773  if( treeprofile->stats.minwaistdepth > nodedepth )
774  treeprofile->stats.minwaistdepth = nodedepth;
775  else if( treeprofile->stats.maxwaistdepth < nodedepth )
776  treeprofile->stats.maxwaistdepth = nodedepth;
777  }
778  assert(treeprofile->stats.minwaistdepth <= treeprofile->stats.maxwaistdepth);
779 
780  return SCIP_OKAY;
781 }
782 
783 /** make a prediction of the total tree size based on the current tree profile */
784 static
786  SCIP* scip, /**< SCIP data structure */
787  TREEPROFILE* treeprofile, /**< tree profile data structure */
788  SCIP_Real minnodesperdepth /**< minimum number of average nodes per depth to make a prediction */
789  )
790 {
791  SCIP_Real estimate;
792  SCIP_Real growthfac;
793  int d;
794  int waist;
795 
796  /* prediction is disabled */
797  if( treeprofile == NULL )
798  return -1.0;
799 
800  /* two few nodes to make a prediction */
801  if( minnodesperdepth * treeprofile->stats.maxdepth > SCIPgetNNodes(scip) )
802  return -1.0;
803 
804  /* reuse previous estimation if tree profile hasn't changed */
805  if( isEqualTreeProfileStats(&treeprofile->lastestimatestats, &treeprofile->stats) )
806  {
807  SCIPdebugMsg(scip, "Reusing previous estimation result %g\n", treeprofile->lastestimate);
808 
809  return treeprofile->lastestimate;
810  }
811 
812  /* compute the (depth of the) waist as convex combination between the minimum and maximum waist depths */
813  waist = (2 * treeprofile->stats.maxwaistdepth + treeprofile->stats.minwaistdepth) / 3;
814 
815  growthfac = 2;
816  estimate = 1;
817 
818  /* loop over all full levels */
819  for( d = 1; d < treeprofile->stats.lastfulldepth; ++d )
820  {
821  SCIP_Real gamma_d = 2.0;
822 
823  estimate += growthfac;
824  growthfac *= gamma_d;
825  }
826 
827  /* loop until the waist is reached */
828  for( ; d < waist; ++d )
829  {
830  SCIP_Real gamma_d = 2.0 - (d - treeprofile->stats.lastfulldepth + 1.0)/(waist - treeprofile->stats.lastfulldepth + 1.0);
831 
832  assert(1.0 <= gamma_d && gamma_d <= 2.0);
833  estimate += growthfac;
834  growthfac *= gamma_d;
835  }
836 
837  /* loop over the remaining levels */
838  for( ; d <= treeprofile->stats.maxdepth; ++d )
839  {
840  SCIP_Real gamma_d = (1.0 - (d - waist + 1.0)/(treeprofile->stats.maxdepth - waist + 1.0));
841  assert(0.0 <= gamma_d && gamma_d <= 1.0);
842 
843  estimate += growthfac;
844  growthfac *= gamma_d;
845  }
846 
847  /* copy tree profile statistics */
848  copyTreeProfileStats(&treeprofile->lastestimatestats, &treeprofile->stats);
849 
850  treeprofile->lastestimate = estimate;
851 
852  return estimate;
853 }
854 
855 /** clean subtrees stored as priority queues */
856 static
858  SCIP* scip, /**< SCIP data structure */
859  SUBTREESUMGAP* ssg /**< subtree sum gap data structure */
860  )
861 {
862  assert(ssg->nsubtrees <= 1 || ssg->subtreepqueues != NULL);
863 
864  /* free all previous priority queues */
865  if( ssg->nsubtrees > 1 )
866  {
867  int s;
868 
869  for( s = 0; s < ssg->nsubtrees; ++s )
870  {
871  int i;
872  SCIP_PQUEUE* pqueue = ssg->subtreepqueues[s];
873  NODEINFO** nodeinfos;
874 
875  assert(pqueue != NULL);
876  nodeinfos = (NODEINFO**)SCIPpqueueElems(pqueue);
877 
878  /* free all remaining elements in reverse order */
879  for( i = SCIPpqueueNElems(pqueue); --i >= 0; )
880  {
881  NODEINFO* nodeinfo = nodeinfos[i];
882  assert(nodeinfo != NULL);
883  SCIPfreeBlockMemory(scip, &nodeinfo);
884  }
885 
886  SCIPpqueueFree(&pqueue);
887  }
888 
890  }
891 
892  ssg->subtreepqueues = NULL;
893 }
894 
895 /** reset subtree sum gap */
896 static
898  SCIP* scip, /**< SCIP data structure */
899  SUBTREESUMGAP* ssg /**< subtree sum gap data structure */
900  )
901 {
902  assert(ssg != NULL);
903  assert(ssg->nodes2info != NULL);
904 
906 
907  subtreeSumGapDelSubtrees(scip, ssg);
908 
909  ssg->value = 1.0;
910  ssg->scalingfactor = 1.0;
911  ssg->nsubtrees = 1;
912  ssg->subtreepqueues = NULL;
914  ssg->nodelastsplit = -1L;
915 
916  return SCIP_OKAY;
917 }
918 
919 /** create a subtree sum gap */
920 static
922  SCIP* scip, /**< SCIP data structure */
923  SUBTREESUMGAP** ssg /**< pointer to store subtree sum gap data structure */
924  )
925 {
926  assert(scip != NULL);
927  assert(ssg != NULL);
928 
929  /* allocate storage */
930  SCIP_CALL( SCIPallocMemory(scip, ssg) );
931  SCIP_CALL( SCIPhashmapCreate(&(*ssg)->nodes2info, SCIPblkmem(scip), INITIALSIZE) );
932 
933  /* explicitly set this to skip removal of subtrees during reset */
934  (*ssg)->nsubtrees = 0;
935 
936  /* reset ssg */
937  SCIP_CALL( subtreeSumGapReset(scip, *ssg) );
938 
939  return SCIP_OKAY;
940 }
941 
942 /** free a subtree sum gap */
943 static
944 void subtreeSumGapFree(
945  SCIP* scip, /**< SCIP data structure */
946  SUBTREESUMGAP** ssg /**< pointer to store subtree sum gap data structure */
947  )
948 {
949  assert(scip != NULL);
950 
951  if( *ssg == NULL )
952  return;
953 
954  if( (*ssg)->nodes2info != NULL )
955  {
956  SCIPhashmapFree(&(*ssg)->nodes2info);
957  }
958 
959  /* delete all subtree data */
960  subtreeSumGapDelSubtrees(scip, *ssg);
961 
962  SCIPfreeMemory(scip, ssg);
963 }
964 
965 /** compare two node infos by comparing their lower bound */
966 static
967 SCIP_DECL_SORTPTRCOMP(compareNodeInfos)
968 {
969  NODEINFO* nodeinfo1 = (NODEINFO*)elem1;
970  NODEINFO* nodeinfo2 = (NODEINFO*)elem2;
972  if( nodeinfo1->lowerbound < nodeinfo2->lowerbound )
973  return -1;
974  else if( nodeinfo1->lowerbound > nodeinfo2->lowerbound )
975  return 1;
976 
977  return 0;
978 }
979 
980 /** position change callback of element in priority queue */
981 static
982 SCIP_DECL_PQUEUEELEMCHGPOS(elemChgPosNodeInfo)
983 {
984  NODEINFO* nodeinfo = (NODEINFO*)elem;
985 
986  assert(oldpos == -1 || oldpos == nodeinfo->pos);
987  nodeinfo->pos = newpos;
988 }
989 
990 /** store node in SSG data structure */
991 static
993  SCIP* scip, /**< SCIP data structure */
994  SUBTREESUMGAP* ssg, /**< subtree sum gap data structure */
995  SCIP_NODE* node, /**< node that should be stored */
996  int subtreeidx /**< subtree index of that node */
997  )
998 {
999  NODEINFO* nodeinfo;
1000 
1001  assert(scip != NULL);
1002  assert(ssg != NULL);
1003  assert(node != NULL);
1004 
1005  /* create a new node info */
1006  SCIP_CALL( SCIPallocBlockMemory(scip, &nodeinfo) );
1007 
1008  /* store node information in data structure and insert into priority queue */
1009  nodeinfo->node = node;
1010  nodeinfo->subtreeidx = subtreeidx;
1011  nodeinfo->pos = -1;
1012  nodeinfo->lowerbound = SCIPnodeGetLowerbound(node);
1013 
1014  SCIPdebugMsg(scip, "Inserting label %d for node number %" SCIP_LONGINT_FORMAT " (%p)\n",
1015  subtreeidx, SCIPnodeGetNumber(node), (void*)node);
1016 
1017  assert(!SCIPhashmapExists(ssg->nodes2info, (void*)node));
1018  /* store node information in Hash Map */
1019  SCIP_CALL( SCIPhashmapInsert(ssg->nodes2info, (void*)node, (void*)nodeinfo) );
1020 
1021  /* create the corresponding priority queue, if it does not exist yet */
1022  assert(subtreeidx >= 0);
1023  assert(subtreeidx < ssg->nsubtrees);
1024 
1025  if( ssg->subtreepqueues[subtreeidx] == NULL )
1026  {
1027  SCIP_CALL( SCIPpqueueCreate(&ssg->subtreepqueues[subtreeidx], 5, 1.2, compareNodeInfos, elemChgPosNodeInfo) );
1028  }
1029 
1030  /* insert node and ensure that its position is up to date */
1031  SCIP_CALL( SCIPpqueueInsert(ssg->subtreepqueues[subtreeidx], (void*)nodeinfo) );
1032  assert(0 <= nodeinfo->pos);
1033  assert(SCIPpqueueNElems(ssg->subtreepqueues[subtreeidx]) > nodeinfo->pos);
1034  assert(SCIPpqueueElems(ssg->subtreepqueues[subtreeidx])[nodeinfo->pos] == (void*)nodeinfo);
1035 
1036  return SCIP_OKAY;
1037 }
1038 
1039 /** split the open nodes of the current tree */
1040 static
1042  SCIP* scip, /**< SCIP data structure */
1043  SUBTREESUMGAP* ssg, /**< subtree sum gap data structure */
1044  SCIP_Bool addfocusnode /**< should the focus node be a subtree, too? */
1045  )
1046 {
1047  SCIP_NODE** opennodes[3];
1048  int nopennodes[3];
1049  int label;
1050  int t;
1051  int nnewsubtrees;
1052 
1053  assert(scip != NULL);
1054  assert(ssg != NULL);
1055 
1056  /* query the open nodes of SCIP */
1057  SCIP_CALL( SCIPgetOpenNodesData(scip, &opennodes[0], &opennodes[1], &opennodes[2], &nopennodes[0], &nopennodes[1], &nopennodes[2]) );
1058 
1059  nnewsubtrees = nopennodes[0] + nopennodes[1] + nopennodes[2] + (addfocusnode ? 1 : 0);
1060 
1061  /* clear hash map from entries */
1063 
1064  /* delete all subtrees */
1065  subtreeSumGapDelSubtrees(scip, ssg);
1066 
1067  ssg->nsubtrees = nnewsubtrees;
1068  SCIPdebugMsg(scip, "Splitting tree into %d subtrees\n", ssg->nsubtrees);
1069 
1070  /* create priority queue array */
1071  if( ssg->nsubtrees > 1 )
1072  {
1074  }
1075  else
1076  {
1077  ssg->subtreepqueues = NULL;
1078 
1079  return SCIP_OKAY;
1080  }
1081 
1082  /* loop over node types (leaves, siblings, children) */
1083  label = 0;
1084  for( t = 0; t < 3; ++t )
1085  {
1086  SCIP_NODE** nodes = opennodes[t];
1087  int nnodes = nopennodes[t];
1088  int n;
1089 
1090  /* label each open node as new, separate subtree */
1091  for( n = 0; n < nnodes; ++n )
1092  {
1093  SCIP_NODE* node = nodes[n];
1094  SCIP_CALL( subtreeSumGapStoreNode(scip, ssg, node, label++) );
1095  }
1096  }
1097 
1098  if( addfocusnode )
1099  {
1100  assert(SCIPgetFocusNode(scip) != NULL);
1101  SCIP_CALL( subtreeSumGapStoreNode(scip, ssg, SCIPgetFocusNode(scip), label) );
1102  }
1103 
1104  return SCIP_OKAY;
1105 }
1106 
1107 /** compute a gap between a lower bound and the current upper bound */
1108 static
1110  SCIP* scip, /**< SCIP data structure */
1111  SCIP_Real lowerbound /**< lower bound value */
1112  )
1114  SCIP_Real db;
1115  SCIP_Real pb;
1116  SCIP_Real abspb;
1117  SCIP_Real absdb;
1118  SCIP_Real gap;
1119 
1120  if( SCIPisInfinity(scip, lowerbound) || lowerbound >= SCIPgetUpperbound(scip) )
1121  return 0.0;
1122 
1123  if( SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
1124  return 1.0;
1125 
1126  db = SCIPretransformObj(scip, lowerbound);
1127  pb = SCIPgetPrimalbound(scip);
1128 
1129  if( SCIPisEQ(scip, db, pb) )
1130  return 0.0;
1131 
1132  abspb = REALABS(pb);
1133  absdb = REALABS(db);
1134  gap = REALABS(pb - db)/MAX(abspb,absdb);
1135  gap = MIN(gap, 1.0);
1136 
1137  return gap;
1138 }
1139 
1140 /** remove node from the subtree sum gap (because it has been solved by branching or is a leaf) */
1141 static
1143  SCIP* scip, /**< SCIP data structure */
1144  SUBTREESUMGAP* ssg, /**< subtree sum gap data structure */
1145  SCIP_NODE* node /**< node that should be removed */
1146  )
1147 {
1148  NODEINFO* nodeinfo;
1149  int subtreeidx;
1150  int pos;
1151  SCIP_PQUEUE* pqueue;
1152 
1153  if( ssg->nsubtrees <= 1 )
1154  return SCIP_OKAY;
1155 
1156  nodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void*)node);
1157 
1158  /* it can happen that the node was not created via branching; search for the most recent ancestor in the queue */
1159  if( nodeinfo == NULL )
1160  {
1161  do
1162  {
1163  node = SCIPnodeGetParent(node);
1164  } while( node != NULL && (nodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void*)node)) == NULL);
1165 
1166  /* no ancestor found */
1167  if( nodeinfo == NULL )
1168  return SCIP_OKAY;
1169  }
1170 
1171  /* get open nodes of this subtree stored as priority queue */
1172  subtreeidx = nodeinfo->subtreeidx;
1173  pqueue = ssg->subtreepqueues[subtreeidx];
1174  assert(pqueue != NULL);
1175 
1176  /* delete the element from the priority queue */
1177  pos = nodeinfo->pos;
1178  assert(pos >= 0);
1179  assert(pos < SCIPpqueueNElems(pqueue));
1180  assert(SCIPpqueueElems(pqueue)[pos] == (void *)nodeinfo);
1181  SCIPpqueueDelPos(pqueue, pos);
1182 
1183  /* update ssg if removed node was the lower bound defining node of its subtree */
1184  if( pos == 0 )
1185  {
1186  NODEINFO* nodeinfofirst;
1187  SCIP_Real oldgap;
1188  SCIP_Real newgap;
1189 
1190  oldgap = calcGap(scip, nodeinfo->lowerbound);
1191  nodeinfofirst = (NODEINFO*)SCIPpqueueFirst(ssg->subtreepqueues[subtreeidx]);
1192  assert(nodeinfofirst == NULL || subtreeidx == nodeinfofirst->subtreeidx);
1193  newgap = calcGap(scip, nodeinfofirst != NULL ? nodeinfofirst->lowerbound : SCIPinfinity(scip) );
1194 
1195  assert(SCIPisLE(scip, newgap, oldgap));
1196 
1197  /* the SSG value is always up-to-date because it is recomputed when the primal bound changes */
1198  ssg->value += ssg->scalingfactor * MIN(newgap - oldgap, 0.0);
1199  }
1200 
1201  SCIP_CALL( SCIPhashmapRemove(ssg->nodes2info, (void*)node) );
1202 
1203  SCIPdebugMsg(scip, "Removed node %" SCIP_LONGINT_FORMAT " from open nodes of SSG\n",
1204  SCIPnodeGetNumber(node));
1205 
1206  SCIPfreeBlockMemory(scip, &nodeinfo);
1207 
1208  return SCIP_OKAY;
1209 }
1210 
1211 /** insert children into subtree sum gap */
1212 static
1214  SCIP* scip, /**< SCIP data structure */
1215  SUBTREESUMGAP* ssg /**< subtree sum gap data structure */
1216  )
1218  int nchildren;
1219  SCIP_NODE** children;
1220  SCIP_NODE* focusnode;
1221  SCIP_NODE* parentnode;
1222  NODEINFO* parentnodeinfo;
1223  int parentnodelabel;
1224  int n;
1225 
1226  assert(scip != NULL);
1227  assert(ssg != NULL);
1228 
1229  if( ssg->nsubtrees == 1 )
1230  return SCIP_OKAY;
1231 
1232  SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
1233 
1234  if( nchildren == 0 )
1235  return SCIP_OKAY;
1236 
1237  focusnode = SCIPgetFocusNode(scip);
1238 
1239  /* a rare case: the search has been stopped at some point, and the current focus node is the only descendant
1240  * of its parent node
1241  */
1242  if( !SCIPhashmapExists(ssg->nodes2info, (void*)focusnode) )
1243  {
1244  parentnode = focusnode;
1245  do
1246  {
1247  parentnode = SCIPnodeGetParent(parentnode);
1248  } while( parentnode != NULL && !SCIPhashmapExists(ssg->nodes2info, (void *)parentnode));
1249 
1250  assert(parentnode != NULL && SCIPhashmapExists(ssg->nodes2info, (void *)parentnode));
1251  }
1252  else
1253  parentnode = focusnode;
1254 
1255  parentnodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void *)parentnode);
1256  parentnodelabel = parentnodeinfo->subtreeidx;
1257 
1258  /* loop over children and insert the focus node label */
1259  for( n = 0; n < nchildren; ++n )
1260  {
1261  assert(SCIPnodeGetParent(children[n]) == focusnode);
1262 
1263  SCIPdebugMsg(scip,
1264  "Inserting label %d for node number %" SCIP_LONGINT_FORMAT " (parent %" SCIP_LONGINT_FORMAT ")\n",
1265  parentnodelabel, SCIPnodeGetNumber(children[n]), SCIPnodeGetNumber(parentnode));
1266 
1267  SCIP_CALL( subtreeSumGapStoreNode(scip, ssg, children[n], parentnodelabel) );
1268  }
1269 
1270  /* remove focus node from hash map */
1271  SCIP_CALL( subtreeSumGapRemoveNode(scip, ssg, parentnode) );
1272 
1273  return SCIP_OKAY;
1274 }
1275 
1276 /* this function is inefficient because it loops over all open nodes, but can be used for debugging */
1277 #ifdef SCIP_DISABLED_CODE
1278 /** compute subtree sum gap from scratch (inefficiently because loop over all open nodes) */
1279 static
1280 SCIP_RETCODE subtreesumgapComputeFromScratch(
1281  SCIP* scip, /**< SCIP data structure */
1282  SUBTREESUMGAP* ssg, /**< subtree sum gap data structure */
1283  SCIP_Bool updatescaling /**< should the scaling factor be updated? */
1284  )
1285 {
1286  SCIP_Real* lowerbounds;
1287  SCIP_NODE** opennodes[3];
1288  SCIP_Real gapsum = 0;
1289  SCIP_Real pb;
1290  int nopennodes[3];
1291  int l;
1292  int t;
1293 
1294  /* treat trivial cases: only 1 subtree, no incumbent solution */
1295  if( SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
1296  {
1297  ssg->value = 1.0;
1298 
1299  return SCIP_OKAY;
1300  }
1301 
1302  /* simply use normal gap in trivial case */
1303  if( ssg->nsubtrees == 1 )
1304  {
1305  ssg->value = calcGap(scip, SCIPgetLowerbound(scip));
1306 
1307  return SCIP_OKAY;
1308  }
1309 
1310  /* allocate temporary memory to store lower bound for every subtree */
1311  SCIP_CALL( SCIPallocBufferArray(scip, &lowerbounds, ssg->nsubtrees) );
1312 
1313  /* initialize lower bounds as SCIPinfinity(scip) */
1314  for( l = 0; l < ssg->nsubtrees; ++l )
1315  lowerbounds[l] = SCIPinfinity(scip);
1316 
1317  /* loop over children, siblings, and leaves to update subtree lower bounds */
1318  SCIP_CALL( SCIPgetOpenNodesData(scip, &opennodes[0], &opennodes[1], &opennodes[2], &nopennodes[0], &nopennodes[1], &nopennodes[2]) );
1319 
1320  /* loop over the three types leaves, siblings, leaves */
1321  for( t = 0; t < 3; ++t )
1322  {
1323  int n;
1324  /* loop over nodes of this type */
1325  for( n = 0; n < nopennodes[t]; ++n )
1326  {
1327  SCIP_NODE* node = opennodes[t][n];
1328  NODEINFO* nodeinfo;
1329  SCIP_Real lowerbound;
1330  int label;
1331  nodeinfo = (NODEINFO*)SCIPhashmapGetImage(ssg->nodes2info, (void *)node);
1332  label = nodeinfo->subtreeidx;
1333  lowerbound = nodeinfo->lowerbound;
1334 
1335  assert(label >= 0 && label < ssg->nsubtrees);
1336  lowerbounds[label] = MIN(lowerbounds[label], lowerbound);
1337  }
1338  }
1339 
1340  /* compute subtree gaps in original space; sum them up */
1341  pb = SCIPgetPrimalbound(scip);
1342  for( l = 0; l < ssg->nsubtrees; ++l )
1343  {
1344  SCIP_Real subtreedualbound;
1345  SCIP_Real subtreegap;
1346  /* skip subtrees with infinite lower bound; they are empty and contribute 0.0 to the gap sum term */
1347  if( SCIPisInfinity(scip, lowerbounds[l]) )
1348  continue;
1349 
1350  subtreedualbound = SCIPretransformObj(scip, lowerbounds[l]);
1351 
1352  if( SCIPisEQ(scip, subtreedualbound, pb) )
1353  continue;
1354 
1355  subtreegap = REALABS(pb - subtreedualbound)/MAX(REALABS(pb),REALABS(subtreedualbound));
1356  subtreegap = MIN(subtreegap, 1.0);
1357 
1358  gapsum += subtreegap;
1359  }
1360 
1361  /* update the scaling factor by using the previous SSG value divided by the current gapsum */
1362  if( updatescaling )
1363  {
1364  ssg->scalingfactor = ssg->value / MAX(gapsum, 1e-6);
1365  }
1366 
1367  /* update and store SSG value by considering scaling factor */
1368  ssg->value = ssg->scalingfactor * gapsum;
1369 
1370  SCIPfreeBufferArray(scip, &lowerbounds);
1371 
1372  return SCIP_OKAY;
1373 }
1374 #endif
1375 
1376 /** compute subtree sum gap from scratch efficiently (linear effort in the number of subtrees) */
1377 static
1379  SCIP* scip, /**< SCIP data structure */
1380  SUBTREESUMGAP* ssg, /**< subtree sum gap data structure */
1381  SCIP_Bool updatescaling /**< should the scaling factor be updated? */
1382  )
1383 {
1384  SCIP_Real gapsum = 0.0;
1385  int l;
1386 
1387  /* treat trivial cases: only 1 subtree, no incumbent solution */
1388  if( SCIPisInfinity(scip, SCIPgetUpperbound(scip)) )
1389  {
1390  ssg->value = 1.0;
1391 
1392  return SCIP_OKAY;
1393  }
1394 
1395  if( ssg->nsubtrees == 1 )
1396  {
1397  ssg->value = calcGap(scip, SCIPgetLowerbound(scip));
1398 
1399  return SCIP_OKAY;
1400  }
1401 
1402  /* compute subtree gaps in original space; sum them up */
1403  for( l = 0; l < ssg->nsubtrees; ++l )
1404  {
1405  SCIP_Real subtreegap;
1406  NODEINFO* nodeinfo;
1407 
1408  assert(ssg->subtreepqueues[l] != NULL);
1409 
1410  nodeinfo = (NODEINFO*)SCIPpqueueFirst(ssg->subtreepqueues[l]);
1411 
1412  /* skip subtrees with infinite lower bound; they are empty and contribute 0.0 to the gap sum term */
1413  if( nodeinfo == NULL || SCIPisInfinity(scip, nodeinfo->lowerbound) )
1414  continue;
1415 
1416  subtreegap = calcGap(scip, nodeinfo->lowerbound);
1417 
1418  gapsum += subtreegap;
1419  }
1420 
1421  /* update the scaling factor by using the previous SSG value divided by the current gapsum */
1422  if( updatescaling )
1423  {
1424  ssg->scalingfactor = ssg->value / MAX(gapsum, 1e-6);
1425  }
1426 
1427  /* update and store SSG value by considering scaling factor */
1428  ssg->value = ssg->scalingfactor * gapsum;
1429 
1430  return SCIP_OKAY;
1431 }
1432 
1433 /** update the subtree sum gap after a node event (branching or deletion of a node) */
1434 static
1436  SCIP* scip, /**< SCIP data structure */
1437  SUBTREESUMGAP* ssg, /**< subtree sum gap data structure */
1438  SCIP_NODE* node, /**< the corresponding node */
1439  int nchildren, /**< number of children */
1440  SCIP_Longint nsolvednodes /**< number of solved nodes so far, used as a time stamp */
1441  )
1442 {
1443  SCIP_Bool updatescaling = FALSE;
1444  SCIP_Bool insertchildren = (ssg->nsubtrees > 1 && nchildren > 0);
1445 
1446  /* if the instance is solved or a node is cutoff at the initsolve stage or we are unbounded, the ssg is 0 */
1448  {
1449  ssg->value = 0.0;
1450 
1451  return SCIP_OKAY;
1452  }
1453 
1454  /* make a new tree split if the primal bound has changed. */
1455  if( ! SCIPisInfinity(scip, SCIPgetUpperbound(scip)) && ! SCIPisEQ(scip, SCIPgetPrimalbound(scip), ssg->pblastsplit) )
1456  {
1457  int nnewsubtrees;
1458  SCIP_Bool addfocusnode;
1459 
1460  addfocusnode = SCIPgetFocusNode(scip) != NULL && SCIPgetNChildren(scip) == 0 && !SCIPwasNodeLastBranchParent(scip, SCIPgetFocusNode(scip));
1461  nnewsubtrees = SCIPgetNSiblings(scip) + SCIPgetNLeaves(scip) + SCIPgetNChildren(scip) + (addfocusnode ? 1 : 0);
1462 
1463  /* check if number of new subtrees does not exceed maximum number of subtrees; always split if no split happened, yet */
1464  if( ssg->nsubtrees <= 1 ||
1465  ((ssg->nmaxsubtrees == -1 || nnewsubtrees <= ssg->nmaxsubtrees) &&
1466  (nsolvednodes - ssg->nodelastsplit >= ssg->nminnodeslastsplit)) )
1467  {
1468  SCIP_CALL( subtreeSumGapSplit(scip, ssg, addfocusnode) );
1469 
1470  /* remember time stamp */
1471  ssg->nodelastsplit = nsolvednodes;
1472  }
1473  else
1474  {
1475  if( ssg->nmaxsubtrees != -1 && nnewsubtrees >= ssg->nmaxsubtrees )
1476  {
1477  SCIPdebugMsg(scip, "Keep split into %d subtrees because new split into %d subtrees exceeds limit %d\n",
1478  ssg->nsubtrees, nnewsubtrees, ssg->nmaxsubtrees);
1479  }
1480  else
1481  {
1482  SCIPdebugMsg(scip, "Keep split into %d subtrees from %" SCIP_LONGINT_FORMAT " nodes ago\n",
1483  ssg->nsubtrees, nsolvednodes - ssg->nodelastsplit);
1484  }
1485 
1486  /* no new split has happened; insert the new children to their SSG subtree */
1487  if( insertchildren )
1488  {
1489  SCIP_CALL( subtreeSumGapInsertChildren(scip, ssg) );
1490  }
1491  }
1492 
1493  ssg->pblastsplit = SCIPgetPrimalbound(scip);
1494 
1495  updatescaling = TRUE;
1496 
1497  /* compute the current SSG value from scratch */
1498  SCIP_CALL( subtreeSumGapComputeFromScratchEfficiently(scip, ssg, updatescaling) );
1499  }
1500  /* otherwise, if new children have been created, label them */
1501  else if( insertchildren )
1502  {
1503  SCIP_CALL( subtreeSumGapInsertChildren(scip, ssg) );
1504  }
1505 
1506  /* remove the node from the hash map if it is a leaf */
1507  if( nchildren == 0 )
1508  {
1509  SCIP_CALL( subtreeSumGapRemoveNode(scip, ssg, node) );
1510  }
1511 
1512  return SCIP_OKAY;
1513 }
1514 
1515 /** reset tree data */
1516 static
1518  SCIP* scip, /**< SCIP data structure */
1519  TREEDATA* treedata /**< tree data */
1520  )
1522  /* simply set everything to 0 */
1523  treedata->ninner = treedata->nleaves = treedata->nvisited = 0L;
1524  treedata->weight = 0.0;
1525 
1526  /* set up root node */
1527  treedata->nnodes = 1;
1528  treedata->nopen = 1;
1529 
1530  SCIP_CALL( subtreeSumGapReset(scip, treedata->ssg) );
1531 
1532  return SCIP_OKAY;
1533 }
1534 
1535 /** create tree data structure */
1536 static
1538  SCIP* scip, /**< SCIP data structure */
1539  TREEDATA** treedata /**< pointer to store tree data */
1540  )
1542  assert(treedata != NULL);
1543  assert(scip != NULL);
1544 
1545  SCIP_CALL( SCIPallocMemory(scip, treedata) );
1546 
1547  SCIP_CALL( subtreeSumGapCreate(scip, &(*treedata)->ssg) );
1548 
1549  SCIP_CALL( resetTreeData(scip, *treedata) );
1550 
1551  return SCIP_OKAY;
1552 }
1553 
1554 /** free tree data structure */
1555 static
1556 void freeTreeData(
1557  SCIP* scip, /**< SCIP data structure */
1558  TREEDATA** treedata /**< pointer to tree data */
1559  )
1561  assert(scip != NULL);
1562 
1563  if( *treedata == NULL )
1564  return;
1565 
1566  subtreeSumGapFree(scip, &(*treedata)->ssg);
1567 
1568  SCIPfreeMemory(scip, treedata);
1569  *treedata = NULL;
1570 }
1571 
1572 /** update tree data structure after a node has been solved/is about to be deleted */
1573 static
1575  SCIP* scip, /**< SCIP data structure */
1576  TREEDATA* treedata, /**< tree data */
1577  SCIP_NODE* node, /**< the corresponding node */
1578  int nchildren /**< the number of children */
1579  )
1580 {
1581  assert(node != NULL);
1582 
1583  ++treedata->nvisited;
1584  treedata->nopen--;
1585 
1586  if( nchildren == 0 )
1587  {
1588  int depth = SCIPnodeGetDepth(node);
1589  treedata->nleaves++;
1590  treedata->weight += pow(0.5, (SCIP_Real)depth);
1591  }
1592  else
1593  {
1594  treedata->nnodes += nchildren;
1595  treedata->nopen += nchildren;
1596  ++treedata->ninner;
1597  }
1598 
1599  /* update the subtree sum gap */
1600  if( ! SCIPisInRestart(scip) )
1601  {
1602  SCIP_CALL( subtreeSumGapUpdate(scip, treedata->ssg, node, nchildren, treedata->nvisited) );
1603  }
1604 
1605  return SCIP_OKAY;
1606 }
1607 
1608 /** get weighted backtrack estimation from this tree data */
1609 static
1611  TREEDATA* treedata /**< tree data */
1612  )
1613 {
1614  if( treedata->weight <= 0.0 || treedata->nleaves == 0 )
1615  return -1.0;
1616 
1617  return 2.0 * treedata->nleaves / (SCIP_Real)treedata->weight - 1.0;
1618 }
1619 
1620 #ifdef SCIP_DEBUG
1621 /* print method for tree data */
1622 static
1623 char* treeDataPrint(
1624  TREEDATA* treedata, /**< tree data */
1625  char* strbuf /**< string buffer */
1626  )
1627 {
1628  (void )SCIPsnprintf(strbuf, SCIP_MAXSTRLEN,
1629  "Tree Data: %" SCIP_LONGINT_FORMAT " nodes ("
1630  "%" SCIP_LONGINT_FORMAT " visited, "
1631  "%" SCIP_LONGINT_FORMAT " inner, "
1632  "%" SCIP_LONGINT_FORMAT " leaves, "
1633  "%" SCIP_LONGINT_FORMAT " open), "
1634  "weight: %.4Lf, ssg %.4f",
1635  treedata->nnodes,
1636  treedata->nvisited,
1637  treedata->ninner,
1638  treedata->nleaves,
1639  treedata->nopen,
1640  treedata->weight,
1641  treedata->ssg->value
1642  );
1643  return strbuf;
1644 }
1645 #endif
1646 
1647 /** reset double exponential smoothing */
1648 static
1650  DOUBLEEXPSMOOTH* des, /**< double exponential smoothing data structure */
1651  SCIP_Real initialvalue /**< the initial value */
1652  )
1654  des->n = 0;
1655  des->level = SCIP_INVALID;
1656  des->trend = SCIP_INVALID;
1657  des->initialvalue = initialvalue;
1658 }
1659 
1660 /** initialize a double exponential smoothing data structure */
1661 static
1662 void doubleExpSmoothInit(
1663  DOUBLEEXPSMOOTH* des, /**< double exponential smoothing data structure */
1664  SCIP_Real x1 /**< the first sample value */
1665  )
1667  assert(des != NULL);
1668 
1669  des->n = 1;
1670  des->level = x1;
1671  des->trend = x1 - des->initialvalue;
1672 
1674 
1675  return;
1676 }
1677 
1678 /** update a double exponential smoothing data structure */
1679 static
1681  DOUBLEEXPSMOOTH* des, /**< double exponential smoothing data structure */
1682  SCIP_Real xnew /**< new sample value */
1683  )
1685  if( des->n == 0 )
1686  doubleExpSmoothInit(des, xnew);
1687  else
1688  {
1689  SCIP_Real newlevel;
1690  SCIP_Real newtrend;
1691 
1692  newlevel = des->alpha * xnew + (1.0 - des->alpha) * (des->level + des->usetrendinlevel ? des->trend : 0.0);
1693  newtrend = des->beta * (newlevel - des->level) + (1.0 - des->beta) * des->trend;
1694 
1695  des->level = newlevel;
1696  des->trend = newtrend;
1697  }
1698 }
1699 
1700 /** get the current trend (slope) computed by this double exponential smoothing */
1701 static
1703  DOUBLEEXPSMOOTH* des /**< double exponential smoothing data structure */
1704  )
1705 {
1706  assert(des != NULL);
1707 
1708  if( des->n == 0 )
1709  return SCIP_INVALID;
1710 
1711  return des->trend;
1712 }
1713 
1714 /** reset time series */
1715 static
1716 void timeSeriesReset(
1717  TIMESERIES* timeseries /**< pointer to store time series */
1718  )
1719 {
1720  timeseries->resolution = 1;
1721  timeseries->nvals = 0;
1722  timeseries->nobs = 0L;
1723  timeseries->currentvalue = timeseries->initialvalue;
1724  timeseries->smoothestimation = SCIP_INVALID;
1725 
1726  doubleExpSmoothReset(&timeseries->des, timeseries->initialvalue);
1727 }
1728 
1729 /** create a time series object */
1730 static
1732  SCIP* scip, /**< SCIP data structure */
1733  TIMESERIES** timeseries, /**< pointer to store time series */
1734  const char* name, /**< name of this time series */
1735  SCIP_Real targetvalue, /**< target value of this time series */
1736  SCIP_Real initialvalue, /**< the initial value of time series */
1737  SCIP_Real alpha, /**< alpha parameter (level weight) for double exponential smoothing */
1738  SCIP_Real beta, /**< beta parameter (level weight) for double exponential smoothing */
1739  DECL_TIMESERIESUPDATE ((*timeseriesupdate)) /**< update callback at nodes, or NULL */
1740  )
1741 {
1742  TIMESERIES* timeseriesptr;
1743  assert(scip != NULL);
1744  assert(timeseries != NULL);
1745  assert(name != NULL);
1746  assert(alpha >= 0.0 && alpha <= 1);
1747  assert(beta >= 0.0 && beta <= 1);
1748 
1749  SCIP_CALL( SCIPallocMemory(scip, timeseries) );
1750 
1751  timeseriesptr = *timeseries;
1752  assert(timeseriesptr != NULL);
1753 
1754  /* copy name */
1755  SCIP_ALLOC( BMSduplicateMemoryArray(&timeseriesptr->name, name, strlen(name)+1) );
1756 
1757  /* copy callbacks */
1758  assert(timeseriesupdate != NULL);
1759  timeseriesptr->timeseriesupdate = timeseriesupdate;
1760 
1761  timeseriesptr->targetvalue = targetvalue;
1762  timeseriesptr->valssize = 1024;
1763  timeseriesptr->initialvalue = initialvalue;
1764 
1765  SCIP_CALL( SCIPallocMemoryArray(scip, &timeseriesptr->vals, timeseriesptr->valssize) );
1766  SCIP_CALL( SCIPallocMemoryArray(scip, &timeseriesptr->estimation, timeseriesptr->valssize) );
1767 
1768  timeSeriesReset(timeseriesptr);
1769 
1770  timeseriesptr->des.alpha = alpha;
1771  timeseriesptr->des.beta = beta;
1772 
1773  SCIPdebugMsg(scip, "Finished creation of time series '%s'\n", timeseriesptr->name);
1774 
1775  return SCIP_OKAY;
1776 }
1777 
1778 /** free a time series */
1779 static
1780 void timeSeriesFree(
1781  SCIP* scip, /**< SCIP data structure */
1782  TIMESERIES** timeseries /**< pointer to time series */
1783  )
1785  assert(scip != NULL);
1786  assert(timeseries != NULL);
1787 
1788  BMSfreeMemoryArray(&(*timeseries)->name);
1789 
1790  SCIPfreeMemoryArray(scip, &(*timeseries)->vals);
1791  SCIPfreeMemoryArray(scip, &(*timeseries)->estimation);
1792 
1793  SCIPfreeMemory(scip, timeseries);
1794 
1795  *timeseries = NULL;
1796 }
1797 
1798 /** get current value of time series */
1799 static
1801  TIMESERIES* timeseries /**< time series */
1802  )
1803 {
1804  assert(timeseries != NULL);
1805 
1806  return timeseries->currentvalue;
1807 }
1808 
1809 /** get target value (which this time series reaches at the end of the solution process) */
1810 static
1812  TIMESERIES* timeseries /**< time series */
1813  )
1814 {
1815  return timeseries->targetvalue;
1816 }
1817 
1818 /** get resolution of time series */
1819 static
1821  TIMESERIES* timeseries /**< time series */
1822  )
1823 {
1824  return timeseries->resolution;
1825 }
1826 
1827 /** estimate tree size at which time series reaches target value */
1828 static
1830  TIMESERIES* timeseries, /**< time series */
1831  TREEDATA* treedata /**< tree data for fallback estimation */
1832  )
1834  SCIP_Real val;
1835  SCIP_Real targetval;
1836  SCIP_Real trend;
1837  SCIP_Real estimated;
1838  const SCIP_Real tolerance = 1e-6;
1839 
1840  /* if no observations have been made yet, return infinity */
1841  if( timeseries->nobs == 0L )
1842  return -1.0;
1843 
1844  val = timeSeriesGetValue(timeseries);
1845  targetval = timeSeriesGetTargetValue(timeseries);
1846 
1847  /* if the value has reached the target value already, return the number of observations */
1848  if( EPSZ(val - targetval, tolerance) )
1849  return treedata->nnodes;
1850 
1851  trend = doubleExpSmoothGetTrend(&timeseries->des);
1852 
1853  /* Get current value and trend. The linear trend estimation may point into the wrong direction
1854  * In this case, we use the fallback mechanism that we will need twice as many nodes.
1855  */
1856  if( (targetval > val && trend < tolerance) || (targetval < val && trend > -tolerance) )
1857  {
1858  return 2.0 * treedata->nvisited;
1859  }
1860 
1861  /* compute after how many additional steps the current trend reaches the target value; multiply by resolution */
1862  estimated = timeSeriesGetResolution(timeseries) * (timeseries->nvals + (targetval - val) / (SCIP_Real)trend);
1863  return timeseries->useleafts ? 2.0 * estimated - 1.0 : estimated;
1864 }
1865 
1866 /** update time series smoothened estimation */
1867 static
1869  TIMESERIES* timeseries, /**< time series */
1870  SCIP_Real estimation /**< estimation value */
1871  )
1873  if( timeseries->smoothestimation == SCIP_INVALID )/*lint !e777*/
1874  timeseries->smoothestimation = estimation;
1875  else
1876  {
1877  timeseries->smoothestimation *= (1.0 - SESCOEFF);
1878  timeseries->smoothestimation += SESCOEFF * estimation;
1879  }
1880 }
1881 
1882 /** get smooth estimation of time series */
1883 static
1885  TIMESERIES* timeseries /**< time series */
1886  )
1887 {
1888  return timeseries->smoothestimation;
1889 }
1890 
1891 /** resample to lower resolution */
1892 static
1893 void timeSeriesResample(
1894  TIMESERIES* timeseries /**< time series */
1895  )
1896 {
1898  int i;
1899 
1900  assert(timeseries->nvals % 2 == 0);
1901 
1902  des = &timeseries->des;
1903  doubleExpSmoothReset(des, timeseries->initialvalue);
1904 
1905  /* compress vals array to store only every second entry */
1906  for( i = 0; i < timeseries->nvals / 2; ++i )
1907  {
1908  timeseries->vals[i] = timeseries->vals[2 * i];
1909  timeseries->estimation[i] = timeseries->estimation[2 * i];
1910  doubleExpSmoothUpdate(des, timeseries->vals[i]);
1911  timeSeriesUpdateSmoothEstimation(timeseries, timeseries->estimation[i]);
1912  }
1913 
1914  timeseries->resolution *= 2;
1915  timeseries->nvals = timeseries->nvals / 2;
1916 }
1917 
1918 /** update time series */
1919 static
1921  SCIP* scip, /**< SCIP data structure */
1922  TIMESERIES* timeseries, /**< time series */
1923  TREEDATA* treedata, /**< tree data */
1924  SCIP_Bool isleaf /**< are we at a leaf node? */
1925  )
1926 {
1927  SCIP_Real value;
1928 
1929  assert(scip != NULL);
1930  assert(timeseries != NULL);
1931  assert(treedata != NULL);
1932 
1933  /* call update callback */
1934  assert(timeseries->timeseriesupdate != NULL);
1935  SCIP_CALL( timeseries->timeseriesupdate(scip, timeseries, treedata, &value) );
1936 
1937  /* store the value as current value */
1938  timeseries->currentvalue = value;
1939 
1940  if( timeseries->useleafts && ! isleaf )
1941  return SCIP_OKAY;
1942 
1943  timeseries->nobs++;
1944 
1945  /* if this is a leaf that matches the time series resolution, store the value */
1946  if( timeseries->nobs % timeseries->resolution == 0 )
1947  {
1948  int tspos;
1949  SCIP_Real estimate;
1950 
1951  assert(timeseries->nvals < timeseries->valssize);
1952  tspos = timeseries->nvals++;
1953  timeseries->vals[tspos] = value;
1954  doubleExpSmoothUpdate(&timeseries->des, value);
1955  estimate = timeSeriesEstimate(timeseries, treedata);
1956  timeseries->estimation[tspos] = estimate;
1957  timeSeriesUpdateSmoothEstimation(timeseries, estimate);
1958  }
1959 
1960  /* if the time series has reached its capacity, resample and increase the resolution */
1961  if( timeseries->nvals == timeseries->valssize )
1962  timeSeriesResample(timeseries);
1963 
1964  return SCIP_OKAY;
1965 }
1966 
1967 /** get name of time series */
1968 static
1969 char* timeSeriesGetName(
1970  TIMESERIES* timeseries /**< time series */
1971  )
1972 {
1973  return timeseries->name;
1974 }
1975 
1976 /** reset all time series */
1977 static
1978 void resetTimeSeries(
1979  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
1980  )
1981 {
1982  TIMESERIES** tss = eventhdlrdata->timeseries;
1983  int t;
1984 
1985  /* loop over time series and reset them */
1986  for( t = 0; t < NTIMESERIES; ++t )
1987  {
1988  assert(tss[t] != NULL);
1989  timeSeriesReset(tss[t]);
1990 
1991  tss[t]->useleafts = eventhdlrdata->useleafts;
1992  }
1993 }
1994 
1995 /*
1996  * Callback methods of event handler
1997  */
1998 
1999 /** free all time series */
2000 static
2001 void freeTimeSeries(
2002  SCIP* scip, /**< SCIP data structure */
2003  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2004  )
2006  TIMESERIES** tss = eventhdlrdata->timeseries;
2007  int t;
2008 
2009  /* loop over time series and reset them */
2010  for( t = 0; t < NTIMESERIES; ++t )
2011  {
2012  assert(tss[t] != NULL);
2013  timeSeriesFree(scip, &tss[t]);
2014  }
2015 }
2016 
2017 /** get ensemble tree size estimation as a combination of the individual time series estimations
2018  *
2019  * the coefficients have been computed based on a nonlinear fit on a broad set of publicly available
2020  * MIP instances; please refer to the publication at the top of this file for further details.
2021  */
2022 static
2024  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2025  )
2026 {
2027  TREEDATA* treedata;
2028  SCIP_Real* coeffs;
2029  SCIP_Real estim;
2030  int t;
2031 
2032  TSPOS tsposs[] = {
2033  TSPOS_GAP,
2035  TSPOS_LFREQ,
2036  TSPOS_SSG,
2037  TSPOS_OPEN
2038  };
2039 
2040  /* coefficients for the early stage (tree weight <= 0.3) */
2041  SCIP_Real coeffs_early[] = {
2042  0.002, /* gap */
2043  0.381, /* tree weight */
2044  0.469, /* leaf-frequency */
2045  0.292, /* SSG */
2046  0.004 /* open-nodes */
2047  };
2048 
2049  /* coefficients for the intermediate stage (0.3 < tree weight <= 0.6) */
2050  SCIP_Real coeffs_intermediate[] = {
2051  0.011, /* gap */
2052  0.193, /* tree weight */
2053  0.351, /* leaf-frequency */
2054  0.012, /* SSG */
2055  0.051 /* open-nodes */
2056  };
2057 
2058  /* coefficients for the late stage (tree weight > 0.6) */
2059  SCIP_Real coeffs_late[] = {
2060  0.000, /* gap */
2061  0.033, /* tree weight */
2062  0.282, /* leaf-frequency */
2063  0.003, /* SSG */
2064  0.024 /* open-nodes */
2065  };
2066 
2067  assert(eventhdlrdata != NULL);
2068  treedata = eventhdlrdata->treedata;
2069 
2070  /* assign coeffs based on stage */
2071  if( treedata->weight <= 0.3 )
2072  {
2073  estim = 0.0;
2074  coeffs = coeffs_early;
2075  /* ensure that coeffs and time series are still aligned */
2076  assert(sizeof(coeffs_early)/sizeof(SCIP_Real) == NTIMESERIES); /*lint !e506*/
2077  }
2078  else if( treedata->weight <= 0.6 )
2079  {
2080  coeffs = coeffs_intermediate;
2081  /* ensure that coeffs and time series are still aligned */
2082  assert(sizeof(coeffs_intermediate)/sizeof(SCIP_Real) == NTIMESERIES); /*lint !e506*/
2083 
2084  /* initialize by intermediate WBE coefficient */
2085  estim = 0.156 * treeDataGetWbe(treedata);
2086  }
2087  else
2088  {
2089  coeffs = coeffs_late;
2090  /* ensure that coeffs and time series are still aligned */
2091  assert(sizeof(coeffs_late)/sizeof(SCIP_Real) == NTIMESERIES); /*lint !e506*/
2092 
2093  /* initialize by late WBE coefficient */
2094  estim = 0.579 * treeDataGetWbe(treedata);
2095  }
2096 
2097  /* combine estimation using the stage-dependent coefficients */
2098  for( t = 0; t < NTIMESERIES; ++t )
2099  {
2100  SCIP_Real testim;
2101  TSPOS tspos = tsposs[t];
2102  testim = timeSeriesEstimate(eventhdlrdata->timeseries[tspos], treedata);
2103 
2104  if( testim < 0.0 )
2105  testim = treedata->nnodes;
2106 
2107  estim += coeffs[t] * testim;
2108  }
2109 
2110  if( estim < treedata->nnodes )
2111  return (SCIP_Real)treedata->nnodes;
2112  else
2113  return estim;
2114 }
2115 
2116 /** get approximation of search tree completion depending on the selected method */
2117 static
2119  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
2120  SCIP_Real* completed /**< pointer to store the search tree completion */
2121  )
2123  SCIP_Real values[9];
2124  TREEDATA* treedata;
2125  char completiontype;
2126 
2127  assert(eventhdlrdata != NULL);
2128  treedata = eventhdlrdata->treedata;
2129  completiontype = eventhdlrdata->completiontypeparam;
2130 
2131  /* infer automatic completion type
2132  *
2133  * use regression forest if available,
2134  * or
2135  * use monotone regression if both SSG and tree weight are meaningful;
2136  * or
2137  * use tree weight or SSG, depending which one is available,
2138  * or
2139  * use gap, which is always available
2140  */
2141  if( completiontype == COMPLETIONTYPE_AUTO )
2142  {
2143  SCIP_Bool useweight = eventhdlrdata->treeisbinary;
2144  SCIP_Bool usessg = treedata->ssg->pblastsplit != SSG_STARTPRIMBOUND;/*lint !e777*/
2145 
2146  if( eventhdlrdata->regforest != NULL )
2147  completiontype = COMPLETIONTYPE_REGFOREST;
2148  else if( useweight && usessg )
2149  completiontype = COMPLETIONTYPE_MONOREG;
2150  else if( useweight )
2151  completiontype = COMPLETIONTYPE_TREEWEIGHT;
2152  else if( usessg )
2153  completiontype = COMPLETIONTYPE_SSG;
2154  else
2155  completiontype = COMPLETIONTYPE_GAP;
2156  }
2157 
2158  /* compute the search tree completion based on the selected method */
2159  switch (completiontype)
2160  {
2161  /* use regression forest */
2163  values[0] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_TREEWEIGHT]);
2164  values[1] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_TREEWEIGHT]->des);
2165  values[2] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_SSG]);
2166  values[3] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_SSG]->des);
2167  values[4] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_LFREQ]);
2168  values[5] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_LFREQ]->des);
2169  values[6] = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_GAP]);
2170  values[7] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_GAP]->des);
2171  values[8] = doubleExpSmoothGetTrend(&eventhdlrdata->timeseries[TSPOS_OPEN]->des) < 0 ? 1.0 : 0.0;
2172 
2173  *completed = SCIPregForestPredict(eventhdlrdata->regforest, values);
2174  break;
2175 
2176  /* interpolate between ssg and tree weight */
2178  *completed = eventhdlrdata->coefmonoweight * (SCIP_Real)treedata->weight +
2179  eventhdlrdata->coefmonossg * (1.0 - treedata->ssg->value);
2180  break;
2181 
2183  *completed = (SCIP_Real)treedata->weight;
2184  break;
2185 
2186  case COMPLETIONTYPE_GAP:
2187  *completed = timeSeriesGetValue(eventhdlrdata->timeseries[TSPOS_GAP]); /* gap is stored as 1 - gap */
2188  break;
2189 
2190  case COMPLETIONTYPE_SSG:
2191  *completed = 1.0 - treedata->ssg->value; /* ssg is decreasing */
2192  break;
2193 
2194  default:
2195  SCIPerrorMessage("Unsupported completion type '%c'\n", completiontype);
2196  SCIPABORT();
2197  return SCIP_PARAMETERWRONGVAL;
2198  }
2199  return SCIP_OKAY;
2200 }
2201 
2202 /** tree size estimation based on search tree completion */
2203 static
2205  SCIP* scip, /**< SCIP data structure */
2206  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
2207  SCIP_Real* estim /**< pointer to store the estimation value */
2208  )
2209 {
2210  SCIP_Real completed;
2211 
2212  *estim = -1.0;
2213 
2214  SCIP_CALL( getSearchCompletion(eventhdlrdata, &completed) );
2215 
2216  completed = MIN(completed, 1.0);
2217 
2218  if( completed > 0.0 )
2219  *estim = SCIPgetNNodes(scip) / completed;
2220 
2221  return SCIP_OKAY;
2222 }
2223 
2224 /** update callback at nodes */
2225 static
2226 DECL_TIMESERIESUPDATE(timeseriesUpdateGap)
2227 { /*lint --e{715}*/
2228  SCIP_Real primalbound;
2229  SCIP_Real dualbound;
2231  assert(scip != NULL);
2232  assert(ts != NULL);
2233  assert(value != NULL);
2234 
2235  /* avoid to call SCIPgetDualbound during a restart where the queue is simply emptied */
2236  if( SCIPisInRestart(scip) )
2237  {
2238  *value = timeSeriesGetValue(ts);
2239 
2240  return SCIP_OKAY;
2241  }
2242 
2243  primalbound = SCIPgetPrimalbound(scip);
2244  dualbound = SCIPgetDualbound(scip);
2245  if( SCIPisInfinity(scip, REALABS(primalbound)) || SCIPisInfinity(scip, REALABS(dualbound)) )
2246  *value = 0;
2247  else if( SCIPisEQ(scip, primalbound, dualbound) )
2248  *value = 1.0;
2249  else
2250  {
2251  SCIP_Real abspb;
2252  SCIP_Real absdb;
2253 
2254  abspb = REALABS(primalbound);
2255  absdb = REALABS(dualbound);
2256  *value = 1.0 - REALABS(primalbound - dualbound)/MAX(abspb, absdb);
2257  }
2258 
2259  /* using this max, we set the closed gap to 0 in the case where the primal and dual bound differ in their sign */
2260  *value = MAX(*value, 0.0);
2261 
2262  return SCIP_OKAY;
2263 }
2264 
2265 /** update callback at nodes */
2266 static
2267 DECL_TIMESERIESUPDATE(timeseriesUpdateTreeWeight)
2268 { /*lint --e{715}*/
2269  *value = (SCIP_Real)treedata->weight;
2270 
2271  return SCIP_OKAY;
2272 }
2273 
2274 /** update callback at nodes */
2275 static
2276 DECL_TIMESERIESUPDATE(timeseriesUpdateLeafFreq)
2277 { /*lint --e{715}*/
2278  if( treedata->nvisited == 0 )
2279  *value = -0.5;
2280  else
2281  *value = (treedata->nleaves - 0.5)/(SCIP_Real)treedata->nvisited;
2282 
2283  return SCIP_OKAY;
2284 }
2285 
2286 /** update callback at nodes */
2287 static
2288 DECL_TIMESERIESUPDATE(timeseriesUpdateSsg)
2289 { /*lint --e{715}*/
2290  if( treedata->nvisited == 0 )
2291  *value = 1.0;
2292  else
2293  *value = treedata->ssg->value;
2294 
2295  return SCIP_OKAY;
2296 }
2297 
2298 /** update callback at nodes */
2299 static
2300 DECL_TIMESERIESUPDATE(timeseriesUpdateOpenNodes)
2301 { /*lint --e{715}*/
2302  if( treedata->nvisited == 0 )
2303  *value = 0.0;
2304  else
2305  *value = (SCIP_Real)treedata->nopen;
2306 
2307  return SCIP_OKAY;
2308 }
2309 
2310 /** include time series to forecast into event handler */
2311 static
2313  SCIP* scip, /**< SCIP data structure */
2314  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2315  )
2317  assert(scip != NULL);
2318  assert(eventhdlrdata != NULL);
2319 
2320  /* include gap time series */
2321  SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_GAP], "gap", 1.0, 0.0,
2322  DES_ALPHA_GAP, DES_BETA_GAP, timeseriesUpdateGap) );
2323 
2324  /* include tree weight time series */
2325  SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_TREEWEIGHT], "tree-weight", 1.0, 0.0,
2326  DES_ALPHA_TREEWEIGHT, DES_BETA_TREEWEIGHT, timeseriesUpdateTreeWeight) );
2327 
2328  /* include leaf time series */
2329  SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_LFREQ], "leaf-frequency", 0.5, -0.5,
2330  DES_ALPHA_LEAFFREQUENCY, DES_BETA_LEAFFREQUENCY, timeseriesUpdateLeafFreq) );
2331 
2332  /* include SSG time series */
2333  SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_SSG], "ssg", 0.0, 1.0,
2334  DES_ALPHA_SSG, DES_BETA_SSG, timeseriesUpdateSsg) );
2335 
2336  /* include open nodes time series */
2337  SCIP_CALL( timeSeriesCreate(scip, &eventhdlrdata->timeseries[TSPOS_OPEN], "open-nodes", 0.0, 0.0,
2338  DES_ALPHA_OPENNODES, DES_BETA_OPENNODES, timeseriesUpdateOpenNodes) );
2339 
2340  return SCIP_OKAY;
2341 }
2342 
2343 /** get restartpolicy based on the value of the restart parameter */
2344 static
2346  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2347  )
2348 {
2349  switch (eventhdlrdata->restartpolicyparam)
2350  {
2352  return RESTARTPOLICY_ALWAYS;
2354  return RESTARTPOLICY_NEVER;
2356  return RESTARTPOLICY_COMPLETION;
2358  return RESTARTPOLICY_ESTIMATION;
2359  default:
2360  SCIPerrorMessage("Unknown restart policy %c\n", eventhdlrdata->restartpolicyparam);
2361  break;
2362  }
2363 
2364  return RESTARTPOLICY_NEVER;
2365 }
2366 
2367 /** check if a restart is applicable considering limit and threshold user parameters */
2368 static
2370  SCIP* scip, /**< SCIP data structure */
2371  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2372  )
2375 
2376  /* check whether to apply restarts when there are active pricers available */
2377  if( SCIPgetNActivePricers(scip) > 0 && ! eventhdlrdata->restartactpricers )
2378  return FALSE;
2379 
2380  /* check whether to apply a restart when nonlinear constraints are present */
2381  if( SCIPisNLPConstructed(scip) && ! eventhdlrdata->restartnonlinear )
2382  return FALSE;
2383 
2384  /* check if max number of restarts has been reached */
2385  if( eventhdlrdata->restartlimit != -1 && eventhdlrdata->nrestartsperformed >= eventhdlrdata->restartlimit )
2386  return FALSE;
2387 
2388  /* check if number of nodes exceeds the minimum number of nodes */
2389  if( eventhdlrdata->countonlyleaves )
2390  nnodes = eventhdlrdata->treedata->nleaves;
2391  else
2392  nnodes = eventhdlrdata->treedata->nvisited;
2393 
2394  if( nnodes < eventhdlrdata->minnodes )
2395  return FALSE;
2396 
2397  return TRUE;
2398 }
2399 
2400 /** should a restart be applied based on the value of the selected completion method? */ /*lint --e{715}*/
2401 static
2403  SCIP* scip, /**< SCIP data structure */
2404  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2405  )
2406 { /*lint --e{715}*/
2407  SCIP_Real completion;
2408 
2409  SCIP_CALL_ABORT( getSearchCompletion(eventhdlrdata, &completion) );
2410 
2411  /* if the estimation exceeds the current number of nodes by a dramatic factor, restart */
2412  if( completion < 1.0 / eventhdlrdata->restartfactor )
2413  {
2414  SCIPstatistic(
2416  "Completion %.5f less than restart threshold %.5f\n",
2417  completion, 1.0 / eventhdlrdata->restartfactor);
2418  )
2419 
2420  return TRUE;
2421  }
2422 
2423  return FALSE;
2424 }
2425 
2426 /** should a restart be applied based on the value of the selected completion method? */
2427 static
2429  SCIP* scip, /**< SCIP data structure */
2430  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2431  )
2433  SCIP_Real estimation;
2434 
2435  estimation = SCIPgetTreesizeEstimation(scip);
2436 
2437  if( estimation < 0.0 )
2438  {
2439  SCIPstatistic(
2441  "Estimation %g is still unavailable\n",
2442  estimation);
2443  )
2444 
2445  return TRUE;
2446  }
2447 
2448  /* if the estimation exceeds the current number of nodes by a dramatic factor, restart */
2449  if( estimation > eventhdlrdata->treedata->nnodes * eventhdlrdata->restartfactor )
2450  {
2451  SCIPstatistic(
2453  "Estimation %g exceeds number of estimation tree nodes %" SCIP_LONGINT_FORMAT " by a factor of %.1f\n",
2454  estimation, eventhdlrdata->treedata->nnodes, estimation / eventhdlrdata->treedata->nnodes);
2455  )
2456 
2457  return TRUE;
2458  }
2459 
2460  return FALSE;
2461 }
2462 
2463 /** check if a restart should be performed based on the given restart policy */
2464 static
2466  SCIP* scip, /**< SCIP data structure */
2467  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
2468  )
2470  SCIP_Bool applyrestart = FALSE;
2471 
2472  switch (getRestartPolicy(eventhdlrdata))
2473  {
2474  case RESTARTPOLICY_ALWAYS:
2475  applyrestart = TRUE;
2476  break;
2477  case RESTARTPOLICY_NEVER:
2478  applyrestart = FALSE;
2479  break;
2481  applyrestart = shouldApplyRestartCompletion(scip, eventhdlrdata);
2482  break;
2484  applyrestart = shouldApplyRestartEstimation(scip, eventhdlrdata);
2485  break;
2486  default:
2487  break;
2488  }
2489 
2490  return applyrestart;
2491 }
2492 
2493 /** update all time series */
2494 static
2496  SCIP* scip, /**< SCIP data structure */
2497  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
2498  TREEDATA* treedata, /**< tree data */
2499  SCIP_Bool isleaf /**< are we at a leaf node? */
2500  )
2501 {
2502  TIMESERIES** tss = eventhdlrdata->timeseries;
2503  int t;
2504 
2505  /* loop over time series */
2506  for( t = 0; t < NTIMESERIES; ++t )
2507  {
2508  assert(tss[t] != NULL);
2509  SCIP_CALL( timeSeriesUpdate(scip, tss[t], treedata, isleaf) );
2510 
2511 #ifdef SCIP_MORE_DEBUG
2512  SCIPdebugMsg(scip,
2513  "Update of time series '%s', current value %.4f (%" SCIP_LONGINT_FORMAT " observations)\n",
2514  timeSeriesGetName(tss[t]), timeSeriesGetValue(tss[t]), tss[t]->nobs);
2515 #endif
2516  }
2517 
2518  return SCIP_OKAY;
2519 }
2520 
2521 /** print a treesize estimation report into the string buffer */
2522 static
2523 char* printReport(
2524  SCIP* scip, /**< SCIP data structure */
2525  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
2526  char* strbuf, /**< string buffer */
2527  int reportnum /**< report number, or 0 to omit number */
2528  )
2529 {
2530  TREEDATA* treedata = eventhdlrdata->treedata;
2531  char* ptr = strbuf;
2532  SCIP_Real completed;
2533  SCIP_Real wbeestim;
2534  char wbeestimstr[SCIP_MAXSTRLEN];
2535  int t;
2536 
2537  /* print report number */
2538  if( reportnum > 0 )
2539  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "Report %d\nTime Elapsed: %.2f\n", reportnum, SCIPgetSolvingTime(scip));
2540 
2541  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
2542  "Estim. Tree Size :%11" SCIP_LONGINT_FORMAT "\n",
2544 
2545  SCIP_CALL_ABORT( getSearchCompletion(eventhdlrdata, &completed) );
2546 
2547  completed = MIN(1.0, completed);
2548  completed = MAX(0.0, completed);
2549 
2550  /* print tree data */
2551  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN,
2552  "%-19s: %" SCIP_LONGINT_FORMAT " nodes ("
2553  "%" SCIP_LONGINT_FORMAT " visited, "
2554  "%" SCIP_LONGINT_FORMAT " internal, "
2555  "%" SCIP_LONGINT_FORMAT " leaves, "
2556  "%" SCIP_LONGINT_FORMAT " open), "
2557  "weight: %.4Lf completed %.4f\n",
2558  "Estimation Tree",
2559  treedata->nnodes,
2560  treedata->nvisited,
2561  treedata->ninner,
2562  treedata->nleaves,
2563  treedata->nopen,
2564  treedata->weight,
2565  completed
2566  );
2567 
2568  /* print estimations */
2569  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "Estimations : %10s %10s %10s %10s %10s",
2570  "estim", "value", "trend", "resolution", "smooth");
2571  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "\n");
2572 
2573  wbeestim = treeDataGetWbe(eventhdlrdata->treedata);
2574  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, " wbe : %10s %10s %10s %10s %10s\n",
2575  real2String(wbeestim, wbeestimstr, 0), "-", "-", "-", "-");
2576 
2577  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, " tree-profile : %10.0f %10s %10s %10s %10s\n",
2578  predictTotalSizeTreeProfile(scip, eventhdlrdata->treeprofile, eventhdlrdata->treeprofile_minnodesperdepth),
2579  "-", "-", "-", "-");
2580 
2581  /* print time series forecasts */
2582  for( t = 0; t < NTIMESERIES; ++t )
2583  {
2584  SCIP_Real trend;
2585  SCIP_Real smoothestim;
2586  TIMESERIES* ts = eventhdlrdata->timeseries[t];
2587  char trendstr[SCIP_MAXSTRLEN];
2588  char smoothestimstr[SCIP_MAXSTRLEN];
2589 
2590  trend = doubleExpSmoothGetTrend(&ts->des);
2591  smoothestim = timeSeriesGetSmoothEstimation(ts);
2592 
2593  ptr += SCIPsnprintf(ptr, SCIP_MAXSTRLEN, " %-17s: %10.0f %10.5f %10s %10d %10s\n",
2594  timeSeriesGetName(ts),
2595  timeSeriesEstimate(ts, eventhdlrdata->treedata),
2596  timeSeriesGetValue(ts),
2597  real2String(trend, trendstr, 5),
2599  real2String(smoothestim, smoothestimstr, 0));
2600  }
2601 
2602  if( reportnum > 0 )
2603  (void) SCIPsnprintf(ptr, SCIP_MAXSTRLEN, "End of Report %d\n", reportnum);
2604 
2605  return strbuf;
2606 }
2607 
2608 
2609 /** copy method for event handler plugins (called when SCIP copies plugins) */
2610 static
2611 SCIP_DECL_EVENTCOPY(eventCopyEstim)
2612 { /*lint --e{715}*/
2613  assert(scip != NULL);
2614 
2616 
2617  return SCIP_OKAY;
2618 }
2619 
2620 /** destructor of event handler to free user data (called when SCIP is exiting) */
2621 static
2622 SCIP_DECL_EVENTFREE(eventFreeEstim)
2623 { /*lint --e{715}*/
2624  SCIP_EVENTHDLRDATA* eventhdlrdata;
2625 
2626  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2627  assert(eventhdlrdata != NULL);
2628 
2629  freeTreeData(scip, &eventhdlrdata->treedata);
2630 
2631  freeTimeSeries(scip, eventhdlrdata);
2632 
2633  SCIPfreeMemory(scip, &eventhdlrdata);
2634 
2635  return SCIP_OKAY;
2636 }
2637 
2638 /** initialization method of event handler (called after problem was transformed) */
2639 static
2640 SCIP_DECL_EVENTINIT(eventInitEstim)
2641 { /*lint --e{715}*/
2642  SCIP_EVENTHDLRDATA* eventhdlrdata;
2643 
2644  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2645  assert(eventhdlrdata != NULL);
2646 
2647  /* test if user specified a regression forest */
2648  if( 0 != strncmp(eventhdlrdata->regforestfilename, DEFAULT_REGFORESTFILENAME, strlen(DEFAULT_REGFORESTFILENAME)) )
2649  {
2650  SCIP_CALL( SCIPregForestFromFile(&eventhdlrdata->regforest, eventhdlrdata->regforestfilename) );
2651  }
2652 
2653  eventhdlrdata->lastrestartrun = 0;
2654  eventhdlrdata->nrestartsperformed = 0;
2655 
2656  return SCIP_OKAY;
2657 }
2658 
2659 /** deinitialization method of event handler (called before transformed problem is freed) */
2660 static
2661 SCIP_DECL_EVENTEXIT(eventExitEstim)
2662 { /*lint --e{715}*/
2663  SCIP_EVENTHDLRDATA* eventhdlrdata;
2664 
2665  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2666  assert(eventhdlrdata != NULL);
2667 
2668  SCIPregForestFree(&eventhdlrdata->regforest);
2669 
2670  return SCIP_OKAY;
2671 }
2672 
2673 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
2674 static
2675 SCIP_DECL_EVENTINITSOL(eventInitsolEstim)
2676 { /*lint --e{715}*/
2677  SCIP_EVENTHDLRDATA* eventhdlrdata;
2678 
2679  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2680  assert(eventhdlrdata != NULL);
2681 
2682  eventhdlrdata->restarthitcounter = 0;
2683  eventhdlrdata->weightlastreport = 0.0;
2684  eventhdlrdata->nreports = 0;
2685 
2686  /* reset tree data */
2687  SCIP_CALL( resetTreeData(scip, eventhdlrdata->treedata) );
2688 
2689  resetTimeSeries(eventhdlrdata);
2690 
2691  SCIP_CALL( SCIPcatchEvent(scip, EVENTTYPE_ESTIM, eventhdlr, NULL, NULL) );
2692 
2693  if( eventhdlrdata->treeprofile_enabled )
2694  {
2695  SCIP_CALL( createTreeProfile(scip, &eventhdlrdata->treeprofile) );
2696  }
2697 
2698  eventhdlrdata->treeisbinary = TRUE;
2699 
2700  return SCIP_OKAY;
2701 }
2702 
2703 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
2704 static
2705 SCIP_DECL_EVENTEXITSOL(eventExitsolEstim)
2706 { /*lint --e{715}*/
2707  SCIP_EVENTHDLRDATA* eventhdlrdata;
2708 
2709  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2710  assert(eventhdlrdata != NULL);
2711 
2712  if( eventhdlrdata->treeprofile != NULL )
2713  freeTreeProfile(scip, &eventhdlrdata->treeprofile);
2714 
2715  SCIP_CALL( SCIPdropEvent(scip, EVENTTYPE_ESTIM, eventhdlr, NULL, -1) );
2716 
2717  return SCIP_OKAY;
2718 }
2719 
2720 /** execution method of event handler */
2721 static
2722 SCIP_DECL_EVENTEXEC(eventExecEstim)
2723 { /*lint --e{715}*/
2724  SCIP_EVENTHDLRDATA* eventhdlrdata;
2725  SCIP_Bool isleaf;
2726  SCIP_EVENTTYPE eventtype;
2727  TREEDATA* treedata;
2728  char strbuf[SCIP_MAXSTRLEN];
2729 
2730  assert(scip != NULL);
2731  assert(eventhdlr != NULL);
2732 
2733  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2734  assert(eventhdlrdata != NULL);
2735  eventtype = SCIPeventGetType(event);
2736  treedata = eventhdlrdata->treedata;
2737 
2738  /* actual leaf nodes for our tree data are children/siblings/leaves or the focus node itself (deadend)
2739  * if it has not been branched on
2740  */
2741  isleaf = (eventtype == SCIP_EVENTTYPE_NODEDELETE) &&
2746 
2747  if( eventtype == SCIP_EVENTTYPE_NODEBRANCHED || isleaf )
2748  {
2749  SCIP_NODE* eventnode;
2750  int nchildren = 0;
2751 
2752  if( eventtype == SCIP_EVENTTYPE_NODEBRANCHED )
2753  {
2754  nchildren = SCIPgetNChildren(scip);
2755 
2756  /* update whether the tree is still binary */
2757  if( nchildren != 2 )
2758  eventhdlrdata->treeisbinary = FALSE;
2759  }
2760 
2761  eventnode = SCIPeventGetNode(event);
2762  SCIP_CALL( updateTreeData(scip, treedata, eventnode, nchildren) );
2763  SCIP_CALL( updateTreeProfile(scip, eventhdlrdata->treeprofile, eventnode) );
2764 
2765 #ifdef SCIP_DEBUG
2766  SCIPdebugMsg(scip, "%s\n", treeDataPrint(treedata, strbuf));
2767 #endif
2768 
2769  SCIP_CALL( updateTimeseries(scip, eventhdlrdata, treedata, nchildren == 0) );
2770 
2771  /* should a new report be printed? */
2772  if( eventhdlrdata->reportfreq >= 0 && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN &&
2773  (eventhdlrdata->reportfreq == 0
2774  || treedata->weight >= eventhdlrdata->weightlastreport + 1.0 / (SCIP_Real)eventhdlrdata->reportfreq) )
2775  {
2776  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s\n", printReport(scip, eventhdlrdata, strbuf, ++eventhdlrdata->nreports));
2777 
2778  if( eventhdlrdata->reportfreq > 0 )
2779  eventhdlrdata->weightlastreport = 1 / (SCIP_Real)eventhdlrdata->reportfreq * SCIPfloor(scip, ((SCIP_Real)treedata->weight * eventhdlrdata->reportfreq));
2780  else
2781  eventhdlrdata->weightlastreport = (SCIP_Real)treedata->weight;
2782  }
2783  }
2784 
2785  /* if nodes have been pruned, things are progressing, don't restart right now */
2786  if( isleaf )
2787  return SCIP_OKAY;
2788 
2789  /* check if all conditions are met such that the event handler should run */
2790  if( ! isRestartApplicable(scip, eventhdlrdata) )
2791  return SCIP_OKAY;
2792 
2793  /* test if a restart should be applied */
2794  if( shouldApplyRestart(scip, eventhdlrdata) )
2795  {
2796  eventhdlrdata->restarthitcounter++;
2797 
2798  if( eventhdlrdata->restarthitcounter >= eventhdlrdata->hitcounterlim )
2799  {
2800  /* safe that we triggered a restart at this run */
2801  if( SCIPgetNRuns(scip) > eventhdlrdata->lastrestartrun )
2802  {
2803  eventhdlrdata->nrestartsperformed++;
2804 
2806  "Restart triggered after %d consecutive estimations that the remaining tree will be large\n",
2807  eventhdlrdata->restarthitcounter);
2808  }
2809 
2810  eventhdlrdata->lastrestartrun = SCIPgetNRuns(scip);
2811 
2812  SCIP_CALL( SCIPrestartSolve(scip) );
2813  }
2814  }
2815  else
2816  {
2817  eventhdlrdata->restarthitcounter = 0;
2818  }
2819 
2820  return SCIP_OKAY;
2821 }
2822 
2823 /** output method of statistics table to output file stream 'file' */
2824 static
2825 SCIP_DECL_TABLEOUTPUT(tableOutputEstim)
2826 { /*lint --e{715}*/
2827  SCIP_EVENTHDLR* eventhdlr;
2828  SCIP_EVENTHDLRDATA* eventhdlrdata;
2829  char strbuf[SCIP_MAXSTRLEN];
2830 
2831  eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
2832  assert(eventhdlr != NULL);
2833 
2834  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2835  assert(eventhdlrdata != NULL);
2836 
2837  SCIPinfoMessage(scip, file, "%s", printReport(scip, eventhdlrdata, strbuf, 0));
2838 
2839  return SCIP_OKAY;
2840 }
2841 
2842 /** output method of search tree completion display column to output file stream 'file' */
2843 static
2844 SCIP_DECL_DISPOUTPUT(dispOutputCompleted)
2845 { /*lint --e{715}*/
2846  SCIP_EVENTHDLR* eventhdlr;
2847  SCIP_EVENTHDLRDATA* eventhdlrdata;
2848  TREEDATA* treedata;
2849  SCIP_Real completed;
2850 
2851  assert(disp != NULL);
2852  assert(strcmp(SCIPdispGetName(disp), DISP_NAME) == 0);
2853  assert(scip != NULL);
2854 
2855  eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
2856  assert(eventhdlr != NULL);
2857  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
2858  assert(eventhdlrdata != NULL);
2859  treedata = eventhdlrdata->treedata;
2860 
2861  SCIP_CALL( getSearchCompletion(eventhdlrdata, &completed) );
2862 
2863  completed = MIN(completed, 1.0);
2864 
2865  if( treedata->weight >= 0.005 && completed > 0 )
2866  SCIPinfoMessage(scip, file, "%7.2f%%", 100.0 * completed);
2867  else
2868  SCIPinfoMessage(scip, file, " unknown");
2869 
2870  return SCIP_OKAY;
2871 }
2872 
2873 /** creates event handler for tree size estimation */
2875  SCIP* scip /**< SCIP data structure */
2876  )
2877 {
2878  SCIP_RETCODE retcode;
2879  SCIP_EVENTHDLRDATA* eventhdlrdata = NULL;
2880  SCIP_EVENTHDLR* eventhdlr = NULL;
2881 
2882  /* create estim event handler data */
2883  SCIP_CALL( SCIPallocMemory(scip, &eventhdlrdata) );
2884  BMSclearMemory(eventhdlrdata);
2885 
2886  SCIP_CALL_TERMINATE( retcode, createTreeData(scip, &eventhdlrdata->treedata), TERMINATE );
2887 
2889  eventExecEstim, eventhdlrdata) );
2890  assert(eventhdlr != NULL);
2891 
2892  /* set non fundamental callbacks via setter functions */
2893  SCIP_CALL( SCIPsetEventhdlrCopy(scip, eventhdlr, eventCopyEstim) );
2894  SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeEstim) );
2895  SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitEstim) );
2896  SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitEstim) );
2897  SCIP_CALL( SCIPsetEventhdlrInitsol(scip, eventhdlr, eventInitsolEstim) );
2898  SCIP_CALL( SCIPsetEventhdlrExitsol(scip, eventhdlr, eventExitsolEstim) );
2899 
2900  /* add estimation event handler parameters */
2901  SCIP_CALL( SCIPaddCharParam(scip, "estimation/restarts/restartpolicy", "restart policy: (a)lways, (c)ompletion, (e)stimation, (n)ever",
2902  &eventhdlrdata->restartpolicyparam, FALSE, DEFAULT_RESTARTPOLICY, "acen", NULL, NULL) );
2903 
2904  SCIP_CALL( SCIPaddCharParam(scip, "estimation/method",
2905  "tree size estimation method: (c)ompletion, (e)nsemble, "
2906  "time series forecasts on either (g)ap, (l)eaf frequency, (o)open nodes, tree (w)eight, (s)sg, "
2907  "or (t)ree profile or w(b)e",
2908  &eventhdlrdata->estimmethod, FALSE, DEFAULT_ESTIMMETHOD, ESTIMMETHODS, NULL, NULL) );
2909 
2910  SCIP_CALL( SCIPaddIntParam(scip, "estimation/restarts/restartlimit", "restart limit",
2911  &eventhdlrdata->restartlimit, FALSE, DEFAULT_RESTARTLIMIT, -1, INT_MAX, NULL, NULL) );
2912 
2913  SCIP_CALL( SCIPaddLongintParam(scip, "estimation/restarts/minnodes", "minimum number of nodes before restart",
2914  &eventhdlrdata->minnodes, FALSE, DEFAULT_MINNODES, -1L, SCIP_LONGINT_MAX, NULL, NULL) );
2915 
2916  SCIP_CALL( SCIPaddBoolParam(scip, "estimation/restarts/countonlyleaves", "should only leaves count for the minnodes parameter?",
2917  &eventhdlrdata->countonlyleaves, DEFAULT_COUNTONLYLEAVES, FALSE, NULL, NULL) );
2918 
2919  SCIP_CALL( SCIPaddRealParam(scip, "estimation/restarts/restartfactor",
2920  "factor by which the estimated number of nodes should exceed the current number of nodes",
2921  &eventhdlrdata->restartfactor, FALSE, DEFAULT_RESTARTFACTOR, 1.0, SCIP_REAL_MAX, NULL, NULL) );
2922 
2923  SCIP_CALL( SCIPaddBoolParam(scip, "estimation/restarts/restartnonlinear",
2924  "whether to apply a restart when nonlinear constraints are present",
2925  &eventhdlrdata->restartnonlinear, FALSE, DEFAULT_RESTARTNONLINEAR, NULL, NULL) );
2926 
2927  SCIP_CALL( SCIPaddBoolParam(scip, "estimation/restarts/restartactpricers",
2928  "whether to apply a restart when active pricers are used",
2929  &eventhdlrdata->restartactpricers, FALSE, DEFAULT_RESTARTACTPRICERS, NULL, NULL) );
2930 
2931  SCIP_CALL( SCIPaddRealParam(scip, "estimation/coefmonoweight",
2932  "coefficient of tree weight in monotone approximation of search completion",
2933  &eventhdlrdata->coefmonoweight, FALSE, DEFAULT_COEFMONOWEIGHT, 0.0, 1.0, NULL, NULL) );
2934 
2935  SCIP_CALL( SCIPaddRealParam(scip, "estimation/coefmonossg",
2936  "coefficient of 1 - SSG in monotone approximation of search completion",
2937  &eventhdlrdata->coefmonossg, FALSE, DEFAULT_COEFMONOSSG, 0.0, 1.0, NULL, NULL) );
2938 
2939  SCIP_CALL( SCIPaddIntParam(scip, "estimation/restarts/hitcounterlim", "limit on the number of successive samples to really trigger a restart",
2940  &eventhdlrdata->hitcounterlim, FALSE, DEFAULT_HITCOUNTERLIM, 1, INT_MAX, NULL, NULL) );
2941 
2942  SCIP_CALL( SCIPaddIntParam(scip, "estimation/reportfreq",
2943  "report frequency on estimation: -1: never, 0:always, k >= 1: k times evenly during search",
2944  &eventhdlrdata->reportfreq, TRUE, DEFAULT_REPORTFREQ, -1, INT_MAX / 2, NULL, NULL) );
2945 
2946  SCIP_CALL( SCIPaddStringParam(scip, "estimation/regforestfilename", "user regression forest in RFCSV format",
2947  &eventhdlrdata->regforestfilename, FALSE, DEFAULT_REGFORESTFILENAME, NULL, NULL) );
2948 
2949  SCIP_CALL( SCIPaddCharParam(scip, "estimation/completiontype",
2950  "approximation of search tree completion: (a)uto, (g)ap, tree (w)eight, (m)onotone regression, (r)egression forest, (s)sg",
2951  &eventhdlrdata->completiontypeparam, FALSE, DEFAULT_COMPLETIONTYPE, "agmrsw", NULL, NULL) );
2952 
2953  SCIP_CALL( SCIPaddBoolParam(scip, "estimation/treeprofile/enabled",
2954  "should the event handler collect data?",
2955  &eventhdlrdata->treeprofile_enabled, FALSE, DEFAULT_TREEPROFILE_ENABLED, NULL, NULL) );
2956 
2957  SCIP_CALL( SCIPaddRealParam(scip, "estimation/treeprofile/minnodesperdepth",
2958  "minimum average number of nodes at each depth before producing estimations",
2959  &eventhdlrdata->treeprofile_minnodesperdepth, FALSE, DEFAULT_TREEPROFILE_MINNODESPERDEPTH, 1.0, SCIP_REAL_MAX, NULL, NULL) );
2960 
2961  SCIP_CALL( SCIPaddBoolParam(scip, "estimation/useleafts",
2962  "use leaf nodes as basic observations for time series, or all nodes?",
2963  &eventhdlrdata->useleafts, TRUE, DEFAULT_USELEAFTS, NULL, NULL) );
2964 
2965  /* SSG parameters */
2966  SCIP_CALL( SCIPaddIntParam(scip, "estimation/ssg/nmaxsubtrees",
2967  "the maximum number of individual SSG subtrees; -1: no limit",
2968  &eventhdlrdata->treedata->ssg->nmaxsubtrees, FALSE, DEFAULT_SSG_NMAXSUBTREES, -1, INT_MAX / 2, NULL, NULL) );
2969 
2970  SCIP_CALL( SCIPaddLongintParam(scip, "estimation/ssg/nminnodeslastsplit",
2971  "minimum number of nodes to process between two consecutive SSG splits",
2972  &eventhdlrdata->treedata->ssg->nminnodeslastsplit, FALSE, DEFAULT_SSG_NMINNODESLASTSPLIT, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
2973 
2974  /* include statistics table */
2976  NULL, NULL, NULL, NULL, NULL, NULL, tableOutputEstim,
2978 
2979  /* include time series into event handler */
2980  SCIP_CALL( includeTimeseries(scip, eventhdlrdata) );
2981 
2982  /* include display column */
2984  NULL, NULL, NULL, NULL, NULL, NULL, dispOutputCompleted,
2986 
2987 /* cppcheck-suppress unusedLabel */
2988 TERMINATE:
2989  if( retcode != SCIP_OKAY )
2990  {
2991  freeTreeData(scip, &eventhdlrdata->treedata);
2992  SCIPfreeMemory(scip, &eventhdlrdata);
2993  }
2994 
2995  return retcode;
2996 }
2997 
2998 /** return an estimation of the final tree size */
3000  SCIP* scip /**< SCIP data structure */
3001  )
3002 {
3003  SCIP_EVENTHDLR* eventhdlr;
3004  SCIP_EVENTHDLRDATA* eventhdlrdata;
3005  TSPOS tspos = TSPOS_NONE;
3006  SCIP_Real estim;
3007 
3008  assert(scip != NULL);
3009 
3010  eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
3011  if( eventhdlr == NULL )
3012  {
3013  SCIPwarningMessage(scip, "SCIPgetTreesizeEstimation() called, but event handler " EVENTHDLR_NAME " is missing.\n");
3014  return -1.0;
3015  }
3016 
3017  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
3018  assert(eventhdlrdata != NULL);
3019 
3020  switch (eventhdlrdata->estimmethod)
3021  {
3022  case ESTIMMETHOD_COMPL:
3023  SCIP_CALL_ABORT( getEstimCompletion(scip, eventhdlrdata, &estim) );
3024  return estim;
3025 
3026  case ESTIMMETHOD_ENSMBL:
3027  return getEnsembleEstimation(eventhdlrdata);
3028 
3029  /* for the requested time series methods, we specify the array position */
3030  case ESTIMMETHOD_GAP:
3031  tspos = TSPOS_GAP;
3032  break;
3033 
3034  case ESTIMMETHOD_LFREQ:
3035  tspos = TSPOS_LFREQ;
3036  break;
3037 
3038  case ESTIMMETHOD_OPEN:
3039  tspos = TSPOS_OPEN;
3040  break;
3041 
3043  tspos = TSPOS_TREEWEIGHT;
3044  break;
3045 
3046  case ESTIMMETHOD_SSG:
3047  tspos = TSPOS_SSG;
3048  break;
3049 
3050  /* tree profile estimation */
3051  case ESTIMMETHOD_TPROF:
3052  return predictTotalSizeTreeProfile(scip, eventhdlrdata->treeprofile, eventhdlrdata->treeprofile_minnodesperdepth);
3053 
3054  /* Weighted backtrack estimation */
3055  case ESTIMMETHOD_WBE:
3056  return treeDataGetWbe(eventhdlrdata->treedata);
3057 
3058  default:
3059  SCIPerrorMessage("Unknown estimation '%c' method specified, should be one of [%s]\n",
3060  eventhdlrdata->estimmethod, ESTIMMETHODS);
3061  SCIPABORT();
3062  break;
3063  }
3064 
3065  assert(tspos != TSPOS_NONE);
3066  return (tspos == TSPOS_NONE ? -1.0 : timeSeriesEstimate(eventhdlrdata->timeseries[tspos], eventhdlrdata->treedata));
3067 }
#define ESTIMMETHODS
Definition: event_estim.c:158
#define DES_ALPHA_SSG
Definition: event_estim.c:128
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
#define EVENTHDLR_DESC
Definition: event_estim.c:74
int SCIPpqueueNElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1468
SCIP_Longint nnodes
Definition: event_estim.c:299
static char * printReport(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, char *strbuf, int reportnum)
Definition: event_estim.c:2527
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
#define DEFAULT_RESTARTFACTOR
Definition: event_estim.c:251
static SCIP_Bool shouldApplyRestartEstimation(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2432
static SCIP_DECL_PQUEUEELEMCHGPOS(elemChgPosNodeInfo)
Definition: event_estim.c:986
static int timeSeriesGetResolution(TIMESERIES *timeseries)
Definition: event_estim.c:1824
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:101
#define DES_BETA_SSG
Definition: event_estim.c:129
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition: scip_table.c:47
public methods for SCIP parameter handling
SCIP_RETCODE SCIPsetEventhdlrInitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINITSOL((*eventinitsol)))
Definition: scip_event.c:183
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:141
#define DEFAULT_RESTARTPOLICY
Definition: event_estim.c:247
#define COMPLETIONTYPE_AUTO
Definition: event_estim.c:139
public methods for branch and bound tree
type definitions for miscellaneous datastructures
static SCIP_RETCODE subtreeSumGapUpdate(SCIP *scip, SUBTREESUMGAP *ssg, SCIP_NODE *node, int nchildren, SCIP_Longint nsolvednodes)
Definition: event_estim.c:1439
public methods for memory management
static void doubleExpSmoothInit(DOUBLEEXPSMOOTH *des, SCIP_Real x1)
Definition: event_estim.c:1666
static SCIP_RETCODE resetTreeData(SCIP *scip, TREEDATA *treedata)
Definition: event_estim.c:1521
static SCIP_Real predictTotalSizeTreeProfile(SCIP *scip, TREEPROFILE *treeprofile, SCIP_Real minnodesperdepth)
Definition: event_estim.c:789
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Bool usetrendinlevel
Definition: event_estim.c:172
static SCIP_Real timeSeriesGetTargetValue(TIMESERIES *timeseries)
Definition: event_estim.c:1815
static SCIP_Bool shouldApplyRestartCompletion(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2406
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7452
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_Real initialvalue
Definition: event_estim.c:171
static void resetTreeProfileStats(TREEPROFILESTATS *treeprofilestats)
Definition: event_estim.c:631
#define SCIP_MAXSTRLEN
Definition: def.h:293
static void freeTreeData(SCIP *scip, TREEDATA **treedata)
Definition: event_estim.c:1560
SCIP_RETCODE SCIPsetEventhdlrExitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXITSOL((*eventexitsol)))
Definition: scip_event.c:197
enum TsPos TSPOS
Definition: event_estim.c:204
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:88
SCIP_RETCODE SCIPsetEventhdlrExit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXIT((*eventexit)))
Definition: scip_event.c:169
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
#define DECL_TIMESERIESUPDATE(x)
Definition: event_estim.c:323
static void freeTimeSeries(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2005
int SCIPgetNSiblings(SCIP *scip)
Definition: scip_tree.c:221
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
#define DEFAULT_TREEPROFILE_ENABLED
Definition: event_estim.c:245
public solving methods
int SCIPgetNLeaves(SCIP *scip)
Definition: scip_tree.c:263
#define DEFAULT_SSG_NMAXSUBTREES
Definition: event_estim.c:255
static SCIP_RETCODE timeSeriesUpdate(SCIP *scip, TIMESERIES *timeseries, TREEDATA *treedata, SCIP_Bool isleaf)
Definition: event_estim.c:1924
static SCIP_DECL_DISPOUTPUT(dispOutputCompleted)
Definition: event_estim.c:2848
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
public methods for timing
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7712
SCIP_Bool useleafts
Definition: event_estim.c:345
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:146
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:389
static SCIP_RETCODE createTreeProfile(SCIP *scip, TREEPROFILE **treeprofile)
Definition: event_estim.c:678
static SCIP_RETCODE subtreeSumGapCreate(SCIP *scip, SUBTREESUMGAP **ssg)
Definition: event_estim.c:925
SCIP_Bool SCIPwasNodeLastBranchParent(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:722
static SCIP_RETCODE subtreeSumGapRemoveNode(SCIP *scip, SUBTREESUMGAP *ssg, SCIP_NODE *node)
Definition: event_estim.c:1146
static void resetTimeSeries(SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:1982
SCIP_Real lastestimate
Definition: event_estim.c:227
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:339
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Longint ninner
Definition: event_estim.c:301
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define TABLE_DESC
Definition: event_estim.c:101
static SCIP_DECL_EVENTEXITSOL(eventExitsolEstim)
Definition: event_estim.c:2709
void * SCIPpqueueFirst(SCIP_PQUEUE *pqueue)
Definition: misc.c:1454
SCIP_NODE * node
Definition: event_estim.c:352
#define SSG_STARTPRIMBOUND
Definition: event_estim.c:162
static void subtreeSumGapDelSubtrees(SCIP *scip, SUBTREESUMGAP *ssg)
Definition: event_estim.c:861
#define DES_ALPHA_OPENNODES
Definition: event_estim.c:131
public methods for displaying runtime statistics
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:116
#define DEFAULT_ESTIMMETHOD
Definition: event_estim.c:240
static void timeSeriesResample(TIMESERIES *timeseries)
Definition: event_estim.c:1897
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:185
void SCIPpqueueFree(SCIP_PQUEUE **pqueue)
Definition: misc.c:1263
#define SCIPdebugMessage
Definition: pub_message.h:87
type definitions for return codes for SCIP methods
static SCIP_RETCODE timeSeriesCreate(SCIP *scip, TIMESERIES **timeseries, const char *name, SCIP_Real targetvalue, SCIP_Real initialvalue, SCIP_Real alpha, SCIP_Real beta, DECL_TIMESERIESUPDATE((*timeseriesupdate)))
Definition: event_estim.c:1735
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:225
SCIP_Longint nopen
Definition: event_estim.c:300
#define ESTIMMETHOD_SSG
Definition: event_estim.c:154
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void timeSeriesUpdateSmoothEstimation(TIMESERIES *timeseries, SCIP_Real estimation)
Definition: event_estim.c:1872
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7442
static void freeTreeProfile(SCIP *scip, TREEPROFILE **treeprofile)
Definition: event_estim.c:702
#define SCIP_LONGINT_MAX
Definition: def.h:163
static SCIP_Bool isEqualTreeProfileStats(TREEPROFILESTATS *stats, TREEPROFILESTATS *other)
Definition: event_estim.c:599
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
#define BMSfreeMemory(ptr)
Definition: memory.h:138
static SCIP_RETCODE includeTimeseries(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2316
#define ESTIMMETHOD_OPEN
Definition: event_estim.c:153
void SCIPpqueueDelPos(SCIP_PQUEUE *pqueue, int pos)
Definition: misc.c:1374
event handler for tree size estimation and restarts
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:57
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
#define DEFAULT_COMPLETIONTYPE
Definition: event_estim.c:239
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
#define COMPLETIONTYPE_GAP
Definition: event_estim.c:144
type definitions for problem statistics
SCIP_Real * estimation
Definition: event_estim.c:336
SCIP_Longint nodelastsplit
Definition: event_estim.c:315
static SCIP_DECL_EVENTCOPY(eventCopyEstim)
Definition: event_estim.c:2615
public methods for numerical tolerances
#define DISP_DESC
Definition: event_estim.c:107
#define DEFAULT_REGFORESTFILENAME
Definition: event_estim.c:236
#define DEFAULT_RESTARTLIMIT
Definition: event_estim.c:248
public methods for querying solving statistics
static char * timeSeriesGetName(TIMESERIES *timeseries)
Definition: event_estim.c:1973
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
#define SCIP_EVENTTYPE_NODEBRANCHED
Definition: type_event.h:86
public methods for the branch-and-bound tree
SCIP_PQUEUE ** subtreepqueues
Definition: event_estim.c:312
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7432
#define TABLE_NAME
Definition: event_estim.c:100
SCIP_Real value
Definition: event_estim.c:310
static SCIP_Real SCIPregForestPredict(SCIP_REGFOREST *regforest, SCIP_Real *datapoint)
Definition: event_estim.c:416
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:144
#define DEFAULT_COUNTONLYLEAVES
Definition: event_estim.c:250
static SCIP_Real calcGap(SCIP *scip, SCIP_Real lowerbound)
Definition: event_estim.c:1113
#define ESTIMMETHOD_GAP
Definition: event_estim.c:151
#define DISP_PRIORITY
Definition: event_estim.c:110
SCIP_Real pblastsplit
Definition: event_estim.c:314
#define ESTIMMETHOD_WBE
Definition: event_estim.c:149
#define TREEPROFILE_MINSIZE
Definition: event_estim.c:161
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:140
static SCIP_RETCODE createTreeData(SCIP *scip, TREEDATA **treedata)
Definition: event_estim.c:1541
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:141
SCIP_RETCODE SCIPsetEventhdlrCopy(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTCOPY((*eventcopy)))
Definition: scip_event.c:127
SCIP_Real * value
Definition: event_estim.c:366
public methods for event handler plugins and event handlers
#define RESTARTPOLICY_CHAR_ALWAYS
Definition: event_estim.c:93
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:155
SCIP_Real SCIPgetDualbound(SCIP *scip)
static SCIP_DECL_EVENTEXEC(eventExecEstim)
Definition: event_estim.c:2726
SCIP_NODE * SCIPeventGetNode(SCIP_EVENT *event)
Definition: event.c:1291
char * name
Definition: event_estim.c:334
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:218
SCIP_RETCODE SCIPsetEventhdlrInit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINIT((*eventinit)))
Definition: scip_event.c:155
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
SCIP_Real level
Definition: event_estim.c:169
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:34
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:191
#define DEFAULT_COEFMONOWEIGHT
Definition: event_estim.c:237
static SCIP_RETCODE SCIPregForestFromFile(SCIP_REGFOREST **regforest, const char *filename)
Definition: event_estim.c:463
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:61
static SCIP_Real getEnsembleEstimation(SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2027
int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:179
static RESTARTPOLICY getRestartPolicy(SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2349
#define DISP_STRIPLINE
Definition: event_estim.c:112
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
#define NULL
Definition: lpi_spx1.cpp:155
#define NTIMESERIES
Definition: event_estim.c:191
static SCIP_DECL_TABLEOUTPUT(tableOutputEstim)
Definition: event_estim.c:2829
#define REALABS(x)
Definition: def.h:201
static char * real2String(SCIP_Real num, char *buf, int digits)
Definition: event_estim.c:376
#define SESCOEFF
Definition: event_estim.c:116
#define ESTIMMETHOD_TREEWEIGHT
Definition: event_estim.c:156
#define MAX_REGFORESTSIZE
Definition: event_estim.c:134
#define ESTIMMETHOD_ENSMBL
Definition: event_estim.c:150
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_Real timeSeriesGetSmoothEstimation(TIMESERIES *timeseries)
Definition: event_estim.c:1888
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint * profile
Definition: event_estim.c:224
static void SCIPregForestFree(SCIP_REGFOREST **regforest)
Definition: event_estim.c:394
#define DES_BETA_OPENNODES
Definition: event_estim.c:132
propagator for symmetry handling
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
static void copyTreeProfileStats(TREEPROFILESTATS *dest, TREEPROFILESTATS *src)
Definition: event_estim.c:615
static SCIP_RETCODE extendMemoryTreeProfile(SCIP *scip, TREEPROFILE *treeprofile, int mindepth)
Definition: event_estim.c:643
SCIP_HASHMAP * nodes2info
Definition: event_estim.c:311
static SCIP_RETCODE getEstimCompletion(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_Real *estim)
Definition: event_estim.c:2208
static SCIP_RETCODE updateTimeseries(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, TREEDATA *treedata, SCIP_Bool isleaf)
Definition: event_estim.c:2499
type definitions for managing events
static SCIP_RETCODE subtreeSumGapReset(SCIP *scip, SUBTREESUMGAP *ssg)
Definition: event_estim.c:901
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:136
SCIP_Real alpha
Definition: event_estim.c:167
#define DES_ALPHA_GAP
Definition: event_estim.c:122
#define DES_USETRENDINLEVEL
Definition: event_estim.c:97
wrapper functions to map file i/o to standard or zlib file i/o
#define RESTARTPOLICY_CHAR_COMPLETION
Definition: event_estim.c:94
SCIP_Real lowerbound
Definition: event_estim.c:353
#define ESTIMMETHOD_COMPL
Definition: event_estim.c:148
#define ESTIMMETHOD_TPROF
Definition: event_estim.c:155
static SCIP_DECL_EVENTFREE(eventFreeEstim)
Definition: event_estim.c:2626
long double weight
Definition: event_estim.c:304
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
public data structures and miscellaneous methods
#define SCIP_EVENTTYPE_NODEDELETE
Definition: type_event.h:87
#define DEFAULT_HITCOUNTERLIM
Definition: event_estim.c:254
#define SCIP_Bool
Definition: def.h:84
static void timeSeriesFree(SCIP *scip, TIMESERIES **timeseries)
Definition: event_estim.c:1784
SCIP_Real SCIPgetTreesizeEstimation(SCIP *scip)
Definition: event_estim.c:3003
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
#define DEFAULT_RESTARTACTPRICERS
Definition: event_estim.c:253
SCIP_RETCODE SCIPincludeDisp(SCIP *scip, const char *name, const char *desc, const char *header, SCIP_DISPSTATUS dispstatus, SCIP_DECL_DISPCOPY((*dispcopy)), SCIP_DECL_DISPFREE((*dispfree)), SCIP_DECL_DISPINIT((*dispinit)), SCIP_DECL_DISPEXIT((*dispexit)), SCIP_DECL_DISPINITSOL((*dispinitsol)), SCIP_DECL_DISPEXITSOL((*dispexitsol)), SCIP_DECL_DISPOUTPUT((*dispoutput)), SCIP_DISPDATA *dispdata, int width, int priority, int position, SCIP_Bool stripline)
Definition: scip_disp.c:46
static SCIP_RETCODE subtreeSumGapStoreNode(SCIP *scip, SUBTREESUMGAP *ssg, SCIP_NODE *node, int subtreeidx)
Definition: event_estim.c:996
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
SCIP_Real trend
Definition: event_estim.c:170
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3573
static SCIP_RETCODE subtreeSumGapInsertChildren(SCIP *scip, SUBTREESUMGAP *ssg)
Definition: event_estim.c:1217
static SCIP_RETCODE updateTreeProfile(SCIP *scip, TREEPROFILE *treeprofile, SCIP_NODE *node)
Definition: event_estim.c:722
#define RESTARTPOLICY_CHAR_NEVER
Definition: event_estim.c:92
public methods for statistics table plugins
static void doubleExpSmoothUpdate(DOUBLEEXPSMOOTH *des, SCIP_Real xnew)
Definition: event_estim.c:1684
SCIP_Longint nminnodeslastsplit
Definition: event_estim.c:316
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10856
#define DEFAULT_COEFMONOSSG
Definition: event_estim.c:238
static void subtreeSumGapFree(SCIP *scip, SUBTREESUMGAP **ssg)
Definition: event_estim.c:948
TREEPROFILESTATS lastestimatestats
Definition: event_estim.c:228
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
SUBTREESUMGAP * ssg
Definition: event_estim.c:305
static SCIP_RETCODE updateTreeData(SCIP *scip, TREEDATA *treedata, SCIP_NODE *node, int nchildren)
Definition: event_estim.c:1578
void ** SCIPpqueueElems(SCIP_PQUEUE *pqueue)
Definition: misc.c:1479
#define TABLE_POSITION
Definition: event_estim.c:102
int SCIPgetNRuns(SCIP *scip)
static SCIP_Bool isRestartApplicable(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2373
SCIP_Longint nleaves
Definition: event_estim.c:302
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BMSclearMemory(ptr)
Definition: memory.h:122
SCIP_NODE * SCIPgetFocusNode(SCIP *scip)
Definition: scip_tree.c:63
#define DISP_POSITION
Definition: event_estim.c:111
static SCIP_RETCODE subtreeSumGapSplit(SCIP *scip, SUBTREESUMGAP *ssg, SCIP_Bool addfocusnode)
Definition: event_estim.c:1045
#define DES_BETA_GAP
Definition: event_estim.c:123
public methods for variable pricer plugins
static SCIP_DECL_SORTPTRCOMP(compareNodeInfos)
Definition: event_estim.c:971
#define COMPLETIONTYPE_SSG
Definition: event_estim.c:143
int resolution
Definition: event_estim.c:344
TREEPROFILESTATS stats
Definition: event_estim.c:226
#define SCIP_REAL_MAX
Definition: def.h:178
public methods for nonlinear relaxation
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1236
#define COMPLETIONTYPE_MONOREG
Definition: event_estim.c:141
static SCIP_DECL_EVENTINIT(eventInitEstim)
Definition: event_estim.c:2644
SCIP_RETCODE SCIPincludeEventHdlrEstim(SCIP *scip)
Definition: event_estim.c:2878
RestartPolicy
Definition: event_estim.c:82
#define DES_BETA_LEAFFREQUENCY
Definition: event_estim.c:126
public methods for managing events
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3379
general public methods
#define DES_ALPHA_LEAFFREQUENCY
Definition: event_estim.c:125
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:158
SCIP_Real smoothestimation
Definition: event_estim.c:337
int subtreeidx
Definition: event_estim.c:355
public methods for solutions
SCIP_Longint nvisited
Definition: event_estim.c:303
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1335
SCIP_RETCODE SCIPrestartSolve(SCIP *scip)
Definition: scip_solve.c:3571
#define DEFAULT_RESTARTNONLINEAR
Definition: event_estim.c:252
SCIP_Real currentvalue
Definition: event_estim.c:339
static void doubleExpSmoothReset(DOUBLEEXPSMOOTH *des, SCIP_Real initialvalue)
Definition: event_estim.c:1653
public methods for message output
#define DEFAULT_USELEAFTS
Definition: event_estim.c:234
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition: scip_sol.c:1567
#define DISP_HEADER
Definition: event_estim.c:108
#define DES_BETA_TREEWEIGHT
Definition: event_estim.c:120
#define SCIPstatistic(x)
Definition: pub_message.h:111
SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7422
#define SCIP_Real
Definition: def.h:177
#define DES_ALPHA_TREEWEIGHT
Definition: event_estim.c:119
static SCIP_Bool shouldApplyRestart(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event_estim.c:2469
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:405
SCIP_Real beta
Definition: event_estim.c:168
public methods for message handling
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define SCIP_INVALID
Definition: def.h:197
#define SCIP_Longint
Definition: def.h:162
static SCIP_RETCODE subtreeSumGapComputeFromScratchEfficiently(SCIP *scip, SUBTREESUMGAP *ssg, SCIP_Bool updatescaling)
Definition: event_estim.c:1382
enum RestartPolicy RESTARTPOLICY
Definition: event_estim.c:90
#define RESTARTPOLICY_CHAR_ESTIMATION
Definition: event_estim.c:95
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
type definitions for message output methods
#define DISP_WIDTH
Definition: event_estim.c:109
SCIP_Real scalingfactor
Definition: event_estim.c:313
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define COMPLETIONTYPE_REGFOREST
Definition: event_estim.c:140
#define EVENTHDLR_NAME
Definition: event_estim.c:73
static SCIP_Real treeDataGetWbe(TREEDATA *treedata)
Definition: event_estim.c:1614
#define nnodes
Definition: gastrans.c:65
SCIP_Real initialvalue
Definition: event_estim.c:340
static void timeSeriesReset(TIMESERIES *timeseries)
Definition: event_estim.c:1720
static SCIP_DECL_EVENTINITSOL(eventInitsolEstim)
Definition: event_estim.c:2679
static SCIP_RETCODE getSearchCompletion(SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_Real *completed)
Definition: event_estim.c:2122
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3096
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIPallocBlockMemory(scip, subsol))
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:223
#define SCIP_ALLOC_TERMINATE(retcode, x, TERM)
Definition: def.h:415
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:325
#define ESTIMMETHOD_LFREQ
Definition: event_estim.c:152
#define DEFAULT_TREEPROFILE_MINNODESPERDEPTH
Definition: event_estim.c:246
#define DISP_NAME
Definition: event_estim.c:106
DOUBLEEXPSMOOTH des
Definition: event_estim.c:333
#define SCIP_ALLOC(x)
Definition: def.h:395
SCIP_Longint SCIPgetNNodes(SCIP *scip)
#define SCIPABORT()
Definition: def.h:356
const char * SCIPdispGetName(SCIP_DISP *disp)
Definition: disp.c:326
TsPos
Definition: event_estim.c:194
#define EVENTTYPE_ESTIM
Definition: event_estim.c:75
#define DEFAULT_SSG_NMINNODESLASTSPLIT
Definition: event_estim.c:258
SCIP_Longint nobs
Definition: event_estim.c:341
SCIP_Real targetvalue
Definition: event_estim.c:338
SCIP_Bool SCIPisInRestart(SCIP *scip)
Definition: scip_solve.c:3677
static SCIP_Real timeSeriesGetValue(TIMESERIES *timeseries)
Definition: event_estim.c:1804
#define TABLE_EARLIEST_STAGE
Definition: event_estim.c:103
#define DEFAULT_MINNODES
Definition: event_estim.c:249
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
#define EPSZ(x, eps)
Definition: def.h:207
#define COMPLETIONTYPE_TREEWEIGHT
Definition: event_estim.c:142
SCIP_Real * vals
Definition: event_estim.c:335
type definitions for displaying statistics tables
public methods for display handler plugins
#define DEFAULT_REPORTFREQ
Definition: event_estim.c:235
static SCIP_DECL_EVENTEXIT(eventExitEstim)
Definition: event_estim.c:2665
static SCIP_Real doubleExpSmoothGetTrend(DOUBLEEXPSMOOTH *des)
Definition: event_estim.c:1706
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define INITIALSIZE
Definition: event_estim.c:115
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
type definitions for displaying runtime statistics
static SCIP_Real timeSeriesEstimate(TIMESERIES *timeseries, TREEDATA *treedata)
Definition: event_estim.c:1833
memory allocation routines