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
96 int maxzeroextensions;
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 )
212 assert(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;
265 (*tcliquegraph)->vars[*nodeidx] = nodevar;
266 (*tcliquegraph)->weights[*nodeidx] = 0;
267 (*tcliquegraph)->nnodes++;
273 cliqueids = (*tcliquegraph)->cliqueids;
274 for(
i = 0;
i < ncliques; ++
i )
276 assert(ncliqueids < (*tcliquegraph)->cliqueidssize);
278 assert(
i == 0 || cliqueids[ncliqueids-1] <= cliqueids[ncliqueids]);
283 (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] = nadjnodes;
284 (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] = ncliqueids;
317 for( value = 0; value < 2; ++value )
319 assert(cliquegraphidx[value][
i] == -1);
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 )
425 unsigned int colmask;
432 rowstart = nu*tablewidth;
434 colmask = 1U << (nu % nbits);
435 for( v = u+1; v <
nvars; ++v )
445 mask = 1U << (nv % nbits);
446 cliquetable[rowstart+nv/nbits] |= mask;
447 cliquetable[nv*tablewidth+colofs] |= colmask;
453 SCIPdebugMsg(
scip,
"clique separator: finished constructing dense clique table\n");
467 int* cliquegraphidx[2];
484 cliquegraphidx[0][
i] = -1;
485 cliquegraphidx[1][
i] = -1;
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));
581 colofs = 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];
599 while( i1 < endi1 && i2 < endi2 )
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 )
638 middle = (left+right)/2;
639 node = tcliquegraph->adjnodes[middle];
642 else if( node > node2 )
672 graphadjnodes = tcliquegraph->adjnodes;
673 nodeadjindex = tcliquegraph->adjnodesidxs[node];
674 nodeadjend = tcliquegraph->adjnodesidxs[node+1];
678 assert(0 <= nodes[
i] && nodes[
i] < tcliquegraph->nnodes);
680 while( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] < nodes[
i] )
682 if( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] == nodes[
i] )
685 adjnodes[nadjnodes] = nodes[
i];
693 adjnodes[nadjnodes] = nodes[
i];
727 assert(ncliquenodes <= sepadata->tcliquegraph->nnodes);
729 for(
i = 0;
i < ncliquenodes; ++
i )
772 *stopsolving =
FALSE;
775 minweightinc = (cliqueweight - *minweight)/10;
776 minweightinc =
MAX(minweightinc, 1);
777 *minweight += minweightinc;
780 if( cliqueweight >
sepadata->scaleval )
794 unscaledweight = 0.0;
795 for(
i = 0;
i < ncliquenodes;
i++ )
796 unscaledweight += varsolvals[cliquenodes[
i]];
856 int maxzeroextensions;
907 tcliquegraph =
sepadata->tcliquegraph;
916 maxtreenodes = (
sepadata->maxtreenodes == -1 ? INT_MAX :
sepadata->maxtreenodes);
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,
928 maxtreenodes,
sepadata->backtrackfreq, maxzeroextensions, -1,
NULL, &tcliquestatus);
1076 sepaExeclpClique, sepaExecsolClique,
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 DEFAULT_MAXSEPACUTS
#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
#define SEPA_MAXBOUNDDIST
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)
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
struct TCLIQUE_Data TCLIQUE_DATA
#define TCLIQUE_NEWSOL(x)
struct SCIP_Clique SCIP_CLIQUE
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)
struct SCIP_Sepa SCIP_SEPA
#define SCIP_DECL_SEPACOPY(x)