Scippy

SCIP

Solving Constraint Integer Programs

presolve.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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presolve.h
17  * @ingroup PUBLICCOREAPI
18  * @brief methods commonly used for presolving
19  * @author Michael Winkler
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_PRESOLVE_H__
25 #define __SCIP_PRESOLVE_H__
26 
27 #include "scip/def.h"
28 #include "scip/type_retcode.h"
29 #include "scip/type_scip.h"
30 #include "scip/type_var.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 /**@defgroup PublicSpecialPresolveMethods Special Methods
37  * @ingroup PublicPresolverMethods
38  * @brief methods commonly used for presolving
39  *
40  * @{
41  */
42 /** try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one
43  * must be fulfilled
44  *
45  * e.g. a set of logicor or bounddisjunctive constraint variables would be such a set
46  *
47  * consider the following set:
48  *
49  * x1 >= 1, x2 >= 3, x3 >= 1, x4 <= 0
50  *
51  * by (global) implication data (cliques, implications, and variable bounds) we have also the following implications
52  * given:
53  *
54  * x1 >= 1 => x3 >= 1
55  * x2 >= 2 => x3 >= 1
56  * x4 <= 0 => x1 >= 1
57  *
58  * Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we
59  * can reduce the set by x4.
60  * Also, the both other implications and x3 >= 1 (in the given variable set) all imply exactly x3 >= 1, so we tighten
61  * the global lower bound of x3 to 1 and the set of variables gets redundant.
62  */
65  SCIP* scip, /**< SCIP data structure */
66  SCIP_VAR** vars, /**< variables array for which at least one must be fulfilled in the
67  * following bounds and boundtypes */
68  SCIP_Real* bounds, /**< bounds array for which at least one must be fulfilled */
69  SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE == SCIP_BOUNDTYPE_LOWER)
70  * for which at least one must be fulfilled */
71  SCIP_Bool* redundants, /**< array which be filled and then indicate if a variable in the set is redundant */
72  int nvars, /**< number of variables */
73  int* nredvars, /**< pointer to store how many variables can be removed */
74  int* nglobalred, /**< pointer to store number of global reductions on variable bounds found
75  * through this set of variables */
76  SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which was part
77  * of the given set of variables, this makes this disjunction redundant */
78  SCIP_Bool* glbinfeas, /**< pointer to store if global infeasibility was detected */
79  SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which might be expensive) */
80  );
81 
82 /* @} */
83 
84 #ifdef __cplusplus
85 }
86 #endif
87 
88 #endif
SCIP_EXPORT SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
Definition: presolve.c:975
#define SCIP_EXPORT
Definition: def.h:98
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:70
#define SCIP_Real
Definition: def.h:164
common defines and data types used in all packages of SCIP