dec_mst.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 
37 #include "dec_mst.h"
38 #include "cons_decomp.h"
39 #include "graph/matrixgraph.h"
41 #include "graph/graph_gcg.h"
42 #include "scip/clock.h"
43 
45 using gcg::Weights;
46 using gcg::GraphGCG;
47 
48 
49 /* constraint handler properties */
50 #define DEC_DETECTORNAME "mst"
51 #define DEC_DESC "detector based on MST clustering"
52 #define DEC_FREQCALLROUND 1
53 #define DEC_MAXCALLROUND INT_MAX
54 #define DEC_MINCALLROUND 0
55 #define DEC_FREQCALLROUNDORIGINAL 1
56 #define DEC_MAXCALLROUNDORIGINAL INT_MAX
57 #define DEC_MINCALLROUNDORIGINAL 0
58 #define DEC_PRIORITY 910
59 #define DEC_DECCHAR 'M'
60 #define DEC_ENABLED FALSE
61 #define DEC_ENABLEDORIGINAL FALSE
62 #define DEC_ENABLEDFINISHING FALSE
63 #define DEC_ENABLEDPOSTPROCESSING FALSE
64 #define DEC_SKIP FALSE
65 #define DEC_USEFULRECALL FALSE
66 #define DEC_LEGACYMODE FALSE
68 /* Default parameter settings*/
69 #define DEFAULT_N_ITERATIONS 51
70 #define DEFAULT_JOHNSON_ENABLE true
71 #define DEFAULT_INTERSECTION_ENABLE false
72 #define DEFAULT_JACCARD_ENABLE false
73 #define DEFAULT_COSINE_ENABLE false
74 #define DEFAULT_SIMPSON_ENABLE false
75 #define DEFAULT_POSTPROC_ENABLE true
76 #define MAX_N_BLOCKS 100
77 
78 /*
79  * Data structures
80  */
81 
83 struct DEC_DetectorData
84 {
85  std::vector< RowGraphWeighted<GraphGCG>*> *graphs;
86  SCIP_RESULT result;
87  SCIP_Bool found;
88  int n_iterations;
89  int n_similarities;
90  SCIP_Bool johnsonenable;
91  SCIP_Bool intersectionenable;
92  SCIP_Bool jaccardenable;
93  SCIP_Bool cosineenable;
94  SCIP_Bool simpsonenable;
95  SCIP_Bool postprocenable;
96 };
97 
98 
99 /*
100  * Local methods
101  */
102 
103 static std::vector<double> getEpsList(int length, double mid, bool isintersection)
104 {
105  int n1, n2;
106  if(isintersection)
107  {
108  n1 = (int) round((length+1) / 2.0);
109  n2 = n1;
110  }
111  else
112  {
113  n2 = (int) round((length+1) / 4.0);
114  n1 = abs(length - n2) + 1;
115  }
116 
117  double s = mid;
118  double end1 = mid + 0.9; // lower boundary
119  double end2 = mid + 0.4; // upper boundary
120 
121  double q1 = pow(end1/s, 1.0/(double)(n1-1));
122  double q2 = pow(end2/s, 1.0/(double)(n2-1));
123 
124  std::vector<double> geom_seq1(n1-1);
125  std::vector<double> geom_seq2(n2);
126 
127  int j = 0;
128  for(int i = n1 - 1; i > 0; i--)
129  {
130  geom_seq1[j] = 2*s-s*pow(q1, (double)i);
131  j++;
132  }
133  for(int i = 0; i < n2; i++)
134  {
135  geom_seq2[i] = s*pow(q2, (double)i);
136  }
137 
138  geom_seq1.insert( geom_seq1.end(), geom_seq2.begin(), geom_seq2.end() );
139 
140  assert((int)geom_seq1.size() == length);
141 
142  return geom_seq1;
143 }
144 
145 /*
146  * detector callback methods
147  */
148 
150 static
152 {
153  DEC_DETECTORDATA* detectordata;
154 
155  assert(scip != NULL);
156 
157  detectordata = DECdetectorGetData(detector);
158  assert(detectordata != NULL);
159  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
160 
161  SCIPfreeMemory(scip, &detectordata);
162 
163  return SCIP_OKAY;
164 }
165 
167 static
169 {
170  DEC_DETECTORDATA* detectordata;
171  assert(scip != NULL);
172 
173  detectordata = DECdetectorGetData(detector);
174  assert(detectordata != NULL);
175  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
176 
177  delete detectordata->graphs;
178 
179  return SCIP_OKAY;
180 }
181 
182 
184 static
186 { /*lint --e{715}*/
187 
188  DEC_DETECTORDATA* detectordata;
189  assert(scip != NULL);
190 
191 
192  detectordata = DECdetectorGetData(detector);
193  assert(detectordata != NULL);
194  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
195 
196  detectordata->n_similarities = -1;
197  detectordata->found = FALSE;
198  detectordata->graphs = new std::vector< RowGraphWeighted<GraphGCG>*>();
199  return SCIP_OKAY;
200 }
201 
203 static
205  gcg::Seeedpool* seeedpool,
206  gcg::Seeed* seeed
207  )
208 {
209  bool completible;
210 
211  //have the open conss open vars?
212  for(int c = 0; c < seeed->getNOpenconss() && !completible; ++c)
213  {
214  int cons = seeed->getOpenconss()[c];
215  for(int v = 0; v < seeed->getNOpenvars() && !completible; ++v)
216  {
217  int var = seeed->getOpenvars()[v];
218  for(int i = 0; i < seeedpool->getNVarsForCons(cons) && !completible; ++i)
219  {
220  if(var == seeedpool->getVarsForCons(cons)[i])
221  {
222  completible = true;
223  }
224  }
225  }
226  }
227  if(!completible)
228  return false;
229 
230  //have the open conss common open vars?
231  for(int c = 0; c < seeed->getNOpenconss(); ++c)
232  {
233  int cons1 = seeed->getOpenconss()[c];
234  for(int d = c + 1; d < seeed->getNOpenconss(); ++d)
235  {
236  int cons2 = seeed->getOpenconss()[d];
237  for(int v = 0; v < seeedpool->getNVarsForCons(cons1); ++v)
238  {
239  int var1 = seeedpool->getVarsForCons(cons1)[v];
240  if(!seeed->isVarOpenvar(var1))
241  continue;
242  for(int w = 0; w < seeedpool->getNVarsForCons(cons2); ++w)
243  {
244  int var2 = seeedpool->getVarsForCons(cons2)[w];
245  if(var1 == var2)
246  return true;
247  }
248  }
249  }
250  }
251  return false;
252 }
253 
255 static
257 { /*lint --e{715}*/
258 
259  assert(scip != NULL);
260  assert(detectordata != NULL);
261  assert(decdecomps != NULL);
262  *result = SCIP_DIDNOTFIND;
263 
264  Weights w(1, 1, 1, 1, 1, 1);
265 
266  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting MST structure:");
267 
268  time_t start, cp0, cp1, d_s, d_e;
269  time(&start);
270 
271  std::vector<std::string> sim;
272 
273  if(detectordata->johnsonenable)
274  {
276  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
278  detectordata->graphs->push_back(g);
279  sim.push_back("Johnson");
280  }
281  if(detectordata->intersectionenable)
282  {
284  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
286  detectordata->graphs->push_back(g);
287  sim.push_back("Intersection");
288  }
289  if(detectordata->jaccardenable)
290  {
292  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
294  detectordata->graphs->push_back(g);
295  sim.push_back("Jaccard");
296  }
297  if(detectordata->cosineenable)
298  {
300  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
302  detectordata->graphs->push_back(g);
303  sim.push_back("Cosine");
304  }
305  if(detectordata->simpsonenable)
306  {
308  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
310  detectordata->graphs->push_back(g);
311  sim.push_back("Simspon");
312  }
313  time(&cp0);
314  detectordata->n_similarities = (int) detectordata->graphs->size();
315 
316  double q = 10; // quantile to search for the percentile needed for the mid of the eps list
317  std::vector<double> mids(detectordata->graphs->size()); // middle values for each eps list
318  std::vector<std::vector<double> > epsLists(detectordata->graphs->size());
319  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
320  {
321  mids[i] = detectordata->graphs->at(i)->getEdgeWeightPercentile(q);
322  if(i == 1 && detectordata->intersectionenable)
323  {
324  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], true); // case for intersection
325  }
326  else
327  {
328  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
329  }
330 
331  }
332 
333  time(&cp1);
334 
335  int max_ndecs = detectordata->n_iterations * detectordata->graphs->size();
336  SCIP_CALL( SCIPallocMemoryArray(scip, decdecomps, max_ndecs) );
337 
338  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
339 
340  *ndecdecomps = 0;
341  time(&d_s);
342  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
343  {
344  RowGraphWeighted<GraphGCG>* graph = detectordata->graphs->at(i);
345  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity: ", sim[i].c_str());
346  int old_n_blocks = -1;
347  int old_non_cl = -1;
348  for(int j = 0; j < (int)epsLists[i].size() ; j++ )
349  {
350  double eps = epsLists[i][j];
351  if(eps <= 0.0)
352  {
353  continue;
354  }
355  if(eps >= 1.0)
356  {
357  break;
358  }
359 
360  // run MST with different eps
361  SCIP_CALL( graph->computePartitionMST(eps, detectordata->postprocenable) );
362 
363 
364  int n_blocks;
365  SCIP_CALL( graph->getNBlocks(n_blocks) );
366  int non_cl;
367 
368  SCIP_CALL( graph->nonClustered(non_cl) );
369 
370  // 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
371  if( n_blocks > max_blocks || n_blocks == 0 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
372  {
373  continue;
374  }
375  // stop. eps is already too big
376  if( n_blocks == 1 && non_cl == 0)
377  {
378  break;
379  }
380  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
381  old_n_blocks = n_blocks;
382  old_non_cl = non_cl;
383 
384 
385  SCIP_CALL( graph->createDecompFromPartition(&(*decdecomps)[*ndecdecomps]) );
386 
387  auto check = DECdecompGetNLinkingvars((*decdecomps)[*ndecdecomps]);
388  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Link Vars: %d. ", check);
389 
390  if( (*decdecomps)[*ndecdecomps] != NULL )
391  {
392  *ndecdecomps += 1;
393  detectordata->found = TRUE;
394  }
395  }
396  delete detectordata->graphs->at(i);
397  detectordata->graphs->at(i) = NULL;
398  }
399 
400  detectordata->graphs->clear();
401  time(&d_e);
402  double elapsed_graphs = difftime(cp0, start);
403  double elapsed_mst = difftime(d_e, d_s);
404 
405  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d decompositions found.\n", detectordata->n_similarities, *ndecdecomps);
406  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "MST runtime: graphs: %.2lf, mst: %.2lf. \n", elapsed_graphs, elapsed_mst);
407 
408  SCIP_CALL( SCIPreallocMemoryArray(scip, decdecomps, *ndecdecomps) );
409 
410  *result = *ndecdecomps > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
411  if( *ndecdecomps == 0 )
412  {
413  SCIPfreeMemoryArrayNull(scip, decdecomps);
414  }
415  return SCIP_OKAY;
416 }
417 
418 //#define propagateSeeedMST NULL
419 
420 static
421 DEC_DECL_PROPAGATESEEED(propagateSeeedMST)
422 { /*lint --e{715}*/
423 
424  int nNewSeeeds;
425  gcg::Seeed* seeed;
426  gcg::Seeed** newSeeeds;
427  DEC_DETECTORDATA* detectordata = DECdetectorGetData(detector);
428  std::vector<SCIP_Real> clockTimes1;
429  std::vector<SCIP_Real> clockTimes2;
430  std::vector<SCIP_Real> clockTimes3;
432  assert(scip != NULL);
433  assert(detectordata != NULL);
434  *result = SCIP_DIDNOTFIND;
435 
436  seeed = new gcg::Seeed(seeedPropagationData->seeedToPropagate);
437  seeed->refineToBlocks();
438 
439  if(!graphCompletible(seeedPropagationData->seeedpool, seeed))
440  {
441  delete seeed;
442  seeedPropagationData->nNewSeeeds = 0;
443  *result = SCIP_SUCCESS;
444  return SCIP_OKAY;
445  }
446  Weights w(1, 1, 1, 1, 1, 1);
447 
448  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting MST structure:");
449 
450  time_t start, cp0, cp1, d_s, d_e;
451  time(&start);
452 
453  std::vector<std::string> sim;
454 
455  SCIP_CLOCK* temporaryClock;
456  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
457 
458  if(detectordata->johnsonenable)
459  {
460  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
462  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::JOHNSON, gcg::WEIGHT_TYPE::DIST));
463  detectordata->graphs->push_back(g);
464  sim.push_back("Johnson");
465  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
466  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
467  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
468  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
469  }
470  if(detectordata->intersectionenable)
471  {
472  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
474  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::INTERSECTION, gcg::WEIGHT_TYPE::DIST));
475  detectordata->graphs->push_back(g);
476  sim.push_back("Intersection");
477  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
478  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
479  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
480  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
481  }
482  if(detectordata->jaccardenable)
483  {
484  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
486  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::JACCARD, gcg::WEIGHT_TYPE::DIST));
487  detectordata->graphs->push_back(g);
488  sim.push_back("Jaccard");
489  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
490  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
491  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
492  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
493  }
494  if(detectordata->cosineenable)
495  {
496  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
498  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed,gcg::DISTANCE_MEASURE::COSINE, gcg::WEIGHT_TYPE::DIST));
499  detectordata->graphs->push_back(g);
500  sim.push_back("Cosine");
501  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
502  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
503  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
504  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
505  }
506  if(detectordata->simpsonenable)
507  {
508  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
510  SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed,gcg::DISTANCE_MEASURE::SIMPSON, gcg::WEIGHT_TYPE::DIST));
511  detectordata->graphs->push_back(g);
512  sim.push_back("Simspon");
513  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
514  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
515  clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
516  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
517  }
518  time(&cp0);
519  detectordata->n_similarities = (int) detectordata->graphs->size();
520 
521  double q = 10; // quantile to search for the percentile needed for the mid of the eps list
522  std::vector<double> mids(detectordata->graphs->size()); // middle values for each eps list
523  std::vector<std::vector<double> > epsLists(detectordata->graphs->size());
524  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
525  {
526  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
527  mids[i] = detectordata->graphs->at(i)->getEdgeWeightPercentile(q);
528  if(i == 1 && detectordata->intersectionenable)
529  {
530  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], true); // case for intersection
531  }
532  else
533  {
534  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
535  }
536  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
537  clockTimes2.push_back(SCIPclockGetTime(temporaryClock));
538  clockTimes2.push_back(SCIPclockGetTime(temporaryClock));
539  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
540  }
541 
542  time(&cp1);
543 
544  int nMaxSeeeds = detectordata->n_iterations * detectordata->graphs->size();
545  SCIP_CALL( SCIPallocMemoryArray(scip, &(newSeeeds), 2 * nMaxSeeeds) );
546 
547  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
548 
549  int n_seeeds_found = 0;
550  nNewSeeeds = 0;
551  time(&d_s);
552  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
553  {
554  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
555  RowGraphWeighted<GraphGCG>* graph = detectordata->graphs->at(i);
556  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity: ", sim[i].c_str());
557  int old_n_blocks = -1;
558  int old_non_cl = -1;
559  for(int j = 0; j < (int)epsLists[i].size() ; j++ )
560  {
561  double eps = epsLists[i][j];
562  if(eps <= 0.0)
563  {
564  continue;
565  }
566  if(eps >= 1.0)
567  {
568  break;
569  }
570 
571  // run MST with different eps
572  SCIP_CALL( graph->computePartitionMSTForPartialGraph(seeedPropagationData->seeedpool, seeed, eps, detectordata->postprocenable) );
573 
574 
575  int n_blocks;
576  SCIP_CALL( graph->getNBlocks(n_blocks) );
577  int non_cl;
578 
579  SCIP_CALL( graph->nonClustered(non_cl) );
580 
581  // 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
582  if( n_blocks > max_blocks || n_blocks == 0 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
583  {
584  continue;
585  }
586  // stop. eps is already too big
587  if( n_blocks == 1 && non_cl == 0)
588  {
589  break;
590  }
591  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
592  old_n_blocks = n_blocks;
593  old_non_cl = non_cl;
594 
595 
596  SCIP_CALL( graph->createSeeedFromPartition(seeed,&newSeeeds[n_seeeds_found], &newSeeeds[n_seeeds_found+1], seeedPropagationData->seeedpool));
597 
598  if((newSeeeds)[n_seeeds_found] != NULL)
599  {
600  nNewSeeeds += 2;
601  detectordata->found = TRUE;
602  }
603  n_seeeds_found += 2;
604  }
605  delete detectordata->graphs->at(i);
606  detectordata->graphs->at(i) = NULL;
607 
608  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
609  clockTimes3.push_back(SCIPclockGetTime(temporaryClock));
610  clockTimes3.push_back(SCIPclockGetTime(temporaryClock));
611  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
612  }
613 
614  delete seeed;
615  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), nNewSeeeds) );
616  seeedPropagationData->nNewSeeeds = nNewSeeeds;
617  for(int j = 0, s = 0; s < nNewSeeeds; ++j)
618  {
619  if(newSeeeds[j] != NULL)
620  {
621  seeedPropagationData->newSeeeds[s] = newSeeeds[j];
622  seeedPropagationData->newSeeeds[s]->addClockTime(clockTimes1[j] + clockTimes2[j] + clockTimes3[j]);
623  seeedPropagationData->newSeeeds[s]->setDetectorPropagated(detector);
624  ++s;
625  }
626  }
627  SCIPfreeMemoryArray(scip, &newSeeeds);
628 
629  detectordata->graphs->clear();
630  time(&d_e);
631  double elapsed_graphs = difftime(cp0, start);
632  double elapsed_mst = difftime(d_e, d_s);
633 
634  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d decompositions found.\n", detectordata->n_similarities, nNewSeeeds);
635  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "MST runtime: graphs: %.2lf, mst: %.2lf. \n", elapsed_graphs, elapsed_mst);
636 
637  *result = nNewSeeeds > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
638  if( nNewSeeeds == 0 )
639  {
640  SCIPfreeMemoryArrayNull(scip, &(seeedPropagationData->newSeeeds));
641  }
642 
643  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
644  return SCIP_OKAY;
645 }
646 
647 #define finishSeeedMST NULL
648 
649 #define detectorPostprocessSeeedMST NULL
650 
651 #define setParamAggressiveMST NULL
652 #define setParamDefaultMST NULL
653 #define setParamFastMST NULL
654 
655 
656 /*
657  * detector specific interface methods
658  */
659 
662  SCIP* scip
663  )
664 {
665 #if !defined(_WIN32) && !defined(_WIN64)
666  DEC_DETECTORDATA *detectordata = NULL;
667  assert(scip != NULL);
668 
669  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
670 
671  assert(detectordata != NULL);
672  detectordata->found = FALSE;
673 
675  detectordata, detectMST, freeMST, initMST, exitMST, propagateSeeedMST, NULL, NULL, finishSeeedMST, detectorPostprocessSeeedMST, setParamAggressiveMST, setParamDefaultMST, setParamFastMST) );
676 
677  /* add arrowheur presolver parameters */
678  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/mst/niterations", "Number of iterations to run mst with different eps.", &detectordata->n_iterations, FALSE, DEFAULT_N_ITERATIONS, 11, 1001, NULL, NULL) );
679  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/johson", "Enable johson distance measure.", &detectordata->johnsonenable, FALSE, DEFAULT_JOHNSON_ENABLE, NULL, NULL ) );
680  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/intersection", "Enable intersection distance measure.", &detectordata->intersectionenable, FALSE, DEFAULT_INTERSECTION_ENABLE, NULL, NULL ) );
681  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/jaccard", "Enable jaccard distance measure.", &detectordata->jaccardenable, FALSE, DEFAULT_JACCARD_ENABLE, NULL, NULL) );
682  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/cosine", "Enable cosine distance measure.", &detectordata->cosineenable, FALSE, DEFAULT_COSINE_ENABLE, NULL, NULL) );
683  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/simpson", "Enable simpson distance measure.", &detectordata->simpsonenable, FALSE, DEFAULT_SIMPSON_ENABLE, NULL, NULL ) );
684  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/postprocenable", "Enable post-processing step..", &detectordata->postprocenable, FALSE, DEFAULT_POSTPROC_ENABLE, NULL, NULL ) );
685 
686 #endif
687  return SCIP_OKAY;
688 }
#define DEC_SKIP
Definition: dec_mst.cpp:64
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_mst.cpp:56
miscellaneous matrixgraph methods for structure detection
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
#define DEC_ENABLEDFINISHING
Definition: dec_mst.cpp:62
#define DEC_MAXCALLROUND
Definition: dec_mst.cpp:53
const int * getOpenconss()
returns array containing constraints not assigned yet
#define DEFAULT_N_ITERATIONS
Definition: dec_mst.cpp:69
#define setParamAggressiveMST
Definition: dec_mst.cpp:651
TCLIQUE_GRAPH * graph
Definition: dec_staircase.c:87
virtual SCIP_RETCODE getNBlocks(int &_n_blocks)
#define DEC_DECCHAR
Definition: dec_mst.cpp:59
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_mst.cpp:55
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define detectorPostprocessSeeedMST
Definition: dec_mst.cpp:649
SCIP_Bool cosineenable
Definition: dec_dbscan.cpp:95
virtual SCIP_RETCODE nonClustered(int &_non_cl)
#define DEFAULT_JOHNSON_ENABLE
Definition: dec_mst.cpp:70
#define DEC_PRIORITY
Definition: dec_mst.cpp:58
#define finishSeeedMST
Definition: dec_mst.cpp:647
#define DEFAULT_POSTPROC_ENABLE
Definition: dec_mst.cpp:75
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
#define MAX_N_BLOCKS
Definition: dec_mst.cpp:76
#define DEC_FREQCALLROUND
Definition: dec_mst.cpp:52
#define DEFAULT_COSINE_ENABLE
Definition: dec_mst.cpp:73
#define DEFAULT_INTERSECTION_ENABLE
Definition: dec_mst.cpp:71
bool isVarOpenvar(int var)
returns true if the var is an open var
static std::vector< double > getEpsList(int length, double mid, bool isintersection)
Definition: dec_mst.cpp:103
Implementation of the graph which supports both node and edge weights.
static DEC_DECL_EXITDETECTOR(exitMST)
Definition: dec_mst.cpp:168
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
#define DEC_DESC
Definition: dec_mst.cpp:51
static DEC_DECL_FREEDETECTOR(freeMST)
Definition: dec_mst.cpp:151
virtual SCIP_RETCODE computePartitionMST(double eps, bool postprocenable)
virtual SCIP_RETCODE computePartitionMSTForPartialGraph(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed, double eps, bool postprocenable)
SCIP_Bool found
Definition: dec_dbscan.cpp:89
static DEC_DECL_INITDETECTOR(initMST)
Definition: dec_mst.cpp:185
virtual SCIP_RETCODE createFromPartialMatrix(Seeedpool *seeedpool, Seeed *seeed, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
SCIP_RETCODE SCIPincludeDetectorMST(SCIP *scip)
Definition: dec_mst.cpp:661
#define DEC_USEFULRECALL
Definition: dec_mst.cpp:65
#define DEC_LEGACYMODE
Definition: dec_mst.cpp:66
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.
detector for diagonal (bordered) structures via Minimum Spanning Tree clustering algorithm ...
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
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_mst.cpp:57
SCIP_Bool simpsonenable
Definition: dec_dbscan.cpp:96
#define DEC_DETECTORNAME
Definition: dec_mst.cpp:50
#define DEC_MINCALLROUND
Definition: dec_mst.cpp:54
const int * getOpenvars()
returns array containing variables not assigned yet
#define DEC_ENABLEDORIGINAL
Definition: dec_mst.cpp:61
static DEC_DECL_PROPAGATESEEED(propagateSeeedMST)
Definition: dec_mst.cpp:421
#define DEFAULT_JACCARD_ENABLE
Definition: dec_mst.cpp:72
int getNOpenconss()
returns size of vector containing constraints not assigned yet
static DEC_DECL_DETECTSTRUCTURE(detectMST)
Definition: dec_mst.cpp:256
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
#define DEC_ENABLED
Definition: dec_mst.cpp:60
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_mst.cpp:63
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
#define setParamFastMST
Definition: dec_mst.cpp:653
#define DEFAULT_SIMPSON_ENABLE
Definition: dec_mst.cpp:74
#define setParamDefaultMST
Definition: dec_mst.cpp:652
static bool graphCompletible(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed)
Definition: dec_mst.cpp:204
SCIP_Bool johnsonenable
Definition: dec_dbscan.cpp:92
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