Scippy

SCIP

Solving Constraint Integer Programs

struct_dcmp.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-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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_dcmp.h
17  * @ingroup INTERNALAPI
18  * @brief data structures for a decomposition and a decomposition store
19  * @author Gregor Hendel
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef SRC_SCIP_STRUCT_DECOMP_H_
25 #define SRC_SCIP_STRUCT_DECOMP_H_
26 
27 #include "scip/type_misc.h"
28 #include "scip/type_dcmp.h"
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 /** decomposition data structure */
36 {
37  SCIP_HASHMAP* var2block; /**< hash map from SCIP variables to block labels */
38  SCIP_HASHMAP* cons2block; /**< hash map from SCIP constraints to block labels */
39  SCIP_Real modularity; /**< modularity score (comparison of within block edges against a random decomposition) */
40  SCIP_Real areascore; /**< area score (fraction of matrix area outside block assignments) of this decomposition */
41  int idxlargestblock; /**< index of the of the largest block (regarding the number of constraints) */
42  int idxsmallestblock; /**< index of the smallest block (regarding the number of constraints) */
43  int* varssize; /**< variable size for each block, sorted by increasing block label */
44  int* consssize; /**< constraint size for each block, sorted by increasing block label */
45  int* labels; /**< integer label for each block */
46  int nblocks; /**< the number of variable blocks without the linking block */
47  int memsize; /**< memory size for block-related arrays, initially equal to nblocks + 1 */
48  int nedges; /**< the number of edges in the block decomposition graph */
49  int mindegree; /**< the minimum degree of the block decomposition graph */
50  int maxdegree; /**< the maximum degree of the block decomposition graph */
51  int ncomponents; /**< the number of connected components in the block decomposition graph */
52  int narticulations; /**< the number of articulation nodes in the block decomposition graph */
53  SCIP_Bool original; /**< is this a decomposition in the original (TRUE) or transformed space? */
54  SCIP_Bool benderslabels; /**< should the variables be labeled for the application of Benders' decomposition */
55  SCIP_Bool statscomplete; /**< are the block decomposition graph statistics completely computed? */
56 };
57 
58 /** data structure to manage decompositions */
60 {
61  SCIP_DECOMP** decomps; /**< array of decompositions in this store */
62  SCIP_DECOMP** origdecomps; /**< array of decompositions in original space */
63  int ndecomps; /**< number of available decompositions */
64  int norigdecomps; /**< number of decompositions in original space */
65  int decompssize; /**< size of the decomposition arrays */
66 };
67 
68 #ifdef __cplusplus
69 }
70 #endif
71 
72 #endif
type definitions for miscellaneous datastructures
SCIP_Real areascore
Definition: struct_dcmp.h:40
SCIP_DECOMP ** origdecomps
Definition: struct_dcmp.h:62
SCIP_Bool original
Definition: struct_dcmp.h:53
SCIP_Real modularity
Definition: struct_dcmp.h:39
int * consssize
Definition: struct_dcmp.h:44
int ncomponents
Definition: struct_dcmp.h:51
int * varssize
Definition: struct_dcmp.h:43
int idxlargestblock
Definition: struct_dcmp.h:41
SCIP_HASHMAP * cons2block
Definition: struct_dcmp.h:38
#define SCIP_Bool
Definition: def.h:70
int idxsmallestblock
Definition: struct_dcmp.h:42
int * labels
Definition: struct_dcmp.h:45
SCIP_Bool benderslabels
Definition: struct_dcmp.h:54
#define SCIP_Real
Definition: def.h:163
type definitions for decompositions and the decomposition store
SCIP_DECOMP ** decomps
Definition: struct_dcmp.h:61
SCIP_Bool statscomplete
Definition: struct_dcmp.h:55
int narticulations
Definition: struct_dcmp.h:52
SCIP_HASHMAP * var2block
Definition: struct_dcmp.h:37