56#if defined(_WIN32) || defined(_WIN64)
62#define SEPA_NAME "clique"
63#define SEPA_DESC "clique separator of stable set relaxation"
64#define SEPA_PRIORITY -5000
66#define SEPA_MAXBOUNDDIST 0.0
67#define SEPA_USESSUBSCIP FALSE
68#define SEPA_DELAY FALSE
70#define DEFAULT_SCALEVAL 1000.0
71#define DEFAULT_MAXTREENODES 10000
72#define DEFAULT_BACKTRACKFREQ 1000
73#define DEFAULT_MAXSEPACUTS 10
74#define DEFAULT_MAXZEROEXTENSIONS 1000
75#define DEFAULT_CLIQUETABLEMEM 20000.0
76#define DEFAULT_CLIQUEDENSITY 0.00
90 SCIP_Real* varsolvals;
96 int maxzeroextensions;
97 SCIP_Real cliquetablemem;
98 SCIP_Real cliquedensity;
100 SCIP_Bool tcliquegraphloaded;
114 unsigned int* cliqueids;
115 unsigned int* cliquetable;
151 (*tcliquegraph)->adjnodesidxs[0] = 0;
152 (*tcliquegraph)->cliqueidsidxs[0] = 0;
153 (*tcliquegraph)->adjnodes =
NULL;
154 (*tcliquegraph)->cliqueids =
NULL;
155 (*tcliquegraph)->cliquetable =
NULL;
156 (*tcliquegraph)->adjnodessize = 0;
157 (*tcliquegraph)->cliqueidssize = 0;
158 (*tcliquegraph)->nnodes = 0;
159 (*tcliquegraph)->tablewidth = 0;
160 (*tcliquegraph)->maxnnodes = maxnnodes;
178 for( v = 0; v < (*tcliquegraph)->nnodes; ++v )
207 if( num > tcliquegraph->cliqueidssize )
230 unsigned int* cliqueids;
243 if( *tcliquegraph ==
NULL )
259 nadjnodes = (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes];
260 ncliqueids = (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes];
263 *
nodeidx = (*tcliquegraph)->nnodes;
266 (*tcliquegraph)->weights[*
nodeidx] = 0;
267 (*tcliquegraph)->nnodes++;
273 cliqueids = (*tcliquegraph)->cliqueids;
274 for(
i = 0;
i < ncliques; ++
i )
283 (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] =
nadjnodes;
284 (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] =
ncliqueids;
317 for( value = 0; value < 2; ++value )
340 SCIP_Real cliquetablemem,
341 SCIP_Real cliquedensity
346 unsigned int* cliquetable;
363 nbits = 8*
sizeof(
unsigned int);
364 tcliquegraph->tablewidth = (tcliquegraph->nnodes +
nbits-1) /
nbits;
367 if( (SCIP_Real)tcliquegraph->nnodes * (
SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem )
372 for(
i = 0;
i < ncliques; ++
i )
379 tablesize = tcliquegraph->nnodes * tcliquegraph->tablewidth;
380 SCIPdebugMsg(
scip,
"clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n",
388 cliquetable = tcliquegraph->cliquetable;
389 tablewidth = tcliquegraph->tablewidth;
413 for( v = 0; v < tcliquegraph->nnodes &&
var != tcliquegraph->vars[v]; ++v )
435 for( v =
u+1; v <
nvars; ++v )
453 SCIPdebugMsg(
scip,
"clique separator: finished constructing dense clique table\n");
521 tcliquegraph =
sepadata->tcliquegraph;
525 for(
i = 0;
i < tcliquegraph->nnodes;
i++ )
530 tcliquegraph->weights[
i] =
MAX(weight, 0);
545 return tcliquegraph->nnodes;
554 return tcliquegraph->weights;
572 if( tcliquegraph->cliquetable !=
NULL )
579 nbits = 8*
sizeof(
unsigned int);
580 mask = (1U << (node2 %
nbits));
582 assert(((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth +
colofs] & mask) != 0)
583 == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/
nbits] & (1U << (node1 %
nbits))) != 0));
584 return ((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth +
colofs] & mask) != 0);
588 unsigned int* cliqueids;
594 cliqueids = tcliquegraph->cliqueids;
595 i1 = tcliquegraph->cliqueidsidxs[node1];
596 endi1 = tcliquegraph->cliqueidsidxs[node1+1];
597 i2 = tcliquegraph->cliqueidsidxs[node2];
598 endi2 = tcliquegraph->cliqueidsidxs[node2+1];
601 while(
i1 <
endi1 && cliqueids[
i1] < cliqueids[
i2] )
606 while(
i2 <
endi2 && cliqueids[
i2] < cliqueids[
i1] )
611 if( cliqueids[
i1] == cliqueids[
i2] )
631 left = tcliquegraph->adjnodesidxs[node1];
632 right = tcliquegraph->adjnodesidxs[node1+1]-1;
633 while( left <= right )
639 node = tcliquegraph->adjnodes[
middle];
642 else if( node > node2 )
674 nodeadjend = tcliquegraph->adjnodesidxs[node+1];
678 assert(0 <= nodes[
i] && nodes[
i] < tcliquegraph->nnodes);
784 SCIP_Real* varsolvals;
856 int maxzeroextensions;
857 SCIP_Bool infeasible;
907 tcliquegraph =
sepadata->tcliquegraph;
1089 "separating/clique/scaleval",
1090 "factor for scaling weights",
1093 "separating/clique/maxtreenodes",
1094 "maximal number of nodes in branch and bound tree (-1: no limit)",
1097 "separating/clique/backtrackfreq",
1098 "frequency for premature backtracking up to tree level 1 (0: no backtracking)",
1101 "separating/clique/maxsepacuts",
1102 "maximal number of clique cuts separated per separation round (-1: no limit)",
1105 "separating/clique/maxzeroextensions",
1106 "maximal number of zero-valued variables extending the clique (-1: no limit)",
1109 "separating/clique/cliquetablemem",
1110 "maximal memory size of dense clique table (in kb)",
1113 "separating/clique/cliquedensity",
1114 "minimal density of cliques to use a dense clique table",
#define SCIP_LONGINT_FORMAT
static const SCIP_Real density
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
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)
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)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPfreeMemoryArrayNull(scip, ptr)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
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)
void SCIProwChgRank(SCIP_ROW *row, int rank)
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)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
int SCIPgetNCliques(SCIP *scip)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPincludeSepaClique(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
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
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)
#define DEFAULT_MAXTREENODES
static SCIP_RETCODE tcliquegraphCreate(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
#define DEFAULT_CLIQUEDENSITY
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)
#define DEFAULT_BACKTRACKFREQ
#define DEFAULT_CLIQUETABLEMEM
#define DEFAULT_MAXZEROEXTENSIONS
static SCIP_RETCODE tcliquegraphEnsureCliqueidsSize(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int num)
static SCIP_RETCODE newsolCliqueAddRow(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int ncliquenodes, int *cliquenodes)
static SCIP_Bool nodesHaveCommonClique(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
#define SEPA_MAXBOUNDDIST
#define DEFAULT_MAXSEPACUTS
static SCIP_RETCODE loadTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
static SCIP_RETCODE tcliquegraphFree(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
static void updateTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
#define TCLIQUE_GETWEIGHTS(x)
#define TCLIQUE_GETNNODES(x)
#define TCLIQUE_ISEDGE(x)
#define TCLIQUE_SELECTADJNODES(x)
enum TCLIQUE_Status TCLIQUE_STATUS
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)
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define TCLIQUE_NEWSOL(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAEXECSOL(x)
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPAEXITSOL(x)
#define SCIP_DECL_SEPACOPY(x)