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