Detailed Description
methods for working with decompositions
Definition in file scip_dcmp.c.
#include <assert.h>
#include "scip/struct_dcmp.h"
#include "scip/debug.h"
#include "scip/dcmp.h"
#include "scip/mem.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_prob.h"
#include "scip/scip_var.h"
#include "scip/scip_mem.h"
#include "scip/struct_scip.h"
#include "scip/pub_cons.h"
#include "scip/pub_dcmp.h"
#include "scip/scip_dcmp.h"
#include "scip/scip_general.h"
#include "scip/scip_param.h"
#include "scip/scip_datastructures.h"
#include "scip/scip_message.h"
Go to the source code of this file.
Macros | |
#define | LABEL_UNASSIGNED INT_MIN /* label constraints or variables as unassigned. Only for internal use */ |
Functions | |
static int | countLabelFromPos (int *labels, int pos, int nlabels) |
static SCIP_RETCODE | ensureCondition (SCIP_Bool condition) |
static int | getVarbufSize (SCIP *scip) |
static void | getDecompVarsConssData (SCIP *scip, SCIP_DECOMP *decomp, SCIP_VAR ***vars, SCIP_CONS ***conss, int *nvars, int *nconss) |
static SCIP_RETCODE | decompGetConsVarsAndLabels (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_VAR **varbuf, int *labelbuf, int bufsize, int *nvars, int *requiredsize, SCIP_Bool *success) |
SCIP_RETCODE | SCIPcreateDecomp (SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels) |
void | SCIPfreeDecomp (SCIP *scip, SCIP_DECOMP **decomp) |
SCIP_RETCODE | SCIPaddDecomp (SCIP *scip, SCIP_DECOMP *decomp) |
void | SCIPgetDecomps (SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original) |
SCIP_RETCODE | SCIPhasConsOnlyLinkVars (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars) |
SCIP_RETCODE | SCIPcomputeDecompConsLabels (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss) |
SCIP_RETCODE | SCIPcomputeDecompVarsLabels (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss) |
SCIP_RETCODE | SCIPassignDecompLinkConss (SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss) |
static int | findLabelIdx (SCIP_DECOMP *decomp, int label) |
static SCIP_RETCODE | computeModularity (SCIP *scip, SCIP_DECOMP *decomp, SCIP_Real *modularity) |
static void | computeAreaScore (SCIP *scip, SCIP_DECOMP *decomp) |
static SCIP_RETCODE | buildBlockGraph (SCIP *scip, SCIP_DECOMP *decomp, int maxgraphedge) |
SCIP_RETCODE | SCIPcomputeDecompStats (SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits) |
Macro Definition Documentation
◆ LABEL_UNASSIGNED
#define LABEL_UNASSIGNED INT_MIN /* label constraints or variables as unassigned. Only for internal use */ |
Definition at line 46 of file scip_dcmp.c.
Referenced by SCIPcomputeDecompConsLabels().
Function Documentation
◆ countLabelFromPos()
|
static |
count occurrences of label in array, starting from pos
- Parameters
-
labels array of labels pos position to start counting from nlabels the number of labels
Definition at line 50 of file scip_dcmp.c.
References NULL.
Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), and SCIPcomputeDecompStats().
◆ ensureCondition()
|
static |
raises an error if the condition is not TRUE
- Parameters
-
condition some condition that must hold
Definition at line 75 of file scip_dcmp.c.
References SCIP_ERROR, and SCIP_OKAY.
Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), SCIPcomputeDecompVarsLabels(), and SCIPhasConsOnlyLinkVars().
◆ getVarbufSize()
|
static |
get variable buffer storage size for the buffer to be large enough to hold all variables
- Parameters
-
scip SCIP data structure
Definition at line 84 of file scip_dcmp.c.
References MAX, SCIPgetNOrigVars(), and SCIPgetNVars().
Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), and SCIPcomputeDecompVarsLabels().
◆ getDecompVarsConssData()
|
static |
get variables and constraints of the original or transformed problem, to which the decomposition corresponds
- Parameters
-
scip SCIP data structure decomp decomposition data structure vars pointer to store original/transformed variables array, or NULL conss pointer to store original/transformed constraints array, or NULL nvars pointer to store original/transformed variables array's length, or NULL nconss pointer to store original/transformed constraints array's length, or NULL
Definition at line 99 of file scip_dcmp.c.
References NULL, SCIP_Bool, SCIPdecompIsOriginal(), SCIPgetConss(), SCIPgetNConss(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetNVars(), SCIPgetOrigConss(), SCIPgetOrigVars(), and SCIPgetVars().
Referenced by buildBlockGraph(), computeAreaScore(), computeModularity(), and SCIPcomputeDecompStats().
◆ decompGetConsVarsAndLabels()
|
static |
query the constraints active variables and their labels
- Parameters
-
scip SCIP data structure decomp decomposition data structure cons the constraint varbuf variable buffer array labelbuf buffer to store labels, or NULL if not needed bufsize size of buffer arrays nvars pointer to store number of variables requiredsize pointer to store required size success pointer to store whether variables and labels were successfully inserted
Definition at line 129 of file scip_dcmp.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdecompGetVarsLabels(), SCIPdecompIsOriginal(), SCIPgetActiveVars(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPvarGetNegatedVar(), SCIPvarIsActive(), SCIPvarIsNegated(), and TRUE.
Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), and SCIPcomputeDecompVarsLabels().
◆ findLabelIdx()
|
static |
return position of a label in decomp array
- Parameters
-
decomp decomposition data structure label the label
Definition at line 672 of file scip_dcmp.c.
References SCIP_Decomp::labels, SCIP_Decomp::nblocks, and SCIPsortedvecFindInt().
Referenced by buildBlockGraph(), and computeModularity().
◆ computeModularity()
|
static |
compute decomposition modularity (comparison of within block edges against a random decomposition)
- Parameters
-
scip SCIP data structure decomp decomposition data structure modularity pointer to store modularity value
Definition at line 686 of file scip_dcmp.c.
References b, countLabelFromPos(), decompGetConsVarsAndLabels(), ensureCondition(), findLabelIdx(), getDecompVarsConssData(), getVarbufSize(), MAX, SCIP_Decomp::nblocks, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPdecompGetConsLabels(), SCIPfreeBufferArray, and SCIPsortInt().
Referenced by SCIPcomputeDecompStats().
◆ computeAreaScore()
|
static |
compute the area score
- Parameters
-
scip SCIP data structure decomp decomposition data structure
Definition at line 804 of file scip_dcmp.c.
References SCIP_Decomp::areascore, SCIP_Decomp::consssize, getDecompVarsConssData(), SCIP_Decomp::nblocks, NULL, SCIP_Real, and SCIP_Decomp::varssize.
Referenced by SCIPcomputeDecompStats().
◆ buildBlockGraph()
|
static |
build the block decomposition graph
- Parameters
-
scip SCIP data structure decomp decomposition data structure maxgraphedge maximum number of edges in block graph computation, or -1 for no limit
Definition at line 837 of file scip_dcmp.c.
References countLabelFromPos(), decompGetConsVarsAndLabels(), ensureCondition(), FALSE, findLabelIdx(), getDecompVarsConssData(), getVarbufSize(), SCIP_Decomp::maxdegree, SCIP_Decomp::mindegree, SCIP_Decomp::narticulations, SCIP_Decomp::nblocks, SCIP_Decomp::ncomponents, SCIP_Decomp::nedges, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECOMP_LINKCONS, SCIP_DECOMP_LINKVAR, SCIP_OKAY, SCIPABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcreateDigraph(), SCIPdecompGetConsLabels(), SCIPdecompGetNBlocks(), SCIPdecompGetVarsLabels(), SCIPdigraphAddArc(), SCIPdigraphComputeUndirectedComponents(), SCIPdigraphFree(), SCIPdigraphGetArticulationPoints(), SCIPdigraphGetNComponents(), SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPsortedvecFindInt(), SCIPsortIntPtr(), SCIPvarGetProbindex(), SCIP_Decomp::statscomplete, TRUE, and SCIP_Decomp::varssize.
Referenced by SCIPcomputeDecompStats().