Detailed Description

clique separator

Author: Kati Wolter; Tobias Achterberg

Definition in file sepa_clique.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_clique.h"
#include "tclique/tclique.h"
#include "scip/pub_misc.h"

Go to the source code of this file.

Macros
#define	SEPA_NAME "clique"

#define	SEPA_DESC "clique separator of stable set relaxation"

#define	SEPA_PRIORITY -5000

#define	SEPA_FREQ 0

#define	SEPA_MAXBOUNDDIST 0.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_SCALEVAL 1000.0

#define	DEFAULT_MAXTREENODES 10000

#define	DEFAULT_BACKTRACKFREQ 1000

#define	DEFAULT_MAXSEPACUTS 10

#define	DEFAULT_MAXZEROEXTENSIONS 1000

#define	DEFAULT_CLIQUETABLEMEM 20000.0

#define	DEFAULT_CLIQUEDENSITY 0.05

Functions
static SCIP_RETCODE	tcliquegraphCreate (SCIP scip, TCLIQUE_GRAPH *tcliquegraph)

static SCIP_RETCODE	tcliquegraphFree (SCIP scip, TCLIQUE_GRAPH *tcliquegraph)

static SCIP_RETCODE	tcliquegraphEnsureAdjnodesSize (SCIP scip, TCLIQUE_GRAPH tcliquegraph, int num)

static SCIP_RETCODE	tcliquegraphEnsureCliqueidsSize (SCIP scip, TCLIQUE_GRAPH tcliquegraph, int num)

static SCIP_RETCODE	tcliquegraphAddNode (SCIP scip, TCLIQUE_GRAPH tcliquegraph, SCIP_VAR var, SCIP_Bool value, int *nodeidx)

static SCIP_RETCODE	tcliquegraphAddCliqueVars (SCIP scip, TCLIQUE_GRAPH tcliquegraph, int *cliquegraphidx)

static SCIP_RETCODE	tcliquegraphAddImplicsVars (SCIP scip, TCLIQUE_GRAPH tcliquegraph, int *cliquegraphidx)

static SCIP_RETCODE	tcliquegraphAddImplicsCliqueVars (SCIP scip, TCLIQUE_GRAPH tcliquegraph, int *cliquegraphidx)

static SCIP_RETCODE	tcliquegraphAddImplics (SCIP scip, TCLIQUE_GRAPH tcliquegraph, int **cliquegraphidx)

static SCIP_RETCODE	tcliquegraphConstructCliqueTable (SCIP scip, TCLIQUE_GRAPH tcliquegraph, SCIP_Real cliquetablemem, SCIP_Real cliquedensity)

static SCIP_RETCODE	loadTcliquegraph (SCIP scip, SCIP_SEPADATA sepadata)

static void	updateTcliquegraph (SCIP scip, SCIP_SEPADATA sepadata)

static	TCLIQUE_GETNNODES (tcliqueGetnnodesClique)

static	TCLIQUE_GETWEIGHTS (tcliqueGetweightsClique)

static SCIP_Bool	nodesHaveCommonClique (TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)

static	TCLIQUE_ISEDGE (tcliqueIsedgeClique)

static	TCLIQUE_SELECTADJNODES (tcliqueSelectadjnodesClique)

static SCIP_RETCODE	newsolCliqueAddRow (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, int ncliquenodes, int cliquenodes, SCIP_Bool *cutoff)

static	TCLIQUE_NEWSOL (tcliqueNewsolClique)

static SCIP_RETCODE	separateCuts (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_RESULT result)

static	SCIP_DECL_SEPACOPY (sepaCopyClique)

static	SCIP_DECL_SEPAFREE (sepaFreeClique)

static	SCIP_DECL_SEPAEXITSOL (sepaExitsolClique)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpClique)

static	SCIP_DECL_SEPAEXECSOL (sepaExecsolClique)

SCIP_RETCODE	SCIPincludeSepaClique (SCIP *scip)

Macro Definition Documentation

#define SEPA_NAME "clique"

Definition at line 32 of file sepa_clique.c.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaClique().

#define SEPA_DESC "clique separator of stable set relaxation"

Definition at line 33 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define SEPA_PRIORITY -5000

Definition at line 34 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define SEPA_FREQ 0

Definition at line 35 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 36 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 37 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define SEPA_DELAY FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 38 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_SCALEVAL 1000.0

factor for scaling weights

Definition at line 40 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_MAXTREENODES 10000

maximal number of nodes in branch and bound tree (-1: no limit)

Definition at line 41 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_BACKTRACKFREQ 1000

frequency for premature backtracking up to tree level 1 (0: no backtracking)

Definition at line 42 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_MAXSEPACUTS 10

maximal number of clique cuts separated per separation round (-1: no limit)

Definition at line 43 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_MAXZEROEXTENSIONS 1000

maximal number of zero-valued variables extending the clique (-1: no limit)

Definition at line 44 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_CLIQUETABLEMEM 20000.0

maximal memory size of dense clique table (in kb)

Definition at line 45 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

#define DEFAULT_CLIQUEDENSITY 0.05

minimal density of cliques to use a dense clique table

Definition at line 46 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

Function Documentation

static SCIP_RETCODE tcliquegraphCreate	(	SCIP *	scip,
		TCLIQUE_GRAPH **	tcliquegraph
	)

static

creates an empty tclique graph data structure

Parameters

scip	SCIP data structure
tcliquegraph	pointer to tclique graph data

Definition at line 99 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and SCIPgetNBinVars().

Referenced by tcliquegraphAddNode().

static SCIP_RETCODE tcliquegraphFree	(	SCIP *	scip,
		TCLIQUE_GRAPH **	tcliquegraph
	)

static

frees the tclique graph data structure and releases all captured variables

Parameters

scip	SCIP data structure
tcliquegraph	pointer to tclique graph data

Definition at line 134 of file sepa_clique.c.

References Scip::cliquetable, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().

Referenced by loadTcliquegraph(), and SCIP_DECL_SEPAEXITSOL().

static SCIP_RETCODE tcliquegraphEnsureAdjnodesSize	(	SCIP *	scip,
		TCLIQUE_GRAPH *	tcliquegraph,
		int	num
	)

static

ensures that the adjnodes array can store at least num entries

Parameters

scip	SCIP data structure
tcliquegraph	tclique graph data
num	minimal number of adjacent nodes to be able to store in the array

Definition at line 165 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.

Referenced by tcliquegraphAddImplics().

static SCIP_RETCODE tcliquegraphEnsureCliqueidsSize	(	SCIP *	scip,
		TCLIQUE_GRAPH *	tcliquegraph,
		int	num
	)

static

ensures that the cliqueids array can store at least num entries

Parameters

scip	SCIP data structure
tcliquegraph	tclique graph data
num	minimal number of adjacent nodes to be able to store in the array

Definition at line 185 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.

Referenced by tcliquegraphAddNode().

static SCIP_RETCODE tcliquegraphAddNode	(	SCIP *	scip,
		TCLIQUE_GRAPH **	tcliquegraph,
		SCIP_VAR *	var,
		SCIP_Bool	value,
		int *	nodeidx
	)

static

adds a node to the tclique graph defined as a variable-value pair; adds all cliques to the cliqueids array the variable is contained in with the given value

Parameters

scip	SCIP data structure
tcliquegraph	pointer to tclique graph data
var	active binary problem variable
value	value of the variable in the node
nodeidx	pointer to store the index of the new node

Definition at line 207 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPcaptureVar(), SCIPcliqueGetId(), SCIPgetNBinVars(), SCIPgetNegatedVar(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetType(), SCIPvarIsActive(), tcliquegraphCreate(), and tcliquegraphEnsureCliqueidsSize().

Referenced by tcliquegraphAddCliqueVars(), tcliquegraphAddImplicsCliqueVars(), and tcliquegraphAddImplicsVars().

static SCIP_RETCODE tcliquegraphAddCliqueVars	(	SCIP *	scip,
		TCLIQUE_GRAPH **	tcliquegraph,
		int **	cliquegraphidx
	)

static

adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique

Parameters

scip	SCIP data structure
tcliquegraph	pointer to tclique graph data
cliquegraphidx	array to store tclique graph node index of variable/value pairs

Definition at line 277 of file sepa_clique.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetVars(), SCIPvarGetNCliques(), and tcliquegraphAddNode().

Referenced by loadTcliquegraph().

static SCIP_RETCODE tcliquegraphAddImplicsVars	(	SCIP *	scip,
		TCLIQUE_GRAPH **	tcliquegraph,
		int **	cliquegraphidx
	)

static

adds all variable/value pairs to the tclique graph that are contained in a 3-clique in the implication graph

Parameters

scip	SCIP data structure
tcliquegraph	pointer to tclique graph data
cliquegraphidx	array to store tclique graph node index of variable/value pairs

Definition at line 320 of file sepa_clique.c.

References NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPgetNBinVars(), SCIPgetVars(), SCIPisStopped(), SCIPsortedvecFindPtr(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetIndex(), SCIPvarGetNBinImpls(), SCIPvarGetProbindex(), SCIPvarGetType(), and tcliquegraphAddNode().

Referenced by loadTcliquegraph().

static SCIP_RETCODE tcliquegraphAddImplicsCliqueVars	(	SCIP *	scip,
		TCLIQUE_GRAPH **	tcliquegraph,
		int **	cliquegraphidx
	)

static

adds all variable/value pairs to the tclique graph that have implications to two variables of the same existing clique

Parameters

scip	SCIP data structure
tcliquegraph	pointer to tclique graph data
cliquegraphidx	array to store tclique graph node index of variable/value pairs

Definition at line 537 of file sepa_clique.c.

References FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPgetNBinVars(), SCIPgetVars(), SCIPisStopped(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetNBinImpls(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarsHaveCommonClique(), and tcliquegraphAddNode().

Referenced by loadTcliquegraph().

static SCIP_RETCODE tcliquegraphAddImplics	(	SCIP *	scip,
		TCLIQUE_GRAPH *	tcliquegraph,
		int **	cliquegraphidx
	)

static

adds all implications between nodes in the tclique graph to the tclique graph

Parameters

scip	SCIP data structure
tcliquegraph	tclique graph data
cliquegraphidx	array to store tclique graph node index of variable/value pairs

Definition at line 655 of file sepa_clique.c.

References FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetNVars(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetNBinImpls(), SCIPvarGetNegationVar(), SCIPvarGetProbindex(), SCIPvarGetProbvarBinary(), tcliquegraphEnsureAdjnodesSize(), and TRUE.

Referenced by loadTcliquegraph().

static SCIP_RETCODE tcliquegraphConstructCliqueTable	(	SCIP *	scip,
		TCLIQUE_GRAPH *	tcliquegraph,
		SCIP_Real	cliquetablemem,
		SCIP_Real	cliquedensity
	)

static

constructs dense clique incidence matrix

Parameters

scip	SCIP data structure
tcliquegraph	tclique graph data
cliquetablemem	maximal memory size of dense clique table (in kb)
cliquedensity	minimal density of cliques to store as dense table

Definition at line 747 of file sepa_clique.c.

References BMSclearMemoryArray, Scip::cliquetable, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetCliques(), SCIPgetNCliques(), SCIPisStopped(), SCIPvarGetNegatedVar(), and SCIPvarGetType().

Referenced by loadTcliquegraph().

static SCIP_RETCODE loadTcliquegraph	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

creates tclique data structure using the implication graph; only variables that are contained in a 3-clique are added as nodes to the clique graph

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 876 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPisStopped(), tcliquegraphAddCliqueVars(), tcliquegraphAddImplics(), tcliquegraphAddImplicsCliqueVars(), tcliquegraphAddImplicsVars(), tcliquegraphConstructCliqueTable(), and tcliquegraphFree().

Referenced by separateCuts().

static void updateTcliquegraph	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

updates the weights in the tclique graph data structure

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 933 of file sepa_clique.c.

References MAX, NULL, and SCIPfeasFloor().

Referenced by separateCuts().

static TCLIQUE_GETNNODES ( tcliqueGetnnodesClique )

static

gets number of nodes in the graph

Definition at line 964 of file sepa_clique.c.

References NULL.

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique )

static

gets weight of nodes in the graph

Definition at line 973 of file sepa_clique.c.

References NULL.

static SCIP_Bool nodesHaveCommonClique	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node1,
		int	node2
	)

static

returns whether the nodes are member of a common clique

Parameters

tcliquegraph	tclique graph data
node1	first node
node2	second node

Definition at line 982 of file sepa_clique.c.

References FALSE, NULL, and TRUE.

Referenced by TCLIQUE_ISEDGE(), and TCLIQUE_SELECTADJNODES().

static TCLIQUE_ISEDGE ( tcliqueIsedgeClique )

static

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

Definition at line 1044 of file sepa_clique.c.

References nodesHaveCommonClique(), NULL, and TRUE.

static TCLIQUE_SELECTADJNODES ( tcliqueSelectadjnodesClique )

static

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 1079 of file sepa_clique.c.

References nodesHaveCommonClique(), and NULL.

static SCIP_RETCODE newsolCliqueAddRow	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		int	ncliquenodes,
		int *	cliquenodes,
		SCIP_Bool *	cutoff
	)

static

basic code for new cliques (needed because of error handling)

Parameters

scip	SCIP data structure
sepa	the cut separator itself
sepadata	data of separator
ncliquenodes	number of nodes in clique
cliquenodes	nodes in clique
cutoff	whether a cutoff has been detected

Definition at line 1127 of file sepa_clique.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), and TRUE.

Referenced by TCLIQUE_NEWSOL().

static TCLIQUE_NEWSOL ( tcliqueNewsolClique )

static

generates cuts using a clique found by algorithm for maximum weight clique and decides whether to stop generating cliques with the algorithm for maximum weight clique

Definition at line 1183 of file sepa_clique.c.

References FALSE, MAX, newsolCliqueAddRow(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisEfficacious(), and TRUE.

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

searches and adds clique cuts that separate the given primal solution

Parameters

scip	SCIP data structure
sepa	the cut separator itself
sol	primal solution that should be separated, or NULL for LP solution
result	pointer to store the result of the separation call

Definition at line 1277 of file sepa_clique.c.

References FALSE, loadTcliquegraph(), NULL, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetSolVals(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetNCalls(), tcliqueMaxClique(), TRUE, and updateTcliquegraph().