Scippy

SCIP

Solving Constraint Integer Programs

sepa_clique.c File Reference

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

#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
scipSCIP data structure
tcliquegraphpointer 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
scipSCIP data structure
tcliquegraphpointer 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 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 166 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
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 188 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().

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
scipSCIP data structure
tcliquegraphpointer to tclique graph data
cliquegraphidxarray to store tclique graph node index of variable/value pairs

Definition at line 258 of file sepa_clique.c.

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

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
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 301 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
scipSCIP data structure
sepadataseparator data

Definition at line 429 of file sepa_clique.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPisStopped(), tcliquegraphAddCliqueVars(), 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
scipSCIP data structure
sepadataseparator data

Definition at line 477 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 508 of file sepa_clique.c.

References NULL.

static TCLIQUE_GETWEIGHTS ( tcliqueGetweightsClique  )
static

gets weight of nodes in the graph

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

Definition at line 526 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 588 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 623 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
scipSCIP data structure
sepathe cut separator itself
sepadatadata of separator
ncliquenodesnumber of nodes in clique
cliquenodesnodes in clique
cutoffwhether a cutoff has been detected

Definition at line 671 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 727 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
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 825 of file sepa_clique.c.

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

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

static SCIP_DECL_SEPACOPY ( sepaCopyClique  )
static

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

Definition at line 941 of file sepa_clique.c.

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

static SCIP_DECL_SEPAFREE ( sepaFreeClique  )
static

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

Definition at line 956 of file sepa_clique.c.

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

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolClique  )
static

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

Definition at line 973 of file sepa_clique.c.

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

static SCIP_DECL_SEPAEXECLP ( sepaExeclpClique  )
static

LP solution separation method of separator

Definition at line 994 of file sepa_clique.c.

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

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolClique  )
static

arbitrary primal solution separation method of separator

Definition at line 1021 of file sepa_clique.c.

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