Detailed Description

clique separator

Author: Kati Wolter; Tobias Achterberg

Definition in file sepa_clique.c.

#include "blockmemshell/memory.h"
#include "scip/pub_implics.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include "scip/sepa_clique.h"
#include "tclique/tclique.h"
#include <string.h>
#include <strings.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.00

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

static SCIP_RETCODE	tcliquegraphFree (SCIP scip, TCLIQUE_GRAPH *tcliquegraph)

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	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

◆ SEPA_NAME

#define SEPA_NAME "clique"

Definition at line 52 of file sepa_clique.c.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaClique().

◆ SEPA_DESC

#define SEPA_DESC "clique separator of stable set relaxation"

Definition at line 53 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -5000

Definition at line 54 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ SEPA_FREQ

#define SEPA_FREQ 0

Definition at line 55 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 56 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 57 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 58 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_SCALEVAL

#define DEFAULT_SCALEVAL 1000.0

factor for scaling weights

Definition at line 60 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_MAXTREENODES

#define DEFAULT_MAXTREENODES 10000

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

Definition at line 61 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_BACKTRACKFREQ

#define DEFAULT_BACKTRACKFREQ 1000

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

Definition at line 62 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS 10

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

Definition at line 63 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_MAXZEROEXTENSIONS

#define DEFAULT_MAXZEROEXTENSIONS 1000

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

Definition at line 64 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_CLIQUETABLEMEM

#define DEFAULT_CLIQUETABLEMEM 20000.0

maximal memory size of dense clique table (in kb)

Definition at line 65 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

◆ DEFAULT_CLIQUEDENSITY

#define DEFAULT_CLIQUEDENSITY 0.00

minimal density of cliques to use a dense clique table

Definition at line 66 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

Function Documentation

◆ tcliquegraphCreate()

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPgetNBinVars().

Referenced by tcliquegraphAddNode().

◆ tcliquegraphFree()

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

References Scip::cliquetable, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().

Referenced by loadTcliquegraph(), and SCIP_DECL_SEPAEXITSOL().

◆ tcliquegraphEnsureCliqueidsSize()

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

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

Referenced by tcliquegraphAddNode().

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

◆ tcliquegraphAddCliqueVars()

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

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

Referenced by loadTcliquegraph().

◆ tcliquegraphConstructCliqueTable()

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

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

Referenced by loadTcliquegraph().

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

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

Referenced by separateCuts().

◆ updateTcliquegraph()

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

References MAX, NULL, and SCIPfeasFloor().

Referenced by separateCuts().

◆ TCLIQUE_GETNNODES()

static TCLIQUE_GETNNODES ( tcliqueGetnnodesClique )

static

gets number of nodes in the graph

Definition at line 531 of file sepa_clique.c.

References NULL.

◆ TCLIQUE_GETWEIGHTS()

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique )

static

gets weight of nodes in the graph

Definition at line 540 of file sepa_clique.c.

References NULL.

◆ nodesHaveCommonClique()

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

References FALSE, NULL, and TRUE.

Referenced by TCLIQUE_ISEDGE(), and TCLIQUE_SELECTADJNODES().

◆ TCLIQUE_ISEDGE()

static TCLIQUE_ISEDGE ( tcliqueIsedgeClique )

static

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

Definition at line 611 of file sepa_clique.c.

References nnodes, nodesHaveCommonClique(), NULL, and TRUE.

◆ TCLIQUE_SELECTADJNODES()

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

References nnodes, nodesHaveCommonClique(), and NULL.

◆ newsolCliqueAddRow()

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

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

Referenced by TCLIQUE_NEWSOL().

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

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

◆ separateCuts()

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

References TCLIQUE_Data::cutoff, FALSE, loadTcliquegraph(), TCLIQUE_Data::ncuts, NULL, TCLIQUE_Data::scaleval, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPallocBufferArray, SCIPcleanupCliques(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVals(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetNCalls(), TCLIQUE_Data::sol, tcliqueMaxClique(), TRUE, and updateTcliquegraph().

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyClique )

static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 963 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaClique(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeClique )

static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 978 of file sepa_clique.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolClique )

static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 995 of file sepa_clique.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and tcliquegraphFree().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpClique )

static

LP solution separation method of separator

Definition at line 1016 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolClique )

static

arbitrary primal solution separation method of separator

Definition at line 1043 of file sepa_clique.c.

References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_SCALEVAL

◆ DEFAULT_MAXTREENODES

◆ DEFAULT_BACKTRACKFREQ

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXZEROEXTENSIONS

◆ DEFAULT_CLIQUETABLEMEM

◆ DEFAULT_CLIQUEDENSITY

Function Documentation

◆ tcliquegraphCreate()

◆ tcliquegraphFree()

◆ tcliquegraphEnsureCliqueidsSize()

◆ tcliquegraphAddNode()

◆ tcliquegraphAddCliqueVars()

◆ tcliquegraphConstructCliqueTable()

◆ loadTcliquegraph()

◆ updateTcliquegraph()

◆ TCLIQUE_GETNNODES()

◆ TCLIQUE_GETWEIGHTS()

◆ nodesHaveCommonClique()

◆ TCLIQUE_ISEDGE()

◆ TCLIQUE_SELECTADJNODES()

◆ newsolCliqueAddRow()

◆ TCLIQUE_NEWSOL()

◆ separateCuts()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIP_DECL_SEPAEXECSOL()