Detailed Description

branch and bound part of algorithm for maximum cliques

Author: Tobias Achterberg; Ralf Borndoerfer; Zoltan Kormos; Kati Wolter

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include "tclique/tclique.h"
#include "tclique/tclique_def.h"
#include "tclique/tclique_coloring.h"
#include "blockmemshell/memory.h"

Go to the source code of this file.

Macros
#define	CHUNK_SIZE (64)

#define	CLIQUEHASH_INITSIZE (1024)

Typedefs
typedef struct clique	CLIQUE

typedef struct cliquehash	CLIQUEHASH

Functions
static void	createClique (CLIQUE *clique, int nodes, int nnodes)

static void	freeClique (CLIQUE **clique)

static int	compSubcliques (CLIQUE clique1, CLIQUE clique2)

static void	checkCliquehash (CLIQUEHASH *cliquehash)

static void	createCliquehash (CLIQUEHASH **cliquehash, int tablesize)

static void	clearCliquehash (CLIQUEHASH *cliquehash)

static void	freeCliquehash (CLIQUEHASH **cliquehash)

static void	ensureCliquehashSize (CLIQUEHASH *cliquehash, int num)

static TCLIQUE_Bool	inCliquehash (CLIQUEHASH cliquehash, CLIQUE clique, int *insertpos)

static void	insertClique (CLIQUEHASH cliquehash, CLIQUE clique, int insertpos)

static void	extendCliqueZeroWeight (TCLIQUE_SELECTADJNODES((selectadjnodes)), TCLIQUE_GRAPH tcliquegraph, int buffer, int Vzero, int nVzero, int maxnzeroextensions, int curcliquenodes, int ncurcliquenodes)

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 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)

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 int	getMaxApBoundIndexNotMaxWeight (int V, int nV, const TCLIQUE_WEIGHT apbound, const TCLIQUE_WEIGHT *weights, TCLIQUE_WEIGHT maxweight)

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)

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)

Macro Definition Documentation

#define CHUNK_SIZE (64)

Definition at line 38 of file tclique_branch.c.

Referenced by tcliqueMaxClique().

#define CLIQUEHASH_INITSIZE (1024)

Definition at line 39 of file tclique_branch.c.

Referenced by tcliqueMaxClique().

Typedef Documentation

typedef struct clique CLIQUE

single element of the clique hash table

Definition at line 48 of file tclique_branch.c.

typedef struct cliquehash CLIQUEHASH

hash table for storing cliques

Definition at line 57 of file tclique_branch.c.

Function Documentation

static void createClique	(	CLIQUE **	clique,
		int *	nodes,
		int	nnodes
	)

static

creates a clique

Parameters

clique	pointer to the clique
nodes	nodes of the clique
nnodes	number of nodes in the clique

Definition at line 70 of file tclique_branch.c.

References ALLOC_ABORT, BMSallocMemory, BMSallocMemoryArray, and NULL.

Referenced by newSolution().

static void freeClique ( CLIQUE ** clique )

static

frees a clique

Parameters

clique pointer to the clique

Definition at line 99 of file tclique_branch.c.

References BMSfreeMemory, BMSfreeMemoryArray, and NULL.

Referenced by clearCliquehash(), and newSolution().

static int compSubcliques	(	CLIQUE *	clique1,
		CLIQUE *	clique2
	)

static

checks, whether clique1 is a subset of clique2 and returns the following value: == 0 if clique1 == clique2, or clique1 is contained in clique2, < 0 if clique1 < clique2, and clique1 is not contained in clique2,

0 if clique1 > clique2, and clique1 is not contained in clique2

Parameters

clique1	first clique to compare
clique2	second clique to compare

Definition at line 116 of file tclique_branch.c.

References FALSE, NULL, TCLIQUE_Bool, and TRUE.

Referenced by checkCliquehash(), and inCliquehash().

static void checkCliquehash ( CLIQUEHASH * cliquehash )

static

performs an integrity check of the clique hash table

Parameters

cliquehash clique hash table

Definition at line 166 of file tclique_branch.c.

References compSubcliques(), and NULL.

Referenced by insertClique().

static void createCliquehash	(	CLIQUEHASH **	cliquehash,
		int	tablesize
	)

static

creates a table for storing cliques

Parameters

cliquehash	pointer to store the clique hash table
tablesize	initial size of the clique hash table

Definition at line 183 of file tclique_branch.c.

References ALLOC_ABORT, BMSallocMemory, BMSallocMemoryArray, and NULL.

Referenced by tcliqueMaxClique().

static void clearCliquehash ( CLIQUEHASH * cliquehash )

static

clears the clique hash table and frees all inserted cliques

Parameters

cliquehash clique hash table

Definition at line 199 of file tclique_branch.c.

References freeClique(), and NULL.

Referenced by freeCliquehash(), and newSolution().

static void freeCliquehash ( CLIQUEHASH ** cliquehash )

static

frees the table for storing cliques and all inserted cliques

Parameters

cliquehash pointer to the clique hash table

Definition at line 216 of file tclique_branch.c.

References BMSfreeMemory, BMSfreeMemoryArray, clearCliquehash(), and NULL.

Referenced by tcliqueMaxClique().

static void ensureCliquehashSize	(	CLIQUEHASH *	cliquehash,
		int	num
	)

static

ensures, that the clique hash table is able to store at least the given number of cliques

Parameters

cliquehash	clique hash table
num	minimal number of cliques to store

Definition at line 233 of file tclique_branch.c.

References ALLOC_ABORT, BMSreallocMemoryArray, and NULL.

Referenced by insertClique().

static TCLIQUE_Bool inCliquehash	(	CLIQUEHASH *	cliquehash,
		CLIQUE *	clique,
		int *	insertpos
	)

static

searches the given clique in the clique hash table and returns whether it (or a stronger clique) exists

Parameters

cliquehash	clique hash table
clique	clique to search in the table
insertpos	position where the clique should be inserted in the table

Definition at line 280 of file tclique_branch.c.

References compSubcliques(), FALSE, NULL, and TRUE.

Referenced by newSolution().

static void insertClique	(	CLIQUEHASH *	cliquehash,
		CLIQUE *	clique,
		int	insertpos
	)

static

inserts clique into clique hash table

Parameters

cliquehash	clique hash table
clique	clique to search in the table
insertpos	position to insert clique into table (returned by inCliquehash())

Definition at line 329 of file tclique_branch.c.

References checkCliquehash(), debug, ensureCliquehashSize(), and NULL.

Referenced by newSolution().

static void extendCliqueZeroWeight	(	TCLIQUE_SELECTADJNODES((*selectadjnodes))	,
		TCLIQUE_GRAPH *	tcliquegraph,
		int *	buffer,
		int *	Vzero,
		int	nVzero,
		int	maxnzeroextensions,
		int *	curcliquenodes,
		int *	ncurcliquenodes
	)

static

extends given clique by additional zero-weight nodes of the given node set

Parameters

tcliquegraph	pointer to graph data structure
buffer	buffer of size nnodes
Vzero	zero weighted nodes
nVzero	number of zero weighted nodes
maxnzeroextensions	maximal number of zero-valued variables extending the clique
curcliquenodes	nodes of the clique
ncurcliquenodes	pointer to store number of nodes in the clique

Definition at line 365 of file tclique_branch.c.

References BMScopyMemoryArray, debugMessage, and NULL.

Referenced by newSolution().

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

calls user callback after a new solution was found, that is better than the current incumbent; the callback decides, whether this solution should be accepted as new incumbent, and whether the solution process should be stopped

Parameters

tcliquegraph	pointer to graph data structure
tcliquedata	user data to pass to user callback function
cliquehash	clique hash table
buffer	buffer of size nnodes
Vzero	zero weighted nodes
nVzero	number of zero weighted nodes
maxnzeroextensions	maximal number of zero-valued variables extending the clique
curcliquenodes	nodes of the new clique
ncurcliquenodes	number of nodes in the new clique
curcliqueweight	weight of the new clique
maxcliquenodes	pointer to store nodes of the maximum weight clique
nmaxcliquenodes	pointer to store number of nodes in the maximum weight clique
maxcliqueweight	pointer to store weight of the maximum weight clique
stopsolving	pointer to store whether the solving should be stopped

Definition at line 426 of file tclique_branch.c.

References BMScopyMemoryArray, clearCliquehash(), createClique(), debugMessage, debugPrintf, extendCliqueZeroWeight(), FALSE, freeClique(), inCliquehash(), insertClique(), NULL, TCLIQUE_Bool, and TRUE.

Referenced by branch().

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
	)

static

tries to find a clique, if V has only one or two nodes

Parameters

tcliquegraph	pointer to graph data structure
V	non-zero weighted nodes for branching
nV	number of non-zero weighted nodes for branching
apbound	apriori bound of nodes for branching
tmpcliquenodes	buffer for storing the temporary clique
ntmpcliquenodes	pointer to store number of nodes of the temporary clique
tmpcliqueweight	pointer to store weight of the temporary clique

Definition at line 532 of file tclique_branch.c.

References NULL.

Referenced by boundSubgraph().

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

calculates upper bound on remaining subgraph, and heuristically generates a clique

Parameters

tcliquegraph	pointer to graph data structure
mem	block memory
buffer	buffer of size nnodes
V	non-zero weighted nodes for branching
nV	number of non-zero weighted nodes for branching
gsd	neighbour color information of all nodes
iscolored	coloring status of all nodes
apbound	apriori bound of nodes for branching
tmpcliquenodes	buffer for storing the temporary clique
ntmpcliquenodes	pointer to store number of nodes of the temporary clique
tmpcliqueweight	pointer to store weight of the temporary clique

Definition at line 600 of file tclique_branch.c.

References NULL, reduced(), and tcliqueColoring().

Referenced by branch().

static int getMaxApBoundIndex	(	int	nV,
		TCLIQUE_WEIGHT *	apbound
	)

static

gets the index of the node of V with the maximum apriori bound; returns -1, if no node exists

Parameters

nV	number of nodes of V
apbound	apriori bound of nodes of V

Definition at line 638 of file tclique_branch.c.

References NULL.

Referenced by branch().

static int getMaxApBoundIndexNotMaxWeight	(	int *	V,
		int	nV,
		const TCLIQUE_WEIGHT *	apbound,
		const TCLIQUE_WEIGHT *	weights,
		TCLIQUE_WEIGHT	maxweight
	)

static

gets the index of the node of V with the maximum apriori bound, but ignores nodes with weights larger than the given maximal weight; returns -1 if no node with weight smaller or equal than maxweight is found

Parameters

V	non-zero weighted nodes for branching
nV	number of non-zero weighted nodes for branching
apbound	apriori bound of nodes of V
weights	weights of nodes
maxweight	maximal weight of node to be candidate for selection

Definition at line 670 of file tclique_branch.c.

References NULL.

Referenced by branch().

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

branches the searching tree, branching nodes are selected in decreasing order of their apriori bound, returns the level to which we should backtrack, or INT_MAX for continuing normally

Parameters

tcliquegraph	pointer to graph data structure
tcliquedata	user data to pass to user callback function
mem	block memory
cliquehash	clique hash table
buffer	buffer of size nnodes
level	level of b&b tree
V	non-zero weighted nodes for branching
nV	number of non-zero weighted nodes for branching
Vzero	zero weighted nodes
nVzero	number of zero weighted nodes
gsd	neighbour color information of all nodes
iscolored	coloring status of all nodes
K	nodes from the b&b tree
weightK	weight of the nodes from b&b tree
maxcliquenodes	pointer to store nodes of the maximum weight clique
nmaxcliquenodes	pointer to store number of nodes in the maximum weight clique
maxcliqueweight	pointer to store weight of the maximum weight clique
curcliquenodes	pointer to store nodes of currenct clique
ncurcliquenodes	pointer to store number of nodes in current clique
curcliqueweight	pointer to store weight of current clique
tmpcliquenodes	buffer for storing the temporary clique
maxfirstnodeweight	maximum weight of branching nodes in level 0; 0 if not used (for cliques with at least one fractional node)
ntreenodes	pointer to store number of nodes of b&b tree
maxntreenodes	maximal number of nodes of b&b tree
backtrackfreq	frequency to backtrack to first level of tree (0: no premature backtracking)
maxnzeroextensions	maximal number of zero-valued variables extending the clique
fixednode	node that is forced to be in the clique, or -1; must have positive weight
status	pointer to store the status of the solving call

Definition at line 706 of file tclique_branch.c.

References ALLOC_ABORT, BMSallocMemoryArray, BMSclearMemoryArray, BMSfreeMemoryArray, BMSgetChunkMemoryUsed, BMSgetMemoryUsed, boundSubgraph(), debugMessage, debugPrintf, FALSE, getMaxApBoundIndex(), getMaxApBoundIndexNotMaxWeight(), newSolution(), NULL, TCLIQUE_Bool, TCLIQUE_NODELIMIT, and TRUE.

Referenced by tcliqueMaxClique().

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
	)

finds maximum weight clique

Parameters

tcliquegraph	pointer to graph data structure that is passed to graph callbacks
tcliquedata	user data to pass to new solution callback function
maxcliquenodes	pointer to store nodes of the maximum weight clique
nmaxcliquenodes	pointer to store number of nodes in the maximum weight clique
maxcliqueweight	pointer to store weight of the maximum weight clique
maxfirstnodeweight	maximum weight of branching nodes in level 0; 0 if not used for cliques with at least one fractional node)
minweight	lower bound for weight of generated cliques
maxntreenodes	maximal number of nodes of b&b tree
backtrackfreq	frequency to backtrack to first level of tree (0: no premature backtracking)
maxnzeroextensions	maximal number of zero-valued variables extending the clique
fixednode	node that is forced to be in the clique, or -1; must have positive weight
ntreenodes	pointer to store the number of used tree nodes (or NULL)
status	pointer to store the status of the solving call

Definition at line 998 of file tclique_branch.c.

References ALLOC_ABORT, BMSallocMemoryArray, BMScreateChunkMemory, BMSdestroyChunkMemory, BMSfreeMemoryArray, branch(), CHUNK_SIZE, CLIQUEHASH_INITSIZE, createCliquehash(), debugMessage, freeCliquehash(), NULL, TCLIQUE_Bool, TCLIQUE_OPTIMAL, and TCLIQUE_USERABORT.

Referenced by computeMinDistance(), findCumulativeConss(), and separateCuts().

SCIP

Detailed Description

Macros

Typedefs

Functions

Macro Definition Documentation

Typedef Documentation

Function Documentation