SCIP
Solving Constraint Integer Programs
sepa_clique.c File Reference
Detailed Description
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 |
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.
◆ 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.
◆ 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.
◆ 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.
◆ 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.
◆ 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.
Function Documentation
◆ tcliquegraphCreate()
|
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 NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPgetNBinVars().
Referenced by tcliquegraphAddNode().
◆ tcliquegraphFree()
|
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 NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArrayNull, and SCIPreleaseVar().
Referenced by loadTcliquegraph(), and SCIP_DECL_SEPAEXITSOL().
◆ tcliquegraphEnsureCliqueidsSize()
|
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 NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.
Referenced by tcliquegraphAddNode().
◆ 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
- 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 NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPcaptureVar(), SCIPcliqueGetId(), SCIPgetNBinVars(), SCIPgetNegatedVar(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetType(), SCIPvarIsActive(), SCIPvarIsImpliedIntegral(), tcliquegraphCreate(), and tcliquegraphEnsureCliqueidsSize().
Referenced by tcliquegraphAddCliqueVars().
◆ tcliquegraphAddCliqueVars()
|
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 NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetVars(), SCIPvarGetNCliques(), and tcliquegraphAddNode().
Referenced by loadTcliquegraph().
◆ tcliquegraphConstructCliqueTable()
|
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 BMSclearMemoryArray, density, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCliques(), SCIPgetNCliques(), SCIPisStopped(), SCIPvarGetNegatedVar(), SCIPvarGetType(), and SCIPvarIsImpliedIntegral().
Referenced by loadTcliquegraph().
◆ 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
- Parameters
-
scip SCIP data structure sepadata separator data
Definition at line 461 of file sepa_clique.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPisStopped(), tcliquegraphAddCliqueVars(), tcliquegraphConstructCliqueTable(), and tcliquegraphFree().
Referenced by separateCuts().
◆ updateTcliquegraph()
|
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 MAX, NULL, and SCIPfeasFloor().
Referenced by separateCuts().
◆ TCLIQUE_GETNNODES()
|
static |
◆ TCLIQUE_GETWEIGHTS()
|
static |
◆ nodesHaveCommonClique()
|
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 FALSE, NULL, and TRUE.
Referenced by TCLIQUE_ISEDGE(), and TCLIQUE_SELECTADJNODES().
◆ TCLIQUE_ISEDGE()
|
static |
returns whether the edge (node1, node2) is in the graph
Definition at line 620 of file sepa_clique.c.
References nnodes, nodesHaveCommonClique(), NULL, and TRUE.
◆ TCLIQUE_SELECTADJNODES()
|
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 nnodes, nodesHaveCommonClique(), and NULL.
◆ newsolCliqueAddRow()
|
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 FALSE, NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPflushRowExtensions(), SCIPinfinity(), SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), and TRUE.
Referenced by TCLIQUE_NEWSOL().
◆ 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 754 of file sepa_clique.c.
References FALSE, MAX, newsolCliqueAddRow(), NULL, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisEfficacious(), and TRUE.
◆ separateCuts()
|
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 FALSE, loadTcliquegraph(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPallocBufferArray, SCIPcleanupCliques(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVals(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetNCalls(), tcliqueMaxClique(), TRUE, and updateTcliquegraph().
Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 957 of file sepa_clique.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaClique(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 972 of file sepa_clique.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), and SCIPsepaSetData().
◆ SCIP_DECL_SEPAEXITSOL()
|
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 FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and tcliquegraphFree().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 1010 of file sepa_clique.c.
References NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().
◆ SCIP_DECL_SEPAEXECSOL()
|
static |
arbitrary primal solution separation method of separator
Definition at line 1037 of file sepa_clique.c.
References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().