Detailed Description

tclique user interface

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

Definition in file tclique.h.

#include "tclique/tclique_def.h"

Macros
#define	TCLIQUE_Bool unsigned int

#define	TRUE 1

#define	FALSE 0

#define	TCLIQUE_NEWSOL(x)

#define	TCLIQUE_GETNNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph)

#define	TCLIQUE_GETWEIGHTS(x) const TCLIQUE_WEIGHT* x (TCLIQUE_GRAPH* tcliquegraph)

#define	TCLIQUE_ISEDGE(x) TCLIQUE_Bool x (TCLIQUE_GRAPH* tcliquegraph, int node1, int node2)

#define	TCLIQUE_SELECTADJNODES(x) int x (TCLIQUE_GRAPH* tcliquegraph, int node, int* nodes, int nnodes, int* adjnodes)

Typedefs
typedef int	TCLIQUE_WEIGHT

typedef struct TCLIQUE_Graph	TCLIQUE_GRAPH

typedef struct TCLIQUE_Data	TCLIQUE_DATA

typedef enum TCLIQUE_Status	TCLIQUE_STATUS

Enumerations
enum	TCLIQUE_Status { TCLIQUE_ERROR = 0, TCLIQUE_NODELIMIT = 1, TCLIQUE_USERABORT = 2, TCLIQUE_OPTIMAL = 3 }

Functions
	TCLIQUE_GETNNODES (tcliqueGetNNodes)

	TCLIQUE_GETWEIGHTS (tcliqueGetWeights)

	TCLIQUE_ISEDGE (tcliqueIsEdge)

	TCLIQUE_SELECTADJNODES (tcliqueSelectAdjnodes)

TCLIQUE_Bool	tcliqueCreate (TCLIQUE_GRAPH **tcliquegraph)

void	tcliqueFree (TCLIQUE_GRAPH **tcliquegraph)

TCLIQUE_Bool	tcliqueAddNode (TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)

void	tcliqueChangeWeight (TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)

TCLIQUE_Bool	tcliqueAddEdge (TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)

TCLIQUE_Bool	tcliqueFlush (TCLIQUE_GRAPH *tcliquegraph)

TCLIQUE_Bool	tcliqueLoadFile (TCLIQUE_GRAPH *tcliquegraph, const char filename, double scaleval, char *probname, int sizeofprobname)

TCLIQUE_Bool	tcliqueSaveFile (TCLIQUE_GRAPH tcliquegraph, const char filename, double scaleval, const char *probname)

int	tcliqueGetNEdges (TCLIQUE_GRAPH *tcliquegraph)

int *	tcliqueGetDegrees (TCLIQUE_GRAPH *tcliquegraph)

int *	tcliqueGetAdjnodes (TCLIQUE_GRAPH *tcliquegraph)

int *	tcliqueGetFirstAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node)

int *	tcliqueGetLastAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node)

void	tcliquePrintGraph (TCLIQUE_GRAPH *tcliquegraph)

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

◆ TCLIQUE_Bool

#define TCLIQUE_Bool unsigned int

type used for boolean values

Definition at line 53 of file tclique.h.

Referenced by branch(), compSubcliques(), newSolution(), tcliqueColoring(), and tcliqueMaxClique().

◆ TRUE

#define TRUE 1

boolean value TRUE

Definition at line 56 of file tclique.h.

◆ FALSE

#define FALSE 0

boolean value FALSE

Definition at line 57 of file tclique.h.

◆ TCLIQUE_NEWSOL

#define TCLIQUE_NEWSOL ( x )

Value:

void x (TCLIQUE_DATA* tcliquedata, int* cliquenodes, int ncliquenodes, \

TCLIQUE_WEIGHT cliqueweight, TCLIQUE_WEIGHT* minweight, TCLIQUE_Bool* acceptsol, TCLIQUE_Bool* stopsolving)

x

SCIP_VAR ** x

Definition: circlepacking.c:63

TCLIQUE_Data

Definition: cons_sos1.c:241

TCLIQUE_Bool

#define TCLIQUE_Bool

Definition: tclique.h:53

TCLIQUE_WEIGHT

int TCLIQUE_WEIGHT

Definition: tclique.h:48

user callback method which is called whenever a feasible clique was found input:

tcliquedata : user data given to tcliqueMaxClique()
cliquenodes : array with nodes of the clique
ncliquenodes : number of nodes in the clique
cliqueweight : weight of the clique output:
minweight : new minimal weight for feasible cliques
acceptsol : setting TRUE makes clique the new best clique, and updates minweight
stopsolving : setting TRUE aborts the search for cliques

Definition at line 88 of file tclique.h.

◆ TCLIQUE_GETNNODES

#define TCLIQUE_GETNNODES ( x ) int x (TCLIQUE_GRAPH* tcliquegraph)

user callback method to get number of nodes in the graph input:

tcliquegraph : user defined graph data structure given to tcliqueMaxClique() returns: number of nodes in the graph

Definition at line 97 of file tclique.h.

◆ TCLIQUE_GETWEIGHTS

#define TCLIQUE_GETWEIGHTS ( x ) const TCLIQUE_WEIGHT* x (TCLIQUE_GRAPH* tcliquegraph)

user callback method to get weights of nodes in the graph input:

tcliquegraph : user defined graph data structure given to tcliqueMaxClique() returns: array of node weights (of length at least equal to the number of nodes in the graph)

Definition at line 105 of file tclique.h.

◆ TCLIQUE_ISEDGE

#define TCLIQUE_ISEDGE ( x ) TCLIQUE_Bool x (TCLIQUE_GRAPH* tcliquegraph, int node1, int node2)

user callback method to return whether the edge (node1, node2) is in the graph input:

tcliquegraph : user defined graph data structure given to tcliqueMaxClique()
node1 : start node of edge (tail)
node2 : end node of edge (head) returns: TRUE if edge is in the graph, FALSE otherwise

Definition at line 115 of file tclique.h.

◆ TCLIQUE_SELECTADJNODES

#define TCLIQUE_SELECTADJNODES ( x ) int x (TCLIQUE_GRAPH* tcliquegraph, int node, int* nodes, int nnodes, int* adjnodes)

user callback method to select all nodes from a given set of nodes which are adjacent to a given node input:

tcliquegraph : user defined graph data structure given to tcliqueMaxClique()
node : node to select adjacent nodes from
nodes : array of nodes to select nodes from
nnodes : number of nodes in 'nodes' array
adjnodes : pointer to memory to store the resulting nodes 'adjnodes' and 'nodes' may point to the same memory location output:
adjnodes : array of nodes that are contained in 'nodes' and that are adjacent to 'node' returns: number of nodes in 'adjnodes'

Definition at line 130 of file tclique.h.

Typedef Documentation

◆ TCLIQUE_WEIGHT

typedef int TCLIQUE_WEIGHT

type used for node weights in the graph

Definition at line 48 of file tclique.h.

◆ TCLIQUE_GRAPH

typedef struct TCLIQUE_Graph TCLIQUE_GRAPH

user defined structure for storing the graph, passed to graph callbacks

Definition at line 49 of file tclique.h.

◆ TCLIQUE_DATA

typedef struct TCLIQUE_Data TCLIQUE_DATA

user defined data to pass to new solution callback method

Definition at line 50 of file tclique.h.

◆ TCLIQUE_STATUS

typedef enum TCLIQUE_Status TCLIQUE_STATUS

Definition at line 68 of file tclique.h.

Enumeration Type Documentation

◆ TCLIQUE_Status

enum TCLIQUE_Status

return status of the TCLIQUE algorithm

Enumerator
TCLIQUE_ERROR	an error occurred
TCLIQUE_NODELIMIT	the node limit was reached
TCLIQUE_USERABORT	the user call back function aborted the solving process
TCLIQUE_OPTIMAL	the optimal solution was found

Definition at line 61 of file tclique.h.

Function Documentation

◆ TCLIQUE_GETNNODES()

TCLIQUE_GETNNODES ( tcliqueGetNNodes )

gets number of nodes in the graph

Definition at line 76 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_GETWEIGHTS()

TCLIQUE_GETWEIGHTS ( tcliqueGetWeights )

gets weight of nodes in the graph

Definition at line 84 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_ISEDGE()

TCLIQUE_ISEDGE ( tcliqueIsEdge )

returns, whether the edge (node1, node2) is in the graph

Definition at line 92 of file tclique_graph.c.

References FALSE, nnodes, NULL, tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and TRUE.

◆ TCLIQUE_SELECTADJNODES()

TCLIQUE_SELECTADJNODES ( tcliqueSelectAdjnodes )

selects all nodes from a given set of nodes which are adjacent to a given node and returns the number of selected nodes

Definition at line 135 of file tclique_graph.c.

References nnodes, NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

◆ tcliqueCreate()

TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH ** tcliquegraph )

creates graph data structure

Parameters

tcliquegraph pointer to store graph data structure

Definition at line 185 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemory, NULL, and TRUE.

Referenced by createConsStoreGraphAtRoot(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIPcreateProbColoring(), and tcliqueLoadFile().

◆ tcliqueFree()

void tcliqueFree ( TCLIQUE_GRAPH ** tcliquegraph )

frees graph data structure

Parameters

tcliquegraph pointer to graph data structure

Definition at line 211 of file tclique_graph.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.

Referenced by doSeachEcAggr(), preprocessGraph(), SCIP_DECL_CONSDELETE(), SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().

◆ tcliqueAddNode()

TCLIQUE_Bool tcliqueAddNode	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node,
		TCLIQUE_WEIGHT	weight
	)

adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0)

Parameters

tcliquegraph	graph data structure
node	node number to add
weight	weight of node to add

Definition at line 340 of file tclique_graph.c.

References FALSE, MAX, tcliqueEnsureSizeNodes(), and TRUE.

Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().

◆ tcliqueChangeWeight()

void tcliqueChangeWeight	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node,
		TCLIQUE_WEIGHT	weight
	)

changes weight of node in graph data structure

Parameters

tcliquegraph	graph data structure
node	node to set new weight
weight	new weight of node (allready scaled)

Definition at line 362 of file tclique_graph.c.

Referenced by preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), and updateWeightsTCliquegraph().

◆ tcliqueAddEdge()

TCLIQUE_Bool tcliqueAddEdge	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node1,
		int	node2
	)

adds edge (node1, node2) to graph data structure (node1 and node2 have to be contained in graph data structure)

New edges are cached, s.t. the graph data structures are not correct until a call to tcliqueFlush(); you have to make sure, that no double edges are inserted.

Parameters

tcliquegraph	graph data structure
node1	start node of edge to add
node2	end node of edge to add

Definition at line 380 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemoryArray, BMSclearMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeCachedEdges(), and TRUE.

Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().

◆ tcliqueFlush()

TCLIQUE_Bool tcliqueFlush ( TCLIQUE_GRAPH * tcliquegraph )

inserts all cached edges into the data structures

Parameters

tcliquegraph graph data structure

Definition at line 417 of file tclique_graph.c.

References BMSfreeMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeEdges(), and TRUE.

Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().

◆ tcliqueLoadFile()

TCLIQUE_Bool tcliqueLoadFile	(	TCLIQUE_GRAPH **	tcliquegraph,
		const char *	filename,
		double	scaleval,
		char *	probname,
		int	sizeofprobname
	)

loads graph data structure from file

Parameters

tcliquegraph	pointer to store graph data structure
filename	name of file with graph data
scaleval	value to scale weights (only integral part of scaled weights is considered)
probname	buffer to store the name of the problem
sizeofprobname	size of buffer to store the name of the problem

Definition at line 552 of file tclique_graph.c.

References BMSallocMemoryArray, FALSE, infoMessage, NULL, tcliqueCreate(), and TRUE.

◆ tcliqueSaveFile()

TCLIQUE_Bool tcliqueSaveFile	(	TCLIQUE_GRAPH *	tcliquegraph,
		const char *	filename,
		double	scaleval,
		const char *	probname
	)

saves graph data structure to file

Parameters

tcliquegraph	graph data structure
filename	name of file to create
scaleval	value to unscale weights with
probname	name of the problem

Definition at line 729 of file tclique_graph.c.

References FALSE, infoMessage, NULL, and TRUE.

◆ tcliqueGetNEdges()

int tcliqueGetNEdges ( TCLIQUE_GRAPH * tcliquegraph )

gets number of edges in the graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 773 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().

◆ tcliqueGetDegrees()

int* tcliqueGetDegrees ( TCLIQUE_GRAPH * tcliquegraph )

gets degree of nodes in graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 783 of file tclique_graph.c.

References NULL.

Referenced by greedyStableSet(), preprocessGraph(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().

◆ tcliqueGetAdjnodes()

int* tcliqueGetAdjnodes ( TCLIQUE_GRAPH * tcliquegraph )

gets adjacent nodes of edges in graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 794 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

◆ tcliqueGetFirstAdjedge()

int* tcliqueGetFirstAdjedge	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node
	)

gets pointer to first adjacent edge of given node in graph

Parameters

tcliquegraph	pointer to graph data structure
node	given node

Definition at line 805 of file tclique_graph.c.

References nnodes, NULL, tcliqueGetAdjnodes(), and tcliqueGetNEdges().

Referenced by COLORprobGetComplementaryGraph(), getNViolatedEdges(), preprocessGraph(), runTabuCol(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIP_DECL_READERWRITE(), TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

◆ tcliqueGetLastAdjedge()

int* tcliqueGetLastAdjedge	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node
	)

gets pointer to last adjacent edge of given node in graph

Parameters

tcliquegraph	pointer to graph data structure
node	given node

Definition at line 829 of file tclique_graph.c.

References nnodes, NULL, tcliqueGetAdjnodes(), tcliqueGetDegrees(), and tcliqueGetNEdges().

Referenced by COLORprobGetComplementaryGraph(), getNViolatedEdges(), preprocessGraph(), runTabuCol(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIP_DECL_READERWRITE(), TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

◆ tcliquePrintGraph()

void tcliquePrintGraph ( TCLIQUE_GRAPH * tcliquegraph )

prints graph data structure

Parameters

tcliquegraph pointer to graph data structure

Definition at line 861 of file tclique_graph.c.

References infoMessage, NULL, tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliqueGetNEdges().

◆ 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 1010 of file tclique_branch.c.

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

Referenced by computeMinDistance(), findCumulativeConss(), preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), sepaBoundInequalitiesFromGraph(), and separateCuts().

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ TCLIQUE_Bool

◆ TRUE

◆ FALSE

◆ TCLIQUE_NEWSOL

◆ TCLIQUE_GETNNODES

◆ TCLIQUE_GETWEIGHTS

◆ TCLIQUE_ISEDGE

◆ TCLIQUE_SELECTADJNODES

Typedef Documentation

◆ TCLIQUE_WEIGHT

◆ TCLIQUE_GRAPH

◆ TCLIQUE_DATA

◆ TCLIQUE_STATUS

Enumeration Type Documentation

◆ TCLIQUE_Status

Function Documentation

◆ TCLIQUE_GETNNODES()

◆ TCLIQUE_GETWEIGHTS()

◆ TCLIQUE_ISEDGE()

◆ TCLIQUE_SELECTADJNODES()

◆ tcliqueCreate()

◆ tcliqueFree()

◆ tcliqueAddNode()

◆ tcliqueChangeWeight()

◆ tcliqueAddEdge()

◆ tcliqueFlush()

◆ tcliqueLoadFile()

◆ tcliqueSaveFile()

◆ tcliqueGetNEdges()

◆ tcliqueGetDegrees()

◆ tcliqueGetAdjnodes()

◆ tcliqueGetFirstAdjedge()

◆ tcliqueGetLastAdjedge()

◆ tcliquePrintGraph()

◆ tcliqueMaxClique()