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_misc.h 26 * @ingroup INTERNALAPI 27 * @brief miscellaneous datastructures 28 * @author Tobias Achterberg 29 */ 30 31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 32 33 #ifndef __SCIP_STRUCT_MISC_H__ 34 #define __SCIP_STRUCT_MISC_H__ 35 36 37 #include "scip/def.h" 38 #include "blockmemshell/memory.h" 39 #include "scip/type_misc.h" 40 41 #ifdef __cplusplus 42 extern "C" { 43 #endif 44 45 /** data structure for sparse solutions */ 46 struct SCIP_SparseSol 47 { 48 SCIP_VAR** vars; /**< variables */ 49 SCIP_Longint* lbvalues; /**< array of lower bounds */ 50 SCIP_Longint* ubvalues; /**< array of upper bounds */ 51 int nvars; /**< number of variables */ 52 }; 53 54 typedef union { 55 void* ptr; /**< pointer element */ 56 unsigned int uinteger; /**< unsigned integer element */ 57 } SCIP_QUEUEELEMENT; 58 59 /** (circular) Queue data structure */ 60 struct SCIP_Queue 61 { 62 SCIP_Real sizefac; /**< memory growing factor */ 63 SCIP_QUEUEELEMENT* slots; /**< array of element slots */ 64 int firstfree; /**< first free slot */ 65 int firstused; /**< first used slot */ 66 int size; /**< total number of available element slots */ 67 }; 68 69 /** priority queue data structure 70 * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue. 71 * The ordering is done through a pointer comparison function. 72 * The array is organized as follows. The root element (that is the "best" element \f$ r \f$ with \f$ r \leq x \f$ for all \f$ x \f$ ) 73 * is stored in position 0. The children of an element at position \f$ p \f$ are stored at positions \f$ q_1 = 2*p+1 \f$ and 74 * \f$ q_2 = 2*p+2 \f$ . That means, the parent of the element at position \f$ q \f$ is at position \f$ p = (q-1)/2 \f$ . 75 * At any time, the condition holds that \f$ p \leq q \f$ for each parent \f$ p \f$ and its children \f$ q \f$ . 76 * Insertion and removal of single elements needs time \f$ O(log n) \f$ . 77 */ 78 struct SCIP_PQueue 79 { 80 SCIP_Real sizefac; /**< memory growing factor */ 81 SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */ 82 SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos));/**< callback to act on position change of elem in priority queue, or NULL */ 83 void** slots; /**< array of element slots */ 84 int len; /**< number of used element slots */ 85 int size; /**< total number of available element slots */ 86 }; 87 88 /** hash table data structure */ 89 struct SCIP_HashTable 90 { 91 SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */ 92 SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */ 93 SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */ 94 BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */ 95 void* userptr; /**< user pointer */ 96 void** slots; /**< slots of the hash table */ 97 uint32_t* hashes; /**< hash values of elements stored in slots */ 98 uint32_t shift; /**< power such that 2^(32-shift) == nslots */ 99 uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */ 100 uint32_t nelements; /**< number of elements in the hashtable */ 101 }; 102 103 /** element list to store single elements of a hash table */ 104 struct SCIP_MultiHashList 105 { 106 void* element; /**< this element */ 107 SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */ 108 }; 109 110 /** multihash table data structure */ 111 struct SCIP_MultiHash 112 { 113 SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */ 114 SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */ 115 SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */ 116 BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */ 117 SCIP_MULTIHASHLIST** lists; /**< multihash table lists of the hash table */ 118 int nlists; /**< number of lists stored in the hash table */ 119 void* userptr; /**< user pointer */ 120 SCIP_Longint nelements; /**< number of elements in the hashtable */ 121 }; 122 123 typedef union { 124 void* ptr; /**< pointer image */ 125 int integer; /**< integer image */ 126 SCIP_Real real; /**< real image */ 127 } SCIP_HASHMAPIMAGE; 128 129 /** hash map entry */ 130 struct SCIP_HashMapEntry 131 { 132 void* origin; /**< origin of element */ 133 SCIP_HASHMAPIMAGE image; /**< image of element */ 134 }; 135 136 /** hash map data structure to map pointers on pointers */ 137 struct SCIP_HashMap 138 { 139 BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */ 140 SCIP_HASHMAPENTRY* slots; /**< buffer for hashmap entries */ 141 uint32_t* hashes; /**< hashes of elements */ 142 uint32_t shift; /**< power such that 2^(32-shift) == nslots */ 143 uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */ 144 uint32_t nelements; /**< number of elements in the hashtable */ 145 SCIP_HASHMAPTYPE hashmaptype; /**< type of entries */ 146 }; 147 148 /** lightweight hash set data structure to map pointers on pointers */ 149 struct SCIP_HashSet 150 { 151 void** slots; /**< buffer for hashmap entries */ 152 uint32_t shift; /**< power such that 2^(64-shift) == nslots */ 153 uint32_t nelements; /**< number of elements in the hashtable */ 154 }; 155 156 /** dynamic array for storing real values */ 157 struct SCIP_RealArray 158 { 159 BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ 160 SCIP_Real* vals; /**< array values */ 161 int valssize; /**< size of vals array */ 162 int firstidx; /**< index of first element in vals array */ 163 int minusedidx; /**< index of first non zero element in vals array */ 164 int maxusedidx; /**< index of last non zero element in vals array */ 165 }; 166 167 /** dynamic array for storing int values */ 168 struct SCIP_IntArray 169 { 170 BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ 171 int* vals; /**< array values */ 172 int valssize; /**< size of vals array */ 173 int firstidx; /**< index of first element in vals array */ 174 int minusedidx; /**< index of first non zero element in vals array */ 175 int maxusedidx; /**< index of last non zero element in vals array */ 176 }; 177 178 /** dynamic array for storing bool values */ 179 struct SCIP_BoolArray 180 { 181 BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ 182 SCIP_Bool* vals; /**< array values */ 183 int valssize; /**< size of vals array */ 184 int firstidx; /**< index of first element in vals array */ 185 int minusedidx; /**< index of first non zero element in vals array */ 186 int maxusedidx; /**< index of last non zero element in vals array */ 187 }; 188 189 /** dynamic array for storing pointers */ 190 struct SCIP_PtrArray 191 { 192 BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */ 193 void** vals; /**< array values */ 194 int valssize; /**< size of vals array */ 195 int firstidx; /**< index of first element in vals array */ 196 int minusedidx; /**< index of first non zero element in vals array */ 197 int maxusedidx; /**< index of last non zero element in vals array */ 198 }; 199 200 /** resource activity */ 201 struct SCIP_ResourceActivity 202 { 203 SCIP_VAR* var; /**< start time variable of the activity */ 204 int duration; /**< duration of the activity */ 205 int demand; /**< demand of the activity */ 206 }; 207 208 /** resource profile */ 209 struct SCIP_Profile 210 { 211 int* timepoints; /**< time point array */ 212 int* loads; /**< array holding the load for each time point */ 213 int capacity; /**< capacity of the resource profile */ 214 int ntimepoints; /**< current number of entries */ 215 int arraysize; /**< current array size */ 216 }; 217 218 /** digraph structure to store and handle graphs */ 219 struct SCIP_Digraph 220 { 221 BMS_BLKMEM* blkmem; /**< block memory pointer to store the data */ 222 int** successors; /**< adjacency list: for each node (first dimension) list of all successors */ 223 void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */ 224 void** nodedata; /**< data for each node of graph */ 225 int* successorssize; /**< sizes of the successor lists for the nodes */ 226 int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */ 227 int* components; /**< array to store the node indices of the components, one component after the other */ 228 int* componentstarts; /**< array to store the start indices of the components in the components array */ 229 int* articulations; /**< array of size narticulations to store the node indices of the articulation points */ 230 int ncomponents; /**< number of undirected components stored */ 231 int componentstartsize; /**< size of array componentstarts */ 232 int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */ 233 int narticulations; /**< number of articulation points among the graph nodes */ 234 SCIP_Bool articulationscheck; /**< TRUE if the (computed) articulation nodes are up-to-date and FALSE otherwise */ 235 }; 236 237 /** binary node data structure for binary tree */ 238 struct SCIP_BtNode 239 { 240 SCIP_BTNODE* parent; /**< pointer to the parent node */ 241 SCIP_BTNODE* left; /**< pointer to the left child node */ 242 SCIP_BTNODE* right; /**< pointer to the right child node */ 243 void* dataptr; /**< user pointer */ 244 }; 245 246 /** binary search tree data structure */ 247 struct SCIP_Bt 248 { 249 SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */ 250 BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */ 251 }; 252 253 /** data structure for incremental linear regression of data points (X_i, Y_i) */ 254 struct SCIP_Regression 255 { 256 SCIP_Real intercept; /**< the current axis intercept of the regression */ 257 SCIP_Real slope; /**< the current slope of the regression */ 258 SCIP_Real meanx; /**< mean of all X observations */ 259 SCIP_Real meany; /**< mean of all Y observations */ 260 SCIP_Real sumxy; /**< accumulated sum of all products X * Y */ 261 SCIP_Real variancesumx; /**< incremental variance term for X observations */ 262 SCIP_Real variancesumy; /**< incremental variance term for Y observations */ 263 SCIP_Real corrcoef; /**< correlation coefficient of X and Y */ 264 int nobservations; /**< number of observations so far */ 265 }; 266 267 /** random number generator data */ 268 struct SCIP_RandNumGen 269 { 270 uint32_t seed; /**< start seed */ 271 uint32_t xor_seed; /**< Xorshift seed */ 272 uint32_t mwc_seed; /**< Multiply-with-carry seed */ 273 uint32_t cst_seed; /**< constant seed */ 274 }; 275 276 /** disjoint set (disjoint set (union find)) data structure for querying and updating connectedness in a graph with integer vertices 0,...,n - 1 */ 277 struct SCIP_DisjointSet 278 { 279 int* parents; /**< array to store the parent node index for every vertex */ 280 int* sizes; /**< array to store the size of the subtree rooted at each vertex */ 281 int size; /**< the number of vertices in the graph */ 282 int componentcount; /**< counter for the number of connected components of the graph */ 283 }; 284 285 /** a linear inequality row in preparation to become a SCIP_ROW */ 286 struct SCIP_RowPrep 287 { 288 SCIP_VAR** vars; /**< variables */ 289 SCIP_Real* coefs; /**< coefficients of variables */ 290 int nvars; /**< number of variables (= number of coefficients) */ 291 int varssize; /**< length of variables array (= lengths of coefficients array) */ 292 SCIP_Real side; /**< side */ 293 SCIP_SIDETYPE sidetype; /**< type of side */ 294 SCIP_Bool local; /**< whether the row is only locally valid (i.e., for the current node) */ 295 char name[SCIP_MAXSTRLEN]; /**< row name */ 296 297 SCIP_Bool recordmodifications;/**< whether to remember variables which coefficients were modified during cleanup */ 298 SCIP_VAR** modifiedvars; /**< variables which coefficient were modified by cleanup */ 299 int nmodifiedvars; /**< number of variables which coefficient was modified */ 300 int modifiedvarssize; /**< length of `modifiedvars` array */ 301 SCIP_Bool modifiedside; /**< whether the side was modified (relaxed) by cleanup */ 302 }; 303 304 #ifdef __cplusplus 305 } 306 #endif 307 308 #endif 309