Scippy

SCIP

Solving Constraint Integer Programs

Decomposition data structure

Detailed Description

methods for creating and accessing user decompositions

Functions

SCIP_EXPORT SCIP_RETCODE SCIPdecompCreate (SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
 
SCIP_EXPORT void SCIPdecompFree (SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
 
SCIP_EXPORT SCIP_Bool SCIPdecompIsOriginal (SCIP_DECOMP *decomp)
 
SCIP_EXPORT void SCIPdecompSetUseBendersLabels (SCIP_DECOMP *decomp, SCIP_Bool benderslabels)
 
SCIP_EXPORT SCIP_Bool SCIPdecompUseBendersLabels (SCIP_DECOMP *decomp)
 
SCIP_EXPORT int SCIPdecompGetNBlocks (SCIP_DECOMP *decomp)
 
SCIP_EXPORT SCIP_Real SCIPdecompGetAreaScore (SCIP_DECOMP *decomp)
 
SCIP_EXPORT SCIP_Real SCIPdecompGetModularity (SCIP_DECOMP *decomp)
 
SCIP_EXPORT int SCIPdecompGetNBlockGraphEdges (SCIP_DECOMP *decomp)
 
SCIP_EXPORT int SCIPdecompGetNBlockGraphComponents (SCIP_DECOMP *decomp)
 
SCIP_EXPORT int SCIPdecompGetNBlockGraphArticulations (SCIP_DECOMP *decomp)
 
SCIP_EXPORT int SCIPdecompGetBlockGraphMaxDegree (SCIP_DECOMP *decomp)
 
SCIP_EXPORT int SCIPdecompGetBlockGraphMinDegree (SCIP_DECOMP *decomp)
 
SCIP_EXPORT SCIP_RETCODE SCIPdecompSetVarsLabels (SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
 
SCIP_EXPORT void SCIPdecompGetVarsLabels (SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
 
SCIP_EXPORT SCIP_RETCODE SCIPdecompSetConsLabels (SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
 
SCIP_EXPORT void SCIPdecompGetConsLabels (SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
 
SCIP_EXPORT SCIP_RETCODE SCIPdecompClear (SCIP_DECOMP *decomp, SCIP_Bool clearvarlabels, SCIP_Bool clearconslabels)
 
SCIP_EXPORT char * SCIPdecompPrintStats (SCIP_DECOMP *decomp, char *strbuf)
 
SCIP_EXPORT SCIP_RETCODE SCIPcreateDecomp (SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
 
SCIP_EXPORT void SCIPfreeDecomp (SCIP *scip, SCIP_DECOMP **decomp)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddDecomp (SCIP *scip, SCIP_DECOMP *decomp)
 
SCIP_EXPORT void SCIPgetDecomps (SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
 
SCIP_EXPORT SCIP_RETCODE SCIPhasConsOnlyLinkVars (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
 
SCIP_EXPORT SCIP_RETCODE SCIPcomputeDecompConsLabels (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
 
SCIP_EXPORT SCIP_RETCODE SCIPcomputeDecompVarsLabels (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
 
SCIP_EXPORT SCIP_RETCODE SCIPassignDecompLinkConss (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
 
SCIP_EXPORT SCIP_RETCODE SCIPcomputeDecompStats (SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
 

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
decomppointer to store the decomposition data structure
blkmemblock memory
nblocksthe number of blocks (without the linking block)
originalis this a decomposition in the original (TRUE) or transformed space?
benderslabelsshould 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
decomppointer to free the decomposition data structure
blkmemblock 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
decompdecomposition 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
decompdecomposition data structure
benderslabelswhether 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition 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
decompdecomposition data structure
varsarray of variables
labelsarray of labels, one per variable
nvarslength 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
decompdecomposition data structure
varsarray of variables
labelsbuffer to store labels, one per variable
nvarslength 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
decompdecomposition data structure
conssarray of constraints
labelsarray of labels, one per constraint
nconsslength 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
decompdecomposition data structure
conssarray of constraints
labelsarray of labels, one per constraint
nconsslength 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
decompdecomposition data structure
clearvarlabelsshould the variable labels be cleared?
clearconslabelsshould 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()

◆ SCIPcreateDecomp()

SCIP_EXPORT SCIP_RETCODE SCIPcreateDecomp ( SCIP scip,
SCIP_DECOMP **  decomp,
int  nblocks,
SCIP_Bool  original,
SCIP_Bool  benderslabels 
)

creates a decomposition

Parameters
scipSCIP data structure
decomppointer to store the decomposition data structure
nblocksthe number of blocks (without the linking block)
originalis this a decomposition in the original (TRUE) or transformed space?
benderslabelsshould 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
scipSCIP data structure
decomppointer 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
scipSCIP data structure
decompdecomposition 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
scipSCIP data structure
decompspointer to store decompositions array
ndecompspointer to store number of decompositions
originalshould 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
scipSCIP data structure
decompdecomposition data structure
consthe constraint
hasonlylinkvarswill 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
scipSCIP data structure
decompdecomposition data structure
conssarray of constraints
nconssnumber 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
scipSCIP data structure
decompdecomposition data structure
conssarray of constraints
nconssnumber 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
scipSCIP data structure
decompdecomposition data structure
conssarray of linking constraints that should be reassigned
nconssnumber of constraints
nskipconsspointer 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()