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 (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_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"
39#include "scip/type_misc.h"
40
41#ifdef __cplusplus
42extern "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
54typedef union {
55 void* ptr; /**< pointer element */
56 unsigned int uinteger; /**< unsigned integer element */
58
59/** (circular) Queue data structure */
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
123typedef 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 */
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
common defines and data types used in all packages of SCIP
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
BMS_BLKMEM * blkmem
Definition: struct_misc.h:181
SCIP_Bool * vals
Definition: struct_misc.h:182
SCIP_BTNODE * parent
Definition: struct_misc.h:240
void * dataptr
Definition: struct_misc.h:243
SCIP_BTNODE * left
Definition: struct_misc.h:241
SCIP_BTNODE * right
Definition: struct_misc.h:242
SCIP_BTNODE * root
Definition: struct_misc.h:249
BMS_BLKMEM * blkmem
Definition: struct_misc.h:250
SCIP_Bool articulationscheck
Definition: struct_misc.h:234
int ** successors
Definition: struct_misc.h:222
void ** nodedata
Definition: struct_misc.h:224
int * successorssize
Definition: struct_misc.h:225
void *** arcdata
Definition: struct_misc.h:223
int componentstartsize
Definition: struct_misc.h:231
int * articulations
Definition: struct_misc.h:229
int * componentstarts
Definition: struct_misc.h:228
int narticulations
Definition: struct_misc.h:233
BMS_BLKMEM * blkmem
Definition: struct_misc.h:221
int * components
Definition: struct_misc.h:227
int * nsuccessors
Definition: struct_misc.h:226
SCIP_HASHMAPIMAGE image
Definition: struct_misc.h:133
uint32_t nelements
Definition: struct_misc.h:144
BMS_BLKMEM * blkmem
Definition: struct_misc.h:139
SCIP_HASHMAPTYPE hashmaptype
Definition: struct_misc.h:145
uint32_t mask
Definition: struct_misc.h:143
uint32_t shift
Definition: struct_misc.h:142
SCIP_HASHMAPENTRY * slots
Definition: struct_misc.h:140
uint32_t * hashes
Definition: struct_misc.h:141
uint32_t nelements
Definition: struct_misc.h:153
void ** slots
Definition: struct_misc.h:151
uint32_t shift
Definition: struct_misc.h:152
void * userptr
Definition: struct_misc.h:95
uint32_t nelements
Definition: struct_misc.h:100
SCIP_DECL_HASHKEYVAL((*hashkeyval))
SCIP_DECL_HASHKEYEQ((*hashkeyeq))
uint32_t shift
Definition: struct_misc.h:98
uint32_t mask
Definition: struct_misc.h:99
BMS_BLKMEM * blkmem
Definition: struct_misc.h:94
void ** slots
Definition: struct_misc.h:96
SCIP_DECL_HASHGETKEY((*hashgetkey))
uint32_t * hashes
Definition: struct_misc.h:97
BMS_BLKMEM * blkmem
Definition: struct_misc.h:170
SCIP_MULTIHASHLIST * next
Definition: struct_misc.h:107
SCIP_DECL_HASHKEYEQ((*hashkeyeq))
SCIP_MULTIHASHLIST ** lists
Definition: struct_misc.h:117
SCIP_DECL_HASHGETKEY((*hashgetkey))
BMS_BLKMEM * blkmem
Definition: struct_misc.h:116
SCIP_DECL_HASHKEYVAL((*hashkeyval))
SCIP_Longint nelements
Definition: struct_misc.h:120
SCIP_DECL_SORTPTRCOMP((*ptrcomp))
void ** slots
Definition: struct_misc.h:83
SCIP_Real sizefac
Definition: struct_misc.h:80
SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos))
int * timepoints
Definition: struct_misc.h:211
void ** vals
Definition: struct_misc.h:193
BMS_BLKMEM * blkmem
Definition: struct_misc.h:192
SCIP_Real sizefac
Definition: struct_misc.h:62
int firstused
Definition: struct_misc.h:65
SCIP_QUEUEELEMENT * slots
Definition: struct_misc.h:63
int firstfree
Definition: struct_misc.h:64
uint32_t xor_seed
Definition: struct_misc.h:271
uint32_t cst_seed
Definition: struct_misc.h:273
uint32_t mwc_seed
Definition: struct_misc.h:272
SCIP_Real * vals
Definition: struct_misc.h:160
BMS_BLKMEM * blkmem
Definition: struct_misc.h:159
SCIP_Real slope
Definition: struct_misc.h:257
SCIP_Real meany
Definition: struct_misc.h:259
SCIP_Real meanx
Definition: struct_misc.h:258
SCIP_Real variancesumx
Definition: struct_misc.h:261
SCIP_Real corrcoef
Definition: struct_misc.h:263
SCIP_Real sumxy
Definition: struct_misc.h:260
SCIP_Real intercept
Definition: struct_misc.h:256
SCIP_Real variancesumy
Definition: struct_misc.h:262
SCIP_Real side
Definition: struct_misc.h:292
SCIP_Bool modifiedside
Definition: struct_misc.h:301
SCIP_VAR ** modifiedvars
Definition: struct_misc.h:298
SCIP_VAR ** vars
Definition: struct_misc.h:288
char name[SCIP_MAXSTRLEN]
Definition: struct_misc.h:295
SCIP_Real * coefs
Definition: struct_misc.h:289
SCIP_Bool local
Definition: struct_misc.h:294
SCIP_Bool recordmodifications
Definition: struct_misc.h:297
int modifiedvarssize
Definition: struct_misc.h:300
SCIP_SIDETYPE sidetype
Definition: struct_misc.h:293
SCIP_Longint * lbvalues
Definition: struct_misc.h:49
SCIP_VAR ** vars
Definition: struct_misc.h:48
SCIP_Longint * ubvalues
Definition: struct_misc.h:50
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:67
type definitions for miscellaneous datastructures
enum SCIP_Hashmaptype SCIP_HASHMAPTYPE
Definition: type_misc.h:63
unsigned int uinteger
Definition: struct_misc.h:56