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