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