dec_dbscan.cpp
Go to the documentation of this file.
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58 #define DEC_FREQCALLROUND 1 /**< frequency the detector gets called in detection loop, i.e. it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0 */
61 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
62 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /**< last round the detector gets called while detecting the original problem */
63 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
68 #define DEC_SKIP FALSE /**< should detector be skipped if other detectors found decompositions */
69 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
195 /** are there conss and vars to be included by the graph and have the conss common vars included by the graph */
297 SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::JOHNSON, gcg::WEIGHT_TYPE::DIST));
308 SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::INTERSECTION, gcg::WEIGHT_TYPE::DIST));
319 SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::JACCARD, gcg::WEIGHT_TYPE::DIST));
330 SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::COSINE, gcg::WEIGHT_TYPE::DIST));
341 SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::SIMPSON, gcg::WEIGHT_TYPE::DIST));
364 epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
375 SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 2 * nMaxPartialdecs) );
404 SCIP_CALL( graph->computePartitionDBSCANForPartialGraph(partialdecdetectiondata->detprobdata, partialdec, eps, detectordata->postprocenable) );
411 // skip the case if we have too many blocks (it means we must increase eps) or if the clustering is the same as the last one
412 if( n_blocks > max_blocks || n_blocks == 0 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
421 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
425 SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &decomp1, &decomp2, partialdecdetectiondata->detprobdata));
447 createddecomps[j]->addClockTime(clockTimes1[i] / ncreateddecomps + clockTimes2[i] / ncreateddecomps + epstime / 2.0);
456 SCIP_CALL( SCIPreallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
466 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d partialdecs found.\n", detectordata->n_similarities, nnewpartialdecs);
467 SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "DBSCAN Runtime: graphs: %.2lf, dbscan: %.2lf. \n", elapsed_graphs, elapsed_dbscan);
550 SCIP_CALL( DECincludeDetector(scip, DEC_DETECTORNAME, DEC_DECCHAR, DEC_DESC, DEC_FREQCALLROUND, DEC_MAXCALLROUND, DEC_MINCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_ENABLED, DEC_ENABLEDFINISHING, DEC_ENABLEDPOSTPROCESSING, DEC_SKIP, DEC_USEFULRECALL,
551 detectordata, freeDBSCAN, initDBSCAN, exitDBSCAN, propagatePartialdecDBSCAN, finishPartialdecDBSCAN, detectorPostprocessPartialdecDBSCAN, setParamAggressiveDBSCAN, setParamDefaultDBSCAN, setParamFastDBSCAN) );
554 SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/dbscan/niterations", "Number of iterations to run dbscan with different eps.", &detectordata->n_iterations, FALSE, DEFAULT_N_ITERATIONS, 11, 1001, NULL, NULL) );
555 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/johson", "Enable johson distance measure.", &detectordata->johnsonenable, FALSE, DEFAULT_JOHNSON_ENABLE, NULL, NULL ) );
556 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/intersection", "Enable intersection distance measure.", &detectordata->intersectionenable, FALSE, DEFAULT_INTERSECTION_ENABLE, NULL, NULL ) );
557 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/jaccard", "Enable jaccard distance measure.", &detectordata->jaccardenable, FALSE, DEFAULT_JACCARD_ENABLE, NULL, NULL) );
558 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/cosine", "Enable cosine distance measure.", &detectordata->cosineenable, FALSE, DEFAULT_COSINE_ENABLE, NULL, NULL) );
559 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/simpson", "Enable simpson distance measure.", &detectordata->simpsonenable, FALSE, DEFAULT_SIMPSON_ENABLE, NULL, NULL ) );
560 SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/postprocenable", "Enable post-processing step.", &detectordata->postprocenable, FALSE, DEFAULT_POSTPROC_ENABLE, NULL, NULL ) );
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
Definition: cons_decomp.cpp:2618
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4198
miscellaneous matrixgraph methods for structure detection
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
Definition: class_partialdecomp.cpp:4721
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: rowgraph_def.h:131
virtual SCIP_RETCODE getNBlocks(int &_n_blocks)
Definition: rowgraph_weighted_def.h:1299
#define detectorPostprocessPartialdecDBSCAN
Definition: dec_dbscan.cpp:479
virtual SCIP_RETCODE nonClustered(int &_non_cl)
Definition: rowgraph_weighted_def.h:1306
A row graph where each row is a node and rows are adjacent if they share a variable....
virtual SCIP_RETCODE computePartitionDBSCANForPartialGraph(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, double eps, bool postprocenable)
Definition: weights.h:41
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultDBSCAN)
Definition: dec_dbscan.cpp:498
static bool graphCompletible(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
Definition: dec_dbscan.cpp:197
static std::vector< double > getEpsList(int length, double mid, bool isintersection)
Definition: dec_dbscan.cpp:106
SCIP_RETCODE SCIPincludeDetectorDBSCAN(SCIP *scip)
Definition: dec_dbscan.cpp:537
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
Definition: cons_decomp.cpp:2609
Definition: rowgraph_weighted.h:63
const int * getOpenconss()
Gets array containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4247
Definition: class_detprobdata.h:106
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
Definition: rowgraph_weighted_def.h:220
detector for diagonal (bordered) structures via DBSCAN clustering algorithm
Definition: graph_gcg.h:57
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDBSCAN)
Definition: dec_dbscan.cpp:482
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
Definition: class_detprobdata.cpp:854
SCIP_RETCODE DECincludeDetector(SCIP *scip, const char *name, const char decchar, const char *description, int freqCallRound, int maxCallRound, int minCallRound, int freqCallRoundOriginal, int maxCallRoundOriginal, int minCallRoundOriginal, int priority, SCIP_Bool enabled, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, DEC_DETECTORDATA *detectordata, DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATEPARTIALDEC((*propagatePartialdecDetector)), DEC_DECL_FINISHPARTIALDEC((*finishPartialdecDetector)), DEC_DECL_POSTPROCESSPARTIALDEC((*postprocessPartialdecDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
Definition: cons_decomp.cpp:3041
Implementation of the graph which supports both node and edge weights.
int getNOpenconss()
Gets size of vector containing constraints not assigned yet.
Definition: class_partialdecomp.cpp:4192
Definition: dec_compgreedily.cpp:73
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
Definition: class_detprobdata.cpp:963
const int * getOpenvars()
Gets array containing variables not assigned yet.
Definition: class_partialdecomp.cpp:4259
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecDBSCAN)
Definition: dec_dbscan.cpp:249