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