Detailed Description
methods for creating and accessing user decompositions
Files | |
file | pub_dcmp.h |
public methods for decompositions | |
file | scip_dcmp.h |
public methods for decompositions | |
Function Documentation
◆ SCIPdecompCreate()
SCIP_EXPORT SCIP_RETCODE SCIPdecompCreate | ( | SCIP_DECOMP ** | decomp, |
BMS_BLKMEM * | blkmem, | ||
int | nblocks, | ||
SCIP_Bool | original, | ||
SCIP_Bool | benderslabels | ||
) |
creates a decomposition
- Parameters
-
decomp pointer to store the decomposition data structure blkmem block memory nblocks the number of blocks (without the linking block) original is this a decomposition in the original (TRUE) or transformed space? benderslabels should the variables be labeled for the application of Benders' decomposition
Definition at line 47 of file dcmp.c.
References BMSallocBlockMemory, BMSallocBlockMemoryArray, FALSE, INIT_MAP_SIZE, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, and SCIPhashmapCreate().
Referenced by SCIPcreateDecomp().
◆ SCIPdecompFree()
SCIP_EXPORT void SCIPdecompFree | ( | SCIP_DECOMP ** | decomp, |
BMS_BLKMEM * | blkmem | ||
) |
frees a decomposition
free a decomposition
- Parameters
-
decomp pointer to free the decomposition data structure blkmem block memory
Definition at line 89 of file dcmp.c.
References BMSfreeBlockMemory, BMSfreeBlockMemoryArray, NULL, and SCIPhashmapFree().
Referenced by freeDecompositions(), and SCIPfreeDecomp().
◆ SCIPdecompIsOriginal()
SCIP_EXPORT SCIP_Bool SCIPdecompIsOriginal | ( | SCIP_DECOMP * | decomp | ) |
returns TRUE if decomposition is in the original space
- Parameters
-
decomp decomposition data structure
Definition at line 236 of file dcmp.c.
References NULL, and SCIP_Decomp::original.
Referenced by decompGetConsVarsAndLabels(), decompHorizonInitialize(), getDecompVarsConssData(), SCIPaddDecomp(), SCIPcomputeDecompVarsLabels(), SCIPdecompstoreAdd(), and SCIPhasConsOnlyLinkVars().
◆ SCIPdecompSetUseBendersLabels()
SCIP_EXPORT void SCIPdecompSetUseBendersLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_Bool | benderslabels | ||
) |
sets the parameter that indicates whether the variables must be labeled for the application of Benders' decomposition
- Parameters
-
decomp decomposition data structure benderslabels whether Benders' variable labels should be used
Definition at line 248 of file dcmp.c.
References SCIP_Decomp::benderslabels, and NULL.
◆ SCIPdecompUseBendersLabels()
SCIP_EXPORT SCIP_Bool SCIPdecompUseBendersLabels | ( | SCIP_DECOMP * | decomp | ) |
returns TRUE if the variables must be labeled for the application of Benders' decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 259 of file dcmp.c.
References SCIP_Decomp::benderslabels, and NULL.
Referenced by SCIP_DECL_HEUREXEC(), SCIPcomputeDecompConsLabels(), SCIPcomputeDecompVarsLabels(), and SCIPtransformDecompstore().
◆ SCIPdecompGetNBlocks()
SCIP_EXPORT int SCIPdecompGetNBlocks | ( | SCIP_DECOMP * | decomp | ) |
gets number of blocks of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 269 of file dcmp.c.
References SCIP_Decomp::nblocks, and NULL.
Referenced by buildBlockGraph(), decompHorizonCreate(), SCIP_DECL_HEUREXEC(), SCIPbendersApplyDecomposition(), SCIPtransformDecompstore(), and selectInitialVariableDecomposition().
◆ SCIPdecompGetAreaScore()
SCIP_EXPORT SCIP_Real SCIPdecompGetAreaScore | ( | SCIP_DECOMP * | decomp | ) |
gets area score of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 279 of file dcmp.c.
References SCIP_Decomp::areascore, and NULL.
◆ SCIPdecompGetModularity()
SCIP_EXPORT SCIP_Real SCIPdecompGetModularity | ( | SCIP_DECOMP * | decomp | ) |
gets modularity of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 289 of file dcmp.c.
References SCIP_Decomp::modularity, and NULL.
◆ SCIPdecompGetNBlockGraphEdges()
SCIP_EXPORT int SCIPdecompGetNBlockGraphEdges | ( | SCIP_DECOMP * | decomp | ) |
gets number of edges in the block-decomposition graph of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 299 of file dcmp.c.
References SCIP_Decomp::nedges, and NULL.
◆ SCIPdecompGetNBlockGraphComponents()
SCIP_EXPORT int SCIPdecompGetNBlockGraphComponents | ( | SCIP_DECOMP * | decomp | ) |
gets number of connected components in the block-decomposition graph of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 309 of file dcmp.c.
References SCIP_Decomp::ncomponents, and NULL.
◆ SCIPdecompGetNBlockGraphArticulations()
SCIP_EXPORT int SCIPdecompGetNBlockGraphArticulations | ( | SCIP_DECOMP * | decomp | ) |
gets number of articulation points in the block-decomposition graph of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 319 of file dcmp.c.
References SCIP_Decomp::narticulations, and NULL.
◆ SCIPdecompGetBlockGraphMaxDegree()
SCIP_EXPORT int SCIPdecompGetBlockGraphMaxDegree | ( | SCIP_DECOMP * | decomp | ) |
gets the maximum degree of the block-decomposition graph of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 329 of file dcmp.c.
References SCIP_Decomp::maxdegree, and NULL.
◆ SCIPdecompGetBlockGraphMinDegree()
SCIP_EXPORT int SCIPdecompGetBlockGraphMinDegree | ( | SCIP_DECOMP * | decomp | ) |
gets the minimum degree of the block-decomposition graph of this decomposition
- Parameters
-
decomp decomposition data structure
Definition at line 339 of file dcmp.c.
References SCIP_Decomp::mindegree, and NULL.
◆ SCIPdecompSetVarsLabels()
SCIP_EXPORT SCIP_RETCODE SCIPdecompSetVarsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_VAR ** | vars, | ||
int * | labels, | ||
int | nvars | ||
) |
sets labels for an array of variables
- Parameters
-
decomp decomposition data structure vars array of variables labels array of labels, one per variable nvars length of variables array
Definition at line 114 of file dcmp.c.
References NULL, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPhashmapSetImageInt(), and SCIP_Decomp::var2block.
Referenced by assignLinking(), SCIPassignDecompLinkConss(), SCIPcomputeDecompStats(), and SCIPtransformDecompstore().
◆ SCIPdecompGetVarsLabels()
SCIP_EXPORT void SCIPdecompGetVarsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_VAR ** | vars, | ||
int * | labels, | ||
int | nvars | ||
) |
queries labels for an array of variables
- Parameters
-
decomp decomposition data structure vars array of variables labels buffer to store labels, one per variable nvars length of variables array
Definition at line 139 of file dcmp.c.
References NULL, SCIP_DECOMP_LINKVAR, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIP_Decomp::var2block.
Referenced by assignLinking(), buildBlockGraph(), decompGetConsVarsAndLabels(), decompHorizonInitialize(), SCIP_DECL_HEUREXEC(), SCIPassignDecompLinkConss(), SCIPbendersApplyDecomposition(), SCIPcomputeDecompStats(), SCIPhasConsOnlyLinkVars(), SCIPtransformDecompstore(), and selectInitialVariableDecomposition().
◆ SCIPdecompSetConsLabels()
SCIP_EXPORT SCIP_RETCODE SCIPdecompSetConsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_CONS ** | conss, | ||
int * | labels, | ||
int | nconss | ||
) |
sets labels for an array of constraints
- Parameters
-
decomp decomposition data structure conss array of constraints labels array of labels, one per constraint nconss length of constraints array
Definition at line 163 of file dcmp.c.
References SCIP_Decomp::cons2block, NULL, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_OKAY, and SCIPhashmapSetImageInt().
Referenced by assignLinking(), readDecomposition(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), and SCIPcomputeDecompStats().
◆ SCIPdecompGetConsLabels()
SCIP_EXPORT void SCIPdecompGetConsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_CONS ** | conss, | ||
int * | labels, | ||
int | nconss | ||
) |
queries labels for an array of constraints
- Parameters
-
decomp decomposition data structure conss array of constraints labels array of labels, one per constraint nconss length of constraints array
Definition at line 188 of file dcmp.c.
References SCIP_Decomp::cons2block, NULL, SCIP_DECOMP_LINKCONS, SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by assignLinking(), buildBlockGraph(), computeModularity(), SCIP_DECL_HEUREXEC(), SCIPbendersApplyDecomposition(), SCIPcomputeDecompStats(), and SCIPcomputeDecompVarsLabels().
◆ SCIPdecompClear()
SCIP_EXPORT SCIP_RETCODE SCIPdecompClear | ( | SCIP_DECOMP * | decomp, |
SCIP_Bool | clearvarlabels, | ||
SCIP_Bool | clearconslabels | ||
) |
clears the corresponding labeling (constraints, variables, or both) of this decomposition
- Parameters
-
decomp decomposition data structure clearvarlabels should the variable labels be cleared? clearconslabels should the constraint labels be cleared?
Definition at line 214 of file dcmp.c.
References SCIP_Decomp::cons2block, NULL, SCIP_CALL, SCIP_OKAY, SCIPhashmapRemoveAll(), and SCIP_Decomp::var2block.
Referenced by SCIPtransformDecompstore().
◆ SCIPdecompPrintStats()
SCIP_EXPORT char* SCIPdecompPrintStats | ( | SCIP_DECOMP * | decomp, |
char * | strbuf | ||
) |
prints decomposition statistics into string buffer
- Parameters
-
decomp decomposition data structure strbuf string buffer storage
Definition at line 349 of file dcmp.c.
References SCIP_Decomp::areascore, SCIP_Decomp::consssize, SCIP_Decomp::idxlargestblock, SCIP_Decomp::idxsmallestblock, SCIP_Decomp::labels, SCIP_Decomp::maxdegree, SCIP_Decomp::mindegree, SCIP_Decomp::modularity, SCIP_Decomp::narticulations, SCIP_Decomp::nblocks, SCIP_Decomp::ncomponents, SCIP_Decomp::nedges, NULL, SCIP_DECOMP_LINKVAR, SCIP_MAXSTRLEN, SCIPsnprintf(), SCIP_Decomp::statscomplete, and SCIP_Decomp::varssize.
Referenced by readDecomposition(), and SCIPtransformDecompstore().
◆ SCIPcreateDecomp()
SCIP_EXPORT SCIP_RETCODE SCIPcreateDecomp | ( | SCIP * | scip, |
SCIP_DECOMP ** | decomp, | ||
int | nblocks, | ||
SCIP_Bool | original, | ||
SCIP_Bool | benderslabels | ||
) |
creates a decomposition
- Parameters
-
scip SCIP data structure decomp pointer to store the decomposition data structure nblocks the number of blocks (without the linking block) original is this a decomposition in the original (TRUE) or transformed space? benderslabels should the variables be labeled for the application of Benders' decomposition
Definition at line 208 of file scip_dcmp.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), and SCIPdecompCreate().
Referenced by readDecomposition(), SCIP_DECL_HEUREXEC(), and SCIPtransformDecompstore().
◆ SCIPfreeDecomp()
SCIP_EXPORT void SCIPfreeDecomp | ( | SCIP * | scip, |
SCIP_DECOMP ** | decomp | ||
) |
frees a decomposition
- Parameters
-
scip SCIP data structure decomp pointer to free the decomposition data structure
Definition at line 224 of file scip_dcmp.c.
References NULL, SCIPblkmem(), and SCIPdecompFree().
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIPaddDecomp()
SCIP_EXPORT SCIP_RETCODE SCIPaddDecomp | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp | ||
) |
adds decomposition to SCIP
- Parameters
-
scip SCIP data structure decomp decomposition to add
Definition at line 235 of file scip_dcmp.c.
References Scip::decompstore, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcheckStage(), SCIPdecompIsOriginal(), SCIPdecompstoreAdd(), and TRUE.
Referenced by readDecomposition().
◆ SCIPgetDecomps()
SCIP_EXPORT void SCIPgetDecomps | ( | SCIP * | scip, |
SCIP_DECOMP *** | decomps, | ||
int * | ndecomps, | ||
SCIP_Bool | original | ||
) |
gets available user decompositions for either the original or transformed problem
- Parameters
-
scip SCIP data structure decomps pointer to store decompositions array ndecomps pointer to store number of decompositions original should the decompositions for the original problem be returned?
Definition at line 253 of file scip_dcmp.c.
References Scip::decompstore, FALSE, NULL, SCIP_CALL_ABORT, SCIPcheckStage(), SCIPdecompstoreGetDecomps(), SCIPdecompstoreGetNDecomps(), SCIPdecompstoreGetNOrigDecomps(), SCIPdecompstoreGetOrigDecomps(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIPhasConsOnlyLinkVars()
SCIP_EXPORT SCIP_RETCODE SCIPhasConsOnlyLinkVars | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp, | ||
SCIP_CONS * | cons, | ||
SCIP_Bool * | hasonlylinkvars | ||
) |
returns TRUE if the constraint cons
contains only linking variables in decomposition decomp
- Parameters
-
scip SCIP data structure decomp decomposition data structure cons the constraint hasonlylinkvars will be set to TRUE if this constraint has only linking variables
Definition at line 272 of file scip_dcmp.c.
References ensureCondition(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetVarsLabels(), SCIPdecompIsOriginal(), SCIPfreeBufferArray, SCIPgetActiveVars(), SCIPgetConsNVars(), SCIPgetConsVars(), and TRUE.
◆ SCIPcomputeDecompConsLabels()
SCIP_EXPORT SCIP_RETCODE SCIPcomputeDecompConsLabels | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp, | ||
SCIP_CONS ** | conss, | ||
int | nconss | ||
) |
computes constraint labels from variable labels
Existing labels for the constraints are simply overridden
The computed labels depend on the flag SCIPdecompUseBendersLabels() of the decomposition. If the flag is set to FALSE, the labeling assigns
- label i, if only variables labeled i are present in the constraint (and optionally linking variables)
- SCIP_DECOMP_LINKCONS, if there are either only variables labeled with SCIP_DECOMP_LINKVAR present, or if there are variables with more than one block label.
If the flag is set to TRUE, the assignment is the same, unless variables from 2 named blocks occur in the same constraint, which is an invalid labeling for the Benders case.
- Parameters
-
scip SCIP data structure decomp decomposition data structure conss array of constraints nconss number of constraints
Definition at line 335 of file scip_dcmp.c.
References decompGetConsVarsAndLabels(), ensureCondition(), FALSE, getVarbufSize(), LABEL_UNASSIGNED, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_INVALIDDATA, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompSetConsLabels(), SCIPdecompUseBendersLabels(), SCIPerrorMessage, SCIPfreeBufferArray, and TRUE.
Referenced by SCIPtransformDecompstore().
◆ SCIPcomputeDecompVarsLabels()
SCIP_EXPORT SCIP_RETCODE SCIPcomputeDecompVarsLabels | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp, | ||
SCIP_CONS ** | conss, | ||
int | nconss | ||
) |
creates a decomposition of the variables from a labeling of the constraints
NOTE: by default, the variable labeling is based on a Dantzig-Wolfe decomposition. This means that constraints in named blocks have have precedence over linking constraints. If a variable exists in constraints from two or more named blocks, then this variable is marked as a linking variable. If a variable occurs in exactly one named block i>=0, it is assigned label i. Variables which are only in linking constraints are unlabeled. However, SCIPdecompGetVarsLabels() will label them as linking variables.
If the variables should be labeled for the application of Benders' decomposition, the decomposition must be flagged explicitly via SCIPdecompSetUseBendersLabels(). With this setting, the presence in linking constraints takes precedence over the presence in named blocks. Now, a variable is considered linking if it is present in at least one linking constraint and an arbitrary number of constraints from named blocks.
- Parameters
-
scip SCIP data structure decomp decomposition data structure conss array of constraints nconss number of constraints
Definition at line 444 of file scip_dcmp.c.
References decompGetConsVarsAndLabels(), ensureCondition(), getVarbufSize(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetConsLabels(), SCIPdecompIsOriginal(), SCIPdecompUseBendersLabels(), SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhashmapSetImageInt(), SCIPvarGetNegatedVar(), SCIPvarIsActive(), SCIPvarIsNegated(), and SCIP_Decomp::var2block.
Referenced by assignLinking(), readDecomposition(), and SCIPtransformDecompstore().
◆ SCIPassignDecompLinkConss()
SCIP_EXPORT SCIP_RETCODE SCIPassignDecompLinkConss | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp, | ||
SCIP_CONS ** | conss, | ||
int | nconss, | ||
int * | nskipconss | ||
) |
assigns linking constraints to blocks
Each linking constraint is assigned to the most frequent block among its variables. Variables of other blocks are relabeled as linking variables. Constraints that have only linking variables are skipped.
- Note
- : In contrast to SCIPcomputeDecompConsLabels(), this method potentially relabels variables.
- Parameters
-
scip SCIP data structure decomp decomposition data structure conss array of linking constraints that should be reassigned nconss number of constraints nskipconss pointer to store the number of constraints that were skipped, or NULL
Definition at line 539 of file scip_dcmp.c.
References countLabelFromPos(), decompGetConsVarsAndLabels(), ensureCondition(), getVarbufSize(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetVarsLabels(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), and SCIPsortIntPtr().
Referenced by assignLinking().
◆ SCIPcomputeDecompStats()
SCIP_EXPORT SCIP_RETCODE SCIPcomputeDecompStats | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp, | ||
SCIP_Bool | uselimits | ||
) |
computes decomposition statistics and store them in the decomposition object
- Parameters
-
scip SCIP data structure decomp decomposition data structure uselimits respect user limits on potentially expensive graph statistics?
Definition at line 1125 of file scip_dcmp.c.
References buildBlockGraph(), computeAreaScore(), computeModularity(), SCIP_Decomp::consssize, countLabelFromPos(), FALSE, getDecompVarsConssData(), SCIP_Decomp::idxlargestblock, SCIP_Decomp::idxsmallestblock, SCIP_Decomp::labels, MAX, SCIP_Decomp::modularity, SCIP_Decomp::nblocks, NULL, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetVarsLabels(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetIntParam(), SCIPsortIntPtr(), SCIP_Decomp::statscomplete, and SCIP_Decomp::varssize.
Referenced by assignLinking(), readDecomposition(), and SCIPtransformDecompstore().