56#define LABEL_UNASSIGNED INT_MIN
72 currlabel = labels[pos];
78 while( endpos < nlabels && labels[endpos] == currlabel );
104 return 2 *
MAX(norigvars, ntransvars);
172 if( bufsize < *
nvars )
174 *requiredsize = *
nvars;
190 if( *requiredsize > bufsize )
196 for( v = 0; v < *
nvars; ++v )
207 if( labelbuf !=
NULL )
223 SCIP_Bool benderslabels
272 SCIP_CALL_ABORT(
SCIPcheckStage(
scip,
"SCIPgetDecomps",
FALSE, original, original,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE) );
274 if( decomps !=
NULL )
277 if( ndecomps !=
NULL )
286 SCIP_Bool* hasonlylinkvars
314 *hasonlylinkvars =
TRUE;
316 for(
i = 0;
i <
nvars && *hasonlylinkvars; ++
i )
357 SCIP_Bool benderserror;
358 SCIP_Bool benderslabels;
372 benderserror =
FALSE;
375 for(
c = 0;
c < nconss && ! benderserror; ++
c )
379 int nlinkingvars = 0;
386 varbufsize, &nconsvars, &requiredsize, &success) );
391 for( v = 0; v < nconsvars; ++v )
393 int varlabel = varlabels[v];
399 conslabel = varlabel;
400 else if( conslabel != varlabel )
420 conslabels[
c] = conslabel;
432 SCIPerrorMessage(
"Error in constraint label computation; variables from multiple named blocks in a single constraint\n");
466 SCIP_Bool benderslabels;
484 for(
c = 0;
c < nconss; ++
c )
493 conslabel = conslabels[
c];
498 if( ! benderslabels )
504 newvarlabel = conslabel;
507 varbufsize, &nconsvars, &requiredsize, &success) );
511 for( v = 0; v < nconsvars; ++v )
585 defaultlabel = varslabels[
c];
591 for(
c = 0;
c < nconss;
c++ )
596 &nconsvars, &requiredsize, &success) );
633 assert(nlinkvars < nconsvars);
642 if( nblockvars > maxnblockvars )
644 maxnblockvars = nblockvars;
649 while( curr < nconsvars );
652 startposs[0] = nlinkvars;
654 startposs[1] = block + maxnblockvars;
655 endposs[1] = nconsvars;
658 for( p = 0; p < 2; ++p )
661 for( v = startposs[p]; v < endposs[p]; ++v )
672 if( nskipconss !=
NULL )
673 *nskipconss = nskipconsslocal;
700 SCIP_Real* modularity
732 for(
c = 0;
c < nconss; ++
c )
735 int conslabel = conslabels[
c];
749 varbufsize, &nconsvars, &requiredsize, &success) );
756 while( varblockstart < nconsvars )
761 varblockpos =
findLabelIdx(decomp, varslabels[varblockstart]);
767 if( varblockpos == blockpos )
768 withinedges[varblockpos] += nblockvars;
773 totaldegrees[blockpos] += nblockvars;
774 totaldegrees[varblockpos] += nblockvars;
775 nnonzeroes += nblockvars;
778 varblockstart += nblockvars;
785 int totaldegreesum = 0;
787 totaldegreesum += totaldegrees[
b];
789 assert(totaldegreesum == 2 * nnonzeroes);
795 nnonzeroes =
MAX(nnonzeroes, 1);
798 SCIP_Real expectedval;
799 expectedval = totaldegrees[
b] / (2.0 * nnonzeroes);
800 expectedval =
SQR(expectedval);
801 *modularity += (withinedges[
b] / (
SCIP_Real)nnonzeroes) - expectedval;
820 SCIP_Real areascore = 1.0;
826 if(
nvars > 0 && nconss > 0 )
829 int nlinkvars = decomp->
varssize[0];
840 areascore -= ((
SCIP_Real)nlinkconss *
nvars + (SCIP_Real)nconss * nlinkvars - (
SCIP_Real)nlinkconss * nlinkvars) * factor;
870 int nlinkingvars = 0;
875 int nblockgraphedges;
882 if( maxgraphedge == -1 )
883 maxgraphedge = INT_MAX;
916 for( v = 0; v <
nvars; ++v )
920 linkvaridx[v] = nlinkingvars;
942 while( conspos < nconss )
947 int nblocklinkingvars = 0;
956 for(
c = conspos;
c < conspos + nblockconss && nblocklinkingvars < nlinkingvars; ++
c )
963 varbufsize, &nconsvars, &requiredsize, &success) );
967 for( j = 0; j < nconsvars && nblocklinkingvars < nlinkingvars; ++j )
969 int linkingvarnodeidx;
975 assert(linkingvarnodeidx >= 0);
977 if( !adjacent[linkingvarnodeidx] )
979 adjacent[linkingvarnodeidx] =
TRUE;
980 adjacentidxs[nblocklinkingvars++] = linkingvarnodeidx;
987 for(
i = 0;
i < nblocklinkingvars; ++
i )
994 for(
i = 0;
i < nblocklinkingvars; ++
i )
995 adjacent[adjacentidxs[
i]] =
FALSE;
999 for(
i = 0;
i < nlinkingvars; ++
i )
1006 conspos += nblockconss;
1018 if( nsuccvar == nblocks )
1020 decomp->
nedges = nblocks * (nblocks - 1) / 2;
1034 nblockgraphedges = 0;
1035 for( n = 0; n < nblocks - 1 && nblockgraphedges < maxgraphedge; ++n )
1037 SCIP_Bool* adjacent;
1040 int nadjacentblks = 0;
1049 for(
i = 0;
i < nsuccblk && nadjacentblks < nblocks - (n + 1); ++
i )
1062 for( j = startpos + 1; j < nsuccvar; ++j )
1064 assert( succnodesvar[j] > n );
1065 if( !adjacent[succnodesvar[j]] )
1067 adjacent[succnodesvar[j]] =
TRUE;
1068 adjacentidxs[nadjacentblks] = succnodesvar[j];
1075 for(
i = 0;
i < nadjacentblks && nblockgraphedges < maxgraphedge; ++
i )
1084 for(
i = 0;
i < nadjacentblks; ++
i )
1085 adjacent[adjacentidxs[
i]] =
FALSE;
1094 decomp->
nedges = nblockgraphedges;
1104 if( nsuccblk < tempmin )
1106 else if( nsuccblk > tempmax )
1127 if( blockgraph !=
NULL)
1157 SCIP_Bool disablemeasures;
1168 if(
nvars == 0 || nconss == 0 )
1221 conslabel = considx < nconss ? conslabels[considx] : INT_MAX;
1223 assert(currlabelidx < decomp->memsize);
1225 decomp->
labels[currlabelidx] =
MIN(varlabel, conslabel);
1228 if( varlabel <= conslabel )
1231 decomp->
varssize[currlabelidx] = 0;
1234 if( conslabel <= varlabel )
1241 considx += decomp->
consssize[currlabelidx];
1249 if( currlabelidx < decomp->nblocks + 1 )
1250 decomp->
nblocks = currlabelidx - 1;
1253 varblockstart = decomp->
varssize[0];
1265 for(
c = consblockstart;
c < consblockstart + nblockconss; ++
c )
1281 for( v = varblockstart; v < varblockstart + nblockvars; ++v )
1310 decomp->
nblocks = currlabelidx - 1;
1326 if( !disablemeasures )
1340 if( maxgraphedge != 0 )
int SCIPdecompstoreGetNOrigDecomps(SCIP_DECOMPSTORE *decompstore)
SCIP_DECOMP ** SCIPdecompstoreGetDecomps(SCIP_DECOMPSTORE *decompstore)
SCIP_DECOMP ** SCIPdecompstoreGetOrigDecomps(SCIP_DECOMPSTORE *decompstore)
SCIP_RETCODE SCIPdecompstoreAdd(SCIP_DECOMPSTORE *decompstore, SCIP_DECOMP *decomp)
int SCIPdecompstoreGetNDecomps(SCIP_DECOMPSTORE *decompstore)
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)
#define SCIP_CALL_ABORT(x)
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
SCIP_RETCODE SCIPaddDecomp(SCIP *scip, SCIP_DECOMP *decomp)
SCIP_RETCODE SCIPhasConsOnlyLinkVars(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS *cons, SCIP_Bool *hasonlylinkvars)
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
int SCIPgetNOrigConss(SCIP *scip)
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
SCIP_CONS ** SCIPgetConss(SCIP *scip)
int SCIPgetNVars(SCIP *scip)
int SCIPgetNConss(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_CONS ** SCIPgetOrigConss(SCIP *scip)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
#define SCIPfreeCleanBufferArray(scip, ptr)
#define SCIPallocCleanBufferArray(scip, ptr, num)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
SCIP_RETCODE SCIPgetActiveVars(SCIP *scip, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize)
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)
assert(minobj< SCIPgetCutoffbound(scip))
methods for block memory pools and memory buffers
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
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)
static SCIP_RETCODE ensureCondition(SCIP_Bool condition)
static void getDecompVarsConssData(SCIP *scip, SCIP_DECOMP *decomp, SCIP_VAR ***vars, SCIP_CONS ***conss, int *nvars, int *nconss)
static int findLabelIdx(SCIP_DECOMP *decomp, int label)
static void computeAreaScore(SCIP *scip, SCIP_DECOMP *decomp)
static int getVarbufSize(SCIP *scip)
static SCIP_RETCODE buildBlockGraph(SCIP *scip, SCIP_DECOMP *decomp, int maxgraphedge)
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 int countLabelFromPos(int *labels, int pos, int nlabels)
public methods for decompositions
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
data structures for a decomposition and a decomposition store
SCIP main data structure.
#define SCIP_DECOMP_LINKVAR
#define SCIP_DECOMP_LINKCONS
enum SCIP_Retcode SCIP_RETCODE