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-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 */
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  */
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 */
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 */
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 */
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
SCIP_CLIQUE ** cliques
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
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:70
SCIP_VAR ** vars
SCIP_DISJOINTSET * djset
unsigned int id
#define SCIP_Real
Definition: def.h:163
#define SCIP_Longint
Definition: def.h:148
common defines and data types used in all packages of SCIP
SCIP_Longint nentries