scip_dcmp.c
Go to the documentation of this file.
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
56#define LABEL_UNASSIGNED INT_MIN /* label constraints or variables as unassigned. Only for internal use */
107/** get variables and constraints of the original or transformed problem, to which the decomposition corresponds */
148 SCIP_Bool* success /**< pointer to store whether variables and labels were successfully inserted */
222 SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */
223 SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */
253 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDecomp", FALSE, SCIPdecompIsOriginal(decomp), SCIPdecompIsOriginal(decomp),
254 SCIPdecompIsOriginal(decomp), SCIPdecompIsOriginal(decomp), TRUE, TRUE, TRUE, !SCIPdecompIsOriginal(decomp),
272 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDecomps", FALSE, original, original, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
275 *decomps = original ? SCIPdecompstoreGetOrigDecomps(scip->decompstore) : SCIPdecompstoreGetDecomps(scip->decompstore);
278 *ndecomps = original ? SCIPdecompstoreGetNOrigDecomps(scip->decompstore) : SCIPdecompstoreGetNDecomps(scip->decompstore);
281/** returns TRUE if the constraint \p cons contains only linking variables in decomposition \p decomp */
286 SCIP_Bool* hasonlylinkvars /**< will be set to TRUE if this constraint has only linking variables */
335 * The computed labels depend on the flag SCIPdecompUseBendersLabels() of the decomposition. If the flag is set
338 * - label i, if only variables labeled i are present in the constraint (and optionally linking variables)
339 * - SCIP_DECOMP_LINKCONS, if there are either only variables labeled with SCIP_DECOMP_LINKVAR present, or
342 * If the flag is set to TRUE, the assignment is the same, unless variables from 2 named blocks occur in the same
395 /* count the number of linking variables, and keep track if there are two variables with different labels */
402 /* there must not be two variables from different named blocks in a single constraint, since the presence
429 /* throw an error and inform the user if the variable block decomposition does not allow a benders constraint labeling */
432 SCIPerrorMessage("Error in constraint label computation; variables from multiple named blocks in a single constraint\n");
442 * NOTE: by default, the variable labeling is based on a Dantzig-Wolfe decomposition. This means that constraints in named
443 * blocks have have precedence over linking constraints. If a variable exists in constraints from
446 * Variables which are only in linking constraints are unlabeled. However, SCIPdecompGetVarsLabels() will
449 * If the variables should be labeled for the application of Benders' decomposition, the decomposition must be
451 * With this setting, the presence in linking constraints takes precedence over the presence in named blocks.
452 * Now, a variable is considered linking if it is present in at least one linking constraint and an arbitrary
510 /* each variable in this constraint gets the constraint label unless it already has a different label -> make it a linking variable */
548 * @note: In contrast to SCIPcomputeDecompConsLabels(), this method potentially relabels variables.
665 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, &vars[startposs[p]], &varslabels[startposs[p]], endposs[p] - startposs[p]) );
695/** compute decomposition modularity (comparison of within block edges against a random decomposition) */
715 /* allocate buffer arrays to hold constraint and variable labels, and store within-edges and total community degrees */
745 /* find the position of the constraint label. Constraints of the border always belong to the first block at index 0 */
770 /* increase the total degrees and nonzero (edge) counts; it is intended that the total degrees sum up
840 areascore -= ((SCIP_Real)nlinkconss * nvars + (SCIP_Real)nconss * nlinkvars - (SCIP_Real)nlinkconss * nlinkvars) * factor;
851 int maxgraphedge /**< maximum number of edges in block graph computation (-1: no limit, 0: disable block graph computation) */
915 /* create a mapping of all linking variables to 0,..,nlinkingvars -1 and store it in array linkvaridx */
929 SCIP_CALL( SCIPcreateDigraph(scip, &blocklinkingvargraph, nblocks + nlinkingvars) );/* nblocks does not include the linking constraints block */
966 /* search for linking variables that are not connected so far; stop as soon as block vertex has max degree */
989 SCIP_CALL( SCIPdigraphAddArc(blocklinkingvargraph, blocknodeidx, nblocks + adjacentidxs[i], NULL) );
990 SCIP_CALL( SCIPdigraphAddArc(blocklinkingvargraph, nblocks + adjacentidxs[i], blocknodeidx, NULL) );
1012 /* check first if any of the linking variables is connected with all blocks -> block graph is complete and connected */
1030 /* from the information of the above bipartite graph, build the block-decomposition graph: nodes -> blocks and double-direction arcs -> linking variables */
1033 /* we count the number of block graph edges manually, because SCIPdigraphGetNArcs() iterates over all nodes */
1046 /* loop over the connected linking variables to the current block and their connected blocks to update the adjacency array */
1074 /* double-direction arcs are added in this step between the current block and its adjacent block nodes */
1192 /* the first label is always LINKVAR, even if Benders' variable labels are used. We can ignore the variables
1193 * labelled as LINKCONS since this label is only required when computing the variable labels for Benders'
1210 /* merge labels (except for border at position 0) since neither variable nor constraint labels by themselves need to be complete */
1246 SCIPdebugMsg(scip, "Counted %d different labels (should be %d)\n", currlabelidx, decomp->nblocks + 1);
1252 /* delete empty blocks from statistics, relabel the corresponding constraints/variables as linking */
1268 SCIP_CALL( SCIPdecompSetConsLabels(decomp, &conssarray[consblockstart], &conslabels[consblockstart], nblockconss) );
1284 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, &varsarray[varblockstart], &varslabels[varblockstart], nblockvars) );
1313 /* now that indices are fixed, store indices with largest and smallest number of constraints */
1324 /* compute more involved statistics such as the area score, the modularity, and the block graph statistics */
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:640
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:611
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:630
SCIP_RETCODE SCIPdecompstoreAdd(SCIP_DECOMPSTORE *decompstore, SCIP_DECOMP *decomp)
Definition: dcmp.c:575
int SCIPdecompstoreGetNDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:621
internal methods for decompositions and the decomposition store
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2208
methods for debugging
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:345
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:124
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:455
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:173
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:550
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:57
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1136
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
Definition: scip_dcmp.c:282
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:198
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:218
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:149
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8089
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7662
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
Definition: misc.c:8000
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:617
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition: scip_var.c:1830
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortInt(int *intarray, int len)
methods for block memory pools and memory buffers
Definition: objbenders.h:44
public methods for managing constraints
public methods for decompositions
public methods for message output
public data structures and miscellaneous methods
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for data structures
static SCIP_RETCODE computeModularity(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Real *modularity)
Definition: scip_dcmp.c:697
static void getDecompVarsConssData(SCIP *scip, SCIP_DECOMP *decomp, SCIP_VAR ***vars, SCIP_CONS ***conss, int *nvars, int *nconss)
Definition: scip_dcmp.c:109
static void computeAreaScore(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:815
static SCIP_RETCODE buildBlockGraph(SCIP *scip, SCIP_DECOMP *decomp, int maxgraphedge)
Definition: scip_dcmp.c:848
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)
Definition: scip_dcmp.c:139
static int countLabelFromPos(int *labels, int pos, int nlabels)
Definition: scip_dcmp.c:60
public methods for decompositions
general public methods
public methods for memory management
public methods for message handling
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for SCIP variables
Definition: struct_cons.h:47
Definition: struct_dcmp.h:45
Definition: struct_misc.h:220
Definition: struct_var.h:208
Definition: struct_scip.h:70
data structures for a decomposition and a decomposition store
SCIP main data structure.