Scippy

SCIP

Solving Constraint Integer Programs

reduce_termsepafull.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reduce_termsepafull.c
17  * @brief several terminal-separator/exact solution reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements terminal-separator based reduction techniques for Steiner tree problems.
21  * These techniques require to solve subproblems to optimality. See reduce_termsepada.c for related,
22  * but heuristic methods (based on dual-ascent).
23  *
24  * A list of all interface methods can be found in reduce.h.
25  *
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 //#define SCIP_DEBUG
30 
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <assert.h>
35 #include "graph.h"
36 #include "solstp.h"
37 #include "reduce.h"
38 #include "mincut.h"
39 #include "portab.h"
40 #include "substpsolver.h"
41 #include "extreduce.h"
42 #include "stpvector.h"
43 #include "scip/scip.h"
44 
45 #define SEPARATOR_MAXSIZE 4
46 #define SEPARATOR_MAXNCHECKS 75
47 #define SEPARATOR_MINTERMRATIO 0.1
48 #define SEPARATOR_MINEFFTERMRATIO 0.3
49 #define COMPONENT_MAXNODESRATIO_2SEPA 0.5
50 #define COMPONENT_MAXNODESRATIO_3SEPA 0.1
51 #define COMPONENT_MAXNODESRATIO_4SEPA 0.025
52 
53 #define COMPONENT_MAXNODESRATIO_1CANDS 0.8
54 #define COMPONENT_MAXNODESRATIO_2CANDS 0.33
55 #define COMPONENT_MAXNODESRATIO_3CANDS 0.15
56 #define COMPONENT_MAXNODESRATIO_4CANDS 0.08
57 #define COMPONENT_MAXNODESRATIO_5PLUSCANDS 0.02
58 
59 
60 /*
61  * Data structures
62  */
63 
64 /** full terminal separator reduction data structure */
66 {
67  STP_Vectype(int*) subsols; /**< stores all required solutions to the current component */
68  DISTDATA* subdistdata; /**< distance data on sub-problem */
69  GRAPH* subgraph; /**< component graph NON-OWNED */
70  SCIP_Real* subgraph_bcosts; /**< edge costs with bottleneck distances */
71  SCIP_Real* subgraph_orgcosts; /**< original edge costs, with artificial edges having cost FARAWAY */
72  STP_Vectype(int*) solcands_sepaedges; /**< bottleneck edges (w.r.t. subgraph) for each solution candidate */
73  STP_Vectype(int*) solcands_sepapart; /**< partition of the separator terminals for each solution candidate */
74  int nsolcands; /**< number of solution candidates */
75 } TSEPAFULL;
76 
77 
78 /** for computing all partitions of a given ground set */
79 typedef struct bell_parititioner
80 {
81  STP_Vectype(int*) partitions; /**< all partitions; each stores as array with mark 0,1,..., according to subset membership
82  of each element 0,...,nelems - 1*/
83  int nelems; /**< number of elements of ground set */
84  int npartitions; /**< number of partitions */
85 } BPARTITIONS;
86 
87 
88 /*
89  * Local methods
90  */
91 
92 
93 /* gets number of partition groups */
94 static
96  int nelems, /**< number of elements */
97  const int* partition /**< group id for each element; 0,1,... */
98  )
99 {
100  int ngroups = 0;
101 
102  assert(nelems > 0);
103  assert(partition);
104 
105  for( int i = 0; i < nelems; i++ )
106  {
107  const int group = partition[i];
108  assert(0 <= group && group < nelems);
109 
110  if( group > ngroups )
111  ngroups = group;
112  }
113 
114  ngroups++;
115 
116  SCIPdebugMessage("number of partition groups: %d \n", ngroups);
117 
118  return ngroups;
119 }
120 
121 
122 /* gets groups sizes */
123 static
125  int nelems, /**< number of elements */
126  int ngroups, /**< number of groups */
127  const int* partition, /**< group id for each element; 0,1,... */
128  int* groups_sizes /**< to be filled: size of each group */
129  )
130 {
131  assert(nelems > 0);
132  assert(partition && groups_sizes);
133  assert(ngroups == getPartitionNgroups(nelems, partition));
134 
135  BMSclearMemoryArray(groups_sizes, ngroups);
136 
137  for( int i = 0; i < nelems; i++ )
138  {
139  const int group = partition[i];
140  assert(0 <= group && group < ngroups);
141 
142  groups_sizes[group]++;
143  }
144 }
145 
146 
147 /** prints top partition if SCIP_DEBUG is defined */
148 static
150  const BPARTITIONS* bparitions /**< to print for */
151  )
152 {
153  assert(bparitions);
154  assert(StpVecGetSize(bparitions->partitions) > 0);
155 
156 #ifdef SCIP_DEBUG
157  SCIPdebugMessage("partition: \n");
158  for( int i = 0; i < bparitions->nelems; i++ )
159  {
160  const int* const partition = bparitions->partitions[StpVecGetSize(bparitions->partitions) - 1];
161  printf("%d ", partition[i]);
162  }
163  printf("\n");
164 #endif
165 }
166 
167 
168 /** recursive add
169  * NOTE: not extremely efficient, only meant for small sizes */
170 static
172  SCIP* scip, /**< SCIP data structure */
173  int subsize, /**< size of subgroup */
174  int maxgroupid, /**< maximum id for partition subset, also marks subset
175  which will be further parititioned */
176  BPARTITIONS* bparts /**< bell partitions */
177  )
178 {
179 
180  assert(0 < subsize && subsize <= bparts->nelems);
181  assert(maxgroupid >= 0);
182  assert(StpVecGetSize(bparts->partitions) > 0);
183 
184  if( subsize >= 2 )
185  {
186  const int* const basepartition = bparts->partitions[StpVecGetSize(bparts->partitions) - 1];
187  const int length = subsize - 1;
188  const uint32_t powsize = (uint32_t) pow(2.0, length);
189  const int nelems = bparts->nelems;
190  const int id0 = maxgroupid;
191  const int id1 = maxgroupid + 1;
192 
193  assert(basepartition);
194 
195  for( uint32_t counter = powsize - 1; counter >= 1; counter-- )
196  {
197  int* partition;
198  int pos;
199  int subsubsize = 0;
200 
201  /* we get the previous partition, and split the group with the highest ID further */
202  SCIP_CALL( SCIPallocMemoryArray(scip, &partition, nelems) );
203  BMScopyMemoryArray(partition, basepartition, nelems);
204 
205  for( pos = 0; pos < nelems; pos++ )
206  {
207  if( partition[pos] == maxgroupid )
208  {
209  partition[pos] = id0;
210  break;
211  }
212  }
213  assert(pos != nelems);
214 
215  for( uint32_t j = 0; j < (uint32_t) length; j++ )
216  {
217  pos++;
218  for( ; pos < nelems; pos++ )
219  if( partition[pos] == maxgroupid )
220  break;
221 
222  assert(pos != nelems);
223 
224  /* Check if jth bit in counter is set */
225  if( counter & ((uint32_t) 1 << j) )
226  {
227  partition[pos] = id1;
228  subsubsize++;
229  }
230  else
231  {
232  partition[pos] = id0;
233  }
234  }
235 
236  StpVecPushBack(scip, bparts->partitions, partition);
237  bpartitionsDebugPrintTop(bparts);
238 
239  SCIP_CALL( bsubpartAdd(scip, subsubsize, id1, bparts) );
240  }
241  }
242 
243  return SCIP_OKAY;
244 }
245 
246 
247 /** computes partitions */
248 static
250  SCIP* scip, /**< SCIP data structure */
251  BPARTITIONS* bparts /**< bell partitions */
252  )
253 {
254  int* part0;
255  const int maxgroupid = 0;
256  const int nelems = bparts->nelems;
257 
258  assert(nelems >= 2);
259  assert(StpVecGetSize(bparts->partitions) == 0);
260 
261  SCIP_CALL( SCIPallocMemoryArray(scip, &part0, nelems) );
262  for( int i = 0; i < bparts->nelems; i++ )
263  part0[i] = maxgroupid;
264 
265  StpVecPushBack(scip, bparts->partitions, part0);
266  bpartitionsDebugPrintTop(bparts);
267 
268  /* start the recursion */
269  SCIP_CALL( bsubpartAdd(scip, nelems, maxgroupid, bparts) );
270 
271  bparts->npartitions = StpVecGetSize(bparts->partitions);
272  assert(bparts->npartitions >= 2);
273 
274 #ifndef NDEBUG
275  if( bparts->nelems == 2 )
276  {
277  assert(bparts->npartitions == 2);
278  }
279  else if( bparts->nelems == 3 )
280  {
281  assert(bparts->npartitions == 5);
282  }
283  else if( bparts->nelems == 4 )
284  {
285  assert(bparts->npartitions == 15);
286  }
287 #endif
288 
289 
290  return SCIP_OKAY;
291 }
292 
293 
294 /** initializes */
295 static
297  SCIP* scip, /**< SCIP data structure */
298  int nelems, /**< number of elements of ground set */
299  BPARTITIONS** bparitions /**< to initialize */
300  )
301 {
302  BPARTITIONS* bparts;
303 
304  assert(scip);
305  assert(nelems >= 2);
306 
307  SCIP_CALL( SCIPallocMemory(scip, bparitions) );
308  bparts = *bparitions;
309 
310  bparts->partitions = NULL;
311  bparts->nelems = nelems;
312  bparts->npartitions = 0;
313 
314  return SCIP_OKAY;
315 }
316 
317 
318 /** frees */
319 static
321  SCIP* scip, /**< SCIP data structure */
322  BPARTITIONS** bparitions /**< to initialize */
323  )
324 {
325  BPARTITIONS* bparts;
326  bparts = *bparitions;
327 
328  assert(scip);
329 
330  for( int i = StpVecGetSize(bparts->partitions) - 1; i >= 0; i-- )
331  {
332  SCIPfreeMemoryArrayNull(scip, &(bparts->partitions[i]));
333  }
334  StpVecFree(scip, bparts->partitions);
335 
336  SCIPfreeMemory(scip, bparitions);
337 }
338 
339 
340 
341 /** sets up distance data for subgraph */
342 static
344  SCIP* scip, /**< SCIP data structure */
345  TERMCOMP* termcomp, /**< component */
346  TSEPAFULL* tsepafull /**< to initialize for */
347  )
348 {
349  GRAPH* subgraph = termcomp->subgraph;
350  const SCIP_Bool useSd = TRUE;
351  // todo test the impact of bias. Could be activated again
352  // if the separator terminals are not used for computing profits
353  const SCIP_Bool useBias = FALSE;
354 
355  assert(tsepafull);
356  assert(!tsepafull->subdistdata);
357 
358  SCIP_CALL( graph_init_dcsr(scip, subgraph) );
359  SCIP_CALL( extreduce_distDataInit(scip, subgraph, 50, useSd, useBias, &(tsepafull->subdistdata)) );
360  graph_free_dcsr(scip, subgraph);
361 
362  return SCIP_OKAY;
363 }
364 
365 
366 /** initializes */
367 static
369  SCIP* scip, /**< SCIP data structure */
370  GRAPH* subgraph, /**< component graph */
371  TSEPAFULL** tsepafull /**< to initialize */
372  )
373 {
374  TSEPAFULL* tfull;
375 
376  assert(scip && subgraph);
377 
378  SCIP_CALL( SCIPallocMemory(scip, tsepafull) );
379  tfull = *tsepafull;
380 
381  tfull->subsols = NULL;
382  tfull->subgraph = subgraph;
383  tfull->solcands_sepaedges = NULL;
384  tfull->solcands_sepapart = NULL;
385  tfull->nsolcands = 0;
386  tfull->subgraph_bcosts = NULL;
387  tfull->subgraph_orgcosts = NULL;
388  tfull->subdistdata = NULL;
389 
390  return SCIP_OKAY;
391 }
392 
393 
394 /** frees */
395 static
397  SCIP* scip, /**< SCIP data structure */
398  TSEPAFULL** tsepafull /**< to initialize */
399  )
400 {
401  TSEPAFULL* tfull;
402  tfull = *tsepafull;
403 
404  for( int i = StpVecGetSize(tfull->subsols) - 1; i >= 0; i-- )
405  {
406  assert(tfull->subsols[i]);
407  SCIPfreeMemoryArray(scip, &(tfull->subsols[i]));
408  }
409  StpVecFree(scip, tfull->subsols);
410 
411  for( int i = StpVecGetSize(tfull->solcands_sepapart) - 1; i >= 0; i-- )
412  {
413  SCIPfreeMemoryArray(scip, &(tfull->solcands_sepapart[i]));
414  }
415  StpVecFree(scip, tfull->solcands_sepapart);
416 
417  for( int i = StpVecGetSize(tfull->solcands_sepaedges) - 1; i >= 0; i-- )
418  {
419  StpVecFree(scip, tfull->solcands_sepaedges[i]);
420  }
421  StpVecFree(scip, tfull->solcands_sepaedges);
422 
423  SCIPfreeMemoryArrayNull(scip, &(tfull->subgraph_bcosts));
424  SCIPfreeMemoryArrayNull(scip, &(tfull->subgraph_orgcosts));
425 
426  if( tfull->subdistdata )
427  {
428  extreduce_distDataFree(scip, tfull->subgraph, &(tfull->subdistdata));
429  }
430 
431  SCIPfreeMemory(scip, tsepafull);
432 }
433 
434 /** add solution candidate edges from given partition */
435 static
437  SCIP* scip, /**< SCIP data structure */
438  int partitionidx, /**< partition index for bpartitions */
439  const TERMCOMP* termcomp, /**< component */
440  BPARTITIONS* bpartitions, /**< partitions of separation terminals */
441  TSEPAFULL* tsepafull /**< full separator */
442  )
443 {
444  const GRAPH* subgraph = termcomp->subgraph;
445  const COMPBUILDER* const builder = termcomp->builder;
446  SCIP_Bool isRuledOut = FALSE;
447  const int nsepaterms = builder->nsepatterms;
448  const int nsolcands = tsepafull->nsolcands;
449  const int* const partition = bpartitions->partitions[partitionidx];
450 
451  SCIPdebugMessage("checking next solution candidate (number %d) \n", nsolcands);
452 
453  assert(partition);
454  assert(StpVecGetSize(tsepafull->solcands_sepaedges) == StpVecGetSize(tsepafull->solcands_sepapart));
455 
456  StpVecPushBack(scip, tsepafull->solcands_sepaedges, NULL);
457  assert(nsolcands == StpVecGetSize(tsepafull->solcands_sepaedges) - 1);
458 
459  for( int subsepaterm = 0; subsepaterm < nsepaterms && !isRuledOut; subsepaterm++ )
460  {
461  const int groupid = partition[subsepaterm];
462 
463  for( int e = subgraph->outbeg[subsepaterm]; e != EAT_LAST; e = subgraph->oeat[e] )
464  {
465  const int head = subgraph->head[e];
466 
467  if( head > subsepaterm )
468  continue;
469 
470  if( groupid == partition[head] )
471  {
472  const SCIP_Real bdist = tsepafull->subgraph_bcosts[e];
473  const SCIP_Real sd =
474  extreduce_distDataGetSdDouble(scip, subgraph, subsepaterm, head, tsepafull->subdistdata);
475 
476  StpVecPushBack(scip, tsepafull->solcands_sepaedges[nsolcands], e);
477 
478 #ifdef SCIP_DEBUG
479  SCIPdebugMessage("%d->%d bdist=%f, sd=%f \n",
480  termcomp->nodemap_subToOrg[subsepaterm],
481  termcomp->nodemap_subToOrg[head],
482  bdist, sd);
483 #endif
484 
485  if( SCIPisGE(scip, bdist, sd) )
486  {
487  isRuledOut = TRUE;
488  break;
489  }
490 
491  assert(LE(sd, BLOCKED));
492  }
493  }
494  }
495 
496  if( isRuledOut )
497  {
498  StpVecFree(scip, tsepafull->solcands_sepaedges[tsepafull->nsolcands]);
499  StpVecPopBack(tsepafull->solcands_sepaedges);
500 
501  SCIPdebugMessage("...ruled-out! \n");
502  }
503  else
504  {
505  tsepafull->nsolcands++;
506 
507  StpVecPushBack(scip, tsepafull->solcands_sepapart, bpartitions->partitions[partitionidx]);
508  bpartitions->partitions[partitionidx] = NULL;
509 
510  SCIPdebugMessage("...added! \n");
511  }
512 }
513 
514 /** computes artificial edges for each solution candidate (and tries to rule-out some candidates already) */
515 static
517  SCIP* scip, /**< SCIP data structure */
518  TERMCOMP* termcomp, /**< component */
519  TSEPAFULL* tsepafull /**< full separator */
520  )
521 {
522  BPARTITIONS* bpartitions;
523  const COMPBUILDER* const builder = termcomp->builder;
524  const int nsepaterms = builder->nsepatterms;
525 
526  assert(nsepaterms <= 4);
527  assert(tsepafull->nsolcands == 0);
528  assert(!tsepafull->solcands_sepaedges);
529 
530 #ifdef SCIP_DEBUG
531  for( int i = 0; i < nsepaterms; i++ )
532  SCIPdebugMessage("sepa sub to org: %d->%d \n", i, termcomp->nodemap_subToOrg[i]);
533 #endif
534 
535  SCIP_CALL( bpartitionsInit(scip, nsepaterms, &bpartitions) );
536  SCIP_CALL( bpartitionsCompute(scip, bpartitions) );
537 
538  for( int i = 0; i < bpartitions->npartitions; i++ )
539  {
540  sepafullAddSingleSolcandEdges(scip, i, termcomp, bpartitions, tsepafull);
541  }
542 
543  bpartitionsFree(scip, &bpartitions);
544 
545  return SCIP_OKAY;
546 }
547 
548 
549 /** builds solution candidates (and tries to rule-out some already) */
550 static
552  SCIP* scip, /**< SCIP data structure */
553  GRAPH* orggraph, /**< graph data structure */
554  TERMCOMP* termcomp, /**< component */
555  TSEPAFULL* tsepafull, /**< sepa */
556  SCIP_Bool* success /**< built? */
557  )
558 {
559  GRAPH* subgraph = termcomp->subgraph;
560  const int nsubedges = graph_get_nEdges(subgraph);
561 
562  assert(!tsepafull->solcands_sepaedges);
563  assert(tsepafull->nsolcands == 0);
564  assert(nsubedges >= 2);
565 
566  SCIP_CALL( reduce_termcompChangeSubgraphToBottleneck(scip, orggraph, termcomp, success) );
567 
568  if( !(*success) )
569  {
570  SCIPdebugMessage("problem while building bottleneck distances, aborting \n");
571  return SCIP_OKAY;
572  }
573 
574  SCIP_CALL( SCIPallocMemoryArray(scip, &(tsepafull->subgraph_bcosts), nsubedges) );
575  SCIP_CALL( SCIPallocMemoryArray(scip, &(tsepafull->subgraph_orgcosts), nsubedges) );
576 
577  BMScopyMemoryArray(tsepafull->subgraph_bcosts, subgraph->cost, nsubedges);
578 
579  /* NOTE: we need to reset the costs for SDs to be valid */
580  reduce_termcompChangeSubgraphToOrgCosts(orggraph, termcomp);
581  BMScopyMemoryArray(tsepafull->subgraph_orgcosts, subgraph->cost, nsubedges);
582 
583  SCIP_CALL( sepafullInitDistdata(scip, termcomp, tsepafull) );
584 
585  /* now do the actual work */
586  SCIP_CALL( sepafullBuildSolcandsEdges(scip, termcomp, tsepafull) );
587 
588  return SCIP_OKAY;
589 }
590 
591 
592 /** promising to do reductions? */
593 static
595  const TERMCOMP* termcomp, /**< component */
596  const TSEPAFULL* tsepafull /**< sepa */
597  )
598 {
599  const COMPBUILDER* const builder = termcomp->builder;
600  SCIP_Real maxratio;
601  const SCIP_Real noderatio = reduce_compbuilderGetSubNodesRatio(builder);
602  const int nsolcands = tsepafull->nsolcands;
603 
604  assert(nsolcands > 0);
605  assert(GT(noderatio, 0.0));
606 
607  if( nsolcands == 1 )
608  {
610  }
611  else if( nsolcands == 2 )
612  {
614  }
615  else if( nsolcands == 3 )
616  {
618  }
619  else if( nsolcands == 4 )
620  {
622  }
623  else
624  {
625  assert(builder->nsepatterms >= 3);
627  }
628 
629  SCIPdebugMessage("FINAL CHECK: noderatio=%f, maxratio=%f\n", noderatio, maxratio);
630 
631  if( noderatio > maxratio )
632  {
633  SCIPdebugMessage("...component is finally NOT promising! \n");
634  return FALSE;
635  }
636 
637  SCIPdebugMessage("...component is finally promising! \n");
638 
639  return TRUE;
640 }
641 
642 
643 /** solves subproblem */
644 static
646  SCIP* scip, /**< SCIP data structure */
647  const GRAPH* subgraph, /**< graph */
648  int* subedges_sol /**< to store solution */
649  )
650 {
651  GRAPH* subgraph_copy;
652  SUBSTP* substp;
653  SCIP_Bool success;
654 
655  assert(subgraph);
656 
657  SCIP_CALL( graph_copy(scip, subgraph, &subgraph_copy) );
658 
659  /* NOTE: subgraph will be moved into substp! */
660  SCIP_CALL( substpsolver_initBC(scip, subgraph_copy, &substp) );
662 
663  SCIP_CALL( substpsolver_setMute(substp) );
664  //SCIP_CALL( substpsolver_setProbIsIndependent(substp) );
666 
667 #ifdef SCIP_DEBUG
668  SCIPdebugMessage("starting to solve subgraph: ");
669  graph_printInfo(subgraph);
670 #endif
671 
672  SCIP_CALL( substpsolver_solve(scip, substp, &success) );
673  assert(success);
674 
675  /* fix solution in original graph */
676  SCIP_CALL( substpsolver_getSolution(substp, subedges_sol) );
677 
678  substpsolver_free(scip, &substp);
679 
680  return SCIP_OKAY;
681 }
682 
683 
684 /** returns TRUE if sub-solution can be ruled out */
685 static
687  SCIP* scip, /**< SCIP data structure */
688  const TERMCOMP* termcomp, /**< component */
689  const int* subsol, /**< solution */
690  const int* sepapartition, /**< partition */
691  STP_Vectype(int) solcand_sepaedges /**< bottleneck edges */
692  )
693 {
694  const GRAPH* subgraph = termcomp->subgraph;
695  int* groups_size;
696  int* groups_nsolbedges;
697  const int nsepaterms = termcomp->builder->nsepatterms;
698  const int ngroups = getPartitionNgroups(nsepaterms, sepapartition);
699  SCIP_Bool isRedundant = FALSE;
700 
701  assert(nsepaterms >= 2);
702  assert(subgraph);
703 
704  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &groups_size, ngroups) );
705  SCIP_CALL_ABORT( SCIPallocClearBufferArray(scip, &groups_nsolbedges, ngroups) );
706 
707  getPartitionGroupsSizes(nsepaterms, ngroups, sepapartition, groups_size);
708 
709  for( int i = 0; i < StpVecGetSize(solcand_sepaedges); i++ )
710  {
711  const int subedge = solcand_sepaedges[i];
712  const int tail = subgraph->tail[subedge];
713  const int group = sepapartition[tail];
714 
715  assert(graph_edge_isInRange(termcomp->subgraph, subedge));
716  assert(tail < nsepaterms);
717  assert(subgraph->head[subedge] < nsepaterms);
718  assert(sepapartition[tail] == sepapartition[subgraph->head[subedge]]);
719  assert(group < ngroups);
720  assert(groups_size[group] >= 2);
721 
722  if( subsol[subedge] == CONNECT || subsol[flipedge(subedge)] == CONNECT )
723  {
724  groups_nsolbedges[group]++;
725  }
726  }
727 
728  for( int i = 0; i < ngroups; i++ )
729  {
730  const int ngroupnodes = groups_size[i];
731  const int ngroupsoledges = groups_nsolbedges[i];
732 
733  assert(ngroupsoledges < ngroupnodes && ngroupnodes <= nsepaterms);
734  assert(0 <= ngroupsoledges);
735 
736  /* is there at least one unconnected group node? */
737  if( ngroupsoledges < ngroupnodes - 1 )
738  {
739  SCIPdebugMessage("ruled out: ngroupsoledges=%d ngroupnodes=%d \n", ngroupsoledges, ngroupnodes);
740  isRedundant = TRUE;
741  break;
742  }
743  }
744 
745  SCIPfreeBufferArray(scip, &groups_nsolbedges);
746  SCIPfreeBufferArray(scip, &groups_size);
747 
748  return isRedundant;
749 }
750 
751 
752 
753 /** sets weight for artificial bottleneck edges between separator terminals */
754 static
756  int cand, /**< candidate number */
757  TERMCOMP* termcomp, /**< component */
758  TSEPAFULL* tsepafull /**< full separation data */
759  )
760 {
761  GRAPH* subgraph = termcomp->subgraph;
762  const SCIP_Real* const subgraph_bcosts = tsepafull->subgraph_bcosts;
763  STP_Vectype(int) solcand_sepaedges = tsepafull->solcands_sepaedges[cand];
764 
765  assert(subgraph_bcosts);
766 
767  for( int i = 0; i < StpVecGetSize(solcand_sepaedges); i++ )
768  {
769  const int subedge = solcand_sepaedges[i];
770  assert(graph_edge_isInRange(subgraph, subedge));
771 
772  subgraph->cost[subedge] = subgraph_bcosts[subedge];
773  subgraph->cost[flipedge(subedge)] = subgraph_bcosts[flipedge(subedge)];
774 
775 #ifdef SCIP_DEBUG
776  SCIPdebugMessage("adding artifical subedge (for solcand %d): ", cand);
777  graph_edge_printInfo(subgraph, subedge);
778 #endif
779  }
780 }
781 
782 
783 /** adds solution for candidate, or rules the solution out */
784 static
786  SCIP* scip, /**< SCIP data structure */
787  int cand, /**< candidate number */
788  TERMCOMP* termcomp, /**< component */
789  TSEPAFULL* tsepafull /**< full separation data */
790  )
791 {
792  int* subsol;
793  GRAPH* subgraph = termcomp->subgraph;
794  STP_Vectype(int) solcand_sepaedges = tsepafull->solcands_sepaedges[cand];
795  const int* const solcand_sepapart = tsepafull->solcands_sepapart[cand];
796  const SCIP_Real* const subgraph_orgcosts = tsepafull->subgraph_orgcosts;
797 
798  assert(0 <= cand && cand < tsepafull->nsolcands);
799  assert(StpVecGetSize(tsepafull->solcands_sepaedges) == StpVecGetSize(tsepafull->solcands_sepapart));
800  assert(subgraph_orgcosts && solcand_sepapart);
801 
802  BMScopyMemoryArray(subgraph->cost, subgraph_orgcosts, subgraph->edges);
803  setSubBottleneckEdges(cand, termcomp, tsepafull);
804 
805  SCIP_CALL( SCIPallocMemoryArray(scip, &subsol, subgraph->edges) );
806  SCIP_CALL( solveSub(scip, subgraph, subsol) );
807  assert(solstp_isValid(scip, subgraph, subsol));
808 
809  if( subSolIsRedundant(scip, termcomp, subsol, solcand_sepapart, solcand_sepaedges) )
810  {
811  SCIPdebugMessage("DISCARDING sub-solution \n");
812  SCIPfreeMemoryArray(scip, &subsol);
813  }
814  else
815  {
816  SCIPdebugMessage("ADDING sub-solution \n");
817  StpVecPushBack(scip, tsepafull->subsols, subsol);
818  }
819 
820  return SCIP_OKAY;
821 }
822 
823 
824 /** performs reductions based on solutions to feasible subproblem */
825 static
827  SCIP* scip, /**< SCIP data structure */
828  GRAPH* orggraph, /**< graph data structure */
829  REDBASE* redbase, /**< reduction base */
830  TSEPAFULL* tsepafull, /**< full separation data */
831  TERMCOMP* termcomp, /**< component */
832  int* nelims /**< number of eliminations */
833  )
834 {
835  const GRAPH* const subgraph = termcomp->subgraph;
836  STP_Vectype(int*) subsols = tsepafull->subsols;
837  const int* const edgemap_subToOrg = termcomp->edgemap_subToOrg;
838  int8_t* edgesolcount;
839  const SCIP_Real* const subgraph_bcosts = tsepafull->subgraph_bcosts;
840  const SCIP_Real* const subgraph_orgcosts = tsepafull->subgraph_orgcosts;
841  SCIP_Real* offset = reduce_solGetOffsetPointer(redbase->redsol);
842  const int nsubedges = graph_get_nEdges(subgraph);
843  const int nvalidsols = StpVecGetSize(subsols);
844 
845  SCIP_CALL( SCIPallocClearMemoryArray(scip, &edgesolcount, nsubedges / 2) );
846 
847  assert(nvalidsols > 0);
848  assert(edgemap_subToOrg && subsols);
849 
850  SCIPdebugMessage("number of valid solution: %d \n", nvalidsols);
851 
852  for( int i = 0; i < StpVecGetSize(subsols); i++ )
853  {
854  const int* const subsol = subsols[i];
855  assert(solstp_isValid(scip, subgraph, subsol));
856 
857  for( int e = 0; e < nsubedges; e += 2 )
858  {
859  if( subsol[e] == CONNECT || subsol[e + 1] == CONNECT )
860  {
861 #ifdef SCIP_DEBUG
862  const int* const subToOrg = termcomp->nodemap_subToOrg;
863  SCIPdebugMessage("solution %d (original) edge: ", i);
864 
865  if( edgemap_subToOrg[e] != -1 )
866  graph_edge_printInfo(orggraph, edgemap_subToOrg[e]);
867  else
868  printf("artificial %d->%d \n", subToOrg[subgraph->tail[e]], subToOrg[subgraph->head[e]]);
869 #endif
870  edgesolcount[e / 2]++;
871  }
872  else
873  {
874  assert(subsol[e] == UNKNOWN && subsol[e + 1] == UNKNOWN);
875  edgesolcount[e / 2]--;
876  }
877  }
878  }
879 
880  for( int e = 0; e < nsubedges / 2; e++ )
881  {
882  const int subedge = e * 2;
883  const int orgedge = edgemap_subToOrg[subedge];
884 
885  if( orgedge == -1 )
886  continue;
887 
888  assert(graph_edge_isInRange(orggraph, orgedge));
889 
890  /* we want to make sure that we don't modify sepa->sepa edges that got a smaller
891  * bottleneck distance */
892  if( !EQ(subgraph_bcosts[subedge], subgraph_orgcosts[subedge]) )
893  {
894  assert(LT(subgraph_bcosts[subedge], subgraph_orgcosts[subedge]));
895  assert(subgraph->tail[subedge] < termcomp->builder->nsepatterms);
896  assert(subgraph->head[subedge] < termcomp->builder->nsepatterms);
897 
898  continue;
899  }
900 
901  if( edgesolcount[e] == nvalidsols )
902  {
903 #ifdef SCIP_DEBUG
904  SCIPdebugMessage("fix edge ");
905  graph_edge_printInfo(orggraph, orgedge);
906 #endif
907  /* NOTE: edge will be automatically contracted later; we avoid trouble other terminal separators */
908  *offset += orggraph->cost[orgedge];
909  orggraph->cost[orgedge] = 0.0;
910  orggraph->cost[flipedge(orgedge)] = 0.0;
911  graph_knot_chg(orggraph, orggraph->tail[orgedge], STP_TERM);
912  graph_knot_chg(orggraph, orggraph->head[orgedge], STP_TERM);
913  (*nelims)++;
914  }
915  else if( edgesolcount[e] == -nvalidsols )
916  {
917 #ifdef SCIP_DEBUG
918  SCIPdebugMessage("delete edge ");
919  graph_edge_printInfo(orggraph, orgedge);
920 #endif
921  graph_edge_del(scip, orggraph, orgedge, TRUE);
922  (*nelims)++;
923  }
924  }
925 
926  SCIPfreeMemoryArray(scip, &edgesolcount);
927 
928  return SCIP_OKAY;
929 }
930 
931 /** performs reductions */
932 static
934  SCIP* scip, /**< SCIP data structure */
935  GRAPH* orggraph, /**< graph data structure */
936  REDBASE* redbase, /**< reduction base */
937  TSEPAFULL* tsepafull, /**< full separation data */
938  TERMCOMP* termcomp, /**< component */
939  int* nelims /**< number of eliminations*/
940  )
941 {
942  const int nsolcands = tsepafull->nsolcands;
943 
944  assert(nsolcands > 0);
945 
946  for( int i = 0; i < nsolcands; i++ )
947  {
948  SCIPdebugMessage("---Checking solution candidate %d: \n", i);
949 
950  SCIP_CALL( sepafullAddSolForCand(scip, i, termcomp, tsepafull) );
951  }
952 
953  SCIP_CALL( sepafullReduceFromSols(scip, orggraph, redbase, tsepafull, termcomp, nelims) );
954 
955  return SCIP_OKAY;
956 }
957 
958 
959 /** promising to perform reductions on given component? */
960 static
962  const GRAPH* g, /**< graph data structure */
963  const COMPBUILDER* builder /**< terminal separator component initializer */
964  )
965 {
966  SCIP_Real maxratio;
967  const SCIP_Real noderatio = reduce_compbuilderGetSubNodesRatio(builder);
968 
969  assert(GT(noderatio, 0.0));
970  assert(builder->nsepatterms <= SEPARATOR_MAXSIZE);
971 
972  if( builder->nsepatterms == 2 )
973  {
975  }
976  else if( builder->nsepatterms == 3 )
977  {
979  }
980  else
981  {
982  assert(builder->nsepatterms == 4);
984  }
985 
986  SCIPdebugMessage("noderatio=%f, maxratio=%f\n", noderatio, maxratio);
987 
988  if( noderatio > maxratio )
989  {
990  SCIPdebugMessage("...component is NOT promising! \n");
991  return FALSE;
992  }
993 
994  SCIPdebugMessage("...component is promising! \n");
995 
996  return TRUE;
997 }
998 
999 
1000 /** processes subgraph associated with builder */
1001 static
1003  SCIP* scip, /**< SCIP data structure */
1004  COMPBUILDER* builder, /**< terminal separator component initializer */
1005  GRAPH* g, /**< graph data structure */
1006  REDBASE* redbase, /**< reduction base */
1007  int* nelims /**< number of eliminations*/
1008  )
1009 {
1010  TSEPAFULL* tsepafull;
1011  TERMCOMP* termcomp;
1012  SCIP_Bool success;
1013 
1014 #ifdef SCIP_DEBUG
1016  SCIPdebugMessage("number of component nodes: %d \n", builder->ncomponentnodes);
1017 #endif
1018 
1019  SCIP_CALL( reduce_termcompInit(scip, g, builder, &termcomp) );
1020  SCIP_CALL( reduce_termcompBuildSubgraph(scip, g, termcomp) );
1021 
1022  /* NOTE: the subgraph does not yet have the bottleneck short-cuts */
1023  SCIP_CALL( sepafullInit(scip, termcomp->subgraph, &tsepafull) );
1024  SCIP_CALL( sepafullBuildSolcands(scip, g, termcomp, tsepafull, &success) );
1025 
1026  /* NOTE: we might fail because the separator is not connected anymore on one side */
1027 
1028  if( success && sepafullSolcandsArePromising(termcomp, tsepafull) )
1029  {
1030  SCIP_CALL( sepafullReduce(scip, g, redbase, tsepafull, termcomp, nelims) );
1031  }
1032 
1033  sepafullFree(scip, &tsepafull);
1034  reduce_termcompFree(scip, &termcomp);
1035 
1036  return SCIP_OKAY;
1037 }
1038 
1039 
1040 /** initializes helpers */
1041 static
1043  SCIP* scip, /**< SCIP data structure */
1044  const GRAPH* g, /**< graph data structure */
1045  COMPBUILDER** builder, /**< to initialize */
1046  TERMSEPAS** termsepas /**< to initialize */
1047  )
1048 {
1049  const int mincheckbound = (int) (SEPARATOR_MINTERMRATIO * g->terms);
1050  const int maxsepasize = SEPARATOR_MAXSIZE;
1051  int maxncompchecks = SEPARATOR_MAXNCHECKS;
1052  int nnodes_real;
1053  SCIP_Real termratio;
1054 
1055  graph_get_nVET(g, &nnodes_real, NULL, NULL);
1056  termratio = (SCIP_Real) g->terms / (SCIP_Real) nnodes_real;
1057 
1058 
1059 
1060  if( maxncompchecks < mincheckbound )
1061  {
1062  SCIPdebugMessage("update nChecks %d->%d \n", maxncompchecks, mincheckbound);
1063  maxncompchecks = mincheckbound;
1064  }
1065 
1066  if( termratio >= SEPARATOR_MINEFFTERMRATIO )
1067  {
1068  maxncompchecks *= 1.5;
1069  }
1070 
1071 #ifdef SCIP_DEBUG
1073  printf("max. number of components to be checked: %d \n", maxncompchecks);
1074 #endif
1075 
1076  /* NOTE: we want to allow a few more terminal separators to be able to choose small ones */
1077  SCIP_CALL( mincut_termsepasInit(scip, g, (int) (2.0 * maxncompchecks), maxsepasize, termsepas) );
1078  SCIP_CALL( reduce_compbuilderInit(scip, g, builder) );
1079 
1080  (*builder)->maxncompchecks = maxncompchecks;
1081  (*builder)->maxsepasize = maxsepasize;
1082 
1083  return SCIP_OKAY;
1084 }
1085 
1086 
1087 /** frees helper */
1088 static
1090  SCIP* scip, /**< SCIP data structure */
1091  COMPBUILDER** builder, /**< to initialize */
1092  TERMSEPAS** termsepas /**< to initialize */
1093  )
1094 {
1095  reduce_compbuilderFree(scip, builder);
1096  mincut_termsepasFree(scip, termsepas);
1097 }
1098 
1099 
1100 
1101 /*
1102  * Interface methods
1103  */
1104 
1105 
1106 /** terminal-separator reduction method using optimal (full) solution of sub-problems */
1108  SCIP* scip, /**< SCIP data structure */
1109  GRAPH* g, /**< graph data structure */
1110  int* solnode, /**< solution nodes mark or NULL */
1111  REDBASE* redbase, /**< reduction base */
1112  int* nelims /**< number of eliminations*/
1113  )
1114 {
1115  SCIP_RANDNUMGEN* randnumgen;
1116  COMPBUILDER* builder;
1117  TERMSEPAS* termsepas;
1118 
1119  assert(scip && g && nelims && redbase);
1120  *nelims = 0;
1121 
1122  if( g->terms == 1 )
1123  {
1124  return SCIP_OKAY;
1125  }
1126 
1127  // int todo;
1128  /* first, we want to get rid of medium sized connected components */
1129  SCIP_CALL( reduce_bidecompositionExact(scip, g, redbase, solnode, nelims) );
1130 
1131  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, (unsigned) g->terms, TRUE) );
1132  SCIP_CALL( initHelpers(scip, g, &builder, &termsepas) );
1133  SCIP_CALL( mincut_findTerminalSeparators(scip, randnumgen, g, termsepas) );
1134 
1135  SCIPdebugMessage("starting termsepFull, with %d separators \n", mincut_termsepasGetNall(termsepas));
1136 
1137  for( ;; )
1138  {
1139  SCIP_Bool compWasFound;
1140 
1141  reduce_termsepaGetNextComp(scip, g, termsepas, builder, &compWasFound);
1142 
1143  if( !compWasFound )
1144  break;
1145 
1146  if( !termcompIsPromising(g, builder) )
1147  continue;
1148 
1149  SCIP_CALL( processComponent(scip, builder, g, redbase, nelims) );
1150 
1151  builder->componentnumber++;
1152  }
1153 
1154  /* NOTE: solution edges have been fixed to 0 before */
1155  if( *nelims > 0 )
1156  SCIP_CALL( reduce_contract0Edges(scip, g, solnode, TRUE) );
1157 
1158  SCIPfreeRandom(scip, &randnumgen);
1159  freeHelpers(scip, &builder, &termsepas);
1160 
1161  return SCIP_OKAY;
1162 }
#define STP_Vectype(type)
Definition: stpvector.h:44
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
#define StpVecGetSize(vec)
Definition: stpvector.h:139
static SCIP_RETCODE sepafullInit(SCIP *scip, GRAPH *subgraph, TSEPAFULL **tsepafull)
static SCIP_Bool subSolIsRedundant(SCIP *scip, const TERMCOMP *termcomp, const int *subsol, const int *sepapartition, STP_Vectype(int) solcand_sepaedges)
#define SEPARATOR_MINTERMRATIO
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
SCIP_RETCODE reduce_termcompChangeSubgraphToBottleneck(SCIP *, GRAPH *, TERMCOMP *, SCIP_Bool *)
void reduce_compbuilderPrintSeparators(const GRAPH *, const COMPBUILDER *)
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
SCIP_Real extreduce_distDataGetSdDouble(SCIP *, const GRAPH *, int, int, DISTDATA *)
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
static SCIP_RETCODE sepafullReduce(SCIP *scip, GRAPH *orggraph, REDBASE *redbase, TSEPAFULL *tsepafull, TERMCOMP *termcomp, int *nelims)
int terms
Definition: graphdefs.h:192
SCIP_RETCODE substpsolver_setMute(SUBSTP *substp)
Definition: substpsolver.c:525
static SCIP_Bool termcompIsPromising(const GRAPH *g, const COMPBUILDER *builder)
void extreduce_distDataFree(SCIP *, const GRAPH *, DISTDATA **)
void reduce_termcompChangeSubgraphToOrgCosts(const GRAPH *, TERMCOMP *)
SCIP_RETCODE reduce_termsepaFull(SCIP *scip, GRAPH *g, int *solnode, REDBASE *redbase, int *nelims)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_free_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1807
includes methods for Steiner tree problem solutions
void reduce_termsepaGetNextComp(SCIP *, const GRAPH *, TERMSEPAS *, COMPBUILDER *, SCIP_Bool *)
SCIP_RETCODE substpsolver_setProbFullPresolve(SUBSTP *substp)
Definition: substpsolver.c:568
static SCIP_RETCODE bpartitionsCompute(SCIP *scip, BPARTITIONS *bparts)
SCIP_RETCODE reduce_compbuilderInit(SCIP *, const GRAPH *, COMPBUILDER **)
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
static SCIP_RETCODE bsubpartAdd(SCIP *scip, int subsize, int maxgroupid, BPARTITIONS *bparts)
#define COMPONENT_MAXNODESRATIO_3SEPA
SCIP_Real reduce_compbuilderGetSubNodesRatio(const COMPBUILDER *)
#define StpVecPopBack(vec)
Definition: stpvector.h:178
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void graph_printInfo(const GRAPH *)
Definition: graph_stats.c:299
#define COMPONENT_MAXNODESRATIO_4SEPA
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:57
int mincut_termsepasGetNall(const TERMSEPAS *termsepas)
Definition: mincut.c:2135
#define SEPARATOR_MINEFFTERMRATIO
#define SEPARATOR_MAXSIZE
header only, simple implementation of an STL like vector
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1721
SCIP_RETCODE substpsolver_initBC(SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
Definition: substpsolver.c:359
static SCIP_RETCODE sepafullBuildSolcandsEdges(SCIP *scip, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
#define COMPONENT_MAXNODESRATIO_2CANDS
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
#define LE(a, b)
Definition: portab.h:83
static void sepafullAddSingleSolcandEdges(SCIP *scip, int partitionidx, const TERMCOMP *termcomp, BPARTITIONS *bpartitions, TSEPAFULL *tsepafull)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
static SCIP_RETCODE sepafullAddSolForCand(SCIP *scip, int cand, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
SCIP_RETCODE mincut_findTerminalSeparators(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, TERMSEPAS *termsepas)
Definition: mincut.c:2274
#define COMPONENT_MAXNODESRATIO_2SEPA
#define SEPARATOR_MAXNCHECKS
static SCIP_RETCODE bpartitionsInit(SCIP *scip, int nelems, BPARTITIONS **bparitions)
#define COMPONENT_MAXNODESRATIO_1CANDS
static void freeHelpers(SCIP *scip, COMPBUILDER **builder, TERMSEPAS **termsepas)
SCIP_RETCODE substpsolver_initHistory(SUBSTP *substp)
Definition: substpsolver.c:430
static SCIP_RETCODE solveSub(SCIP *scip, const GRAPH *subgraph, int *subedges_sol)
#define NULL
Definition: lpi_spx1.cpp:155
Solver for Steiner tree (sub-) problems.
static SCIP_RETCODE sepafullBuildSolcands(SCIP *scip, GRAPH *orggraph, TERMCOMP *termcomp, TSEPAFULL *tsepafull, SCIP_Bool *success)
#define EQ(a, b)
Definition: portab.h:79
#define SCIP_CALL(x)
Definition: def.h:384
static void sepafullFree(SCIP *scip, TSEPAFULL **tsepafull)
static void setSubBottleneckEdges(int cand, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
#define LT(a, b)
Definition: portab.h:81
static int getPartitionNgroups(int nelems, const int *partition)
SCIP_RETCODE reduce_termcompBuildSubgraph(SCIP *, GRAPH *, TERMCOMP *)
static SCIP_RETCODE processComponent(SCIP *scip, COMPBUILDER *builder, GRAPH *g, REDBASE *redbase, int *nelims)
void reduce_termcompFree(SCIP *, TERMCOMP **)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE substpsolver_getSolution(SUBSTP *substp, int *edgesol)
Definition: substpsolver.c:500
int *RESTRICT tail
Definition: graphdefs.h:223
REDSOL * redsol
Definition: reducedefs.h:105
void mincut_termsepasFree(SCIP *scip, TERMSEPAS **termsepas)
Definition: mincut.c:2113
#define COMPONENT_MAXNODESRATIO_5PLUSCANDS
#define flipedge(edge)
Definition: graphdefs.h:84
#define STP_TERM
Definition: graphdefs.h:61
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
static void bpartitionsDebugPrintTop(const BPARTITIONS *bparitions)
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
SCIP_RETCODE mincut_termsepasInit(SCIP *scip, const GRAPH *g, int maxnsepas, int maxsepasize, TERMSEPAS **termsepas)
Definition: mincut.c:2074
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
static void bpartitionsFree(SCIP *scip, BPARTITIONS **bparitions)
SCIP_RETCODE reduce_termcompInit(SCIP *, const GRAPH *, COMPBUILDER *, TERMCOMP **)
SCIP_RETCODE extreduce_distDataInit(SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
void reduce_compbuilderFree(SCIP *, COMPBUILDER **)
static SCIP_RETCODE sepafullReduceFromSols(SCIP *scip, GRAPH *orggraph, REDBASE *redbase, TSEPAFULL *tsepafull, TERMCOMP *termcomp, int *nelims)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
#define COMPONENT_MAXNODESRATIO_3CANDS
SCIP_Real * reduce_solGetOffsetPointer(REDSOL *)
Definition: reduce_sol.c:1285
#define SCIP_Real
Definition: def.h:177
struct bell_parititioner BPARTITIONS
#define BLOCKED
Definition: graphdefs.h:90
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_RETCODE graph_copy(SCIP *, const GRAPH *, GRAPH **)
Definition: graph_base.c:939
static SCIP_Bool sepafullSolcandsArePromising(const TERMCOMP *termcomp, const TSEPAFULL *tsepafull)
int edges
Definition: graphdefs.h:219
void substpsolver_free(SCIP *scip, SUBSTP **substp)
Definition: substpsolver.c:380
static DPSUBSOL ** subsol
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
static SCIP_RETCODE initHelpers(SCIP *scip, const GRAPH *g, COMPBUILDER **builder, TERMSEPAS **termsepas)
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
SCIP_RETCODE reduce_contract0Edges(SCIP *, GRAPH *, int *, SCIP_Bool)
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
Minimum cut routines for Steiner problems.
SCIP_RETCODE substpsolver_solve(SCIP *scip, SUBSTP *substp, SCIP_Bool *success)
Definition: substpsolver.c:452
includes various reduction methods for Steiner tree problems
void graph_printInfoReduced(const GRAPH *)
Definition: graph_stats.c:375
SCIP_RETCODE reduce_bidecompositionExact(SCIP *, GRAPH *, REDBASE *, int *, int *)
Definition: reduce_sepa.c:1085
static SCIP_RETCODE sepafullInitDistdata(SCIP *scip, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
static void getPartitionGroupsSizes(int nelems, int ngroups, const int *partition, int *groups_sizes)
SCIP callable library.
struct terminal_separator_full TSEPAFULL