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   	#ifndef __SCIP_EVENT_SHADOWTREE_H__
42   	#define __SCIP_EVENT_SHADOWTREE_H__
43   	
44   	#include "scip/def.h"
45   	#include "scip/type_scip.h"
46   	#include "scip/type_event.h"
47   	#include "scip/type_tree.h"
48   	#include "scip/type_var.h"
49   	#include "scip/type_misc.h"
50   	
51   	#ifdef __cplusplus
52   	extern "C" {
53   	#endif
54   	
55   	/** bound change for branch-and-bound tree node in shadow tree */
56   	struct SCIP_ShadowBoundUpdate
57   	{
58   	   SCIP_VAR*             var;                /**< changed variable */
59   	   SCIP_Real             newbound;           /**< bound change */
60   	   SCIP_BOUNDTYPE        boundchgtype;       /**< which bound of variable is changed (upper or lower) */
61   	};
62   	typedef struct SCIP_ShadowBoundUpdate SCIP_SHADOWBOUNDUPDATE;
63   	
64   	/** branch-and-bound tree node for the shadowtree */
65   	struct SCIP_ShadowNode
66   	{
67   	   SCIP_Longint          nodeid;             /**< ID of corresponding branch-and-bound tree node */
68   	   struct SCIP_ShadowNode* parent;           /**< parent of this shadowtree node. NULL iff it is the root node */
69   	   struct SCIP_ShadowNode** children;        /**< list of children of this shadowtree node. NULL iff it is a leaf */
70   	   int                   nchildren;          /**< number of elements in children
71   	                                              *   0 iff it is a leaf, -1 iff original node is DELETED */
72   	   SCIP_SHADOWBOUNDUPDATE* branchingdecisions;/**< the variables branched on in this node.
73   	                                               *  NULL iff nbranchingdecisions == 0 */
74   	   int                   nbranchingdecisions;/**< the number of variables branched on in this node
75   	                                              *   0 iff branchingdecisions == NULL */
76   	   SCIP_SHADOWBOUNDUPDATE* propagations;     /**< the propagation (and branching decisions) updates in the node
77   	                                              *   This is populated after branching with the propagations in that node.
78   	                                              *   NULL iff npropagations == 0 */
79   	   int                   npropagations;      /**< the number of propagations. 0 iff propagations == NULL */
80   	};
81   	typedef struct SCIP_ShadowNode SCIP_SHADOWNODE;
82   	
83   	/** shadow tree data structure */
84   	struct SCIP_ShadowTree
85   	{
86   	   SCIP_HASHTABLE*       nodemap;            /**< pointer to the hashmap containing all shadow tree nodes */
87   	};
88   	typedef struct SCIP_ShadowTree SCIP_SHADOWTREE;
89   	
90   	/** get the time spent in the shadow tree eventhdlr */
91   	SCIP_EXPORT
92   	SCIP_Real SCIPgetShadowTreeEventHandlerExecutionTime(
93   	   SCIP*                 scip,               /**< SCIP data structure */
94   	   SCIP_EVENTHDLR*       eventhdlr           /**< event handler */
95   	);
96   	
97   	/** given a node number, returns the node in the shadow tree, or NULL if it doesn't exist */
98   	SCIP_EXPORT
99   	SCIP_SHADOWNODE* SCIPshadowTreeGetShadowNodeFromNodeNumber(
100  	   SCIP_SHADOWTREE*      shadowtree,         /**< pointer to the shadow tree */
101  	   SCIP_Longint          nodeno              /**< index of the node, equivalent to the standard branch-and-bound tree */
102  	);
103  	
104  	/** given a node, returns the node in the shadowtree, or NULL if it doesn't exist */
105  	SCIP_EXPORT
106  	SCIP_SHADOWNODE* SCIPshadowTreeGetShadowNode(
107  	   SCIP_SHADOWTREE*      shadowtree,         /**< pointer to the shadow tree */
108  	   SCIP_NODE*            node                /**< node from the actual branch-and-bound tree */
109  	);
110  	
111  	/** gets the shadow tree */
112  	SCIP_EXPORT
113  	SCIP_SHADOWTREE* SCIPgetShadowTree(
114  	   SCIP_EVENTHDLR*       eventhdlr           /**< event handler */
115  	);
116  	
117  	/** activates shadow tree eventhandler if it is not already activated (which keeps a copy of the tree) */
118  	SCIP_EXPORT
119  	SCIP_RETCODE SCIPactivateShadowTree(
120  	   SCIP*                 scip,               /**< SCIP data structure */
121  	   SCIP_EVENTHDLR*       eventhdlr           /**< event handler */
122  	);
123  	
124  	/** creates event handler for event */
125  	SCIP_EXPORT
126  	SCIP_RETCODE SCIPincludeEventHdlrShadowTree(
127  	   SCIP*                 scip,               /**< SCIP data structure */
128  	   SCIP_EVENTHDLR**      eventhdlrptr        /**< pointer to store the event handler */
129  	);
130  	
131  	#ifdef __cplusplus
132  	}
133  	#endif
134  	
135  	#endif
136