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 */ 55 struct SCIP_Probingnode 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) */ 73 struct SCIP_Sibling 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 */ 91 struct SCIP_Junction 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 */ 97 struct SCIP_Pseudofork 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 */ 124 struct SCIP_Subroot 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: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 */ 171 struct SCIP_PendingBdchg 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 260