Scippy

SCIP

Solving Constraint Integer Programs

struct_tree.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_tree.h
17  * @brief datastructures for branch and bound tree
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_STRUCT_TREE_H__
24 #define __SCIP_STRUCT_TREE_H__
25 
26 
27 #include "scip/def.h"
28 #include "scip/type_lp.h"
29 #include "scip/type_var.h"
30 #include "scip/type_tree.h"
31 #include "scip/type_cons.h"
32 #include "scip/type_nodesel.h"
33 #include "lpi/type_lpi.h"
34 
35 
36 #ifdef __cplusplus
37 extern "C" {
38 #endif
39 
40 /** probing node, possibly with solved LP, where bounds and constraints have been changed,
41  * and rows and columns might have been added
42  */
43 struct SCIP_Probingnode
44 {
45  SCIP_LPISTATE* lpistate; /**< LP state information */
46  int ninitialcols; /**< number of LP columns before the node was processed */
47  int ninitialrows; /**< number of LP rows before the node was processed */
48  int ncols; /**< total number of columns of this node's LP */
49  int nrows; /**< total number of rows of this node's LP */
50  SCIP_Bool lpwasprimfeas; /**< primal feasibility of saved LP state information */
51  SCIP_Bool lpwasdualfeas; /**< dual feasibility of saved LP state information */
52 };
53 
54 /** sibling information (should not exceed the size of a pointer) */
55 struct SCIP_Sibling
56 {
57  int arraypos; /**< position of node in the siblings array */
58 };
59 
60 /** child information (should not exceed the size of a pointer) */
61 struct SCIP_Child
62 {
63  int arraypos; /**< position of node in the children array */
64 };
65 
66 /** leaf information (should not exceed the size of a pointer) */
67 struct SCIP_Leaf
68 {
69  SCIP_NODE* lpstatefork; /**< fork/subroot node defining the LP state of the leaf */
70 };
71 
72 /** fork without LP solution, where only bounds and constraints have been changed */
73 struct SCIP_Junction
74 {
75  int nchildren; /**< number of children of this parent node */
76 };
77 
78 /** fork without LP solution, where bounds and constraints have been changed, and rows and columns were added */
79 struct SCIP_Pseudofork
80 {
81  SCIP_COL** addedcols; /**< array with pointers to new columns added at this node into the LP */
82  SCIP_ROW** addedrows; /**< array with pointers to new rows added at this node into the LP */
83  int naddedcols; /**< number of columns added at this node */
84  int naddedrows; /**< number of rows added at this node */
85  int nchildren; /**< number of children of this parent node */
86 };
87 
88 /** fork with solved LP, where bounds and constraints have been changed, and rows and columns were added */
89 struct SCIP_Fork
90 {
91  SCIP_COL** addedcols; /**< array with pointers to new columns added at this node into the LP */
92  SCIP_ROW** addedrows; /**< array with pointers to new rows added at this node into the LP */
93  SCIP_LPISTATE* lpistate; /**< LP state information */
94  SCIP_Real lpobjval; /**< the LP objective value for that node, needed to compute the pseudo costs correctly */
95  int naddedcols; /**< number of columns added at this node */
96  int naddedrows; /**< number of rows added at this node */
97  int nlpistateref; /**< number of times, the LP state is needed */
98  unsigned int nchildren:30; /**< number of children of this parent node */
99  unsigned int lpwasprimfeas:1; /**< primal feasibility of saved LP state information */
100  unsigned int lpwasdualfeas:1; /**< dual feasibility of saved LP state information */
101 };
102 
103 /** fork with solved LP, where bounds and constraints have been changed, and rows and columns were removed and added */
104 struct SCIP_Subroot
105 {
106  SCIP_COL** cols; /**< array with pointers to the columns in the same order as in the LP */
107  SCIP_ROW** rows; /**< array with pointers to the rows in the same order as in the LP */
108  SCIP_LPISTATE* lpistate; /**< LP state information */
109  SCIP_Real lpobjval; /**< the LP objective value for that node, needed to compute the pseudo costs correctly */
110  int ncols; /**< number of columns in the LP */
111  int nrows; /**< number of rows in the LP */
112  int nlpistateref; /**< number of times, the LP state is needed */
113  unsigned int nchildren:30; /**< number of children of this parent node */
114  unsigned int lpwasprimfeas:1; /**< primal feasibility of saved LP state information */
115  unsigned int lpwasdualfeas:1; /**< dual feasibility of saved LP state information */
116 };
117 
118 /** node data structure */
119 struct SCIP_Node
120 {
121  SCIP_Longint number; /**< successively assigned number of the node */
122  SCIP_Real lowerbound; /**< lower (dual) bound of subtree */
123  SCIP_Real estimate; /**< estimated value of feasible solution in subtree */
124  union
125  {
126  SCIP_PROBINGNODE* probingnode; /**< data for probing nodes */
127  SCIP_SIBLING sibling; /**< data for sibling nodes */
128  SCIP_CHILD child; /**< data for child nodes */
129  SCIP_LEAF leaf; /**< data for leaf nodes */
130  SCIP_JUNCTION junction; /**< data for junction nodes */
131  SCIP_PSEUDOFORK* pseudofork; /**< data for pseudo fork nodes */
132  SCIP_FORK* fork; /**< data for fork nodes */
133  SCIP_SUBROOT* subroot; /**< data for subroot nodes */
134  } data;
135  SCIP_NODE* parent; /**< parent node in the tree */
136  SCIP_CONSSETCHG* conssetchg; /**< constraint set changes at this node or NULL */
137  SCIP_DOMCHG* domchg; /**< domain changes at this node or NULL */
138  unsigned int depth:16; /**< depth in the tree */
139  unsigned int nodetype:4; /**< type of node */
140  unsigned int active:1; /**< is node in the path to the current node? */
141  unsigned int cutoff:1; /**< should the node and all sub nodes be cut off from the tree? */
142  unsigned int reprop:1; /**< should propagation be applied again, if the node is on the active path? */
143  unsigned int repropsubtreemark:9;/**< subtree repropagation marker for subtree repropagation */
144 };
145 
146 /** bound change information for pending bound changes */
147 struct SCIP_PendingBdchg
148 {
149  SCIP_NODE* node; /**< node to add bound change to */
150  SCIP_VAR* var; /**< variable to change the bounds for */
151  SCIP_Real newbound; /**< new value for bound */
152  SCIP_BOUNDTYPE boundtype; /**< type of bound: lower or upper bound */
153  SCIP_CONS* infercons; /**< constraint that deduced the bound change, or NULL */
154  SCIP_PROP* inferprop; /**< propagator that deduced the bound change, or NULL */
155  int inferinfo; /**< user information for inference to help resolving the conflict */
156  SCIP_Bool probingchange; /**< is the bound change a temporary setting due to probing? */
157 };
158 
159 /** branch and bound tree */
160 struct SCIP_Tree
161 {
162  SCIP_NODE* root; /**< root node of the tree */
163  SCIP_NODEPQ* leaves; /**< leaves of the tree */
164  SCIP_NODE** path; /**< array of nodes storing the active path from root to current node, which
165  * is usually the focus or a probing node; in case of a cut off, the path
166  * may already end earlier */
167  SCIP_NODE* focusnode; /**< focus node: the node that is stored together with its children and
168  * siblings in the tree data structure; the focus node is the currently
169  * processed node; it doesn't need to be active all the time, because it
170  * may be cut off and the active path stops at the cut off node */
171  SCIP_NODE* focuslpfork; /**< LP defining pseudofork/fork/subroot of the focus node */
172  SCIP_NODE* focuslpstatefork; /**< LP state defining fork/subroot of the focus node */
173  SCIP_NODE* focussubroot; /**< subroot of the focus node's sub tree */
174  SCIP_NODE* probingroot; /**< root node of the current probing path, or NULL */
175  SCIP_NODE** children; /**< array with children of the focus node */
176  SCIP_NODE** siblings; /**< array with siblings of the focus node */
177  SCIP_Real* childrenprio; /**< array with node selection priorities of children */
178  SCIP_Real* siblingsprio; /**< array with node selection priorities of siblings */
179  int* pathnlpcols; /**< array with number of LP columns for each problem in active path (except
180  * newly added columns of the focus node and the current probing node) */
181  int* pathnlprows; /**< array with number of LP rows for each problem in active path (except
182  * newly added rows of the focus node and the current probing node) */
183  SCIP_LPISTATE* probinglpistate; /**< LP state information before probing started */
184  SCIP_LPINORMS* probinglpinorms; /**< LP pricing norms information before probing started */
185  SCIP_PENDINGBDCHG* pendingbdchgs; /**< array of pending bound changes, or NULL */
186  SCIP_Longint focuslpstateforklpcount; /**< LP number of last solved LP in current LP state fork, or -1 if unknown */
187  int pendingbdchgssize; /**< size of pendingbdchgs array */
188  int npendingbdchgs; /**< number of pending bound changes */
189  int childrensize; /**< available slots in children vector */
190  int nchildren; /**< number of children of focus node (number of used slots in children vector) */
191  int siblingssize; /**< available slots in siblings vector */
192  int nsiblings; /**< number of siblings of focus node (number of used slots in siblings vector) */
193  int pathlen; /**< length of the current path */
194  int pathsize; /**< number of available slots in path arrays */
195  int effectiverootdepth; /**< first depth with node with at least two children */
196  int appliedeffectiverootdepth; /**< the effective root depth which was already enforced (that is constraint and bound changes were made global) */
197  int correctlpdepth; /**< depth to which current LP data corresponds to LP data of active path */
198  int cutoffdepth; /**< depth of first node in active path that is marked being cutoff */
199  int repropdepth; /**< depth of first node in active path that has to be propagated again */
200  int repropsubtreecount; /**< cyclicly increased counter to create markers for subtree repropagation */
201  SCIP_Bool focusnodehaslp; /**< is LP being processed in the focus node? */
202  SCIP_Bool probingnodehaslp; /**< was the LP solved (at least once) in the current probing node? */
203  SCIP_Bool focuslpconstructed; /**< was the LP of the focus node already constructed? */
204  SCIP_Bool cutoffdelayed; /**< the treeCutoff() call was delayed because of diving and has to be executed */
205  SCIP_Bool probinglpwasflushed;/**< was the LP flushed before we entered the probing mode? */
206  SCIP_Bool probinglpwassolved; /**< was the LP solved before we entered the probing mode? */
207  SCIP_Bool probingloadlpistate;/**< must the LP state be reloaded because of a backtrack in probing? */
208  SCIP_Bool probinglpwasrelax; /**< was the LP a valid relaxation before we entered the probing mode? */
209  SCIP_Bool probingsolvedlp; /**< was the LP solved during probing mode, i.e., was SCIPsolveProbingLP() called? */
210  SCIP_Bool forcinglpmessage; /**< was forcing LP solving message be posted */
211  SCIP_Bool sbprobing; /**< is the probing mode used for strong branching? */
212  SCIP_Bool probinglpwasprimfeas;/**< primal feasibility when probing started */
213  SCIP_Bool probinglpwasdualfeas;/**< dual feasibility when probing started */
214 };
215 
216 #ifdef __cplusplus
217 }
218 #endif
219 
220 #endif
221