Scippy

SCIP

Solving Constraint Integer Programs

struct_misc.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 2002-2022 Zuse Institute Berlin */
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 */
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 */
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  */
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 */
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 */
105 {
106  void* element; /**< this element */
107  SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */
108 };
109 
110 /** multihash table data structure */
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 */
128 
129 /** hash map entry */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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) */
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 */
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 */
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 */
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
uint32_t * hashes
Definition: struct_misc.h:141
SCIP_BTNODE * parent
Definition: struct_misc.h:240
SCIP_Bool recordmodifications
Definition: struct_misc.h:297
void ** slots
Definition: struct_misc.h:96
SCIP_Real * vals
Definition: struct_misc.h:160
BMS_BLKMEM * blkmem
Definition: struct_misc.h:94
SCIP_QUEUEELEMENT * slots
Definition: struct_misc.h:63
void *** arcdata
Definition: struct_misc.h:223
BMS_BLKMEM * blkmem
Definition: struct_misc.h:221
#define SCIP_DECL_HASHKEYVAL(x)
Definition: type_misc.h:197
type definitions for miscellaneous datastructures
uint32_t shift
Definition: struct_misc.h:142
BMS_BLKMEM * blkmem
Definition: struct_misc.h:250
SCIP_Real intercept
Definition: struct_misc.h:256
#define SCIP_MAXSTRLEN
Definition: def.h:302
SCIP_Bool modifiedside
Definition: struct_misc.h:301
void ** nodedata
Definition: struct_misc.h:224
int firstfree
Definition: struct_misc.h:64
SCIP_Bool local
Definition: struct_misc.h:294
#define SCIP_DECL_HASHGETKEY(x)
Definition: type_misc.h:191
int * componentstarts
Definition: struct_misc.h:228
uint32_t * hashes
Definition: struct_misc.h:97
uint32_t shift
Definition: struct_misc.h:152
SCIP_SIDETYPE sidetype
Definition: struct_misc.h:293
uint32_t mwc_seed
Definition: struct_misc.h:272
uint32_t mask
Definition: struct_misc.h:99
void ** slots
Definition: struct_misc.h:151
uint32_t cst_seed
Definition: struct_misc.h:273
uint32_t nelements
Definition: struct_misc.h:100
SCIP_VAR ** vars
Definition: struct_misc.h:48
SCIP_MULTIHASHLIST ** lists
Definition: struct_misc.h:117
void * dataptr
Definition: struct_misc.h:243
unsigned int uinteger
Definition: struct_misc.h:56
SCIP_Real corrcoef
Definition: struct_misc.h:263
BMS_BLKMEM * blkmem
Definition: struct_misc.h:139
void * userptr
Definition: struct_misc.h:95
SCIP_BTNODE * root
Definition: struct_misc.h:249
int ** successors
Definition: struct_misc.h:222
void ** slots
Definition: struct_misc.h:83
SCIP_Real meany
Definition: struct_misc.h:259
BMS_BLKMEM * blkmem
Definition: struct_misc.h:159
BMS_BLKMEM * blkmem
Definition: struct_misc.h:170
SCIP_BTNODE * left
Definition: struct_misc.h:241
SCIP_VAR ** vars
Definition: struct_misc.h:288
int * timepoints
Definition: struct_misc.h:211
uint32_t mask
Definition: struct_misc.h:143
SCIP_Real variancesumx
Definition: struct_misc.h:261
SCIP_Real sizefac
Definition: struct_misc.h:80
SCIP_Longint * lbvalues
Definition: struct_misc.h:49
uint32_t shift
Definition: struct_misc.h:98
int narticulations
Definition: struct_misc.h:233
SCIP_Real slope
Definition: struct_misc.h:257
enum SCIP_Hashmaptype SCIP_HASHMAPTYPE
Definition: type_misc.h:63
uint32_t xor_seed
Definition: struct_misc.h:271
SCIP_Bool * vals
Definition: struct_misc.h:182
int * components
Definition: struct_misc.h:227
SCIP_Real side
Definition: struct_misc.h:292
#define SCIP_Bool
Definition: def.h:93
SCIP_Real variancesumy
Definition: struct_misc.h:262
int modifiedvarssize
Definition: struct_misc.h:300
int * successorssize
Definition: struct_misc.h:225
#define SCIP_DECL_PQUEUEELEMCHGPOS(x)
Definition: type_misc.h:208
int * articulations
Definition: struct_misc.h:229
SCIP_Longint * ubvalues
Definition: struct_misc.h:50
SCIP_Real sumxy
Definition: struct_misc.h:260
uint32_t nelements
Definition: struct_misc.h:153
SCIP_Bool articulationscheck
Definition: struct_misc.h:234
SCIP_Real meanx
Definition: struct_misc.h:258
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:188
SCIP_HASHMAPTYPE hashmaptype
Definition: struct_misc.h:145
SCIP_HASHMAPENTRY * slots
Definition: struct_misc.h:140
SCIP_BTNODE * right
Definition: struct_misc.h:242
SCIP_VAR ** modifiedvars
Definition: struct_misc.h:298
#define SCIP_Real
Definition: def.h:186
int componentstartsize
Definition: struct_misc.h:231
uint32_t nelements
Definition: struct_misc.h:144
BMS_BLKMEM * blkmem
Definition: struct_misc.h:116
BMS_BLKMEM * blkmem
Definition: struct_misc.h:181
#define SCIP_Longint
Definition: def.h:171
#define SCIP_DECL_HASHKEYEQ(x)
Definition: type_misc.h:194
void ** vals
Definition: struct_misc.h:193
SCIP_MULTIHASHLIST * next
Definition: struct_misc.h:107
BMS_BLKMEM * blkmem
Definition: struct_misc.h:192
int * nsuccessors
Definition: struct_misc.h:226
SCIP_Real * coefs
Definition: struct_misc.h:289
SCIP_Longint nelements
Definition: struct_misc.h:120
SCIP_Real sizefac
Definition: struct_misc.h:62
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
SCIP_HASHMAPIMAGE image
Definition: struct_misc.h:133
int firstused
Definition: struct_misc.h:65
memory allocation routines
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:67