Scippy

SCIP

Solving Constraint Integer Programs

tclique.h File Reference

Detailed Description

tclique user interface

Author
Tobias Achterberg
Ralf Borndoerfer
Zoltan Kormos
Kati Wolter

Definition in file tclique.h.

Go to the source code of this file.

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 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)
SCIP_VAR ** x
Definition: circlepacking.c:54
#define TCLIQUE_Bool
Definition: tclique.h:44
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

Definition at line 59 of file tclique.h.

Enumeration Type Documentation

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

TCLIQUE_GETNNODES ( tcliqueGetNNodes  )

gets number of nodes in the graph

Definition at line 67 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_GETWEIGHTS()

TCLIQUE_GETWEIGHTS ( tcliqueGetWeights  )

gets weight of nodes in the graph

Definition at line 75 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 83 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 126 of file tclique_graph.c.

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

◆ tcliqueCreate()

TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH **  tcliquegraph)

creates graph data structure

Parameters
tcliquegraphpointer 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()

void tcliqueFree ( TCLIQUE_GRAPH **  tcliquegraph)

frees graph data structure

Parameters
tcliquegraphpointer 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()

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
tcliquegraphgraph data structure
nodenode number to add
weightweight 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()

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

changes weight of node in graph data structure

Parameters
tcliquegraphgraph data structure
nodenode to set new weight
weightnew weight of node (allready scaled)

Definition at line 353 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
tcliquegraphgraph data structure
node1start node of edge to add
node2end 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()

TCLIQUE_Bool tcliqueFlush ( TCLIQUE_GRAPH tcliquegraph)

inserts all cached edges into the data structures

Parameters
tcliquegraphgraph 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()

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

loads graph data structure from file

Parameters
tcliquegraphpointer to store graph data structure
filenamename of file with graph data
scalevalvalue to scale weights (only integral part of scaled weights is considered)
probnamebuffer to store the name of the problem
sizeofprobnamesize of buffer to store the name of the problem

Definition at line 543 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
tcliquegraphgraph data structure
filenamename of file to create
scalevalvalue to unscale weights with
probnamename of the problem

Definition at line 716 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
tcliquegraphpointer to graph data structure

Definition at line 760 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
tcliquegraphpointer to graph data structure

Definition at line 770 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
tcliquegraphpointer to graph data structure

Definition at line 781 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
tcliquegraphpointer to graph data structure
nodegiven node

Definition at line 792 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
tcliquegraphpointer to graph data structure
nodegiven node

Definition at line 816 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
tcliquegraphpointer to graph data structure

Definition at line 848 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
tcliquegraphpointer to graph data structure that is passed to graph callbacks
tcliquedatauser data to pass to new solution callback function
maxcliquenodespointer to store nodes of the maximum weight clique
nmaxcliquenodespointer to store number of nodes in the maximum weight clique
maxcliqueweightpointer to store weight of the maximum weight clique
maxfirstnodeweightmaximum weight of branching nodes in level 0; 0 if not used for cliques with at least one fractional node)
minweightlower bound for weight of generated cliques
maxntreenodesmaximal number of nodes of b&b tree
backtrackfreqfrequency to backtrack to first level of tree (0: no premature backtracking)
maxnzeroextensionsmaximal number of zero-valued variables extending the clique
fixednodenode that is forced to be in the clique, or -1; must have positive weight
ntreenodespointer to store the number of used tree nodes (or NULL)
statuspointer 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().