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 visit scipopt.org. */ 13 /* */ 14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 15 16 /**@file struct_implics.h 17 * @ingroup INTERNALAPI 18 * @brief datastructures for implications, variable bounds, and cliques 19 * @author Tobias Achterberg 20 */ 21 22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 23 24 #ifndef __SCIP_STRUCT_IMPLICS_H__ 25 #define __SCIP_STRUCT_IMPLICS_H__ 26 27 28 #include "scip/def.h" 29 #include "scip/type_implics.h" 30 #include "scip/type_lp.h" 31 #include "scip/type_misc.h" 32 #include "scip/type_var.h" 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 /** variable bounds of a variable x in the form x <= b*z + d or x >= b*z + d */ 39 struct SCIP_VBounds 40 { 41 SCIP_VAR** vars; /**< variables z in variable bounds x <= b*z + d or x >= b*z + d */ 42 SCIP_Real* coefs; /**< coefficients b in variable bounds x <= b*z + d or x >= b*z + d */ 43 SCIP_Real* constants; /**< constants d in variable bounds x <= b*z + d or x >= b*z + d */ 44 int len; /**< number of existing variable bounds (used slots in arrays) */ 45 int size; /**< size of vars, coefs, and constants arrays */ 46 }; 47 48 /** implications for binary variable x to non-binary variables y in the form 49 * x <= 0 ==> y <= b or y >= b (stored in arrays[0]) 50 * x >= 1 ==> y <= b or y >= b (stored in arrays[1]) 51 * array is sorted by variable index of y 52 */ 53 struct SCIP_Implics 54 { 55 SCIP_VAR** vars[2]; /**< variables y in implications y <= b or y >= b */ 56 SCIP_BOUNDTYPE* types[2]; /**< types of implications y <= b (SCIP_BOUNDTYPE_UPPER) 57 * or y >= b (SCIP_BOUNDTYPE_LOWER) */ 58 SCIP_Real* bounds[2]; /**< bounds b in implications y <= b or y >= b */ 59 int* ids[2]; /**< unique ids of implications; < 0 iff implication is a shortcut, 60 * i.e., it was added as part of the transitive closure of another implication */ 61 int size[2]; /**< size of implvars, implbounds and implvals arrays for x <= 0 and x >= 1*/ 62 int nimpls[2]; /**< number of all implications for x <= 0 and x >= 1 */ 63 }; 64 65 /** single clique, stating that at most one of the binary variables can be fixed to the corresponding value */ 66 struct SCIP_Clique 67 { 68 SCIP_VAR** vars; /**< variables in the clique */ 69 SCIP_Bool* values; /**< values of the variables in the clique */ 70 int nvars; /**< number of variables in the clique */ 71 int size; /**< size of vars and values arrays */ 72 int startcleanup; /**< clean up position to start with */ 73 int index; /**< the index of the clique in the cliquetable cliques array */ 74 unsigned int id:30; /**< unique identifier of clique */ 75 unsigned int eventsissued:1; /**< were the IMPLADDED events on the variables already issued? */ 76 unsigned int equation:1; /**< is the clique an equation or an inequality? */ 77 }; 78 79 /** list of cliques for a single variable */ 80 struct SCIP_CliqueList 81 { 82 SCIP_CLIQUE** cliques[2]; /**< cliques the variable fixed to FALSE/TRUE is member of */ 83 int ncliques[2]; /**< number of cliques the variable fixed to FALSE/TRUE is member of */ 84 int size[2]; /**< size of cliques arrays */ 85 }; 86 87 /** collection of cliques */ 88 struct SCIP_CliqueTable 89 { 90 SCIP_HASHTABLE* hashtable; /**< hash table holding all cliques */ 91 SCIP_HASHMAP* varidxtable; /**< mapping from binary variable to their corresponding node indices */ 92 SCIP_DISJOINTSET* djset; /**< disjoint set (union find) data structure to maintain component information */ 93 SCIP_CLIQUE** cliques; /**< cliques stored in the table */ 94 SCIP_Longint nentries; /**< number of entries in the whole clique table */ 95 int ncliques; /**< number of cliques stored in the table */ 96 int size; /**< size of cliques array */ 97 int ncreatedcliques; /**< number of ever created cliques */ 98 int ncleanupfixedvars; /**< number of fixed variables when the last cleanup was performed */ 99 int ncleanupaggrvars; /**< number of aggregated variables when the last cleanup was performed */ 100 int ndirtycliques; /**< number of cliques stored when the last cleanup was performed */ 101 int ncliquecomponents; /**< number of connected components in clique graph */ 102 SCIP_Bool incleanup; /**< is this clique table currently performing cleanup? */ 103 SCIP_Bool compsfromscratch; /**< must the connected components of the clique graph be recomputed from scratch? */ 104 }; 105 106 #ifdef __cplusplus 107 } 108 #endif 109 110 #endif 111