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 */
(1) Event null_return: |
Calling "SCIPhashtableRetrieve" which might return null. [details] |
(2) Event return_null_var: |
Returning "(SCIP_SHADOWNODE *)SCIPhashtableRetrieve(shadowtree->nodemap, (void *)&tmpnode)", which is null. |
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
(1) Event null_return: |
Calling "SCIPshadowTreeGetShadowNodeFromNodeNumber" which might return null. [details] |
(2) Event return_null_fn: |
Returning the return value of "SCIPshadowTreeGetShadowNodeFromNodeNumber", which might be null. |
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