1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 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 53 #include "scip/event_solvingphase.h" 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; 110 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; 123 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 210 SCIP_RETCODE addNodesInformation( 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 230 assert(SCIPnodeGetType(node) == SCIP_NODETYPE_CHILD || SCIPnodeGetType(node) == SCIP_NODETYPE_LEAF 231 || SCIPnodeGetType(node) == SCIP_NODETYPE_SIBLING); 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 318 int getNNodesBelowIncumbent( 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 337 SCIP_RETCODE recomputeNodeInformation( 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 384 SCIP_RETCODE createDepthinfo( 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 409 SCIP_RETCODE freeDepthinfo( 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 428 void releaseNodeFromDepthInfo( 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 472 SCIP_RETCODE ensureDepthInfoArraySize( 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 517 SCIP_RETCODE releaseNodeInformation( 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 552 int checkLeavesBelowIncumbent( 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 600 SCIP_Real getX( 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 */ 611 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPgetStage(scip) == SCIP_STAGE_SOLVED ) 612 x = (SCIP_Real)SCIPgetNLPIterations(scip); 613 else 614 x = 1.0; 615 break; 616 case 'n': 617 /* get total number of solving nodes so far */ 618 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPgetStage(scip) == SCIP_STAGE_SOLVED ) 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 645 SCIP_Real getCurrentRegressionTangentAxisIntercept( 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 678 SCIP_Bool checkRankOneTransition( 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 692 SCIP_Bool checkEstimateCriterion( 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 717 SCIP_Bool checkLogCriterion( 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 746 SCIP_Bool checkOptimalSolution( 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 769 SCIP_Bool transitionPhase3( 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", 786 SCIPgetNNodes(scip), getNRank1Nodes(scip), SCIPgetPrimalbound(scip), SCIPgetSolvingTime(scip)); 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", 796 SCIPgetNNodes(scip), SCIPgetPrimalbound(scip), SCIPgetSolvingTime(scip)); 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 830 void determineSolvingPhase( 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 847 SCIP_RETCODE changeEmphasisParameters( 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 { 857 case SOLVINGPHASE_FEASIBILITY: 858 paramemphasis = SCIP_PARAMEMPHASIS_PHASEFEAS; 859 break; 860 case SOLVINGPHASE_IMPROVEMENT: 861 paramemphasis = SCIP_PARAMEMPHASIS_PHASEIMPROVE; 862 break; 863 case SOLVINGPHASE_PROOF: 864 paramemphasis = SCIP_PARAMEMPHASIS_PHASEPROOF; 865 break; 866 case SOLVINGPHASE_UNINITIALIZED: 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 881 SCIP_RETCODE changeParametersUsingSettingsFiles( 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 { 892 case SOLVINGPHASE_FEASIBILITY: 893 paramfilename = eventhdlrdata->feassetname; 894 break; 895 case SOLVINGPHASE_IMPROVEMENT: 896 paramfilename = eventhdlrdata->improvesetname; 897 break; 898 case SOLVINGPHASE_PROOF: 899 paramfilename = eventhdlrdata->proofsetname; 900 break; 901 case SOLVINGPHASE_UNINITIALIZED: 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 935 SCIP_RETCODE fixOrUnfixRelevantParameters( 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 1005 SCIP_RETCODE adaptSolverBehavior( 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 */ 1021 SCIP_CALL( SCIPsetEmphasis(scip, SCIP_PARAMEMPHASIS_DEFAULT, FALSE) ); 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 1035 SCIP_RETCODE applySolvingPhase( 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 1091 SCIP_RETCODE updateLogRegression( 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 1118 SCIP_RETCODE updateDataStructures( 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 */ 1130 case SCIP_EVENTTYPE_BESTSOLFOUND: 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 */ 1139 case SCIP_EVENTTYPE_NODEFOCUSED: 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 */ 1148 case SCIP_EVENTTYPE_NODEBRANCHED: 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 1229 SCIP_DECL_EVENTCOPY(eventCopySolvingphase) 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 */ 1236 SCIP_CALL( SCIPincludeEventHdlrSolvingphase(scip) ); 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) 1247 { 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) 1287 { 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 1314 SCIP_RETCODE collectNondefaultParams( 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) 1407 { 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 1469 1470 /** output method of display column to output file stream 'file' */ 1471 static 1472 SCIP_DECL_DISPOUTPUT(dispOutputNRank1Nodes) 1473 { 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 */ 1479 SCIPdispInt(SCIPgetMessagehdlr(scip), file, getNRank1Nodes(scip), DISP_WIDT_NRANK1NODES); 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 1492 1493 /** output method of display column to output file stream 'file' */ 1494 static 1495 SCIP_DECL_DISPOUTPUT(dispOutputNnodesbelowinc) 1496 { 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 */ 1502 SCIPdispInt(SCIPgetMessagehdlr(scip), file, getNNodesBelowIncumbent(scip), DISP_WIDT_NNODESBELOWINC); 1503 1504 return SCIP_OKAY; 1505 } 1506 1507 /** creates event handler for Solvingphase event */ 1508 SCIP_RETCODE SCIPincludeEventHdlrSolvingphase( 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 */ 1535 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, 1536 eventExecSolvingphase, eventhdlrdata) ); 1537 assert(eventhdlr != NULL); 1538 1539 /* include the new displays into scip */ 1540 SCIP_CALL( SCIPincludeDisp(scip, DISP_NAME_NRANK1NODES, DISP_DESC_NRANK1NODES, DISP_HEAD_NRANK1NODES, SCIP_DISPSTATUS_OFF, 1541 NULL, NULL, NULL, NULL, NULL, NULL, dispOutputNRank1Nodes, NULL, DISP_WIDT_NRANK1NODES, DISP_PRIO_NRANK1NODES, DISP_POSI_NRANK1NODES, 1542 DISP_STRI_NRANK1NODES) ); 1543 SCIP_CALL( SCIPincludeDisp(scip, DISP_NAME_NNODESBELOWINC, DISP_DESC_NNODESBELOWINC, DISP_HEAD_NNODESBELOWINC, SCIP_DISPSTATUS_OFF, 1544 NULL, NULL, NULL, NULL, NULL, NULL, dispOutputNnodesbelowinc, NULL, DISP_WIDT_NNODESBELOWINC, DISP_PRIO_NNODESBELOWINC, DISP_POSI_NNODESBELOWINC, 1545 DISP_STRI_NNODESBELOWINC) ); 1546 1547 /* set non fundamental callbacks via setter functions */ 1548 SCIP_CALL( SCIPsetEventhdlrCopy(scip, eventhdlr, eventCopySolvingphase) ); 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, 1572 FALSE, DEFAULT_NODEOFFSET, 1L, SCIP_LONGINT_MAX, NULL, NULL) ); 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 } 1603