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