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

◆ SEPA_DESC

#define SEPA_DESC "clique separator of stable set relaxation"

Definition at line 62 of file sepa_clique.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -5000

Definition at line 63 of file sepa_clique.c.

◆ SEPA_FREQ

#define SEPA_FREQ 0

Definition at line 64 of file sepa_clique.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 65 of file sepa_clique.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 66 of file sepa_clique.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 67 of file sepa_clique.c.

◆ DEFAULT_SCALEVAL

#define DEFAULT_SCALEVAL 1000.0

factor for scaling weights

Definition at line 69 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 70 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 71 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 72 of file sepa_clique.c.

◆ DEFAULT_MAXZEROEXTENSIONS

#define DEFAULT_MAXZEROEXTENSIONS 1000

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

Definition at line 73 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 74 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 75 of file sepa_clique.c.

Referenced by SCIPincludeSepaClique().

Function Documentation

◆ tcliquegraphCreate()

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

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

Referenced by tcliquegraphAddNode().

◆ tcliquegraphFree()

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

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().

Referenced by loadTcliquegraph(), and SCIP_DECL_SEPAEXITSOL().

◆ tcliquegraphEnsureCliqueidsSize()

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

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

Referenced by tcliquegraphAddNode().

◆ tcliquegraphAddNode()

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

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

Referenced by tcliquegraphAddCliqueVars().

◆ tcliquegraphAddCliqueVars()

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

References assert(), i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetVars(), SCIPvarGetNCliques(), tcliquegraphAddNode(), var, and vars.

Referenced by loadTcliquegraph().

◆ tcliquegraphConstructCliqueTable()

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

References assert(), BMSclearMemoryArray, density, i, nnodes, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCliques(), SCIPgetNCliques(), SCIPisStopped(), SCIPvarGetNegatedVar(), SCIPvarGetType(), SCIPvarIsImpliedIntegral(), var, and vars.

Referenced by loadTcliquegraph().

◆ loadTcliquegraph()

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

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

Referenced by separateCuts().

◆ updateTcliquegraph()

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

References assert(), i, MAX, NULL, SCIPfeasFloor(), and sepadata.

Referenced by separateCuts().

◆ TCLIQUE_GETNNODES()

TCLIQUE_GETNNODES ( tcliqueGetnnodesClique )

static

gets number of nodes in the graph

Definition at line 540 of file sepa_clique.c.

References assert(), and NULL.

◆ TCLIQUE_GETWEIGHTS()

TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique )

static

gets weight of nodes in the graph

Definition at line 549 of file sepa_clique.c.

References assert(), and NULL.

◆ nodesHaveCommonClique()

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

References assert(), FALSE, NULL, SCIP_Bool, and TRUE.

Referenced by TCLIQUE_ISEDGE(), and TCLIQUE_SELECTADJNODES().

◆ TCLIQUE_ISEDGE()

TCLIQUE_ISEDGE ( tcliqueIsedgeClique )

static

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

Definition at line 620 of file sepa_clique.c.

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

◆ TCLIQUE_SELECTADJNODES()

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

References assert(), i, nnodes, nodesHaveCommonClique(), and NULL.

◆ newsolCliqueAddRow()

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

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

Definition at line 703 of file sepa_clique.c.

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

Referenced by TCLIQUE_NEWSOL().

◆ TCLIQUE_NEWSOL()

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

References assert(), FALSE, i, MAX, newsolCliqueAddRow(), NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisEfficacious(), sepadata, and TRUE.

◆ separateCuts()

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

References assert(), FALSE, loadTcliquegraph(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPallocBufferArray, SCIPcleanupCliques(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVals(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetNCalls(), sepadata, sol, tcliqueMaxClique(), TRUE, and updateTcliquegraph().

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

SCIP_DECL_SEPACOPY ( sepaCopyClique )

static

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

Definition at line 957 of file sepa_clique.c.

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

◆ SCIP_DECL_SEPAFREE()

SCIP_DECL_SEPAFREE ( sepaFreeClique )

static

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

Definition at line 972 of file sepa_clique.c.

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

◆ SCIP_DECL_SEPAEXITSOL()

SCIP_DECL_SEPAEXITSOL ( sepaExitsolClique )

static

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

Definition at line 989 of file sepa_clique.c.

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

◆ SCIP_DECL_SEPAEXECLP()

SCIP_DECL_SEPAEXECLP ( sepaExeclpClique )

static

LP solution separation method of separator

Definition at line 1010 of file sepa_clique.c.

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

◆ SCIP_DECL_SEPAEXECSOL()

SCIP_DECL_SEPAEXECSOL ( sepaExecsolClique )

static

arbitrary primal solution separation method of separator

Definition at line 1037 of file sepa_clique.c.

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

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