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-2017 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 email to scip@zib.de. */
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_lp.h"
30 #include "scip/type_var.h"
31 #include "scip/type_implics.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 /** variable bounds of a variable x in the form x <= b*z + d or x >= b*z + d */
39 {
40  SCIP_VAR** vars; /**< variables z in variable bounds x <= b*z + d or x >= b*z + d */
41  SCIP_Real* coefs; /**< coefficients b in variable bounds x <= b*z + d or x >= b*z + d */
42  SCIP_Real* constants; /**< constants d in variable bounds x <= b*z + d or x >= b*z + d */
43  int len; /**< number of existing variable bounds (used slots in arrays) */
44  int size; /**< size of vars, coefs, and constants arrays */
45 };
46 
47 /** implications for binary variable x to non-binary variables y in the form
48  * x <= 0 ==> y <= b or y >= b (stored in arrays[0])
49  * x >= 1 ==> y <= b or y >= b (stored in arrays[1])
50  * array is sorted by variable index of y
51  */
53 {
54  SCIP_VAR** vars[2]; /**< variables y in implications y <= b or y >= b */
55  SCIP_BOUNDTYPE* types[2]; /**< types of implications y <= b (SCIP_BOUNDTYPE_UPPER)
56  * or y >= b (SCIP_BOUNDTYPE_LOWER) */
57  SCIP_Real* bounds[2]; /**< bounds b in implications y <= b or y >= b */
58  int* ids[2]; /**< unique ids of implications; < 0 iff implication is a shortcut,
59  * i.e., it was added as part of the transitive closure of another implication */
60  int size[2]; /**< size of implvars, implbounds and implvals arrays for x <= 0 and x >= 1*/
61  int nimpls[2]; /**< number of all implications for x <= 0 and x >= 1 */
62 };
63 
64 /** single clique, stating that at most one of the binary variables can be fixed to the corresponding value */
66 {
67  SCIP_VAR** vars; /**< variables in the clique */
68  SCIP_Bool* values; /**< values of the variables in the clique */
69  int nvars; /**< number of variables in the clique */
70  int size; /**< size of vars and values arrays */
71  int startcleanup; /**< clean up position to start with */
72  int index; /**< the index of the clique in the cliquetable cliques array */
73  unsigned int id:30; /**< unique identifier of clique */
74  unsigned int eventsissued:1; /**< were the IMPLADDED events on the variables already issued? */
75  unsigned int equation:1; /**< is the clique an equation or an inequality? */
76 };
77 
78 /** list of cliques for a single variable */
80 {
81  SCIP_CLIQUE** cliques[2]; /**< cliques the variable fixed to FALSE/TRUE is member of */
82  int ncliques[2]; /**< number of cliques the variable fixed to FALSE/TRUE is member of */
83  int size[2]; /**< size of cliques arrays */
84 };
85 
86 /** collection of cliques */
88 {
89  SCIP_HASHTABLE* hashtable; /**< hash table holding all cliques */
90  SCIP_CLIQUE** cliques; /**< cliques stored in the table */
91  SCIP_Longint nentries; /**< number of entries in the whole clique table */
92  int ncliques; /**< number of cliques stored in the table */
93  int size; /**< size of cliques array */
94  int ncreatedcliques; /**< number of ever created cliques */
95  int ncleanupfixedvars; /**< number of fixed variables when the last cleanup was performed */
96  int ncleanupaggrvars; /**< number of aggregated variables when the last cleanup was performed */
97  int ndirtycliques; /**< number of cliques stored when the last cleanup was performed */
98  int ncliquecomponents; /**< number of connected components in clique graph */
99  SCIP_Bool incleanup; /**< is this clique table currently performing cleanup? */
100  SCIP_Bool componentupdate; /**< must the connected components of the clique graph be updated? */
101 };
102 
103 #ifdef __cplusplus
104 }
105 #endif
106 
107 #endif
SCIP_Bool componentupdate
SCIP_CLIQUE ** cliques
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
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 incleanup
type definitions for problem variables
SCIP_VAR ** vars
unsigned int equation
SCIP_Bool * values
#define SCIP_Bool
Definition: def.h:61
SCIP_VAR ** vars
unsigned int id
#define SCIP_Real
Definition: def.h:135
#define SCIP_Longint
Definition: def.h:120
common defines and data types used in all packages of SCIP
SCIP_Longint nentries