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