Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SCIP 9.2.0
SCIP 8.1.0
SCIP 7.0.3
SCIP 6.0.2
SCIP 5.0.1
SCIP 4.0.1
SCIP 3.2.1
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 */
38
struct
SCIP_VBounds
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
*/
52
struct
SCIP_Implics
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 */
65
struct
SCIP_Clique
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 */
79
struct
SCIP_CliqueList
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 */
87
struct
SCIP_CliqueTable
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_CliqueTable::componentupdate
SCIP_Bool componentupdate
Definition:
struct_implics.h:100
SCIP_CliqueTable::cliques
SCIP_CLIQUE ** cliques
Definition:
struct_implics.h:90
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition:
type_lp.h:50
SCIP_VBounds
Definition:
struct_implics.h:38
SCIP_CliqueTable::ncliquecomponents
int ncliquecomponents
Definition:
struct_implics.h:98
type_implics.h
type definitions for implications, variable bounds, and cliques
SCIP_CliqueTable::hashtable
SCIP_HASHTABLE * hashtable
Definition:
struct_implics.h:89
SCIP_VBounds::constants
SCIP_Real * constants
Definition:
struct_implics.h:42
SCIP_Var
Definition:
struct_var.h:197
SCIP_Clique::eventsissued
unsigned int eventsissued
Definition:
struct_implics.h:74
SCIP_CliqueTable::ncleanupaggrvars
int ncleanupaggrvars
Definition:
struct_implics.h:96
SCIP_CliqueTable::size
int size
Definition:
struct_implics.h:93
SCIP_VBounds::coefs
SCIP_Real * coefs
Definition:
struct_implics.h:41
type_lp.h
type definitions for LP management
SCIP_VBounds::size
int size
Definition:
struct_implics.h:44
SCIP_CliqueTable::incleanup
SCIP_Bool incleanup
Definition:
struct_implics.h:99
type_var.h
type definitions for problem variables
SCIP_VBounds::vars
SCIP_VAR ** vars
Definition:
struct_implics.h:40
SCIP_Clique::equation
unsigned int equation
Definition:
struct_implics.h:75
SCIP_CliqueList
Definition:
struct_implics.h:79
SCIP_Clique::values
SCIP_Bool * values
Definition:
struct_implics.h:68
SCIP_Bool
#define SCIP_Bool
Definition:
def.h:61
SCIP_Clique::size
int size
Definition:
struct_implics.h:70
SCIP_CliqueTable::ncleanupfixedvars
int ncleanupfixedvars
Definition:
struct_implics.h:95
SCIP_CliqueTable::ncreatedcliques
int ncreatedcliques
Definition:
struct_implics.h:94
SCIP_Clique::vars
SCIP_VAR ** vars
Definition:
struct_implics.h:67
SCIP_HashTable
Definition:
struct_misc.h:74
SCIP_Clique::nvars
int nvars
Definition:
struct_implics.h:69
SCIP_Clique::id
unsigned int id
Definition:
struct_implics.h:73
SCIP_CliqueTable
Definition:
struct_implics.h:87
SCIP_Clique::index
int index
Definition:
struct_implics.h:72
SCIP_CliqueTable::ndirtycliques
int ndirtycliques
Definition:
struct_implics.h:97
SCIP_Real
#define SCIP_Real
Definition:
def.h:135
SCIP_Clique::startcleanup
int startcleanup
Definition:
struct_implics.h:71
SCIP_Clique
Definition:
struct_implics.h:65
SCIP_Longint
#define SCIP_Longint
Definition:
def.h:120
SCIP_VBounds::len
int len
Definition:
struct_implics.h:43
def.h
common defines and data types used in all packages of SCIP
SCIP_Implics
Definition:
struct_implics.h:52
SCIP_CliqueTable::ncliques
int ncliques
Definition:
struct_implics.h:92
SCIP_CliqueTable::nentries
SCIP_Longint nentries
Definition:
struct_implics.h:91