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   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  */
66 SCIP_EXPORT
67 SCIP_RETCODE SCIPincludePresolGateextraction(
68    SCIP*                 scip                /**< SCIP data structure */
69    );
70 
71 #ifdef __cplusplus
72 }
73 #endif
74 
75 #endif
76