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   pub_tree.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  public methods for branch and bound tree
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#ifndef __SCIP_PUB_TREE_H__
34   	#define __SCIP_PUB_TREE_H__
35   	
36   	#include "scip/def.h"
37   	#include "scip/type_cons.h"
38   	#include "scip/type_lp.h"
39   	#include "scip/type_misc.h"
40   	#include "scip/type_reopt.h"
41   	#include "scip/type_retcode.h"
42   	#include "scip/type_tree.h"
43   	#include "scip/type_var.h"
44   	
45   	#ifdef NDEBUG
46   	#include "scip/struct_tree.h"
47   	#endif
48   	
49   	#ifdef __cplusplus
50   	extern "C" {
51   	#endif
52   	
53   	/*
54   	 * Node methods
55   	 */
56   	
57   	/**@addtogroup PublicNodeMethods
58   	 *
59   	 * @{
60   	 */
61   	
62   	/** node comparator for best lower bound */
63   	SCIP_EXPORT
64   	SCIP_DECL_SORTPTRCOMP(SCIPnodeCompLowerbound);
65   	
66   	/** returns the set of variable branchings that were performed in the parent node to create this node */
67   	SCIP_EXPORT
68   	void SCIPnodeGetParentBranchings(
69   	   SCIP_NODE*            node,               /**< node data */
70   	   SCIP_VAR**            branchvars,         /**< array of variables on which the branching has been performed in the parent node */
71   	   SCIP_Real*            branchbounds,       /**< array of bounds which the branching in the parent node set */
72   	   SCIP_BOUNDTYPE*       boundtypes,         /**< array of boundtypes which the branching in the parent node set */
73   	   int*                  nbranchvars,        /**< number of variables on which branching has been performed in the parent node
74   	                                              *   if this is larger than the array size, arrays should be reallocated and method should be called again */
75   	   int                   branchvarssize      /**< available slots in arrays */
76   	   );
77   	
78   	/** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node */
79   	SCIP_EXPORT
80   	void SCIPnodeGetAncestorBranchings(
81   	   SCIP_NODE*            node,               /**< node data */
82   	   SCIP_VAR**            branchvars,         /**< array of variables on which the branchings has been performed in all ancestors */
83   	   SCIP_Real*            branchbounds,       /**< array of bounds which the branchings in all ancestors set */
84   	   SCIP_BOUNDTYPE*       boundtypes,         /**< array of boundtypes which the branchings in all ancestors set */
85   	   int*                  nbranchvars,        /**< number of variables on which branchings have been performed in all ancestors
86   	                                              *   if this is larger than the array size, arrays should be reallocated and method should be called again */
87   	   int                   branchvarssize      /**< available slots in arrays */
88   	   );
89   	
90   	/** returns the set of variable branchings that were performed between the given @p node and the given @p parent node. */
91   	SCIP_EXPORT
92   	void SCIPnodeGetAncestorBranchingsPart(
93   	   SCIP_NODE*            node,               /**< node data */
94   	   SCIP_NODE*            parent,             /**< node data */
95   	   SCIP_VAR**            branchvars,         /**< array of variables on which the branchings has been performed in all ancestors */
96   	   SCIP_Real*            branchbounds,       /**< array of bounds which the branchings in all ancestors set */
97   	   SCIP_BOUNDTYPE*       boundtypes,         /**< array of boundtypes which the branchings in all ancestors set */
98   	   int*                  nbranchvars,        /**< number of variables on which branchings have been performed in all ancestors
99   	                                              *   if this is larger than the array size, arrays should be reallocated and method should be called again */
100  	   int                   branchvarssize      /**< available slots in arrays */
101  	   );
102  	
103  	/** outputs the path into given file stream in GML format */
104  	SCIP_EXPORT
105  	SCIP_RETCODE SCIPnodePrintAncestorBranchings(
106  	   SCIP_NODE*            node,               /**< node data */
107  	   FILE*                 file                /**< file to output the path */
108  	   );
109  	
110  	/** returns the set of variable branchings that were performed in all ancestor nodes (nodes on the path to the root) to create this node
111  	 *  sorted by the nodes, starting from the current node going up to the root
112  	 */
113  	SCIP_EXPORT
114  	void SCIPnodeGetAncestorBranchingPath(
115  	   SCIP_NODE*            node,               /**< node data */
116  	   SCIP_VAR**            branchvars,         /**< array of variables on which the branchings has been performed in all ancestors */
117  	   SCIP_Real*            branchbounds,       /**< array of bounds which the branchings in all ancestors set */
118  	   SCIP_BOUNDTYPE*       boundtypes,         /**< array of boundtypes which the branchings in all ancestors set */
119  	   int*                  nbranchvars,        /**< number of variables on which branchings have been performed in all ancestors
120  	                                              *   if this is larger than the array size, arrays should be reallocated and method
121  	                                              *   should be called again */
122  	   int                   branchvarssize,     /**< available slots in arrays */
123  	   int*                  nodeswitches,       /**< marks, where in the arrays the branching decisions of the next node on the path
124  	                                              *   start; branchings performed at the parent of node always start at position 0.
125  	                                              *   For single variable branching, nodeswitches[i] = i holds */
126  	   int*                  nnodes,             /**< number of nodes in the nodeswitch array */
127  	   int                   nodeswitchsize      /**< available slots in node switch array */
128  	   );
129  	
130  	
131  	/** checks for two nodes whether they share the same root path, i.e., whether one is an ancestor of the other */
132  	SCIP_EXPORT
133  	SCIP_Bool SCIPnodesSharePath(
134  	   SCIP_NODE*            node1,              /**< node data */
135  	   SCIP_NODE*            node2               /**< node data */
136  	   );
137  	
138  	/** finds the common ancestor node of two given nodes */
139  	SCIP_EXPORT
140  	SCIP_NODE* SCIPnodesGetCommonAncestor(
141  	   SCIP_NODE*            node1,              /**< node data */
142  	   SCIP_NODE*            node2               /**< node data */
143  	   );
144  	
145  	
146  	/** gets the type of the node */
147  	SCIP_EXPORT
148  	SCIP_NODETYPE SCIPnodeGetType(
149  	   SCIP_NODE*            node                /**< node */
150  	   );
151  	
152  	/** gets successively assigned number of the node */
153  	SCIP_EXPORT
154  	SCIP_Longint SCIPnodeGetNumber(
155  	   SCIP_NODE*            node                /**< node */
156  	   );
157  	
158  	/** gets the depth of the node */
159  	SCIP_EXPORT
160  	int SCIPnodeGetDepth(
161  	   SCIP_NODE*            node                /**< node */
162  	   );
163  	
164  	/** gets the lower bound of the node */
165  	SCIP_EXPORT
166  	SCIP_Real SCIPnodeGetLowerbound(
167  	   SCIP_NODE*            node                /**< node */
168  	   );
169  	
170  	/** gets the estimated value of the best feasible solution in subtree of the node */
171  	SCIP_EXPORT
172  	SCIP_Real SCIPnodeGetEstimate(
173  	   SCIP_NODE*            node                /**< node */
174  	   );
175  	
176  	
177  	/** gets the reoptimization type of a node */
178  	SCIP_EXPORT
179  	SCIP_REOPTTYPE SCIPnodeGetReopttype(
180  	   SCIP_NODE*            node                /**< node */
181  	   );
182  	
183  	/** gets the unique id to identify the node during reoptimization; id is 0 if the node is the root or not part of the
184  	 * reoptimization tree
185  	 */
186  	SCIP_EXPORT
187  	unsigned int SCIPnodeGetReoptID(
188  	   SCIP_NODE*            node                /**< node */
189  	   );
190  	
191  	/** sets the reoptimization type of the node */
192  	SCIP_EXPORT
193  	void SCIPnodeSetReopttype(
194  	   SCIP_NODE*            node,               /**< node */
195  	   SCIP_REOPTTYPE        reopttype           /**< reoptimization type */
196  	   );
197  	
198  	/** sets a unique id to identify the node during reoptimization */
199  	SCIP_EXPORT
200  	void SCIPnodeSetReoptID(
201  	   SCIP_NODE*            node,               /**< node */
202  	   unsigned int          id                  /**< unique id */
203  	   );
204  	
205  	/** counts the number of bound changes due to branching, constraint propagation, and propagation */
206  	SCIP_EXPORT
207  	void SCIPnodeGetNDomchg(
208  	   SCIP_NODE*            node,               /**< node */
209  	   int*                  nbranchings,        /**< pointer to store number of branchings (or NULL if not needed) */
210  	   int*                  nconsprop,          /**< pointer to store number of constraint propagations (or NULL if not needed) */
211  	   int*                  nprop               /**< pointer to store number of propagations (or NULL if not needed) */
212  	   );
213  	
214  	/** gets the domain change information of the node, i.e., the information about the differences in the
215  	 *  variables domains to the parent node
216  	 */
217  	SCIP_EXPORT
218  	SCIP_DOMCHG* SCIPnodeGetDomchg(
219  	   SCIP_NODE*            node                /**< node */
220  	   );
221  	
222  	/** gets the parent node of a node in the branch-and-bound tree, if any */
223  	SCIP_EXPORT
224  	SCIP_NODE* SCIPnodeGetParent(
225  	   SCIP_NODE*            node                /**< node */
226  	   );
227  	
228  	/** returns all constraints added to a given node */
229  	SCIP_EXPORT
230  	void SCIPnodeGetAddedConss(
231  	   SCIP_NODE*            node,               /**< node */
232  	   SCIP_CONS**           addedconss,         /**< array to store the constraints */
233  	   int*                  naddedconss,        /**< number of added constraints */
234  	   int                   addedconsssize      /**< size of the constraint array */
235  	   );
236  	
237  	/** returns the number of added constraints to the given node */
238  	SCIP_EXPORT
239  	int SCIPnodeGetNAddedConss(
240  	   SCIP_NODE*           node
241  	   );
242  	
243  	/** returns whether node is in the path to the current node */
244  	SCIP_EXPORT
245  	SCIP_Bool SCIPnodeIsActive(
246  	   SCIP_NODE*            node                /**< node */
247  	   );
248  	
249  	/** returns whether the node is marked to be propagated again */
250  	SCIP_EXPORT
251  	SCIP_Bool SCIPnodeIsPropagatedAgain(
252  	   SCIP_NODE*            node                /**< node data */
253  	   );
254  	
255  	/* returns the set of changed constraints for a particular node */
256  	SCIP_EXPORT
257  	SCIP_CONSSETCHG* SCIPnodeGetConssetchg(
258  	   SCIP_NODE*            node                /**< node data */
259  	   );
260  	
261  	
262  	#ifdef NDEBUG
263  	
264  	/* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
265  	 * speed up the algorithms.
266  	 */
267  	
268  	#define SCIPnodeGetType(node)           ((SCIP_NODETYPE)(node)->nodetype)
269  	#define SCIPnodeGetNumber(node)         ((node)->number)
270  	#define SCIPnodeGetDepth(node)          ((int) (node)->depth)
271  	#define SCIPnodeGetLowerbound(node)     ((node)->lowerbound)
272  	#define SCIPnodeGetEstimate(node)       ((node)->estimate)
273  	#define SCIPnodeGetDomchg(node)         ((node)->domchg)
274  	#define SCIPnodeGetParent(node)         ((node)->parent)
275  	#define SCIPnodeIsActive(node)          ((node)->active)
276  	#define SCIPnodeIsPropagatedAgain(node) ((node)->reprop)
277  	#define SCIPnodeGetConssetchg(node)    ((node)->conssetchg)
278  	
279  	#endif
280  	
281  	/** @} */
282  	
283  	#ifdef __cplusplus
284  	}
285  	#endif
286  	
287  	#endif
288