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-2015 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 extern
64  SCIP* scip /**< SCIP data structure */
65  );
66 
67 #ifdef __cplusplus
68 }
69 #endif
70 
71 #endif
SCIP_RETCODE SCIPincludePresolGateextraction(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct Scip SCIP
Definition: type_scip.h:30
SCIP callable library.