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_shadowtree.c 26 * @ingroup DEFPLUGINS_EVENT 27 * @brief event handler for maintaining the unmodified branch-and-bound tree 28 * @author Jasper van Doornmalen 29 * 30 * It is possible that SCIP detects that variable bounds can be restricted globally further than formerly known. 31 * In that case, it is decided to update the global bounds of these variables, and modify the history of the branching 32 * decisions this way. This breaks methods that depend on the assumption that historic choices in the branch-and-bound 33 * tree remain unmodified througout the search, e.g., dynamic symmetry handling constraints. 34 * 35 * This event handler registers decisions made by the branch-and-bound tree directly at the moment of branching, and 36 * does not modify those at later stages of the solve. 37 */ 38 39 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 40 41 #include "blockmemshell/memory.h" 42 #include "scip/debug.h" 43 #include "scip/pub_cons.h" 44 #include "scip/pub_message.h" 45 #include "scip/pub_var.h" 46 #include "scip/struct_var.h" 47 #include "scip/type_var.h" 48 #include "scip/scip.h" 49 #include "scip/scip_branch.h" 50 #include "scip/scip_conflict.h" 51 #include "scip/scip_cons.h" 52 #include "scip/scip_copy.h" 53 #include "scip/scip_cut.h" 54 #include "scip/scip_general.h" 55 #include "scip/scip_lp.h" 56 #include "scip/scip_mem.h" 57 #include "scip/scip_message.h" 58 #include "scip/scip_numerics.h" 59 #include "scip/scip_param.h" 60 #include "scip/scip_prob.h" 61 #include "scip/scip_probing.h" 62 #include "scip/scip_sol.h" 63 #include "scip/scip_var.h" 64 #include "scip/struct_scip.h" 65 #include "scip/struct_mem.h" 66 #include "scip/struct_tree.h" 67 #include "scip/symmetry.h" 68 #include <ctype.h> 69 #include <string.h> 70 #include <memory.h> 71 #include "scip/event_shadowtree.h" 72 73 #define EVENTHDLR_NAME "event_shadowtree" 74 #define EVENTHDLR_DESC "event handler for maintaining the unmodified branch-and-bound tree" 75 #define NODEMAP_MAX_INITIAL_SIZE 10000 76 #define NODEMAP_MAX_INITIAL_SIZE_2LOG 14 77 78 79 /* 80 * Data structures 81 */ 82 83 84 /** wrapper for shadow tree eventhandler data */ 85 struct SCIP_EventhdlrData 86 { 87 #ifndef NDEBUG 88 SCIP* scip; /**< SCIP data structure */ 89 #endif 90 SCIP_SHADOWTREE* shadowtree; /**< Shadow tree structure */ 91 SCIP_CLOCK* clock; /**< clock for measuring time in shadow tree events */ 92 SCIP_Bool active; /**< whether a shadow tree should be maintained */ 93 }; 94 95 96 /* 97 * Local methods 98 */ 99 100 /** hash key for SCIP_SHADOWNODE */ 101 static 102 SCIP_DECL_HASHGETKEY(hashGetKeyShadowNode) 103 { /*lint --e{715}*/ 104 return elem; 105 } 106 107 /** returns TRUE iff the indices of both node numbers are equal */ 108 static 109 SCIP_DECL_HASHKEYEQ(hashKeyEqShadowNode) 110 { /*lint --e{715}*/ 111 return ((SCIP_SHADOWNODE*) key1)->nodeid == ((SCIP_SHADOWNODE*) key2)->nodeid; 112 } 113 114 /** returns the hash value of the key */ 115 static 116 SCIP_DECL_HASHKEYVAL(hashKeyValShadowNode) 117 { /*lint --e{715}*/ 118 return (unsigned int) ((SCIP_SHADOWNODE*) key)->nodeid; 119 } 120 121 122 /** get the time spent in the shadow tree eventhdlr */ 123 SCIP_Real SCIPgetShadowTreeEventHandlerExecutionTime( 124 SCIP* scip, /**< SCIP data structure */ 125 SCIP_EVENTHDLR* eventhdlr /**< event handler */ 126 ) 127 { 128 SCIP_EVENTHDLRDATA* eventhdlrdata; 129 130 eventhdlrdata = (SCIP_EVENTHDLRDATA*) SCIPeventhdlrGetData(eventhdlr); 131 assert( eventhdlrdata != NULL ); 132 assert( eventhdlrdata->scip != NULL ); 133 assert( eventhdlrdata->scip == scip ); 134 assert( eventhdlrdata->clock != NULL ); 135 136 return SCIPgetClockTime(scip, eventhdlrdata->clock); 137 } 138 139 140 /** given a node number, returns the node in the shadow tree, or NULL if it doesn't exist */ 141 SCIP_SHADOWNODE* SCIPshadowTreeGetShadowNodeFromNodeNumber( 142 SCIP_SHADOWTREE* shadowtree, /**< pointer to the shadow tree */ 143 SCIP_Longint nodeid /**< index of the node, equivalent to the standard branch and bound tree */ 144 ) 145 { 146 SCIP_SHADOWNODE tmpnode; 147 148 assert( shadowtree != NULL ); 149 assert( nodeid >= 0 ); 150 151 tmpnode.nodeid = nodeid; 152 153 /* the following line of code returns NULL if it cannot find the entry in the hashtable */ 154 return (SCIP_SHADOWNODE*) SCIPhashtableRetrieve(shadowtree->nodemap, (void*) &tmpnode); 155 } 156 157 /** given a node, returns the node in the shadowtree, or NULL if it doesn't exist */ 158 SCIP_SHADOWNODE* SCIPshadowTreeGetShadowNode( 159 SCIP_SHADOWTREE* shadowtree, /**< pointer to the shadow tree */ 160 SCIP_NODE* node /**< node from the actual branch-and-bound tree */ 161 ) 162 { 163 assert( shadowtree != NULL ); 164 assert( node != NULL ); 165 166 return SCIPshadowTreeGetShadowNodeFromNodeNumber(shadowtree, SCIPnodeGetNumber(node)); 167 } 168 169 /* 170 * Callback methods of event handler 171 */ 172 173 /** event handler for branching event */ 174 static 175 SCIP_DECL_EVENTEXEC(eventExecNodeBranched) 176 { 177 SCIP_EVENTHDLRDATA* eventhdlrdata; 178 SCIP_SHADOWTREE* shadowtree; 179 SCIP_SHADOWNODE* eventshadownode; 180 SCIP_SHADOWNODE* childshadownode; 181 SCIP_NODE* eventnode; 182 SCIP_NODE** children; 183 SCIP_NODE* childnode; 184 SCIP_DOMCHG* domchg; 185 SCIP_BOUNDCHG* boundchg; 186 SCIP_SHADOWBOUNDUPDATE* branchingdecisions; 187 SCIP_SHADOWBOUNDUPDATE* update; 188 int maxnbranchingdecisions; 189 int nbranchingdecisions; 190 int nboundchgs; 191 int nchildren; 192 int i; 193 int c; 194 195 assert( scip != NULL ); 196 assert( eventhdlr != NULL ); 197 assert( event != NULL ); 198 assert( SCIPeventGetType(event) & SCIP_EVENTTYPE_NODEBRANCHED ); 199 200 /* no branching during probing */ 201 assert( !SCIPinProbing(scip) ); 202 203 eventnode = SCIPeventGetNode(event); 204 assert( SCIPgetFocusNode(scip) == eventnode ); 205 assert( SCIPnodeGetType(eventnode) == SCIP_NODETYPE_FOCUSNODE ); 206 207 eventhdlrdata = (SCIP_EVENTHDLRDATA*) SCIPeventhdlrGetData(eventhdlr); 208 assert( eventhdlrdata != NULL ); 209 assert( scip == eventhdlrdata->scip ); 210 211 shadowtree = eventhdlrdata->shadowtree; 212 assert( shadowtree != NULL ); 213 214 eventshadownode = SCIPshadowTreeGetShadowNode(shadowtree, eventnode); 215 216 /* only add children to the shadowtree if eventnode is in the shadowtree */ 217 if ( eventshadownode == NULL ) 218 return SCIP_OKAY; 219 220 assert( eventshadownode->nchildren == 0 ); 221 assert( eventshadownode->children == NULL ); 222 223 SCIP_CALL( SCIPgetChildren(scip, &children, &nchildren) ); 224 225 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &eventshadownode->children, nchildren) ); 226 eventshadownode->nchildren = nchildren; 227 228 maxnbranchingdecisions = 1; /* good guess that there's one branching variable, because that's likely the number */ 229 SCIP_CALL( SCIPallocBufferArray(scip, &branchingdecisions, maxnbranchingdecisions) ); 230 231 /* get all variables branched upon and check all branches */ 232 for (c = 0; c < nchildren; ++c) 233 { 234 nbranchingdecisions = 0; 235 236 childnode = children[c]; 237 domchg = SCIPnodeGetDomchg(childnode); 238 239 /* loop through all bound changes */ 240 nboundchgs = SCIPdomchgGetNBoundchgs(domchg); 241 for (i = 0; i < nboundchgs; ++i) 242 { 243 /* get bound change info */ 244 boundchg = SCIPdomchgGetBoundchg(domchg, i); 245 assert( boundchg != NULL ); 246 247 /* branching decisions have to be in the beginning of the bound change array */ 248 if ( SCIPboundchgGetBoundchgtype(boundchg) != SCIP_BOUNDCHGTYPE_BRANCHING ) 249 break; 250 251 if ( nbranchingdecisions >= maxnbranchingdecisions ) 252 { 253 assert( nbranchingdecisions == maxnbranchingdecisions ); 254 assert( maxnbranchingdecisions > 0 ); 255 maxnbranchingdecisions = SCIPcalcMemGrowSize(scip, maxnbranchingdecisions + 1); 256 SCIP_CALL( SCIPreallocBufferArray(scip, &branchingdecisions, maxnbranchingdecisions) ); 257 } 258 assert( nbranchingdecisions < maxnbranchingdecisions ); 259 260 /* get corresponding branching step */ 261 update = &branchingdecisions[nbranchingdecisions++]; 262 update->var = SCIPboundchgGetVar(boundchg); 263 update->boundchgtype = SCIPboundchgGetBoundtype(boundchg); 264 update->newbound = SCIPboundchgGetNewbound(boundchg); 265 } 266 267 /* create the child in the shadow tree */ 268 SCIP_CALL( SCIPallocBlockMemory(scip, &childshadownode) ); 269 eventshadownode->children[c] = childshadownode; 270 271 childshadownode->nodeid = SCIPnodeGetNumber(childnode); 272 childshadownode->parent = eventshadownode; 273 274 /* children are only set after this node is focused and branched on */ 275 childshadownode->children = NULL; 276 childshadownode->nchildren = 0; 277 278 if ( nbranchingdecisions <= 0 ) 279 childshadownode->branchingdecisions = NULL; 280 else 281 { 282 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &childshadownode->branchingdecisions, nbranchingdecisions) ); 283 for (i = 0; i < nbranchingdecisions; ++i) 284 { 285 /* this copies the whole struct */ 286 childshadownode->branchingdecisions[i] = branchingdecisions[i]; 287 } 288 } 289 childshadownode->nbranchingdecisions = nbranchingdecisions; 290 291 /* propagations are only set after this node is focused and branched on */ 292 childshadownode->propagations = NULL; 293 childshadownode->npropagations = 0; 294 295 /* add childshadownode to the nodemap as well 296 * 297 * The hashtable only checks by the 'nodeid' field, so we just check if there's none with this nodeid. 298 */ 299 assert( !SCIPhashtableExists(shadowtree->nodemap, (void*) childshadownode)); 300 SCIP_CALL( SCIPhashtableInsert(shadowtree->nodemap, childshadownode) ); 301 } 302 SCIPfreeBufferArray(scip, &branchingdecisions); 303 304 /* also store the propagations in the eventnode (the node that got solved by branching) */ 305 domchg = SCIPnodeGetDomchg(eventnode); 306 307 /* loop through all bound changes in the focus node */ 308 nboundchgs = SCIPdomchgGetNBoundchgs(domchg); 309 if ( nboundchgs <= 0 ) 310 { 311 assert( nboundchgs == 0 ); 312 313 /* this is set to NULL at initialization of this shadownode, already */ 314 assert( eventshadownode->npropagations == 0 ); 315 assert( eventshadownode->branchingdecisions == NULL ); 316 } 317 else 318 { 319 /* just include everything, even the branching decisions! */ 320 eventshadownode->npropagations = nboundchgs; 321 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &eventshadownode->propagations, nboundchgs) ); 322 for (i = 0; i < nboundchgs; ++i) 323 { 324 boundchg = SCIPdomchgGetBoundchg(domchg, i); 325 assert( boundchg != NULL ); 326 update = &(eventshadownode->propagations[i]); 327 update->var = SCIPboundchgGetVar(boundchg); 328 update->boundchgtype = SCIPboundchgGetBoundtype(boundchg); 329 update->newbound = SCIPboundchgGetNewbound(boundchg); 330 } 331 } 332 333 return SCIP_OKAY; 334 } /*lint !e715*/ 335 336 337 /** event handler for node deletion event */ 338 static 339 SCIP_DECL_EVENTEXEC(eventExecNodeDeleted) 340 { /*lint !e396*/ 341 SCIP_EVENTHDLRDATA* eventhdlrdata; 342 SCIP_SHADOWTREE* shadowtree; 343 SCIP_NODE* deletednode; 344 SCIP_SHADOWNODE* deletedshadownode; 345 int c; 346 SCIP_SHADOWNODE* childshadownode; 347 348 assert( scip != NULL ); 349 assert( eventhdlr != NULL ); 350 assert( event != NULL ); 351 assert( SCIPeventGetType(event) & SCIP_EVENTTYPE_NODEDELETE ); 352 353 deletednode = SCIPeventGetNode(event); 354 assert( deletednode != NULL ); 355 356 /* probing nodes are not stored */ 357 if( SCIPnodeGetType(deletednode) == SCIP_NODETYPE_PROBINGNODE ) 358 return SCIP_OKAY; 359 360 eventhdlrdata = (SCIP_EVENTHDLRDATA*) SCIPeventhdlrGetData(eventhdlr); 361 assert( eventhdlrdata != NULL ); 362 assert( scip == eventhdlrdata->scip ); 363 364 shadowtree = eventhdlrdata->shadowtree; 365 assert( shadowtree != NULL ); 366 367 deletedshadownode = SCIPshadowTreeGetShadowNode(shadowtree, deletednode); 368 369 /* no need to delete if not included in the shadowtree */ 370 if ( deletedshadownode == NULL ) 371 return SCIP_OKAY; 372 assert( deletedshadownode->nodeid == SCIPnodeGetNumber(deletednode) ); 373 374 /* It is possible that deletedshadownode has a non-deleted sibling. 375 * If the branching variable of this sibling differs from deletedshadownode's, 376 * then in the variable branching order also the branching variables of deletedshadownode must be included, 377 * e.g., see `shadowtreeFillNodeDepthBranchIndices` in symmetry_lexred.c. 378 * As such, we may not delete deletedshadownode just yet. However, we can delete its children. 379 * So, mark deletedshadownode as 'ready to delete' by freeing its children, and setting nchildren to -1. 380 * SCIP always deletes leaf nodes only, so if `deletedshadownode` is removed, 381 * its children in the shadowtree (if they exist) in the 'ready to delete' state. */ 382 assert( deletedshadownode->nchildren >= 0 ); 383 assert( (deletedshadownode->nchildren == 0) == (deletedshadownode->children == NULL) ); 384 for (c = 0; c < deletedshadownode->nchildren; ++c) 385 { 386 childshadownode = deletedshadownode->children[c]; 387 388 /* remove from hashtable */ 389 SCIP_CALL( SCIPhashtableRemove(shadowtree->nodemap, (void*) childshadownode) ); 390 391 /* clean childshadownode */ 392 assert( childshadownode->npropagations >= 0 ); 393 assert( (childshadownode->npropagations > 0) != (childshadownode->propagations == NULL) ); 394 SCIPfreeBlockMemoryArrayNull(scip, &childshadownode->propagations, childshadownode->npropagations); 395 396 assert( childshadownode->nbranchingdecisions >= 0 ); 397 assert( (childshadownode->nbranchingdecisions > 0) != (childshadownode->branchingdecisions == NULL) ); 398 SCIPfreeBlockMemoryArrayNull(scip, &childshadownode->branchingdecisions, childshadownode->nbranchingdecisions); 399 400 /* childshadownode must be in the 'ready to delete'-state */ 401 assert( childshadownode->nchildren < 0 ); 402 403 SCIPfreeBlockMemory(scip, &childshadownode); 404 } 405 406 assert( (deletedshadownode->nchildren > 0) != (deletedshadownode->children == NULL) ); 407 if ( deletedshadownode->nchildren > 0 ) 408 { 409 SCIPfreeBlockMemoryArray(scip, &deletedshadownode->children, deletedshadownode->nchildren); 410 } 411 412 /* mark deletedshadownode as 'ready to delete' */ 413 deletedshadownode->children = NULL; 414 deletedshadownode->nchildren = -1; 415 416 return SCIP_OKAY; 417 } /*lint !e715*/ 418 419 420 /** execution method for all events handled by this eventhandler */ 421 static 422 SCIP_DECL_EVENTEXEC(eventExec) 423 { 424 SCIP_EVENTHDLRDATA* eventhdlrdata; 425 426 assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0 ); 427 428 eventhdlrdata = (SCIP_EVENTHDLRDATA*) SCIPeventhdlrGetData(eventhdlr); 429 assert( eventhdlrdata != NULL ); 430 assert( scip == eventhdlrdata->scip ); 431 assert( eventhdlrdata->clock != NULL ); 432 433 SCIP_CALL( SCIPstartClock(scip, eventhdlrdata->clock) ); 434 435 switch (SCIPeventGetType(event)) 436 { 437 case SCIP_EVENTTYPE_NODEBRANCHED: 438 SCIP_CALL( eventExecNodeBranched(scip, eventhdlr, event, eventdata) ); 439 break; 440 case SCIP_EVENTTYPE_NODEDELETE: 441 SCIP_CALL( eventExecNodeDeleted(scip, eventhdlr, event, eventdata) ); 442 break; 443 default: 444 SCIPerrorMessage("unrecognized eventtype in shadowtree event handler\n"); 445 return SCIP_ERROR; 446 } 447 448 SCIP_CALL( SCIPstopClock(scip, eventhdlrdata->clock) ); 449 450 return SCIP_OKAY; 451 } 452 453 454 /** frees shadow tree data structure */ 455 static 456 SCIP_RETCODE freeShadowTree( 457 SCIP* scip, /**< SCIP data structure */ 458 SCIP_SHADOWTREE* shadowtree /**< pointer to shadow tree*/ 459 ) 460 { 461 int i; 462 int nentries; 463 SCIP_SHADOWNODE* shadownode; 464 465 assert( scip != NULL ); 466 assert( shadowtree != NULL ); 467 assert( shadowtree->nodemap != NULL ); 468 469 nentries = SCIPhashtableGetNEntries(shadowtree->nodemap); 470 471 /* free all shadow tree nodes */ 472 for (i = 0; i < nentries; ++i) 473 { 474 shadownode = (SCIP_SHADOWNODE*) SCIPhashtableGetEntry(shadowtree->nodemap, i); 475 if ( shadownode == NULL ) 476 continue; 477 478 assert( shadownode != NULL ); 479 480 assert( shadownode->npropagations >= 0 ); 481 assert( (shadownode->npropagations > 0) != (shadownode->propagations == NULL) ); 482 SCIPfreeBlockMemoryArrayNull(scip, &shadownode->propagations, shadownode->npropagations); 483 484 assert( shadownode->nbranchingdecisions >= 0 ); 485 assert( (shadownode->nbranchingdecisions > 0) != (shadownode->branchingdecisions == NULL) ); 486 SCIPfreeBlockMemoryArrayNull(scip, &shadownode->branchingdecisions, shadownode->nbranchingdecisions); 487 488 assert( shadownode->nchildren >= -1 ); 489 assert( (shadownode->nchildren > 0) != (shadownode->children == NULL) ); 490 SCIPfreeBlockMemoryArrayNull(scip, &shadownode->children, shadownode->nchildren); 491 492 SCIPfreeBlockMemory(scip, &shadownode); 493 } 494 SCIPhashtableFree(&(shadowtree->nodemap)); 495 496 return SCIP_OKAY; 497 } 498 499 500 /** destructor of event handler to free shadow tree data (called when SCIP is exiting) */ 501 static 502 SCIP_DECL_EVENTFREE(eventFreeShadowTree) 503 { 504 SCIP_EVENTHDLRDATA* eventhdlrdata; 505 506 assert( scip != NULL ); 507 assert( eventhdlr != NULL ); 508 assert( SCIPgetStage(scip) != SCIP_STAGE_SOLVING ); 509 510 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 511 assert( eventhdlrdata != NULL ); 512 assert( eventhdlrdata->scip == scip ); 513 assert( eventhdlrdata->clock != NULL ); 514 515 SCIP_CALL( SCIPfreeClock(scip, &eventhdlrdata->clock) ); 516 517 if ( eventhdlrdata->shadowtree != NULL ) 518 { 519 SCIP_CALL( freeShadowTree(scip, eventhdlrdata->shadowtree) ); 520 SCIPfreeBlockMemory(scip, &eventhdlrdata->shadowtree); 521 } 522 523 SCIPfreeBlockMemory(scip, &eventhdlrdata); 524 525 return SCIP_OKAY; 526 } 527 528 529 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */ 530 static 531 SCIP_DECL_EVENTINITSOL(eventInitsolShadowTree) 532 { 533 int initialnodemapsize; 534 535 SCIP_EVENTHDLRDATA* eventhdlrdata; 536 SCIP_SHADOWTREE* shadowtree; 537 SCIP_SHADOWNODE* rootnode; 538 539 assert( scip != NULL ); 540 assert( eventhdlr != NULL ); 541 542 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 543 assert( eventhdlrdata != NULL ); 544 assert( eventhdlrdata->scip == scip ); 545 546 assert( eventhdlrdata->shadowtree == NULL ); 547 assert( SCIPisTransformed(scip) ); 548 549 /* early termination */ 550 if ( !eventhdlrdata->active ) 551 return SCIP_OKAY; 552 553 SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata->shadowtree) ); 554 shadowtree = eventhdlrdata->shadowtree; 555 556 /* prevent unnecessary reallocations by having a good initial guess for the tree size 557 * 558 * By default, we initialize NODEMAP_MAX_INITIAL_SIZE slots, unless reasonably fewer nodes suffice. 559 * Knowing that a full enumeration tree on n binary variables has size 2^n, we base our guess on this number, 560 * counting with the number of binary and integer variables in the problem. 561 */ 562 initialnodemapsize = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) >= NODEMAP_MAX_INITIAL_SIZE_2LOG ? 563 NODEMAP_MAX_INITIAL_SIZE : 564 MIN(NODEMAP_MAX_INITIAL_SIZE, 1 << (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip))); /*lint !e666 !e701 !e747*/ 565 SCIP_CALL( SCIPhashtableCreate(&shadowtree->nodemap, scip->mem->probmem, initialnodemapsize, 566 hashGetKeyShadowNode, hashKeyEqShadowNode, hashKeyValShadowNode, NULL) ); 567 568 /* the root node is the only branch-and-bound tree node not created by branching, so add. */ 569 SCIP_CALL( SCIPallocBlockMemory(scip, &rootnode) ); 570 rootnode->nodeid = 1ll; /*lint !e620*/ /* root node has number 1 */ 571 rootnode->parent = NULL; 572 rootnode->children = NULL; 573 rootnode->nchildren = 0; 574 rootnode->branchingdecisions = NULL; 575 rootnode->nbranchingdecisions = 0; 576 rootnode->propagations = NULL; 577 rootnode->npropagations = 0; 578 579 /* add to the nodemap structure */ 580 SCIP_CALL( SCIPhashtableInsert(shadowtree->nodemap, rootnode) ); 581 582 /* catch NODEBRANCHED and NODEDELETE events */ 583 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED | SCIP_EVENTTYPE_NODEDELETE, eventhdlr, NULL, NULL) ); 584 585 return SCIP_OKAY; 586 } 587 588 589 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */ 590 static 591 SCIP_DECL_EVENTEXITSOL(eventExitsolShadowTree) 592 { 593 SCIP_EVENTHDLRDATA* eventhdlrdata; 594 595 assert( scip != NULL ); 596 assert( eventhdlr != NULL ); 597 598 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 599 assert( eventhdlrdata != NULL ); 600 assert( eventhdlrdata->scip == scip ); 601 assert( SCIPisTransformed(scip) ); 602 603 /* early termination */ 604 if ( !eventhdlrdata->active ) 605 { 606 assert( eventhdlrdata->shadowtree == NULL ); 607 return SCIP_OKAY; 608 } 609 610 assert( eventhdlrdata->shadowtree != NULL ); 611 612 SCIP_CALL( freeShadowTree(scip, eventhdlrdata->shadowtree) ); 613 SCIPfreeBlockMemory(scip, &eventhdlrdata->shadowtree); 614 eventhdlrdata->shadowtree = NULL; 615 616 /* do not listen for NODEBRANCHED events */ 617 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_NODEBRANCHED | SCIP_EVENTTYPE_NODEDELETE, eventhdlr, NULL, -1) ); 618 619 return SCIP_OKAY; 620 } 621 622 623 /** gets the shadow tree */ 624 SCIP_SHADOWTREE* SCIPgetShadowTree( 625 SCIP_EVENTHDLR* eventhdlr /**< event handler */ 626 ) 627 { 628 SCIP_EVENTHDLRDATA* eventhdlrdata; 629 assert( eventhdlr != NULL ); 630 assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0 ); 631 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 632 assert( eventhdlrdata != NULL ); 633 634 return eventhdlrdata->shadowtree; 635 } 636 637 638 /** activates shadow tree eventhandler if it is not already activated (which keeps a copy of the tree) */ 639 SCIP_RETCODE SCIPactivateShadowTree( 640 SCIP* scip, /**< SCIP data structure */ 641 SCIP_EVENTHDLR* eventhdlr /**< event handler */ 642 ) 643 { 644 SCIP_EVENTHDLRDATA* eventhdlrdata; 645 assert( eventhdlr != NULL ); 646 assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0 ); 647 eventhdlrdata = SCIPeventhdlrGetData(eventhdlr); 648 assert( eventhdlrdata != NULL ); 649 assert( eventhdlrdata->scip == scip ); 650 assert( eventhdlrdata->shadowtree == NULL ); 651 652 /* active param may not be changed between (and including) the initsol and exitsol stages */ 653 SCIP_CALL( SCIPcheckStage(scip, "SCIPactivateShadowTree", TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, 654 FALSE, FALSE, FALSE, FALSE, FALSE) ); 655 656 eventhdlrdata->active = TRUE; 657 658 return SCIP_OKAY; 659 } 660 661 662 /** creates event handler for event */ 663 SCIP_RETCODE SCIPincludeEventHdlrShadowTree( 664 SCIP* scip, /**< SCIP data structure */ 665 SCIP_EVENTHDLR** eventhdlrptr /**< pointer to store the event handler */ 666 ) 667 { 668 SCIP_EVENTHDLRDATA* eventhdlrdata; 669 SCIP_EVENTHDLR* eventhdlr; 670 671 /* create event handler data */ 672 eventhdlrdata = NULL; 673 SCIP_CALL( SCIPallocBlockMemory(scip, &eventhdlrdata) ); 674 675 #ifndef NDEBUG 676 /* only needed for assertions, to check whether we're working with the correct SCIP. */ 677 eventhdlrdata->scip = scip; 678 #endif 679 680 /* shadow tree must be activated */ 681 eventhdlrdata->active = FALSE; 682 683 /* do not start with a shadow tree by default. Initialize at initsol, remove at exitsol. */ 684 eventhdlrdata->shadowtree = NULL; 685 eventhdlr = NULL; 686 687 /* include event handler into SCIP */ 688 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExec, eventhdlrdata) ); 689 assert(eventhdlr != NULL); 690 *eventhdlrptr = eventhdlr; 691 692 /* clock */ 693 SCIP_CALL( SCIPcreateClock(scip, &eventhdlrdata->clock) ); 694 695 /* set non fundamental callbacks via setter functions */ 696 697 /* frees the event handler */ 698 SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeShadowTree) ); 699 700 /* initialize the shadowtree data structure, initialize by setting the root node */ 701 SCIP_CALL( SCIPsetEventhdlrInitsol(scip, eventhdlr, eventInitsolShadowTree) ); 702 703 /* free the shadowtree data structure */ 704 SCIP_CALL( SCIPsetEventhdlrExitsol(scip, eventhdlr, eventExitsolShadowTree) ); 705 706 return SCIP_OKAY; 707 } 708