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