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