scip_dcmp.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46 #define LABEL_UNASSIGNED INT_MIN /* label constraints or variables as unassigned. Only for internal use */
97 /** get variables and constraints of the original or transformed problem, to which the decomposition corresponds */
138 SCIP_Bool* success /**< pointer to store whether variables and labels were successfully inserted */
212 SCIP_Bool original, /**< is this a decomposition in the original (TRUE) or transformed space? */
213 SCIP_Bool benderslabels /**< should the variables be labeled for the application of Benders' decomposition */
243 SCIP_CALL( SCIPcheckStage(scip, "SCIPaddDecomp", FALSE, SCIPdecompIsOriginal(decomp), SCIPdecompIsOriginal(decomp),
244 SCIPdecompIsOriginal(decomp), SCIPdecompIsOriginal(decomp), TRUE, TRUE, TRUE, !SCIPdecompIsOriginal(decomp),
262 SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetDecomps", FALSE, original, original, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE) );
265 *decomps = original ? SCIPdecompstoreGetOrigDecomps(scip->decompstore) : SCIPdecompstoreGetDecomps(scip->decompstore);
268 *ndecomps = original ? SCIPdecompstoreGetNOrigDecomps(scip->decompstore) : SCIPdecompstoreGetNDecomps(scip->decompstore);
271 /** returns TRUE if the constraint \p cons contains only linking variables in decomposition \p decomp */
276 SCIP_Bool* hasonlylinkvars /**< will be set to TRUE if this constraint has only linking variables */
325 * The computed labels depend on the flag SCIPdecompUseBendersLabels() of the decomposition. If the flag is set
328 * - label i, if only variables labeled i are present in the constraint (and optionally linking variables)
329 * - SCIP_DECOMP_LINKCONS, if there are either only variables labeled with SCIP_DECOMP_LINKVAR present, or
332 * If the flag is set to TRUE, the assignment is the same, unless variables from 2 named blocks occur in the same
385 /* count the number of linking variables, and keep track if there are two variables with different labels */
392 /* there must not be two variables from different named blocks in a single constraint, since the presence
418 /* throw an error and inform the user if the variable block decomposition does not allow a benders constraint labeling */
421 SCIPerrorMessage("Error in constraint label computation; variables from multiple named blocks in a single constraint\n");
431 * NOTE: by default, the variable labeling is based on a Dantzig-Wolfe decomposition. This means that constraints in named
432 * blocks have have precedence over linking constraints. If a variable exists in constraints from
435 * Variables which are only in linking constraints are unlabeled. However, SCIPdecompGetVarsLabels() will
438 * If the variables should be labeled for the application of Benders' decomposition, the decomposition must be
440 * With this setting, the presence in linking constraints takes precedence over the presence in named blocks.
441 * Now, a variable is considered linking if it is present in at least one linking constraint and an arbitrary
499 /* each variable in this constraint gets the constraint label unless it already has a different label -> make it a linking variable */
537 * @note: In contrast to SCIPcomputeDecompConsLabels(), this method potentially relabels variables.
654 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, &vars[startposs[p]], &varslabels[startposs[p]], endposs[p] - startposs[p]) );
684 /** compute decomposition modularity (comparison of within block edges against a random decomposition) */
704 /* allocate buffer arrays to hold constraint and variable labels, and store within-edges and total community degrees */
734 /* find the position of the constraint label. Constraints of the border always belong to the first block at index 0 */
759 /* increase the total degrees and nonzero (edge) counts; it is intended that the total degrees sum up
829 areascore -= ((SCIP_Real)nlinkconss * nvars + (SCIP_Real)nconss * nlinkvars - (SCIP_Real)nlinkconss * nlinkvars) * factor;
840 int maxgraphedge /**< maximum number of edges in block graph computation (-1: no limit, 0: disable block graph computation) */
904 /* create a mapping of all linking variables to 0,..,nlinkingvars -1 and store it in array linkvaridx */
918 SCIP_CALL( SCIPcreateDigraph(scip, &blocklinkingvargraph, nblocks + nlinkingvars) );/* nblocks does not include the linking constraints block */
955 /* search for linking variables that are not connected so far; stop as soon as block vertex has max degree */
978 SCIP_CALL( SCIPdigraphAddArc(blocklinkingvargraph, blocknodeidx, nblocks + adjacentidxs[i], NULL) );
979 SCIP_CALL( SCIPdigraphAddArc(blocklinkingvargraph, nblocks + adjacentidxs[i], blocknodeidx, NULL) );
1001 /* check first if any of the linking variables is connected with all blocks -> block graph is complete and connected */
1019 /* from the information of the above bipartite graph, build the block-decomposition graph: nodes -> blocks and double-direction arcs -> linking variables */
1022 /* we count the number of block graph edges manually, because SCIPdigraphGetNArcs() iterates over all nodes */
1035 /* loop over the connected linking variables to the current block and their connected blocks to update the adjacency array */
1063 /* double-direction arcs are added in this step between the current block and its adjacent block nodes */
1181 /* the first label is always LINKVAR, even if Benders' variable labels are used. We can ignore the variables
1182 * labelled as LINKCONS since this label is only required when computing the variable labels for Benders'
1199 /* merge labels (except for border at position 0) since neither variable nor constraint labels by themselves need to be complete */
1235 SCIPdebugMsg(scip, "Counted %d different labels (should be %d)\n", currlabelidx, decomp->nblocks + 1);
1241 /* delete empty blocks from statistics, relabel the corresponding constraints/variables as linking */
1257 SCIP_CALL( SCIPdecompSetConsLabels(decomp, &conssarray[consblockstart], &conslabels[consblockstart], nblockconss) );
1273 SCIP_CALL( SCIPdecompSetVarsLabels(decomp, &varsarray[varblockstart], &varslabels[varblockstart], nblockvars) );
1302 /* now that indices are fixed, store indices with largest and smallest number of constraints */
1313 /* compute more involved statistics such as the area score, the modularity, and the block graph statistics */
Definition: struct_dcmp.h:35
public methods for SCIP parameter handling
Definition: struct_scip.h:59
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3297
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:630
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:188
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:444
public methods for memory management
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:539
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:7991
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:601
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1125
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7721
static void getDecompVarsConssData(SCIP *scip, SCIP_DECOMP *decomp, SCIP_VAR ***vars, SCIP_CONS ***conss, int *nvars, int *nconss)
Definition: scip_dcmp.c:99
Definition: struct_var.h:198
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:335
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:139
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:114
public methods for problem variables
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8186
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
public methods for SCIP variables
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:608
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:253
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:620
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
public methods for decompositions
public methods for managing constraints
int SCIPdecompstoreGetNDecomps(SCIP_DECOMPSTORE *decompstore)
Definition: dcmp.c:611
Definition: struct_cons.h:37
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2558
methods for block memory pools and memory buffers
SCIP_RETCODE SCIPdecompstoreAdd(SCIP_DECOMPSTORE *decompstore, SCIP_DECOMP *decomp)
Definition: dcmp.c:565
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:2177
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
Definition: type_retcode.h:33
static SCIP_RETCODE computeModularity(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Real *modularity)
Definition: scip_dcmp.c:686
SCIP main data structure.
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7564
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2514
public methods for constraint handler plugins and constraints
Definition: type_retcode.h:34
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:163
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7706
static void computeAreaScore(SCIP *scip, SCIP_DECOMP *decomp)
Definition: scip_dcmp.c:804
static SCIP_RETCODE buildBlockGraph(SCIP *scip, SCIP_DECOMP *decomp, int maxgraphedge)
Definition: scip_dcmp.c:837
data structures for a decomposition and a decomposition store
methods for debugging
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:47
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
Definition: misc.c:7902
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
Definition: scip_dcmp.c:272
internal methods for decompositions and the decomposition store
general public methods
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:129
public methods for message handling
public methods for data structures
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:208
void SCIPsortInt(int *intarray, int len)
static int countLabelFromPos(int *labels, int pos, int nlabels)
Definition: scip_dcmp.c:50
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:259
Definition: type_retcode.h:43
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
public methods for decompositions
Definition: objbenders.h:33
public methods for global and local (sub)problems
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
Definition: scip_var.c:1827
Definition: struct_misc.h:210