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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file scip_dcmp.h
26  * @ingroup DecompMethods
27  * @brief public methods for decompositions
28  * @author Gregor Hendel
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef SCIP_SCIP_DECOMP_H_
34 #define SCIP_SCIP_DECOMP_H_
35 
36 #include "scip/def.h"
37 #include "scip/type_cons.h"
38 #include "scip/type_dcmp.h"
39 #include "scip/type_retcode.h"
40 #include "scip/type_scip.h"
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 
46 /**@addtogroup DecompMethods
47  *
48  * @{
49  */
50 
51 /** creates a decomposition */
52 SCIP_EXPORT
54  SCIP* scip, /**< SCIP data structure */
55  SCIP_DECOMP** decomp, /**< pointer to store the decomposition data structure */
56  int nblocks, /**< the number of blocks (without the linking block) */
57  SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */
58  SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */
59  );
60 
61 /** frees a decomposition */
62 SCIP_EXPORT
63 void SCIPfreeDecomp(
64  SCIP* scip, /**< SCIP data structure */
65  SCIP_DECOMP** decomp /**< pointer to free the decomposition data structure */
66  );
67 
68 /** adds decomposition to SCIP */
69 SCIP_EXPORT
71  SCIP* scip, /**< SCIP data structure */
72  SCIP_DECOMP* decomp /**< decomposition to add */
73  );
74 
75 /** gets available user decompositions for either the original or transformed problem */
76 SCIP_EXPORT
77 void SCIPgetDecomps(
78  SCIP* scip, /**< SCIP data structure */
79  SCIP_DECOMP*** decomps, /**< pointer to store decompositions array */
80  int* ndecomps, /**< pointer to store number of decompositions */
81  SCIP_Bool original /**< should the decompositions for the original problem be returned? */
82  );
83 
84 /** returns TRUE if the constraint \p cons contains only linking variables in decomposition \p decomp */
85 SCIP_EXPORT
87  SCIP* scip, /**< SCIP data structure */
88  SCIP_DECOMP* decomp, /**< decomposition data structure */
89  SCIP_CONS* cons, /**< the constraint */
90  SCIP_Bool* hasonlylinkvars /**< will be set to TRUE if this constraint has only linking variables */
91  );
92 
93 /** computes constraint labels from variable labels
94  *
95  * Existing labels for the constraints are simply overridden
96  *
97  * The computed labels depend on the flag SCIPdecompUseBendersLabels() of the decomposition. If the flag is set
98  * to FALSE, the labeling assigns
99  *
100  * - label i, if only variables labeled i are present in the constraint (and optionally linking variables)
101  * - SCIP_DECOMP_LINKCONS, if there are either only variables labeled with SCIP_DECOMP_LINKVAR present, or
102  * if there are variables with more than one block label.
103  *
104  * If the flag is set to TRUE, the assignment is the same, unless variables from 2 named blocks occur in the same
105  * constraint, which is an invalid labeling for the Benders case.
106  */
107 SCIP_EXPORT
109  SCIP* scip, /**< SCIP data structure */
110  SCIP_DECOMP* decomp, /**< decomposition data structure */
111  SCIP_CONS** conss, /**< array of constraints */
112  int nconss /**< number of constraints */
113  );
114 
115 /** creates a decomposition of the variables from a labeling of the constraints
116  *
117  * NOTE: by default, the variable labeling is based on a Dantzig-Wolfe decomposition. This means that constraints in named
118  * blocks have have precedence over linking constraints. If a variable exists in constraints from
119  * two or more named blocks, then this variable is marked as a linking variable.
120  * If a variable occurs in exactly one named block i>=0, it is assigned label i.
121  * Variables which are only in linking constraints are unlabeled. However, SCIPdecompGetVarsLabels() will
122  * label them as linking variables.
123  *
124  * If the variables should be labeled for the application of Benders' decomposition, the decomposition must be
125  * flagged explicitly via SCIPdecompSetUseBendersLabels().
126  * With this setting, the presence in linking constraints takes precedence over the presence in named blocks.
127  * Now, a variable is considered linking if it is present in at least one linking constraint and an arbitrary
128  * number of constraints from named blocks.
129  */
130 SCIP_EXPORT
132  SCIP* scip, /**< SCIP data structure */
133  SCIP_DECOMP* decomp, /**< decomposition data structure */
134  SCIP_CONS** conss, /**< array of constraints */
135  int nconss /**< number of constraints */
136  );
137 
138 /** assigns linking constraints to blocks
139  *
140  * Each linking constraint is assigned to the most frequent block among its variables.
141  * Variables of other blocks are relabeled as linking variables.
142  * Constraints that have only linking variables are skipped.
143  *
144  * @note: In contrast to SCIPcomputeDecompConsLabels(), this method potentially relabels variables.
145  */
146 SCIP_EXPORT
148  SCIP* scip, /**< SCIP data structure */
149  SCIP_DECOMP* decomp, /**< decomposition data structure */
150  SCIP_CONS** conss, /**< array of linking constraints that should be reassigned */
151  int nconss, /**< number of constraints */
152  int* nskipconss /**< pointer to store the number of constraints that were skipped, or NULL */
153  );
154 
155 /** computes decomposition statistics and store them in the decomposition object */
156 SCIP_EXPORT
158  SCIP* scip, /**< SCIP data structure */
159  SCIP_DECOMP* decomp, /**< decomposition data structure */
160  SCIP_Bool uselimits /**< respect user limits on potentially expensive graph statistics? */
161  );
162 
163 /** @} */
164 
165 #ifdef __cplusplus
166 }
167 #endif
168 
169 #endif
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:453
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:548
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1134
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:344
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
Definition: scip_dcmp.c:233
type definitions for return codes for SCIP methods
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:262
type definitions for SCIP&#39;s main datastructure
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
Definition: scip_dcmp.c:281
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:217
type definitions for decompositions and the decomposition store
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:244
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers