Scippy

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-2020 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 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 #include "scip/def.h"
55 #include "scip/type_retcode.h"
56 #include "scip/type_scip.h"
57 
58 #ifdef __cplusplus
59 extern "C" {
60 #endif
61 
62 /** creates the gateextraction presolver and includes it in SCIP
63  *
64  * @ingroup PresolverIncludes
65  */
68  SCIP* scip /**< SCIP data structure */
69  );
70 
71 #ifdef __cplusplus
72 }
73 #endif
74 
75 #endif
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_RETCODE SCIPincludePresolGateextraction(SCIP *scip)
common defines and data types used in all packages of SCIP