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
presol_gateextraction.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 presol_gateextraction.h
17
* @ingroup PRESOLVERS
18
* @brief gateextraction presolver
19
* @author Michael Winkler
20
*/
21
22
/* This presolver tries to extract gate-constraints meaning and-constraints and set-partitioning constraints (and could
23
* be expanded to find xor-constraints too). This is done by detecting linearizations or systems of inequalities which
24
* form an and-constraint or a set-partitioning constraint. An example:
25
*
26
* we have a logicor constraint of the form: x + y + z >= 1
27
*
28
* and we also have the following set-packing constraints: (x + y <= 1 and x + z <= 1) <=> (~x + ~y >= 1 and ~x + ~z >= 1)
29
*
30
* - these three constraints form an and-constraint: x = ~y * ~z (x = AND(~y,~z))
31
*
32
* if an additional set-packing constraint exists: y + z <= 1
33
*
34
* - these four constraints form a set-partitioning cons.: x + y + z = 1
35
*
36
* some information can be found:
37
*
38
* http://www.cs.ubc.ca/~hutter/earg/papers07/cnf-structure.pdf
39
* http://www.cadence.com/cn/cadence/cadence_labs/Documents/niklas_SAT_2005_Effective.pdf
40
*
41
* We also do some check for logicor and set-packing/-partitioning constraint with the same variables to upgrade these
42
* both constraints into one. For example:
43
*
44
* x + y + z >= 1 and x + y + z <= 1 form x + y + z = 1
45
*
46
*/
47
48
49
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
50
51
#ifndef __SCIP_PRESOL_GATEEXTRACTION_H__
52
#define __SCIP_PRESOL_GATEEXTRACTION_H__
53
54
55
#include "
scip/scip.h
"
56
57
#ifdef __cplusplus
58
extern
"C"
{
59
#endif
60
61
/** creates the gateextraction presolver and includes it in SCIP
62
*
63
* @ingroup PresolverIncludes
64
*/
65
extern
66
SCIP_RETCODE
SCIPincludePresolGateextraction
(
67
SCIP
*
scip
/**< SCIP data structure */
68
);
69
70
#ifdef __cplusplus
71
}
72
#endif
73
74
#endif
Scip
Definition:
struct_scip.h:58
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
SCIPincludePresolGateextraction
SCIP_RETCODE SCIPincludePresolGateextraction(SCIP *scip)
Definition:
presol_gateextraction.c:1767
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.