Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-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_mst.cpp
29  * @ingroup DETECTORS
30  * @brief minimum spanning tree clustering detector
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 minimum spanning tree 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 
41 #include "dec_mst.h"
42 #include "cons_decomp.h"
43 #include "graph/matrixgraph.h"
45 #include "graph/graph_gcg.h"
46 #include "scip/clock.h"
47 
48 
50 using gcg::Weights;
51 using gcg::GraphGCG;
52 
53 
54 /* constraint handler properties */
55 #define DEC_DETECTORNAME "mst" /**< name of detector */
56 #define DEC_DESC "detector based on MST clustering" /**< description of detector */
57 #define DEC_PRIORITY 910 /**< 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 'M' /**< 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 /* Default parameter settings*/
72 #define DEFAULT_N_ITERATIONS 51
73 #define DEFAULT_JOHNSON_ENABLE true
74 #define DEFAULT_INTERSECTION_ENABLE false
75 #define DEFAULT_JACCARD_ENABLE false
76 #define DEFAULT_COSINE_ENABLE false
77 #define DEFAULT_SIMPSON_ENABLE false
78 #define DEFAULT_POSTPROC_ENABLE true
79 #define MAX_N_BLOCKS 100
80 
81 /*
82  * Data structures
83  */
84 
85 /** detector handler data */
86 struct DEC_DetectorData
87 {
88  SCIP_RESULT result; /**< result pointer to indicate success or failure */
89  SCIP_Bool found;
90  int n_iterations;
91  int n_similarities; /**< number of active similarities */
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 
151 /** destructor of detector to free user data (called when GCG is exiting) */
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 
168 /** destructor of detector to free detector data (called before the solving process begins) */
169 static
171 {
172  return SCIP_OKAY;
173 }
174 
175 
176 /** detection initialization function of detector (called before solving is about to begin) */
177 static
179 { /*lint --e{715}*/
180 
181  DEC_DETECTORDATA* detectordata;
182  assert(scip != NULL);
183 
184 
185  detectordata = DECdetectorGetData(detector);
186  assert(detectordata != NULL);
187  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
188 
189  detectordata->n_similarities = -1;
190  detectordata->found = FALSE;
191  return SCIP_OKAY;
192 }
193 
194 /** are there conss and vars to be included by the graph and have the conss common vars included by the graph */
195 static
197  gcg::DETPROBDATA* detprobdata,
198  gcg::PARTIALDECOMP* partialdec
199  )
200 {
201  bool completible;
202 
203  //have the open conss open vars?
204  for(int c = 0; c < partialdec->getNOpenconss() && !completible; ++c)
205  {
206  int cons = partialdec->getOpenconss()[c];
207  for(int v = 0; v < partialdec->getNOpenvars() && !completible; ++v)
208  {
209  int var = partialdec->getOpenvars()[v];
210  for(int i = 0; i < detprobdata->getNVarsForCons(cons) && !completible; ++i)
211  {
212  if(var == detprobdata->getVarsForCons(cons)[i])
213  {
214  completible = true;
215  }
216  }
217  }
218  }
219  if(!completible)
220  return false;
221 
222  //have the open conss common open vars?
223  for(int c = 0; c < partialdec->getNOpenconss(); ++c)
224  {
225  int cons1 = partialdec->getOpenconss()[c];
226  for(int d = c + 1; d < partialdec->getNOpenconss(); ++d)
227  {
228  int cons2 = partialdec->getOpenconss()[d];
229  for(int v = 0; v < detprobdata->getNVarsForCons(cons1); ++v)
230  {
231  int var1 = detprobdata->getVarsForCons(cons1)[v];
232  if(!partialdec->isVarOpenvar(var1))
233  continue;
234  for(int w = 0; w < detprobdata->getNVarsForCons(cons2); ++w)
235  {
236  int var2 = detprobdata->getVarsForCons(cons2)[w];
237  if(var1 == var2)
238  return true;
239  }
240  }
241  }
242  }
243  return false;
244 }
245 
246 
247 //#define propagatePartialdecMST NULL
248 
249 static
250 DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecMST)
251 { /*lint --e{715}*/
252 
253  int nnewpartialdecs;
254  gcg::PARTIALDECOMP* partialdec;
255  DEC_DETECTORDATA* detectordata = DECdetectorGetData(detector);
256  std::vector<SCIP_Real> clockTimes1; /* vector containing times in seconds */
257  std::vector<SCIP_Real> clockTimes2; /* vector containing times in seconds */
258  std::vector< RowGraphWeighted<GraphGCG>*> graphs;
259  SCIP_CLOCK* overallClock;
260 
261  assert(scip != NULL);
262  assert(detectordata != NULL);
263  *result = SCIP_DIDNOTFIND;
264 
265  SCIP_CALL_ABORT( SCIPcreateClock(scip, &overallClock) );
266  SCIP_CALL_ABORT( SCIPstartClock(scip, overallClock) );
267 
268  partialdec = partialdecdetectiondata->workonpartialdec;
269  partialdec->refineToBlocks();
270 
271  if( !graphCompletible(partialdecdetectiondata->detprobdata, partialdec) )
272  {
273  delete partialdec;
274  partialdecdetectiondata->nnewpartialdecs = 0;
275  SCIP_CALL_ABORT( SCIPstopClock(scip, overallClock) );
276  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, overallClock);
277  SCIP_CALL_ABORT(SCIPfreeClock(scip, &overallClock) );
278  *result = SCIP_SUCCESS;
279  return SCIP_OKAY;
280  }
281 
282  Weights w(1, 1, 1, 1, 1, 1);
283 
284  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting MST structure:");
285 
286  time_t start, cp0, cp1, d_s, d_e;
287  time(&start);
288 
289  std::vector<std::string> sim;
290  SCIP_CLOCK* temporaryClock;
291 
292  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
293 
294  if(detectordata->johnsonenable)
295  {
296  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
298  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::JOHNSON, gcg::WEIGHT_TYPE::DIST));
299  graphs.push_back(g);
300  sim.push_back("Johnson");
301  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
302  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
303  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
304  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
305  }
306  if(detectordata->intersectionenable)
307  {
308  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
310  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::INTERSECTION, gcg::WEIGHT_TYPE::DIST));
311  graphs.push_back(g);
312  sim.push_back("Intersection");
313  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
314  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
315  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
316  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
317  }
318  if(detectordata->jaccardenable)
319  {
320  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
322  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec, gcg::DISTANCE_MEASURE::JACCARD, gcg::WEIGHT_TYPE::DIST));
323  graphs.push_back(g);
324  sim.push_back("Jaccard");
325  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
326  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
327  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
328  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
329  }
330  if(detectordata->cosineenable)
331  {
332  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
334  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec,gcg::DISTANCE_MEASURE::COSINE, gcg::WEIGHT_TYPE::DIST));
335  graphs.push_back(g);
336  sim.push_back("Cosine");
337  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
338  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
339  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
340  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
341  }
342  if(detectordata->simpsonenable)
343  {
344  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
346  SCIP_CALL( g->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec,gcg::DISTANCE_MEASURE::SIMPSON, gcg::WEIGHT_TYPE::DIST));
347  graphs.push_back(g);
348  sim.push_back("Simspon");
349  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
350  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
351  clockTimes1.push_back(SCIPgetClockTime(scip, temporaryClock));
352  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
353  }
354  time(&cp0);
355  detectordata->n_similarities = (int) graphs.size();
356 
357  double q = 10; // quantile to search for the percentile needed for the mid of the eps list
358  std::vector<double> mids(graphs.size()); // middle values for each eps list
359  std::vector<std::vector<double> > epsLists(graphs.size());
360  for(int i = 0; i < (int)graphs.size(); i++)
361  {
362  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
363  mids[i] = graphs.at(i)->getEdgeWeightPercentile(q);
364  if(i == 1 && detectordata->intersectionenable)
365  {
366  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], true); // case for intersection
367  }
368  else
369  {
370  epsLists[i] = getEpsList(detectordata->n_iterations, mids[i], false); // case for all except intersection
371  }
372  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
373  clockTimes2.push_back(SCIPgetClockTime(scip, temporaryClock));
374  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock) );
375  }
376 
377  time(&cp1);
378 
379  int nMaxPartialdecs = detectordata->n_iterations * graphs.size();
380  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
381  char decinfo[SCIP_MAXSTRLEN];
382 
383  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 2 * nMaxPartialdecs) );
384 
385  nnewpartialdecs = 0;
386  time(&d_s);
387  for( int i = 0; i < (int)graphs.size(); i++ )
388  {
389  RowGraphWeighted<GraphGCG>* graph = graphs.at(i);
390  int old_n_blocks = -1;
391  int old_non_cl = -1;
392  std::vector<gcg::PARTIALDECOMP*> createddecomps;
393  std::vector<std::pair<double, SCIP_Real>> clockTimes3;
394  gcg::PARTIALDECOMP *decomp1 = NULL, *decomp2 = NULL;
395 
396  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
397  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity: ", sim[i].c_str());
398  createddecomps.reserve(2 * epsLists[i].size());
399  clockTimes3.reserve(epsLists[i].size());
400 
401  for( double eps : epsLists[i] )
402  {
403  if( eps <= 0.0 )
404  {
405  continue;
406  }
407  if( eps >= 1.0 )
408  {
409  break;
410  }
411 
412  // run MST with different eps
413  SCIP_CALL( graph->computePartitionMSTForPartialGraph(partialdecdetectiondata->detprobdata, partialdec, eps, detectordata->postprocenable) );
414 
415  int n_blocks;
416  int non_cl;
417  SCIP_CALL( graph->getNBlocks(n_blocks) );
418  SCIP_CALL( graph->nonClustered(non_cl) );
419 
420  // 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
421  if( n_blocks > max_blocks || n_blocks == 0 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
422  {
423  continue;
424  }
425  // stop. eps is already too big
426  if( n_blocks == 1 && non_cl == 0)
427  {
428  break;
429  }
430  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
431  old_n_blocks = n_blocks;
432  old_non_cl = non_cl;
433 
434  SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &decomp1, &decomp2, partialdecdetectiondata->detprobdata));
435  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
436 
437  if( decomp1 != NULL )
438  {
439  assert(decomp2 != NULL);
440  detectordata->found = TRUE;
441  createddecomps.push_back(decomp1);
442  createddecomps.push_back(decomp2);
443  clockTimes3.emplace_back(eps, SCIPgetClockTime(scip, temporaryClock));
444  }
445 
446  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
447  }
448 
449  size_t ncreateddecomps = createddecomps.size();
450  for( unsigned int j = 0; j < ncreateddecomps; ++j )
451  {
452  double eps = clockTimes3[j / 2].first;
453  SCIP_Real epstime = clockTimes3[j / 2].second;
454  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "mst_%s_%f", sim[i].c_str(), eps);
455  createddecomps[j]->addDetectorChainInfo(decinfo);
456  createddecomps[j]->addClockTime(clockTimes1[i] / ncreateddecomps + clockTimes2[i] / ncreateddecomps + epstime / 2.0);
457  partialdecdetectiondata->newpartialdecs[nnewpartialdecs + j] = createddecomps[j];
458  }
459  nnewpartialdecs += ncreateddecomps;
460 
461  delete graphs.at(i);
462  graphs[i] = NULL;
463  }
464 
465  SCIP_CALL( SCIPreallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
466  partialdecdetectiondata->nnewpartialdecs = nnewpartialdecs;
467  SCIP_CALL_ABORT( SCIPstopClock(scip, overallClock) );
468  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, overallClock);
469  SCIP_CALL_ABORT(SCIPfreeClock(scip, &overallClock) );
470 
471  time(&d_e);
472  double elapsed_graphs = difftime(cp0, start);
473  double elapsed_mst = difftime(d_e, d_s);
474 
475  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d decompositions found.\n", detectordata->n_similarities, nnewpartialdecs);
476  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "MST runtime: graphs: %.2lf, mst: %.2lf. \n", elapsed_graphs, elapsed_mst);
477 
478  *result = nnewpartialdecs > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
479  if( nnewpartialdecs == 0 )
480  {
481  SCIPfreeMemoryArrayNull(scip, &(partialdecdetectiondata->newpartialdecs));
482  }
483 
484  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
485  return SCIP_OKAY;
486 }
487 
488 #define finishPartialdecMST NULL
489 
490 #define detectorPostprocessPartialdecMST NULL
491 
492 static
493 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveMST)
494 {
495  char setstr[SCIP_MAXSTRLEN];
496  const char* name = DECdetectorGetName(detector);
497 
498  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
499  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
500 
501  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
502  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
503 
504  return SCIP_OKAY;
505 }
506 
507 
508 static
509 DEC_DECL_SETPARAMDEFAULT(setParamDefaultMST)
510 {
511  char setstr[SCIP_MAXSTRLEN];
512  const char* name = DECdetectorGetName(detector);
513 
514  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
515  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
516 
517  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
518  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
519 
520  return SCIP_OKAY;
521 }
522 
523 static
524 DEC_DECL_SETPARAMFAST(setParamFastMST)
525 {
526  char setstr[SCIP_MAXSTRLEN];
527  const char* name = DECdetectorGetName(detector);
528 
529  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
530  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
531 
532  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
533  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
534 
535  return SCIP_OKAY;
536 }
537 
538 
539 /*
540  * detector specific interface methods
541  */
542 
543 /** creates the handler for xyz detector and includes it in SCIP */
545  SCIP* scip /**< SCIP data structure */
546  )
547 {
548 #if !defined(_WIN32) && !defined(_WIN64)
549  DEC_DETECTORDATA *detectordata = NULL;
550  assert(scip != NULL);
551 
552  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
553 
554  assert(detectordata != NULL);
555  detectordata->found = FALSE;
556 
558  detectordata, freeMST, initMST, exitMST, propagatePartialdecMST, finishPartialdecMST, detectorPostprocessPartialdecMST, setParamAggressiveMST, setParamDefaultMST, setParamFastMST) );
559 
560  /* add arrowheur presolver parameters */
561  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) );
562  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/johson", "Enable johson distance measure.", &detectordata->johnsonenable, FALSE, DEFAULT_JOHNSON_ENABLE, NULL, NULL ) );
563  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/intersection", "Enable intersection distance measure.", &detectordata->intersectionenable, FALSE, DEFAULT_INTERSECTION_ENABLE, NULL, NULL ) );
564  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/jaccard", "Enable jaccard distance measure.", &detectordata->jaccardenable, FALSE, DEFAULT_JACCARD_ENABLE, NULL, NULL) );
565  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/cosine", "Enable cosine distance measure.", &detectordata->cosineenable, FALSE, DEFAULT_COSINE_ENABLE, NULL, NULL) );
566  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/simpson", "Enable simpson distance measure.", &detectordata->simpsonenable, FALSE, DEFAULT_SIMPSON_ENABLE, NULL, NULL ) );
567  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mst/postprocenable", "Enable post-processing step.", &detectordata->postprocenable, FALSE, DEFAULT_POSTPROC_ENABLE, NULL, NULL ) );
568 
569 #endif
570  return SCIP_OKAY;
571 }
#define DEC_ENABLEDFINISHING
Definition: dec_mst.cpp:66
static DEC_DECL_FREEDETECTOR(freeMST)
Definition: dec_mst.cpp:153
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
SCIP_RETCODE SCIPincludeDetectorMST(SCIP *scip)
Definition: dec_mst.cpp:544
SCIP_Bool cosineenable
Definition: dec_dbscan.cpp:96
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
#define DEC_DESC
Definition: dec_mst.cpp:56
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_mst.cpp:61
#define DEC_SKIP
Definition: dec_mst.cpp:68
miscellaneous matrixgraph methods for structure detection
#define DEFAULT_INTERSECTION_ENABLE
Definition: dec_mst.cpp:74
#define DEC_PRIORITY
Definition: dec_mst.cpp:57
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_mst.cpp:62
#define detectorPostprocessPartialdecMST
Definition: dec_mst.cpp:490
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecMST)
Definition: dec_mst.cpp:250
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: rowgraph_def.h:131
virtual SCIP_RETCODE getNBlocks(int &_n_blocks)
virtual SCIP_RETCODE nonClustered(int &_non_cl)
#define MAX_N_BLOCKS
Definition: dec_mst.cpp:79
A row graph where each row is a node and rows are adjacent if they share a variable....
#define DEFAULT_N_ITERATIONS
Definition: dec_mst.cpp:72
#define DEC_DETECTORNAME
Definition: dec_mst.cpp:55
@ INTERSECTION
static DEC_DECL_INITDETECTOR(initMST)
Definition: dec_mst.cpp:178
#define DEFAULT_JOHNSON_ENABLE
Definition: dec_mst.cpp:73
SCIP_Bool found
Definition: dec_dbscan.cpp:90
SCIP_Bool intersectionenable
Definition: dec_dbscan.cpp:94
static std::vector< double > getEpsList(int length, double mid, bool isintersection)
Definition: dec_mst.cpp:105
#define DEFAULT_SIMPSON_ENABLE
Definition: dec_mst.cpp:77
#define DEC_MINCALLROUND
Definition: dec_mst.cpp:60
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define DEC_DECCHAR
Definition: dec_mst.cpp:64
virtual SCIP_RETCODE computePartitionMSTForPartialGraph(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, double eps, bool postprocenable)
static bool graphCompletible(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
Definition: dec_mst.cpp:196
void refineToBlocks()
refine partialdec with focus on blocks
#define DEFAULT_COSINE_ENABLE
Definition: dec_mst.cpp:76
detector for diagonal (bordered) structures via Minimum Spanning Tree clustering algorithm
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveMST)
Definition: dec_mst.cpp:493
const int * getOpenconss()
Gets array containing constraints not assigned yet.
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_mst.cpp:63
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultMST)
Definition: dec_mst.cpp:509
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
#define DEC_FREQCALLROUND
Definition: dec_mst.cpp:58
#define DEFAULT_JACCARD_ENABLE
Definition: dec_mst.cpp:75
SCIP_RESULT result
Definition: dec_dbscan.cpp:89
#define DEFAULT_POSTPROC_ENABLE
Definition: dec_mst.cpp:78
class to manage partial decompositions
#define DEC_ENABLED
Definition: dec_mst.cpp:65
#define DEC_USEFULRECALL
Definition: dec_mst.cpp:69
SCIP_Bool postprocenable
Definition: dec_dbscan.cpp:98
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.
SCIP_Bool johnsonenable
Definition: dec_dbscan.cpp:93
static DEC_DECL_EXITDETECTOR(exitMST)
Definition: dec_mst.cpp:170
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.
static DEC_DECL_SETPARAMFAST(setParamFastMST)
Definition: dec_mst.cpp:524
#define DEC_MAXCALLROUND
Definition: dec_mst.cpp:59
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_mst.cpp:67
SCIP_Bool jaccardenable
Definition: dec_dbscan.cpp:95
SCIP_Bool simpsonenable
Definition: dec_dbscan.cpp:97
#define finishPartialdecMST
Definition: dec_mst.cpp:488