dec_hcgpartition.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 
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42 
43 
44 /* #define SCIP_DEBUG */
45 #include "dec_hcgpartition.h"
46 
47 
48 #if !defined(_WIN32) && !defined(_WIN64)
49 #include <cassert>
50 #include <cstring>
51 #include <cerrno>
52 #include <unistd.h>
53 #include <iostream>
54 #include <vector>
55 #include <algorithm>
56 
57 
58 #include "cons_decomp.h"
59 #include "struct_decomp.h"
60 #include "pub_decomp.h"
61 #include "scip_misc.h"
62 #include "scip/pub_misc.h"
63 #include "scip/cons_linear.h"
64 #include "scip/cons_setppc.h"
65 #include "graph/matrixgraph.h"
66 #include "graph/hypercolgraph.h"
67 #include "graph/graph_tclique.h"
68 #include "graph/weights.h"
69 #include "class_seeed.h"
70 #include "class_seeedpool.h"
71 #include "scip/clock.h"
72 
73 
74 #include <set>
75 
76 using gcg::HypercolGraph;
77 using gcg::MatrixGraph;
78 using gcg::Weights;
79 
80 #define DEC_DETECTORNAME "hcgpartition"
81 #define DEC_DESC "enforces arrowhead structures using graph partitioning"
82 #define DEC_FREQCALLROUND 1
83 #define DEC_MAXCALLROUND 0
84 #define DEC_MINCALLROUND 0
85 #define DEC_FREQCALLROUNDORIGINAL 1
86 #define DEC_MAXCALLROUNDORIGINAL 0
87 #define DEC_MINCALLROUNDORIGINAL 0
88 #define DEC_PRIORITY 1000
89 #define DEC_DECCHAR 'G'
90 #define DEC_ENABLED FALSE
91 #define DEC_ENABLEDORIGINAL FALSE
92 #define DEC_ENABLEDFINISHING FALSE
93 #define DEC_ENABLEDPOSTPROCESSING FALSE
94 #define DEC_SKIP FALSE
95 #define DEC_USEFULRECALL TRUE
96 #define DEC_LEGACYMODE FALSE
99 /* Default parameter settings */
100 #define DEFAULT_VARWEIGHT 1
101 #define DEFAULT_VARWEIGHTBIN 2
102 #define DEFAULT_VARWEIGHTINT 2
103 #define DEFAULT_VARWEIGHTIMPL 2
104 #define DEFAULT_VARWEIGHTCONT 1
105 #define DEFAULT_CONSWEIGHT 5
106 #define DEFAULT_RANDSEED 1
107 #define DEFAULT_TIDY TRUE
108 #define DEFAULT_DUMMYNODES 0.2
109 #define DEFAULT_CONSWEIGHT_SETPPC 5
111 #define DEFAULT_MINBLOCKS 2
112 #define DEFAULT_MAXBLOCKS 20
113 #define DEFAULT_MAXNBLOCKCANDIDATES 1
114 #define DEFAULT_ALPHA 0.0
115 #define DEFAULT_BETA 0.5
117 #define DEFAULT_METIS_UBFACTOR 5.0
118 #define DEFAULT_METIS_VERBOSE FALSE
119 #define DEFAULT_METISUSEPTYPE_RB TRUE
120 #define DEFAULT_REALNAME FALSE
121 #define DEFAULT_TYPE 'r'
125 #define SET_MULTIPLEFORSIZETRANSF 12500
126 
127 /*
128  * Data structures
129  */
130 
132 struct DEC_DetectorData
133 {
134  /* Graph stuff for hmetis */
135  /* weight parameters */
136  int varWeight;
137  int varWeightBinary;
138  int varWeightContinous;
139  int varWeightInteger;
143  SCIP_Real alpha;
144  SCIP_Real beta;
146  /* general parameters */
147  SCIP_Real dummynodes;
148  SCIP_Bool tidy;
149  int maxnblockcandidates;
150  int maxblocks;
151  int minblocks;
153  /* metis parameters */
155  SCIP_Real metisubfactor;
156  SCIP_Bool metisverbose;
157  SCIP_Bool metisuseptyperb;
158  SCIP_Bool realname;
160  /* various data */
161  SCIP_Bool found;
162  char type;
165 };
167 
168 
169 
170 /*
171  * Local methods
172  */
173 
175 static
176 DEC_DECL_FREEDETECTOR(freeHcgpartition)
177 {
178  DEC_DETECTORDATA* detectordata;
179 
180  assert(scip != NULL);
181 
182  detectordata = DECdetectorGetData(detector);
183  assert(detectordata != NULL);
184  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
185 
186  SCIPfreeMemory(scip, &detectordata);
187 
188  return SCIP_OKAY;
189 }
190 
192 static
193 
194 DEC_DECL_INITDETECTOR(initHcgpartition)
195 {
196  int nconss;
197  DEC_DETECTORDATA* detectordata;
198  assert(scip != NULL);
199 
200  detectordata = DECdetectorGetData(detector);
201  assert(detectordata != NULL);
202  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
203 
204  detectordata->found = FALSE;
205 
206  nconss = SCIPgetNConss(scip);
207  detectordata->maxblocks = MIN(nconss, detectordata->maxblocks);
208 
209 
210  return SCIP_OKAY;
211 }
212 
214 static
215 
216 DEC_DECL_EXITDETECTOR(exitHcgpartition)
217 {
218  assert(scip != NULL);
219 
221  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
222 
223 
224  return SCIP_OKAY;
225 }
226 
228 static
229 SCIP_RETCODE callMetis(
230  SCIP* scip,
231  DEC_DETECTORDATA* detectordata,
233  char tempfile[SCIP_MAXSTRLEN],
234  int nblocks,
235  SCIP_RESULT* result
236  )
237 {
238  char metiscall[SCIP_MAXSTRLEN];
239  char metisout[SCIP_MAXSTRLEN];
240 
241  SCIP_CLOCK* metisclock;
242 
243  int status;
244 
245  SCIP_Real remainingtime;
246 
247  assert(scip != NULL);
248  assert(detectordata != NULL);
249 
250  *result = SCIP_DIDNOTRUN;
251 
252  SCIPcreateWallClock(scip, &metisclock);
253  remainingtime = DECgetRemainingTime(scip);
254 
255  if( remainingtime <= 0 )
256  {
257  return SCIP_OKAY;
258  }
259 
260  /* call metis via syscall as there is no library usable ... */
261  if( !SCIPisInfinity(scip, DECgetRemainingTime(scip)) )
262  {
263  (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"ulimit -t %.0f;hmetis %s %d -seed %d -ptype %s -ufactor %f %s\"",
264  remainingtime,
265  tempfile,
266  nblocks,
267  detectordata->randomseed,
268  detectordata->metisuseptyperb ? "rb" : "kway",
269  detectordata->metisubfactor,
270  detectordata->metisverbose ? "" : "> /dev/null" );
271  }
272  else
273  {
274  (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"hmetis %s %d -seed %d -ptype %s -ufactor %f %s\"",
275  tempfile,
276  nblocks,
277  detectordata->randomseed,
278  detectordata->metisuseptyperb ? "rb" : "kway",
279  detectordata->metisubfactor,
280  detectordata->metisverbose ? "" : "> /dev/null" );
281  }
282 
283  SCIP_CALL( SCIPstartClock(scip, metisclock) );
284  SCIPdebugMessage("Calling metis with: %s\n", metiscall);
285  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " %d", nblocks );
286  status = system( metiscall );
287 
288  SCIP_CALL( SCIPstopClock(scip, metisclock) );
289  SCIPdebugMessage("time left before metis started: %f, time metis spend %f, remainingtime: %f\n", remainingtime, SCIPgetClockTime(scip, metisclock), remainingtime-SCIPgetClockTime(scip, metisclock) );
290 
291  SCIP_CALL( SCIPfreeClock(scip, &metisclock) );
292 
293  /* check error codes */
294  if( status == -1 )
295  {
296  SCIPerrorMessage("System call did not succed: %s\n", strerror( errno ));
297  SCIPerrorMessage("Call was %s\n", metiscall);
298  }
299  else if( status != 0 )
300  {
301 
302  SCIPerrorMessage("Calling hmetis unsuccessful! See the above error message for more details.\n");
303  SCIPerrorMessage("Call was %s\n", metiscall);
304  assert(false);
305  }
306 
307  /* exit gracefully in case of errors */
308  if( status != 0 )
309  {
310  return SCIP_ERROR;
311  }
312 
313  (void) SCIPsnprintf(metisout, SCIP_MAXSTRLEN, "%s.part.%d", tempfile, nblocks);
314  SCIP_CALL( graph->readPartition(metisout) );
315 
316  /* if desired delete the temoprary metis file */
317  if( detectordata->tidy )
318  {
319  status = remove( metisout );
320  if( status == -1 )
321  {
322  SCIPerrorMessage("Could not remove metis output file: %s\n", strerror( errno ));
323  return SCIP_WRITEERROR;
324  }
325  }
326  else
327  {
328  SCIPinfoMessage(scip, NULL, "Temporary file is in: %s\n", tempfile);
329  }
330  *result = SCIP_SUCCESS;
331  return SCIP_OKAY;
332 }
333 
335 static
336 SCIP_RETCODE createMetisFile(
337  SCIP* scip,
338  DEC_DETECTORDATA* detectordata,
339  int seeedID,
341  char tempfile[SCIP_MAXSTRLEN]
342  )
343 {
344  int nvertices;
345  int ndummyvertices;
346  int fd;
347  nvertices = graph->getNNonzeroes();
348  /*lint --e{524}*/
349  ndummyvertices = SCIPceil(scip, detectordata->dummynodes*nvertices);
350  graph->setDummynodes(ndummyvertices);
351 
352  if( !detectordata->realname )
353  {
354  (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%c-%d.metis.XXXXXX", DEC_DECCHAR, seeedID );
355  }
356  else
357  {
358  (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%s-%c-%d.metis.XXXXXX", SCIPgetProbName(scip), DEC_DECCHAR, seeedID);
359  }
360 
361  fd = mkstemp(tempfile);
362 
363  SCIP_CALL( graph->writeToFile(fd, TRUE) );
364  close(fd);
365  return SCIP_OKAY;
366 }
367 
369 static
370 bool connected(
371  gcg::Seeedpool* seeedpool,
372  gcg::Seeed* seeed
373  )
374 {
375  std::vector<int> queue;
376  std::vector<int> visited;
377  std::vector<bool> inqueue(seeedpool->getNConss(), false);
378  std::vector<bool> isvisited(seeedpool->getNConss(), false);
379  int start = -1;
380 
381  if(seeed->getNOpenconss() < 2)
382  return false;
383 
384  start = seeed->getOpenconss()[0];
385 
386  queue.push_back(start);
387  inqueue[start] = true;
388  do
389  {
390  int node = queue[0];
391  queue.erase(queue.begin());
392  inqueue[node] = false;
393  visited.push_back(node);
394  isvisited[node] = true;
395  for(int v = 0; v < seeedpool->getNVarsForCons(node); ++v)
396  {
397  int var = seeedpool->getVarsForCons(node)[v];
398  if(!seeed->isVarOpenvar(var))
399  continue;
400  for(int c = 0; c < seeedpool->getNConssForVar(var); ++c)
401  {
402  int cons = seeedpool->getConssForVar(var)[c];
403  if(!seeed->isConsOpencons(cons))
404  continue;
405  if( isvisited[cons] )
406  continue;
407  if( inqueue[cons] )
408  continue;
409  queue.push_back(cons);
410  inqueue[cons] = true;
411  }
412  }
413  } while(!queue.empty());
414 
415  if((int)visited.size() != seeed->getNOpenconss())
416  return false;
417  else
418  return true;
419 }
420 
422 static
423 SCIP_RETCODE detection(
424  SCIP* scip,
425  DEC_DETECTORDATA* detectordata,
426  Seeed_Propagation_Data* seeedPropagationData,
427  gcg::Seeed* seeed,
428  bool border,
429  SCIP_RESULT* result
430 )
431 {
432 
433  /* add hcgpartition presolver parameters */
434  char setstr[SCIP_MAXSTRLEN];
435  char decinfo[SCIP_MAXSTRLEN];
437  int k;
438  int j;
439  int s;
440  int nMaxSeeeds;
441  int nNewSeeeds = 0;
442  gcg::Seeed** newSeeeds;
443  SCIP_CLOCK* clock;
444  SCIP_CLOCK* temporaryClock;
445  std::vector<SCIP_Real> clockTimes;
447  /* Graph stuff for hmetis */
449  char tempfile[SCIP_MAXSTRLEN];
452  SCIP_CALL_ABORT( SCIPcreateClock(scip, &clock) );
453  SCIP_CALL_ABORT( SCIPstartClock(scip, clock) );
454 
455  *result = SCIP_DIDNOTFIND;
456 
457  std::vector<int> numberOfBlocks = seeedPropagationData->seeedpool->getSortedCandidatesNBlocks();
458  if(numberOfBlocks.empty())
459  numberOfBlocks.push_back(8);
460 
461  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/hcgpartition/maxnblockcandidates");
462  SCIP_CALL( SCIPgetIntParam(scip, setstr, &maxnblockcandidates) );
463 
464  maxnblockcandidates = MIN(maxnblockcandidates, (int) numberOfBlocks.size() );
465 
466  assert(scip != NULL);
467  assert(detectordata != NULL);
468 
469  SCIPdebugMessage("Detecting structure from %s\n", DEC_DETECTORNAME);
470  nMaxSeeeds = detectordata->maxblocks-detectordata->minblocks+1;
471 
472  /* allocate space for output data */
473  SCIP_CALL( SCIPallocMemoryArray(scip, &(newSeeeds), 2 * nMaxSeeeds) );
474 
475  /* build the hypergraph structure from the original problem */
476 
477  Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
478  graph = new HypercolGraph<gcg::GraphTclique>(scip, w);
479 
480  SCIP_CALL( graph->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed) );
481  SCIP_CALL( createMetisFile(scip, detectordata, seeed->getID(), graph, tempfile) );
482 
483  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting Arrowhead structure:");
484 
485 
486  SCIP_CALL_ABORT( SCIPstopClock(scip, clock ) );
487  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
488 
489  for( j = 0, k = 0; k < maxnblockcandidates; ++k)
490  {
491  int nblocks = numberOfBlocks[k] - seeed->getNBlocks();
492  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
493  SCIP_RETCODE retcode;
494  if(nblocks > seeed->getNOpenconss() || nblocks <= 0)
495  {
496  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
497  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
498  continue;
499  }
500 
501  retcode = callMetis(scip, detectordata, graph, tempfile, nblocks, result);
502 
503  if( *result != SCIP_SUCCESS || retcode != SCIP_OKAY)
504  {
505  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
506  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
507  continue;
508  }
509 
510  SCIP_CALL( graph->createSeeedFromPartition(seeed, &newSeeeds[j], &newSeeeds[j+1], seeedPropagationData->seeedpool));
511  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
512  if( (newSeeeds)[j] != NULL )
513  {
514  nNewSeeeds = nNewSeeeds + 2;
515  detectordata->found = TRUE;
516  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "hc\\_%d", numberOfBlocks[k]);
517  newSeeeds[j]->addDetectorChainInfo(decinfo);
518  newSeeeds[j+1]->addDetectorChainInfo(decinfo);
519 
520  clockTimes.push_back(SCIPclockGetTime(temporaryClock));
521  clockTimes.push_back(SCIPclockGetTime(temporaryClock)); // 2x because two seeeds where created
522  }
523  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
524  j = j + 2;
525  }
526 
527  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
528  SCIP_CALL_ABORT( SCIPstartClock(scip, clock ) );
529 
530  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d seeeds found.\n", nNewSeeeds);
531 
532  delete graph;
533  graph = NULL;
534 
535  assert(nNewSeeeds % 2 == 0);
536  if(border)
537  {
538  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), nNewSeeeds) );
539  seeedPropagationData->nNewSeeeds = nNewSeeeds;
540  for(j = 0, s = 0; s < nNewSeeeds; ++j)
541  {
542  if(newSeeeds[j] != NULL)
543  {
544  seeedPropagationData->newSeeeds[s] = newSeeeds[j];
545  ++s;
546  }
547  }
548  }
549  else
550  {
551  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), nNewSeeeds/2) );
552  seeedPropagationData->nNewSeeeds = nNewSeeeds/2;
553  for(j = 0, s = 0; s < nNewSeeeds/2; j+=2)
554  {
555  if(newSeeeds[j] != NULL)
556  {
557  seeedPropagationData->newSeeeds[s] = newSeeeds[j];
558  ++s;
559  }
560  }
561  }
562 
563 
564  SCIPfreeMemoryArray(scip, &newSeeeds);
565 
566  if( detectordata->tidy )
567  {
568  int status = remove( tempfile );
569  if( status == -1 )
570  {
571  SCIPerrorMessage("Could not remove metis input file: ", strerror( errno ));
572  SCIP_CALL_ABORT( SCIPstopClock(scip, clock ) );
573  SCIP_CALL_ABORT(SCIPfreeClock(scip, &clock) );
574  return SCIP_WRITEERROR;
575  }
576  }
577 
578  SCIP_CALL_ABORT( SCIPstopClock(scip, clock ) );
579  if(border)
580  {
581  for( s = 0; s < seeedPropagationData->nNewSeeeds; ++s )
582  seeedPropagationData->newSeeeds[s]->addClockTime( SCIPclockGetTime(clock) + clockTimes[s] );
583  }
584  else
585  {
586  for( s = 0; s < seeedPropagationData->nNewSeeeds; ++s )
587  seeedPropagationData->newSeeeds[s]->addClockTime( SCIPclockGetTime(clock) + clockTimes[2*s] );
588  }
589  SCIP_CALL_ABORT(SCIPfreeClock(scip, &clock) );
590 
591  *result = detectordata->found ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
592  return SCIP_OKAY;
593 }
594 
596 static
597 SCIP_RETCODE fromToolbox(
598  SCIP_Bool propagate,
599  SCIP* scip,
600  DEC_DETECTOR* detector,
601  SEEED_PROPAGATION_DATA* seeedPropagationData,
602  SCIP_RESULT* result,
603  SCIP_DIALOGHDLR* dialoghdlr,
604  SCIP_DIALOG* dialog
605  )
606 {
607  /* add hcgpartition presolver parameters */
608  char decinfo[SCIP_MAXSTRLEN];
609  gcg::Seeed** newSeeeds;
610  DEC_DETECTORDATA* detectordata;
611  gcg::Seeed* seeed;
612  SCIP_RETCODE retcode;
613  char* command;
614  int commandlen;
615  SCIP_Bool endoffile;
616  int nblocks;
617  /* Graph stuff for hmetis */
619  char tempfile[SCIP_MAXSTRLEN];
621  seeed = seeedPropagationData->seeedToPropagate;
622  detectordata = DECdetectorGetData(detector);
623 
624  *result = SCIP_DIDNOTFIND;
625 
626  std::vector<int> numberOfBlocks = seeedPropagationData->seeedpool->getSortedCandidatesNBlocks();
627  if(numberOfBlocks.empty())
628  numberOfBlocks.push_back(8);
629 
630  int nconss = seeedPropagationData->seeedpool->getNConss();
631  detectordata->maxblocks = MIN(nconss, detectordata->maxblocks);
632 
633  assert(scip != NULL);
634  assert(detectordata != NULL);
635 
636  SCIPdebugMessage("Detecting structure from %s\n", DEC_DETECTORNAME);
637 
638  /* allocate space for output data */
639  assert(detectordata->maxblocks >= detectordata->minblocks);
640  SCIP_CALL( SCIPallocMemoryArray(scip, &(newSeeeds), 2 ) );
641 
642  /* build the hypergraph structure from the original problem */
643 
644  Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
645  graph = new HypercolGraph<gcg::GraphTclique>(scip, w);
646 
647  SCIP_CALL( graph->createFromPartialMatrix(seeedPropagationData->seeedpool, seeed) );
648  SCIP_CALL( createMetisFile(scip, detectordata, seeed->getID(), graph, tempfile) );
649 
650  detectordata->metisubfactor = DEFAULT_METIS_UBFACTOR; //@TODO: resolve s.t. this parameter does not have to be set manually here
651  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting Arrowhead structure:\n");
652 
653  SCIPinfoMessage(scip, NULL, "Maximal number of blocks the decomposition can contain: %d\n", seeed->getNOpenconss());
654  SCIP_CALL( SCIPdialoghdlrGetWord(dialoghdlr, dialog, "Type in the number of blocks that the decomposition should contain (e.g. \"5\") \nGCG/toolbox> ", &command, &endoffile) );
655  commandlen = strlen(command);
656 
657  if( commandlen != 0 )
658  {
659  nblocks = atoi(command);
660  }
661  else
662  {
663  SCIPinfoMessage(scip, NULL, "Invalid input!\n");
664  return SCIP_OKAY;
665  }
666 
667  if(nblocks > seeed->getNOpenconss() || nblocks <= 0)
668  {
669  SCIPinfoMessage(scip, NULL, "Invalid number of blocks, choose at most %d\n", seeed->getNOpenconss());
670  return SCIP_OKAY;
671  }
672 
673  retcode = callMetis(scip, detectordata, graph, tempfile, nblocks, result);
674 
675  if( *result != SCIP_SUCCESS || retcode != SCIP_OKAY)
676  {
677  *result = SCIP_DIDNOTFIND;
678  return SCIP_OKAY;
679  }
680 
681  if( detectordata->tidy )
682  {
683  int status = remove( tempfile );
684  if( status == -1 )
685  {
686  SCIPerrorMessage("Could not remove metis input file: ", strerror( errno ));
687  return SCIP_WRITEERROR;
688  }
689  }
690 
691  SCIP_CALL( graph->createSeeedFromPartition(seeed, &newSeeeds[0], &newSeeeds[1], seeedPropagationData->seeedpool));
692  delete graph;
693  graph = NULL;
694  if( (newSeeeds)[0] != NULL && !propagate ) //finishing successful
695  {
696  detectordata->found = TRUE;
697  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "hc\\_%d", numberOfBlocks[0]);
698  newSeeeds[0]->addDetectorChainInfo(decinfo);
699  seeedPropagationData->newSeeeds[0] = (newSeeeds)[0];
700  ++(seeedPropagationData->nNewSeeeds);
701  seeedPropagationData->newSeeeds[0]->setFinishingDetectorPropagated(detector);
702  SCIPfreeMemoryArray(scip, &newSeeeds);
703  *result = SCIP_SUCCESS;
704  return SCIP_OKAY;
705  }
706  else if( (newSeeeds)[1] != NULL && propagate ) //propagation successful
707  {
708  detectordata->found = TRUE;
709  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "hc\\_%d", numberOfBlocks[0]);
710  newSeeeds[1]->addDetectorChainInfo(decinfo);
711  seeedPropagationData->newSeeeds[0] = (newSeeeds)[1];
712  ++(seeedPropagationData->nNewSeeeds);
713  seeedPropagationData->newSeeeds[0]->setDetectorPropagated(detector);
714  SCIPfreeMemoryArray(scip, &newSeeeds);
715  *result = SCIP_SUCCESS;
716  return SCIP_OKAY;
717  }
718  else //propagation/finishing unsuccessful
719  {
720  SCIPfreeMemoryArray(scip, &newSeeeds);
721  *result = SCIP_DIDNOTFIND;
722  return SCIP_OKAY;
723  }
724 }
725 
727 static
728 DEC_DECL_DETECTSTRUCTURE(detectHcgpartition)
729 {
730  int i;
731  int j;
732  int ndecs;
733 
735  char tempfile[SCIP_MAXSTRLEN];
737  assert(scip != NULL);
738  assert(detectordata != NULL);
739  assert(decdecomps != NULL);
740  assert(ndecdecomps != NULL);
741 
742  SCIPdebugMessage("Detecting structure from %s\n", DEC_DETECTORNAME);
743  ndecs = detectordata->maxblocks-detectordata->minblocks+1;
744  *ndecdecomps = 0;
745 
746  /* allocate space for output data */
747  assert(detectordata->maxblocks >= detectordata->minblocks);
748  SCIP_CALL( SCIPallocMemoryArray(scip, decdecomps, ndecs) );
749 
750  /* build the hypergraph structure from the original problem */
751 
752  Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
753  graph = new HypercolGraph<gcg::GraphTclique>(scip, w);
754 
755  SCIP_CALL( graph->createFromMatrix(SCIPgetConss(scip), SCIPgetVars(scip), SCIPgetNConss(scip), SCIPgetNVars(scip)) );
756  SCIP_CALL( createMetisFile(scip, detectordata, 0, graph, tempfile) );
757 
758  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting Arrowhead structure:");
759  for( j = 0, i = detectordata->minblocks; i <= detectordata->maxblocks; ++i )
760  {
761  SCIP_RETCODE retcode;
762  /* get the partitions for the new variables from metis */
763  retcode = callMetis(scip, detectordata, graph, tempfile, i, result);
764 
765  if( *result != SCIP_SUCCESS || retcode != SCIP_OKAY )
766  {
767  continue;
768  }
769 
770  SCIP_CALL( graph->createDecompFromPartition(&(*decdecomps)[j]) );
771  if( (*decdecomps)[j] != NULL )
772  {
773  *ndecdecomps += 1;
774  ++j;
775  detectordata->found = TRUE;
776  }
777  }
778  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d decompositions found.\n", *ndecdecomps);
779 
780  delete graph;
781  graph = NULL;
782 
783  SCIP_CALL( SCIPreallocMemoryArray(scip, decdecomps, *ndecdecomps) );
784 
785  if( detectordata->tidy )
786  {
787  int status = remove( tempfile );
788  if( status == -1 )
789  {
790  SCIPerrorMessage("Could not remove metis input file: ", strerror( errno ));
791  return SCIP_WRITEERROR;
792  }
793  }
794 
795 
796  *result = detectordata->found ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
797  return SCIP_OKAY;
798 }
799 #endif
800 
801 
802 static
803 DEC_DECL_PROPAGATESEEED(propagateSeeedHcgpartition)
804 {
805  gcg::Seeed* seeed;
806  seeed = seeedPropagationData->seeedToPropagate;
808  SCIP_CLOCK* temporaryClock;
809  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
810  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
811 
812 
813  //assert( seeed->checkConsistency( seeedPropagationData->seeedpool ));
814 
815  seeed->considerImplicits();
816  //assert( seeed->checkConsistency( seeedPropagationData->seeedpool ));
817 
818  seeed->refineToMaster();
819 
820  //assert( seeed->checkConsistency( seeedPropagationData->seeedpool ));
821 
822  if(!connected(seeedPropagationData->seeedpool, seeed) || seeed->alreadyAssignedConssToBlocks() )
823  {
825  }
826 
827  detection(scip, DECdetectorGetData(detector), seeedPropagationData, seeed, TRUE, result);
828 
829  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
830 
831 
832  for( int s = 0; s < seeedPropagationData->nNewSeeeds; ++s )
833  {
834  seeedPropagationData->newSeeeds[s]->addClockTime( SCIPclockGetTime(temporaryClock ) );
835  }
836 
837  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
838 
839 
840  return SCIP_OKAY;
841 }
842 
843 static
844 DEC_DECL_PROPAGATEFROMTOOLBOX(propagateFromToolboxHcgpartition)
845 {
846  return fromToolbox(TRUE, scip, detector, seeedPropagationData, result, dialoghdlr, dialog );
847 }
849 static
850 DEC_DECL_FINISHFROMTOOLBOX(finishFromToolboxHcgpartition)
851 {
852  return fromToolbox(FALSE, scip, detector, seeedPropagationData, result, dialoghdlr, dialog );
853 }
855 static
856 DEC_DECL_FINISHSEEED(finishSeeedHcgpartition)
857 {
858 
859  SCIP_CLOCK* temporaryClock;
860  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
861  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
862 
863 
864  gcg::Seeed* seeed = seeedPropagationData->seeedToPropagate;
865 
866  seeed->considerImplicits();
867  seeed->refineToBlocks();
868 
869  if( !connected(seeedPropagationData->seeedpool, seeed ) )
870  {
872  }
873 
874  detection(scip, DECdetectorGetData(detector), seeedPropagationData, seeed, FALSE, result);
875 
876  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
877 
878 
879  for( int s = 0; s < seeedPropagationData->nNewSeeeds; ++s )
880  {
881  seeedPropagationData->newSeeeds[s]->considerImplicits();
882  seeedPropagationData->newSeeeds[s]->refineToBlocks();
883  seeedPropagationData->newSeeeds[s]->addClockTime( SCIPclockGetTime(temporaryClock ) );
884  assert(seeedPropagationData->newSeeeds[s]->getNOpenconss() == 0);
885  assert(seeedPropagationData->newSeeeds[s]->getNOpenvars() == 0);
886  }
887 
888  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
889 
890 
891  return SCIP_OKAY;
892 }
893 
894 #define detectorPostprocessSeeedHcgpartition NULL
895 
896 static
897 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHcgpartition)
898 {
899  char setstr[SCIP_MAXSTRLEN];
900  const char* name = DECdetectorGetName(detector);
901  int newval;
902  SCIP_Real modifier;
903 
904  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
905  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
906 
907  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
908  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
909 
910  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
911  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
912 
913  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxcallround", name);
914  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
915  ++newval;
916  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
917  SCIPinfoMessage(scip, NULL, "After Setting %s = %d\n", setstr, newval);
918 
919 
920  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origmaxcallround", name);
921  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
922  ++newval;
923  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
924  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
925 
926  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
927  {
928  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
929  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
930  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
931  return SCIP_OKAY;
932  }
933 
934  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
935 
936  modifier = log(modifier) / log(2);
937 
938  if (!SCIPisFeasPositive(scip, modifier) )
939  modifier = -1.;
940 
941  modifier = SCIPfloor(scip, modifier);
942  modifier += 1;
943 
944  newval = MAX( 0, DEFAULT_MAXNBLOCKCANDIDATES - modifier + 2 );
945  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
946  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
947  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
948 
949  return SCIP_OKAY;
950 
951 }
952 
953 
954 static
955 DEC_DECL_SETPARAMDEFAULT(setParamDefaultHcgpartition)
956 {
957  char setstr[SCIP_MAXSTRLEN];
958  int newval;
959  SCIP_Real modifier;
960 
961  const char* name = DECdetectorGetName(detector);
962 
963  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
964  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
965 
966  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
967  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDORIGINAL) );
968 
969  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
970  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
971 
972  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
973  {
974  return SCIP_OKAY;
975  }
976 
977  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
978 
979  modifier = log(modifier) / log(2);
980 
981  if (!SCIPisFeasPositive(scip, modifier) )
982  modifier = -1.;
983 
984  modifier = SCIPfloor(scip, modifier);
985  modifier += 1;
986 
987  newval = MAX( 0, DEFAULT_MAXNBLOCKCANDIDATES - modifier );
988  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
989  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
990  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
991 
992 
993 
994  return SCIP_OKAY;
995 
996 }
997 
998 static
999 DEC_DECL_SETPARAMFAST(setParamFastHcgpartition)
1000 {
1001  char setstr[SCIP_MAXSTRLEN];
1002  int newval;
1003  SCIP_Real modifier;
1004 
1005 
1006  const char* name = DECdetectorGetName(detector);
1007 
1008  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
1009  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
1010 
1011  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
1012  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
1013 
1014  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
1015  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
1016 
1017  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
1018  {
1019  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
1020  SCIP_CALL( SCIPsetIntParam(scip, setstr, DEFAULT_MAXNBLOCKCANDIDATES ) );
1021  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, DEFAULT_MAXNBLOCKCANDIDATES);
1022  return SCIP_OKAY;
1023  }
1024 
1025 
1026  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
1027 
1028  modifier = log(modifier) / log(2);
1029 
1030  if (!SCIPisFeasPositive(scip, modifier) )
1031  modifier = -1.;
1032 
1033  modifier = SCIPfloor(scip, modifier);
1034  modifier += 1;
1035 
1036  newval = MAX( 0, DEFAULT_MAXNBLOCKCANDIDATES - modifier - 2 );
1037  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
1038  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1039  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1040 
1041  return SCIP_OKAY;
1042 
1043 }
1044 
1045 
1046 
1048 extern "C"
1049 SCIP_RETCODE SCIPincludeDetectorHcgpartition(
1050  SCIP* scip
1051  )
1052 {
1053 #if !defined(_WIN32) && !defined(_WIN64)
1054  DEC_DETECTORDATA *detectordata = NULL;
1055  assert(scip != NULL);
1056 
1057  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
1058  assert(detectordata != NULL);
1059 
1060 
1061  SCIP_CALL( DECincludeDetector(scip, DEC_DETECTORNAME, DEC_DECCHAR, DEC_DESC, DEC_FREQCALLROUND, DEC_MAXCALLROUND, DEC_MINCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_ENABLED, DEC_ENABLEDORIGINAL, DEC_ENABLEDFINISHING, DEC_ENABLEDPOSTPROCESSING, DEC_SKIP, DEC_USEFULRECALL, DEC_LEGACYMODE, detectordata, detectHcgpartition, freeHcgpartition, initHcgpartition, exitHcgpartition, propagateSeeedHcgpartition, propagateFromToolboxHcgpartition, finishFromToolboxHcgpartition, finishSeeedHcgpartition, detectorPostprocessSeeedHcgpartition, setParamAggressiveHcgpartition, setParamDefaultHcgpartition, setParamFastHcgpartition) );
1062 
1063 
1064  /* add hcgpartition detector parameters */
1065  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/maxnblockcandidates", "The maximal number of block number candidates", &detectordata->maxnblockcandidates, FALSE, DEFAULT_MAXNBLOCKCANDIDATES, 0, 1000000, NULL, NULL) );
1066  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/maxblocks", "The maximal number of blocks (only used in legacy mode; detector is called for all block numbers in [minblocks,maxblocks])", &detectordata->maxblocks, FALSE, DEFAULT_MAXBLOCKS, 2, 1000000, NULL, NULL) );
1067  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/minblocks", "The minimal number of blocks (only used in legacy mode; detector is called for all block numbers in [minblocks,maxblocks])", &detectordata->minblocks, FALSE, DEFAULT_MINBLOCKS, 2, 1000000, NULL, NULL) );
1068  SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/beta", "Factor on how heavy equality (beta) and inequality constraints are measured", &detectordata->beta, FALSE, DEFAULT_BETA, 0.0, 1.0, NULL, NULL ) );
1069  SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/alpha", "Factor on how heavy the standard deviation of the coefficients is measured", &detectordata->alpha, FALSE, DEFAULT_ALPHA, 0.0, 1E20, NULL, NULL ) );
1070  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeight", "Weight of a variable hyperedge", &detectordata->varWeight, FALSE, DEFAULT_VARWEIGHT, 0, 1000000, NULL, NULL) );
1071  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightBinary", "Weight of a binary variable hyperedge", &detectordata->varWeightBinary, FALSE, DEFAULT_VARWEIGHTBIN, 0, 1000000, NULL, NULL) );
1072  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightContinous", "Weight of a continuos variable hyperedge", &detectordata->varWeightContinous, FALSE, DEFAULT_VARWEIGHTCONT, 0, 1000000, NULL, NULL) );
1073  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightImplint", "Weight of a implicit integer variable hyperedge", &detectordata->varWeightImplint, FALSE, DEFAULT_VARWEIGHTIMPL, 0, 1000000, NULL, NULL) );
1074  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/varWeightInteger", "Weight of a integer variable hyperedge", &detectordata->varWeightInteger, FALSE, DEFAULT_VARWEIGHTINT, 0, 1000000, NULL, NULL) );
1075  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/consWeight", "Weight of a constraint hyperedge", &detectordata->consWeight, FALSE, DEFAULT_CONSWEIGHT, 0, 1000000, NULL, NULL) );
1076  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/tidy", "Whether to clean up temporary files", &detectordata->tidy, FALSE, DEFAULT_TIDY, NULL, NULL) );
1077  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/randomseed", "Random seed for hmetis", &detectordata->randomseed, FALSE, DEFAULT_RANDSEED, -1, INT_MAX, NULL, NULL) );
1078  SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/dummynodes", "Percentage of dummy nodes for metis", &detectordata->dummynodes, FALSE, DEFAULT_DUMMYNODES, 0.0, 1.0, NULL, NULL) );
1079  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hcgpartition/consWeightSetppc", "Weight for constraint hyperedges that are setpartitioning or covering constraints", &detectordata->consWeightSetppc, FALSE, DEFAULT_CONSWEIGHT_SETPPC, 0, 1000000, NULL, NULL) );
1080  SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hcgpartition/ubfactor", "Unbalance factor for metis", &detectordata->metisubfactor, FALSE, DEFAULT_METIS_UBFACTOR, 0.0, 1E20, NULL, NULL ) );
1081  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/metisverbose", "Should the metis output be displayed", &detectordata->metisverbose, FALSE, DEFAULT_METIS_VERBOSE, NULL, NULL ) );
1082  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/metisuseptyperb", "Should the rb or kway method be used for partitioning by metis", &detectordata->metisuseptyperb, FALSE, DEFAULT_METISUSEPTYPE_RB, NULL, NULL) );
1083  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hcgpartition/realname", "Should the problem be used for metis files or a temporary name", &detectordata->realname, FALSE, DEFAULT_REALNAME, NULL, NULL) );
1084 
1085 #endif
1086  return SCIP_OKAY;
1087 }
SCIP_RETCODE considerImplicits()
: assigns every open cons/var in the following manner:
arrowhead and bordered detector via graph partitioning (uses hmetis)
#define SET_MULTIPLEFORSIZETRANSF
#define DEC_ENABLED
SCIP_Real DECgetRemainingTime(SCIP *scip)
returns the remaining time of scip that the decomposition may use
struct DEC_Detector DEC_DETECTOR
Definition: type_detector.h:46
gcg::Seeedpool * seeedpool
miscellaneous matrixgraph methods for structure detection
std::vector< int > getSortedCandidatesNBlocks()
returns the candidates for number of blocks added by the user followed by the found ones sorted in de...
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Seeed_Propagation_Data *seeedPropagationData, gcg::Seeed *seeed, bool border, SCIP_RESULT *result)
#define DEFAULT_VARWEIGHTINT
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
SCIP_RETCODE SCIPincludeDetectorHcgpartition(SCIP *scip)
#define DEC_ENABLEDPOSTPROCESSING
const int * getOpenconss()
returns array containing constraints not assigned yet
#define DEFAULT_CONSWEIGHT
SCIP_Bool metisverbose
#define DEFAULT_VARWEIGHTIMPL
#define DEC_DETECTORNAME
TCLIQUE_GRAPH * graph
Definition: dec_staircase.c:87
#define DEC_MAXCALLROUND
static DEC_DECL_PROPAGATEFROMTOOLBOX(propagateFromToolboxHcgpartition)
#define DEC_DECCHAR
#define DEFAULT_ALPHA
static DEC_DECL_FINISHSEEED(finishSeeedHcgpartition)
static DEC_DECL_FREEDETECTOR(freeHcgpartition)
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
SCIP_RETCODE setFinishingDetectorPropagated(DEC_DETECTOR *detector)
sets seeed to be finished by a detector
#define DEFAULT_METIS_VERBOSE
virtual SCIP_RETCODE writeToFile(int fd, SCIP_Bool writeweights)
Definition: matrixgraph.h:79
#define DEC_DESC
static DEC_DECL_EXITDETECTOR(exitHcgpartition)
static SCIP_RETCODE fromToolbox(SCIP_Bool propagate, SCIP *scip, DEC_DETECTOR *detector, SEEED_PROPAGATION_DATA *seeedPropagationData, SCIP_RESULT *result, SCIP_DIALOGHDLR *dialoghdlr, SCIP_DIALOG *dialog)
#define DEFAULT_REALNAME
#define DEC_USEFULRECALL
static bool connected(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed)
#define DEFAULT_METIS_UBFACTOR
#define DEC_PRIORITY
static DEC_DECL_DETECTSTRUCTURE(detectHcgpartition)
int getNConssForVar(int varIndex)
virtual int getNNonzeroes() const
Definition: matrixgraph.h:152
#define DEFAULT_CONSWEIGHT_SETPPC
virtual SCIP_RETCODE createFromPartialMatrix(Seeedpool *seeedpool, Seeed *seeed)
Definition: matrixgraph.h:146
#define DEFAULT_BETA
SCIP_RETCODE refineToMaster()
refine seeed with focus on master: do obvious (
int getNConss()
returns the number of variables considered in the seeedpool
static DEC_DECL_SETPARAMFAST(setParamFastHcgpartition)
bool isVarOpenvar(int var)
returns true if the var is an open var
weight class for graphs
bool alreadyAssignedConssToBlocks()
method to check if at leas one constraint is assigned to some block
SCIP_Real metisubfactor
#define DEFAULT_MINBLOCKS
#define DEC_FREQCALLROUND
static DEC_DECL_FINISHFROMTOOLBOX(finishFromToolboxHcgpartition)
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
gcg::Seeed * seeedToPropagate
#define DEFAULT_VARWEIGHTBIN
SCIP_RETCODE setDetectorPropagated(DEC_DETECTOR *detector)
sets seeed to be propagated by a detector
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHcgpartition)
#define DEFAULT_MAXBLOCKS
const int * getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
SCIP_Bool found
Definition: dec_dbscan.cpp:89
int getID()
returns the unique id of the seeed
Column hypergraph.
void addDetectorChainInfo(const char *decinfo)
adds a detectorchain information string to the corresponding vector (that carries information for eac...
#define DEC_MAXCALLROUNDORIGINAL
#define DEC_SKIP
#define DEFAULT_DUMMYNODES
virtual SCIP_RETCODE createDecompFromPartition(DEC_DECOMP **decomp)
Definition: matrixgraph.h:89
void setDummynodes(int dummynodes_)
Definition: matrixgraph.h:122
#define DEC_FREQCALLROUNDORIGINAL
static SCIP_RETCODE callMetis(SCIP *scip, DEC_DETECTORDATA *detectordata, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN], int nblocks, SCIP_RESULT *result)
#define DEC_ENABLEDFINISHING
virtual SCIP_RETCODE createFromMatrix(SCIP_CONS **conss, SCIP_VAR **vars, int nconss_, int nvars_)
Definition: matrixgraph.h:138
SCIP_Bool metisuseptyperb
int getNBlocks()
returns the number of blocks
#define DEC_LEGACYMODE
#define DEFAULT_VARWEIGHT
static DEC_DECL_INITDETECTOR(initHcgpartition)
#define DEFAULT_VARWEIGHTCONT
#define DEFAULT_MAXNBLOCKCANDIDATES
#define DEFAULT_RANDSEED
virtual SCIP_RETCODE createSeeedFromPartition(Seeed *oldSeeed, Seeed **firstSeeed, Seeed **secondSeeed, Seeedpool *seeedpool)
Definition: matrixgraph.h:99
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_ENABLEDORIGINAL
virtual SCIP_RETCODE readPartition(const char *filename)
Definition: matrixgraph.h:113
#define DEC_MINCALLROUNDORIGINAL
bool isConsOpencons(int cons)
returns true if the cons is an open cons
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultHcgpartition)
int getNOpenconss()
returns size of vector containing constraints not assigned yet
SCIP_RETCODE assignSmallestComponentsButOneConssAdjacency()
computes components corresponding to connectedness of conss and vars as in
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
#define DEFAULT_METISUSEPTYPE_RB
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
interface to the SCIP tclique graph library
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
static DEC_DECL_PROPAGATESEEED(propagateSeeedHcgpartition)
static SCIP_RETCODE createMetisFile(SCIP *scip, DEC_DETECTORDATA *detectordata, int seeedID, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN])
void addClockTime(SCIP_Real clocktime)
incorporates the needed time of a certain detector in the detector chain
interface data structure for the detector calling methods
#define DEFAULT_TIDY
constraint handler for structure detection
#define detectorPostprocessSeeedHcgpartition
public methods for working with decomposition structures
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
#define DEC_MINCALLROUND