Scippy

SCIP

Solving Constraint Integer Programs

event_solvingphase.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file event_solvingphase.c
17  * @ingroup DEFPLUGINS_EVENT
18  * @brief event handler for solving phase dependent parameter adjustment
19  * @author Gregor Hendel
20  *
21  * this event handler provides methods to support parameter adjustment at every new of the three solving phases:
22  * - Feasibility phase - before the first solution is found
23  * - Improvement phase - after the first solution was found until an optimal solution is found or believed to be found
24  * - Proof phase - the remaining time of the solution process after an optimal or believed-to-be optimal incumbent has been found.
25  *
26  * Of course, this event handler cannot detect by itself whether a given incumbent is optimal prior to termination of the
27  * solution process. It rather uses heuristic transitions based on properties of the search tree in order to
28  * determine the appropriate stage. Settings files can be passed to this event handler for each of the three phases.
29  *
30  * This approach of phase-based parameter adjustment was first presented in
31  *
32  * Gregor Hendel
33  * Empirical Analysis of Solving Phases in Mixed-Integer Programming
34  * Master thesis, Technical University Berlin (2014)
35  *
36  * with the main results also available from
37  *
38  * Gregor Hendel
39  * Exploiting solving phases in mixed-integer programs (2015)
40  */
41 
42 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 
45 #include "scip/pub_disp.h"
46 #include "scip/pub_event.h"
47 #include "scip/pub_message.h"
48 #include "scip/pub_misc.h"
49 #include "scip/pub_misc_sort.h"
50 #include "scip/pub_paramset.h"
51 #include "scip/pub_tree.h"
52 #include "scip/scip_disp.h"
53 #include "scip/scip_event.h"
54 #include "scip/scip_general.h"
55 #include "scip/scip_mem.h"
56 #include "scip/scip_message.h"
57 #include "scip/scip_numerics.h"
58 #include "scip/scip_param.h"
59 #include "scip/scip_sol.h"
60 #include "scip/scip_solve.h"
61 #include "scip/scip_solvingstats.h"
62 #include "scip/scip_timing.h"
63 #include "scip/scip_tree.h"
64 #include <string.h>
65 
66 #define EVENTHDLR_NAME "solvingphase"
67 #define EVENTHDLR_DESC "event handler to adjust settings depending on current stage"
68 
69 #define EVENTHDLR_EVENT SCIP_EVENTTYPE_BESTSOLFOUND | SCIP_EVENTTYPE_NODEBRANCHED | SCIP_EVENTTYPE_NODEFOCUSED /**< the actual event to be caught */
70 #define TRANSITIONMETHODS "elor" /**< which heuristic transition method: (e)stimate based, (l)ogarithmic regression based, (o)ptimal value based (cheat!),
71  * (r)ank-1 node based? */
72 #define DEFAULT_SETNAME "-" /**< default settings file name for solving phase setting files */
73 #define DEFAULT_TRANSITIONMETHOD 'r' /**< the default transition method */
74 #define DEFAULT_NODEOFFSET 50L /**< default node offset before transition to proof phase is active */
75 #define DEFAULT_FALLBACK FALSE /**< should the phase transition fall back to suboptimal phase? */
76 #define DEFAULT_INTERRUPTOPTIMAL FALSE /**< should solving process be interrupted if optimal solution was found? */
77 
78 #define DEFAULT_ENABLED FALSE /**< should the event handler be executed? */
79 #define DEFAULT_TESTMODE FALSE /**< should the event handler test the criteria? */
80 
81 #define DEFAULT_USERESTART1TO2 FALSE /**< should a restart be applied between the feasibility and improvement phase? */
82 #define DEFAULT_USERESTART2TO3 FALSE /**< should a restart be applied between the improvement and the proof phase? */
83 #define DEFAULT_USEEMPHSETTINGS TRUE /**< should emphasis settings be used for the different solving phases, or settings files? */
84 
85 /* logarithmic regression settings */
86 #define DEFAULT_LOGREGRESSION_XTYPE 'n' /**< default type to use for log regression - (t)ime, (n)odes, (l)p iterations */
87 #define LOGREGRESSION_XTYPES "lnt" /**< available types for log regression - (t)ime, (n)odes, (l)p iterations */
88 /*
89  * Data structures
90  */
91 
92 /** enumerator to represent the current solving phase */
93 enum SolvingPhase
94 {
95  SOLVINGPHASE_UNINITIALIZED = -1, /**< solving phase has not been initialized yet */
96  SOLVINGPHASE_FEASIBILITY = 0, /**< no solution was found until now */
97  SOLVINGPHASE_IMPROVEMENT = 1, /**< current incumbent solution is suboptimal */
98  SOLVINGPHASE_PROOF = 2 /**< current incumbent is optimal */
99 };
100 typedef enum SolvingPhase SOLVINGPHASE;
102 /** depth information structure */
103 struct DepthInfo
104 {
105  int nsolvednodes; /**< number of nodes that were solved so far at this depth */
106  SCIP_Real minestimate; /**< the minimum estimate of a solved node */
107  SCIP_NODE** minnodes; /**< points to the rank-1 nodes at this depth (open nodes whose estimate is lower than current
108  minimum estimate over solved nodes) */
109  int nminnodes; /**< the number of minimum nodes */
110  int minnodescapacity; /**< the capacity of the min nodes array */
111 };
112 
113 typedef struct DepthInfo DEPTHINFO;
115 /** event handler data */
116 struct SCIP_EventhdlrData
117 {
118  char logregression_xtype;/**< type to use for log regression - (t)ime, (n)odes, (l)p iterations */
119  SCIP_Bool enabled; /**< should the event handler be executed? */
120  char* feassetname; /**< settings file parameter for the feasibility phase -- precedence over emphasis settings */
121  char* improvesetname; /**< settings file parameter for the improvement phase -- precedence over emphasis settings */
122  char* proofsetname; /**< settings file parameter for the proof phase -- precedence over emphasis settings */
123  SCIP_Real optimalvalue; /**< value of optimal solution of the problem */
124  SCIP_Longint nnodesleft; /**< store the number of open nodes that are considered internally to update data */
125  SOLVINGPHASE solvingphase; /**< the current solving phase */
126  char transitionmethod; /**< transition method from improvement phase -> proof phase?
127  * (e)stimate based, (l)ogarithmic regression based, (o)ptimal value based (cheat!),
128  * (r)ank-1 node based */
129  SCIP_Longint nodeoffset; /**< node offset for triggering rank-1 node based phased transition */
130  SCIP_Longint lastndelayedcutoffs;/**< the number of delayed cutoffs since the last update of a focus node */
131  SCIP_Bool fallback; /**< should the phase transition fall back to improvement phase? */
132  SCIP_Bool interruptoptimal; /**< interrupt after optimal solution was found */
133  SCIP_Bool userestart1to2; /**< should a restart be applied between the feasibility and improvement phase? */
134  SCIP_Bool userestart2to3; /**< should a restart be applied between the improvement and the proof phase? */
135  SCIP_Bool useemphsettings; /**< should emphasis settings for the solving phases be used, or settings files? */
136 
137  SCIP_Bool testmode; /**< should transitions be tested only, but not triggered? */
138  SCIP_Bool rank1reached; /**< has the rank-1 transition into proof phase been reached? */
139  SCIP_Bool estimatereached; /**< has the best-estimate transition been reached? */
140  SCIP_Bool optimalreached; /**< is the incumbent already optimal? */
141  SCIP_Bool logreached; /**< has a logarithmic phase transition been reached? */
142  SCIP_Bool newbestsol; /**< has a new incumbent been found since the last node was solved? */
143 
144  SCIP_REGRESSION* regression; /**< regression data for log linear regression of the incumbent solutions */
145  SCIP_Real lastx; /**< X-value of last observation */
146  SCIP_Real lasty; /**< Y-value of last observation */
147  SCIP_PARAM** nondefaultparams; /**< parameters with non-default values during problem initialization */
148  int nnondefaultparams; /**< number of parameters with non-default values during problem initialization */
149  int nondefaultparamssize;/**< capacity of the array of non-default parameters */
150  int eventfilterpos; /**< the event filter position, or -1, if event has not (yet) been caught */
151  DEPTHINFO** depthinfos; /**< array of depth infos for every depth of the search tree */
152  int maxdepth; /**< maximum depth so far */
153  int nrank1nodes; /**< number of rank-1 nodes */
154  int nnodesbelowincumbent;/**< number of open nodes with an estimate lower than the current incumbent */
155 };
156 
157 
158 /*
159  * methods for rank-1 and active estimate transition
160  */
161 
162 /** nodes are sorted first by their estimates, and if estimates are equal, by their number */
163 static
164 SCIP_DECL_SORTPTRCOMP(sortCompTreeinfo)
165 {
166  SCIP_NODE* node1;
167  SCIP_NODE* node2;
168  SCIP_Real estim1;
169  SCIP_Real estim2;
170  node1 = (SCIP_NODE*)elem1;
171  node2 = (SCIP_NODE*)elem2;
172 
173  estim1 = SCIPnodeGetEstimate(node1);
174  estim2 = SCIPnodeGetEstimate(node2);
175 
176  /* compare estimates */
177  if( estim1 < estim2 )
178  return -1;
179  else if( estim1 > estim2 )
180  return 1;
181  else
182  {
183  SCIP_Longint number1;
184  SCIP_Longint number2;
185 
186  number1 = SCIPnodeGetNumber(node1);
187  number2 = SCIPnodeGetNumber(node2);
188 
189  /* compare numbers */
190  if( number1 < number2 )
191  return -1;
192  else if( number1 > number2 )
193  return 1;
194  }
195 
196  return 0;
197 }
198 
199 /** insert an array of open nodes (leaves/siblings/children) into the event handler data structures and update the transition information */
200 static
202  SCIP* scip, /**< SCIP data structure */
203  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
204  SCIP_NODE** nodes, /**< array of nodes */
205  int nnodes /**< number of nodes */
206  )
207 {
208  int n;
209 
210  assert(nnodes == 0 || nodes != NULL);
211  assert(scip != NULL);
212  assert(eventhdlrdata->depthinfos != NULL);
213 
214  /* store every relevant node in the data structure for its depth */
215  for( n = 0; n < nnodes; ++n )
216  {
217  SCIP_NODE* node = nodes[n];
218  DEPTHINFO* depthinfo = eventhdlrdata->depthinfos[SCIPnodeGetDepth(node)];
219  SCIP_Real estim = SCIPnodeGetEstimate(node);
220 
223 
224  /* an open node has rank 1 if it has an estimate at least as small as the best solved node at this depth */
225  if( depthinfo->nsolvednodes == 0 || SCIPisGE(scip, depthinfo->minestimate, SCIPnodeGetEstimate(node)) )
226  {
227  int pos;
228 
229  /* allocate additional memory to hold new node */
230  if( depthinfo->nminnodes == depthinfo->minnodescapacity )
231  {
232  int oldcapacity = depthinfo->minnodescapacity;
233  depthinfo->minnodescapacity *= 2;
234  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &depthinfo->minnodes, oldcapacity, depthinfo->minnodescapacity) );
235  }
236 
237  /* find correct insert position */
238  SCIPsortedvecInsertPtr((void **)depthinfo->minnodes, sortCompTreeinfo, (void*)node, &depthinfo->nminnodes, &pos);
239  assert(pos >= 0 && pos < depthinfo->nminnodes);
240  assert(depthinfo->minnodes[pos] == node);
241 
242  /* update rank 1 node information */
243  ++eventhdlrdata->nrank1nodes;
244  }
245 
246  /* update active estimate information by bookkeeping nodes with an estimate smaller than the current incumbent */
247  if( SCIPisLT(scip, estim, SCIPgetUpperbound(scip) ) )
248  ++eventhdlrdata->nnodesbelowincumbent;
249  }
250 
251  /* update the number of open search nodes */
252  eventhdlrdata->nnodesleft += nnodes;
253 
254  return SCIP_OKAY;
255 }
256 
257 /** remove a node from the data structures of the event handler */
258 static
259 void removeNode(
260  SCIP_NODE* node, /**< node that should be removed */
261  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
262  )
263 {
264  DEPTHINFO* depthinfo;
265  int pos;
266  SCIP_Bool contained;
267 
268  assert(node != NULL);
269 
270  /* get depth information for the depth of this node */
271  depthinfo = eventhdlrdata->depthinfos[SCIPnodeGetDepth(node)];
272 
273  /* no node is saved at this depth */
274  if( depthinfo->nminnodes == 0 )
275  return;
276 
277  /* search for the node by using binary search */
278  contained = SCIPsortedvecFindPtr((void **)depthinfo->minnodes, sortCompTreeinfo, (void *)node, depthinfo->nminnodes, &pos);
279 
280  /* remove the node if it is contained */
281  if( contained )
282  {
283  SCIPsortedvecDelPosPtr((void **)depthinfo->minnodes, sortCompTreeinfo, pos, &(depthinfo->nminnodes));
284  --eventhdlrdata->nrank1nodes;
285  }
286 }
287 
288 /** returns the current number of rank 1 nodes in the tree */
289 static
290 int getNRank1Nodes(
291  SCIP* scip /**< SCIP data structure */
292  )
293 {
294  SCIP_EVENTHDLRDATA* eventhdlrdata;
295 
296  assert(scip != NULL);
297 
298  eventhdlrdata = SCIPeventhdlrGetData(SCIPfindEventhdlr(scip, EVENTHDLR_NAME));
299 
300  /* return the stored number of rank 1 nodes only during solving stage */
301  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
302  return eventhdlrdata->nrank1nodes;
303  else
304  return -1;
305 }
306 
307 /** returns the current number of open nodes which have an estimate lower than the incumbent solution */
308 static
310  SCIP* scip /**< SCIP data structure */
311  )
312 {
313  SCIP_EVENTHDLRDATA* eventhdlrdata;
314 
315  assert(scip != NULL);
316 
317  eventhdlrdata = SCIPeventhdlrGetData(SCIPfindEventhdlr(scip, EVENTHDLR_NAME));
318 
319  /* return the stored number of nodes only during solving stage */
320  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
321  return eventhdlrdata->nnodesbelowincumbent;
322  else
323  return -1;
324 }
325 
326 /** discards all previous node information and renews it */
327 static
329  SCIP* scip, /**< SCIP data structure */
330  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
331  )
332 {
333  SCIP_NODE** leaves;
334  SCIP_NODE** children;
335  SCIP_NODE** siblings;
336 
337  int nleaves;
338  int nchildren;
339  int nsiblings;
340  int d;
341 
342  /* the required node information is only available after solving started */
343  if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING )
344  return SCIP_OKAY;
345 
346  assert(eventhdlrdata != NULL);
347 
348  /* reset depth information */
349  for( d = 0; d < eventhdlrdata->maxdepth; ++d )
350  eventhdlrdata->depthinfos[d]->nminnodes = 0;
351 
352  eventhdlrdata->nrank1nodes = 0;
353  eventhdlrdata->nnodesbelowincumbent = 0;
354  eventhdlrdata->nnodesleft = 0;
355 
356  nleaves = nchildren = nsiblings = 0;
357 
358  /* get leaves, children, and sibling arrays and update the event handler data structures */
359  SCIP_CALL( SCIPgetOpenNodesData(scip, &leaves, &children, &siblings, &nleaves, &nchildren, &nsiblings) );
360 
361  SCIP_CALL ( addNodesInformation(scip, eventhdlrdata, children, nchildren) );
362 
363  SCIP_CALL ( addNodesInformation(scip, eventhdlrdata, siblings, nsiblings) );
364 
365  SCIP_CALL ( addNodesInformation(scip, eventhdlrdata, leaves, nleaves) );
366 
367  /* information needs to be recomputed from scratch if a new incumbent is found */
368  eventhdlrdata->newbestsol = FALSE;
369 
370  return SCIP_OKAY;
371 }
372 
373 /** allocates memory for a depth info */
374 static
376  SCIP* scip, /**< SCIP data structure */
377  DEPTHINFO** depthinfo /**< pointer to depth information structure */
378  )
379 {
380  assert(scip != NULL);
381  assert(depthinfo != NULL);
382 
383  /* allocate the necessary memory */
384  SCIP_CALL( SCIPallocBlockMemory(scip, depthinfo) );
385 
386  /* reset the depth information */
387  (*depthinfo)->minestimate = SCIPinfinity(scip);
388  (*depthinfo)->nsolvednodes = 0;
389  (*depthinfo)->nminnodes = 0;
390  (*depthinfo)->minnodescapacity = 2;
391 
392  /* allocate array to store nodes */
393  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*depthinfo)->minnodes, (*depthinfo)->minnodescapacity) );
394 
395  return SCIP_OKAY;
396 }
397 
398 /** frees depth information data structure */
399 static
401  SCIP* scip, /**< SCIP data structure */
402  DEPTHINFO** depthinfo /**< pointer to depth information structure */
403  )
404 {
405  assert(scip != NULL);
406  assert(depthinfo != NULL);
407  assert(*depthinfo != NULL);
408  assert((*depthinfo)->minnodes != NULL);
409 
410  /* free nodes data structure and then the structure itself */
411  SCIPfreeBlockMemoryArray(scip, &(*depthinfo)->minnodes, (*depthinfo)->minnodescapacity);
412  SCIPfreeBlockMemory(scip, depthinfo);
413 
414  return SCIP_OKAY;
415 }
416 
417 /** removes the node itself and updates the data if this node defined an active estimate globally or locally at its depth level */
418 static
420  SCIP* scip, /**< SCIP data structure */
421  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
422  SCIP_NODE* node /**< node to be removed from the data structures of the event handler */
423  )
424 {
425  DEPTHINFO* depthinfo;
426 
427  assert(scip != NULL);
428  assert(node != NULL);
429  assert(eventhdlrdata != NULL);
430 
431  /* get the correct depth info at the node depth */
432  depthinfo = eventhdlrdata->depthinfos[SCIPnodeGetDepth(node)];
433  assert(depthinfo != NULL);
434 
435  /* remove the node from the data structures */
436  removeNode(node, eventhdlrdata);
437 
438  /* compare the node estimate to the minimum estimate of the particular depth */
439  if( SCIPisLT(scip, SCIPnodeGetEstimate(node), depthinfo->minestimate) )
440  depthinfo->minestimate = SCIPnodeGetEstimate(node);
441 
442  /* decrease counter of active estimate nodes if node has an estimate that is below the current incumbent */
443  if( SCIPisLT(scip, SCIPnodeGetEstimate(node), SCIPgetUpperbound(scip)) && SCIPnodeGetDepth(node) > 0 )
444  eventhdlrdata->nnodesbelowincumbent--;
445 
446  /* loop over remaining, unsolved nodes and decide whether they are still rank-1 nodes */
447  while( depthinfo->nminnodes > 0 && SCIPisGT(scip, SCIPnodeGetEstimate(depthinfo->minnodes[depthinfo->nminnodes - 1]), depthinfo->minestimate) )
448  {
449  /* forget about node */
450  --(depthinfo->nminnodes);
451  --(eventhdlrdata->nrank1nodes);
452  }
453 
454  /* increase the number of solved nodes at this depth */
455  ++(depthinfo->nsolvednodes);
456 
457  /* decrease the counter for the number of open nodes */
458  --eventhdlrdata->nnodesleft;
459 }
460 
461 /** ensures sufficient size for depthInfo array */
462 static
464  SCIP* scip, /**< SCIP data structure */
465  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
466  SCIP_NODE* node /**< node to be removed from the data structures of the event handler */
467  )
468 {
469  int nodedepth;
470  int newsize;
471  int oldsize;
472  nodedepth = SCIPnodeGetDepth(node);
473  oldsize = eventhdlrdata->maxdepth;
474  newsize = oldsize;
475 
476  /* create depth info array with small initial size or enlarge the existing array if new node is deeper */
477  if( oldsize == 0 )
478  {
479  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &eventhdlrdata->depthinfos, 10) );
480  newsize = 10;
481  }
482  else if( nodedepth + 1 >= eventhdlrdata->maxdepth )
483  {
484  assert(nodedepth > 0);
485  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &eventhdlrdata->depthinfos, oldsize, 2 * nodedepth) ); /*lint !e647*/
486  newsize = 2 * nodedepth;
487  }
488 
489  /* create the according depth information pointers */
490  if( newsize > oldsize )
491  {
492  int c;
493 
494  for( c = oldsize; c < newsize; ++c )
495  {
496  SCIP_CALL( createDepthinfo(scip, &(eventhdlrdata->depthinfos[c])) );
497  }
498 
499  eventhdlrdata->maxdepth = newsize;
500  }
501  assert(newsize > nodedepth);
502 
503  return SCIP_OKAY;
504 }
505 
506 /** ensures the capacity of the event handler data structures and removes the current node */
507 static
509  SCIP* scip, /**< SCIP data structure */
510  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
511  SCIP_NODE* node /**< node to be removed from the data structures of the event handler */
512  )
513 {
514  assert(scip != NULL);
515  assert(node != NULL);
516  assert(eventhdlrdata != NULL);
517 
518  /* ensure the depth info data structure can hold this node */
519  SCIP_CALL( ensureDepthInfoArraySize(scip, eventhdlrdata, node) );
520 
521  /* in case that selected nodes were cut off in between two calls to this method, build data structures from scratch again */
522  if( SCIPgetNDelayedCutoffs(scip) > eventhdlrdata->lastndelayedcutoffs || eventhdlrdata->newbestsol
523  || eventhdlrdata->nnodesleft - 1 != SCIPgetNNodesLeft(scip) )
524  {
525  SCIP_CALL( recomputeNodeInformation(scip, eventhdlrdata) );
526 
527  eventhdlrdata->lastndelayedcutoffs = SCIPgetNDelayedCutoffs(scip);
528  }
529  else
530  {
531  /* remove the node from the data structures */
532  releaseNodeFromDepthInfo(scip, eventhdlrdata, node);
533  }
534 
535  assert(eventhdlrdata->nnodesleft == SCIPgetNNodesLeft(scip));
536 
537  return SCIP_OKAY;
538 }
539 
540 #ifndef NDEBUG
541 /** ensures correctness of counters by explicitly summing up all children, leaves, and siblings with small estimates */
542 static
544  SCIP* scip
545  )
546 {
547  SCIP_NODE** nodes;
548  SCIP_RETCODE retcode;
549  int nnodes;
550  int n;
551  SCIP_Real upperbound = SCIPgetUpperbound(scip);
552  int nodesbelow = 0;
553 
554  /* compare children estimate and current upper bound */
555  retcode = SCIPgetChildren(scip, &nodes, &nnodes);
556  assert(retcode == SCIP_OKAY);
557 
558  for( n = 0; n < nnodes; ++n )
559  {
560  if( SCIPisLT(scip, SCIPnodeGetEstimate(nodes[n]), upperbound) )
561  ++nodesbelow;
562  }
563 
564  /* compare sibling estimate and current upper bound */
565  retcode = SCIPgetSiblings(scip, &nodes, &nnodes);
566  assert(retcode == SCIP_OKAY);
567 
568  for( n = 0; n < nnodes; ++n )
569  {
570  if( SCIPisLT(scip, SCIPnodeGetEstimate(nodes[n]), upperbound) )
571  ++nodesbelow;
572  }
573 
574  /* compare leaf node and current upper bound */
575  retcode = SCIPgetLeaves(scip, &nodes, &nnodes);
576  assert(retcode == SCIP_OKAY);
577 
578  for( n = 0; n < nnodes; ++n )
579  {
580  if( SCIPisLT(scip, SCIPnodeGetEstimate(nodes[n]), upperbound) )
581  ++nodesbelow;
582  }
583 
584  assert(nodesbelow <= SCIPgetNNodesLeft(scip));
585  return nodesbelow;
586 }
587 #endif
588 
589 /** get the point of the X axis for the regression according to the user choice of X type (time/nodes/iterations)*/
590 static
592  SCIP* scip, /**< SCIP data structure */
593  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
594  )
595 {
596  SCIP_Real x;
597 
598  switch( eventhdlrdata->logregression_xtype )
599  {
600  case 'l':
601  /* get number of LP iterations so far */
604  else
605  x = 1.0;
606  break;
607  case 'n':
608  /* get total number of solving nodes so far */
610  x = (SCIP_Real)SCIPgetNTotalNodes(scip);
611  else
612  x = 1.0;
613  break;
614  case 't':
615  /* get solving time */
616  x = SCIPgetSolvingTime(scip);
617  break;
618  default:
619  x = 1.0;
620  break;
621  }
622 
623  /* prevent the calculation of logarithm too close to zero */
624  x = MAX(x, .1);
625  x = log(x);
626 
627  return x;
628 }
629 
630 
631 
632 
633 
634 /** get axis intercept of current tangent to logarithmic regression curve */
635 static
637  SCIP* scip, /**< SCIP data structure */
638  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data structure */
639  )
640 {
641  SCIP_REGRESSION* regression;
642  SCIP_Real currentx;
643  SCIP_Real regressionslope;
644 
645  assert(scip != NULL);
646  assert(eventhdlrdata != NULL);
647 
648  regression = eventhdlrdata->regression;
649  assert(regression != NULL);
650 
651  /* don't rely on too few (<= 2) observations */
652  if( SCIPregressionGetNObservations(regression) <= 2 )
653  return SCIPinfinity(scip);
654 
655  currentx = getX(scip, eventhdlrdata);
656  regressionslope = SCIPregressionGetSlope(regression);
657 
658  return regressionslope * currentx + SCIPregressionGetIntercept(regression) - regressionslope;
659 }
660 
661 /*
662  * Local methods
663  */
664 
665 /** checks if rank-1 transition has been reached, that is, when all open nodes have a best-estimate higher than the best
666  * previously checked node at this depth
667  */
668 static
670  SCIP* scip, /**< SCIP data structure */
671  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
672  )
673 {
674  /* at least one solution is required for the transition */
675  if( SCIPgetNSols(scip) > 0 )
676  return (SCIPgetNNodes(scip) > eventhdlrdata->nodeoffset && getNRank1Nodes(scip) == 0);
677  else
678  return FALSE;
679 }
680 
681 /** check if Best-Estimate criterion was reached, that is, when the active estimate is not better than the current incumbent solution */
682 static
684  SCIP* scip, /**< SCIP data structure */
685  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
686  )
687 {
688  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
689 
690  if( SCIPgetNSols(scip) > 0 )
691  return ((SCIPgetNNodes(scip) > eventhdlrdata->nodeoffset) && (eventhdlrdata->nnodesbelowincumbent == 0));
692  else
693  return FALSE;
694 }
695 
696 /** check if logarithmic phase transition has been reached.
697  *
698  * the logarithmic phase transition is reached when the slope of the logarithmic primal progress (as a function of the number of
699  * LP iterations or solving nodes) becomes gentle. More concretely, we measure the slope by calculating the axis intercept of the tangent of
700  * the logarithmic primal progress. We then compare this axis intercept to the first and current primal bound and say that
701  * the logarithmic phase transition is reached as soon as the axis intercept passes the current primal bound so that the
702  * scalar becomes negative.
703  *
704  * While it would be enough to directly compare the primal bound and the axis intercept of the
705  * tangent to check the criterion, the scalar allows for a continuous indicator how far the phase transition is still ahead
706  */
707 static
709  SCIP* scip, /**< SCIP data structure */
710  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
711  )
712 {
713  if( SCIPgetNSols(scip) > 0 )
714  {
715  SCIP_Real axisintercept = getCurrentRegressionTangentAxisIntercept(scip, eventhdlrdata);
716  if( !SCIPisInfinity(scip, axisintercept) )
717  {
718  SCIP_Real primalbound;
719  SCIP_Real lambda;
720  SCIP_Real firstprimalbound = SCIPgetFirstPrimalBound(scip);
721 
722  primalbound = SCIPgetPrimalbound(scip);
723 
724  /* lambda is the scalar to describe the axis intercept as a linear combination of the current and the first primal bound
725  * as intercept = pb_0 + lambda * (pb - pb_0) */
726  lambda = (axisintercept - primalbound) / (firstprimalbound - primalbound);
727 
728  if( SCIPisNegative(scip, lambda) )
729  return TRUE;
730  }
731  }
732  return FALSE;
733 }
734 
735 /** check if incumbent solution is nearly optimal; we allow a relative deviation of 10^-9 */
736 static
738  SCIP* scip, /**< SCIP data structure */
739  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
740  )
741 {
742  SCIP_Real referencevalue;
743  SCIP_Real primalbound;
744 
745  referencevalue = eventhdlrdata->optimalvalue;
746  primalbound = SCIPgetPrimalbound(scip);
747 
748  if(!SCIPisInfinity(scip, REALABS(primalbound)) && !SCIPisInfinity(scip, referencevalue) )
749  {
750  SCIP_Real max = MAX3(1.0, REALABS(primalbound), REALABS(referencevalue)); /*lint !e666*/
751 
752  if( EPSZ((primalbound - referencevalue)/max, 1e-9) )
753  return TRUE;
754  }
755  return FALSE;
756 }
757 
758 /** check if we are in the proof phase */
759 static
761  SCIP* scip, /**< SCIP data structure */
762  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
763  )
764 {
765  if( eventhdlrdata->solvingphase == SOLVINGPHASE_PROOF && !eventhdlrdata->fallback )
766  return TRUE;
767 
768  /* check criterion based on selected transition method */
769  switch( eventhdlrdata->transitionmethod )
770  {
771  case 'r':
772 
773  /* check rank-1 transition */
774  if( checkRankOneTransition(scip, eventhdlrdata) )
775  {
776  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "reached rank-1 transition: nodes: %lld, rank-1: %d bound: %9.5g time: %.2f\n",
778  return TRUE;
779  }
780  break;
781  case 'o':
782 
783  /* cheat and use knowledge about optimal solution */
784  if( checkOptimalSolution(scip, eventhdlrdata) )
785  {
786  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "optimal solution found: %lld, bound: %9.5g time: %.2f\n",
788  return TRUE;
789  }
790  break;
791  case 'e':
792 
793  /* check best-estimate transition */
794  if( checkEstimateCriterion(scip, eventhdlrdata) )
795  {
796  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "reached best-estimate transition: nodes: %lld, estimate: %d bound: %9.5g time: %.2f\n",
797  SCIPgetNNodes(scip), eventhdlrdata->nnodesbelowincumbent, SCIPgetPrimalbound(scip), SCIPgetSolvingTime(scip));
798  return TRUE;
799  }
800  return FALSE;
801  case 'l':
802 
803  /* check logarithmic transition */
804  if( checkLogCriterion(scip, eventhdlrdata) )
805  {
806  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "reached a logarithmic phase transition: %.2f\n", SCIPgetSolvingTime(scip));
807  return TRUE;
808  }
809  break;
810  default:
811  return FALSE;
812  }
813 
814  return FALSE;
815 }
816 
817 /* determine the solving phase: feasibility phase if no solution was found yet, otherwise improvement phase or proof phase
818  * depending on whether selected transition criterion was already reached and fallback is active or not
819  */
820 static
822  SCIP* scip, /**< SCIP data structure */
823  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
824  )
825 {
826  /* without solution, we are in the feasibility phase */
827  if( SCIPgetNSols(scip) == 0 )
828  eventhdlrdata->solvingphase = SOLVINGPHASE_FEASIBILITY;
829  else if( eventhdlrdata->solvingphase != SOLVINGPHASE_PROOF || eventhdlrdata->fallback )
830  eventhdlrdata->solvingphase = SOLVINGPHASE_IMPROVEMENT;
831 
832  if( eventhdlrdata->solvingphase == SOLVINGPHASE_IMPROVEMENT && transitionPhase3(scip, eventhdlrdata) )
833  eventhdlrdata->solvingphase = SOLVINGPHASE_PROOF;
834 }
835 
836 /** changes parameters by using emphasis settings */
837 static
839  SCIP* scip, /**< SCIP data structure */
840  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
841  )
842 {
843  SCIP_PARAMEMPHASIS paramemphasis;
844 
845  /* choose the appropriate emphasis settings for the new solving phase */
846  switch(eventhdlrdata->solvingphase)
847  {
849  paramemphasis = SCIP_PARAMEMPHASIS_PHASEFEAS;
850  break;
852  paramemphasis = SCIP_PARAMEMPHASIS_PHASEIMPROVE;
853  break;
854  case SOLVINGPHASE_PROOF:
855  paramemphasis = SCIP_PARAMEMPHASIS_PHASEPROOF;
856  break;
858  default:
859  SCIPdebugMsg(scip, "Unknown solving phase: %d -> ABORT!\n ", eventhdlrdata->solvingphase);
860  SCIPABORT();
861  paramemphasis = SCIP_PARAMEMPHASIS_DEFAULT;
862  break;
863  }
864 
865  SCIP_CALL( SCIPsetEmphasis(scip, paramemphasis, FALSE) );
866 
867  return SCIP_OKAY;
868 }
869 
870 /** change general solving strategy of SCIP depending on the phase by reading from settings file */
871 static
873  SCIP* scip, /**< SCIP data structure */
874  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
875  )
876 {
877  FILE* file;
878  char* paramfilename = NULL;
879 
880  /* choose the settings file for the new solving phase */
881  switch(eventhdlrdata->solvingphase)
882  {
884  paramfilename = eventhdlrdata->feassetname;
885  break;
887  paramfilename = eventhdlrdata->improvesetname;
888  break;
889  case SOLVINGPHASE_PROOF:
890  paramfilename = eventhdlrdata->proofsetname;
891  break;
893  default:
894  SCIPdebugMsg(scip, "Unknown solving phase: %d -> ABORT!\n ", eventhdlrdata->solvingphase);
895  return SCIP_INVALIDCALL;
896  }
897 
898  assert(paramfilename != NULL);
899 
900  /* return if no there is no user-specified settings file for the current phase */
901  if( strcmp(paramfilename, DEFAULT_SETNAME) == 0 )
902  return SCIP_OKAY;
903 
904  file = fopen(paramfilename, "r");
905 
906  /* test if file could be found and print a warning if not */
907  if( file == NULL )
908  {
909  SCIPwarningMessage(scip, "Parameter file <%s> not found--keeping settings as before.\n", paramfilename);
910  }
911  else
912  {
913  /* we can close the file */
914  fclose(file);
915 
916  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Reading parameters from file <%s>\n", paramfilename);
917 
918  SCIP_CALL( SCIPreadParams(scip, paramfilename) );
919  }
920 
921  return SCIP_OKAY;
922 } /*lint !e593*/
923 
924 /** fix/unfix relevant solving parameters that should not accidentally be set to default values */
925 static
927  SCIP* scip, /**< SCIP data structure */
928  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< event handler data */
929  SCIP_Bool fix /**< should the parameters be fixed (true) or unfixed? */
930  )
931 {
932  int p;
933  const char* relevantparams[] = {
934  "limits/time",
935  "limits/nodes",
936  "limits/totalnodes",
937  "limits/stallnodes",
938  "limits/memory",
939  "limits/gap",
940  "limits/absgap",
941  "limits/solutions",
942  "limits/bestsol",
943  "limits/maxsol",
944  "limits/maxorigsol",
945  "limits/restarts",
946  "limits/autorestartnodes",
947  "limits/softtime",
948  "solvingphases/enabled",
949  "solvingphases/fallback",
950  "solvingphases/interruptoptimal",
951  "solvingphases/nodeoffset",
952  "solvingphases/feassetname",
953  "solvingphases/proofsetname",
954  "solvingphases/optimalvalue",
955  "solvingphases/improvesetname",
956  "solvingphases/testmode",
957  "solvingphases/transitionmethod",
958  "solvingphases/useemphsettings",
959  "solvingphases/userestart1to2",
960  "solvingphases/userestart2to3",
961  "solvingphases/xtype"
962  };
963  int nrelevantparams = 28;
964 
965  /* fix or unfix all specified limit parameters */
966  for( p = 0; p < nrelevantparams; ++p )
967  {
968  if( fix )
969  {
970  SCIP_CALL( SCIPfixParam(scip, relevantparams[p]) );
971  }
972  else
973  {
974  SCIP_CALL( SCIPunfixParam(scip, relevantparams[p]) );
975  }
976  }
977 
978  /* fix or unfix all collected, non-default parameters after problem transformation */
979  for( p = 0; p < eventhdlrdata->nnondefaultparams; ++p )
980  {
981  if( fix && ! SCIPparamIsFixed(eventhdlrdata->nondefaultparams[p]) )
982  {
983  SCIP_CALL( SCIPfixParam(scip, SCIPparamGetName(eventhdlrdata->nondefaultparams[p])) );
984  }
985  else if( ! fix && SCIPparamIsFixed(eventhdlrdata->nondefaultparams[p]) )
986  {
987  SCIP_CALL( SCIPunfixParam(scip, SCIPparamGetName(eventhdlrdata->nondefaultparams[p])) );
988  }
989  }
990 
991  return SCIP_OKAY;
992 }
993 
994 /** change settings depending whether emphasis settings should be used, or settings files */
995 static
997  SCIP* scip, /**< SCIP data structure */
998  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
999  )
1000 {
1001  /* fix relevant parameters such that they are not overwritten */
1002  SCIP_CALL( fixOrUnfixRelevantParameters(scip, eventhdlrdata, TRUE) );
1003 
1004  /* change settings using emphasis */
1005  if( eventhdlrdata->useemphsettings )
1006  {
1007  SCIP_CALL( changeEmphasisParameters(scip, eventhdlrdata) );
1008  }
1009  else
1010  {
1011  /* reset to default settings; this happens automatically when using emphasis settings */
1013  }
1014 
1015  /* read optional, phase-specific settings */
1016  SCIP_CALL( changeParametersUsingSettingsFiles(scip, eventhdlrdata) );
1017 
1018  /* unfix relevant parameters that have been fixed for changing emphasis */
1019  SCIP_CALL( fixOrUnfixRelevantParameters(scip, eventhdlrdata, FALSE) );
1020 
1021  return SCIP_OKAY;
1022 }
1023 
1024 /* apply the user-specified phase-based settings: A phase transition invokes the read of phase-specific settings from a file */
1025 static
1027  SCIP* scip, /**< SCIP data structure */
1028  SCIP_EVENTHDLRDATA* eventhdlrdata /**< event handler data */
1029  )
1030 {
1031  SOLVINGPHASE oldsolvingphase;
1032  SCIP_Bool restart;
1033 
1034  /* return immediately if we are in the proof phase */
1035  if( eventhdlrdata->solvingphase == SOLVINGPHASE_PROOF && !eventhdlrdata->fallback )
1036  return SCIP_OKAY;
1037 
1038  /* save current solving phase */
1039  oldsolvingphase = eventhdlrdata->solvingphase;
1040 
1041  /* determine current solving phase */
1042  determineSolvingPhase(scip, eventhdlrdata);
1043 
1044  /* nothing has changed */
1045  if( oldsolvingphase == eventhdlrdata->solvingphase )
1046  return SCIP_OKAY;
1047 
1048  /* check if the solving process should be interrupted when the current solution is optimal */
1049  if( eventhdlrdata->solvingphase == SOLVINGPHASE_PROOF && eventhdlrdata->transitionmethod == 'o' &&
1050  eventhdlrdata->interruptoptimal )
1051  {
1052  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Solution is optimal. Calling user interruption.\n");
1053 
1054  /* we call interrupt solve but do not return yet because user-specified settings for the proof phase are applied first */
1055  SCIP_CALL( SCIPinterruptSolve(scip) );
1056  }
1057 
1058  /* check if a restart should be performed after phase transition */
1059  if( eventhdlrdata->solvingphase == SOLVINGPHASE_IMPROVEMENT && eventhdlrdata->userestart1to2 )
1060  restart = TRUE;
1061  else if( eventhdlrdata->solvingphase == SOLVINGPHASE_PROOF && eventhdlrdata->userestart2to3 )
1062  restart = TRUE;
1063  else
1064  restart = FALSE;
1065 
1066  /* inform SCIP that a restart should be performed */
1067  if( restart )
1068  {
1069  SCIP_CALL( SCIPrestartSolve(scip) );
1070  }
1071 
1072  /* change general solving settings depending on solving strategy */
1073  SCIP_CALL( adaptSolverBehavior(scip, eventhdlrdata) );
1074 
1075  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,"Changed solving phase to phase %d.\n", eventhdlrdata->solvingphase);
1076 
1077  return SCIP_OKAY;
1078 }
1079 
1080 /** update the logarithmic regression */
1081 static
1083  SCIP* scip, /**< SCIP data structure */
1084  SCIP_EVENTHDLRDATA* eventhdlrdata /**< data of event handler */
1085  )
1086 {
1087  SCIP_Real regressionx;
1088  SCIP_Real regressiony;
1089 
1090  regressionx = getX(scip, eventhdlrdata);
1091  regressiony = SCIPgetPrimalbound(scip);
1092 
1093  /* remove the last observation if it has been observed at the same x */
1094  if( SCIPisEQ(scip, eventhdlrdata->lastx, regressionx) )
1095  {
1096  SCIPregressionRemoveObservation(eventhdlrdata->regression, eventhdlrdata->lastx, eventhdlrdata->lasty);
1097  }
1098 
1099  /* add the new observation to the regression and save it if another update is necessary */
1100  SCIPregressionAddObservation(eventhdlrdata->regression, regressionx, regressiony);
1101  eventhdlrdata->lastx = regressionx;
1102  eventhdlrdata->lasty = regressiony;
1103 
1104  return SCIP_OKAY;
1105 }
1106 
1107 /** update data structures based on the event type caught */
1108 static
1110  SCIP* scip, /**< SCIP data structure */
1111  SCIP_EVENTHDLRDATA* eventhdlrdata, /**< data of event handler */
1112  SCIP_EVENTTYPE eventtype /**< type of the caught event */
1113  )
1114 {
1115  SCIP_NODE** children;
1116  int nchildren;
1117 
1118  switch( eventtype )
1119  {
1120  /* store that a new best solution was found, but delay the update of node information until a node was solved */
1122  eventhdlrdata->newbestsol = TRUE;
1123 
1124  /* update logarithmic regression of solution process */
1125  SCIP_CALL( updateLogRegression(scip, eventhdlrdata) );
1126 
1127  break;
1128 
1129  /* release the focus node from the open node data structures */
1131  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1132 
1133  SCIP_CALL( releaseNodeInformation(scip, eventhdlrdata, SCIPgetCurrentNode(scip)));
1134  assert(eventhdlrdata->nnodesbelowincumbent <= SCIPgetNNodesLeft(scip));
1135 
1136  break;
1137 
1138  /* store node information for child nodes */
1140  assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING);
1141 
1142  /* if we lost track of exact number of open search nodes, we recompute node information from scratch */
1143  if( eventhdlrdata->newbestsol || eventhdlrdata->nnodesleft + SCIPgetNChildren(scip) != SCIPgetNNodesLeft(scip) )
1144  {
1145  SCIP_CALL( recomputeNodeInformation(scip, eventhdlrdata) );
1146  eventhdlrdata->newbestsol = FALSE;
1147 
1148  return SCIP_OKAY;
1149  }
1150  else
1151  {
1152  SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) );
1153  SCIP_CALL( addNodesInformation(scip, eventhdlrdata, children, nchildren) );
1154  }
1155 
1156  assert(eventhdlrdata->nnodesleft == SCIPgetNNodesLeft(scip));
1157  break;
1158 
1159  default:
1160  break;
1161  }
1162 
1163  /* ensure that required tree information was correctly computed; only available in solving stage and at the beginning
1164  * or end of a node solution process because we delay the recomputation of the node information)
1165  */
1166  assert(SCIPgetStage(scip) != SCIP_STAGE_SOLVING ||
1167  (eventtype == SCIP_EVENTTYPE_BESTSOLFOUND) ||
1168  (eventhdlrdata->nnodesleft == SCIPgetNNodesLeft(scip) && eventhdlrdata->nnodesbelowincumbent == checkLeavesBelowIncumbent(scip)));
1169 
1170  return SCIP_OKAY;
1171 }
1172 
1173 /** test all criteria whether they have been reached */
1174 static
1175 void testCriteria(
1176  SCIP* scip, /**< SCIP data structure */
1177  SCIP_EVENTHDLRDATA* eventhdlrdata /**< data of event handler */
1178  )
1179 {
1180  assert(scip != NULL);
1181  assert(eventhdlrdata != NULL);
1182 
1183  if( ! eventhdlrdata->logreached && checkLogCriterion(scip, eventhdlrdata) )
1184  {
1185  eventhdlrdata->logreached = TRUE;
1186  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Log criterion reached after %lld nodes, %.2f sec.\n",
1187  SCIPgetNNodes(scip), SCIPgetSolvingTime(scip));
1188  }
1189  if( ! eventhdlrdata->rank1reached && checkRankOneTransition(scip, eventhdlrdata) )
1190  {
1191  eventhdlrdata->rank1reached = TRUE;
1192  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Rank 1 criterion reached after %lld nodes, %.2f sec.\n",
1193  SCIPgetNNodes(scip), SCIPgetSolvingTime(scip));
1194  }
1195 
1196  if( ! eventhdlrdata->estimatereached && checkEstimateCriterion(scip, eventhdlrdata) )
1197  {
1198  eventhdlrdata->estimatereached = TRUE;
1199  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Estimate criterion reached after %lld nodes, %.2f sec.\n",
1200  SCIPgetNNodes(scip), SCIPgetSolvingTime(scip));
1201  }
1202 
1203  if( ! eventhdlrdata->optimalreached && checkOptimalSolution(scip, eventhdlrdata) )
1204  {
1205  eventhdlrdata->optimalreached = TRUE;
1206  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Optimum reached after %lld nodes, %.2f sec.\n",
1207  SCIPgetNNodes(scip), SCIPgetSolvingTime(scip));
1208  }
1209 }
1210 
1211 /*
1212  * Callback methods of event handler
1213  */
1214 
1215 /** copy method for event handler (called when SCIP copies plugins) */
1216 /* todo this code needs to stay disabled as long as the soft limit event handler is not copied, because we save
1217  * the soft time limit parameter but this will crash as soon as we are in a SCIP copy */
1218 #ifdef SCIP_DISABLED_CODE
1219 static
1221 { /*lint --e{715}*/
1222  assert(scip != NULL);
1223  assert(eventhdlr != NULL);
1224  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1225 
1226  /* call inclusion method of event handler */
1228 
1229  return SCIP_OKAY;
1230 }
1231 #else
1232 #define eventCopySolvingphase NULL
1233 #endif
1234 
1235 /** destructor of event handler to free user data (called when SCIP is exiting) */
1236 static
1237 SCIP_DECL_EVENTFREE(eventFreeSolvingphase)
1239  SCIP_EVENTHDLRDATA* eventhdlrdata;
1240 
1241  assert(scip != NULL);
1242  assert(eventhdlr != NULL);
1243  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1244 
1245  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1246  assert(eventhdlrdata != NULL);
1247 
1248  SCIPregressionFree(&eventhdlrdata->regression);
1249 
1250  SCIPfreeBlockMemory(scip, &eventhdlrdata);
1251  SCIPeventhdlrSetData(eventhdlr, NULL);
1252 
1253  return SCIP_OKAY;
1254 }
1255 
1256 /** initialization method of event handler (called after problem was transformed) */
1257 static
1258 SCIP_DECL_EVENTINITSOL(eventInitsolSolvingphase)
1259 { /*lint --e{715}*/
1260  SCIP_EVENTHDLRDATA* eventhdlrdata;
1261 
1262  assert(scip != NULL);
1263  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1264  eventhdlrdata->depthinfos = NULL;
1265  eventhdlrdata->maxdepth = 0;
1266  eventhdlrdata->nnodesbelowincumbent = 0;
1267  eventhdlrdata->nnodesleft = 0;
1268  eventhdlrdata->nrank1nodes = 0;
1269  eventhdlrdata->lastndelayedcutoffs = SCIPgetNDelayedCutoffs(scip);
1270  eventhdlrdata->newbestsol = FALSE;
1271 
1272  return SCIP_OKAY;
1273 }
1274 
1275 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
1276 static
1277 SCIP_DECL_EVENTEXITSOL(eventExitsolSolvingphase)
1279  SCIP_EVENTHDLRDATA* eventhdlrdata;
1280 
1281  assert(scip != NULL);
1282  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1283 
1284  /* free all data storage acquired during this branch-and-bound run */
1285  if( eventhdlrdata->maxdepth > 0 )
1286  {
1287  int c;
1288 
1289  /* free depth information */
1290  for( c = 0; c < eventhdlrdata->maxdepth; ++c )
1291  {
1292  SCIP_CALL( freeDepthinfo(scip, &(eventhdlrdata->depthinfos[c])) );
1293  }
1294 
1295  /* free depth information array */
1296  SCIPfreeBlockMemoryArray(scip, &eventhdlrdata->depthinfos, eventhdlrdata->maxdepth);
1297  eventhdlrdata->maxdepth = 0;
1298  }
1299 
1300  return SCIP_OKAY;
1301 }
1302 
1303 /** collects all parameters that are set to non-default values and stores them in eventhdlrdata */
1304 static
1306  SCIP* scip, /**< SCIP data structure */
1307  SCIP_EVENTHDLRDATA* eventhdlrdata /**< data of event handler */
1308  )
1309 {
1310  SCIP_PARAM** params;
1311  int nparams;
1312  int p;
1313 
1314  params = SCIPgetParams(scip);
1315  nparams = SCIPgetNParams(scip);
1316 
1317  eventhdlrdata->nnondefaultparams = 0;
1318  eventhdlrdata->nondefaultparams = NULL;
1319  eventhdlrdata->nondefaultparamssize = 0;
1320 
1321  /* loop over parameters and store the non-default ones */
1322  for( p = 0; p < nparams; ++p )
1323  {
1324  SCIP_PARAM* param = params[p];
1325 
1326  /* collect parameter if it is nondefault */
1327  if( ! SCIPparamIsDefault(param) )
1328  {
1329  if( eventhdlrdata->nnondefaultparams == 0 )
1330  {
1331  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &eventhdlrdata->nondefaultparams, 8) );
1332  eventhdlrdata->nondefaultparamssize = 8;
1333  }
1334  else if( eventhdlrdata->nnondefaultparams == eventhdlrdata->nondefaultparamssize )
1335  {
1336  eventhdlrdata->nondefaultparamssize *= 2;
1337  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &eventhdlrdata->nondefaultparams, \
1338  eventhdlrdata->nnondefaultparams, eventhdlrdata->nondefaultparamssize) );
1339  }
1340 
1341  eventhdlrdata->nondefaultparams[eventhdlrdata->nnondefaultparams++] = param;
1342  }
1343  }
1344 
1345  return SCIP_OKAY;
1346 }
1347 
1348 /** initialization method of event handler (called after problem was transformed) */
1349 static
1350 SCIP_DECL_EVENTINIT(eventInitSolvingphase)
1351 { /*lint --e{715}*/
1352  SCIP_EVENTHDLRDATA* eventhdlrdata;
1353 
1354  assert(scip != NULL);
1355  assert(eventhdlr != NULL);
1356  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1357 
1358  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1359  assert(eventhdlrdata != NULL);
1360 
1361  /* initialize the solving phase */
1362  eventhdlrdata->solvingphase = SOLVINGPHASE_UNINITIALIZED;
1363 
1364  /* none of the transitions is reached yet */
1365  eventhdlrdata->optimalreached = FALSE;
1366  eventhdlrdata->logreached = FALSE;
1367  eventhdlrdata->rank1reached = FALSE;
1368  eventhdlrdata->estimatereached = FALSE;
1369  eventhdlrdata->nnondefaultparams = 0;
1370  eventhdlrdata->nondefaultparams = NULL;
1371  eventhdlrdata->nondefaultparamssize = 0;
1372 
1373  /* apply solving phase for the first time after problem was transformed to apply settings for the feasibility phase */
1374  if( eventhdlrdata->enabled )
1375  {
1376  /* collect non-default parameters */
1377  SCIP_CALL( collectNondefaultParams(scip, eventhdlrdata) );
1378 
1379  SCIP_CALL( applySolvingPhase(scip, eventhdlrdata) );
1380  }
1381 
1382  /* only start catching events if event handler is enabled or in test mode */
1383  if( eventhdlrdata->enabled || eventhdlrdata->testmode )
1384  {
1385  SCIP_CALL( SCIPcatchEvent(scip, EVENTHDLR_EVENT, eventhdlr, NULL, &eventhdlrdata->eventfilterpos) );
1386  }
1387 
1388  /* reset solving regression */
1389  SCIPregressionReset(eventhdlrdata->regression);
1390  eventhdlrdata->lastx = SCIP_INVALID;
1391  eventhdlrdata->lasty = SCIP_INVALID;
1392 
1393  return SCIP_OKAY;
1394 }
1395 /** deinitialization method of event handler (called before problem is freed) */
1396 static
1397 SCIP_DECL_EVENTEXIT(eventExitSolvingphase)
1399  SCIP_EVENTHDLRDATA* eventhdlrdata;
1400 
1401  assert(scip != NULL);
1402  assert(eventhdlr != NULL);
1403  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1404 
1405  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1406  assert(eventhdlrdata != NULL);
1407 
1408  /* free collected, non-default parameters */
1409  SCIPfreeBlockMemoryArrayNull(scip, &eventhdlrdata->nondefaultparams, eventhdlrdata->nondefaultparamssize);
1410 
1411  return SCIP_OKAY;
1412 }
1413 
1414 
1415 /** execution method of event handler */
1416 static
1417 SCIP_DECL_EVENTEXEC(eventExecSolvingphase)
1418 { /*lint --e{715}*/
1419  SCIP_EVENTHDLRDATA* eventhdlrdata;
1420  SCIP_EVENTTYPE eventtype;
1421 
1422  assert(scip != NULL);
1423  assert(eventhdlr != NULL);
1424 
1425  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
1426  eventtype = SCIPeventGetType(event);
1427  assert(eventtype & (EVENTHDLR_EVENT));
1428  assert(eventtype != SCIP_EVENTTYPE_NODEFOCUSED || SCIPeventGetNode(event) == SCIPgetCurrentNode(scip));
1429 
1430  /* update data structures depending on the event */
1431  SCIP_CALL( updateDataStructures(scip, eventhdlrdata, eventtype) );
1432 
1433  /* if the phase-based solver is enabled, we check if a phase transition occurred and alter the settings accordingly */
1434  if( eventhdlrdata->enabled )
1435  {
1436  SCIP_CALL( applySolvingPhase(scip, eventhdlrdata) );
1437  }
1438 
1439  /* in test mode, we check every transition criterion */
1440  if( eventhdlrdata->testmode )
1441  {
1442  testCriteria(scip, eventhdlrdata);
1443  }
1444 
1445  return SCIP_OKAY;
1446 }
1447 
1448 /*
1449  * displays that come with this event handler
1450  */
1451 
1452 /* defines for the rank 1 node display */
1453 #define DISP_NAME_NRANK1NODES "nrank1nodes"
1454 #define DISP_DESC_NRANK1NODES "current number of rank1 nodes left"
1455 #define DISP_HEAD_NRANK1NODES "rank1"
1456 #define DISP_WIDT_NRANK1NODES 7
1457 #define DISP_PRIO_NRANK1NODES 40000
1458 #define DISP_POSI_NRANK1NODES 500
1459 #define DISP_STRI_NRANK1NODES TRUE
1461 /** output method of display column to output file stream 'file' */
1462 static
1463 SCIP_DECL_DISPOUTPUT(dispOutputNRank1Nodes)
1465  assert(disp != NULL);
1466  assert(strcmp(SCIPdispGetName(disp), DISP_NAME_NRANK1NODES) == 0);
1467  assert(scip != NULL);
1468 
1469  /* ouput number of rank 1 nodes */
1471 
1472  return SCIP_OKAY;
1473 }
1474 
1475 /* display for the number of nodes below the current incumbent */
1476 #define DISP_NAME_NNODESBELOWINC "nnodesbelowinc"
1477 #define DISP_DESC_NNODESBELOWINC "current number of nodes with an estimate better than the current incumbent"
1478 #define DISP_HEAD_NNODESBELOWINC "nbInc"
1479 #define DISP_WIDT_NNODESBELOWINC 6
1480 #define DISP_PRIO_NNODESBELOWINC 40000
1481 #define DISP_POSI_NNODESBELOWINC 550
1482 #define DISP_STRI_NNODESBELOWINC TRUE
1484 /** output method of display column to output file stream 'file' */
1485 static
1486 SCIP_DECL_DISPOUTPUT(dispOutputNnodesbelowinc)
1488  assert(disp != NULL);
1489  assert(strcmp(SCIPdispGetName(disp), DISP_NAME_NNODESBELOWINC) == 0);
1490  assert(scip != NULL);
1491 
1492  /* display the number of nodes with an estimate below the the current incumbent */
1494 
1495  return SCIP_OKAY;
1496 }
1497 
1498 /** creates event handler for Solvingphase event */
1500  SCIP* scip /**< SCIP data structure */
1501  )
1502 {
1503  SCIP_EVENTHDLRDATA* eventhdlrdata;
1504  SCIP_EVENTHDLR* eventhdlr;
1505 
1506  /* create solving phase event handler data */
1507  eventhdlrdata = NULL;
1508  SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata) );
1509  assert(eventhdlrdata != NULL);
1510 
1511  eventhdlrdata->feassetname = NULL;
1512  eventhdlrdata->improvesetname = NULL;
1513  eventhdlrdata->proofsetname = NULL;
1514 
1515  eventhdlrdata->depthinfos = NULL;
1516  eventhdlrdata->maxdepth = 0;
1517  eventhdlrdata->eventfilterpos = -1;
1518 
1519  /* create a regression */
1520  eventhdlrdata->regression = NULL;
1521  SCIP_CALL( SCIPregressionCreate(&eventhdlrdata->regression) );
1522 
1523  eventhdlr = NULL;
1524 
1525  /* include event handler into SCIP */
1527  eventExecSolvingphase, eventhdlrdata) );
1528  assert(eventhdlr != NULL);
1529 
1530  /* include the new displays into scip */
1537 
1538  /* set non fundamental callbacks via setter functions */
1540  SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeSolvingphase) );
1541  SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitSolvingphase) );
1542  SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitSolvingphase) );
1543  SCIP_CALL( SCIPsetEventhdlrInitsol(scip, eventhdlr, eventInitsolSolvingphase) );
1544  SCIP_CALL( SCIPsetEventhdlrExitsol(scip, eventhdlr, eventExitsolSolvingphase) );
1545 
1546  /* add Solvingphase event handler parameters */
1547  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/enabled", "should the event handler adapt the solver behavior?",
1548  &eventhdlrdata->enabled, FALSE, DEFAULT_ENABLED, NULL, NULL) );
1549 
1550  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/testmode", "should the event handler test all phase transitions?",
1551  &eventhdlrdata->testmode, FALSE, DEFAULT_TESTMODE, NULL, NULL) );
1552 
1553  SCIP_CALL( SCIPaddStringParam(scip, EVENTHDLR_NAME "s/feassetname", "settings file for feasibility phase -- precedence over emphasis settings",
1554  &eventhdlrdata->feassetname, FALSE, DEFAULT_SETNAME, NULL, NULL) );
1555 
1556  SCIP_CALL( SCIPaddStringParam(scip, EVENTHDLR_NAME "s/improvesetname", "settings file for improvement phase -- precedence over emphasis settings",
1557  &eventhdlrdata->improvesetname, FALSE, DEFAULT_SETNAME, NULL, NULL) );
1558 
1559  SCIP_CALL( SCIPaddStringParam(scip, EVENTHDLR_NAME "s/proofsetname", "settings file for proof phase -- precedence over emphasis settings",
1560  &eventhdlrdata->proofsetname, FALSE, DEFAULT_SETNAME, NULL, NULL) );
1561 
1562  SCIP_CALL( SCIPaddLongintParam(scip, EVENTHDLR_NAME "s/nodeoffset", "node offset for rank-1 and estimate transitions", &eventhdlrdata->nodeoffset,
1564  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/fallback", "should the event handler fall back from optimal phase?",
1565  &eventhdlrdata->fallback, FALSE, DEFAULT_FALLBACK, NULL, NULL) );
1566  SCIP_CALL( SCIPaddCharParam(scip ,EVENTHDLR_NAME "s/transitionmethod",
1567  "transition method: Possible options are 'e'stimate,'l'ogarithmic regression,'o'ptimal-value based,'r'ank-1",
1568  &eventhdlrdata->transitionmethod, FALSE, DEFAULT_TRANSITIONMETHOD, TRANSITIONMETHODS, NULL, NULL) );
1569  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/interruptoptimal",
1570  "should the event handler interrupt the solving process after optimal solution was found?",
1571  &eventhdlrdata->interruptoptimal, FALSE, DEFAULT_INTERRUPTOPTIMAL, NULL, NULL) );
1572 
1573  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/userestart1to2",
1574  "should a restart be applied between the feasibility and improvement phase?",
1575  &eventhdlrdata->userestart1to2, FALSE, DEFAULT_USERESTART1TO2, NULL, NULL) );
1576 
1577  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/userestart2to3",
1578  "should a restart be applied between the improvement and the proof phase?",
1579  &eventhdlrdata->userestart2to3, FALSE, DEFAULT_USERESTART2TO3, NULL, NULL) );
1580 
1581  SCIP_CALL(SCIPaddRealParam(scip, EVENTHDLR_NAME "s/optimalvalue", "optimal solution value for problem",
1582  &eventhdlrdata->optimalvalue, FALSE, SCIP_INVALID, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1583 
1584  /* add parameter for logarithmic regression */
1585  SCIP_CALL( SCIPaddCharParam(scip, EVENTHDLR_NAME "s/xtype", "x-type for logarithmic regression - (t)ime, (n)odes, (l)p iterations",
1586  &eventhdlrdata->logregression_xtype, FALSE, DEFAULT_LOGREGRESSION_XTYPE, LOGREGRESSION_XTYPES, NULL, NULL) );
1587 
1588  SCIP_CALL( SCIPaddBoolParam(scip, EVENTHDLR_NAME "s/useemphsettings",
1589  "should emphasis settings for the solving phases be used, or settings files?",
1590  &eventhdlrdata->useemphsettings, FALSE, DEFAULT_USEEMPHSETTINGS, NULL, NULL) );
1591 
1592  return SCIP_OKAY;
1593 }
static SCIP_RETCODE recomputeNodeInformation(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPeventhdlrSetData(SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:335
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
static SCIP_RETCODE applySolvingPhase(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
#define DISP_HEAD_NRANK1NODES
#define TRANSITIONMETHODS
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
static SCIP_RETCODE fixOrUnfixRelevantParameters(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_Bool fix)
public methods for SCIP parameter handling
#define DISP_HEAD_NNODESBELOWINC
#define DISP_NAME_NRANK1NODES
static SCIP_Bool transitionPhase3(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
public methods for branch and bound tree
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void removeNode(SCIP_NODE *node, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_RETCODE adaptSolverBehavior(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool checkRankOneTransition(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_NODE * SCIPeventGetNode(SCIP_EVENT *event)
Definition: event.c:1291
public methods for memory management
#define DISP_WIDT_NNODESBELOWINC
static SCIP_RETCODE freeDepthinfo(SCIP *scip, DEPTHINFO **depthinfo)
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3407
SCIP_EXPORT SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:225
#define DEFAULT_USERESTART1TO2
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:123
#define DEFAULT_TESTMODE
public solving methods
SCIP_RETCODE SCIPregressionCreate(SCIP_REGRESSION **regression)
Definition: misc.c:406
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7429
public methods for timing
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:146
SCIP_RETCODE SCIPgetOpenNodesData(SCIP *scip, SCIP_NODE ***leaves, SCIP_NODE ***children, SCIP_NODE ***siblings, int *nleaves, int *nchildren, int *nsiblings)
Definition: scip_tree.c:388
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
SCIP_EXPORT void SCIPsortedvecDelPosPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int pos, int *len)
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define FALSE
Definition: def.h:73
static SCIP_Real getCurrentRegressionTangentAxisIntercept(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_EXPORT int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7439
SCIP_RETCODE SCIPsetEventhdlrInitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINITSOL((*eventinitsol)))
Definition: scip_event.c:183
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_RETCODE addNodesInformation(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE **nodes, int nnodes)
#define SCIP_EVENTTYPE_NODEFOCUSED
Definition: type_event.h:83
#define DEFAULT_FALLBACK
SCIP_Real minestimate
SCIP_RETCODE SCIPgetChildren(SCIP *scip, SCIP_NODE ***children, int *nchildren)
Definition: scip_tree.c:154
#define EVENTHDLR_NAME
const char * SCIPparamGetName(SCIP_PARAM *param)
Definition: paramset.c:650
public methods for displaying runtime statistics
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Bool SCIPparamIsDefault(SCIP_PARAM *param)
Definition: paramset.c:927
#define DEFAULT_NODEOFFSET
SCIP_Real SCIPgetUpperbound(SCIP *scip)
static SCIP_DECL_EVENTEXEC(eventExecSolvingphase)
#define DISP_POSI_NNODESBELOWINC
#define DEFAULT_ENABLED
#define SCIP_LONGINT_MAX
Definition: def.h:149
static SCIP_RETCODE changeEmphasisParameters(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
#define SCIPdebugMsg
Definition: scip_message.h:69
static int checkLeavesBelowIncumbent(SCIP *scip)
SCIP_RETCODE SCIPsetEventhdlrCopy(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTCOPY((*eventcopy)))
Definition: scip_event.c:127
SCIP_VAR ** x
Definition: circlepacking.c:54
static SCIP_Bool checkEstimateCriterion(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_PARAM ** SCIPgetParams(SCIP *scip)
Definition: scip_param.c:994
SCIP_Real SCIPregressionGetIntercept(SCIP_REGRESSION *regression)
Definition: misc.c:264
public methods for querying solving statistics
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
int SCIPregressionGetNObservations(SCIP_REGRESSION *regression)
Definition: misc.c:244
#define SCIP_EVENTTYPE_NODEBRANCHED
Definition: type_event.h:86
static SCIP_DECL_SORTPTRCOMP(sortCompTreeinfo)
public methods for the branch-and-bound tree
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:325
void SCIPregressionRemoveObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition: misc.c:339
static SCIP_RETCODE ensureDepthInfoArraySize(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE *node)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for handling parameter settings
SCIP_EXPORT void SCIPsortedvecInsertPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *keyval, int *len, int *pos)
#define EVENTHDLR_DESC
SCIP_NODE ** minnodes
void SCIPregressionReset(SCIP_REGRESSION *regression)
Definition: misc.c:390
SCIP_RETCODE SCIPsetEventhdlrFree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTFREE((*eventfree)))
Definition: scip_event.c:141
enum SolvingPhase SOLVINGPHASE
SCIP_RETCODE SCIPfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:358
SCIP_Real SCIPregressionGetSlope(SCIP_REGRESSION *regression)
Definition: misc.c:254
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
public methods for event handler plugins and event handlers
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
SCIP_RETCODE SCIPgetLeaves(SCIP *scip, SCIP_NODE ***leaves, int *nleaves)
Definition: scip_tree.c:238
static SCIP_Real getX(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_Bool SCIPparamIsFixed(SCIP_PARAM *param)
Definition: paramset.c:690
#define DISP_DESC_NNODESBELOWINC
#define DISP_PRIO_NNODESBELOWINC
SCIP_Real SCIPgetFirstPrimalBound(SCIP *scip)
int SCIPgetNChildren(SCIP *scip)
Definition: scip_tree.c:178
static SCIP_RETCODE collectNondefaultParams(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Longint SCIPgetNDelayedCutoffs(SCIP *scip)
static int getNNodesBelowIncumbent(SCIP *scip)
#define REALABS(x)
Definition: def.h:187
static SCIP_DECL_DISPOUTPUT(dispOutputNRank1Nodes)
#define DISP_POSI_NRANK1NODES
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
static SCIP_RETCODE updateLogRegression(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:185
#define DEFAULT_SETNAME
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition: scip_param.c:376
#define DEFAULT_INTERRUPTOPTIMAL
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
#define DISP_STRI_NNODESBELOWINC
#define DEFAULT_LOGREGRESSION_XTYPE
#define SCIP_Bool
Definition: def.h:70
static SCIP_DECL_EVENTFREE(eventFreeSolvingphase)
static SCIP_DECL_EVENTINITSOL(eventInitsolSolvingphase)
SolvingPhase
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:91
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition: scip_param.c:877
#define DISP_STRI_NRANK1NODES
static SCIP_RETCODE createDepthinfo(SCIP *scip, DEPTHINFO **depthinfo)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincludeDisp(SCIP *scip, const char *name, const char *desc, const char *header, SCIP_DISPSTATUS dispstatus, SCIP_DECL_DISPCOPY((*dispcopy)), SCIP_DECL_DISPFREE((*dispfree)), SCIP_DECL_DISPINIT((*dispinit)), SCIP_DECL_DISPEXIT((*dispexit)), SCIP_DECL_DISPINITSOL((*dispinitsol)), SCIP_DECL_DISPEXITSOL((*dispexitsol)), SCIP_DECL_DISPOUTPUT((*dispoutput)), SCIP_DISPDATA *dispdata, int width, int priority, int position, SCIP_Bool stripline)
Definition: scip_disp.c:46
SCIP_RETCODE SCIPsetEventhdlrExitsol(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXITSOL((*eventexitsol)))
Definition: scip_event.c:197
SCIP_EXPORT SCIP_Real SCIPnodeGetEstimate(SCIP_NODE *node)
Definition: tree.c:7459
int SCIPgetNParams(SCIP *scip)
Definition: scip_param.c:1008
SCIPInterval log(const SCIPInterval &x)
eventhdlr for solving phase dependent parameter adjustment
int SCIPgetNNodesLeft(SCIP *scip)
Definition: scip_tree.c:612
static int getNRank1Nodes(SCIP *scip)
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
#define DEFAULT_USERESTART2TO3
void SCIPregressionFree(SCIP_REGRESSION **regression)
Definition: misc.c:422
static SCIP_DECL_EVENTEXIT(eventExitSolvingphase)
enum SCIP_ParamEmphasis SCIP_PARAMEMPHASIS
Definition: type_paramset.h:74
#define SCIP_REAL_MAX
Definition: def.h:164
#define SCIP_REAL_MIN
Definition: def.h:165
#define DISP_WIDT_NRANK1NODES
methods for sorting joint arrays of various types
public methods for managing events
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition: type_event.h:96
#define DISP_NAME_NNODESBELOWINC
general public methods
static SCIP_RETCODE releaseNodeInformation(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE *node)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
public methods for solutions
#define EVENTHDLR_EVENT
SCIP_RETCODE SCIPsetEventhdlrInit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINIT((*eventinit)))
Definition: scip_event.c:155
SCIP_RETCODE SCIPreadParams(SCIP *scip, const char *filename)
Definition: scip_param.c:767
public methods for message output
#define SCIP_Real
Definition: def.h:163
#define DEFAULT_USEEMPHSETTINGS
#define SCIP_DECL_EVENTCOPY(x)
Definition: type_event.h:174
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetSiblings(SCIP *scip, SCIP_NODE ***siblings, int *nsiblings)
Definition: scip_tree.c:196
public methods for message handling
SCIP_RETCODE SCIPincludeEventHdlrSolvingphase(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_INVALID
Definition: def.h:183
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
static SCIP_RETCODE updateDataStructures(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_EVENTTYPE eventtype)
#define SCIP_Longint
Definition: def.h:148
static void determineSolvingPhase(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
#define nnodes
Definition: gastrans.c:65
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
SCIP_EXPORT SCIP_NODETYPE SCIPnodeGetType(SCIP_NODE *node)
Definition: tree.c:7419
#define eventCopySolvingphase
const char * SCIPdispGetName(SCIP_DISP *disp)
Definition: disp.c:326
void SCIPregressionAddObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition: misc.c:371
#define DEFAULT_TRANSITIONMETHOD
static void releaseNodeFromDepthInfo(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata, SCIP_NODE *node)
static SCIP_RETCODE changeParametersUsingSettingsFiles(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
#define DISP_DESC_NRANK1NODES
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
#define DISP_PRIO_NRANK1NODES
#define SCIPABORT()
Definition: def.h:336
static SCIP_DECL_EVENTEXITSOL(eventExitsolSolvingphase)
static SCIP_DECL_EVENTINIT(eventInitSolvingphase)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:158
static SCIP_Bool checkOptimalSolution(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
#define EPSZ(x, eps)
Definition: def.h:193
public methods for display handler plugins
#define LOGREGRESSION_XTYPES
SCIP_RETCODE SCIPsetEventhdlrExit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXIT((*eventexit)))
Definition: scip_event.c:169
SCIP_RETCODE SCIPrestartSolve(SCIP *scip)
Definition: scip_solve.c:3433
static void testCriteria(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
static SCIP_Bool checkLogCriterion(SCIP *scip, SCIP_EVENTHDLRDATA *eventhdlrdata)
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:142
void SCIPdispInt(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, int val, int width)
Definition: disp.c:618