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   struct_tree.h
26   	 * @ingroup INTERNALAPI
27   	 * @brief  data structures 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_STRUCT_TREE_H__
34   	#define __SCIP_STRUCT_TREE_H__
35   	
36   	
37   	#include "lpi/type_lpi.h"
38   	#include "scip/def.h"
39   	#include "scip/type_cons.h"
40   	#include "scip/type_history.h"
41   	#include "scip/type_lp.h"
42   	#include "scip/type_nodesel.h"
43   	#include "scip/type_prop.h"
44   	#include "scip/type_tree.h"
45   	#include "scip/type_var.h"
46   	
47   	
48   	#ifdef __cplusplus
49   	extern "C" {
50   	#endif
51   	
52   	/** probing node, possibly with solved LP, where bounds and constraints have been changed,
53   	 *  and rows and columns might have been added
54   	 */
55   	struct SCIP_Probingnode
56   	{
57   	   SCIP_LPISTATE*        lpistate;           /**< LP state information */
58   	   SCIP_LPINORMS*        lpinorms;           /**< LP pricing norms information */
59   	   int                   ninitialcols;       /**< number of LP columns before the node was processed */
60   	   int                   ninitialrows;       /**< number of LP rows before the node was processed */
61   	   int                   ncols;              /**< total number of columns of this node's LP */
62   	   int                   nrows;              /**< total number of rows of this node's LP */
63   	   SCIP_VAR**            origobjvars;        /**< variables whose objective function coefficients have changed */
64   	   SCIP_Real*            origobjvals;        /**< original objective function coefficients */
65   	   int                   nchgdobjs;          /**< number of changed objective coefficients */
66   	   SCIP_Bool             lpwasprimfeas;      /**< primal feasibility of saved LP state information */
67   	   SCIP_Bool             lpwasprimchecked;   /**< primal feasibility check state of saved LP state information  */
68   	   SCIP_Bool             lpwasdualfeas;      /**< dual feasibility of saved LP state information */
69   	   SCIP_Bool             lpwasdualchecked;   /**< dual feasibility check state of saved LP state information  */
70   	};
71   	
72   	/** sibling information (should not exceed the size of a pointer) */
73   	struct SCIP_Sibling
74   	{
75   	   int                   arraypos;           /**< position of node in the siblings array */
76   	};
77   	
78   	/** child information (should not exceed the size of a pointer) */
79   	struct SCIP_Child
80   	{
81   	   int                   arraypos;           /**< position of node in the children array */
82   	};
83   	
84   	/** leaf information (should not exceed the size of a pointer) */
85   	struct SCIP_Leaf
86   	{
87   	   SCIP_NODE*            lpstatefork;        /**< fork/subroot node defining the LP state of the leaf */
88   	};
89   	
90   	/** fork without LP solution, where only bounds and constraints have been changed */
91   	struct SCIP_Junction
92   	{
93   	   int                   nchildren;          /**< number of children of this parent node */
94   	};
95   	
96   	/** fork without LP solution, where bounds and constraints have been changed, and rows and columns were added */
97   	struct SCIP_Pseudofork
98   	{
99   	   SCIP_COL**            addedcols;          /**< array with pointers to new columns added at this node into the LP */
100  	   SCIP_ROW**            addedrows;          /**< array with pointers to new rows added at this node into the LP */
101  	   int                   naddedcols;         /**< number of columns added at this node */
102  	   int                   naddedrows;         /**< number of rows added at this node */
103  	   int                   nchildren;          /**< number of children of this parent node */
104  	};
105  	
106  	/** fork with solved LP, where bounds and constraints have been changed, and rows and columns were added */
107  	struct SCIP_Fork
108  	{
109  	   SCIP_COL**            addedcols;          /**< array with pointers to new columns added at this node into the LP */
110  	   SCIP_ROW**            addedrows;          /**< array with pointers to new rows added at this node into the LP */
111  	   SCIP_LPISTATE*        lpistate;           /**< LP state information */
112  	   SCIP_Real             lpobjval;           /**< the LP objective value for that node, needed to compute the pseudo costs correctly */
113  	   int                   naddedcols;         /**< number of columns added at this node */
114  	   int                   naddedrows;         /**< number of rows added at this node */
115  	   int                   nlpistateref;       /**< number of times, the LP state is needed */
116  	   unsigned int          nchildren:28;       /**< number of children of this parent node */
117  	   unsigned int          lpwasprimfeas:1;    /**< primal feasibility of saved LP state information */
118  	   unsigned int          lpwasprimchecked:1; /**< primal feasibility check state of saved LP state information */
119  	   unsigned int          lpwasdualfeas:1;    /**< dual feasibility of saved LP state information */
120  	   unsigned int          lpwasdualchecked:1; /**< dual feasibility check state of saved LP state information */
121  	};
122  	
123  	/** fork with solved LP, where bounds and constraints have been changed, and rows and columns were removed and added */
124  	struct SCIP_Subroot
125  	{
126  	   SCIP_COL**            cols;               /**< array with pointers to the columns in the same order as in the LP */
127  	   SCIP_ROW**            rows;               /**< array with pointers to the rows in the same order as in the LP */
128  	   SCIP_LPISTATE*        lpistate;           /**< LP state information */
129  	   SCIP_Real             lpobjval;           /**< the LP objective value for that node, needed to compute the pseudo costs correctly */
130  	   int                   ncols;              /**< number of columns in the LP */
131  	   int                   nrows;              /**< number of rows in the LP */
132  	   int                   nlpistateref;       /**< number of times, the LP state is needed */
133  	   unsigned int          nchildren:30;       /**< number of children of this parent node */
134  	   unsigned int          lpwasprimfeas:1;    /**< primal feasibility of saved LP state information */
135  	   unsigned int          lpwasprimchecked:1; /**< primal feasibility check state of saved LP state information */
136  	   unsigned int          lpwasdualfeas:1;    /**< dual feasibility of saved LP state information */
137  	   unsigned int          lpwasdualchecked:1; /**< dual feasibility check state of saved LP state information */
138  	};
139  	
140  	/** node data structure */
141  	struct SCIP_Node
142  	{
143  	   SCIP_Longint          number;             /**< successively assigned number of the node */
144  	   SCIP_Real             lowerbound;         /**< lower (dual) bound of subtree */
145  	   SCIP_Real             estimate;           /**< estimated value of feasible solution in subtree */
146  	   union
147  	   {
148  	      SCIP_PROBINGNODE*  probingnode;        /**< data for probing nodes */
149  	      SCIP_SIBLING       sibling;            /**< data for sibling nodes */
150  	      SCIP_CHILD         child;              /**< data for child nodes */
151  	      SCIP_LEAF          leaf;               /**< data for leaf nodes */
152  	      SCIP_JUNCTION      junction;           /**< data for junction nodes */
153  	      SCIP_PSEUDOFORK*   pseudofork;         /**< data for pseudo fork nodes */
154  	      SCIP_FORK*         fork;               /**< data for fork nodes */
155  	      SCIP_SUBROOT*      subroot;            /**< data for subroot nodes */
156  	   } data;
157  	   SCIP_NODE*            parent;             /**< parent node in the tree */
158  	   SCIP_CONSSETCHG*      conssetchg;         /**< constraint set changes at this node or NULL */
159  	   SCIP_DOMCHG*          domchg;             /**< domain changes at this node or NULL */
160  	   unsigned int          depth:30;           /**< depth in the tree */
161  	   unsigned int          reoptid:32;         /**< unique id to identify the node during reoptimization */
162  	   unsigned int          reopttype:3;        /**< node type during reoptimization */
163  	   unsigned int          repropsubtreemark:9;/**< subtree repropagation marker for subtree repropagation */
164  	   unsigned int          active:1;           /**< is node in the path to the current node? */
165  	   unsigned int          cutoff:1;           /**< should the node and all sub nodes be cut off from the tree? */
166  	   unsigned int          reprop:1;           /**< should propagation be applied again, if the node is on the active path? */
167  	   unsigned int          nodetype:4;         /**< type of node */
168  	};
169  	
170  	/** bound change information for pending bound changes */
171  	struct SCIP_PendingBdchg
172  	{
173  	   SCIP_NODE*            node;               /**< node to add bound change to */
174  	   SCIP_VAR*             var;                /**< variable to change the bounds for */
175  	   SCIP_Real             newbound;           /**< new value for bound */
176  	   SCIP_BOUNDTYPE        boundtype;          /**< type of bound: lower or upper bound */
177  	   SCIP_CONS*            infercons;          /**< constraint that deduced the bound change, or NULL */
178  	   SCIP_PROP*            inferprop;          /**< propagator that deduced the bound change, or NULL */
179  	   int                   inferinfo;          /**< user information for inference to help resolving the conflict */
180  	   SCIP_Bool             probingchange;      /**< is the bound change a temporary setting due to probing? */
181  	};
182  	
183  	/** branch and bound tree */
184  	struct SCIP_Tree
185  	{
186  	   SCIP_NODE*            root;               /**< root node of the tree */
187  	   SCIP_NODEPQ*          leaves;             /**< leaves of the tree */
188  	   SCIP_NODE**           path;               /**< array of nodes storing the active path from root to current node, which
189  	                                              *   is usually the focus or a probing node; in case of a cut off, the path
190  	                                              *   may already end earlier */
191  	   SCIP_NODE*            focusnode;          /**< focus node: the node that is stored together with its children and
192  	                                              *   siblings in the tree data structure; the focus node is the currently
193  	                                              *   processed node; it doesn't need to be active all the time, because it
194  	                                              *   may be cut off and the active path stops at the cut off node */
195  	   SCIP_NODE*            focuslpfork;        /**< LP defining pseudofork/fork/subroot of the focus node */
196  	   SCIP_NODE*            focuslpstatefork;   /**< LP state defining fork/subroot of the focus node */
197  	   SCIP_NODE*            focussubroot;       /**< subroot of the focus node's sub tree */
198  	   SCIP_NODE*            probingroot;        /**< root node of the current probing path, or NULL */
199  	   SCIP_NODE**           children;           /**< array with children of the focus node */
200  	   SCIP_NODE**           siblings;           /**< array with siblings of the focus node */
201  	   SCIP_Real*            childrenprio;       /**< array with node selection priorities of children */
202  	   SCIP_Real*            siblingsprio;       /**< array with node selection priorities of siblings */
203  	   SCIP_VAR**            divebdchgvars[2];   /**< two arrays to store variables for branching */
204  	   SCIP_BRANCHDIR*       divebdchgdirs[2];   /**< arrays to hold the directions for diving */
205  	   SCIP_Real*            divebdchgvals[2];   /**< arrays to store bound change values for diving */
206  	   int*                  pathnlpcols;        /**< array with number of LP columns for each problem in active path (except
207  	                                              *   newly added columns of the focus node and the current probing node) */
208  	   int*                  pathnlprows;        /**< array with number of LP rows for each problem in active path (except
209  	                                              *   newly added rows of the focus node and the current probing node) */
210  	   SCIP_LPISTATE*        probinglpistate;    /**< LP state information before probing started */
211  	   SCIP_LPISTATE*        focuslpistate;      /**< LP state information of focus node */
212  	   SCIP_LPINORMS*        probinglpinorms;    /**< LP pricing norms information before probing started */
213  	   SCIP_PENDINGBDCHG*    pendingbdchgs;      /**< array of pending bound changes, or NULL */
214  	   SCIP_Real*            probdiverelaxsol;   /**< array with stored original relaxation solution during diving or probing */
215  	   int                   nprobdiverelaxsol;  /**< size of probdiverelaxsol */
216  	   SCIP_Longint          focuslpstateforklpcount; /**< LP number of last solved LP in current LP state fork, or -1 if unknown */
217  	   SCIP_Longint          lastbranchparentid; /**< last node id/number of branching parent */
218  	   int                   divebdchgsize[2];   /**< holds the two sizes of the dive bound change information */
219  	   int                   ndivebdchanges[2];  /**< current number of stored dive bound changes for the next depth */
220  	   int                   pendingbdchgssize;  /**< size of pendingbdchgs array */
221  	   int                   npendingbdchgs;     /**< number of pending bound changes */
222  	   int                   childrensize;       /**< available slots in children vector */
223  	   int                   nchildren;          /**< number of children of focus node (number of used slots in children vector) */
224  	   int                   siblingssize;       /**< available slots in siblings vector */
225  	   int                   nsiblings;          /**< number of siblings of focus node (number of used slots in siblings vector) */
226  	   int                   pathlen;            /**< length of the current path */
227  	   int                   pathsize;           /**< number of available slots in path arrays */
228  	   int                   effectiverootdepth; /**< first depth with node with at least two children */
229  	   int                   appliedeffectiverootdepth; /**< the effective root depth which was already enforced (that is constraint and bound changes were made global) */
230  	   int                   correctlpdepth;     /**< depth to which current LP data corresponds to LP data of active path */
231  	   int                   cutoffdepth;        /**< depth of first node in active path that is marked being cutoff */
232  	   int                   repropdepth;        /**< depth of first node in active path that has to be propagated again */
233  	   int                   repropsubtreecount; /**< cyclicly increased counter to create markers for subtree repropagation */
234  	   int                   probingsumchgdobjs; /**< number of changed objective coefficients in all probing nodes */
235  	   SCIP_Bool             focusnodehaslp;     /**< is LP being processed in the focus node? */
236  	   SCIP_Bool             probingnodehaslp;   /**< was the LP solved (at least once) in the current probing node? */
237  	   SCIP_Bool             focuslpconstructed; /**< was the LP of the focus node already constructed? */
238  	   SCIP_Bool             cutoffdelayed;      /**< the treeCutoff() call was delayed because of diving and has to be executed */
239  	   SCIP_Bool             probinglpwasflushed;/**< was the LP flushed before we entered the probing mode? */
240  	   SCIP_Bool             probinglpwassolved; /**< was the LP solved before we entered the probing mode? */
241  	   SCIP_Bool             probingloadlpistate;/**< must the LP state be reloaded because of a backtrack in probing? */
242  	   SCIP_Bool             probinglpwasrelax;  /**< was the LP a valid relaxation before we entered the probing mode? */
243  	   SCIP_Bool             probingsolvedlp;    /**< was the LP solved during probing mode, i.e., was SCIPsolveProbingLP() called? */
244  	   SCIP_Bool             forcinglpmessage;   /**< was forcing LP solving message be posted */
245  	   SCIP_Bool             probingobjchanged;  /**< was the objective function changed during probing? */
246  	   SCIP_Bool             sbprobing;          /**< is the probing mode used for strong branching? */
247  	   SCIP_Bool             probinglpwasprimfeas;/**< primal feasibility when probing started */
248  	   SCIP_Bool             probinglpwasprimchecked;/**< primal feasibility has been checked when probing started */
249  	   SCIP_Bool             probinglpwasdualfeas;/**< dual feasibility when probing started */
250  	   SCIP_Bool             probinglpwasdualchecked;/**< dual feasibility has been check when probing started */
251  	   SCIP_Bool             probdiverelaxstored; /**< was a relax solution stored before diving or probing ? */
252  	   SCIP_Bool             probdiverelaxincludeslp; /**< did the stored relaxation solution include all lp cuts ? */
253  	};
254  	
255  	#ifdef __cplusplus
256  	}
257  	#endif
258  	
259  	#endif
260