Scippy

SCIP

Solving Constraint Integer Programs

scip_dcmp.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-2022 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 scip_dcmp.h
17  * @ingroup DecompMethods
18  * @brief public methods for decompositions
19  * @author Gregor Hendel
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef SCIP_SCIP_DECOMP_H_
25 #define SCIP_SCIP_DECOMP_H_
26 
27 #include "scip/def.h"
28 #include "scip/type_cons.h"
29 #include "scip/type_dcmp.h"
30 #include "scip/type_retcode.h"
31 #include "scip/type_scip.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 /**@addtogroup DecompMethods
38  *
39  * @{
40  */
41 
42 /** creates a decomposition */
43 SCIP_EXPORT
45  SCIP* scip, /**< SCIP data structure */
46  SCIP_DECOMP** decomp, /**< pointer to store the decomposition data structure */
47  int nblocks, /**< the number of blocks (without the linking block) */
48  SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */
49  SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */
50  );
51 
52 /** frees a decomposition */
53 SCIP_EXPORT
54 void SCIPfreeDecomp(
55  SCIP* scip, /**< SCIP data structure */
56  SCIP_DECOMP** decomp /**< pointer to free the decomposition data structure */
57  );
58 
59 /** adds decomposition to SCIP */
60 SCIP_EXPORT
62  SCIP* scip, /**< SCIP data structure */
63  SCIP_DECOMP* decomp /**< decomposition to add */
64  );
65 
66 /** gets available user decompositions for either the original or transformed problem */
67 SCIP_EXPORT
68 void SCIPgetDecomps(
69  SCIP* scip, /**< SCIP data structure */
70  SCIP_DECOMP*** decomps, /**< pointer to store decompositions array */
71  int* ndecomps, /**< pointer to store number of decompositions */
72  SCIP_Bool original /**< should the decompositions for the original problem be returned? */
73  );
74 
75 /** returns TRUE if the constraint \p cons contains only linking variables in decomposition \p decomp */
76 SCIP_EXPORT
78  SCIP* scip, /**< SCIP data structure */
79  SCIP_DECOMP* decomp, /**< decomposition data structure */
80  SCIP_CONS* cons, /**< the constraint */
81  SCIP_Bool* hasonlylinkvars /**< will be set to TRUE if this constraint has only linking variables */
82  );
83 
84 /** computes constraint labels from variable labels
85  *
86  * Existing labels for the constraints are simply overridden
87  *
88  * The computed labels depend on the flag SCIPdecompUseBendersLabels() of the decomposition. If the flag is set
89  * to FALSE, the labeling assigns
90  *
91  * - label i, if only variables labeled i are present in the constraint (and optionally linking variables)
92  * - SCIP_DECOMP_LINKCONS, if there are either only variables labeled with SCIP_DECOMP_LINKVAR present, or
93  * if there are variables with more than one block label.
94  *
95  * If the flag is set to TRUE, the assignment is the same, unless variables from 2 named blocks occur in the same
96  * constraint, which is an invalid labeling for the Benders case.
97  */
98 SCIP_EXPORT
100  SCIP* scip, /**< SCIP data structure */
101  SCIP_DECOMP* decomp, /**< decomposition data structure */
102  SCIP_CONS** conss, /**< array of constraints */
103  int nconss /**< number of constraints */
104  );
105 
106 /** creates a decomposition of the variables from a labeling of the constraints
107  *
108  * NOTE: by default, the variable labeling is based on a Dantzig-Wolfe decomposition. This means that constraints in named
109  * blocks have have precedence over linking constraints. If a variable exists in constraints from
110  * two or more named blocks, then this variable is marked as a linking variable.
111  * If a variable occurs in exactly one named block i>=0, it is assigned label i.
112  * Variables which are only in linking constraints are unlabeled. However, SCIPdecompGetVarsLabels() will
113  * label them as linking variables.
114  *
115  * If the variables should be labeled for the application of Benders' decomposition, the decomposition must be
116  * flagged explicitly via SCIPdecompSetUseBendersLabels().
117  * With this setting, the presence in linking constraints takes precedence over the presence in named blocks.
118  * Now, a variable is considered linking if it is present in at least one linking constraint and an arbitrary
119  * number of constraints from named blocks.
120  */
121 SCIP_EXPORT
123  SCIP* scip, /**< SCIP data structure */
124  SCIP_DECOMP* decomp, /**< decomposition data structure */
125  SCIP_CONS** conss, /**< array of constraints */
126  int nconss /**< number of constraints */
127  );
128 
129 /** assigns linking constraints to blocks
130  *
131  * Each linking constraint is assigned to the most frequent block among its variables.
132  * Variables of other blocks are relabeled as linking variables.
133  * Constraints that have only linking variables are skipped.
134  *
135  * @note: In contrast to SCIPcomputeDecompConsLabels(), this method potentially relabels variables.
136  */
137 SCIP_EXPORT
139  SCIP* scip, /**< SCIP data structure */
140  SCIP_DECOMP* decomp, /**< decomposition data structure */
141  SCIP_CONS** conss, /**< array of linking constraints that should be reassigned */
142  int nconss, /**< number of constraints */
143  int* nskipconss /**< pointer to store the number of constraints that were skipped, or NULL */
144  );
145 
146 /** computes decomposition statistics and store them in the decomposition object */
147 SCIP_EXPORT
149  SCIP* scip, /**< SCIP data structure */
150  SCIP_DECOMP* decomp, /**< decomposition data structure */
151  SCIP_Bool uselimits /**< respect user limits on potentially expensive graph statistics? */
152  );
153 
154 /** @} */
155 
156 #ifdef __cplusplus
157 }
158 #endif
159 
160 #endif
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:444
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:539
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1125
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:335
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
Definition: scip_dcmp.c:224
type definitions for return codes for SCIP methods
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:253
type definitions for SCIP&#39;s main datastructure
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
Definition: scip_dcmp.c:272
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:208
type definitions for decompositions and the decomposition store
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:235
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers