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
SCIP_EXPORT	TCLIQUE_GETNNODES (tcliqueGetNNodes)

SCIP_EXPORT	TCLIQUE_GETWEIGHTS (tcliqueGetWeights)

SCIP_EXPORT	TCLIQUE_ISEDGE (tcliqueIsEdge)

SCIP_EXPORT	TCLIQUE_SELECTADJNODES (tcliqueSelectAdjnodes)

SCIP_EXPORT TCLIQUE_Bool	tcliqueCreate (TCLIQUE_GRAPH **tcliquegraph)

SCIP_EXPORT void	tcliqueFree (TCLIQUE_GRAPH **tcliquegraph)

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

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

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

SCIP_EXPORT TCLIQUE_Bool	tcliqueFlush (TCLIQUE_GRAPH *tcliquegraph)

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

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

SCIP_EXPORT int	tcliqueGetNEdges (TCLIQUE_GRAPH *tcliquegraph)

SCIP_EXPORT int *	tcliqueGetDegrees (TCLIQUE_GRAPH *tcliquegraph)

SCIP_EXPORT int *	tcliqueGetAdjnodes (TCLIQUE_GRAPH *tcliquegraph)

SCIP_EXPORT int *	tcliqueGetFirstAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node)

SCIP_EXPORT int *	tcliqueGetLastAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node)

SCIP_EXPORT void	tcliquePrintGraph (TCLIQUE_GRAPH *tcliquegraph)

SCIP_EXPORT 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 44 of file tclique.h.

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

◆ TRUE

#define TRUE 1

boolean value TRUE

Definition at line 47 of file tclique.h.

◆ FALSE

#define FALSE 0

boolean value FALSE

Definition at line 48 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:54

TCLIQUE_Data

Definition: cons_sos1.c:233

TCLIQUE_Bool

#define TCLIQUE_Bool

Definition: tclique.h:44

TCLIQUE_WEIGHT

int TCLIQUE_WEIGHT

Definition: tclique.h:39

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 79 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 88 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 96 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 106 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 121 of file tclique.h.

Typedef Documentation

◆ TCLIQUE_WEIGHT

typedef int TCLIQUE_WEIGHT

type used for node weights in the graph

Definition at line 39 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 40 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 41 of file tclique.h.

◆ TCLIQUE_STATUS

typedef enum TCLIQUE_Status TCLIQUE_STATUS

Definition at line 59 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 52 of file tclique.h.

Function Documentation

◆ TCLIQUE_GETNNODES()

SCIP_EXPORT TCLIQUE_GETNNODES ( tcliqueGetNNodes )

gets number of nodes in the graph

Definition at line 67 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_GETWEIGHTS()

SCIP_EXPORT TCLIQUE_GETWEIGHTS ( tcliqueGetWeights )

gets weight of nodes in the graph

Definition at line 75 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_ISEDGE()

SCIP_EXPORT TCLIQUE_ISEDGE ( tcliqueIsEdge )

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

Definition at line 83 of file tclique_graph.c.

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

◆ TCLIQUE_SELECTADJNODES()

SCIP_EXPORT 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 126 of file tclique_graph.c.

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

◆ tcliqueCreate()

SCIP_EXPORT TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH ** tcliquegraph )

creates graph data structure

Parameters

tcliquegraph pointer to store graph data structure

Definition at line 176 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()

SCIP_EXPORT void tcliqueFree ( TCLIQUE_GRAPH ** tcliquegraph )

frees graph data structure

Parameters

tcliquegraph pointer to graph data structure

Definition at line 202 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()

SCIP_EXPORT 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 331 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()

SCIP_EXPORT 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 353 of file tclique_graph.c.

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

◆ tcliqueAddEdge()

SCIP_EXPORT 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 371 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()

SCIP_EXPORT TCLIQUE_Bool tcliqueFlush ( TCLIQUE_GRAPH * tcliquegraph )

inserts all cached edges into the data structures

Parameters

tcliquegraph graph data structure

Definition at line 408 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()

SCIP_EXPORT 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 543 of file tclique_graph.c.

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

◆ tcliqueSaveFile()

SCIP_EXPORT 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 732 of file tclique_graph.c.

References FALSE, infoMessage, NULL, and TRUE.

◆ tcliqueGetNEdges()

SCIP_EXPORT int tcliqueGetNEdges ( TCLIQUE_GRAPH * tcliquegraph )

gets number of edges in the graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 776 of file tclique_graph.c.

References NULL.

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

◆ tcliqueGetDegrees()

SCIP_EXPORT int* tcliqueGetDegrees ( TCLIQUE_GRAPH * tcliquegraph )

gets degree of nodes in graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 786 of file tclique_graph.c.

References NULL.

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

◆ tcliqueGetAdjnodes()

SCIP_EXPORT int* tcliqueGetAdjnodes ( TCLIQUE_GRAPH * tcliquegraph )

gets adjacent nodes of edges in graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 797 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

◆ tcliqueGetFirstAdjedge()

SCIP_EXPORT 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 808 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()

SCIP_EXPORT 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 832 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()

SCIP_EXPORT void tcliquePrintGraph ( TCLIQUE_GRAPH * tcliquegraph )

prints graph data structure

Parameters

tcliquegraph pointer to graph data structure

Definition at line 864 of file tclique_graph.c.

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

◆ tcliqueMaxClique()

SCIP_EXPORT 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 1001 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()