Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_dbscan.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file dec_dbscan.cpp
29  * @ingroup DETECTORS
30  * @brief detector DBSCAN
31  * @author Igor Pesic
32  *
33  * @note requires package to be installed: GSL library, requires flag to be set: `GSL=true`
34  *
35  * This detector performs DBSCAN clustering.
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 #include <time.h> // for measuring time performance
40 #include <string>
41 #include "dec_dbscan.h"
42 #include "cons_decomp.h"
43 #include "graph/matrixgraph.h"
45 #include "graph/graph_gcg.h"
46 #include "scip/clock.h"
47 #include "iostream"
48 
50 using gcg::Weights;
51 using gcg::GraphGCG;
52 
53 
54 /* constraint handler properties */
55 #define DEC_DETECTORNAME "dbscan" /**< name of detector */
56 #define DEC_DESC "detector based on DBSCAN clustering" /**< description of detector */
57 #define DEC_PRIORITY 901 /**< priority of the constraint handler for separation */
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 */
59 #define DEC_MAXCALLROUND INT_MAX /**< last round the detector gets called */
60 #define DEC_MINCALLROUND 0 /**< first round the detector gets called */
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 */
64 #define DEC_DECCHAR 'D' /**< display character of detector */
65 #define DEC_ENABLED FALSE /**< should the detection be enabled */
66 #define DEC_ENABLEDFINISHING FALSE /**< should the finishing be enabled */
67 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the postprocessing be enabled */
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 */
70 
71 
72 /* Default parameter settings*/
73 #define DEFAULT_N_ITERATIONS 51
74 #define DEFAULT_JOHNSON_ENABLE true
75 #define DEFAULT_INTERSECTION_ENABLE false
76 #define DEFAULT_JACCARD_ENABLE false
77 #define DEFAULT_COSINE_ENABLE false
78 #define DEFAULT_SIMPSON_ENABLE false
79 #define DEFAULT_POSTPROC_ENABLE true
80 #define MAX_N_BLOCKS 100
81 
82 /*
83  * Data structures
84  */
85 
86 /** detector handler data */
87 struct DEC_DetectorData
88 {
89  SCIP_RESULT result; /**< result pointer to indicate success or failure */
90  SCIP_Bool found;
92  int n_similarities; /**< number of active similarities */
93  SCIP_Bool johnsonenable;
94  SCIP_Bool intersectionenable;
95  SCIP_Bool jaccardenable;
96  SCIP_Bool cosineenable;
97  SCIP_Bool simpsonenable;
98  SCIP_Bool postprocenable;
99 };
100 
101 
102 /*
103  * Local methods
104  */
105 
106 static std::vector<double> getEpsList(int length, double mid, bool isintersection)
107 {
108  int n1, n2;
109  if(isintersection)
110  {
111  n1 = (int) round((length+1) / 2.0);
112  n2 = n1;
113  }
114  else
115  {
116  n2 = (int) round((length+1) / 4.0);
117  n1 = abs(length - n2) + 1;
118  }
119 
120  double s = mid;
121  double end1 = mid + 0.9; // lower boundary
122  double end2 = mid + 0.4; // upper boundary
123 
124  double q1 = pow(end1/s, 1.0/(double)(n1-1));
125  double q2 = pow(end2/s, 1.0/(double)(n2-1));
126 
127  std::vector<double> geom_seq1(n1-1);
128  std::vector<double> geom_seq2(n2);
129 
130  int j = 0;
131  for(int i = n1 - 1; i > 0; i--)
132  {
133  geom_seq1[j] = 2*s-s*pow(q1, (double)i);
134  j++;
135  }
136  for(int i = 0; i < n2; i++)
137  {
138  geom_seq2[i] = s*pow(q2, (double)i);
139  }
140 
141  geom_seq1.insert( geom_seq1.end(), geom_seq2.begin(), geom_seq2.end() );
142 
143  assert((int)geom_seq1.size() == length);
144 
145  return geom_seq1;
146 }
147 
148 /*
149  * detector callback methods
150  */
151 
152 /** destructor of detector to free user data (called when GCG is exiting) */
153 static
155 {
156  DEC_DETECTORDATA* detectordata;
157 
158  assert(scip != NULL);
159 
160  detectordata = DECdetectorGetData(detector);
161  assert(detectordata != NULL);
162  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
163 
164  SCIPfreeMemory(scip, &detectordata);
165 
166  return SCIP_OKAY;
167 }
168 
169 /** destructor of detector to free detector data (called before the solving process begins) */
170 static
172 {
173  return SCIP_OKAY;
174 }
175 
176 
177 /** detection initialization function of detector (called before solving is about to begin) */
178 static
180 { /*lint --e{715}*/
181 
182  DEC_DETECTORDATA* detectordata;
183  assert(scip != NULL);
184 
185 
186  detectordata = DECdetectorGetData(detector);
187  assert(detectordata != NULL);
188  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
189 
190  detectordata->n_similarities = -1;
191  detectordata->found = FALSE;
192  return SCIP_OKAY;
193 }
194 
195 /** are there conss and vars to be included by the graph and have the conss common vars included by the graph */
196 static
198  gcg::DETPROBDATA* detprobdata,
199  gcg::PARTIALDECOMP* partialdec
200  )
201 {
202  bool completible;
203 
204  //have the open conss open vars?
205  for(int c = 0; c < partialdec->getNOpenconss() && !completible; ++c)
206  {
207  int cons = partialdec->getOpenconss()[c];
208  for(int v = 0; v < partialdec->getNOpenvars() && !completible; ++v)
209  {
210  int var = partialdec->getOpenvars()[v];
211  for(int i = 0; i < detprobdata->getNVarsForCons(cons) && !completible; ++i)
212  {
213  if(var == detprobdata->getVarsForCons(cons)[i])
214  {
215  completible = true;
216  }
217  }
218  }
219  }
220  if(!completible)
221  return false;
222 
223  //have the open conss common open vars?
224  for(int c = 0; c < partialdec->getNOpenconss(); ++c)
225  {
226  int cons1 = partialdec->getOpenconss()[c];
227  for(int d = c + 1; d < partialdec->getNOpenconss(); ++d)
228  {
229  int cons2 = partialdec->getOpenconss()[d];
230  for(int v = 0; v < detprobdata->getNVarsForCons(cons1); ++v)
231  {
232  int var1 = detprobdata->getVarsForCons(cons1)[v];
233  if(!partialdec->isVarOpenvar(var1))
234  continue;
235  for(int w = 0; w < detprobdata->getNVarsForCons(cons2); ++w)
236  {
237  int var2 = detprobdata->getVarsForCons(cons2)[w];
238  if(var1 == var2)
239  return true;
240  }
241  }
242  }
243  }
244  return false;
245 }
246 
247 
248 static
249 DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecDBSCAN)
250 { /*lint --e{715}*/
251 
252  int nnewpartialdecs;
253  gcg::PARTIALDECOMP* partialdec;
254  DEC_DETECTORDATA* detectordata = DECdetectorGetData(detector);
255  std::vector<SCIP_Real> clockTimes1; /* vector containing times in seconds */
256  std::vector<SCIP_Real> clockTimes2; /* vector containing times in seconds */
257  std::vector< RowGraphWeighted<GraphGCG>*> graphs;
258  SCIP_CLOCK* overallClock;
259 
260  assert(scip != NULL);
261  assert(detectordata != NULL);
262  *result = SCIP_DIDNOTFIND;
263 
264  SCIP_CALL_ABORT( SCIPcreateClock(scip, &overallClock) );
265  SCIP_CALL_ABORT( SCIPstartClock(scip, overallClock) );
266 
267  partialdec = partialdecdetectiondata->workonpartialdec;
268  partialdec->refineToBlocks();
269 
270  if( !graphCompletible(partialdecdetectiondata->detprobdata, partialdec) )
271  {
272  delete partialdec;
273  partialdecdetectiondata->nnewpartialdecs = 0;
274  SCIP_CALL_ABORT( SCIPstopClock(scip, overallClock) );
275  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, overallClock);
276  SCIP_CALL_ABORT(SCIPfreeClock(scip, &overallClock) );
277  *result = SCIP_SUCCESS;
278  return SCIP_OKAY;
279  }
280 
281  Weights w(1, 1, 1, 1, 1, 1);
282 
283  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting DBSCAN structure:");
284 
285  time_t start, cp0, d_s, d_e;
286  time(&start);
287 
288  std::vector<std::string> sim;
289  SCIP_CLOCK* temporaryClock;
290 
291  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
292 
293  if( detectordata->johnsonenable )
294  {
295  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
297  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::JOHNSON, gcg::WEIGHT_TYPE::DIST));
298  graphs.push_back(g);
299  sim.emplace_back("Johnson");
300  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
301  clockTimes1.push_back(SCIPgetClockTime( scip, temporaryClock));
302  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
303  }
304  if( detectordata->intersectionenable )
305  {
306  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
308  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::INTERSECTION, gcg::WEIGHT_TYPE::DIST));
309  graphs.push_back(g);
310  sim.emplace_back("Intersection");
311  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
312  clockTimes1.push_back(SCIPgetClockTime( scip, temporaryClock));
313  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
314  }
315  if( detectordata->jaccardenable )
316  {
317  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
319  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::JACCARD, gcg::WEIGHT_TYPE::DIST));
320  graphs.push_back(g);
321  sim.emplace_back("Jaccard");
322  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
323  clockTimes1.push_back(SCIPgetClockTime( scip, temporaryClock));
324  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
325  }
326  if( detectordata->cosineenable )
327  {
328  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
330  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::COSINE, gcg::WEIGHT_TYPE::DIST));
331  graphs.push_back(g);
332  sim.emplace_back("Cosine");
333  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
334  clockTimes1.push_back(SCIPgetClockTime( scip, temporaryClock));
335  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
336  }
337  if( detectordata->simpsonenable )
338  {
339  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
341  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::SIMPSON, gcg::WEIGHT_TYPE::DIST));
342  graphs.push_back(g);
343  sim.emplace_back("Simspon");
344  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
345  clockTimes1.push_back(SCIPgetClockTime( scip, temporaryClock));
346  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
347  }
348  time(&cp0);
349  detectordata->n_similarities = (int) graphs.size();
350 
351  double q = 10; // quantile to search for the percentile needed for the mid of the eps list
352  std::vector<double> mids(graphs.size()); // middle values for each eps list
353  std::vector<std::vector<double> > epsLists(graphs.size());
354  for( int i = 0; i < (int)graphs.size(); i++ )
355  {
356  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
357  mids[i] = graphs.at(i)->getEdgeWeightPercentile(q);
358  if( i == 1 && detectordata->intersectionenable )
359  {
360  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], true); // case for intersection
361  }
362  else
363  {
364  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
365  }
366  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
367  clockTimes2.push_back(SCIPgetClockTime( scip, temporaryClock));
368  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock) );
369  }
370 
371  int nMaxPartialdecs = detectordata->n_iterations * graphs.size();
372  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
373  char decinfo[SCIP_MAXSTRLEN];
374 
375  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 2 * nMaxPartialdecs) );
376  nnewpartialdecs = 0;
377  time(&d_s);
378  for( int i = 0; i < (int)graphs.size(); i++ )
379  {
380  RowGraphWeighted<GraphGCG>* graph = graphs.at(i);
381  int old_n_blocks = -1;
382  int old_non_cl = -1;
383  std::vector<gcg::PARTIALDECOMP*> createddecomps;
384  std::vector<std::pair<double, SCIP_Real>> clockTimes3;
385  gcg::PARTIALDECOMP *decomp1 = NULL, *decomp2 = NULL;
386 
387  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
388  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity:", sim[i].c_str());
389  createddecomps.reserve(2 * epsLists[i].size());
390  clockTimes3.reserve(epsLists[i].size());
391 
392  for( double eps : epsLists[i] )
393  {
394  if( eps <= 0.0 )
395  {
396  continue;
397  }
398  if( eps >= 1.0 )
399  {
400  break;
401  }
402 
403  // run DBSCAN with different eps
404  SCIP_CALL( graph->computePartitionDBSCANForPartialGraph(partialdecdetectiondata->detprobdata, partialdec, eps, detectordata->postprocenable) );
405 
406  int n_blocks;
407  int non_cl;
408  SCIP_CALL( graph->getNBlocks(n_blocks) );
409  SCIP_CALL( graph->nonClustered(non_cl) );
410 
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) )
413  {
414  continue;
415  }
416  // stop. eps is already too big
417  if( n_blocks == 1 && non_cl == 0)
418  {
419  break;
420  }
421  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
422  old_n_blocks = n_blocks;
423  old_non_cl = non_cl;
424 
425  SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &decomp1, &decomp2, partialdecdetectiondata->detprobdata));
426  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
427 
428  if( decomp1 != NULL )
429  {
430  assert(decomp2 != NULL);
431  detectordata->found = TRUE;
432  createddecomps.push_back(decomp1);
433  createddecomps.push_back(decomp2);
434  clockTimes3.emplace_back(eps, SCIPgetClockTime(scip, temporaryClock));
435  }
436 
437  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
438  }
439 
440  size_t ncreateddecomps = createddecomps.size();
441  for( unsigned int j = 0; j < ncreateddecomps; ++j )
442  {
443  double eps = clockTimes3[j / 2].first;
444  SCIP_Real epstime = clockTimes3[j / 2].second;
445  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "dbscan_%s_%f", sim[i].c_str(), eps);
446  createddecomps[j]->addDetectorChainInfo(decinfo);
447  createddecomps[j]->addClockTime(clockTimes1[i] / ncreateddecomps + clockTimes2[i] / ncreateddecomps + epstime / 2.0);
448  partialdecdetectiondata->newpartialdecs[nnewpartialdecs + j] = createddecomps[j];
449  }
450  nnewpartialdecs += ncreateddecomps;
451 
452  delete graphs.at(i);
453  graphs[i] = NULL;
454  }
455 
456  SCIP_CALL( SCIPreallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
457  partialdecdetectiondata->nnewpartialdecs = nnewpartialdecs;
458  SCIP_CALL_ABORT( SCIPstopClock(scip, overallClock) );
459  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, overallClock);
460  SCIP_CALL_ABORT(SCIPfreeClock(scip, &overallClock) );
461 
462  time(&d_e);
463  double elapsed_graphs = difftime(cp0, start);
464  double elapsed_dbscan = difftime(d_e, d_s);
465 
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);
468 
469  *result = nnewpartialdecs > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
470  if( nnewpartialdecs == 0 )
471  {
472  SCIPfreeMemoryArrayNull(scip, &(partialdecdetectiondata->newpartialdecs));
473  }
474  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
475  return SCIP_OKAY;
476 }
477 
478 #define finishPartialdecDBSCAN NULL
479 #define detectorPostprocessPartialdecDBSCAN NULL
480 
481 static
482 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDBSCAN)
483 {
484  char setstr[SCIP_MAXSTRLEN];
485  const char* name = DECdetectorGetName(detector);
486 
487  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
488  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
489 
490  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
491  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
492 
493  return SCIP_OKAY;
494 }
495 
496 
497 static
498 DEC_DECL_SETPARAMDEFAULT(setParamDefaultDBSCAN)
499 {
500  char setstr[SCIP_MAXSTRLEN];
501 
502  const char* name = DECdetectorGetName(detector);
503 
504  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
505  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
506 
507  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
508  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
509 
510  return SCIP_OKAY;
511 }
512 
513 static
514 DEC_DECL_SETPARAMFAST(setParamFastDBSCAN)
515 {
516  char setstr[SCIP_MAXSTRLEN];
517 
518  const char* name = DECdetectorGetName(detector);
519 
520  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
521  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
522 
523  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
524  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
525 
526 
527  return SCIP_OKAY;
528 }
529 
530 
531 
532 /*
533  * detector specific interface methods
534  */
535 
536 /** creates the handler for xyz detector and includes it in SCIP */
538  SCIP* scip /**< SCIP data structure */
539  )
540 {
541 #if !defined(_WIN32) && !defined(_WIN64)
542  DEC_DETECTORDATA *detectordata = NULL;
543  assert(scip != NULL);
544 
545  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
546 
547  assert(detectordata != NULL);
548  detectordata->found = FALSE;
549 
551  detectordata, freeDBSCAN, initDBSCAN, exitDBSCAN, propagatePartialdecDBSCAN, finishPartialdecDBSCAN, detectorPostprocessPartialdecDBSCAN, setParamAggressiveDBSCAN, setParamDefaultDBSCAN, setParamFastDBSCAN) );
552 
553  /* add arrowheur presolver parameters */
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 ) );
561 
562 #endif
563  return SCIP_OKAY;
564 }
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_dbscan.cpp:67
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
#define DEFAULT_N_ITERATIONS
Definition: dec_dbscan.cpp:73
#define DEC_MAXCALLROUND
Definition: dec_dbscan.cpp:59
SCIP_Bool cosineenable
Definition: dec_dbscan.cpp:96
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
#define MAX_N_BLOCKS
Definition: dec_dbscan.cpp:80
miscellaneous matrixgraph methods for structure detection
#define DEFAULT_INTERSECTION_ENABLE
Definition: dec_dbscan.cpp:75
#define DEC_DETECTORNAME
Definition: dec_dbscan.cpp:55
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: rowgraph_def.h:131
#define DEC_ENABLEDFINISHING
Definition: dec_dbscan.cpp:66
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_dbscan.cpp:62
virtual SCIP_RETCODE getNBlocks(int &_n_blocks)
#define detectorPostprocessPartialdecDBSCAN
Definition: dec_dbscan.cpp:479
#define DEC_SKIP
Definition: dec_dbscan.cpp:68
virtual SCIP_RETCODE nonClustered(int &_non_cl)
#define DEFAULT_JOHNSON_ENABLE
Definition: dec_dbscan.cpp:74
A row graph where each row is a node and rows are adjacent if they share a variable....
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_dbscan.cpp:61
virtual SCIP_RETCODE computePartitionDBSCANForPartialGraph(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, double eps, bool postprocenable)
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultDBSCAN)
Definition: dec_dbscan.cpp:498
static bool graphCompletible(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
Definition: dec_dbscan.cpp:197
#define DEC_DECCHAR
Definition: dec_dbscan.cpp:64
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_dbscan.cpp:63
static std::vector< double > getEpsList(int length, double mid, bool isintersection)
Definition: dec_dbscan.cpp:106
@ INTERSECTION
SCIP_Bool found
Definition: dec_dbscan.cpp:90
static DEC_DECL_SETPARAMFAST(setParamFastDBSCAN)
Definition: dec_dbscan.cpp:514
SCIP_Bool intersectionenable
Definition: dec_dbscan.cpp:94
SCIP_RETCODE SCIPincludeDetectorDBSCAN(SCIP *scip)
Definition: dec_dbscan.cpp:537
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
void refineToBlocks()
refine partialdec with focus on blocks
#define DEC_FREQCALLROUND
Definition: dec_dbscan.cpp:58
const int * getOpenconss()
Gets array containing constraints not assigned yet.
#define DEFAULT_COSINE_ENABLE
Definition: dec_dbscan.cpp:77
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
#define DEC_MINCALLROUND
Definition: dec_dbscan.cpp:60
detector for diagonal (bordered) structures via DBSCAN clustering algorithm
static DEC_DECL_FREEDETECTOR(freeDBSCAN)
Definition: dec_dbscan.cpp:154
SCIP_RESULT result
Definition: dec_dbscan.cpp:89
#define DEFAULT_POSTPROC_ENABLE
Definition: dec_dbscan.cpp:79
class to manage partial decompositions
#define DEFAULT_SIMPSON_ENABLE
Definition: dec_dbscan.cpp:78
#define DEC_USEFULRECALL
Definition: dec_dbscan.cpp:69
SCIP_Bool postprocenable
Definition: dec_dbscan.cpp:98
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDBSCAN)
Definition: dec_dbscan.cpp:482
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
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)),)
Implementation of the graph which supports both node and edge weights.
int getNOpenconss()
Gets size of vector containing constraints not assigned yet.
#define DEC_PRIORITY
Definition: dec_dbscan.cpp:57
static DEC_DECL_INITDETECTOR(initDBSCAN)
Definition: dec_dbscan.cpp:179
SCIP_Bool johnsonenable
Definition: dec_dbscan.cpp:93
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
const int * getOpenvars()
Gets array containing variables not assigned yet.
#define DEC_ENABLED
Definition: dec_dbscan.cpp:65
#define finishPartialdecDBSCAN
Definition: dec_dbscan.cpp:478
#define DEC_DESC
Definition: dec_dbscan.cpp:56
static DEC_DECL_EXITDETECTOR(exitDBSCAN)
Definition: dec_dbscan.cpp:171
SCIP_Bool jaccardenable
Definition: dec_dbscan.cpp:95
SCIP_Bool simpsonenable
Definition: dec_dbscan.cpp:97
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecDBSCAN)
Definition: dec_dbscan.cpp:249
#define DEFAULT_JACCARD_ENABLE
Definition: dec_dbscan.cpp:76