clique separator
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 |
#define SEPA_NAME "clique" |
Definition at line 62 of file sepa_clique.c.
#define SEPA_DESC "clique separator of stable set relaxation" |
Definition at line 63 of file sepa_clique.c.
#define SEPA_PRIORITY -5000 |
Definition at line 64 of file sepa_clique.c.
#define SEPA_FREQ 0 |
Definition at line 65 of file sepa_clique.c.
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 66 of file sepa_clique.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 67 of file sepa_clique.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 68 of file sepa_clique.c.
#define DEFAULT_SCALEVAL 1000.0 |
factor for scaling weights
Definition at line 70 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 71 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 72 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 73 of file sepa_clique.c.
#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().
#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().
#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().
|
static |
creates an empty tclique graph data structure
scip | SCIP data structure |
tcliquegraph | pointer 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().
|
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 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().
|
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 199 of file sepa_clique.c.
References assert(), NULL, 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 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().
|
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 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().
|
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 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().
|
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 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().
|
static |
updates the weights in the tclique graph data structure
scip | SCIP data structure |
sepadata | separator data |
Definition at line 510 of file sepa_clique.c.
References assert(), i, MAX, NULL, SCIPfeasFloor(), and sepadata.
Referenced by separateCuts().
|
static |
gets number of nodes in the graph
Definition at line 541 of file sepa_clique.c.
|
static |
gets weight of nodes in the graph
Definition at line 550 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 559 of file sepa_clique.c.
References assert(), FALSE, NULL, SCIP_Bool, and TRUE.
Referenced by TCLIQUE_ISEDGE(), and TCLIQUE_SELECTADJNODES().
|
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.
|
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.
|
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 |
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().
|
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.
|
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 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().
|
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.
|
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.
|
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().
|
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().
|
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.