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