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-2018 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 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 #include <time.h> // for measuring time performance
36 #include <string>
37 #include "dec_dbscan.h"
38 #include "cons_decomp.h"
39 #include "graph/matrixgraph.h"
41 #include "graph/graph_gcg.h"
42 #include "scip/clock.h"
43 #include "iostream"
44 
46 using gcg::Weights;
47 using gcg::GraphGCG;
48 
49 
50 /* constraint handler properties */
51 #define DEC_DETECTORNAME "dbscan"
52 #define DEC_DESC "detector based on dbscan clustering"
53 #define DEC_FREQCALLROUND 1
54 #define DEC_MAXCALLROUND INT_MAX
55 #define DEC_MINCALLROUND 0
56 #define DEC_FREQCALLROUNDORIGINAL 1
57 #define DEC_MAXCALLROUNDORIGINAL INT_MAX
58 #define DEC_MINCALLROUNDORIGINAL 0
59 #define DEC_PRIORITY 901
60 #define DEC_DECCHAR 'D'
61 #define DEC_ENABLED FALSE
62 #define DEC_ENABLEDORIGINAL FALSE
63 #define DEC_ENABLEDFINISHING FALSE
64 #define DEC_ENABLEDPOSTPROCESSING FALSE
65 #define DEC_SKIP FALSE
66 #define DEC_USEFULRECALL FALSE
67 #define DEC_LEGACYMODE FALSE
70 /* Default parameter settings*/
71 #define DEFAULT_N_ITERATIONS 51
72 #define DEFAULT_JOHNSON_ENABLE true
73 #define DEFAULT_INTERSECTION_ENABLE false
74 #define DEFAULT_JACCARD_ENABLE false
75 #define DEFAULT_COSINE_ENABLE false
76 #define DEFAULT_SIMPSON_ENABLE false
77 #define DEFAULT_POSTPROC_ENABLE true
78 #define MAX_N_BLOCKS 100
79 
80 /*
81  * Data structures
82  */
83 
85 struct DEC_DetectorData
86 {
87  std::vector< RowGraphWeighted<GraphGCG>*> *graphs;
88  SCIP_RESULT result;
89  SCIP_Bool found;
92  SCIP_Bool johnsonenable;
93  SCIP_Bool intersectionenable;
94  SCIP_Bool jaccardenable;
95  SCIP_Bool cosineenable;
96  SCIP_Bool simpsonenable;
97  SCIP_Bool postprocenable;
98 };
99 
100 
101 /*
102  * Local methods
103  */
104 
105 static std::vector<double> getEpsList(int length, double mid, bool isintersection)
106 {
107  int n1, n2;
108  if(isintersection)
109  {
110  n1 = (int) round((length+1) / 2.0);
111  n2 = n1;
112  }
113  else
114  {
115  n2 = (int) round((length+1) / 4.0);
116  n1 = abs(length - n2) + 1;
117  }
118 
119  double s = mid;
120  double end1 = mid + 0.9; // lower boundary
121  double end2 = mid + 0.4; // upper boundary
122 
123  double q1 = pow(end1/s, 1.0/(double)(n1-1));
124  double q2 = pow(end2/s, 1.0/(double)(n2-1));
125 
126  std::vector<double> geom_seq1(n1-1);
127  std::vector<double> geom_seq2(n2);
128 
129  int j = 0;
130  for(int i = n1 - 1; i > 0; i--)
131  {
132  geom_seq1[j] = 2*s-s*pow(q1, (double)i);
133  j++;
134  }
135  for(int i = 0; i < n2; i++)
136  {
137  geom_seq2[i] = s*pow(q2, (double)i);
138  }
139 
140  geom_seq1.insert( geom_seq1.end(), geom_seq2.begin(), geom_seq2.end() );
141 
142  assert((int)geom_seq1.size() == length);
143 
144  return geom_seq1;
145 }
146 
147 /*
148  * detector callback methods
149  */
150 
152 static
154 {
155  DEC_DETECTORDATA* detectordata;
156 
157  assert(scip != NULL);
158 
159  detectordata = DECdetectorGetData(detector);
160  assert(detectordata != NULL);
161  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
162 
163  SCIPfreeMemory(scip, &detectordata);
164 
165  return SCIP_OKAY;
166 }
167 
169 static
171 {
172  DEC_DETECTORDATA* detectordata;
173  assert(scip != NULL);
174 
175  detectordata = DECdetectorGetData(detector);
176  assert(detectordata != NULL);
177  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
178 
179  delete detectordata->graphs;
180 
181  return SCIP_OKAY;
182 }
183 
184 
186 static
188 { /*lint --e{715}*/
189 
190  DEC_DETECTORDATA* detectordata;
191  assert(scip != NULL);
192 
193 
194  detectordata = DECdetectorGetData(detector);
195  assert(detectordata != NULL);
196  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
197 
198  detectordata->n_similarities = -1;
199  detectordata->found = FALSE;
200  detectordata->graphs = new std::vector< RowGraphWeighted<GraphGCG>*>();
201  return SCIP_OKAY;
202 }
203 
205 static
207  gcg::Seeedpool* seeedpool,
208  gcg::Seeed* seeed
209  )
210 {
211  bool completible;
212 
213  //have the open conss open vars?
214  for(int c = 0; c < seeed->getNOpenconss() && !completible; ++c)
215  {
216  int cons = seeed->getOpenconss()[c];
217  for(int v = 0; v < seeed->getNOpenvars() && !completible; ++v)
218  {
219  int var = seeed->getOpenvars()[v];
220  for(int i = 0; i < seeedpool->getNVarsForCons(cons) && !completible; ++i)
221  {
222  if(var == seeedpool->getVarsForCons(cons)[i])
223  {
224  completible = true;
225  }
226  }
227  }
228  }
229  if(!completible)
230  return false;
231 
232  //have the open conss common open vars?
233  for(int c = 0; c < seeed->getNOpenconss(); ++c)
234  {
235  int cons1 = seeed->getOpenconss()[c];
236  for(int d = c + 1; d < seeed->getNOpenconss(); ++d)
237  {
238  int cons2 = seeed->getOpenconss()[d];
239  for(int v = 0; v < seeedpool->getNVarsForCons(cons1); ++v)
240  {
241  int var1 = seeedpool->getVarsForCons(cons1)[v];
242  if(!seeed->isVarOpenvar(var1))
243  continue;
244  for(int w = 0; w < seeedpool->getNVarsForCons(cons2); ++w)
245  {
246  int var2 = seeedpool->getVarsForCons(cons2)[w];
247  if(var1 == var2)
248  return true;
249  }
250  }
251  }
252  }
253  return false;
254 }
255 
257 static
259 { /*lint --e{715}*/
260 
261  assert(scip != NULL);
262  assert(detectordata != NULL);
263  assert(decdecomps != NULL);
264  *result = SCIP_DIDNOTFIND;
265 
266  Weights w(1, 1, 1, 1, 1, 1);
267 
268  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting DBSCAN structure:");
269 
270  time_t start, cp0, d_s, d_e;
271  time(&start);
272 
273  std::vector<std::string> sim;
274 
275 
276  if(detectordata->johnsonenable)
277  {
279  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
281  detectordata->graphs->push_back(g);
282  sim.push_back("Johnson");
283  }
284  if(detectordata->intersectionenable)
285  {
287  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
289  detectordata->graphs->push_back(g);
290  sim.push_back("Intersection");
291  }
292  if(detectordata->jaccardenable)
293  {
295  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
297  detectordata->graphs->push_back(g);
298  sim.push_back("Jaccard");
299  }
300  if(detectordata->cosineenable)
301  {
303  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
305  detectordata->graphs->push_back(g);
306  sim.push_back("Cosine");
307  }
308  if(detectordata->simpsonenable)
309  {
311  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
313  detectordata->graphs->push_back(g);
314  sim.push_back("Simspon");
315  }
316  time(&cp0);
317  detectordata->n_similarities = (int) detectordata->graphs->size();
318 
319 
320 
321  double q = 10; // quantile to search for the percentile needed for the mid of the eps list
322  std::vector<double> mids(detectordata->graphs->size()); // middle values for each eps list
323  std::vector<std::vector<double> > epsLists(detectordata->graphs->size());
324  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
325  {
326  mids[i] = detectordata->graphs->at(i)->getEdgeWeightPercentile(q);
327  if(i == 1 && detectordata->intersectionenable)
328  {
329  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], true); // case for intersection
330  }
331  else
332  {
333  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
334  }
335 
336  }
337 
338 
339  int max_ndecs = detectordata->n_iterations * detectordata->graphs->size();
340  SCIP_CALL( SCIPallocMemoryArray(scip, decdecomps, max_ndecs) );
341 
342 
343  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
344  int n_decs_found = 0;
345 
346  *ndecdecomps = 0;
347  time(&d_s);
348  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
349  {
350  RowGraphWeighted<GraphGCG>* graph = detectordata->graphs->at(i);
351  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity:", sim[i].c_str());
352  int old_n_blocks = -1;
353  int old_non_cl = -1;
354  for(int j = 0; j < (int)epsLists[i].size() ; j++ )
355  {
356  double eps = epsLists[i][j];
357  if(eps <= 0.0)
358  {
359  continue;
360  }
361  if(eps >= 1.0)
362  {
363  break;
364  }
365 
366  // run DBSCAN with different eps
367  SCIP_CALL( graph->computePartitionDBSCAN(eps, detectordata->postprocenable) );
368 
369  int n_blocks;
370  SCIP_CALL( graph->getNBlocks(n_blocks) );
371  int non_cl;
372  SCIP_CALL( graph->nonClustered(non_cl) );
373 
374  // 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
375  if( n_blocks > max_blocks || n_blocks == 0 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
376  {
377  continue;
378  }
379  // stop. eps is already too big
380  if( n_blocks == 1 && non_cl == 0)
381  {
382  break;
383  }
384  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
385  old_n_blocks = n_blocks;
386  old_non_cl = non_cl;
387 
388 
389  SCIP_CALL( graph->createDecompFromPartition(&(*decdecomps)[n_decs_found]) );
390 
391  auto check = DECdecompGetNLinkingvars((*decdecomps)[n_decs_found]);
392  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Link Vars: %d. ", check);
393 
394  if( (*decdecomps)[n_decs_found] != NULL )
395  {
396  *ndecdecomps += 1;
397  ++n_decs_found;
398  detectordata->found = TRUE;
399  }
400  }
401  delete detectordata->graphs->at(i);
402  detectordata->graphs->at(i) = NULL;
403  }
404 
405  // empty the graphs vector
406  //std::vector< RowGraphWeighted<GraphGCG>*>().swap(detectordata->graphs);
407  detectordata->graphs->clear();
408  time(&d_e);
409  double elapsed_graphs = difftime(cp0, start);
410  double elapsed_dbscan = difftime(d_e, d_s);
411 
412  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d decompositions found.\n", detectordata->n_similarities, *ndecdecomps);
413  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "DBSCAN Runtime: graphs: %.2lf, dbscan: %.2lf. \n", elapsed_graphs, elapsed_dbscan);
414 
415  SCIP_CALL( SCIPreallocMemoryArray(scip, decdecomps, *ndecdecomps) );
416 
417  *result = *ndecdecomps > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
418  if( *ndecdecomps == 0 )
419  {
420  SCIPfreeMemoryArrayNull(scip, decdecomps);
421  }
422  return SCIP_OKAY;
423 }
424 
425 static
426 DEC_DECL_PROPAGATESEEED(propagateSeeedDBSCAN)
427 { /*lint --e{715}*/
428 
429  int nNewSeeeds;
430  gcg::Seeed* seeed;
431  gcg::Seeed** newSeeeds;
432  DEC_DETECTORDATA* detectordata = DECdetectorGetData(detector);
433  std::vector<SCIP_Real> clockTimes1;
434  std::vector<SCIP_Real> clockTimes2;
435  std::vector<SCIP_Real> clockTimes3;
438  assert(scip != NULL);
439  assert(detectordata != NULL);
440  *result = SCIP_DIDNOTFIND;
441 
442  seeed = seeedPropagationData->seeedToPropagate;
443  seeed->refineToBlocks();
444  if(!graphCompletible(seeedPropagationData->seeedpool, seeed))
445  {
446  delete seeed;
447  seeedPropagationData->nNewSeeeds = 0;
448  *result = SCIP_SUCCESS;
449  return SCIP_OKAY;
450  }
451 
452  Weights w(1, 1, 1, 1, 1, 1);
453 
454  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting DBSCAN structure:");
455 
456  time_t start, cp0, d_s, d_e;
457  time(&start);
458 
459  std::vector<std::string> sim;
460 
461  SCIP_CLOCK* temporaryClock;
462  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
463 
464  if(detectordata->johnsonenable)
465  {
466  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
468  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::JOHNSON, gcg::WEIGHT_TYPE::DIST));
469  detectordata->graphs->push_back(g);
470  sim.push_back("Johnson");
471  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
472  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
473  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
474  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
475  }
476  if(detectordata->intersectionenable)
477  {
478  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
480  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::INTERSECTION, gcg::WEIGHT_TYPE::DIST));
481  detectordata->graphs->push_back(g);
482  sim.push_back("Intersection");
483  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
484  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
485  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
486  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
487  }
488  if(detectordata->jaccardenable)
489  {
490  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
492  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::JACCARD, gcg::WEIGHT_TYPE::DIST));
493  detectordata->graphs->push_back(g);
494  sim.push_back("Jaccard");
495  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
496  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
497  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
498  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
499  }
500  if(detectordata->cosineenable)
501  {
502  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
504  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::COSINE, gcg::WEIGHT_TYPE::DIST));
505  detectordata->graphs->push_back(g);
506  sim.push_back("Cosine");
507  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
508  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
509  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
510  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
511  }
512  if(detectordata->simpsonenable)
513  {
514  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
516  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::SIMPSON, gcg::WEIGHT_TYPE::DIST));
517  detectordata->graphs->push_back(g);
518  sim.push_back("Simspon");
519  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
520  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
521  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
522  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
523  }
524  time(&cp0);
525 
526  detectordata->n_similarities = (int) detectordata->graphs->size();
527 
528  double q = 10; // quantile to search for the percentile needed for the mid of the eps list
529  std::vector<double> mids(detectordata->graphs->size()); // middle values for each eps list
530  std::vector<std::vector<double> > epsLists(detectordata->graphs->size());
531  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
532  {
533  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
534  mids[i] = detectordata->graphs->at(i)->getEdgeWeightPercentile(q);
535  if(i == 1 && detectordata->intersectionenable)
536  {
537  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], true); // case for intersection
538  }
539  else
540  {
541  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
542  }
543  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
544  clockTimes2.push_back(SCIPclockGetTime(temporaryClock));
545  clockTimes2.push_back(SCIPclockGetTime(temporaryClock));
546  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
547  }
548 
549 
550  int nMaxSeeeds = detectordata->n_iterations * detectordata->graphs->size();
551  SCIP_CALL( SCIPallocMemoryArray(scip, &(newSeeeds), 2 * nMaxSeeeds) );
552 
553 
554  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
555  int n_seeeds_found = 0;
556 
557  nNewSeeeds = 0;
558  time(&d_s);
559  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
560  {
561  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
562  RowGraphWeighted<GraphGCG>* graph = detectordata->graphs->at(i);
563  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity:", sim[i].c_str());
564  int old_n_blocks = -1;
565  int old_non_cl = -1;
566  for(int j = 0; j < (int)epsLists[i].size() ; j++ )
567  {
568  double eps = epsLists[i][j];
569  if(eps <= 0.0)
570  {
571  continue;
572  }
573  if(eps >= 1.0)
574  {
575  break;
576  }
577 
578  // run DBSCAN with different eps
579  SCIP_CALL( graph->computePartitionDBSCANForPartialGraph(seeedPropagationData->seeedpool, seeed, eps, detectordata->postprocenable) );
580 
581  int n_blocks;
582  SCIP_CALL( graph->getNBlocks(n_blocks) );
583  int non_cl;
584  SCIP_CALL( graph->nonClustered(non_cl) );
585 
586  // 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
587  if( n_blocks > max_blocks || n_blocks == 0 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
588  {
589  continue;
590  }
591  // stop. eps is already too big
592  if( n_blocks == 1 && non_cl == 0)
593  {
594  break;
595  }
596  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
597  old_n_blocks = n_blocks;
598  old_non_cl = non_cl;
599 
600 
601  SCIP_CALL( graph->createSeeedFromPartition(seeed, &newSeeeds[n_seeeds_found], &newSeeeds[n_seeeds_found+1], seeedPropagationData->seeedpool));
602 
603  if((newSeeeds)[n_seeeds_found] != NULL)
604  {
605  nNewSeeeds += 2;
606  detectordata->found = TRUE;
607  }
608  n_seeeds_found += 2;
609 
610  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
611  clockTimes3.push_back(SCIPclockGetTime(temporaryClock));
612  clockTimes3.push_back(SCIPclockGetTime(temporaryClock));
613  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
614  }
615  delete detectordata->graphs->at(i);
616  detectordata->graphs->at(i) = NULL;
617  }
618 
619  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), nNewSeeeds) );
620  seeedPropagationData->nNewSeeeds = nNewSeeeds;
621  for(int j = 0, s = 0; s < nNewSeeeds; ++j)
622  {
623  if(newSeeeds[j] != NULL)
624  {
625  char decinfo[SCIP_MAXSTRLEN];
626 
627  seeedPropagationData->newSeeeds[s] = newSeeeds[j];
628  seeedPropagationData->newSeeeds[s]->addClockTime(clockTimes1[j] + clockTimes2[j] + clockTimes3[j]);
629  seeedPropagationData->newSeeeds[s]->setDetectorPropagated(detector);
630  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "dbscan");
631  seeedPropagationData->newSeeeds[s]->addDetectorChainInfo(decinfo);
632 
633  ++s;
634  }
635  }
636  SCIPfreeMemoryArray(scip, &newSeeeds);
637 
638  // empty the graphs vector
639  //std::vector< RowGraphWeighted<GraphGCG>*>().swap(detectordata->graphs);
640  detectordata->graphs->clear();
641  time(&d_e);
642  double elapsed_graphs = difftime(cp0, start);
643  double elapsed_dbscan = difftime(d_e, d_s);
644 
645  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d seeeds found.\n", detectordata->n_similarities, nNewSeeeds);
646  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "DBSCAN Runtime: graphs: %.2lf, dbscan: %.2lf. \n", elapsed_graphs, elapsed_dbscan);
647 
648 
649  *result = nNewSeeeds > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
650  if( nNewSeeeds == 0 )
651  {
652  SCIPfreeMemoryArrayNull(scip, &(seeedPropagationData->newSeeeds));
653  }
654  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
655  return SCIP_OKAY;
656 }
657 
658 #define finishSeeedDBSCAN NULL
659 #define detectorPostprocessSeeedDBSCAN NULL
660 
661 static
662 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDBSCAN)
663 {
664  char setstr[SCIP_MAXSTRLEN];
665  const char* name = DECdetectorGetName(detector);
666 
667  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
668  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
669 
670  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
671  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
672 
673  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
674  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
675 
676  return SCIP_OKAY;
677 
678 }
679 
680 
681 static
682 DEC_DECL_SETPARAMDEFAULT(setParamDefaultDBSCAN)
683 {
684  char setstr[SCIP_MAXSTRLEN];
685 
686  const char* name = DECdetectorGetName(detector);
687 
688  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
689  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
690 
691  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
692  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDORIGINAL) );
693 
694  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
695  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
696 
697  return SCIP_OKAY;
698 
699 }
700 
701 static
702 DEC_DECL_SETPARAMFAST(setParamFastDBSCAN)
703 {
704  char setstr[SCIP_MAXSTRLEN];
705 
706  const char* name = DECdetectorGetName(detector);
707 
708  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
709  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
710 
711  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
712  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
713 
714  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
715  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
716 
717 
718  return SCIP_OKAY;
719 
720 }
721 
722 
723 
724 /*
725  * detector specific interface methods
726  */
727 
730  SCIP* scip
731  )
732 {
733 #if !defined(_WIN32) && !defined(_WIN64)
734  DEC_DETECTORDATA *detectordata = NULL;
735  assert(scip != NULL);
736 
737  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
738 
739  assert(detectordata != NULL);
740  detectordata->found = FALSE;
741 
743  detectordata, detectDBSCAN, freeDBSCAN, initDBSCAN, exitDBSCAN, propagateSeeedDBSCAN, NULL, NULL, finishSeeedDBSCAN, detectorPostprocessSeeedDBSCAN, setParamAggressiveDBSCAN, setParamDefaultDBSCAN, setParamFastDBSCAN) );
744 
745  /* add arrowheur presolver parameters */
746  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) );
747  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/johson", "Enable johson distance measure.", &detectordata->johnsonenable, FALSE, DEFAULT_JOHNSON_ENABLE, NULL, NULL ) );
748  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/intersection", "Enable intersection distance measure.", &detectordata->intersectionenable, FALSE, DEFAULT_INTERSECTION_ENABLE, NULL, NULL ) );
749  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/jaccard", "Enable jaccard distance measure.", &detectordata->jaccardenable, FALSE, DEFAULT_JACCARD_ENABLE, NULL, NULL) );
750  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/cosine", "Enable cosine distance measure.", &detectordata->cosineenable, FALSE, DEFAULT_COSINE_ENABLE, NULL, NULL) );
751  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/simpson", "Enable simpson distance measure.", &detectordata->simpsonenable, FALSE, DEFAULT_SIMPSON_ENABLE, NULL, NULL ) );
752  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/dbscan/postprocenable", "Enable post-processing step..", &detectordata->postprocenable, FALSE, DEFAULT_POSTPROC_ENABLE, NULL, NULL ) );
753 
754 #endif
755  return SCIP_OKAY;
756 }
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
miscellaneous matrixgraph methods for structure detection
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
#define DEFAULT_JOHNSON_ENABLE
Definition: dec_dbscan.cpp:72
static bool graphCompletible(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed)
Definition: dec_dbscan.cpp:206
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_dbscan.cpp:56
const int * getOpenconss()
returns array containing constraints not assigned yet
#define DEFAULT_JACCARD_ENABLE
Definition: dec_dbscan.cpp:74
#define MAX_N_BLOCKS
Definition: dec_dbscan.cpp:78
TCLIQUE_GRAPH * graph
Definition: dec_staircase.c:87
#define DEC_DECCHAR
Definition: dec_dbscan.cpp:60
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_dbscan.cpp:64
virtual SCIP_RETCODE getNBlocks(int &_n_blocks)
#define DEFAULT_N_ITERATIONS
Definition: dec_dbscan.cpp:71
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define DEFAULT_INTERSECTION_ENABLE
Definition: dec_dbscan.cpp:73
#define DEC_MAXCALLROUND
Definition: dec_dbscan.cpp:54
#define DEC_DETECTORNAME
Definition: dec_dbscan.cpp:51
#define DEC_ENABLEDFINISHING
Definition: dec_dbscan.cpp:63
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_dbscan.cpp:57
SCIP_Bool cosineenable
Definition: dec_dbscan.cpp:95
virtual SCIP_RETCODE nonClustered(int &_non_cl)
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_dbscan.cpp:58
#define DEC_SKIP
Definition: dec_dbscan.cpp:65
static DEC_DECL_DETECTSTRUCTURE(detectDBSCAN)
Definition: dec_dbscan.cpp:258
SCIP_RETCODE SCIPincludeDetectorDBSCAN(SCIP *scip)
Definition: dec_dbscan.cpp:729
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultDBSCAN)
Definition: dec_dbscan.cpp:682
int getNOpenvars()
returns size of vector containing variables not assigned yet
int DECdecompGetNLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1043
virtual SCIP_RETCODE createSeeedFromPartition(Seeed *oldSeeed, Seeed **firstSeeed, Seeed **secondSeeed, Seeedpool *seeedpool)
Definition: rowgraph_def.h:131
static std::vector< double > getEpsList(int length, double mid, bool isintersection)
Definition: dec_dbscan.cpp:105
bool isVarOpenvar(int var)
returns true if the var is an open var
Implementation of the graph which supports both node and edge weights.
static DEC_DECL_SETPARAMFAST(setParamFastDBSCAN)
Definition: dec_dbscan.cpp:702
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
SCIP_Bool found
Definition: dec_dbscan.cpp:89
virtual SCIP_RETCODE createFromPartialMatrix(Seeedpool *seeedpool, Seeed *seeed, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
#define DEFAULT_COSINE_ENABLE
Definition: dec_dbscan.cpp:75
#define DEC_USEFULRECALL
Definition: dec_dbscan.cpp:66
#define DEC_MINCALLROUND
Definition: dec_dbscan.cpp:55
#define detectorPostprocessSeeedDBSCAN
Definition: dec_dbscan.cpp:659
#define DEC_PRIORITY
Definition: dec_dbscan.cpp:59
#define DEC_FREQCALLROUND
Definition: dec_dbscan.cpp:53
static DEC_DECL_INITDETECTOR(initDBSCAN)
Definition: dec_dbscan.cpp:187
A row graph where each row is a node and rows are adjacent if they share a variable. The edges are weighted according to specified similarity measure.
SCIP_Bool intersectionenable
Definition: dec_dbscan.cpp:93
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 enabledOriginal, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, SCIP_Bool legacymode, DEC_DETECTORDATA *detectordata, DEC_DECL_DETECTSTRUCTURE((*detectStructure)), DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATESEEED((*propagateSeeedDetector)), DEC_DECL_PROPAGATEFROMTOOLBOX((*propagateFromToolboxDetector)), DEC_DECL_FINISHFROMTOOLBOX((*finishFromToolboxDetector)), DEC_DECL_FINISHSEEED((*finishSeeedDetector)), DEC_DECL_POSTPROCESSSEEED((*postprocessSeeedDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
includes one detector
detector for diagonal (bordered) structures via DBSCAN clustering algorithm
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDBSCAN)
Definition: dec_dbscan.cpp:662
SCIP_Bool simpsonenable
Definition: dec_dbscan.cpp:96
static DEC_DECL_PROPAGATESEEED(propagateSeeedDBSCAN)
Definition: dec_dbscan.cpp:426
#define DEFAULT_POSTPROC_ENABLE
Definition: dec_dbscan.cpp:77
const int * getOpenvars()
returns array containing variables not assigned yet
#define DEFAULT_SIMPSON_ENABLE
Definition: dec_dbscan.cpp:76
static DEC_DECL_EXITDETECTOR(exitDBSCAN)
Definition: dec_dbscan.cpp:170
virtual SCIP_RETCODE computePartitionDBSCAN(double eps, bool postprocenable)
#define finishSeeedDBSCAN
Definition: dec_dbscan.cpp:658
static DEC_DECL_FREEDETECTOR(freeDBSCAN)
Definition: dec_dbscan.cpp:153
int getNOpenconss()
returns size of vector containing constraints not assigned yet
#define DEC_LEGACYMODE
Definition: dec_dbscan.cpp:67
#define DEC_ENABLEDORIGINAL
Definition: dec_dbscan.cpp:62
#define DEC_DESC
Definition: dec_dbscan.cpp:52
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
Definition: rowgraph_def.h:62
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
SCIP_Bool postprocenable
Definition: dec_dbscan.cpp:97
void addClockTime(SCIP_Real clocktime)
incorporates the needed time of a certain detector in the detector chain
constraint handler for structure detection
std::vector< RowGraphWeighted< GraphGCG > * > * graphs
Definition: dec_dbscan.cpp:87
#define DEC_ENABLED
Definition: dec_dbscan.cpp:61
SCIP_Bool johnsonenable
Definition: dec_dbscan.cpp:92
virtual SCIP_RETCODE computePartitionDBSCANForPartialGraph(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed, double eps, bool postprocenable)
SCIP_Bool jaccardenable
Definition: dec_dbscan.cpp:94
SCIP_RETCODE refineToBlocks()
refine seeed with focus on blocks: assigns open conss and vars if they can be found in blocks (withou...
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint