Scippy

SCIP

Solving Constraint Integer Programs

struct_implics.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_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 */
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  */
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 */
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 */
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 */
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
SCIP_CLIQUE ** cliques
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
SCIP_HASHMAP * varidxtable
type definitions for miscellaneous datastructures
type definitions for implications, variable bounds, and cliques
SCIP_HASHTABLE * hashtable
SCIP_Real * constants
unsigned int eventsissued
SCIP_Real * coefs
type definitions for LP management
SCIP_Bool compsfromscratch
type definitions for problem variables
SCIP_VAR ** vars
unsigned int equation
SCIP_Bool * values
#define SCIP_Bool
Definition: def.h:91
SCIP_VAR ** vars
SCIP_DISJOINTSET * djset
unsigned int id
#define SCIP_Real
Definition: def.h:173
#define SCIP_Longint
Definition: def.h:158
common defines and data types used in all packages of SCIP
SCIP_Longint nentries