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