clique separator
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.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) |
#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.00 |
minimal density of cliques to use a dense clique table
Definition at line 46 of file sepa_clique.c.
Referenced by SCIPincludeSepaClique().
|
static |
creates an empty tclique graph data structure
scip | SCIP data structure |
tcliquegraph | pointer to tclique graph data |
Definition at line 101 of file sepa_clique.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPgetNBinVars().
Referenced by tcliquegraphAddNode().
|
static |
frees the tclique graph data structure and releases all captured variables
scip | SCIP data structure |
tcliquegraph | pointer to tclique graph data |
Definition at line 137 of file sepa_clique.c.
References Scip::cliquetable, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().
Referenced by loadTcliquegraph(), and SCIP_DECL_SEPAEXITSOL().
|
static |
ensures that the cliqueids array can store at least num entries
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 169 of file sepa_clique.c.
References SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.
Referenced by tcliquegraphAddNode().
|
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
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 191 of file sepa_clique.c.
References SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPcaptureVar(), SCIPcliqueGetId(), SCIPgetNBinVars(), SCIPgetNegatedVar(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetType(), SCIPvarIsActive(), tcliquegraphCreate(), and tcliquegraphEnsureCliqueidsSize().
Referenced by tcliquegraphAddCliqueVars().
|
static |
adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique
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 261 of file sepa_clique.c.
References SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetVars(), SCIPvarGetNCliques(), and tcliquegraphAddNode().
Referenced by loadTcliquegraph().
|
static |
constructs dense clique incidence matrix
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 307 of file sepa_clique.c.
References BMSclearMemoryArray, Scip::cliquetable, density, nnodes, 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().
|
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
scip | SCIP data structure |
sepadata | separator data |
Definition at line 432 of file sepa_clique.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPisStopped(), tcliquegraphAddCliqueVars(), tcliquegraphConstructCliqueTable(), and tcliquegraphFree().
Referenced by separateCuts().
|
static |
updates the weights in the tclique graph data structure
scip | SCIP data structure |
sepadata | separator data |
Definition at line 480 of file sepa_clique.c.
References MAX, and SCIPfeasFloor().
Referenced by separateCuts().
|
static |
gets number of nodes in the graph
Definition at line 511 of file sepa_clique.c.
|
static |
gets weight of nodes in the graph
Definition at line 520 of file sepa_clique.c.
|
static |
returns whether the nodes are member of a common clique
tcliquegraph | tclique graph data |
node1 | first node |
node2 | second node |
Definition at line 529 of file sepa_clique.c.
Referenced by TCLIQUE_ISEDGE(), and TCLIQUE_SELECTADJNODES().
|
static |
returns, whether the edge (node1, node2) is in the graph
Definition at line 591 of file sepa_clique.c.
References nnodes, nodesHaveCommonClique(), and TRUE.
|
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 626 of file sepa_clique.c.
References nnodes, and nodesHaveCommonClique().
|
static |
basic code for new cliques (needed because of error handling)
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 674 of file sepa_clique.c.
References FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), and TRUE.
Referenced by TCLIQUE_NEWSOL().
|
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 729 of file sepa_clique.c.
References FALSE, MAX, newsolCliqueAddRow(), SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisEfficacious(), and TRUE.
|
static |
searches and adds clique cuts that separate the given primal solution
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 827 of file sepa_clique.c.
References TCLIQUE_Data::cutoff, FALSE, loadTcliquegraph(), TCLIQUE_Data::ncuts, 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().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 943 of file sepa_clique.c.
References SCIP_CALL, SCIP_OKAY, SCIPincludeSepaClique(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 958 of file sepa_clique.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 975 of file sepa_clique.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and tcliquegraphFree().
|
static |
LP solution separation method of separator
Definition at line 996 of file sepa_clique.c.
References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().
|
static |
arbitrary primal solution separation method of separator
Definition at line 1023 of file sepa_clique.c.
References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().