SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

methods for working with decompositions

Author
Gregor Hendel

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"
#include "scip/pub_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 56 of file scip_dcmp.c.

Referenced by SCIPcomputeDecompConsLabels().

Function Documentation

◆ countLabelFromPos()

int countLabelFromPos ( int * labels,
int pos,
int nlabels )
static

count occurrences of label in array, starting from pos

Parameters
labelsarray of labels
posposition to start counting from
nlabelsthe number of labels

Definition at line 60 of file scip_dcmp.c.

References assert(), and NULL.

Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), and SCIPcomputeDecompStats().

◆ ensureCondition()

SCIP_RETCODE ensureCondition ( SCIP_Bool condition)
static

raises an error if the condition is not TRUE

Parameters
conditionsome condition that must hold

Definition at line 85 of file scip_dcmp.c.

References SCIP_Bool, SCIP_ERROR, and SCIP_OKAY.

Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), SCIPcomputeDecompVarsLabels(), and SCIPhasConsOnlyLinkVars().

◆ getVarbufSize()

int getVarbufSize ( SCIP * scip)
static

get variable buffer storage size for the buffer to be large enough to hold all variables

Parameters
scipSCIP data structure

Definition at line 94 of file scip_dcmp.c.

References MAX, SCIPgetNOrigVars(), and SCIPgetNVars().

Referenced by buildBlockGraph(), computeModularity(), SCIPassignDecompLinkConss(), SCIPcomputeDecompConsLabels(), and SCIPcomputeDecompVarsLabels().

◆ getDecompVarsConssData()

void getDecompVarsConssData ( SCIP * scip,
SCIP_DECOMP * decomp,
SCIP_VAR *** vars,
SCIP_CONS *** conss,
int * nvars,
int * nconss )
static

get variables and constraints of the original or transformed problem, to which the decomposition corresponds

Parameters
scipSCIP data structure
decompdecomposition data structure
varspointer to store original/transformed variables array, or NULL
consspointer to store original/transformed constraints array, or NULL
nvarspointer to store original/transformed variables array's length, or NULL
nconsspointer to store original/transformed constraints array's length, or NULL

Definition at line 109 of file scip_dcmp.c.

References assert(), NULL, nvars, SCIP_Bool, SCIPdecompIsOriginal(), SCIPgetConss(), SCIPgetNConss(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetNVars(), SCIPgetOrigConss(), SCIPgetOrigVars(), SCIPgetVars(), and vars.

Referenced by buildBlockGraph(), computeAreaScore(), computeModularity(), and SCIPcomputeDecompStats().

◆ decompGetConsVarsAndLabels()

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 )
static

query the constraints active variables and their labels

Parameters
scipSCIP data structure
decompdecomposition data structure
consthe constraint
varbufvariable buffer array
labelbufbuffer to store labels, or NULL if not needed
bufsizesize of buffer arrays
nvarspointer to store number of variables
requiredsizepointer to store required size
successpointer to store whether variables and labels were successfully inserted

Definition at line 139 of file scip_dcmp.c.

References assert(), FALSE, NULL, nvars, 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()

int findLabelIdx ( SCIP_DECOMP * decomp,
int label )
static

return position of a label in decomp array

Parameters
decompdecomposition data structure
labelthe label

Definition at line 683 of file scip_dcmp.c.

References SCIP_Decomp::labels, SCIP_Decomp::nblocks, and SCIPsortedvecFindInt().

Referenced by buildBlockGraph(), and computeModularity().

◆ computeModularity()

SCIP_RETCODE computeModularity ( SCIP * scip,
SCIP_DECOMP * decomp,
SCIP_Real * modularity )
static

compute decomposition modularity (comparison of within block edges against a random decomposition)

Parameters
scipSCIP data structure
decompdecomposition data structure
modularitypointer to store modularity value

Definition at line 697 of file scip_dcmp.c.

References assert(), b, c, 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, SCIPsortInt(), and SQR.

Referenced by SCIPcomputeDecompStats().

◆ computeAreaScore()

void computeAreaScore ( SCIP * scip,
SCIP_DECOMP * decomp )
static

compute the area score

Parameters
scipSCIP data structure
decompdecomposition data structure

Definition at line 815 of file scip_dcmp.c.

References SCIP_Decomp::areascore, SCIP_Decomp::consssize, getDecompVarsConssData(), i, SCIP_Decomp::nblocks, NULL, nvars, SCIP_Real, and SCIP_Decomp::varssize.

Referenced by SCIPcomputeDecompStats().

◆ buildBlockGraph()