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