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