sepa_clique.c
Go to the documentation of this file.
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
71#define DEFAULT_MAXTREENODES 10000 /**< maximal number of nodes in branch and bound tree (-1: no limit) */
72#define DEFAULT_BACKTRACKFREQ 1000 /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
73#define DEFAULT_MAXSEPACUTS 10 /**< maximal number of clique cuts separated per separation round (-1: no limit) */
74#define DEFAULT_MAXZEROEXTENSIONS 1000 /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
90 SCIP_Real* varsolvals; /**< LP solution of binary variables (contained in a 3-clique in implgraph) */
94 int backtrackfreq; /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
95 int maxsepacuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */
96 int maxzeroextensions; /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
100 SCIP_Bool tcliquegraphloaded; /**< TRUE if tcliquegraph is already loaded (tcliquegraph can be NULL),
187 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, (*tcliquegraph)->maxnnodes + 1);
210 SCIP_CALL( SCIPreallocMemoryArray(scip, &tcliquegraph->cliqueids, tcliquegraph->cliqueidssize) );
217/** adds a node to the tclique graph defined as a variable-value pair; adds all cliques to the cliqueids array the
289/** adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique */
324 SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, var, (SCIP_Bool)value, &cliquegraphidx[value][i]) );
364 tcliquegraph->tablewidth = (tcliquegraph->nnodes + nbits-1) / nbits; /* number of ints needed */
367 if( (SCIP_Real)tcliquegraph->nnodes * (SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem )
380 SCIPdebugMsg(scip, "clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n",
407 /* implicit integer and integer variables are currently not present in the constructed tclique graph */
412 assert(var != NULL); /* var must exist even if negated, since it is stored in the tcliquegraph */
427 /* implicit integer and integer variables are currently not present in the constructed tclique graph */
440 /* implicit integer and integer variables are currently not present in the constructed tclique graph */
491 /* it occurs that it might be that some cliques were not yet removed from the global clique array, so SCIPgetNClique
497 SCIP_CALL( tcliquegraphConstructCliqueTable(scip, sepadata->tcliquegraph, sepadata->cliquetablemem, sepadata->cliquedensity) );
583 == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/nbits] & (1U << (node1 % nbits))) != 0)); /*lint !e701*/
630 /* check if node2 is contained in adjacency list of node1 (list is ordered by adjacent nodes) */
671 /* check for each node in given nodes set, if it is adjacent to the given node or shares a common clique */
677 /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */
722 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "clique%" SCIP_LONGINT_FORMAT "_%d", sepadata->ncalls, sepadata->ncuts);
723 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
770 /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */
809 /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent,
821 /* in case an internal SCIP error occurred we stop the algorithm and store the error code for later
838 * @todo Should the existing cliques in the table be separated before starting the tclique algorithm?
877 /* if we already detected that no implications between binary variables exist, nothing has to be done */
896 /* we did not find any variables that are contained in a clique with at least 3 variables in the
912 SCIP_CALL( SCIPgetSolVals(scip, sol, tcliquegraph->nnodes, tcliquegraph->vars, sepadata->varsolvals) );
917 maxzeroextensions = (sepadata->maxzeroextensions == -1 ? INT_MAX : sepadata->maxzeroextensions);
925 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
927 cliquenodes, &ncliquenodes, &cliqueweight, (int)sepadata->scaleval-1, (int)sepadata->scaleval+1,
930 /* in case an internal error occurred during the maximal clique computation, evaluate that one */
988/** solving process deinitialization method of separator (called before branch and bound process data is freed) */
1074 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
1111 &sepadata->cliquetablemem, TRUE, DEFAULT_CLIQUETABLEMEM, 0.0, (SCIP_Real)INT_MAX/1024.0, NULL, NULL) );
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
memory allocation routines
Definition: objbenders.h:44
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for SCIP variables
static SCIP_RETCODE tcliquegraphAddNode(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph, SCIP_VAR *var, SCIP_Bool value, int *nodeidx)
Definition: sepa_clique.c:221
static SCIP_RETCODE tcliquegraphCreate(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
Definition: sepa_clique.c:131
static SCIP_RETCODE tcliquegraphAddCliqueVars(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph, int **cliquegraphidx)
Definition: sepa_clique.c:291
static SCIP_RETCODE tcliquegraphConstructCliqueTable(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_Real cliquetablemem, SCIP_Real cliquedensity)
Definition: sepa_clique.c:337
static TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
Definition: sepa_clique.c:656
static SCIP_RETCODE tcliquegraphEnsureCliqueidsSize(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int num)
Definition: sepa_clique.c:199
static SCIP_RETCODE newsolCliqueAddRow(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int ncliquenodes, int *cliquenodes)
Definition: sepa_clique.c:704
static SCIP_Bool nodesHaveCommonClique(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: sepa_clique.c:559
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_clique.c:842
static SCIP_RETCODE loadTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_clique.c:462
static SCIP_RETCODE tcliquegraphFree(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
Definition: sepa_clique.c:167
static void updateTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_clique.c:510
clique separator
Definition: struct_implics.h:76
Definition: struct_lp.h:202
Definition: struct_sepa.h:47
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70
Definition: cons_sos1.c:236
tclique user interface
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
Definition: tclique_branch.c:1010