48#define CHUNK_SIZE (64)
49#define CLIQUEHASH_INITSIZE (1024)
100 for( j =
i; j > 0 && node < (*clique)->nodes[j-1]; --j )
101 (*clique)->nodes[j] = (*clique)->nodes[j-1];
102 (*clique)->nodes[j] = node;
104 (*clique)->nnodes =
nnodes;
140 clique2smaller =
FALSE;
141 while( pos1 < clique1->
nnodes && pos2 < clique2->
nnodes )
143 if( clique1->nodes[pos1] < clique2->nodes[pos2] )
148 return (clique2smaller ? +1 : -1);
150 else if( clique1->nodes[pos1] > clique2->nodes[pos2] )
156 clique2smaller =
TRUE;
166 if( pos1 < clique1->
nnodes )
167 return (clique2smaller ? +1 : -1);
184 for(
i = 0;
i < cliquehash->ncliques-1; ++
i )
188#define checkCliquehash(cliquehash)
203 (*cliquehash)->cliquessize = tablesize;
204 (*cliquehash)->ncliques = 0;
218 for(
i = 0;
i < cliquehash->ncliques; ++
i )
221 cliquehash->ncliques = 0;
250 if( num > cliquehash->cliquessize )
254 newsize = 2*cliquehash->cliquessize;
259 cliquehash->cliquessize = newsize;
261 assert(cliquehash->cliquessize >= num);
275 debugMessage(
"cliquehash (%d cliques):\n", cliquehash->ncliques);
276 for(
i = 0;
i < cliquehash->ncliques; ++
i )
281 for( j = 0; j < cliquehash->cliques[
i]->nnodes; ++j )
302 assert(cliquehash->cliquessize > 0);
308 right = cliquehash->ncliques-1;
309 while( left <= right )
311 middle = (left+right)/2;
326 for( middle = left-1; middle >= 0; --middle )
349 assert(0 <= insertpos && insertpos <= cliquehash->ncliques);
355 for(
i = cliquehash->ncliques;
i > insertpos; --
i )
356 cliquehash->cliques[
i] = cliquehash->cliques[
i-1];
357 cliquehash->cliques[insertpos] = clique;
358 cliquehash->ncliques++;
363 debug(printCliquehash(cliquehash));
381 int maxnzeroextensions,
397 debugMessage(
"extending temporary clique (size %d) with zero-weighted nodes (nVzero=%d)\n", *ncurcliquenodes, nVzero);
399 if( maxnzeroextensions == 0 )
410 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[
i], zerocands, nzerocands, zerocands);
415 while( nzerocands > 0 )
418 curcliquenodes[*ncurcliquenodes] = zerocands[0];
419 (*ncurcliquenodes)++;
423 if( nzeroextensions >= maxnzeroextensions )
427 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[(*ncurcliquenodes)-1], zerocands, nzerocands, zerocands);
446 int maxnzeroextensions,
451 int* nmaxcliquenodes,
464 assert(curcliqueweight > *maxcliqueweight);
469 *stopsolving =
FALSE;
476 if( cliquehash->ncliques > 0 )
479 acceptsol = !
inCliquehash(cliquehash, clique, &insertpos);
488 curcliquenodes, &ncurcliquenodes);
493 newsol(tcliquedata, curcliquenodes, ncurcliquenodes, curcliqueweight, maxcliqueweight, &acceptsol, stopsolving);
506 assert(cliquehash->ncliques == 0);
525 *nmaxcliquenodes = ncurcliquenodes;
526 if( curcliqueweight > *maxcliqueweight )
527 *maxcliqueweight = curcliqueweight;
531 debugMessage(
" -> clique %s (weight %d):", acceptsol ?
"accepted" :
"rejected", curcliqueweight);
534 for(
i = 0;
i < ncurcliquenodes; ++
i )
551 int* ntmpcliquenodes,
561 assert(0 <= nV && nV <= 2);
567 weights = getweights(tcliquegraph);
568 assert(nV == 0 || weights[V[0]] > 0);
569 assert(nV <= 1 || weights[V[1]] > 0);
572 apbound[0] = weights[V[0]];
574 apbound[1] = weights[V[1]];
577 if( nV >= 2 && isedge(tcliquegraph, V[0], V[1]) )
579 assert(isedge(tcliquegraph, V[1], V[0]));
582 tmpcliquenodes[0] = V[0];
583 tmpcliquenodes[1] = V[1];
584 *ntmpcliquenodes = 2;
585 *tmpcliqueweight = weights[V[0]] + weights[V[1]];
586 apbound[0] += weights[V[1]];
588 else if( nV >= 2 && weights[V[1]] > weights[V[0]] )
591 tmpcliquenodes[0] = V[1];
592 *ntmpcliquenodes = 1;
593 *tmpcliqueweight = weights[V[1]];
598 tmpcliquenodes[0] = V[0];
599 *ntmpcliquenodes = 1;
600 *tmpcliqueweight = weights[V[0]];
604 *tmpcliqueweight = 0;
605 *ntmpcliquenodes = 0;
625 int* ntmpcliquenodes,
635 reduced(getweights, isedge, tcliquegraph, V, nV, apbound, tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
636 return *tmpcliqueweight;
641 return tcliqueColoring(getnnodes, getweights, selectadjnodes, tcliquegraph,
642 mem, buffer, V, nV, gsd, iscolored, apbound,
643 tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
663 for(
i = 0 ;
i < nV;
i++ )
666 if( apbound[
i] >= maxapbound )
668 maxapbound = apbound[
i];
699 for(
i = 0 ;
i < nV;
i++ )
704 if( apbound[
i] >= maxapbound && weights[V[
i]] <= maxweight )
706 maxapbound = apbound[
i];
739 int* nmaxcliquenodes,
742 int* ncurcliquenodes,
750 int maxnzeroextensions,
778 assert(maxfirstnodeweight >= 0);
780 assert(maxntreenodes >= 0);
787 level, *ntreenodes, *maxcliqueweight, *curcliqueweight,
790 debugMessage(
" -> current branching (weight %d):", weightK);
791 for(
i = 0;
i < level; ++
i )
795 for(
i = 0;
i < nV; ++
i )
799 if( *ntreenodes > maxntreenodes )
805 weights = getweights(tcliquegraph);
806 backtracklevel = INT_MAX;
814 subgraphweight =
boundSubgraph(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph,
815 mem, buffer, V, nV, gsd, iscolored, apbound,
816 tmpcliquenodes, &ntmpcliquenodes, &tmpcliqueweight);
820 for(
i = 0;
i < nV; ++
i )
822 assert(0 <= V[
i] && V[
i] < getnnodes(tcliquegraph));
825 assert((apbound[
i] == 0) == (weights[V[
i]] == 0));
833 if( weightK + tmpcliqueweight > *curcliqueweight && (level > 0 || fixednode == -1) )
836 for(
i = 0;
i < level; ++
i )
837 curcliquenodes[
i] = K[
i];
838 for(
i = 0;
i < ntmpcliquenodes; ++
i )
839 curcliquenodes[level+
i] = tmpcliquenodes[
i];
840 *ncurcliquenodes = level + ntmpcliquenodes;
841 *curcliqueweight = weightK + tmpcliqueweight;
844 debugMessage(
" -> new current clique with weight %d at node %d in level %d:",
845 *curcliqueweight, *ntreenodes, level);
846 for(
i = 0;
i < *ncurcliquenodes; ++
i )
857 if( weightK + subgraphweight > *maxcliqueweight && (nV > 2 || (fixednode >= 0 && level == 0)) )
873 weightKold = weightK;
875 debugMessage(
"============================ branching level %d ===============================\n", level);
878 while( backtracklevel >= level && nValive > 0 )
883 if( level > 1 && backtrackfreq > 0 && (*ntreenodes) % backtrackfreq == 0 )
890 if( level == 1 && fixednode >= 0 )
893 for( branchidx = 0; branchidx < nValive && V[branchidx] != fixednode; branchidx++ )
895 assert(branchidx < nValive);
896 assert(V[branchidx] == fixednode);
898 else if( level == 1 && maxfirstnodeweight > 0 )
904 assert(0 <= branchidx && branchidx < nValive && nValive <= nV);
905 assert(apbound[branchidx] > 0);
906 assert(weights[V[branchidx]] > 0);
909 if( (weightKold + apbound[branchidx]) <= *maxcliqueweight )
912 debugMessage(
"%d. branching in level %d (treenode %d): bidx=%d, node %d, weight %d, upperbound: %d+%d = %d, maxclique=%d\n",
913 nV-nValive+1, level, *ntreenodes, branchidx, V[branchidx], weights[V[branchidx]], weightKold,
914 apbound[branchidx], weightKold + apbound[branchidx], *maxcliqueweight);
922 branchingnode = V[branchidx];
923 K[level-1] = branchingnode;
924 weightK = weightKold + weights[branchingnode];
930 for(
i = branchidx;
i < nValive; ++
i )
933 apbound[
i] = apbound[
i+1];
939 nVcurrent = selectadjnodes(tcliquegraph, branchingnode, V, nValive, Vcurrent);
942 backtracklevel =
branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata,
943 mem, cliquehash, buffer,
944 level, Vcurrent, nVcurrent, Vzero, nVzero, gsd, iscolored, K, weightK,
945 maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
946 curcliquenodes, ncurcliquenodes, curcliqueweight, tmpcliquenodes,
947 maxfirstnodeweight, ntreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, -1, status);
952 if( nVcurrent == nValive )
954 debugMessage(
"branching on node %d was optimal - ignoring remaining candidates\n", branchingnode);
963 debugMessage(
"========================== branching level %d end =============================\n\n", level);
975 if( *curcliqueweight > *maxcliqueweight )
979 debugMessage(
"found clique of weight %d at node %d in level %d\n", *curcliqueweight, *ntreenodes, level);
980 newSolution(selectadjnodes, tcliquegraph, newsol, tcliquedata, cliquehash, buffer, Vzero, nVzero,
981 maxnzeroextensions, curcliquenodes, *ncurcliquenodes, *curcliqueweight,
982 maxcliquenodes, nmaxcliquenodes, maxcliqueweight, &stopsolving);
986 debugMessage(
" -> solving terminated by callback method\n");
992 *ncurcliquenodes = 0;
993 *curcliqueweight = 0;
997 if( level > backtracklevel )
999 debugMessage(
"premature backtracking after %d nodes - level %d\n", *ntreenodes, level);
1006 return backtracklevel;
1018 int* maxcliquenodes,
1019 int* nmaxcliquenodes,
1026 int maxnzeroextensions,
1045 int* curcliquenodes;
1046 int ncurcliquenodes;
1048 int* tmpcliquenodes;
1055 assert(maxntreenodes >= 0);
1056 assert(backtrackfreq >= 0);
1057 assert(maxnzeroextensions >= 0);
1063 if( getnnodes ==
NULL )
1064 getnnodes = tcliqueGetNNodes;
1065 if( getweights ==
NULL )
1066 getweights = tcliqueGetWeights;
1067 if( isedge ==
NULL )
1068 isedge = tcliqueIsEdge;
1069 if( selectadjnodes ==
NULL )
1070 selectadjnodes = tcliqueSelectAdjnodes;
1073 nnodes = getnnodes(tcliquegraph);
1078 if( newsol !=
NULL )
1092 *nmaxcliquenodes = 0;
1093 *maxcliqueweight = minweight-1;
1094 ncurcliquenodes = 0;
1095 curcliqueweight = 0;
1099 weights = getweights(tcliquegraph);
1105 if( weights[
i] == 0 )
1121 backtracklevel =
branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, mem,
1122 cliquehash, buffer, 0, V, nV, Vzero, nVzero, gsd, iscolored, K, 0,
1123 maxcliquenodes, nmaxcliquenodes, maxcliqueweight,
1124 curcliquenodes, &ncurcliquenodes, &curcliqueweight, tmpcliquenodes,
1125 maxfirstnodeweight, &nbbtreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, fixednode, status);
1127 if ( ntreenodes !=
NULL )
1128 *ntreenodes = nbbtreenodes;
1145 if( newsol !=
NULL )
#define SCIP_LONGINT_FORMAT
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
#define BMSfreeMemory(ptr)
#define BMSreallocMemoryArray(ptr, num)
#define BMSgetChunkMemoryUsed(mem)
struct BMS_ChkMem BMS_CHKMEM
#define BMSgetMemoryUsed()
#define BMSallocMemoryArray(ptr, num)
#define BMSfreeMemoryArray(ptr)
#define BMScopyMemoryArray(ptr, source, num)
#define BMSdestroyChunkMemory(mem)
#define BMScreateChunkMemory(sz, isz, gbf)
#define BMSclearMemoryArray(ptr, num)
#define BMSallocMemory(ptr)
#define TCLIQUE_GETWEIGHTS(x)
#define TCLIQUE_GETNNODES(x)
#define TCLIQUE_ISEDGE(x)
#define TCLIQUE_SELECTADJNODES(x)
enum TCLIQUE_Status TCLIQUE_STATUS
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define TCLIQUE_NEWSOL(x)
static void clearCliquehash(CLIQUEHASH *cliquehash)
static void newSolution(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, CLIQUEHASH *cliquehash, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int ncurcliquenodes, TCLIQUE_WEIGHT curcliqueweight, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_Bool *stopsolving)
static int branch(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, BMS_CHKMEM *mem, CLIQUEHASH *cliquehash, int *buffer, int level, int *V, int nV, int *Vzero, int nVzero, NBC *gsd, TCLIQUE_Bool *iscolored, int *K, TCLIQUE_WEIGHT weightK, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, int *curcliquenodes, int *ncurcliquenodes, TCLIQUE_WEIGHT *curcliqueweight, int *tmpcliquenodes, TCLIQUE_WEIGHT maxfirstnodeweight, int *ntreenodes, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, TCLIQUE_STATUS *status)
static void freeClique(CLIQUE **clique)
static void extendCliqueZeroWeight(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int *ncurcliquenodes)
static TCLIQUE_Bool inCliquehash(CLIQUEHASH *cliquehash, CLIQUE *clique, int *insertpos)
#define CLIQUEHASH_INITSIZE
struct cliquehash CLIQUEHASH
static void ensureCliquehashSize(CLIQUEHASH *cliquehash, int num)
static void checkCliquehash(CLIQUEHASH *cliquehash)
static void createClique(CLIQUE **clique, int *nodes, int nnodes)
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
static void insertClique(CLIQUEHASH *cliquehash, CLIQUE *clique, int insertpos)
static int getMaxApBoundIndexNotMaxWeight(int *V, int nV, const TCLIQUE_WEIGHT *apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight)
static void freeCliquehash(CLIQUEHASH **cliquehash)
static int compSubcliques(CLIQUE *clique1, CLIQUE *clique2)
static TCLIQUE_WEIGHT boundSubgraph(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, BMS_CHKMEM *mem, int *buffer, int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, TCLIQUE_WEIGHT *apbound, int *tmpcliquenodes, int *ntmpcliquenodes, TCLIQUE_WEIGHT *tmpcliqueweight)
static int getMaxApBoundIndex(int nV, TCLIQUE_WEIGHT *apbound)
static void createCliquehash(CLIQUEHASH **cliquehash, int tablesize)
static void reduced(TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_GRAPH *tcliquegraph, int *V, int nV, TCLIQUE_WEIGHT *apbound, int *tmpcliquenodes, int *ntmpcliquenodes, TCLIQUE_WEIGHT *tmpcliqueweight)
TCLIQUE_WEIGHT tcliqueColoring(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, BMS_CHKMEM *mem, int *buffer, int *V, int nV, NBC *gsd, TCLIQUE_Bool *iscolored, TCLIQUE_WEIGHT *apbound, int *clique, int *nclique, TCLIQUE_WEIGHT *weightclique)
coloring part of algorithm for maximum cliques
struct _LIST_ITV LIST_ITV