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