SCIP Doxygen Documentation
Loading...
Searching...
No Matches

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

◆ SEPA_DESC

#define SEPA_DESC   "clique separator of stable set relaxation"

Definition at line 63 of file sepa_clique.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -5000

Definition at line 64 of file sepa_clique.c.

◆ SEPA_FREQ

#define SEPA_FREQ   0

Definition at line 65 of file sepa_clique.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 66 of file sepa_clique.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 67 of file sepa_clique.c.

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 68 of file sepa_clique.c.

◆ DEFAULT_SCALEVAL

#define DEFAULT_SCALEVAL   1000.0

factor for scaling weights

Definition at line 70 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 71 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 72 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 73 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 74 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 75 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 76 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
scipSCIP data structure
tcliquegraphpointer to tclique graph data

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

Definition at line 167 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
scipSCIP data structure
tcliquegraphtclique graph data
numminimal number of adjacent nodes to be able to store in the array

Definition at line 199 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
scipSCIP data structure
tcliquegraphpointer to tclique graph data
varactive binary problem variable
valuevalue of the variable in the node
nodeidxpointer to store the index of the new node

Definition at line 221 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(), 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
scipSCIP data structure
tcliquegraphpointer to tclique graph data
cliquegraphidxarray to store tclique graph node index of variable/value pairs

Definition at line 291 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
scipSCIP data structure
tcliquegraphtclique graph data
cliquetablememmaximal memory size of dense clique table (in kb)
cliquedensityminimal density of cliques to store as dense table

Definition at line 337 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(), 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
scipSCIP data structure
sepadataseparator data

Definition at line 462 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
scipSCIP data structure
sepadataseparator data

Definition at line 510 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 541 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 550 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
tcliquegraphtclique graph data
node1first node
node2second node

Definition at line 559 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 621 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 656 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
scipSCIP data structure
sepathe cut separator itself
sepadatadata of separator
ncliquenodesnumber of nodes in clique
cliquenodesnodes in clique

Definition at line 704 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 755 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
scipSCIP data structure
sepathe cut separator itself
solprimal solution that should be separated, or NULL for LP solution
resultpointer to store the result of the separation call

Definition at line 842 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 958 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 973 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 990 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 1011 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 1038 of file sepa_clique.c.

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