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  	
(2) Event example_assign: Example 1: Assigning: "eventshadownode" = return value from "SCIPshadowTreeGetShadowNode(shadowtree, eventnode)".
Also see events: [returned_null][example_checked][example_assign][example_checked][example_assign][example_checked][example_assign][example_checked][example_assign][example_assign][example_checked][var_assigned][dereference]
214  	   eventshadownode = SCIPshadowTreeGetShadowNode(shadowtree, eventnode);
215  	
216  	   /* only add children to the shadowtree if eventnode is in the shadowtree */
(3) Event example_checked: Example 1 (cont.): "eventshadownode" has its value checked in "eventshadownode == NULL".
Also see events: [returned_null][example_assign][example_assign][example_checked][example_assign][example_checked][example_assign][example_checked][example_assign][example_assign][example_checked][var_assigned][dereference]
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  	
(4) Event example_assign: Example 2: Assigning: "deletedshadownode" = return value from "SCIPshadowTreeGetShadowNode(shadowtree, deletednode)".
Also see events: [returned_null][example_assign][example_checked][example_checked][example_assign][example_checked][example_assign][example_checked][example_assign][example_assign][example_checked][var_assigned][dereference]
367  	   deletedshadownode = SCIPshadowTreeGetShadowNode(shadowtree, deletednode);
368  	
369  	   /* no need to delete if not included in the shadowtree */
(5) Event example_checked: Example 2 (cont.): "deletedshadownode" has its value checked in "deletedshadownode == NULL".
Also see events: [returned_null][example_assign][example_checked][example_assign][example_assign][example_checked][example_assign][example_checked][example_assign][example_assign][example_checked][var_assigned][dereference]
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