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"

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 55 of file scip_dcmp.c.

Referenced by SCIPcomputeDecompConsLabels().

Function Documentation

◆ countLabelFromPos()

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

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 59 of file scip_dcmp.c.

References NULL.

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

◆ ensureCondition()

static SCIP_RETCODE ensureCondition ( SCIP_Bool condition )

static

raises an error if the condition is not TRUE

Parameters

condition some condition that must hold

Definition at line 84 of file scip_dcmp.c.

References SCIP_ERROR, and SCIP_OKAY.

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

◆ getVarbufSize()

static int getVarbufSize ( SCIP * scip )

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 93 of file scip_dcmp.c.

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

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

◆ getDecompVarsConssData()

static 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

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 108 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 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

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 138 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 int findLabelIdx	(	SCIP_DECOMP *	decomp,
		int	label
	)

static

return position of a label in decomp array

Parameters

decomp	decomposition data structure
label	the label

Definition at line 681 of file scip_dcmp.c.

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

Referenced by buildBlockGraph(), and computeModularity().

◆ computeModularity()

static 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

scip	SCIP data structure
decomp	decomposition data structure
modularity	pointer to store modularity value

Definition at line 695 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 void computeAreaScore	(	SCIP *	scip,
		SCIP_DECOMP *	decomp
	)

static

compute the area score

Parameters

scip	SCIP data structure
decomp	decomposition data structure

Definition at line 813 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 SCIP_RETCODE buildBlockGraph	(	SCIP *	scip,
		SCIP_DECOMP *	decomp,
		int	maxgraphedge
	)

static

build the block decomposition graph

Parameters

scip	SCIP data structure
decomp	decomposition data structure
maxgraphedge	maximum number of edges in block graph computation (-1: no limit, 0: disable block graph computation)

Definition at line 846 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ LABEL_UNASSIGNED

Function Documentation

◆ countLabelFromPos()

◆ ensureCondition()

◆ getVarbufSize()

◆ getDecompVarsConssData()

◆ decompGetConsVarsAndLabels()

◆ findLabelIdx()

◆ computeModularity()

◆ computeAreaScore()

◆ buildBlockGraph()