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-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  */
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) */
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 */
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 */
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 */
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:16; /**< depth in the tree */
161  unsigned int nodetype:4; /**< type of node */
162  unsigned int active:1; /**< is node in the path to the current node? */
163  unsigned int cutoff:1; /**< should the node and all sub nodes be cut off from the tree? */
164  unsigned int reprop:1; /**< should propagation be applied again, if the node is on the active path? */
165  unsigned int repropsubtreemark:9;/**< subtree repropagation marker for subtree repropagation */
166  unsigned int reoptid:29; /**< unique id to identify the node during reoptimization */
167  unsigned int reopttype:3; /**< node type during reoptimization */
168 };
169 
170 /** bound change information for pending bound changes */
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
SCIP_NODE * node
Definition: struct_tree.h:173
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
SCIP_NODE * lpstatefork
Definition: struct_tree.h:87
SCIP_Bool lpwasdualchecked
Definition: struct_tree.h:69
SCIP_PSEUDOFORK * pseudofork
Definition: struct_tree.h:153
SCIP_NODE * focussubroot
Definition: struct_tree.h:197
unsigned int lpwasdualfeas
Definition: struct_tree.h:136
SCIP_Real * origobjvals
Definition: struct_tree.h:64
int naddedcols
Definition: struct_tree.h:113
SCIP_Longint lastbranchparentid
Definition: struct_tree.h:217
SCIP_Longint focuslpstateforklpcount
Definition: struct_tree.h:216
int * pathnlprows
Definition: struct_tree.h:208
unsigned int active
Definition: struct_tree.h:162
SCIP_PROBINGNODE * probingnode
Definition: struct_tree.h:148
unsigned int repropsubtreemark
Definition: struct_tree.h:165
int naddedrows
Definition: struct_tree.h:114
SCIP_Bool probingchange
Definition: struct_tree.h:180
SCIP_VAR * var
Definition: struct_tree.h:174
SCIP_Real newbound
Definition: struct_tree.h:175
unsigned int lpwasdualchecked
Definition: struct_tree.h:120
unsigned int cutoff
Definition: struct_tree.h:163
SCIP_Bool probdiverelaxstored
Definition: struct_tree.h:251
unsigned int nodetype
Definition: struct_tree.h:161
SCIP_LPINORMS * probinglpinorms
Definition: struct_tree.h:212
SCIP_Bool probinglpwasdualchecked
Definition: struct_tree.h:250
unsigned int reprop
Definition: struct_tree.h:164
SCIP_Bool sbprobing
Definition: struct_tree.h:246
SCIP_Real estimate
Definition: struct_tree.h:145
SCIP_FORK * fork
Definition: struct_tree.h:154
SCIP_Real lpobjval
Definition: struct_tree.h:129
SCIP_Bool probinglpwasflushed
Definition: struct_tree.h:239
SCIP_COL ** addedcols
Definition: struct_tree.h:109
SCIP_Bool probingsolvedlp
Definition: struct_tree.h:243
SCIP_NODE ** siblings
Definition: struct_tree.h:200
SCIP_JUNCTION junction
Definition: struct_tree.h:152
unsigned int lpwasdualfeas
Definition: struct_tree.h:119
int childrensize
Definition: struct_tree.h:222
unsigned int reoptid
Definition: struct_tree.h:166
int pathsize
Definition: struct_tree.h:227
int npendingbdchgs
Definition: struct_tree.h:221
SCIP_Real lpobjval
Definition: struct_tree.h:112
SCIP_Longint number
Definition: struct_tree.h:143
SCIP_ROW ** rows
Definition: struct_tree.h:127
unsigned int lpwasprimchecked
Definition: struct_tree.h:118
type definitions for LP management
int nlpistateref
Definition: struct_tree.h:115
int pendingbdchgssize
Definition: struct_tree.h:220
SCIP_Real * siblingsprio
Definition: struct_tree.h:202
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
SCIP_LPISTATE * lpistate
Definition: struct_tree.h:111
unsigned int lpwasprimchecked
Definition: struct_tree.h:135
SCIP_Bool probinglpwassolved
Definition: struct_tree.h:240
SCIP_Bool probingloadlpistate
Definition: struct_tree.h:241
SCIP_DOMCHG * domchg
Definition: struct_tree.h:159
SCIP_Bool forcinglpmessage
Definition: struct_tree.h:244
int nsiblings
Definition: struct_tree.h:225
int cutoffdepth
Definition: struct_tree.h:231
SCIP_Real * childrenprio
Definition: struct_tree.h:201
SCIP_SUBROOT * subroot
Definition: struct_tree.h:155
SCIP_Bool probingobjchanged
Definition: struct_tree.h:245
unsigned int reopttype
Definition: struct_tree.h:167
int repropsubtreecount
Definition: struct_tree.h:233
int siblingssize
Definition: struct_tree.h:224
SCIP_LPISTATE * probinglpistate
Definition: struct_tree.h:210
SCIP_NODE ** path
Definition: struct_tree.h:188
int repropdepth
Definition: struct_tree.h:232
SCIP_NODE * focuslpstatefork
Definition: struct_tree.h:196
type definitions for specific LP solvers interface
int appliedeffectiverootdepth
Definition: struct_tree.h:229
SCIP_Real * probdiverelaxsol
Definition: struct_tree.h:214
int correctlpdepth
Definition: struct_tree.h:230
SCIP_SIBLING sibling
Definition: struct_tree.h:149
SCIP_NODEPQ * leaves
Definition: struct_tree.h:187
type definitions for problem variables
SCIP_Bool probinglpwasprimchecked
Definition: struct_tree.h:248
SCIP_COL ** cols
Definition: struct_tree.h:126
SCIP_CONS * infercons
Definition: struct_tree.h:177
SCIP_BOUNDTYPE boundtype
Definition: struct_tree.h:176
SCIP_LPINORMS * lpinorms
Definition: struct_tree.h:58
SCIP_LEAF leaf
Definition: struct_tree.h:151
SCIP_Bool lpwasdualfeas
Definition: struct_tree.h:68
#define SCIP_Bool
Definition: def.h:93
int arraypos
Definition: struct_tree.h:81
SCIP_Bool lpwasprimchecked
Definition: struct_tree.h:67
SCIP_Bool focuslpconstructed
Definition: struct_tree.h:237
int nprobdiverelaxsol
Definition: struct_tree.h:215
unsigned int depth
Definition: struct_tree.h:160
SCIP_NODE ** children
Definition: struct_tree.h:199
SCIP_VAR ** origobjvars
Definition: struct_tree.h:63
unsigned int lpwasdualchecked
Definition: struct_tree.h:137
int probingsumchgdobjs
Definition: struct_tree.h:234
SCIP_Bool lpwasprimfeas
Definition: struct_tree.h:66
SCIP_ROW ** addedrows
Definition: struct_tree.h:100
int * pathnlpcols
Definition: struct_tree.h:206
SCIP_Bool probinglpwasrelax
Definition: struct_tree.h:242
type definitions for branch and bound tree
SCIP_Bool cutoffdelayed
Definition: struct_tree.h:238
SCIP_Bool probdiverelaxincludeslp
Definition: struct_tree.h:252
SCIP_CONSSETCHG * conssetchg
Definition: struct_tree.h:158
SCIP_NODE * probingroot
Definition: struct_tree.h:198
type definitions for propagators
SCIP_NODE * parent
Definition: struct_tree.h:157
SCIP_LPISTATE * lpistate
Definition: struct_tree.h:57
SCIP_NODE * focuslpfork
Definition: struct_tree.h:195
SCIP_Real lowerbound
Definition: struct_tree.h:144
SCIP_LPISTATE * lpistate
Definition: struct_tree.h:128
#define SCIP_Real
Definition: def.h:186
type definitions for branching and inference history
int effectiverootdepth
Definition: struct_tree.h:228
#define SCIP_Longint
Definition: def.h:171
SCIP_COL ** addedcols
Definition: struct_tree.h:99
SCIP_Bool probinglpwasprimfeas
Definition: struct_tree.h:247
int nchildren
Definition: struct_tree.h:223
unsigned int lpwasprimfeas
Definition: struct_tree.h:134
common defines and data types used in all packages of SCIP
SCIP_PENDINGBDCHG * pendingbdchgs
Definition: struct_tree.h:213
SCIP_Bool probingnodehaslp
Definition: struct_tree.h:236
SCIP_NODE * root
Definition: struct_tree.h:186
SCIP_LPISTATE * focuslpistate
Definition: struct_tree.h:211
SCIP_CHILD child
Definition: struct_tree.h:150
unsigned int nchildren
Definition: struct_tree.h:133
type definitions for node selectors
SCIP_PROP * inferprop
Definition: struct_tree.h:178
SCIP_ROW ** addedrows
Definition: struct_tree.h:110
unsigned int lpwasprimfeas
Definition: struct_tree.h:117
unsigned int nchildren
Definition: struct_tree.h:116
type definitions for constraints and constraint handlers
SCIP_Bool probinglpwasdualfeas
Definition: struct_tree.h:249
SCIP_NODE * focusnode
Definition: struct_tree.h:191
SCIP_Bool focusnodehaslp
Definition: struct_tree.h:235