tclique_branch.c
Go to the documentation of this file.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
152 /* clique2 has an element not contained in clique1: clique2 is lex-smaller, but probably clique1 is
241 /** ensures, that the clique hash table is able to store at least the given number of cliques */
288 /** searches the given clique in the clique hash table and returns whether it (or a stronger clique) exists */
324 /* we found the correct insertion position for the clique, but it might be contained in a lex-smaller clique */
397 debugMessage("extending temporary clique (size %d) with zero-weighted nodes (nVzero=%d)\n", *ncurcliquenodes, nVzero);
413 /* put zero-weighted candidates into the clique, and remove non-adjacent nodes from the candidate set */
427 nzerocands = selectadjnodes(tcliquegraph, curcliquenodes[(*ncurcliquenodes)-1], zerocands, nzerocands, zerocands);
431 /** calls user callback after a new solution was found, that is better than the current incumbent
433 * The callback decides, whether this solution should be accepted as new incumbent, and whether the solution process
493 newsol(tcliquedata, curcliquenodes, ncurcliquenodes, curcliqueweight, maxcliqueweight, &acceptsol, stopsolving);
495 /* if clique was accepted, clear the clique hash table; otherwise, insert it into the clique hash table, such that
531 debugMessage(" -> clique %s (weight %d):", acceptsol ? "accepted" : "rejected", curcliqueweight);
635 reduced(getweights, isedge, tcliquegraph, V, nV, apbound, tmpcliquenodes, ntmpcliquenodes, tmpcliqueweight);
647 /** gets the index of the node of V with the maximum apriori bound; returns -1, if no node exists */
676 /** gets the index of the node of V with the maximum apriori bound, but ignores nodes with weights
714 /** branches the searching tree, branching nodes are selected in decreasing order of their apriori bound,
745 TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
749 int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
751 int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */
786 debugMessage("(level %d, treenode %d) maxclique = %d, curclique = %d [mem=%" SCIP_LONGINT_FORMAT " (%" SCIP_LONGINT_FORMAT "), cliques=%d]\n",
813 /* use coloring relaxation to generate an upper bound for the current subtree and a heuristic solution */
830 * if the user wanted to have a fixed variable inside the clique and we are in level 0, we first have to
852 /* discard subtree, if the upper bound is not better than the weight of the currently best clique;
853 * if only 2 nodes are left, the maximal weighted clique was already calculated in boundSubgraph() and nothing
855 * however, if the user wanted to have a fixed node and we are in the first decision level, we have to continue
875 debugMessage("============================ branching level %d ===============================\n", level);
882 /* check if we meet the backtracking frequency - in this case abort the search until we have reached first level */
912 debugMessage("%d. branching in level %d (treenode %d): bidx=%d, node %d, weight %d, upperbound: %d+%d = %d, maxclique=%d\n",
942 backtracklevel = branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, /*lint !e838*/
954 debugMessage("branching on node %d was optimal - ignoring remaining candidates\n", branchingnode);
963 debugMessage("========================== branching level %d end =============================\n\n", level);
969 /* check, whether any branchings have been applied, or if this node is a leaf of the branching tree */
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,
1015 TCLIQUE_GRAPH* tcliquegraph, /**< pointer to graph data structure that is passed to graph callbacks */
1021 TCLIQUE_WEIGHT maxfirstnodeweight, /**< maximum weight of branching nodes in level 0; 0 if not used
1025 int backtrackfreq, /**< frequency to backtrack to first level of tree (0: no premature backtracking) */
1027 int fixednode, /**< node that is forced to be in the clique, or -1; must have positive weight */
1121 backtracklevel = branch(getnnodes, getweights, isedge, selectadjnodes, tcliquegraph, newsol, tcliquedata, mem,
1125 maxfirstnodeweight, &nbbtreenodes, maxntreenodes, backtrackfreq, maxnzeroextensions, fixednode, status);
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)
Definition: tclique_branch.c:437
tclique defines
static void extendCliqueZeroWeight(TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, int *buffer, int *Vzero, int nVzero, int maxnzeroextensions, int *curcliquenodes, int *ncurcliquenodes)
Definition: tclique_branch.c:375
static int getMaxApBoundIndexNotMaxWeight(int *V, int nV, const TCLIQUE_WEIGHT *apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight)
Definition: tclique_branch.c:682
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)
Definition: tclique_coloring.c:230
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)
Definition: tclique_branch.c:611
static void ensureCliquehashSize(CLIQUEHASH *cliquehash, int num)
Definition: tclique_branch.c:243
static void insertClique(CLIQUEHASH *cliquehash, CLIQUE *clique, int insertpos)
Definition: tclique_branch.c:339
Definition: tclique.h:66
tclique user interface
coloring part of algorithm for maximum cliques
Definition: cons_sos1.c:239
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)
Definition: tclique_branch.c:1010
static TCLIQUE_Bool inCliquehash(CLIQUEHASH *cliquehash, CLIQUE *clique, int *insertpos)
Definition: tclique_branch.c:290
Definition: tclique.h:64
static void createCliquehash(CLIQUEHASH **cliquehash, int tablesize)
Definition: tclique_branch.c:193
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)
Definition: tclique_branch.c:543
static int compSubcliques(CLIQUE *clique1, CLIQUE *clique2)
Definition: tclique_branch.c:126
struct _NBC NBC
static int getMaxApBoundIndex(int nV, TCLIQUE_WEIGHT *apbound)
Definition: tclique_branch.c:649
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)
Definition: tclique_branch.c:718
Definition: tclique.h:65
static void createClique(CLIQUE **clique, int *nodes, int nnodes)
Definition: tclique_branch.c:80
struct _LIST_ITV LIST_ITV
memory allocation routines