Scippy

SCIP

Solving Constraint Integer Programs

tclique_branch.c File Reference

Detailed Description

branch and bound part of algorithm for maximum cliques

Author
Tobias Achterberg
Ralf Borndoerfer
Zoltan Kormos
Kati Wolter

Definition in file tclique_branch.c.

#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
cliquepointer to the clique
nodesnodes of the clique
nnodesnumber 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
cliquepointer 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
clique1first clique to compare
clique2second 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
cliquehashclique 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
cliquehashpointer to store the clique hash table
tablesizeinitial 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
cliquehashclique 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
cliquehashpointer 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
cliquehashclique hash table
numminimal number of cliques to store

Definition at line 233 of file tclique_branch.c.

References ALLOC_ABORT, BMSreallocMemoryArray, debugMessage, debugPrintf, 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
cliquehashclique hash table
cliqueclique to search in the table
insertposposition 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
cliquehashclique hash table
cliqueclique to search in the table
insertposposition 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
tcliquegraphpointer to graph data structure
bufferbuffer of size nnodes
Vzerozero weighted nodes
nVzeronumber of zero weighted nodes
maxnzeroextensionsmaximal number of zero-valued variables extending the clique
curcliquenodesnodes of the clique
ncurcliquenodespointer 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
tcliquegraphpointer to graph data structure
tcliquedatauser data to pass to user callback function
cliquehashclique hash table
bufferbuffer of size nnodes
Vzerozero weighted nodes
nVzeronumber of zero weighted nodes
maxnzeroextensionsmaximal number of zero-valued variables extending the clique
curcliquenodesnodes of the new clique
ncurcliquenodesnumber of nodes in the new clique
curcliqueweightweight of the new clique
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
stopsolvingpointer to store whether the solving should be stopped

Definition at line 427 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
tcliquegraphpointer to graph data structure
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching
apboundapriori bound of nodes for branching
tmpcliquenodesbuffer for storing the temporary clique
ntmpcliquenodespointer to store number of nodes of the temporary clique
tmpcliqueweightpointer to store weight of the temporary clique

Definition at line 533 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
tcliquegraphpointer to graph data structure
memblock memory
bufferbuffer of size nnodes
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching
gsdneighbour color information of all nodes
iscoloredcoloring status of all nodes
apboundapriori bound of nodes for branching
tmpcliquenodesbuffer for storing the temporary clique
ntmpcliquenodespointer to store number of nodes of the temporary clique
tmpcliqueweightpointer to store weight of the temporary clique

Definition at line 601 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
nVnumber of nodes of V
apboundapriori bound of nodes of V

Definition at line 639 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
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching
apboundapriori bound of nodes of V
weightsweights of nodes
maxweightmaximal weight of node to be candidate for selection

Definition at line 672 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
tcliquegraphpointer to graph data structure
tcliquedatauser data to pass to user callback function
memblock memory
cliquehashclique hash table
bufferbuffer of size nnodes
levellevel of b&b tree
Vnon-zero weighted nodes for branching
nVnumber of non-zero weighted nodes for branching
Vzerozero weighted nodes
nVzeronumber of zero weighted nodes
gsdneighbour color information of all nodes
iscoloredcoloring status of all nodes
Knodes from the b&b tree
weightKweight of the nodes from b&b tree
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
curcliquenodespointer to store nodes of currenct clique
ncurcliquenodespointer to store number of nodes in current clique
curcliqueweightpointer to store weight of current clique
tmpcliquenodesbuffer for storing the temporary clique
maxfirstnodeweightmaximum weight of branching nodes in level 0; 0 if not used (for cliques with at least one fractional node)
ntreenodespointer to store number of nodes of b&b tree
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
statuspointer to store the status of the solving call

Definition at line 708 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
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 1000 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(), searchEcAggrWithCliques(), sepaBoundInequalitiesFromGraph(), and separateCuts().