dec_mcl.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 <iostream>
38 #include "dec_mcl.h"
39 #include "cons_decomp.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 "mcl"
51 #define DEC_DESC "detector based on mcl 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 'L'
60 #ifdef WITH_GSL
61 #define DEC_ENABLED TRUE
62 #define DEC_ENABLEDORIGINAL TRUE
63 #else
64 #define DEC_ENABLED FALSE
65 #define DEC_ENABLEDORIGINAL FALSE
66 #endif
67 #define DEC_ENABLEDFINISHING FALSE
68 #define DEC_ENABLEDPOSTPROCESSING FALSE
69 #define DEC_SKIP FALSE
70 #define DEC_USEFULRECALL FALSE
71 #define DEC_LEGACYMODE FALSE
73 /* Default parameter settings*/
74 #define DEFAULT_N_ITERATIONS 13
75 #define DEFAULT_JOHNSON_ENABLE true
76 #define DEFAULT_INTERSECTION_ENABLE false
77 #define DEFAULT_JACCARD_ENABLE false
78 #define DEFAULT_COSINE_ENABLE false
79 #define DEFAULT_SIMPSON_ENABLE false
80 #define DEFAULT_POSTPROC_ENABLE true
81 #define MAX_N_ITERATIONS 20
82 #define MAX_N_BLOCKS 100
83 
84 /*
85  * Data structures
86  */
87 
89 struct DEC_DetectorData
90 {
91  std::vector< RowGraphWeighted<GraphGCG>*> *graphs;
92  SCIP_RESULT result;
93  SCIP_Bool found;
94  int n_iterations;
95  int n_similarities;
96  SCIP_Bool johnsonenable;
97  SCIP_Bool intersectionenable;
98  SCIP_Bool jaccardenable;
99  SCIP_Bool cosineenable;
100  SCIP_Bool simpsonenable;
101  SCIP_Bool postprocenable;
102 };
103 
104 
105 /*
106  * Local methods
107  */
108 
109 
110 /*
111  * detector callback methods
112  */
113 
115 static
117 {
118  DEC_DETECTORDATA* detectordata;
119 
120  assert(scip != NULL);
121 
122  detectordata = DECdetectorGetData(detector);
123  assert(detectordata != NULL);
124  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
125 
126  SCIPfreeMemory(scip, &detectordata);
127 
128  return SCIP_OKAY;
129 }
130 
132 static
134 {
135  DEC_DETECTORDATA* detectordata;
136  assert(scip != NULL);
137 
138  detectordata = DECdetectorGetData(detector);
139  assert(detectordata != NULL);
140  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
141 
142  delete detectordata->graphs;
143 
144  return SCIP_OKAY;
145 }
146 
147 
149 static
151 { /*lint --e{715}*/
152 
153  DEC_DETECTORDATA* detectordata;
154  assert(scip != NULL);
155 
156 
157  detectordata = DECdetectorGetData(detector);
158  assert(detectordata != NULL);
159  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
160 
161  detectordata->n_similarities = -1;
162  detectordata->found = FALSE;
163  detectordata->graphs = new std::vector< RowGraphWeighted<GraphGCG>*>();
164  return SCIP_OKAY;
165 }
166 
168 static inline
170  gcg::Seeedpool* seeedpool,
171  gcg::Seeed* seeed
172  )
173 {
174  bool completible;
175 
176  //have the open conss open vars?
177  for(int c = 0; c < seeed->getNOpenconss() && !completible; ++c)
178  {
179  int cons = seeed->getOpenconss()[c];
180  for(int v = 0; v < seeed->getNOpenvars() && !completible; ++v)
181  {
182  int var = seeed->getOpenvars()[v];
183  for(int i = 0; i < seeedpool->getNVarsForCons(cons) && !completible; ++i)
184  {
185  if(var == seeedpool->getVarsForCons(cons)[i])
186  {
187  completible = true;
188  }
189  }
190  }
191  }
192  if(!completible)
193  return false;
194 
195  //have the open conss common open vars?
196  for(int c = 0; c < seeed->getNOpenconss(); ++c)
197  {
198  int cons1 = seeed->getOpenconss()[c];
199  for(int d = c + 1; d < seeed->getNOpenconss(); ++d)
200  {
201  int cons2 = seeed->getOpenconss()[d];
202  for(int v = 0; v < seeedpool->getNVarsForCons(cons1); ++v)
203  {
204  int var1 = seeedpool->getVarsForCons(cons1)[v];
205  if(!seeed->isVarOpenvar(var1))
206  continue;
207  for(int w = 0; w < seeedpool->getNVarsForCons(cons2); ++w)
208  {
209  int var2 = seeedpool->getVarsForCons(cons2)[w];
210  if(var1 == var2)
211  return true;
212  }
213  }
214  }
215  }
216  return false;
217 }
218 
220 static
222 { /*lint --e{715}*/
223 
224  assert(scip != NULL);
225  assert(detectordata != NULL);
226  assert(decdecomps != NULL);
227  *result = SCIP_DIDNOTFIND;
228 
229  detectordata->n_iterations = std::min(detectordata->n_iterations, MAX_N_ITERATIONS);
230 
231  Weights w(1, 1, 1, 1, 1, 1);
232 
233  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting MCL structure:");
234 
235  time_t start, cp1, d_s, d_e;
236  time(&start);
237 
238  std::vector<std::string> sim;
239 
240  if(detectordata->johnsonenable)
241  {
243  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
245  detectordata->graphs->push_back(g);
246  sim.push_back("Johnson");
247  }
248  if(detectordata->intersectionenable)
249  {
251  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
253  detectordata->graphs->push_back(g);
254  sim.push_back("Intersection");
255  }
256  if(detectordata->jaccardenable)
257  {
259  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
261  detectordata->graphs->push_back(g);
262  sim.push_back("Jaccard");
263  }
264  if(detectordata->cosineenable)
265  {
267  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
269  detectordata->graphs->push_back(g);
270  sim.push_back("Cosine");
271  }
272  if(detectordata->simpsonenable)
273  {
275  SCIP_CALL( g->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip),
277  detectordata->graphs->push_back(g);
278  sim.push_back("Simspon");
279  }
280  detectordata->n_similarities = (int) detectordata->graphs->size();
281 
282 
283  std::vector<double> inflatefactors(detectordata->n_iterations);
284  double inflate = 1.1;
285  for(int i = 0; i < detectordata->n_iterations; i++)
286  {
287  inflatefactors[i] = inflate;
288  inflate += 0.05;
289  }
290  time(&cp1);
291 
292  int max_ndecs = detectordata->n_iterations * detectordata->graphs->size();
293  SCIP_CALL( SCIPallocMemoryArray(scip, decdecomps, max_ndecs) );
294 
295 
296  const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
297  int n_decs_found = 0;
298 
299  *ndecdecomps = 0;
300  time(&d_s);
301  for(int i = 0; i < (int)detectordata->graphs->size(); i++)
302  {
303  RowGraphWeighted<GraphGCG>* graph = detectordata->graphs->at(i);
304  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity:", sim[i].c_str());
305  int old_n_blocks = -1;
306  int old_non_cl = -1;
307  for(int j = 0; j < (int)inflatefactors.size() ; j++ )
308  {
309  double inflatefactor = inflatefactors[j];
310 
311  // run MCL with different inflate factors
312  int stoppedAfter;
313  SCIP_CALL( graph->computePartitionMCL(stoppedAfter, inflatefactor, detectordata->postprocenable) );
314 
315  int n_blocks;
316  SCIP_CALL( graph->getNBlocks(n_blocks) );
317  int non_cl;
318  SCIP_CALL( graph->nonClustered(non_cl) );
319 
320 
321  // skip the case if we have 1 block (it means we must increase inflate factor) or if the clustering is the same as the last one
322  if(n_blocks == 1 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
323  {
324  continue;
325  }
326  // stop. inflate factor is already too big
327  if( n_blocks > max_blocks )
328  {
329  break;
330  }
331 
332  old_n_blocks = n_blocks;
333  old_non_cl = non_cl;
334  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Inflate factor: %.2f, ", inflatefactor);
335  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Stopped after: %d iters, ", stoppedAfter);
336  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
337 
338  SCIP_CALL( graph->createDecompFromPartition(&(*decdecomps)[n_decs_found]) );
339 
340  auto check = DECdecompGetNLinkingvars((*decdecomps)[n_decs_found]);
341  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Link Vars: %d. ", check);
342 
343  if( (*decdecomps)[n_decs_found] != NULL )
344  {
345  *ndecdecomps += 1;
346  ++n_decs_found;
347  detectordata->found = TRUE;
348  }
349  }
350  delete detectordata->graphs->at(i);
351  detectordata->graphs->at(i) = NULL;
352  }
353 
354  detectordata->graphs->clear();
355  time(&d_e);
356  double elapsed_graphs = difftime(cp1, start);
357  double elapsed_mcl = difftime(d_e, d_s);
358 
359  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d decompositions found.\n", detectordata->n_similarities, *ndecdecomps);
360  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "MCL runtime: graphs: %.2lf, mcl: %.2lf. \n", elapsed_graphs, elapsed_mcl);
361 
362  SCIP_CALL( SCIPreallocMemoryArray(scip, decdecomps, *ndecdecomps) );
363 
364  *result = *ndecdecomps > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
365  if( *ndecdecomps == 0 )
366  {
367  SCIPfreeMemoryArrayNull(scip, decdecomps);
368  }
369  return SCIP_OKAY;
370 }
371 
372 #define propagateSeeedMCL NULL
373 //static
374 //DEC_DECL_PROPAGATESEEED(propagateSeeedMCL)
375 //{ /*lint --e{715}*/
376 //
377 // int nNewSeeeds;
378 // gcg::Seeed* seeed;
379 // gcg::Seeed** newSeeeds;
380 // DEC_DETECTORDATA* detectordata = DECdetectorGetData(detector);
381 // std::vector<SCIP_Real> clockTimes1; /**< vector containing times in seconds */
382 // std::vector<SCIP_Real> clockTimes2; /**< vector containing times in seconds */
383 //
384 // assert(scip != NULL);
385 // assert(detectordata != NULL);
386 // *result = SCIP_DIDNOTFIND;
387 //
388 // seeed = new gcg::Seeed(seeedPropagationData->seeedToPropagate);
389 // seeed->refineToBlocks(seeedPropagationData->seeedpool);
390 // if(!graphCompletible(seeedPropagationData->seeedpool, seeed))
391 // {
392 // delete seeed;
393 // seeedPropagationData->nNewSeeeds = 0;
394 // *result = SCIP_SUCCESS;
395 // return SCIP_OKAY;
396 // }
397 //
398 // detectordata->n_iterations = std::min(detectordata->n_iterations, MAX_N_ITERATIONS);
399 //
400 // Weights w(1, 1, 1, 1, 1, 1);
401 //
402 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting MCL structure:");
403 //
404 // time_t start, cp1, d_s, d_e;
405 // time(&start);
406 //
407 // std::vector<std::string> sim;
408 //
409 // SCIP_CLOCK* temporaryClock;
410 // SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
411 //
412 // if(detectordata->johnsonenable)
413 // {
414 // SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
415 // RowGraphWeighted<GraphGCG>* g = new RowGraphWeighted<GraphGCG>(scip, w);
416 // SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::JOHNSON, gcg::WEIGHT_TYPE::SIM));
417 // detectordata->graphs->push_back(g);
418 // sim.push_back("Johnson");
419 // SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
420 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
421 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
422 // SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
423 // }
424 // if(detectordata->intersectionenable)
425 // {
426 // SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
427 // RowGraphWeighted<GraphGCG>* g = new RowGraphWeighted<GraphGCG>(scip, w);
428 // SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::INTERSECTION, gcg::WEIGHT_TYPE::SIM));
429 // detectordata->graphs->push_back(g);
430 // sim.push_back("Intersection");
431 // SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
432 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
433 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
434 // SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
435 // }
436 // if(detectordata->jaccardenable)
437 // {
438 // SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
439 // RowGraphWeighted<GraphGCG>* g = new RowGraphWeighted<GraphGCG>(scip, w);
440 // SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::JACCARD, gcg::WEIGHT_TYPE::SIM));
441 // detectordata->graphs->push_back(g);
442 // sim.push_back("Jaccard");
443 // SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
444 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
445 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
446 // SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
447 // }
448 // if(detectordata->cosineenable)
449 // {
450 // SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
451 // RowGraphWeighted<GraphGCG>* g = new RowGraphWeighted<GraphGCG>(scip, w);
452 // SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::COSINE, gcg::WEIGHT_TYPE::SIM));
453 // detectordata->graphs->push_back(g);
454 // sim.push_back("Cosine");
455 // SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
456 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
457 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
458 // SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
459 // }
460 // if(detectordata->simpsonenable)
461 // {
462 // SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
463 // RowGraphWeighted<GraphGCG>* g = new RowGraphWeighted<GraphGCG>(scip, w);
464 // SCIP_CALL( g->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed, gcg::DISTANCE_MEASURE::SIMPSON, gcg::WEIGHT_TYPE::SIM));
465 // detectordata->graphs->push_back(g);
466 // sim.push_back("Simspon");
467 // SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
468 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
469 // clockTimes1.push_back(SCIPclockGetTime(temporaryClock));
470 // SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
471 // }
472 // detectordata->n_similarities = (int) detectordata->graphs->size();
473 //
474 //
475 // std::vector<double> inflatefactors(detectordata->n_iterations);
476 // double inflate = 1.1;
477 // for(int i = 0; i < detectordata->n_iterations; i++)
478 // {
479 // inflatefactors[i] = inflate;
480 // inflate += 0.05;
481 // }
482 // time(&cp1);
483 //
484 // int nMaxSeeeds = detectordata->n_iterations * detectordata->graphs->size();
485 // SCIP_CALL( SCIPallocMemoryArray(scip, &(newSeeeds), 2 * nMaxSeeeds) );
486 //
487 //
488 // const int max_blocks = std::min((int)round(0.3 * SCIPgetNConss(scip)), MAX_N_BLOCKS);
489 // int n_seeeds_found = 0;
490 //
491 // nNewSeeeds = 0;
492 // time(&d_s);
493 // for(int i = 0; i < (int)detectordata->graphs->size(); i++)
494 // {
495 // SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
496 // RowGraphWeighted<GraphGCG>* graph = detectordata->graphs->at(i);
497 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n %s similarity:", sim[i].c_str());
498 // int old_n_blocks = -1;
499 // int old_non_cl = -1;
500 // for(int j = 0; j < (int)inflatefactors.size() ; j++ )
501 // {
502 // double inflatefactor = inflatefactors[j];
503 //
504 // // run MCL with different inflate factors
505 // int stoppedAfter;
506 // SCIP_CALL( graph->computePartitionMCLForPartialGraph(seeedPropagationData->seeedpool, seeed, stoppedAfter, inflatefactor, detectordata->postprocenable) );
507 //
508 // int n_blocks;
509 // SCIP_CALL( graph->getNBlocks(n_blocks) );
510 // int non_cl;
511 // SCIP_CALL( graph->nonClustered(non_cl) );
512 //
513 //
514 // // skip the case if we have 1 block (it means we must increase inflate factor) or if the clustering is the same as the last one
515 // if(n_blocks == 1 || (n_blocks == old_n_blocks && non_cl == old_non_cl) )
516 // {
517 // continue;
518 // }
519 // // stop. inflate factor is already too big
520 // if( n_blocks > max_blocks )
521 // {
522 // break;
523 // }
524 //
525 // old_n_blocks = n_blocks;
526 // old_non_cl = non_cl;
527 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\n Inflate factor: %.2f, ", inflatefactor);
528 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Stopped after: %d iters, ", stoppedAfter);
529 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Blocks: %d, Master Conss: %d/%d, ", n_blocks, non_cl, SCIPgetNConss(scip));
530 //
531 // SCIP_CALL( graph->createSeeedFromPartition(seeed,&newSeeeds[n_seeeds_found], &newSeeeds[n_seeeds_found+1], seeedPropagationData->seeedpool));
532 //
533 // if((newSeeeds)[n_seeeds_found] != NULL)
534 // {
535 // nNewSeeeds += 2;
536 // detectordata->found = TRUE;
537 // }
538 // n_seeeds_found += 2;
539 // }
540 // delete detectordata->graphs->at(i);
541 // detectordata->graphs->at(i) = NULL;
542 // SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
543 // clockTimes2.push_back(SCIPclockGetTime(temporaryClock));
544 // clockTimes2.push_back(SCIPclockGetTime(temporaryClock));
545 // SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
546 // }
547 //
548 // delete seeed;
549 // SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), nNewSeeeds) );
550 // seeedPropagationData->nNewSeeeds = nNewSeeeds;
551 // for(int j = 0, s = 0; s < nNewSeeeds; ++j)
552 // {
553 // if(newSeeeds[j] != NULL)
554 // {
555 // seeedPropagationData->newSeeeds[s] = newSeeeds[j];
556 // seeedPropagationData->newSeeeds[s]->addClockTime(clockTimes1[j] + clockTimes2[j]);
557 // seeedPropagationData->newSeeeds[s]->setDetectorPropagated(seeedPropagationData->seeedpool->getIndexForDetector(detector));
558 // ++s;
559 // }
560 // }
561 // SCIPfreeMemoryArray(scip, &newSeeeds);
562 //
563 // detectordata->graphs->clear();
564 // time(&d_e);
565 // double elapsed_graphs = difftime(cp1, start);
566 // double elapsed_mcl = difftime(d_e, d_s);
567 //
568 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d similarities used, %d decompositions found.\n", detectordata->n_similarities, nNewSeeeds);
569 // SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "MCL runtime: graphs: %.2lf, mcl: %.2lf. \n", elapsed_graphs, elapsed_mcl);
570 //
571 // *result = nNewSeeeds > 0 ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
572 // if( nNewSeeeds == 0 )
573 // {
574 // SCIPfreeMemoryArrayNull(scip, &(seeedPropagationData->newSeeeds));
575 // }
576 // SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
577 // return SCIP_OKAY;
578 //}
579 
580 #define finishSeeedMCL NULL
581 
582 #define detectorPostprocessSeeedMCL NULL
583 
584 #define setParamAggressiveMCL NULL
585 #define setParamDefaultMCL NULL
586 #define setParamFastMCL NULL
587 
588 
589 
590 /*
591  * detector specific interface methods
592  */
593 
596  SCIP* scip
597  )
598 {
599 #if !defined(_WIN32) && !defined(_WIN64)
600  DEC_DETECTORDATA *detectordata = NULL;
601  assert(scip != NULL);
602 
603  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
604 
605  assert(detectordata != NULL);
606  detectordata->found = FALSE;
607 
609  detectordata, detectMCL, freeMCL, initMCL, exitMCL, propagateSeeedMCL, NULL, NULL, finishSeeedMCL, detectorPostprocessSeeedMCL, setParamAggressiveMCL, setParamDefaultMCL, setParamFastMCL) );
610 
611  /* add arrowheur presolver parameters */
612  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/mcl/niterations", "Number of iterations to run MCL with different inflate factor (max=20).", &detectordata->n_iterations, FALSE, DEFAULT_N_ITERATIONS, 1, 20, NULL, NULL) );
613  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mcl/johson", "Enable johson distance measure.", &detectordata->johnsonenable, FALSE, DEFAULT_JOHNSON_ENABLE, NULL, NULL ) );
614  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mcl/intersection", "Enable intersection distance measure.", &detectordata->intersectionenable, FALSE, DEFAULT_INTERSECTION_ENABLE, NULL, NULL ) );
615  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mcl/jaccard", "Enable jaccard distance measure.", &detectordata->jaccardenable, FALSE, DEFAULT_JACCARD_ENABLE, NULL, NULL) );
616  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mcl/cosine", "Enable cosine distance measure.", &detectordata->cosineenable, FALSE, DEFAULT_COSINE_ENABLE, NULL, NULL) );
617  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mcl/simpson", "Enable simpson distance measure.", &detectordata->simpsonenable, FALSE, DEFAULT_SIMPSON_ENABLE, NULL, NULL ) );
618  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/mcl/postprocenable", "Enable post-processing step..", &detectordata->postprocenable, FALSE, DEFAULT_POSTPROC_ENABLE, NULL, NULL ) );
619 
620 #endif
621  return SCIP_OKAY;
622 }
detector for diagonal (bordered) structures via MCL clustering algorithm
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_, DISTANCE_MEASURE dist, WEIGHT_TYPE w_type)
static DEC_DECL_EXITDETECTOR(exitMCL)
Definition: dec_mcl.cpp:133
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
static bool graphCompletible(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed)
Definition: dec_mcl.cpp:169
#define propagateSeeedMCL
Definition: dec_mcl.cpp:372
const int * getOpenconss()
returns array containing constraints not assigned yet
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_mcl.cpp:57
virtual SCIP_RETCODE computePartitionMCL(int &stoppedAfter, double inflatefactor, bool postprocenable)
#define DEC_ENABLEDORIGINAL
Definition: dec_mcl.cpp:65
TCLIQUE_GRAPH * graph
Definition: dec_staircase.c:87
virtual SCIP_RETCODE getNBlocks(int &_n_blocks)
static DEC_DECL_FREEDETECTOR(freeMCL)
Definition: dec_mcl.cpp:116
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define MAX_N_ITERATIONS
Definition: dec_mcl.cpp:81
static DEC_DECL_INITDETECTOR(initMCL)
Definition: dec_mcl.cpp:150
SCIP_Bool cosineenable
Definition: dec_dbscan.cpp:95
virtual SCIP_RETCODE nonClustered(int &_non_cl)
#define DEC_ENABLED
Definition: dec_mcl.cpp:64
#define DEFAULT_POSTPROC_ENABLE
Definition: dec_mcl.cpp:80
int getNOpenvars()
returns size of vector containing variables not assigned yet
#define MAX_N_BLOCKS
Definition: dec_mcl.cpp:82
#define DEC_MINCALLROUND
Definition: dec_mcl.cpp:54
#define finishSeeedMCL
Definition: dec_mcl.cpp:580
int DECdecompGetNLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1043
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_mcl.cpp:56
#define DEC_DESC
Definition: dec_mcl.cpp:51
#define DEC_FREQCALLROUND
Definition: dec_mcl.cpp:52
bool isVarOpenvar(int var)
returns true if the var is an open var
#define DEFAULT_COSINE_ENABLE
Definition: dec_mcl.cpp:78
Implementation of the graph which supports both node and edge weights.
#define detectorPostprocessSeeedMCL
Definition: dec_mcl.cpp:582
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
#define setParamAggressiveMCL
Definition: dec_mcl.cpp:584
SCIP_Bool found
Definition: dec_dbscan.cpp:89
#define DEFAULT_INTERSECTION_ENABLE
Definition: dec_mcl.cpp:76
SCIP_RETCODE SCIPincludeDetectorMCL(SCIP *scip)
Definition: dec_mcl.cpp:595
static DEC_DECL_DETECTSTRUCTURE(detectMCL)
Definition: dec_mcl.cpp:221
#define DEC_DECCHAR
Definition: dec_mcl.cpp:59
#define DEFAULT_SIMPSON_ENABLE
Definition: dec_mcl.cpp:79
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_mcl.cpp:55
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_mcl.cpp:68
#define DEC_DETECTORNAME
Definition: dec_mcl.cpp:50
#define DEC_LEGACYMODE
Definition: dec_mcl.cpp:71
#define DEC_PRIORITY
Definition: dec_mcl.cpp:58
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.
#define DEC_MAXCALLROUND
Definition: dec_mcl.cpp:53
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
SCIP_Bool simpsonenable
Definition: dec_dbscan.cpp:96
const int * getOpenvars()
returns array containing variables not assigned yet
#define setParamFastMCL
Definition: dec_mcl.cpp:586
#define DEC_ENABLEDFINISHING
Definition: dec_mcl.cpp:67
#define DEFAULT_N_ITERATIONS
Definition: dec_mcl.cpp:74
int getNOpenconss()
returns size of vector containing constraints not assigned yet
#define DEFAULT_JOHNSON_ENABLE
Definition: dec_mcl.cpp:75
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
#define DEC_SKIP
Definition: dec_mcl.cpp:69
constraint handler for structure detection
#define DEFAULT_JACCARD_ENABLE
Definition: dec_mcl.cpp:77
#define setParamDefaultMCL
Definition: dec_mcl.cpp:585
SCIP_Bool johnsonenable
Definition: dec_dbscan.cpp:92
SCIP_Bool jaccardenable
Definition: dec_dbscan.cpp:94
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
#define DEC_USEFULRECALL
Definition: dec_mcl.cpp:70