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