Scippy

SCIP

Solving Constraint Integer Programs

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 46 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
labelsarray of labels
posposition to start counting from
nlabelsthe number of labels

Definition at line 50 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
conditionsome 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 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 84 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
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 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 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 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 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 672 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
scipSCIP data structure
decompdecomposition data structure
modularitypointer 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 void computeAreaScore ( SCIP scip,
SCIP_DECOMP decomp 
)
static

compute the area score

Parameters
scipSCIP data structure
decompdecomposition 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()