Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file dec_hrgpartition.cpp
29  * @ingroup DETECTORS
30  * @brief arrowhead and bordered detector via graph partitioning (uses hmetis)
31  * @author Martin Bergner
32  *
33  * Detects arrowhead (double bordered) decompositions as well as decompositions
34  * with only linking variables or linking constraints.
35  *
36  * This detector needs hmetis and works only under Linux/MacOS, it further needs the Z-shell (zsh)
37  * to enforce memory and time limits on hmetis as this is the only shell reliably doing that.
38  */
39 
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 #include <queue>
54 
55 #ifdef HMETIS_HEADER
56 #include "hmetis.h"
57 #else
58 #define HMETIS_EXECUTABLE "hmetis"
59 #endif
60 
61 #include "cons_decomp.h"
62 #include "struct_decomp.h"
63 #include "pub_decomp.h"
64 #include "scip_misc.h"
65 #include "scip/pub_misc.h"
66 #include "scip/cons_linear.h"
67 #include "scip/cons_setppc.h"
68 #include "graph/matrixgraph.h"
69 #include "graph/hyperrowgraph.h"
70 #include "graph/graph_tclique.h"
71 #include "graph/weights.h"
72 #include "class_partialdecomp.h"
73 #include "class_detprobdata.h"
74 #include "scip/clock.h"
75 
76 
77 #include <set>
78 
79 using gcg::HyperrowGraph;
80 using gcg::MatrixGraph;
81 using gcg::Weights;
82 
83 #define DEC_DETECTORNAME "hrgpartition" /**< name of the detector */
84 #define DEC_DESC "enforces arrowhead structures using graph partitioning" /**< description of detector */
85 #define DEC_FREQCALLROUND 1 /**< frequency the detector gets called in detection loop ,ie it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0 */
86 #define DEC_MAXCALLROUND 0 /**< last round the detector gets called */
87 #define DEC_MINCALLROUND 0 /**< first round the detector gets called */
88 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
89 #define DEC_MAXCALLROUNDORIGINAL 0 /**< last round the detector gets called while detecting the original problem */
90 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
91 #define DEC_PRIORITY 1000 /**< priority of the detector */
92 #define DEC_DECCHAR 'r' /**< display character of detector */
93 #define DEC_ENABLED FALSE /**< should detector be called by default */
94 #define DEC_ENABLEDFINISHING FALSE /**< should the finishing be enabled */
95 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the postprocessing be enabled */
96 #define DEC_SKIP FALSE /**< should detector be skipped if others found detections */
97 #define DEC_USEFULRECALL TRUE /**< is it useful to call this detector on a descendant of the propagated partialdec */
98 
99 
100 /* Default parameter settings */
101 #define DEFAULT_VARWEIGHT 1 /**< weight for variable nodes */
102 #define DEFAULT_VARWEIGHTBIN 2 /**< weight for binary variable nodes */
103 #define DEFAULT_VARWEIGHTINT 2 /**< weight for integer variable nodes */
104 #define DEFAULT_VARWEIGHTIMPL 2 /**< weight for implicit integer variable nodes */
105 #define DEFAULT_VARWEIGHTCONT 1 /**< weight for continous variable nodes */
106 #define DEFAULT_CONSWEIGHT 5 /**< weight for constraint hyperedges */
107 #define DEFAULT_RANDSEED 1 /**< random seed for the hmetis call */
108 #define DEFAULT_TIDY TRUE /**< whether to clean up afterwards */
109 #define DEFAULT_DUMMYNODES 0.2 /**< percentage of dummy vertices*/
110 #define DEFAULT_CONSWEIGHT_SETPPC 5 /**< weight for constraint hyperedges that are setpartitioning or covering
111  constraints */
112 
113 #define DEFAULT_LIMITNCONSSNVARSDEFAULT 10000 /**< limit for sum of nvars and nconss for enabling this detector in default */
114 #define DEFAULT_ENABLEDFORLARGEPROBLEMS FALSE /** should this detector be enabled even the limit nconssnvars is exceeded */
115 
116 #define DEFAULT_MINBLOCKS 2 /**< value for the minimum number of blocks to be considered */
117 #define DEFAULT_MAXBLOCKS 20 /**< value for the maximum number of blocks to be considered */
118 #define DEFAULT_MAXNBLOCKCANDIDATES 3 /**< number of block number candidates to be considered */
119 #define DEFAULT_ALPHA 0.0 /**< factor for standard deviation of constraint weights */
120 #define DEFAULT_BETA 0.5 /**< factor of how the weight for equality and inequality constraints is
121  distributed (keep 1/2 for the same on both) */
122 #define DEFAULT_METIS_UBFACTOR 5.0 /**< default unbalance factor given to metis on the commandline */
123 #define DEFAULT_METIS_VERBOSE FALSE /**< should metis be verbose */
124 #define DEFAULT_METISUSEPTYPE_RB TRUE /**< Should metis use the rb or kway partitioning algorithm */
125 #define DEFAULT_REALNAME FALSE /**< whether the metis name should be real or temporary */
126 #define DEFAULT_TYPE 'r' /**< type of the decomposition 'c' column hypergraph (single bordered, no
127  linking constraints), 'r' row hypergraph (single bordered, no linking
128  variables) and 'a' column-row hypergraph (arrowhead) */
129 #define DEFAULT_FALLBACK_NBLOCKS 8
130 #define SET_MULTIPLEFORSIZETRANSF 12500
131 
132 /*
133  * Data structures
134  */
135 
136 /** private detector data */
137 struct DEC_DetectorData
138 {
139 
140  /* weight parameters */
141  int varWeight; /**< weight of a variable hyperedge */
142  int varWeightBinary; /**< weight of a binary variable hyperedge */
143  int varWeightContinous; /**< weight of a continuous variable hyperedge */
144  int varWeightInteger; /**< weight of an integer variable hyperedge */
145  int varWeightImplint; /**< weight of an implicit integer variable hyperedge */
146  int consWeight; /**< weight of a constraint hyperedge */
147  int consWeightSetppc; /**< weight of a setppc constraint hyperedge */
148  SCIP_Real alpha; /**< factor for constraint coefficient value standard deviation */
149  SCIP_Real beta; /**< factor for equality od inequality constraints */
150 
151  /* general parameters */
152  SCIP_Real dummynodes; /**< percent of dummy nodes */
153  SCIP_Bool tidy; /**< whether tempory metis files should be cleaned up */
154  int limitnconssnvarsdefault; /**< limit for sum of nvars and nconss for enabling this detector in default*/
156 
157  int maxnblockcandidates; /**< maximal number of block canddidates to test */
158  int maxblocks; /**< maximal number of blocks to test */
159  int minblocks; /**< minimal number of blocks to test */
160 
161  /* metis parameters */
162  int randomseed; /**< metis random seed */
163  SCIP_Real metisubfactor; /**< metis unbalance factor */
164  SCIP_Bool metisverbose; /**< should metis ouput be displayed */
165  SCIP_Bool metisuseptyperb; /**< flag to indicate whether metis uses kway or rb partitioning */
166  SCIP_Bool realname; /**< flag to indicate real problem name or temporary filename for metis files */
167 
168  /* various data */
169  SCIP_Bool found; /**< indicates whethere a decomposition has been found */
170  char type; /**< type of the decomposition 'c' column hypergraph (single bordered, no linking
171  constraints), 'r' row hypergraph (single bordered, no linking variables) and
172  'a' column-row hypergraph (arrowhead) */
173 };
174 
175 
176 
177 
178 /*
179  * Local methods
180  */
181 
182 /* put your local methods here, and declare them static */
183 
184 
185 
186 /** destructor of detector to free user data (called when GCG is exiting) */
187 static
188 DEC_DECL_FREEDETECTOR(freeHrgpartition)
189 {
190  DEC_DETECTORDATA* detectordata;
191 
192  assert(scip != NULL);
193 
194  detectordata = DECdetectorGetData(detector);
195  assert(detectordata != NULL);
196  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
197 
198  SCIPfreeMemory(scip, &detectordata);
199 
200  return SCIP_OKAY;
201 }
202 
203 
204 
205 /** detector initialization method */
206 static
207 DEC_DECL_INITDETECTOR(initHrgpartition)
208 {
209  int nconss;
210  DEC_DETECTORDATA* detectordata;
211  assert(scip != NULL);
212 
213 
214  detectordata = DECdetectorGetData(detector);
215  assert(detectordata != NULL);
216  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
217 
218  nconss = SCIPgetNConss(scip);
219  detectordata->maxblocks = MIN(nconss, detectordata->maxblocks);
220 
221 
222 
223  return SCIP_OKAY;
224 }
225 
226 /** presolving deinitialization method of presolver (called after presolving has been finished) */
227 static
228 DEC_DECL_EXITDETECTOR(exitHrgpartition)
229 {
230 
231  assert(scip != NULL);
232 
233  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
234 
235 
236  return SCIP_OKAY;
237 }
238 
239 /** will call hmetis via a system call */
240 static
241 SCIP_RETCODE callMetis(
242  SCIP* scip, /**< SCIP data struture */
243  DEC_DETECTORDATA* detectordata, /**< presolver data data structure */
244  MatrixGraph<gcg::GraphTclique>* graph, /**< the graph of the matrix */
245  char tempfile[SCIP_MAXSTRLEN], /**< filename for the metis input file */
246  int nblocks, /**< number of blocks */
247  SCIP_RESULT* result /**< result indicating whether the detection was successful */
248  )
249 {
250  char metiscall[SCIP_MAXSTRLEN];
251  char metisout[SCIP_MAXSTRLEN];
252  SCIP_CLOCK* metisclock;
253 
254  int status;
255 
256  SCIP_Real remainingtime;
257 
258  assert(scip != NULL);
259  assert(detectordata != NULL);
260 
261  *result = SCIP_DIDNOTRUN;
262 
263  remainingtime = DECgetRemainingTime(scip);
264  SCIP_CALL( SCIPcreateWallClock(scip, &metisclock) );
265 
266  if( remainingtime <= 0 )
267  {
268  return SCIP_OKAY;
269  }
270 
271  /* call metis via syscall as there is no library usable ... */
272  if( !SCIPisInfinity(scip, DECgetRemainingTime(scip)) )
273  {
274  (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"ulimit -t %.0f;" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
275  remainingtime,
276  tempfile,
277  nblocks,
278  detectordata->randomseed,
279  detectordata->metisuseptyperb ? "rb" : "kway",
280  detectordata->metisubfactor,
281  detectordata->metisverbose ? "" : "> /dev/null" );
282  }
283  else
284  {
285  (void) SCIPsnprintf(metiscall, SCIP_MAXSTRLEN, "zsh -c \"" HMETIS_EXECUTABLE " %s %d -seed %d -ptype %s -ufactor %f %s\"",
286  tempfile,
287  nblocks,
288  detectordata->randomseed,
289  detectordata->metisuseptyperb ? "rb" : "kway",
290  detectordata->metisubfactor,
291  detectordata->metisverbose ? "" : "> /dev/null" );
292  }
293 
294  SCIP_CALL( SCIPstartClock(scip, metisclock) );
295  SCIPdebugMessage("Calling metis with: %s\n", metiscall);
296  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " %d", nblocks );
297  status = system( metiscall );
298 
299  SCIP_CALL( SCIPstopClock(scip, metisclock) );
300  SCIPdebugMessage("time left before metis started: %f, time metis spend %f, remainingtime: %f\n", remainingtime, SCIPgetClockTime(scip, metisclock), remainingtime-SCIPgetClockTime(scip, metisclock) );
301 
302  SCIP_CALL( SCIPfreeClock(scip, &metisclock) );
303 
304  /* check error codes */
305  if( status == -1 )
306  {
307  SCIPerrorMessage("System call did not succed: %s\n", strerror( errno ));
308  SCIPerrorMessage("Call was %s\n", metiscall);
309  }
310  else if( status != 0 )
311  {
312 
313  SCIPerrorMessage("Calling hmetis unsuccessful! See the above error message for more details.\n");
314  SCIPerrorMessage("Call was %s\n", metiscall);
315  }
316 
317  /* exit gracefully in case of errors */
318  if( status != 0 )
319  {
320  return SCIP_ERROR;
321  }
322 
323  (void) SCIPsnprintf(metisout, SCIP_MAXSTRLEN, "%s.part.%d", tempfile, nblocks);
324  SCIP_CALL( graph->readPartition(metisout) );
325 
326  /* if desired delete the temoprary metis file */
327  if( detectordata->tidy )
328  {
329  status = remove( metisout );
330  if( status == -1 )
331  {
332  SCIPerrorMessage("Could not remove metis output file: %s\n", strerror( errno ));
333  return SCIP_WRITEERROR;
334  }
335  }
336  else
337  {
338  SCIPinfoMessage(scip, NULL, "Temporary file is in: %s\n", tempfile);
339  }
340  *result = SCIP_SUCCESS;
341  return SCIP_OKAY;
342 }
343 
344 /** creates the temporary metis input file */
345 static
346 SCIP_RETCODE createMetisFile(
347  SCIP* scip, /**< SCIP data struture */
348  DEC_DETECTORDATA* detectordata, /**< detector data structure */
349  int partialdecID, /**< ID of partial decomposition to be used */
350  MatrixGraph<gcg::GraphTclique>* graph, /**< the graph of the matrix */
351  char tempfile[SCIP_MAXSTRLEN] /**< filename for the metis input file */
352 
353  )
354 {
355  int nvertices;
356  int ndummyvertices;
357  int fd;
358  nvertices = graph->getNNonzeroes();
359  /*lint --e{524}*/
360  ndummyvertices = SCIPceil(scip, detectordata->dummynodes*nvertices);
361  graph->setDummynodes(ndummyvertices);
362 
363  if( !detectordata->realname )
364  {
365  (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%c-%d.metis.XXXXXX", DEC_DECCHAR, partialdecID );
366  }
367  else
368  {
369  (void) SCIPsnprintf(tempfile, SCIP_MAXSTRLEN, "gcg-%s-%s-%c.metis.XXXXXX", SCIPgetProbName(scip), DEC_DECCHAR, partialdecID);
370  }
371 
372  fd = mkstemp(tempfile);
373 
374  SCIP_CALL( graph->writeToFile(fd, TRUE) );
375  close(fd);
376  return SCIP_OKAY;
377 }
378 
379 /** @returns whether the hyperrolgraph is connected */
380 static
382  gcg::DETPROBDATA* detprobdata,
383  gcg::PARTIALDECOMP* partialdec
384  )
385 {
386  std::vector<int> queue;
387  std::vector<int> visited;
388  std::vector<bool> inqueue(detprobdata->getNVars(), false);
389  std::vector<bool> isvisited(detprobdata->getNVars(), false);
390  int start = -1;
391 
392  if(partialdec->getNOpenvars() < 2)
393  return false;
394 
395  start = partialdec->getOpenvars()[0];
396  queue.push_back(start);
397  inqueue[start] = true;
398  do
399  {
400  int node = queue[0];
401  queue.erase(queue.begin());
402  inqueue[node] = false;
403  visited.push_back(node);
404  isvisited[node] = true;
405  for( int c = 0; c < detprobdata->getNConssForVar(node); ++c )
406  {
407  int cons = detprobdata->getConssForVar(node)[c];
408  if(!partialdec->isConsOpencons(cons))
409  continue;
410  for( int v = 0; v < detprobdata->getNVarsForCons(cons); ++v )
411  {
412  int var = detprobdata->getVarsForCons(cons)[v];
413  if( !partialdec->isVarOpenvar(var) )
414  continue;
415  if( isvisited[var] )
416  continue;
417  if( inqueue[var] )
418  continue;
419  queue.push_back(var);
420  inqueue[var] = true;
421  }
422  }
423  } while( !queue.empty() );
424 
425  if((int)visited.size() != partialdec->getNOpenvars())
426  return false;
427  else
428  return true;
429 }
430 
431 /** detection function for partialdecs */
432 static
433 SCIP_RETCODE detection(
434  SCIP* scip, /**< SCIP data structure */
435  DEC_DETECTORDATA* detectordata, /**< detectordata of the detector */
436  Partialdec_Detection_Data* partialdecdetectiondata, /**< partialdecdetectiondata (including the detprobdata) where to store the new Partialdecs */
437  gcg::PARTIALDECOMP* partialdec, /**< partialdec to propagate */
438  bool allowopenpartialdecs, /**< whether new partialdecs should be stored in which this detector only assignes conss to master */
439  SCIP_RESULT* result /**< pointer where to store the result */
440 )
441 {
442  /* add hrgpartition presolver parameters */
443  char setstr[SCIP_MAXSTRLEN];
444  char decinfo[SCIP_MAXSTRLEN];
445  int maxnblockcandidates;
446  int k;
447  int j;
448  int s;
449  int nMaxPartialdecs;
450  gcg::PARTIALDECOMP** newpartialdecs;
451  SCIP_CLOCK* clock;
452  SCIP_CLOCK* temporaryClock;
453  std::vector<SCIP_Real> clockTimes; /* vector containing times in seconds */
454 
455  /* Graph stuff for hmetis */
456  MatrixGraph<gcg::GraphTclique>* graph; /* the graph of the matrix */
457  char tempfile[SCIP_MAXSTRLEN]; /**< filename for the metis input file */
458 
459  SCIP_CALL_ABORT( SCIPcreateClock(scip, &clock) );
460  SCIP_CALL_ABORT( SCIPstartClock(scip, clock) );
461 
462  *result = SCIP_DIDNOTFIND;
463 
464  std::vector<int> numberOfBlocks;
465  partialdecdetectiondata->detprobdata->getSortedCandidatesNBlocks(numberOfBlocks);
466  if( numberOfBlocks.empty() )
467  numberOfBlocks.push_back(DEFAULT_FALLBACK_NBLOCKS);
468 
469  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/hrgpartition/maxnblockcandidates");
470  SCIP_CALL( SCIPgetIntParam(scip, setstr, &maxnblockcandidates) );
471 
472  maxnblockcandidates = MIN(maxnblockcandidates, (int) numberOfBlocks.size() );
473 
474  SCIPdebugMessage("number of block numbers to test: %d\n", maxnblockcandidates);
475 
476  assert(scip != NULL);
477  assert(detectordata != NULL);
478 
479  SCIPdebugMessage("Detecting structure from %s\n", DEC_DETECTORNAME);
480  nMaxPartialdecs = detectordata->maxblocks-detectordata->minblocks+1;
481 
482  /* allocate space for output data */
483  SCIP_CALL( SCIPallocMemoryArray(scip, &(newpartialdecs), 2 * nMaxPartialdecs) );
484 
485  /* build the hypergraph structure from the original problem */
486 
487  Weights w(detectordata->varWeight, detectordata->varWeightBinary, detectordata->varWeightContinous,detectordata->varWeightInteger,detectordata->varWeightInteger,detectordata->consWeight);
488  graph = new HyperrowGraph<gcg::GraphTclique>(scip, w);
489 
490  SCIP_CALL( graph->createFromPartialMatrix(partialdecdetectiondata->detprobdata, partialdec) );
491  SCIP_CALL( createMetisFile(scip, detectordata, partialdec->getID(), graph, tempfile) );
492 
493  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting Arrowhead structure:");
494 
495  SCIP_CALL_ABORT( SCIPstopClock(scip, clock ) );
496  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
497 
498  for( j = 0, k = 0; k < maxnblockcandidates; ++k )
499  {
500  int nblocks = numberOfBlocks[k] - partialdec->getNBlocks();
501  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
502  SCIP_RETCODE retcode;
503 
504  if( nblocks > partialdec->getNOpenvars() || nblocks <= 1 )
505  {
506  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
507  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
508  continue;
509  }
510 
511  retcode = callMetis(scip, detectordata, graph, tempfile, nblocks, result);
512 
513  if( *result != SCIP_SUCCESS || retcode != SCIP_OKAY)
514  {
515  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
516  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
517  continue;
518  }
519 
520  if( allowopenpartialdecs )
521  {
522  SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], &newpartialdecs[j+1], partialdecdetectiondata->detprobdata));
523  }
524  else
525  {
526  SCIP_CALL( graph->createPartialdecFromPartition(partialdec, &newpartialdecs[j], NULL, partialdecdetectiondata->detprobdata));
527  }
528 
529  if( newpartialdecs[j] != NULL )
530  {
531  if( !allowopenpartialdecs )
532  {
533  newpartialdecs[j]->considerImplicits();
534  newpartialdecs[j]->refineToBlocks();
535  assert(newpartialdecs[j]->getNOpenconss() == 0);
536  assert(newpartialdecs[j]->getNOpenvars() == 0);
537  }
538  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
539 
540  detectordata->found = TRUE;
541  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "hr\\_%d", numberOfBlocks[k]);
542  newpartialdecs[j]->addDetectorChainInfo(decinfo);
543 
544  if( allowopenpartialdecs )
545  {
546  clockTimes.push_back(SCIPgetClockTime(scip, temporaryClock) / 2);
547  clockTimes.push_back(SCIPgetClockTime(scip, temporaryClock) / 2);
548  newpartialdecs[j + 1]->addDetectorChainInfo(decinfo);
549  j += 2;
550  }
551  else
552  {
553  clockTimes.push_back(SCIPgetClockTime(scip, temporaryClock));
554  j++;
555  }
556  }
557  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
558  }
559  delete graph;
560 
561  int nnewpartialdecs = j;
562  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " done, %d partialdecs found.\n", nnewpartialdecs);
563  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), nnewpartialdecs) );
564  partialdecdetectiondata->nnewpartialdecs = nnewpartialdecs;
565  for( s = 0; s < nnewpartialdecs; ++s )
566  {
567  partialdecdetectiondata->newpartialdecs[s] = newpartialdecs[s];
568  partialdecdetectiondata->newpartialdecs[s]->addClockTime(clockTimes[s] + SCIPgetClockTime(scip, temporaryClock) / nnewpartialdecs);
569  }
570 
571  SCIPfreeMemoryArray(scip, &newpartialdecs);
572  SCIP_CALL_ABORT( SCIPfreeClock(scip, &temporaryClock) );
573  SCIP_CALL_ABORT( SCIPfreeClock(scip, &clock) );
574 
575  if( detectordata->tidy )
576  {
577  int status = remove( tempfile );
578  if( status == -1 )
579  {
580  SCIPerrorMessage("Could not remove metis input file: %s", strerror( errno ));
581  return SCIP_WRITEERROR;
582  }
583  }
584 
585  *result = detectordata->found ? SCIP_SUCCESS: SCIP_DIDNOTFIND;
586  return SCIP_OKAY;
587 }
588 
589 
590 #endif
591 
592 
593 static
594 DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecHrgpartition)
595 {
596  SCIP_CLOCK* temporaryClock;
597  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
598  SCIP_Bool enabledforlarge;
599  int limit;
600 
601  SCIPgetBoolParam(scip, "detection/detectors/hrgpartition/enabledforlargeproblems", &enabledforlarge);
602  SCIPgetIntParam(scip, "detection/detectors/hrgpartition/limitnconssnvarsdefault", &limit);
603 
604  if ( !enabledforlarge && (SCIPgetNConss(scip) + SCIPgetNVars(scip) > limit) )
605  {
606  partialdecdetectiondata->detectiontime = 0;
607  partialdecdetectiondata->nnewpartialdecs = 0;
608  *result = SCIP_SUCCESS;
609  return SCIP_OKAY;
610  }
611 
612  SCIPdebugMessage("Started propagate partialdec of detector %s and partial decomp %d \n", DEC_DETECTORNAME, partialdec->getID() );
613 
614  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
615  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
616 
617  partialdec->considerImplicits();
618  partialdec->refineToMaster();
619 
620  if( partialdec->alreadyAssignedConssToBlocks() )
621  {
622  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
623  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
624  partialdecdetectiondata->detectiontime = 0;
625  partialdecdetectiondata->nnewpartialdecs = 0;
626  *result = SCIP_SUCCESS;
627  return SCIP_OKAY;
628  }
629 
630  if( !connected(partialdecdetectiondata->detprobdata, partialdec) )
631  {
633  }
634 
635  detection(scip, DECdetectorGetData(detector), partialdecdetectiondata, partialdec, true, result);
636 
637  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
638  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
639  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
640 
641  return SCIP_OKAY;
642 }
643 
644 
645 #define finishPartialdecHrgpartition NULL
646 #define detectorPostprocessPartialdecHrgpartition NULL
647 
648 
649 static
650 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHrgpartition)
651 {
652  char setstr[SCIP_MAXSTRLEN];
653  const char* name = DECdetectorGetName(detector);
654  int newval;
655  SCIP_Real modifier;
656 
657  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
658  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
659 
660  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
661  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
662 
663  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxcallround", name);
664  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
665  ++newval;
666  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
667  SCIPinfoMessage(scip, NULL, "After Setting %s = %d\n", setstr, newval);
668 
669 
670  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origmaxcallround", name);
671  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
672  ++newval;
673  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
674 
675  /* check if no problem is read */
676  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
677  {
678  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
679  SCIP_CALL( SCIPsetIntParam(scip, setstr, DEFAULT_MAXNBLOCKCANDIDATES ) );
680  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, DEFAULT_MAXNBLOCKCANDIDATES);
681  return SCIP_OKAY;
682  }
683 
684  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
685 
686  modifier = log(modifier) / log(2);
687 
688  if (!SCIPisFeasPositive(scip, modifier) )
689  modifier = -1.;
690 
691  modifier = SCIPfloor(scip, modifier);
692  modifier += 1;
693 
694  newval = MAX( 0, DEFAULT_MAXNBLOCKCANDIDATES - modifier + 2 );
695  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
696  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
697  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
698 
699  return SCIP_OKAY;
700 }
701 
702 
703 static
704 DEC_DECL_SETPARAMDEFAULT(setParamDefaultHrgpartition)
705 {
706  char setstr[SCIP_MAXSTRLEN];
707  int newval;
708  SCIP_Real modifier;
709 
710  const char* name = DECdetectorGetName(detector);
711 
712  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
713  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
714 
715  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
716  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
717 
718  /* check if no problem is read */
719  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
720  {
721  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
722  SCIP_CALL( SCIPsetIntParam(scip, setstr, DEFAULT_MAXNBLOCKCANDIDATES ) );
723  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, DEFAULT_MAXNBLOCKCANDIDATES);
724  return SCIP_OKAY;
725  }
726 
727  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
728 
729  modifier = log(modifier) / log(2);
730 
731  if (!SCIPisFeasPositive(scip, modifier) )
732  modifier = -1.;
733 
734  modifier = SCIPfloor(scip, modifier);
735  modifier += 1;
736 
737  newval = MAX( 0, DEFAULT_MAXNBLOCKCANDIDATES - modifier );
738  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
739  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
740  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
741 
742  return SCIP_OKAY;
743 }
744 
745 static
746 DEC_DECL_SETPARAMFAST(setParamFastHrgpartition)
747 {
748  char setstr[SCIP_MAXSTRLEN];
749  int newval;
750  SCIP_Real modifier;
751 
752  const char* name = DECdetectorGetName(detector);
753 
754  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
755  if ( SCIPgetStage(scip) >= SCIP_STAGE_PROBLEM && SCIPgetNConss(scip) + SCIPgetNVars(scip) < 6000 )
756  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
757  else SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
758 
759  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
760  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
761 
762  /* check if no problem is read */
763  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
764  {
765  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
766  SCIP_CALL( SCIPsetIntParam(scip, setstr, DEFAULT_MAXNBLOCKCANDIDATES ) );
767  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, DEFAULT_MAXNBLOCKCANDIDATES);
768  return SCIP_OKAY;
769  }
770 
771  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
772 
773  modifier = log(modifier) / log(2);
774 
775  if (!SCIPisFeasPositive(scip, modifier) )
776  modifier = -1.;
777 
778  modifier = SCIPfloor(scip, modifier);
779  modifier += 1;
780 
781  newval = MAX( 0, DEFAULT_MAXNBLOCKCANDIDATES - modifier - 2 );
782  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxnblockcandidates", name);
783  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
784  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
785 
786  return SCIP_OKAY;
787 }
788 
789 
790 /** creates the hrgpartition presolver and includes it in SCIP */
791 extern "C"
793  SCIP* scip /**< SCIP data structure */
794  )
795 {
796 #if !defined(_WIN32) && !defined(_WIN64)
797  DEC_DETECTORDATA *detectordata = NULL;
798  assert(scip != NULL);
799 
800  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
801 
802  assert(detectordata != NULL);
803  detectordata->found = FALSE;
804 
805  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_ENABLEDFINISHING,DEC_ENABLEDPOSTPROCESSING, DEC_SKIP, DEC_USEFULRECALL, detectordata, freeHrgpartition, initHrgpartition, exitHrgpartition, propagatePartialdecHrgpartition, finishPartialdecHrgpartition, detectorPostprocessPartialdecHrgpartition, setParamAggressiveHrgpartition, setParamDefaultHrgpartition, setParamFastHrgpartition) );
806 
807  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) );
808 
809  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) );
810 
811  /* add hrgpartition presolver parameters */
812  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/maxnblockcandidates", "The maximal number of block number candidates", &detectordata->maxnblockcandidates, FALSE, DEFAULT_MAXNBLOCKCANDIDATES, 0, 1000000, NULL, NULL) );
813  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/maxblocks", "The maximal number of blocks (detector is called for all block numbers in [minblocks,maxblocks])", &detectordata->maxblocks, FALSE, DEFAULT_MAXBLOCKS, 2, 1000000, NULL, NULL) );
814  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/minblocks", "The minimal number of blocks (detector is called for all block numbers in [minblocks,maxblocks])", &detectordata->minblocks, FALSE, DEFAULT_MINBLOCKS, 2, 1000000, NULL, NULL) );
815  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 ) );
816  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 ) );
817  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeight", "Weight of a variable hyperedge", &detectordata->varWeight, FALSE, DEFAULT_VARWEIGHT, 0, 1000000, NULL, NULL) );
818  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightBinary", "Weight of a binary variable hyperedge", &detectordata->varWeightBinary, FALSE, DEFAULT_VARWEIGHTBIN, 0, 1000000, NULL, NULL) );
819  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightContinous", "Weight of a continuos variable hyperedge", &detectordata->varWeightContinous, FALSE, DEFAULT_VARWEIGHTCONT, 0, 1000000, NULL, NULL) );
820  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightImplint", "Weight of a implicit integer variable hyperedge", &detectordata->varWeightImplint, FALSE, DEFAULT_VARWEIGHTIMPL, 0, 1000000, NULL, NULL) );
821  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/varWeightInteger", "Weight of a integer variable hyperedge", &detectordata->varWeightInteger, FALSE, DEFAULT_VARWEIGHTINT, 0, 1000000, NULL, NULL) );
822  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/consWeight", "Weight of a constraint hyperedge", &detectordata->consWeight, FALSE, DEFAULT_CONSWEIGHT, 0, 1000000, NULL, NULL) );
823  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/tidy", "Whether to clean up temporary files", &detectordata->tidy, FALSE, DEFAULT_TIDY, NULL, NULL) );
824  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/hrgpartition/randomseed", "Random seed for hmetis", &detectordata->randomseed, FALSE, DEFAULT_RANDSEED, -1, INT_MAX, NULL, NULL) );
825  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) );
826  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) );
827  SCIP_CALL( SCIPaddRealParam(scip, "detection/detectors/hrgpartition/ubfactor", "Unbalance factor for metis", &detectordata->metisubfactor, FALSE, DEFAULT_METIS_UBFACTOR, 0.0, 1E20, NULL, NULL ) );
828  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/hrgpartition/metisverbose", "Should the metis output be displayed", &detectordata->metisverbose, FALSE, DEFAULT_METIS_VERBOSE, NULL, NULL ) );
829  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) );
830  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) );
831 #endif
832  return SCIP_OKAY;
833 }
static bool connected(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
#define DEFAULT_METIS_UBFACTOR
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
structure information for decomposition information in GCG projects
#define DEFAULT_VARWEIGHTBIN
int getNOpenvars()
Gets size of vector containing variables not assigned yet.
static SCIP_RETCODE createMetisFile(SCIP *scip, DEC_DETECTORDATA *detectordata, int partialdecID, MatrixGraph< gcg::GraphTclique > *graph, char tempfile[SCIP_MAXSTRLEN])
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
miscellaneous matrixgraph methods for structure detection
#define DEC_DETECTORNAME
#define DEFAULT_VARWEIGHTINT
static DEC_DECL_INITDETECTOR(initHrgpartition)
constraint handler for structure detection
bool isVarOpenvar(int var)
Checks whether the var is an open var.
weight class for graphs
void getSortedCandidatesNBlocks(std::vector< int > &candidates)
gets the candidates for number of blocks added by the user followed by the found ones sorted in desce...
#define DEFAULT_METISUSEPTYPE_RB
#define DEFAULT_CONSWEIGHT
#define DEC_FREQCALLROUND
virtual SCIP_RETCODE writeToFile(int fd, SCIP_Bool writeweights)
Definition: matrixgraph.h:79
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
#define DEFAULT_MAXBLOCKS
virtual SCIP_RETCODE createFromPartialMatrix(DETPROBDATA *detprobdata, PARTIALDECOMP *partialdec)
Definition: matrixgraph.h:146
std::vector< int > & getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
various SCIP helper methods
SCIP_Bool found
Definition: dec_dbscan.cpp:90
SCIP_Real DECgetRemainingTime(SCIP *scip)
returns the remaining time of scip that the decomposition may use
#define DEC_SKIP
void considerImplicits()
: assigns every open cons/var
#define DEFAULT_VARWEIGHT
#define DEC_FREQCALLROUNDORIGINAL
#define DEFAULT_VARWEIGHTIMPL
void setDummynodes(int dummynodes_)
Definition: matrixgraph.h:122
#define DEC_MINCALLROUNDORIGINAL
#define DEFAULT_BETA
int getNVars()
return the number of variables considered in the detprobdata
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
interface data structure for the detector calling methods
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveHrgpartition)
void refineToBlocks()
refine partialdec with focus on blocks
interface to the SCIP tclique graph library
#define DEFAULT_LIMITNCONSSNVARSDEFAULT
#define DEC_MAXCALLROUNDORIGINAL
#define DEC_ENABLEDFINISHING
gcg::DETPROBDATA * detprobdata
#define DEFAULT_METIS_VERBOSE
#define DEFAULT_RANDSEED
#define DEC_MINCALLROUND
void assignSmallestComponentsButOneConssAdjacency()
computes components by connectedness of conss and vars
static DEC_DECL_EXITDETECTOR(exitHrgpartition)
arrowhead and bordered detector via graph partitioning (uses hmetis)
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecHrgpartition)
virtual int getNNonzeroes() const
Definition: matrixgraph.h:152
#define HMETIS_EXECUTABLE
static SCIP_RETCODE detection(SCIP *scip, DEC_DETECTORDATA *detectordata, Partialdec_Detection_Data *partialdecdetectiondata, gcg::PARTIALDECOMP *partialdec, bool allowopenpartialdecs, SCIP_RESULT *result)
#define DEC_DECCHAR
static DEC_DECL_FREEDETECTOR(freeHrgpartition)
#define detectorPostprocessPartialdecHrgpartition
Column hypergraph.
class to manage partial decompositions
int getNBlocks()
Gets the number of blocks.
#define DEFAULT_REALNAME
gcg::PARTIALDECOMP ** newpartialdecs
#define DEC_MAXCALLROUND
#define DEFAULT_FALLBACK_NBLOCKS
virtual SCIP_RETCODE readPartition(const char *filename)
Definition: matrixgraph.h:113
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
#define DEFAULT_ENABLEDFORLARGEPROBLEMS
SCIP_RETCODE DECincludeDetector(SCIP *scip, const char *name, const char decchar, const char *description, int freqCallRound, int maxCallRound, int minCallRound, int freqCallRoundOriginal, int maxCallRoundOriginal, int minCallRoundOriginal, int priority, SCIP_Bool enabled, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, DEC_DETECTORDATA *detectordata, DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATEPARTIALDEC((*propagatePartialdecDetector)), DEC_DECL_FINISHPARTIALDEC((*finishPartialdecDetector)), DEC_DECL_POSTPROCESSPARTIALDEC((*postprocessPartialdecDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
#define DEFAULT_CONSWEIGHT_SETPPC
#define DEC_DESC
bool isConsOpencons(int cons)
Gets whether the cons is an open cons.
#define DEC_USEFULRECALL
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultHrgpartition)
int getID()
returns the unique id of the partialdec
class storing (potentially incomplete) decompositions
#define DEC_ENABLEDPOSTPROCESSING
#define DEC_ENABLED
bool alreadyAssignedConssToBlocks()
method to check if at least one constraint is assigned to some block
SCIP_Bool enabledforlargeproblems
int getNConssForVar(int varIndex)
returns the number of constraints for a given variable where the var has a nonzero entry in
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
#define finishPartialdecHrgpartition
#define DEFAULT_DUMMYNODES
#define DEFAULT_MINBLOCKS
#define DEFAULT_ALPHA
void refineToMaster()
refine partialdec with focus on master
const int * getOpenvars()
Gets array containing variables not assigned yet.
#define DEFAULT_TIDY
class storing partialdecs and the problem matrix
SCIP_RETCODE SCIPincludeDetectorHrgpartition(SCIP *scip)
#define DEFAULT_VARWEIGHTCONT
static DEC_DECL_SETPARAMFAST(setParamFastHrgpartition)
virtual SCIP_RETCODE createPartialdecFromPartition(PARTIALDECOMP *oldpartialdec, PARTIALDECOMP **firstpartialdec, PARTIALDECOMP **secondpartialdec, DETPROBDATA *detprobdata)
Definition: matrixgraph.h:99
public methods for working with decomposition structures
#define DEC_PRIORITY
#define DEFAULT_MAXNBLOCKCANDIDATES