Scippy

SCIP

Solving Constraint Integer Programs

reduce_sepa.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_sepa.c
17  * @brief several node-separator based reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements node-separator based reduction techniques for several Steiner problems.
21  * It contains rather simple test with articulation points, and more involved ones with terminal-separators.
22  *
23  * A list of all interface methods can be found in reduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 //#define SCIP_DEBUG
29 //#define BENCH_SEPA_PARTIAL
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include <assert.h>
34 #include "graph.h"
35 #include "reduce.h"
36 #include "substpsolver.h"
37 #include "bidecomposition.h"
38 #include "portab.h"
39 #include "stpvector.h"
40 #include "scip/scip.h"
41 
42 #ifdef BENCH_SEPA_PARTIAL
43 #include "time.h"
44 #endif
45 
46 #define BIDECOMP_MINRED_MULTIPLIER 2
47 #define BIDECOMP_MINMAXCOMPRATIO_FIRST 0.95
48 #define BIDECOMP_MINMAXCOMPRATIO 0.80
49 #define BIDECOMP_MINMAXCOMPRATIO_PARTIAL 0.99
50 #define BIDECOMP_MAXCOMPRATIO_PARTIAL 0.05
51 #define BIDECOMP_MAXCOMPRATIO_AGGRESSIVE 0.5
52 #define BIDECOMP_MINNODES 10
53 #define BIDECOMP_MINNODES_PARTIAL 10
54 
55 
56 //#define CUTTREE_PRINT_STATISTICS
57 
58 
59 /** Steiner tree based bi-connected component reduction */
60 typedef struct cut_tree_data
61 {
62  int* nodes_prednode; /**< predecessor per node */
63  SCIP_Bool* comps_isHit; /**< of size ncomps */
64  SCIP_Bool* nodes_isTree; /**< of size |V| */
65  SCIP_Bool cutnode0isNeeded; /**< special treatment */
66 } CUTTREE;
67 
68 
69 /*
70  * Local methods
71  */
72 
73 /** helper */
74 static inline
76  const CUTNODES* cutnodes /**< cut nodes */
77  )
78 {
79  const int lastcutnode = cutnodes->artpoints[StpVecGetSize(cutnodes->artpoints) - 1];
80  assert(StpVecGetSize(cutnodes->artpoints) >= 1);
81 
82  assert(lastcutnode >= 0);
83  assert(cutnodes->biconn_nodesmark[lastcutnode] == 0);
84 
85  return lastcutnode;
86 }
87 
88 
89 #ifdef CUTTREE_PRINT_STATISTICS
90 /** helper */
91 static inline
92 void cutNodesTraverseSub(
93  SCIP* scip, /**< SCIP data structure */
94  const GRAPH* g, /**< graph data structure */
95  int node,
96  SCIP_Bool* isVisited, /**< */
97  int* nterms,
98  int* ncompnodes
99  )
100 {
101  STP_Vectype(int) stack = NULL;
102  const int nnodes = graph_get_nNodes(g);
103 
104  *nterms = 0;
105  *ncompnodes = 0;
106  assert(!isVisited[node]);
107 
108  StpVecReserve(scip, stack, nnodes);
109  StpVecPushBack(scip, stack, node);
110  isVisited[node] = TRUE;
111 
112  while( StpVecGetSize(stack) )
113  {
114  const int k = stack[StpVecGetSize(stack) - 1];
115  StpVecPopBack(stack);
116 
117  if( Is_term(g->term[k]) )
118  {
119  (*nterms)++;
120  }
121  (*ncompnodes)++;
122 
123  assert(isVisited[k]);
124 
125  for( int e = g->outbeg[k]; e != EAT_LAST; e = g->oeat[e] )
126  {
127  const int head = g->head[e];
128  if( !isVisited[head] )
129  {
130  isVisited[head] = TRUE;
131  StpVecPushBack(scip, stack, head);
132  }
133  }
134  }
135 
136  StpVecFree(scip, stack);
137 }
138 
139 
140 /** traverses tree from cut-node */
141 static inline
142 SCIP_RETCODE cutNodesTraverseFromCutNode(
143  SCIP* scip, /**< SCIP data structure */
144  const GRAPH* g, /**< graph data structure */
145  int node,
146  const CUTNODES* cutnodes /**< cut nodes */
147  )
148 {
149  SCIP_Bool* isVisited;
150  const int nnodes = graph_get_nNodes(g);
151  STP_Vectype(int) comps_id = NULL;
152  STP_Vectype(int) comps_nterms = NULL;
153 
154  assert(StpVecGetSize(cutnodes->artpoints) >= 1);
155 
156  SCIP_CALL( SCIPallocBufferArray(scip, &isVisited, nnodes) );
157 
158  printf("check cut-node ");
159  graph_knot_printInfo(g, node);
160 
161  for( int i = 0; i < nnodes; ++i )
162  isVisited[i] = FALSE;
163 
164  isVisited[node] = TRUE;
165 
166  printf(" belowterms=%d, belownodes=%d ... \n", cutnodes->childcount_terms[node], cutnodes->childcount_nodes[node]);
167 
168  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
169  {
170  int nterms;
171  int ncompnodes;
172  const int base = g->head[e];
173 
174  if( isVisited[base] )
175  continue;
176 
177  cutNodesTraverseSub(scip, g, base, isVisited, &nterms, &ncompnodes);
178  StpVecPushBack(scip, comps_id, cutnodes->biconn_nodesmark[base]);
179  StpVecPushBack(scip, comps_nterms, nterms);
180 
181  printf("component=%d: ", cutnodes->biconn_nodesmark[base]);
182  printf("nterms=%d, ", nterms);
183  printf("ncompnodes=%d \n", ncompnodes);
184  }
185 
186 
187 
188  StpVecFree(scip, comps_nterms);
189  StpVecFree(scip, comps_id);
190  SCIPfreeBufferArray(scip, &isVisited);
191 
192  return SCIP_OKAY;
193 }
194 #endif
195 
196 #ifdef XXXXX
197 /** checks bi-connected leaf components */
198 static
199 SCIP_RETCODE cutNodesTreeCheckLeaveComponents(
200  SCIP* scip, /**< SCIP data structure */
201  const GRAPH* g, /**< graph data structure */
202  const CUTNODES* cutnodes, /**< cut nodes */
203  CUTTREE* cuttree /**< cut tree data */
204  )
205 {
206  STP_Vectype(int) stack = NULL;
207  int* RESTRICT nodes_pred = cuttree->nodes_prednode;
208  SCIP_Bool* RESTRICT nodes_isVisited = cutnodes->nodes_isVisited;
209  SCIP_Bool* RESTRICT nodes_isTree = cuttree->nodes_isTree;
210  const int* const biconn_nodesmark = biconn_nodesmark;
211  const int nnodes = graph_get_nNodes(g);
212  const int root = cutnodes->dfsroot;
213  const int lastcutnode = cutNodesGetLastCutnode(cutnodes);
214  int termscount = g->terms;
215 
216  /* save terminals per component, set to -1 if cut node is encountered */
217 
218  return SCIP_OKAY;
219 }
220 #endif
221 
222 
223 /** helper */
224 static inline
226  int node, /**< node to add */
227  const CUTNODES* cutnodes, /**< cut nodes */
228  int lastcutnode, /**< last cut node */
229  CUTTREE* cuttree /**< cut tree data */
230  )
231 {
232  const int nodecomp = cutnodes->biconn_nodesmark[node];
233  assert(0 <= nodecomp && nodecomp < cutnodes->biconn_ncomps);
234 
235  cuttree->nodes_isTree[node] = TRUE;
236 
237  if( node != lastcutnode )
238  cuttree->comps_isHit[nodecomp] = TRUE;
239 
240  /* NOTE: lastcutnode needs special treatment, because it is considered as part of the
241  * bi-connected component that it induces */
242  if( nodecomp != 0 && cutnodes->biconn_comproots[nodecomp] == lastcutnode )
243  {
244  cuttree->cutnode0isNeeded = TRUE;
245  assert(node != lastcutnode);
246  }
247 }
248 
249 
250 /** builds Steiner tree */
251 static
253  SCIP* scip, /**< SCIP data structure */
254  const GRAPH* g, /**< graph data structure */
255  const CUTNODES* cutnodes, /**< cut nodes */
256  CUTTREE* cuttree /**< cut tree data */
257  )
258 {
259  STP_Vectype(int) stack = NULL;
260  int* RESTRICT nodes_pred = cuttree->nodes_prednode;
261  SCIP_Bool* RESTRICT nodes_isTree = cuttree->nodes_isTree;
262  const int nnodes = graph_get_nNodes(g);
263  const int root = cutnodes->dfsroot;
264  const int lastcutnode = cutNodesGetLastCutnode(cutnodes);
265  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
266  int termscount = isPcMw ? graph_pc_nNonLeafTerms(g) : g->terms;
267 
268  assert(nodes_pred && nodes_isTree && cuttree->comps_isHit);
269  assert(!nodes_isTree[root] && !cuttree->comps_isHit[cutnodes->biconn_nodesmark[root]]);
270  assert(!cuttree->cutnode0isNeeded);
271 
272  StpVecReserve(scip, stack, nnodes);
273 
274  nodes_pred[root] = root;
275  cutNodesTreeAddNode(root, cutnodes, lastcutnode, cuttree);
276  StpVecPushBack(scip, stack, root);
277  termscount--;
278 
279  /* do a DFS until all terminals have been hit */
280  while( StpVecGetSize(stack) > 0 && termscount > 0 )
281  {
282  const int node = stack[StpVecGetSize(stack) - 1];
283  StpVecPopBack(stack);
284 
285  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
286  {
287  const int head = g->head[e];
288 
289  if( nodes_pred[head] < 0 && g->mark[head] )
290  {
291  nodes_pred[head] = node;
292 
293  StpVecPushBack(scip, stack, head);
294 
295  if( Is_term(g->term[head]) )
296  {
297  assert(!nodes_isTree[head]);
298 
299  if( isPcMw && graph_pc_termIsNonLeafTerm(g, head) )
300  continue;
301 
302  termscount--;
303 
304  for( int pred = head; !nodes_isTree[pred]; pred = nodes_pred[pred] )
305  {
306  assert(graph_knot_isInRange(g, pred));
307  cutNodesTreeAddNode(pred, cutnodes, lastcutnode, cuttree);
308  }
309  }
310  }
311  }
312  }
313 
314  cuttree->cutnode0isNeeded = (cuttree->cutnode0isNeeded && (nodes_isTree[lastcutnode]));
315 
316  assert(termscount == 0 || isPcMw);
317  StpVecFree(scip, stack);
318 }
319 
320 
321 /** deletes unvisited components */
322 static
324  SCIP* scip, /**< SCIP data structure */
325  const CUTNODES* cutnodes, /**< cut nodes */
326  const CUTTREE* cuttree, /**< cut tree data */
327  GRAPH* g, /**< graph */
328  SCIP_Real* fixedp, /**< pointer to offset value */
329  int* nelims /**< pointer to number of reductions */
330  )
331 {
332  const SCIP_Bool* const comps_isHit = cuttree->comps_isHit;
333  const int* const biconn_nodesmark = cutnodes->biconn_nodesmark;
334  const int lastcutnode = cutNodesGetLastCutnode(cutnodes);
335  const int nnodes = graph_get_nNodes(g);
336 
337  for( int i = 0; i < nnodes; i++ )
338  {
339  int comp;
340 
341  if( !g->mark[i] )
342  continue;
343 
344  comp = biconn_nodesmark[i];
345 
346  if( !comps_isHit[comp] && i != lastcutnode )
347  {
348 
349 #ifdef SCIP_DEBUG
350  SCIPdebugMessage("delete: ");
351  graph_knot_printInfo(g, i);
352 #endif
353  assert(!cuttree->nodes_isTree[i]);
354 
355  if( Is_term(g->term[i]) )
356  {
357  assert(graph_pc_isPcMw(g));
358  assert(graph_pc_termIsNonLeafTerm(g, i));
359 
360  graph_pc_deleteTerm(scip, g, i, fixedp);
361  }
362  else
363  {
364  graph_knot_del(scip, g, i, TRUE);
365  }
366 
367  (*nelims)++;
368  }
369  }
370 }
371 
372 
373 #ifndef NDEBUG
374 /** debug checker: makes sure that all remaining proper cut nodes are terminals */
375 static
377  const CUTNODES* cutnodes, /**< cut nodes */
378  const GRAPH* g /**< graph */
379  )
380 {
381  const int nnodes = graph_get_nNodes(g);
382 
383  // todo probably wrong
384 #ifdef SCIP_DISABLED
385  const int* const biconn_nodesmark = cutnodes->biconn_nodesmark;
386  const int* biconn_comproot = cutnodes->biconn_comproots;
387 
388  /* 1. make sure that the components of non-terminal cut-nodes are empty */
389 
390  for( int i = 0; i < cutnodes->biconn_ncomps; i++ )
391  {
392  const int cutnode = biconn_comproot[i];
393  assert(graph_knot_isInRange(g, cutnode));
394 
395  if( g->grad[cutnode] == 0 || Is_term(g->term[cutnode]) )
396  continue;
397 
398  for( int k = 0; k < nnodes; k++ )
399  {
400  if( biconn_nodesmark[k] != i )
401  continue;
402 
403  if( g->grad[k] > 0 && g->mark[k] && k != cutnode )
404  {
405  printf("issue for \n");
406  graph_knot_printInfo(g, k);
407  return FALSE;
408  }
409  }
410  }
411 #endif
412 
413  /* 2. make sure that for any nonterminal all incident edges are in the same component! */
414 
415  for( int i = 0; i < nnodes; i++ )
416  {
417  const int compid = cutnodes->biconn_nodesmark[i];
418 
419  if( g->grad[i] == 0 || Is_term(g->term[i]) )
420  continue;
421 
422  for( int e = g->outbeg[i]; e != EAT_LAST; e = g->oeat[e] )
423  {
424  const int head = g->head[e];
425 
426  if( cutnodes->biconn_nodesmark[head] != compid && !Is_term(g->term[head]) )
427  {
428  printf("issue for compid=%d, %d \n", compid, cutnodes->biconn_nodesmark[head] );
429  graph_knot_printInfo(g, i);
430  graph_knot_printInfo(g, head);
431 
432  return FALSE;
433  }
434  }
435  }
436 
437 
438  return TRUE;
439 }
440 #endif
441 
442 
443 /** changes required cut-nodes from non-terminals to terminals */
444 static
446  SCIP* scip, /**< SCIP data structure */
447  const CUTNODES* cutnodes, /**< cut nodes */
448  const CUTTREE* cuttree, /**< cut tree data */
449  GRAPH* g /**< graph */
450  )
451 {
452  const int* const biconn_nodesmark = cutnodes->biconn_nodesmark;
453  const SCIP_Bool* const nodes_isTree = cuttree->nodes_isTree;
454  const int ncutnodes = StpVecGetSize(cutnodes->artpoints);
455 
456  assert(nodes_isTree);
457  assert(ncutnodes > 0);
458 
459  for( int i = 0; i < ncutnodes; i++ )
460  {
461  const int cutnode = cutnodes->artpoints[i];
462  assert(graph_knot_isInRange(g, cutnode));
463 
464  if( g->grad[cutnode] == 0 )
465  continue;
466 
467  if( i == ncutnodes - 1 && !cuttree->cutnode0isNeeded )
468  continue;
469 
470  if( Is_term(g->term[cutnode]) )
471  {
472  assert(nodes_isTree[cutnode]);
473  continue;
474  }
475 
476  if( nodes_isTree[cutnode] )
477  {
478  const int compid = biconn_nodesmark[cutnode];
479  SCIP_Bool isTerm = FALSE;
480 
481  for( int e = g->outbeg[cutnode]; e != EAT_LAST; e = g->oeat[e] )
482  {
483  const int head = g->head[e];
484 
485  if( biconn_nodesmark[head] != compid && head != cutnodes->biconn_comproots[compid] )
486  {
487  isTerm = TRUE;
488  break;
489  }
490  }
491 
492  if( isTerm )
493  {
494 #ifdef SCIP_DEBUG
495  SCIPdebugMessage("cut node to terminal: ");
496  graph_knot_printInfo(g, cutnode);
497 #endif
498  graph_knot_chg(g, cutnode, STP_TERM);
499 
500  // todo remove me
501  if(g->grad[cutnode] == 1 )
502  {
503  printf("error in cut nodes terms");
504  exit(1);
505  }
506 
507  }
508  }
509  }
510 
511  assert(cutNodesTreeMakeTermsIsComplete(cutnodes, g));
512 }
513 
514 
515 /** initializes */
516 static
518  SCIP* scip, /**< SCIP data structure */
519  const GRAPH* g, /**< graph data structure */
520  const CUTNODES* cutnodes, /**< cut nodes */
521  CUTTREE* cuttree /**< cut tree data */
522  )
523 {
524  int* nodes_prednode;
527  const int nnodes = graph_get_nNodes(g);
528  const int ncomps = cutnodes->biconn_ncomps;
529 
530  assert(ncomps > 0);
531  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_prednode, nnodes) );
532  SCIP_CALL( SCIPallocBufferArray(scip, &nodes_isTree, nnodes) );
533  SCIP_CALL( SCIPallocBufferArray(scip, &comps_isHit, ncomps) );
534 
535  for( int i = 0; i < nnodes; i++ )
536  {
537  nodes_isTree[i] = FALSE;
538  nodes_prednode[i] = -1;
539  }
540 
541  for( int i = 0; i < ncomps; i++ )
542  comps_isHit[i] = FALSE;
543 
544  cuttree->nodes_prednode = nodes_prednode;
545  cuttree->nodes_isTree = nodes_isTree;
546  cuttree->comps_isHit = comps_isHit;
547 
548  return SCIP_OKAY;
549 }
550 
551 
552 /** exits */
553 static
555  SCIP* scip, /**< SCIP data structure */
556  CUTTREE* cuttree /**< cut tree data */
557  )
558 {
559  SCIPfreeBuffer(scip, &(cuttree->comps_isHit));
560  SCIPfreeBuffer(scip, &(cuttree->nodes_isTree));
561  SCIPfreeBuffer(scip, &(cuttree->nodes_prednode));
562 }
563 
564 
565 /** helper that extracts, reduces, re-inserts */
566 static
568  SCIP* scip, /**< SCIP data structure */
569  const BIDECOMP* bidecomp, /**< all-components storage */
570  int compindex, /**< component index */
571  GRAPH* graph, /**< graph data structure */
572  REDBASE* redbase /**< reduction stuff */
573  )
574 {
575  REDSOL* redsol = redbase->redsol;
576  SUBINOUT* subinout = bidecomp->subinout;
577  GRAPH* subgraph;
578 
579  assert(graph_valid(scip, graph));
580 
581  SCIP_CALL( graph_subgraphExtract(scip, graph, subinout, &subgraph) );
582 
583  SCIP_CALL( reduce_solLevelTopUpdate(scip, subgraph, redsol) );
585 
586 #ifdef SCIP_DEBUG
587  SCIPdebugMessage("subgraph before reduction: ");
588  graph_printInfoReduced(subgraph);
589 #endif
590 
591  {
592  RPARAMS* redparams = redbase->redparameters;
593  const int reductbound_org = redparams->reductbound;
594  const SCIP_Real offset_org = reduce_solGetOffset(redsol);
596  SCIPdebugMessage("subgraph: reductbound_min=%d reductbound=%d \n",
597  redparams->reductbound_min,redparams->reductbound );
598 
599  reduce_solSetOffset(0.0, redsol);
600  redbase->bidecompparams->newLevelStarted = TRUE;
601 
602  SCIP_CALL(reduce_redLoopStp(scip, subgraph, redbase));
603 
604  redparams->reductbound = reductbound_org;
605  reduce_solSetOffset(reduce_solGetOffset(redsol) + offset_org, redsol);
606 
607  assert(GE(reduce_solGetOffset(redsol), offset_org));
608  }
609 
610 #ifdef SCIP_DEBUG
611  SCIPdebugMessage("subgraph after reduction: ");
612  graph_printInfoReduced(subgraph);
613 #endif
614  SCIP_CALL(graph_subgraphReinsert(scip, subinout, graph, &subgraph));
615 
617  reduce_solLevelTopClean(scip, redsol);
618 
619  assert(graph_valid(scip, graph));
620 
621  return SCIP_OKAY;
622 }
623 
624 
625 /** reduces subproblem */
626 static
628  SCIP* scip, /**< SCIP data structure */
629  const BIDECOMP* bidecomp, /**< all-components storage */
630  int compindex, /**< component index */
631  GRAPH* g, /**< graph data structure */
632  REDBASE* redbase /**< reduction stuff */
633  )
634 {
635  assert(scip && g && bidecomp && redbase);
636  assert(redbase->bidecompparams);
637 
638  if( bidecomposition_componentIsTrivial(bidecomp, compindex) )
639  {
640  return SCIP_OKAY;
641  }
642 
643  SCIPdebugMessage("(depth %d) reduce component %d: \n", redbase->bidecompparams->depth, compindex);
644 
645  bidecomposition_markSub(bidecomp, compindex, g);
646  SCIP_CALL( decomposeReduceSubDoIt(scip, bidecomp, compindex, g, redbase) );
647 
648  return SCIP_OKAY;
649 }
650 
651 
652 /** fixes original edges */
653 static
655  SCIP* scip, /**< SCIP data structure */
656  const SUBINOUT* subinout, /**< helper for problem mapping */
657  SUBSTP* substp, /**< sub-problem */
658  GRAPH* orggraph, /**< original graph */
659  REDBASE* redbase, /**< reduction stuff */
660  int* nelims /**< number of eliminations or NULL */
661  )
662 {
663  SCIP_Real* offset = reduce_solGetOffsetPointer(redbase->redsol);
664  int* subedges_sol;
665  const int* const subedgesToOrg = graph_subinoutGetSubToOrgEdgeMap(subinout);
666  const int nsubedges = substpsolver_getNsubedges(substp);
667 
668  assert(nsubedges > 0);
669 
670  SCIP_CALL( SCIPallocBufferArray(scip, &subedges_sol, nsubedges) );
671  SCIP_CALL( substpsolver_getSolution(substp, subedges_sol) );
672 
673  for( int i = 0; i < nsubedges; i += 2 )
674  {
675  const int orgedge = subedgesToOrg[i];
676  assert(graph_edge_isInRange(orggraph, orgedge));
677 
678  if( subedges_sol[i] == CONNECT || subedges_sol[i + 1] == CONNECT )
679  {
680  SCIPdebugMessage("fix edge %d \n", orgedge);
681 
682  *offset += orggraph->cost[orgedge];
683 
684  /* NOTE: edge will be automatically contracted later; we avoid trouble with other
685  * connected components markers in this way */
686  orggraph->cost[orgedge] = 0.0;
687  orggraph->cost[flipedge(orgedge)] = 0.0;
688  graph_knot_chg(orggraph, orggraph->tail[orgedge], STP_TERM);
689  graph_knot_chg(orggraph, orggraph->head[orgedge], STP_TERM);
690  }
691  else
692  {
693  SCIPdebugMessage("delete edge %d \n", orgedge);
694 
695  if( nelims )
696  (*nelims)++;
697 
698  assert(subedges_sol[i] == UNKNOWN && subedges_sol[i + 1] == UNKNOWN);
699  graph_edge_del(scip, orggraph, orgedge, TRUE);
700  }
701  }
702 
703  SCIPfreeBufferArray(scip, &subedges_sol);
704 
705  return SCIP_OKAY;
706 }
707 
708 
709 
710 /** solves subproblems */
711 static
713  SCIP* scip, /**< SCIP data structure */
714  const BIDECOMP* bidecomp, /**< all-components storage */
715  GRAPH* orggraph, /**< graph data structure */
716  GRAPH* subgraph, /**< sub-graph */
717  REDBASE* redbase, /**< reduction stuff */
718  int* nelims /**< number of eliminations or NULL */
719  )
720 {
721  SUBINOUT* subinout = bidecomp->subinout;
722  SUBSTP* substp;
723  SCIP_Bool success;
724 
725  /* NOTE: subgraph will be moved into substp! */
726  SCIP_CALL( substpsolver_init(scip, subgraph, &substp) );
728  orggraph, substp) );
729 
730  SCIP_CALL( substpsolver_setMute(substp) );
731  //SCIP_CALL( substpsolver_setProbIsIndependent(substp) );
733 
734 #ifdef SCIP_DEBUG
735  printf("subgraph: ");
736  graph_printInfo(subgraph);
737 #endif
738 
739  SCIP_CALL( substpsolver_solve(scip, substp, &success) );
740  assert(success);
741 
742  /* fix solution in original graph */
743  SCIP_CALL( decomposeExactFixSol(scip, subinout, substp, orggraph, redbase, nelims) );
744 
745  graph_subinoutClean(scip, subinout);
746  substpsolver_free(scip, &substp);
747 
748  return SCIP_OKAY;
749 }
750 
751 
752 /** tries to solve subproblem */
753 static
755  SCIP* scip, /**< SCIP data structure */
756  const BIDECOMP* bidecomp, /**< all-components storage */
757  int compindex, /**< component index */
758  GRAPH* g, /**< graph data structure */
759  REDBASE* redbase, /**< reduction stuff */
760  int* nelims /**< number of eliminations or NULL */
761  )
762 {
763  GRAPH* subgraph;
764  SUBINOUT* subinout = bidecomp->subinout;
765  int subroot;
766 
767  assert(redbase->bidecompparams);
768 
769  if( bidecomposition_componentIsTrivial(bidecomp, compindex) )
770  {
771  SCIPdebugMessage("component is trivial, returning \n");
772  return SCIP_OKAY;
773  }
774 
775  SCIPdebugMessage("(depth %d) solve component %d to optimality \n", redbase->bidecompparams->depth, compindex);
776 
777  bidecomposition_markSub(bidecomp, compindex, g);
778  SCIP_CALL( graph_subgraphExtract(scip, g, subinout, &subgraph) );
779 
780 #ifdef SCIP_DEBUG
781  SCIPdebugMessage("original nodes of connected components: \n");
782 
783  for( int i = 0; i < orggraph->knots; i++ )
784  {
785  if( orggraph->mark[i] )
786  graph_knot_printInfo(orggraph, i);
787  }
788  #endif
789 
790  SCIP_CALL( bidecomposition_getMarkedSubRoot(scip, bidecomp, g, subgraph, &subroot) );
791  subgraph->source = subroot;
792 
793  SCIP_CALL( decomposeExactSubDoIt(scip, bidecomp, g, subgraph, redbase, nelims) );
794 
795  return SCIP_OKAY;
796 }
797 
798 
799 /** is promising? */
800 static
802  const GRAPH* g, /**< graph data structure */
803  const BIDECPARAMS* bidecompparams, /**< bidecomposition parameters */
804  const BIDECOMP* bidecomp /**< bidecomposition data structure */
805  )
806 {
807  const SCIP_Real mincompratio = bidecompparams->depth == 0 ? BIDECOMP_MINMAXCOMPRATIO_FIRST : BIDECOMP_MINMAXCOMPRATIO;
808  const SCIP_Real maxratio = bidecomposition_getMaxcompNodeRatio(bidecomp);
809 
810  assert(GT(maxratio, 0.0));
811 
812  if( bidecompparams->depth > 1 && g->knots < BIDECOMP_MINNODES )
813  return FALSE;
814 
815  return (maxratio < mincompratio);
816 }
817 
818 
819 /** is decomposition with (exact) solution of small components promising? */
820 static
822  const GRAPH* g, /**< graph data structure */
823  const REDBASE* redbase, /**< reduction stuff */
824  const BIDECOMP* bidecomp /**< bidecomposition data structure */
825  )
826 {
827  SCIP_Real maxratio;
828 
829  /* NOTE: we don't want to solve exactly in recombination heuristic etc. */
830  if( !redbase->redparameters->userec )
831  return FALSE;
832 
833  maxratio = bidecomposition_getMaxcompNodeRatio(bidecomp);
834  assert(GT(maxratio, 0.0));
835 
837  return FALSE;
838 
839  return (maxratio < BIDECOMP_MINMAXCOMPRATIO_PARTIAL);
840 }
841 
842 
843 /** reduced biconnected components separately */
844 static
846  SCIP* scip, /**< SCIP data structure */
847  GRAPH* g, /**< graph data structure */
848  BIDECOMP* bidecomp, /**< bidecomposition data structure */
849  REDBASE* redbase /**< reduction stuff */
850  )
851 {
852  REDSOL* redsol = redbase->redsol;
853 
854  SCIP_CALL( bidecomposition_initSubInOut(scip, g, bidecomp) );
855  SCIP_CALL( reduce_solLevelAdd(scip, g, redsol) );
856  redbase->bidecompparams->depth++;
857 
858  /* reduce each biconnected component individually */
859  for( int i = 0; i < bidecomp->nbicomps; i++ )
860  {
861  SCIP_CALL( decomposeReduceSub(scip, bidecomp, i, g, redbase) );
862  }
863 
864  redbase->bidecompparams->depth--;
865  /* NOTE: also removes level */
866  reduce_solLevelTopFinalize(scip, g, redsol);
867 
868  return SCIP_OKAY;
869 }
870 
871 
872 /** solves smaller biconnected components to optimality */
873 static
875  SCIP* scip, /**< SCIP data structure */
876  SCIP_Real maxcompratio, /**< max nodes ratio */
877  GRAPH* g, /**< graph data structure */
878  BIDECOMP* bidecomp, /**< bi-decomposition */
879  int* solnode, /**< solution nodes or NULL */
880  REDBASE* redbase, /**< reduction stuff */
881  int* nelims /**< number of eliminations or NULL */
882  )
883 {
884 #ifdef BENCH_SEPA_PARTIAL
885  static double totalTime = 0.0;
886  const double startTime = (double) clock() / (double) CLOCKS_PER_SEC;
887  double endTime;
888 #endif
889 
890  SCIP_CALL( bidecomposition_initSubInOut(scip, g, bidecomp) );
893 
894  SCIPdebugMessage("solving problem by partial exact decomposition at depth %d (%d components) \n",
895  redbase->bidecompparams->depth, bidecomp->nbicomps);
896 
897  /* solve small biconnected component individually */
898  for( int i = 0; i < bidecomp->nbicomps; i++ )
899  {
900  const SCIP_Real nodesratio = bidecomposition_getCompNodeRatio(bidecomp, i);
901  SCIPdebugMessage("nodes ratio of component %d: %f \n", i, nodesratio);
902 
903  if( nodesratio > maxcompratio )
904  {
905  SCIPdebugMessage("component is too large, skipping component \n");
906  continue;
907  }
908 
909  SCIP_CALL( decomposeExactSubTry(scip, bidecomp, i, g, redbase, nelims) );
910  }
911 
912  /* NOTE: solution edges have been fixed to 0 before */
913  SCIP_CALL( reduce_contract0Edges(scip, g, solnode, TRUE) );
914 
915 #ifdef BENCH_SEPA_PARTIAL
916  endTime = (double) clock() / (double) CLOCKS_PER_SEC;
917  totalTime += endTime - startTime;
918  printf("TIME FOR PARTIAL EXACT DECOMPISITION: %f (total: %f) \n", endTime - startTime, totalTime);
919 #endif
920 
921  return SCIP_OKAY;
922 }
923 
924 
925 /** tries to solve or reduce biconnected components separately */
926 static
928  SCIP* scip, /**< SCIP data structure */
929  const CUTNODES* cutnodes, /**< cut nodes */
930  GRAPH* g, /**< graph data structure */
931  REDBASE* redbase, /**< reduction stuff */
932  int* solnode, /**< solution nodes or NULL */
933  SCIP_Bool* wasDecomposed /**< performed recursive reduction? */
934  )
935 {
936  BIDECOMP* bidecomp;
937 
938  /* NOTE: does not work because we do node contractions when reinserting the subgraph,
939  * and because order of nodes is changed in subbgraph */
940  assert(redbase->solnode == NULL && "not supported");
941  assert(redbase->bidecompparams);
942  assert(redbase->bidecompparams->depth < redbase->bidecompparams->maxdepth);
943  assert(graph_valid(scip, g));
944  assert(*wasDecomposed == FALSE);
945 
946  SCIP_CALL( bidecomposition_init(scip, cutnodes, g, &bidecomp) );
947 
948  if( decomposeIsPromising(g, redbase->bidecompparams, bidecomp) )
949  {
950  SCIP_CALL( decomposeReduce(scip, g, bidecomp, redbase) );
951  *wasDecomposed = TRUE;
952  }
953  else if( decomposePartialIsPromising(g, redbase, bidecomp) )
954  {
955  SCIP_CALL( decomposePartialExact(scip, BIDECOMP_MAXCOMPRATIO_PARTIAL, g, bidecomp, solnode, redbase, NULL) );
956  }
957 
958  bidecomposition_free(scip, &bidecomp);
959  assert(graph_valid(scip, g));
960 
961  return SCIP_OKAY;
962 }
963 
964 
965 /** solves (not too large) biconnected component separately */
966 static
968  SCIP* scip, /**< SCIP data structure */
969  const CUTNODES* cutnodes, /**< cut nodes */
970  GRAPH* g, /**< graph data structure */
971  REDBASE* redbase, /**< reduction stuff */
972  int* solnode, /**< solution nodes or NULL */
973  int* nelims /**< number of eliminations */
974  )
975 {
976  BIDECOMP* bidecomp;
977 
978  /* NOTE: does not work because we do node contractions when reinserting the subgraph,
979  * and because order of nodes is changed in subbgraph */
980  assert(redbase->solnode == NULL && "not supported");
981  assert(redbase->bidecompparams);
982  assert(graph_valid(scip, g));
983 
984  SCIP_CALL( bidecomposition_init(scip, cutnodes, g, &bidecomp) );
985 
986  if( decomposePartialIsPromising(g, redbase, bidecomp) )
987  {
988  SCIP_CALL( decomposePartialExact(scip, BIDECOMP_MAXCOMPRATIO_AGGRESSIVE, g, bidecomp, solnode, redbase, nelims) );
989  }
990 
991  bidecomposition_free(scip, &bidecomp);
992  assert(graph_valid(scip, g));
993 
994  return SCIP_OKAY;
995 }
996 
997 
998 /*
999  * Interface methods
1000  */
1001 
1002 
1003 /** removes non-necessary bi-connected components and creates new terminals from cut-nodes */
1005  SCIP* scip, /**< SCIP data structure */
1006  const CUTNODES* cutnodes, /**< cut nodes */
1007  GRAPH* g, /**< graph data structure */
1008  SCIP_Real* fixedp, /**< pointer to offset value */
1009  int* nelims /**< pointer to number of reductions */
1010  )
1011 {
1012  CUTTREE cuttree = { NULL, NULL, NULL, FALSE };
1013 
1014  SCIP_CALL( cutNodesTreeInit(scip, g, cutnodes, &cuttree) );
1015  cutNodesTreeBuildSteinerTree(scip, g, cutnodes, &cuttree);
1016 
1017 #ifdef CUTTREE_PRINT_STATISTICS
1018  printf("\n STATS: \n");
1019 
1020  for( int i = 0; i < StpVecGetSize(cutnodes->artpoints); i++ )
1021  {
1022  const int cutnode = cutnodes->artpoints[i];
1023  SCIP_CALL( cutNodesTraverseFromCutNode(scip, g, cutnode, cutnodes) );
1024  }
1025 #endif
1026 
1027  cutNodesTreeDeleteComponents(scip, cutnodes, &cuttree, g, fixedp, nelims);
1028 
1029  if( !graph_pc_isPcMw(g) )
1030  cutNodesTreeMakeTerms(scip, cutnodes, &cuttree, g);
1031 
1032  cutNodesTreeExit(scip, &cuttree);
1033 
1034  return SCIP_OKAY;
1035 }
1036 
1037 
1038 /** decomposition into biconnected components and recursive reduction */
1040  SCIP* scip, /**< SCIP data structure */
1041  GRAPH* g, /**< graph data structure */
1042  REDBASE* redbase, /**< reduction base */
1043  int* solnode, /**< solution nodes or NULL */
1044  SCIP_Bool* wasDecomposed /**< performed recursive reduction? */
1045  )
1046 {
1047  CUTNODES* cutnodes;
1048 
1049  assert(scip && g && redbase && wasDecomposed);
1050  assert(graph_typeIsSpgLike(g) && "only SPG decomposition supported yet");
1051 
1052  *wasDecomposed = FALSE;
1053 
1054  if( g->terms == 1 )
1055  return SCIP_OKAY;
1056 
1057  graph_mark(g);
1058 
1059  if( !bidecomposition_isPossible(g) )
1060  {
1061  SCIPdebugMessage("graph is too large...don't decompose \n");
1062  return SCIP_OKAY;
1063  }
1064 
1065  SCIP_CALL( bidecomposition_cutnodesInit(scip, g, &cutnodes) );
1066  bidecomposition_cutnodesCompute(g, cutnodes);
1067 
1068  if( cutnodes->biconn_ncomps > 0 )
1069  {
1070  int dummy = 0;
1071  /* get rid of non-required biconnected components (without terminals) */
1072  SCIP_CALL( reduce_nonTerminalComponents(scip, cutnodes, g, reduce_solGetOffsetPointer(redbase->redsol), &dummy) );
1073 
1074  /* decompose and reduce recursively? */
1075  SCIP_CALL( decomposeExec(scip, cutnodes, g, redbase, solnode, wasDecomposed) );
1076  }
1077 
1078  bidecomposition_cutnodesFree(scip, &cutnodes);
1079 
1080  return SCIP_OKAY;
1081 }
1082 
1083 
1084 /** solves smaller connected components to optimality */
1086  SCIP* scip, /**< SCIP data structure */
1087  GRAPH* g, /**< graph data structure */
1088  REDBASE* redbase, /**< reduction base */
1089  int* solnode, /**< solution nodes or NULL */
1090  int* nelims /**< number of eliminations */
1091  )
1092 {
1093  CUTNODES* cutnodes;
1094 
1095  assert(scip && g && redbase && nelims);
1096  assert(graph_typeIsSpgLike(g) && "only SPG decomposition supported yet");
1097 
1098  *nelims = 0;
1099 
1100  if( g->terms == 1 )
1101  return SCIP_OKAY;
1102 
1103  graph_mark(g);
1104 
1105  if( !bidecomposition_isPossible(g) )
1106  {
1107  SCIPdebugMessage("graph is too large...don't decompose \n");
1108  return SCIP_OKAY;
1109  }
1110 
1111  SCIP_CALL( bidecomposition_cutnodesInit(scip, g, &cutnodes) );
1112  bidecomposition_cutnodesCompute(g, cutnodes);
1113 
1114  if( cutnodes->biconn_ncomps > 0 )
1115  {
1116  /* get rid of non-required biconnected components (without terminals) */
1117  SCIP_CALL( reduce_nonTerminalComponents(scip, cutnodes, g, reduce_solGetOffsetPointer(redbase->redsol), nelims) );
1118 
1119  SCIP_CALL( decomposeExecExact(scip, cutnodes, g, redbase, solnode, nelims) );
1120  }
1121 
1122  bidecomposition_cutnodesFree(scip, &cutnodes);
1123 
1124  return SCIP_OKAY;
1125 }
1126 
1127 
1128 
1129 /** articulation points based, simple reduction */
1131  SCIP* scip, /**< SCIP data structure */
1132  GRAPH* g, /**< graph data structure */
1133  SCIP_Real* fixedp, /**< pointer to offset value */
1134  int* nelims /**< pointer to number of reductions */
1135  )
1136 {
1137  CUTNODES* cutnodes;
1138 
1139  assert(scip && g && nelims);
1140  graph_mark(g);
1141 
1142  *nelims = 0;
1143 
1144  if( !bidecomposition_isPossible(g) )
1145  {
1146  SCIPdebugMessage("graph is too large...don't decompose \n");
1147  return SCIP_OKAY;
1148  }
1149 
1150  SCIP_CALL( bidecomposition_cutnodesInit(scip, g, &cutnodes) );
1151  bidecomposition_cutnodesCompute(g, cutnodes);
1152 
1153  if( cutnodes->biconn_ncomps > 0 )
1154  {
1155  SCIP_CALL( reduce_nonTerminalComponents(scip, cutnodes, g, fixedp, nelims) );
1156  }
1157 
1158  bidecomposition_cutnodesFree(scip, &cutnodes);
1159 
1160  return SCIP_OKAY;
1161 }
#define STP_Vectype(type)
Definition: stpvector.h:44
static SCIP_RETCODE cutNodesTreeInit(SCIP *scip, const GRAPH *g, const CUTNODES *cutnodes, CUTTREE *cuttree)
Definition: reduce_sepa.c:517
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static volatile int nterms
Definition: interrupt.c:38
#define StpVecGetSize(vec)
Definition: stpvector.h:139
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
int * biconn_comproots
#define BIDECOMP_MAXCOMPRATIO_AGGRESSIVE
Definition: reduce_sepa.c:51
void reduce_solLevelTopTransferSolBack(const int *, REDSOL *)
Definition: reduce_sol.c:1010
int source
Definition: graphdefs.h:195
SCIP_RETCODE reduce_solLevelTopTransferSolTo(const int *, REDSOL *)
Definition: reduce_sol.c:1067
SCIP_Bool bidecomposition_isPossible(const GRAPH *g)
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_RETCODE graph_subinoutActivateEdgeMap(const GRAPH *, SUBINOUT *)
Definition: graph_sub.c:769
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
int reduce_getMinNreductions(const GRAPH *, int)
Definition: reduce_base.c:1087
SCIP_RETCODE substpsolver_setMute(SUBSTP *substp)
Definition: substpsolver.c:525
int terms
Definition: graphdefs.h:192
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
SCIP_RETCODE substpsolver_setProbFullPresolve(SUBSTP *substp)
Definition: substpsolver.c:568
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
#define BIDECOMP_MINRED_MULTIPLIER
Definition: reduce_sepa.c:46
static void cutNodesTreeMakeTerms(SCIP *scip, const CUTNODES *cutnodes, const CUTTREE *cuttree, GRAPH *g)
Definition: reduce_sepa.c:445
#define FALSE
Definition: def.h:87
void graph_subinoutActivateNewHistory(SUBINOUT *)
Definition: graph_sub.c:788
SCIP_RETCODE reduce_nonTerminalComponents(SCIP *scip, const CUTNODES *cutnodes, GRAPH *g, SCIP_Real *fixedp, int *nelims)
Definition: reduce_sepa.c:1004
#define BIDECOMP_MINMAXCOMPRATIO_PARTIAL
Definition: reduce_sepa.c:49
#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
SCIP_Bool * nodes_isTree
Definition: reduce_sepa.c:64
void bidecomposition_free(SCIP *scip, BIDECOMP **bidecomposition)
const int * graph_subinoutGetSubToOrgNodeMap(const SUBINOUT *)
Definition: graph_sub.c:799
#define StpVecPopBack(vec)
Definition: stpvector.h:182
#define EAT_LAST
Definition: graphdefs.h:58
#define StpVecReserve(scip, vec, _size_)
Definition: stpvector.h:186
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE substpsolver_init(SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
Definition: substpsolver.c:313
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void graph_printInfo(const GRAPH *)
Definition: graph_stats.c:299
#define BIDECOMP_MINMAXCOMPRATIO
Definition: reduce_sepa.c:48
header only, simple implementation of an STL like vector
several decomposition methods for Steiner tree problems
struct cut_tree_data CUTTREE
static SCIP_Bool decomposePartialIsPromising(const GRAPH *g, const REDBASE *redbase, const BIDECOMP *bidecomp)
Definition: reduce_sepa.c:821
int *RESTRICT mark
Definition: graphdefs.h:198
static SCIP_RETCODE decomposeExactSubTry(SCIP *scip, const BIDECOMP *bidecomp, int compindex, GRAPH *g, REDBASE *redbase, int *nelims)
Definition: reduce_sepa.c:754
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
static void cutNodesTreeDeleteComponents(SCIP *scip, const CUTNODES *cutnodes, const CUTTREE *cuttree, GRAPH *g, SCIP_Real *fixedp, int *nelims)
Definition: reduce_sepa.c:323
SCIP_RETCODE reduce_articulations(SCIP *scip, GRAPH *g, SCIP_Real *fixedp, int *nelims)
Definition: reduce_sepa.c:1130
static SCIP_RETCODE decomposeReduceSub(SCIP *scip, const BIDECOMP *bidecomp, int compindex, GRAPH *g, REDBASE *redbase)
Definition: reduce_sepa.c:627
SCIP_Real bidecomposition_getCompNodeRatio(const BIDECOMP *bidecomp, int compindex)
int *RESTRICT oeat
Definition: graphdefs.h:231
#define GE(a, b)
Definition: portab.h:85
int * biconn_nodesmark
static void cutNodesTreeAddNode(int node, const CUTNODES *cutnodes, int lastcutnode, CUTTREE *cuttree)
Definition: reduce_sepa.c:225
SCIP_RETCODE substpsolver_transferHistory(const int *edgeMapToOrg, GRAPH *orggraph, SUBSTP *substp)
Definition: substpsolver.c:404
void reduce_solLevelTopClean(SCIP *, REDSOL *)
Definition: reduce_sol.c:997
void bidecomposition_markSub(const BIDECOMP *bidecomp, int compindex, GRAPH *g)
void bidecomposition_cutnodesCompute(const GRAPH *g, CUTNODES *cutnodes)
#define BIDECOMP_MINNODES
Definition: reduce_sepa.c:52
void reduce_solLevelTopFinalize(SCIP *, GRAPH *, REDSOL *)
Definition: reduce_sol.c:956
static SCIP_RETCODE decomposePartialExact(SCIP *scip, SCIP_Real maxcompratio, GRAPH *g, BIDECOMP *bidecomp, int *solnode, REDBASE *redbase, int *nelims)
Definition: reduce_sepa.c:874
int *RESTRICT grad
Definition: graphdefs.h:201
static int cutNodesGetLastCutnode(const CUTNODES *cutnodes)
Definition: reduce_sepa.c:75
SCIP_RETCODE graph_subgraphExtract(SCIP *, GRAPH *, SUBINOUT *, GRAPH **)
Definition: graph_sub.c:712
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real bidecomposition_getMaxcompNodeRatio(const BIDECOMP *bidecomp)
Solver for Steiner tree (sub-) problems.
SCIP_Real reduce_solGetOffset(const REDSOL *)
Definition: reduce_sol.c:1137
SCIP_RETCODE reduce_bidecompositionExact(SCIP *scip, GRAPH *g, REDBASE *redbase, int *solnode, int *nelims)
Definition: reduce_sepa.c:1085
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_node.c:111
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE reduce_solLevelAdd(SCIP *, const GRAPH *, REDSOL *)
Definition: reduce_sol.c:897
SCIP_RETCODE bidecomposition_cutnodesInit(SCIP *scip, const GRAPH *g, CUTNODES **cutnodes)
#define BIDECOMP_MINMAXCOMPRATIO_FIRST
Definition: reduce_sepa.c:47
static SCIP_Bool decomposeIsPromising(const GRAPH *g, const BIDECPARAMS *bidecompparams, const BIDECOMP *bidecomp)
Definition: reduce_sepa.c:801
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
void reduce_solSetOffset(SCIP_Real, REDSOL *)
Definition: reduce_sol.c:1124
#define SCIP_Bool
Definition: def.h:84
static SCIP_Bool cutNodesTreeMakeTermsIsComplete(const CUTNODES *cutnodes, const GRAPH *g)
Definition: reduce_sepa.c:376
SCIP_RETCODE bidecomposition_initSubInOut(SCIP *scip, const GRAPH *g, BIDECOMP *bidecomposition)
SCIP_RETCODE reduce_bidecomposition(SCIP *scip, GRAPH *g, REDBASE *redbase, int *solnode, SCIP_Bool *wasDecomposed)
Definition: reduce_sepa.c:1039
static void cutNodesTreeExit(SCIP *scip, CUTTREE *cuttree)
Definition: reduce_sepa.c:554
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
#define flipedge(edge)
Definition: graphdefs.h:84
const int * graph_subinoutGetOrgToSubNodeMap(const SUBINOUT *)
Definition: graph_sub.c:825
#define STP_TERM
Definition: graphdefs.h:61
static SCIP_RETCODE decomposeReduce(SCIP *scip, GRAPH *g, BIDECOMP *bidecomp, REDBASE *redbase)
Definition: reduce_sepa.c:845
int *RESTRICT term
Definition: graphdefs.h:196
void bidecomposition_cutnodesFree(SCIP *scip, CUTNODES **cutnodes)
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
int graph_pc_nNonLeafTerms(const GRAPH *)
static SCIP_RETCODE decomposeExec(SCIP *scip, const CUTNODES *cutnodes, GRAPH *g, REDBASE *redbase, int *solnode, SCIP_Bool *wasDecomposed)
Definition: reduce_sepa.c:927
static SCIP_RETCODE decomposeExecExact(SCIP *scip, const CUTNODES *cutnodes, GRAPH *g, REDBASE *redbase, int *solnode, int *nelims)
Definition: reduce_sepa.c:967
#define SCIPfreeBuffer(scip, ptr)
Definition: scip_mem.h:125
static SCIP_RETCODE decomposeExactFixSol(SCIP *scip, const SUBINOUT *subinout, SUBSTP *substp, GRAPH *orggraph, REDBASE *redbase, int *nelims)
Definition: reduce_sepa.c:654
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
void graph_subinoutClean(SCIP *, SUBINOUT *)
Definition: graph_sub.c:882
#define BIDECOMP_MAXCOMPRATIO_PARTIAL
Definition: reduce_sepa.c:50
static SCIP_RETCODE decomposeReduceSubDoIt(SCIP *scip, const BIDECOMP *bidecomp, int compindex, GRAPH *graph, REDBASE *redbase)
Definition: reduce_sepa.c:567
int graph_pc_deleteTerm(SCIP *, GRAPH *, int, SCIP_Real *)
const int * graph_subinoutGetSubToOrgEdgeMap(const SUBINOUT *)
Definition: graph_sub.c:812
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_Real * reduce_solGetOffsetPointer(REDSOL *)
Definition: reduce_sol.c:1285
#define BIDECOMP_MINNODES_PARTIAL
Definition: reduce_sepa.c:53
#define SCIP_Real
Definition: def.h:177
SCIP_Bool * comps_isHit
Definition: reduce_sepa.c:63
static void cutNodesTreeBuildSteinerTree(SCIP *scip, const GRAPH *g, const CUTNODES *cutnodes, CUTTREE *cuttree)
Definition: reduce_sepa.c:252
#define StpVecFree(scip, vec)
Definition: stpvector.h:153
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_Bool cutnode0isNeeded
Definition: reduce_sepa.c:65
SCIP_RETCODE reduce_solLevelTopUpdate(SCIP *, const GRAPH *, REDSOL *)
Definition: reduce_sol.c:922
int substpsolver_getNsubedges(const SUBSTP *substp)
Definition: substpsolver.c:488
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
BIDECPARAMS * bidecompparams
Definition: reducedefs.h:103
void substpsolver_free(SCIP *scip, SUBSTP **substp)
Definition: substpsolver.c:380
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
RPARAMS * redparameters
Definition: reducedefs.h:102
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:167
SCIP_RETCODE reduce_redLoopStp(SCIP *, GRAPH *, REDBASE *)
Definition: reduce_base.c:2074
SCIP_RETCODE reduce_contract0Edges(SCIP *, GRAPH *, int *, SCIP_Bool)
SCIP_Bool bidecomposition_componentIsTrivial(const BIDECOMP *bidecomp, int compindex)
SCIP_RETCODE bidecomposition_getMarkedSubRoot(SCIP *scip, const BIDECOMP *bidecomp, const GRAPH *orggraph, const GRAPH *subgraph, int *subroot)
SCIP_RETCODE graph_subgraphReinsert(SCIP *, SUBINOUT *, GRAPH *, GRAPH **)
Definition: graph_sub.c:983
SCIP_RETCODE substpsolver_solve(SCIP *scip, SUBSTP *substp, SCIP_Bool *success)
Definition: substpsolver.c:452
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
int * nodes_prednode
Definition: reduce_sepa.c:62
includes various reduction methods for Steiner tree problems
void graph_printInfoReduced(const GRAPH *)
Definition: graph_stats.c:375
SCIP_RETCODE bidecomposition_init(SCIP *scip, const CUTNODES *cutnodes, const GRAPH *g, BIDECOMP **bidecomposition)
static SCIP_RETCODE decomposeExactSubDoIt(SCIP *scip, const BIDECOMP *bidecomp, GRAPH *orggraph, GRAPH *subgraph, REDBASE *redbase, int *nelims)
Definition: reduce_sepa.c:712
SCIP callable library.