32 #define SEPA_NAME "clique" 33 #define SEPA_DESC "clique separator of stable set relaxation" 34 #define SEPA_PRIORITY -5000 36 #define SEPA_MAXBOUNDDIST 0.0 37 #define SEPA_USESSUBSCIP FALSE 38 #define SEPA_DELAY FALSE 40 #define DEFAULT_SCALEVAL 1000.0 41 #define DEFAULT_MAXTREENODES 10000 42 #define DEFAULT_BACKTRACKFREQ 1000 43 #define DEFAULT_MAXSEPACUTS 10 44 #define DEFAULT_MAXZEROEXTENSIONS 1000 45 #define DEFAULT_CLIQUETABLEMEM 20000.0 46 #define DEFAULT_CLIQUEDENSITY 0.00 66 int maxzeroextensions;
85 unsigned int* cliquetable;
108 assert(tcliquegraph !=
NULL);
114 assert(maxnnodes > 0);
121 (*tcliquegraph)->adjnodesidxs[0] = 0;
122 (*tcliquegraph)->cliqueidsidxs[0] = 0;
123 (*tcliquegraph)->adjnodes =
NULL;
124 (*tcliquegraph)->cliqueids =
NULL;
125 (*tcliquegraph)->cliquetable =
NULL;
126 (*tcliquegraph)->adjnodessize = 0;
127 (*tcliquegraph)->cliqueidssize = 0;
128 (*tcliquegraph)->nnodes = 0;
129 (*tcliquegraph)->tablewidth = 0;
130 (*tcliquegraph)->maxnnodes = maxnnodes;
144 assert(tcliquegraph !=
NULL);
145 assert(*tcliquegraph !=
NULL);
148 for( v = 0; v < (*tcliquegraph)->nnodes; ++v )
175 assert(tcliquegraph !=
NULL);
177 if( num > tcliquegraph->cliqueidssize )
182 assert(num <= tcliquegraph->cliqueidssize);
207 assert(tcliquegraph !=
NULL);
210 assert(nodeidx !=
NULL);
213 if( *tcliquegraph ==
NULL )
217 assert(*tcliquegraph !=
NULL);
229 nadjnodes = (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes];
230 ncliqueids = (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes];
233 *nodeidx = (*tcliquegraph)->nnodes;
235 (*tcliquegraph)->vars[*nodeidx] = nodevar;
236 (*tcliquegraph)->weights[*nodeidx] = 0;
237 (*tcliquegraph)->nnodes++;
243 cliqueids = (*tcliquegraph)->cliqueids;
244 for( i = 0; i < ncliques; ++i )
246 assert(ncliqueids < (*tcliquegraph)->cliqueidssize);
248 assert(i == 0 || cliqueids[ncliqueids-1] <= cliqueids[ncliqueids]);
253 (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] = nadjnodes;
254 (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] = ncliqueids;
271 assert(tcliquegraph !=
NULL);
272 assert(cliquegraphidx !=
NULL);
273 assert(cliquegraphidx[0] !=
NULL);
274 assert(cliquegraphidx[1] !=
NULL);
280 for( i = 0; i < nvars; ++i )
287 for( value = 0; value < 2; ++value )
289 assert(cliquegraphidx[value][i] == -1);
316 unsigned int* cliquetable;
330 assert(tcliquegraph !=
NULL);
333 nbits = 8*
sizeof(
unsigned int);
334 tcliquegraph->tablewidth = (tcliquegraph->nnodes + nbits-1) / nbits;
337 if( (
SCIP_Real)tcliquegraph->nnodes * (
SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem )
342 for( i = 0; i < ncliques; ++i )
345 if( density < cliquedensity )
349 tablesize = tcliquegraph->nnodes * tcliquegraph->tablewidth;
350 SCIPdebugMsg(scip,
"clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n",
358 cliquetable = tcliquegraph->cliquetable;
359 tablewidth = tcliquegraph->tablewidth;
383 for( v = 0; v < tcliquegraph->nnodes && var != tcliquegraph->vars[v]; ++v )
385 assert(v < tcliquegraph->
nnodes);
395 unsigned int colmask;
402 rowstart = nu*tablewidth;
404 colmask = 1U << (nu % nbits);
405 for( v = u+1; v < nvars; ++v )
415 mask = 1U << (nv % nbits);
416 cliquetable[rowstart+nv/nbits] |= mask;
417 cliquetable[nv*tablewidth+colofs] |= colmask;
423 SCIPdebugMsg(scip,
"clique separator: finished constructing dense clique table\n");
437 int* cliquegraphidx[2];
441 assert(sepadata !=
NULL);
442 assert(sepadata->tcliquegraph ==
NULL);
452 for( i = 0; i < nvars; ++i )
454 cliquegraphidx[0][i] = -1;
455 cliquegraphidx[1][i] = -1;
464 if( sepadata->tcliquegraph !=
NULL )
488 assert(sepadata !=
NULL);
489 assert(sepadata->varsolvals !=
NULL);
491 tcliquegraph = sepadata->tcliquegraph;
492 assert(tcliquegraph !=
NULL);
495 for( i = 0; i < tcliquegraph->nnodes; i++ )
500 tcliquegraph->weights[i] =
MAX(weight, 0);
513 assert(tcliquegraph !=
NULL);
515 return tcliquegraph->nnodes;
522 assert(tcliquegraph !=
NULL);
524 return tcliquegraph->weights;
535 assert(tcliquegraph !=
NULL);
542 if( tcliquegraph->cliquetable !=
NULL )
549 nbits = 8*
sizeof(
unsigned int);
550 mask = (1U << (node2 % nbits));
551 colofs = node2 / nbits;
552 assert(((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0)
553 == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/nbits] & (1U << (node1 % nbits))) != 0));
554 return ((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0);
564 cliqueids = tcliquegraph->cliqueids;
565 i1 = tcliquegraph->cliqueidsidxs[node1];
566 endi1 = tcliquegraph->cliqueidsidxs[node1+1];
567 i2 = tcliquegraph->cliqueidsidxs[node2];
568 endi2 = tcliquegraph->cliqueidsidxs[node2+1];
569 while( i1 < endi1 && i2 < endi2 )
571 while( i1 < endi1 && cliqueids[i1] < cliqueids[i2] )
576 while( i2 < endi2 && cliqueids[i2] < cliqueids[i1] )
581 if( cliqueids[i1] == cliqueids[i2] )
596 assert(tcliquegraph !=
NULL);
597 assert(0 <= node1 && node1 < tcliquegraph->
nnodes);
598 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
601 left = tcliquegraph->adjnodesidxs[node1];
602 right = tcliquegraph->adjnodesidxs[node1+1]-1;
603 while( left <= right )
608 middle = (left+right)/2;
609 node = tcliquegraph->adjnodes[middle];
612 else if( node > node2 )
634 assert(tcliquegraph !=
NULL);
635 assert(0 <= node && node < tcliquegraph->
nnodes);
636 assert(nnodes == 0 || nodes !=
NULL);
637 assert(adjnodes !=
NULL);
642 graphadjnodes = tcliquegraph->adjnodes;
643 nodeadjindex = tcliquegraph->adjnodesidxs[node];
644 nodeadjend = tcliquegraph->adjnodesidxs[node+1];
645 for( i = 0; i <
nnodes; i++ )
648 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
649 assert(i == 0 || nodes[i-1] < nodes[i]);
650 while( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] < nodes[i] )
652 if( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] == nodes[i] )
655 adjnodes[nadjnodes] = nodes[i];
663 adjnodes[nadjnodes] = nodes[i];
688 assert( cutoff !=
NULL );
691 vars = sepadata->tcliquegraph->vars;
692 assert(sepadata->tcliquegraph->nnodes > 0);
693 assert(vars !=
NULL);
701 assert(ncliquenodes <= sepadata->tcliquegraph->nnodes);
703 for( i = 0; i < ncliquenodes; ++i )
705 assert(cliquenodes[i] < sepadata->tcliquegraph->nnodes);
735 assert(acceptsol !=
NULL);
736 assert(stopsolving !=
NULL);
739 assert(sepadata !=
NULL);
740 assert(sepadata->scip !=
NULL);
741 assert(sepadata->sepa !=
NULL);
742 assert(sepadata->tcliquegraph !=
NULL);
743 assert(sepadata->ncuts >= 0);
747 *stopsolving =
FALSE;
750 minweightinc = (cliqueweight - *minweight)/10;
751 minweightinc =
MAX(minweightinc, 1);
752 *minweight += minweightinc;
755 if( cliqueweight > sepadata->scaleval )
764 scip = sepadata->scip;
765 sepa = sepadata->sepa;
766 varsolvals = sepadata->varsolvals;
767 assert(varsolvals !=
NULL);
770 unscaledweight = 0.0;
771 for( i = 0; i < ncliquenodes; i++ )
772 unscaledweight += varsolvals[cliquenodes[i]];
779 retcode =
newsolCliqueAddRow(scip, sepa, sepadata, ncliquenodes, cliquenodes, &cutoff);
784 sepadata->cutoff =
TRUE;
790 SCIPdebugMsg(scip,
" -> found clique cut (act=%g)\n", unscaledweight);
796 if( sepadata->maxsepacuts >= 0 )
798 if( sepadata->ncuts > sepadata->maxsepacuts/2 )
800 if( sepadata->ncuts >= sepadata->maxsepacuts )
810 sepadata->retcode = retcode;
842 int maxzeroextensions;
845 assert(scip !=
NULL);
856 assert(sepadata !=
NULL);
860 sepadata->cutoff =
FALSE;
864 if( sepadata->tcliquegraph ==
NULL && sepadata->tcliquegraphloaded )
870 if( !sepadata->tcliquegraphloaded )
872 assert(sepadata->tcliquegraph ==
NULL);
874 SCIPdebugMsg(scip,
"loading implication and clique graph\n");
876 sepadata->tcliquegraphloaded =
TRUE;
878 if( sepadata->tcliquegraph ==
NULL )
881 sepadata->tcliquegraphloaded =
FALSE;
887 SCIPdebugMsg(scip,
"no 3-cliques found in implication graph\n");
893 tcliquegraph = sepadata->tcliquegraph;
894 assert(tcliquegraph !=
NULL);
902 maxtreenodes = (sepadata->maxtreenodes == -1 ? INT_MAX : sepadata->maxtreenodes);
903 maxzeroextensions = (sepadata->maxzeroextensions == -1 ? INT_MAX : sepadata->maxzeroextensions);
905 SCIPdebugMsg(scip,
"searching for violated clique cuts\n");
911 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
912 tcliquegraph, tcliqueNewsolClique, (
TCLIQUE_DATA*)sepadata,
913 cliquenodes, &ncliquenodes, &cliqueweight, (
int)sepadata->
scaleval-1, (
int)sepadata->
scaleval+1,
914 maxtreenodes, sepadata->backtrackfreq, maxzeroextensions, -1,
NULL, &tcliquestatus);
919 SCIPdebugMsg(scip,
"finished searching clique cuts: found %d cuts\n", sepadata->
ncuts);
928 else if( sepadata->
ncuts > 0 )
947 assert(sepa !=
NULL);
964 assert(sepadata !=
NULL);
965 assert(sepadata->tcliquegraph ==
NULL);
981 assert(sepadata !=
NULL);
984 if( sepadata->tcliquegraph !=
NULL )
988 assert(sepadata->tcliquegraph ==
NULL);
989 sepadata->tcliquegraphloaded =
FALSE;
1051 sepadata->tcliquegraph =
NULL;
1052 sepadata->scip = scip;
1053 sepadata->sol =
NULL;
1054 sepadata->varsolvals =
NULL;
1055 sepadata->ncalls = 0;
1056 sepadata->ncuts = 0;
1057 sepadata->tcliquegraphloaded =
FALSE;
1062 sepaExeclpClique, sepaExecsolClique,
1065 assert(sepa !=
NULL);
1066 sepadata->sepa = sepa;
1075 "separating/clique/scaleval",
1076 "factor for scaling weights",
1079 "separating/clique/maxtreenodes",
1080 "maximal number of nodes in branch and bound tree (-1: no limit)",
1083 "separating/clique/backtrackfreq",
1084 "frequency for premature backtracking up to tree level 1 (0: no backtracking)",
1087 "separating/clique/maxsepacuts",
1088 "maximal number of clique cuts separated per separation round (-1: no limit)",
1091 "separating/clique/maxzeroextensions",
1092 "maximal number of zero-valued variables extending the clique (-1: no limit)",
1095 "separating/clique/cliquetablemem",
1096 "maximal memory size of dense clique table (in kb)",
1099 "separating/clique/cliquedensity",
1100 "minimal density of cliques to use a dense clique table",
enum SCIP_Result SCIP_RESULT
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
enum TCLIQUE_Status TCLIQUE_STATUS
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define DEFAULT_BACKTRACKFREQ
static SCIP_RETCODE loadTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_RETCODE newsolCliqueAddRow(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int ncliquenodes, int *cliquenodes, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPincludeSepaClique(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
static SCIP_RETCODE tcliquegraphConstructCliqueTable(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_Real cliquetablemem, SCIP_Real cliquedensity)
#define SCIPfreeBlockMemory(scip, ptr)
static TCLIQUE_GETNNODES(tcliqueGetnnodesClique)
static TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
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)
static SCIP_DECL_SEPAFREE(sepaFreeClique)
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
static SCIP_RETCODE tcliquegraphEnsureCliqueidsSize(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int num)
static SCIP_RETCODE tcliquegraphCreate(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
static SCIP_Bool nodesHaveCommonClique(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
#define DEFAULT_CLIQUEDENSITY
static void updateTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
static TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
#define SEPA_MAXBOUNDDIST
static SCIP_DECL_SEPAEXECSOL(sepaExecsolClique)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
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)
static TCLIQUE_NEWSOL(tcliqueNewsolClique)
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
static SCIP_RETCODE tcliquegraphFree(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
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_CLIQUETABLE * cliquetable
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
#define SCIPallocBufferArray(scip, ptr, num)
public data structures and miscellaneous methods
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXZEROEXTENSIONS
static SCIP_DECL_SEPACOPY(sepaCopyClique)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
static TCLIQUE_ISEDGE(tcliqueIsedgeClique)
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)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
#define SCIPallocMemoryArray(scip, ptr, num)
int SCIPgetNBinVars(SCIP *scip)
static const SCIP_Real density
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
static SCIP_RETCODE tcliquegraphAddNode(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph, SCIP_VAR *var, SCIP_Bool value, int *nodeidx)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
static SCIP_RETCODE tcliquegraphAddCliqueVars(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph, int **cliquegraphidx)
void SCIProwChgRank(SCIP_ROW *row, int rank)
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
int SCIPgetNCliques(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
static SCIP_DECL_SEPAEXECLP(sepaExeclpClique)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
#define BMSclearMemoryArray(ptr, num)
#define DEFAULT_MAXTREENODES
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
#define SCIPfreeMemoryArrayNull(scip, ptr)
#define DEFAULT_CLIQUETABLEMEM
static SCIP_DECL_SEPAEXITSOL(sepaExitsolClique)
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)
struct SCIP_SepaData SCIP_SEPADATA
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
int SCIPcliqueGetId(SCIP_CLIQUE *clique)