methods for creating and accessing user decompositions
Files | |
file | pub_dcmp.h |
public methods for decompositions | |
file | scip_dcmp.h |
public methods for decompositions | |
SCIP_RETCODE SCIPdecompCreate | ( | SCIP_DECOMP ** | decomp, |
BMS_BLKMEM * | blkmem, | ||
int | nblocks, | ||
SCIP_Bool | original, | ||
SCIP_Bool | benderslabels ) |
creates a decomposition
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 56 of file dcmp.c.
References assert(), BMSallocBlockMemory, BMSallocBlockMemoryArray, FALSE, INIT_MAP_SIZE, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, and SCIPhashmapCreate().
Referenced by SCIP_DECL_HEUREXEC(), and SCIPcreateDecomp().
void SCIPdecompFree | ( | SCIP_DECOMP ** | decomp, |
BMS_BLKMEM * | blkmem ) |
frees a decomposition
free a decomposition
decomp | pointer to free the decomposition data structure |
blkmem | block memory |
Definition at line 98 of file dcmp.c.
References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArray, NULL, and SCIPhashmapFree().
Referenced by freeDecompositions(), SCIP_DECL_HEUREXEC(), and SCIPfreeDecomp().
SCIP_Bool SCIPdecompIsOriginal | ( | SCIP_DECOMP * | decomp | ) |
returns TRUE if decomposition is in the original space
decomp | decomposition data structure |
Definition at line 245 of file dcmp.c.
References assert(), NULL, and SCIP_Decomp::original.
Referenced by decompGetConsVarsAndLabels(), decompHorizonInitialize(), getDecompVarsConssData(), SCIP_DECL_HEUREXEC(), SCIPaddDecomp(), SCIPassignDecompLinkConss(), SCIPcomputeDecompVarsLabels(), SCIPdecompstoreAdd(), and SCIPhasConsOnlyLinkVars().
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
decomp | decomposition data structure |
benderslabels | whether Benders' variable labels should be used |
Definition at line 257 of file dcmp.c.
References assert(), SCIP_Decomp::benderslabels, and NULL.
SCIP_Bool SCIPdecompUseBendersLabels | ( | SCIP_DECOMP * | decomp | ) |
returns TRUE if the variables must be labeled for the application of Benders' decomposition
decomp | decomposition data structure |
Definition at line 268 of file dcmp.c.
References assert(), SCIP_Decomp::benderslabels, and NULL.
Referenced by SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIPcomputeDecompConsLabels(), SCIPcomputeDecompVarsLabels(), and SCIPtransformDecompstore().
int SCIPdecompGetNBlocks | ( | SCIP_DECOMP * | decomp | ) |
gets number of blocks of this decomposition
decomp | decomposition data structure |
Definition at line 278 of file dcmp.c.
References assert(), SCIP_Decomp::nblocks, and NULL.
Referenced by buildBlockGraph(), chooseDecomp(), decompHorizonCreate(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIPbendersApplyDecomposition(), SCIPtransformDecompstore(), and selectInitialVariableDecomposition().
SCIP_Real SCIPdecompGetAreaScore | ( | SCIP_DECOMP * | decomp | ) |
gets area score of this decomposition
decomp | decomposition data structure |
Definition at line 288 of file dcmp.c.
References SCIP_Decomp::areascore, assert(), and NULL.
SCIP_Real SCIPdecompGetModularity | ( | SCIP_DECOMP * | decomp | ) |
gets modularity of this decomposition
decomp | decomposition data structure |
Definition at line 298 of file dcmp.c.
References assert(), SCIP_Decomp::modularity, and NULL.
SCIP_RETCODE SCIPdecompGetVarsSize | ( | SCIP_DECOMP * | decomp, |
int * | varssize, | ||
int | nlabels ) |
gets variable size for each block, sorted by increasing block label
To get all variable sizes, set nlabels to SCIPdecompGetNBlocks() + 1. The first entry corresponds to the number of border variables.
decomp | decomposition data structure |
varssize | array to store variable sizes of blocks |
nlabels | length of variable sizes array |
Definition at line 315 of file dcmp.c.
References assert(), i, SCIP_Decomp::labels, SCIP_Decomp::nblocks, NULL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, and SCIP_Decomp::varssize.
Referenced by createAndSplitProblem().
SCIP_RETCODE SCIPdecompGetConssSize | ( | SCIP_DECOMP * | decomp, |
int * | consssize, | ||
int | nlabels ) |
gets constraint size for each block, sorted by increasing block label
To get all constraint sizes, set nlabels to SCIPdecompGetNBlocks() + 1. The first entry corresponds to the number of border constraints.
decomp | decomposition data structure |
consssize | array to store constraint sizes of blocks |
nlabels | length of constraint sizes array |
Definition at line 348 of file dcmp.c.
References assert(), SCIP_Decomp::consssize, i, SCIP_Decomp::labels, SCIP_Decomp::nblocks, NULL, SCIP_DECOMP_LINKVAR, and SCIP_OKAY.
Referenced by createAndSplitProblem(), and SCIP_DECL_HEUREXEC().
int SCIPdecompGetNBorderVars | ( | SCIP_DECOMP * | decomp | ) |
gets number of border variables of this decomposition
decomp | decomposition data structure |
Definition at line 378 of file dcmp.c.
References assert(), SCIP_Decomp::labels, NULL, SCIP_DECOMP_LINKVAR, and SCIP_Decomp::varssize.
Referenced by assignLinking(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEUREXEC().
int SCIPdecompGetNBorderConss | ( | SCIP_DECOMP * | decomp | ) |
gets number of border constraints of this decomposition
decomp | decomposition data structure |
Definition at line 393 of file dcmp.c.
References assert(), SCIP_Decomp::consssize, SCIP_Decomp::labels, NULL, and SCIP_DECOMP_LINKVAR.
Referenced by SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEUREXEC().
int SCIPdecompGetNBlockGraphEdges | ( | SCIP_DECOMP * | decomp | ) |
gets number of edges in the block-decomposition graph of this decomposition
decomp | decomposition data structure |
Definition at line 404 of file dcmp.c.
References assert(), SCIP_Decomp::nedges, and NULL.
int SCIPdecompGetNBlockGraphComponents | ( | SCIP_DECOMP * | decomp | ) |
gets number of connected components in the block-decomposition graph of this decomposition
decomp | decomposition data structure |
Definition at line 414 of file dcmp.c.
References assert(), SCIP_Decomp::ncomponents, and NULL.
int SCIPdecompGetNBlockGraphArticulations | ( | SCIP_DECOMP * | decomp | ) |
gets number of articulation points in the block-decomposition graph of this decomposition
decomp | decomposition data structure |
Definition at line 424 of file dcmp.c.
References assert(), SCIP_Decomp::narticulations, and NULL.
int SCIPdecompGetBlockGraphMaxDegree | ( | SCIP_DECOMP * | decomp | ) |
gets the maximum degree of the block-decomposition graph of this decomposition
decomp | decomposition data structure |
Definition at line 434 of file dcmp.c.
References assert(), SCIP_Decomp::maxdegree, and NULL.
int SCIPdecompGetBlockGraphMinDegree | ( | SCIP_DECOMP * | decomp | ) |
gets the minimum degree of the block-decomposition graph of this decomposition
decomp | decomposition data structure |
Definition at line 444 of file dcmp.c.
References assert(), SCIP_Decomp::mindegree, and NULL.
SCIP_RETCODE SCIPdecompSetVarsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_VAR ** | vars, | ||
int * | labels, | ||
int | nvars ) |
sets labels for an array of variables
decomp | decomposition data structure |
vars | array of variables |
labels | array of labels, one per variable |
nvars | length of variables array |
Definition at line 123 of file dcmp.c.
References assert(), i, NULL, nvars, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPhashmapSetImageInt(), SCIP_Decomp::var2block, and vars.
Referenced by assignLinking(), assignLinking(), SCIPassignDecompLinkConss(), SCIPcomputeDecompStats(), and SCIPtransformDecompstore().
void SCIPdecompGetVarsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_VAR ** | vars, | ||
int * | labels, | ||
int | nvars ) |
queries labels for an array of variables
decomp | decomposition data structure |
vars | array of variables |
labels | buffer to store labels, one per variable |
nvars | length of variables array |
Definition at line 148 of file dcmp.c.
References assert(), i, NULL, nvars, SCIP_DECOMP_LINKVAR, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIP_Decomp::var2block, and vars.
Referenced by assignLinking(), assignLinking(), buildBlockGraph(), decompGetConsVarsAndLabels(), decompHorizonInitialize(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIPassignDecompLinkConss(), SCIPbendersApplyDecomposition(), SCIPcomputeDecompStats(), SCIPhasConsOnlyLinkVars(), SCIPtransformDecompstore(), and selectInitialVariableDecomposition().
SCIP_RETCODE SCIPdecompSetConsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_CONS ** | conss, | ||
int * | labels, | ||
int | nconss ) |
sets labels for an array of constraints
decomp | decomposition data structure |
conss | array of constraints |
labels | array of labels, one per constraint |
nconss | length of constraints array |
Definition at line 172 of file dcmp.c.
References assert(), SCIP_Decomp::cons2block, i, NULL, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_OKAY, and SCIPhashmapSetImageInt().
Referenced by assignLinking(), assignLinking(), readDecomposition(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), and SCIPcomputeDecompStats().
void SCIPdecompGetConsLabels | ( | SCIP_DECOMP * | decomp, |
SCIP_CONS ** | conss, | ||
int * | labels, | ||
int | nconss ) |
queries labels for an array of constraints
decomp | decomposition data structure |
conss | array of constraints |
labels | array of labels, one per constraint |
nconss | length of constraints array |
Definition at line 197 of file dcmp.c.
References assert(), SCIP_Decomp::cons2block, i, NULL, SCIP_DECOMP_LINKCONS, SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by assignLinking(), assignLinking(), buildBlockGraph(), computeModularity(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), SCIPbendersApplyDecomposition(), SCIPcomputeDecompStats(), and SCIPcomputeDecompVarsLabels().
SCIP_RETCODE SCIPdecompClear | ( | SCIP_DECOMP * | decomp, |
SCIP_Bool | clearvarlabels, | ||
SCIP_Bool | clearconslabels ) |
clears the corresponding labeling (constraints, variables, or both) of this decomposition
decomp | decomposition data structure |
clearvarlabels | should the variable labels be cleared? |
clearconslabels | should the constraint labels be cleared? |
Definition at line 223 of file dcmp.c.
References assert(), SCIP_Decomp::cons2block, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPhashmapRemoveAll(), and SCIP_Decomp::var2block.
Referenced by SCIPtransformDecompstore().
char * SCIPdecompPrintStats | ( | SCIP_DECOMP * | decomp, |
char * | strbuf ) |
prints decomposition statistics into string buffer
decomp | decomposition data structure |
strbuf | string buffer storage |
Definition at line 454 of file dcmp.c.
References SCIP_Decomp::areascore, assert(), SCIP_Decomp::consssize, i, 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(), SCIP_DECL_HEUREXEC(), and SCIPtransformDecompstore().
SCIP_RETCODE SCIPcreateDecomp | ( | SCIP * | scip, |
SCIP_DECOMP ** | decomp, | ||
int | nblocks, | ||
SCIP_Bool | original, | ||
SCIP_Bool | benderslabels ) |
creates a decomposition
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 217 of file scip_dcmp.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), and SCIPdecompCreate().
Referenced by readDecomposition(), SCIP_DECL_HEUREXEC(), and SCIPtransformDecompstore().
void SCIPfreeDecomp | ( | SCIP * | scip, |
SCIP_DECOMP ** | decomp ) |
frees a decomposition
scip | SCIP data structure |
decomp | pointer to free the decomposition data structure |
Definition at line 233 of file scip_dcmp.c.
References assert(), NULL, SCIPblkmem(), and SCIPdecompFree().
Referenced by SCIP_DECL_HEUREXEC().
SCIP_RETCODE SCIPaddDecomp | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp ) |
adds decomposition to SCIP
scip | SCIP data structure |
decomp | decomposition to add |
Definition at line 244 of file scip_dcmp.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcheckStage(), SCIPdecompIsOriginal(), SCIPdecompstoreAdd(), and TRUE.
Referenced by readDecomposition().
void SCIPgetDecomps | ( | SCIP * | scip, |
SCIP_DECOMP *** | decomps, | ||
int * | ndecomps, | ||
SCIP_Bool | original ) |
gets available user decompositions for either the original or transformed problem
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 262 of file scip_dcmp.c.
References assert(), FALSE, NULL, SCIP_CALL_ABORT, SCIPcheckStage(), SCIPdecompstoreGetDecomps(), SCIPdecompstoreGetNDecomps(), SCIPdecompstoreGetNOrigDecomps(), SCIPdecompstoreGetOrigDecomps(), and TRUE.
Referenced by chooseDecomp(), SCIP_DECL_HEUREXEC(), and SCIP_DECL_HEUREXEC().
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
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 281 of file scip_dcmp.c.
References assert(), ensureCondition(), i, NULL, nvars, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetVarsLabels(), SCIPdecompIsOriginal(), SCIPfreeBufferArray, SCIPgetActiveVars(), SCIPgetConsNVars(), SCIPgetConsVars(), and TRUE.
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
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.
scip | SCIP data structure |
decomp | decomposition data structure |
conss | array of constraints |
nconss | number of constraints |
Definition at line 344 of file scip_dcmp.c.
References assert(), c, decompGetConsVarsAndLabels(), ensureCondition(), FALSE, getVarbufSize(), i, LABEL_UNASSIGNED, NULL, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_UNUSED, SCIPallocBufferArray, SCIPdecompSetConsLabels(), SCIPdecompUseBendersLabels(), SCIPerrorMessage, SCIPfreeBufferArray, and TRUE.
Referenced by assignLinking(), and SCIPtransformDecompstore().
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.
scip | SCIP data structure |
decomp | decomposition data structure |
conss | array of constraints |
nconss | number of constraints |
Definition at line 454 of file scip_dcmp.c.
References assert(), c, decompGetConsVarsAndLabels(), ensureCondition(), getVarbufSize(), i, NULL, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetConsLabels(), SCIPdecompIsOriginal(), SCIPdecompUseBendersLabels(), SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPhashmapSetImageInt(), SCIPvarGetNegatedVar(), SCIPvarIsActive(), SCIPvarIsNegated(), var, and SCIP_Decomp::var2block.
Referenced by assignLinking(), readDecomposition(), and SCIPtransformDecompstore().
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.
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 549 of file scip_dcmp.c.
References assert(), c, countLabelFromPos(), decompGetConsVarsAndLabels(), ensureCondition(), getVarbufSize(), i, NULL, nvars, SCIP_CALL, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdecompGetVarsLabels(), SCIPdecompIsOriginal(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetOrigVars(), SCIPgetVars(), SCIPsortIntPtr(), and vars.
Referenced by assignLinking().
SCIP_RETCODE SCIPcomputeDecompStats | ( | SCIP * | scip, |
SCIP_DECOMP * | decomp, | ||
SCIP_Bool | uselimits ) |
computes decomposition statistics and store them in the decomposition object
scip | SCIP data structure |
decomp | decomposition data structure |
uselimits | respect user limits on potentially expensive graph statistics? |
Definition at line 1135 of file scip_dcmp.c.
References assert(), buildBlockGraph(), c, computeAreaScore(), computeModularity(), SCIP_Decomp::consssize, countLabelFromPos(), FALSE, getDecompVarsConssData(), i, SCIP_Decomp::idxlargestblock, SCIP_Decomp::idxsmallestblock, SCIP_Decomp::labels, MAX, SCIP_Decomp::modularity, SCIP_Decomp::nblocks, NULL, nvars, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPdecompGetConsLabels(), SCIPdecompGetVarsLabels(), SCIPdecompSetConsLabels(), SCIPdecompSetVarsLabels(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetBoolParam(), SCIPgetIntParam(), SCIPsortIntPtr(), SCIP_Decomp::statscomplete, varidx, vars, and SCIP_Decomp::varssize.
Referenced by assignLinking(), assignLinking(), readDecomposition(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXEC(), and SCIPtransformDecompstore().