Scippy

SCIP

Solving Constraint Integer Programs

extreduce_base.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 extreduce_base.c
17  * @brief extended reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements interface methods for extended reduction techniques for several Steiner problems.
21  *
22  * A list of all interface methods can be found in reduce.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 //#define SCIP_DEBUG
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <assert.h>
31 #include "graph.h"
32 #include "solstp.h"
33 #include "extreduce.h"
34 
35 #define EXT_PSEUDO_DEGREE_MIN 3
36 #define EXT_PSEUDO_DEGREE_MAX 5
37 
38 #define STP_GENSTAR_MAXDEG 6
39 #define STP_GENSTAR_MAXENDDEG 4
40 
41 #define GENSTAR_NODE_OTHER 0
42 #define GENSTAR_NODE_TAIL 1
43 #define GENSTAR_NODE_HEAD 2
44 #define GENSTAR_NODE_COMBI 3
45 
46 #define EXT_PROFIT_MINRATIO 0.05
47 
48 
50 
51 
52 
53 /** generalized star */
54 typedef struct general_star
55 {
57  STP_Vectype(int) edges_tail;
58  STP_Vectype(int) edges_head;
59  STP_Vectype(int) edges_all;
60  int* nodes_mark;
61  int* tmp_compedges;
62  int* tmp_extleaves;
63  int edge;
64  int replacedge_tail;
65  int replacedge_head;
66 } GENSTAR;
67 
68 
69 /** helper */
71 {
72  SCIP_Real* cutoffs; /**< cutoffs array of size STP_DELPSEUDO_MAXNEDGES */
73  int* nodestouches; /**< touches array on nodes */
74  SCIP_Real* offsetp; /**< pointer to store offset */
75  STP_Bool* nodeInSol; /**< solution marker per node or NULL */
76  int node; /**< current node */
77  int nelims_extended; /**< number of eliminations */
78  int nelims_simple; /**< number of eliminations for simple deletion */
79  SCIP_Bool cutoffIsPromising; /**< is sufficient cutoff possible? */
80  SCIP_Bool cutoffIsComputed; /**< already computed?? */
81  SCIP_Bool useSolForEq; /**< use solution for equality? */
82  enum EXTPSEUDO_MODE deletionMode; /**< what to delete */
83 } EXTPSEUDO;
84 
85 
86 #ifndef NDEBUG
87 /** all good with the graph->mark array? */
88 static
90  const REDCOST* redcostdata, /**< reduced cost data */
91  const GRAPH* graph /**< graph data structure */
92 )
93 {
94  const int nnodes = graph_get_nNodes(graph);
95  const int redcostroot = redcosts_getRootTop(redcostdata);
96 
97  assert(graph_knot_isInRange(graph, redcostroot));
98 
99  for( int k = 0; k < nnodes; k++ )
100  {
101  if( graph->grad[k] == 0 && k != redcostroot && !Is_term(graph->term[k]) )
102  {
103  if( graph->mark[k] )
104  {
105  graph_knot_printInfo(graph, k);
106  return FALSE;
107  }
108  }
109  }
110 
111  return TRUE;
112 }
113 #endif
114 
115 
116 /** replaces edge by a path */
117 static inline
119  SCIP* scip, /**< SCIP */
120  int edge, /**< edge to replace */
121  const GENSTAR* genstar, /**< star */
122  GRAPH* graph, /**< graph data structure (in/out) */
123  REDCOST* redcostdata, /**< reduced cost data structures */
124  DISTDATA* distdata, /**< distance data (in/out) */
125  EXTPERMA* extpermanent /**< (in/out) */
126 )
127 {
128  const int tail = graph->tail[edge];
129  const int head = graph->head[edge];
130  const int path_edgein = flipedge(genstar->replacedge_tail);
131  const int path_edgeout = genstar->replacedge_head;
132 
133 #ifdef SCIP_DEBUG
134  SCIPdebugMessage("replacing edge ");
135  graph_edge_printInfo(graph, edge);
136 
137  SCIPdebugMessage("by path \n");
138  graph_edge_printInfo(graph, path_edgein);
139  graph_edge_printInfo(graph, edge);
140  graph_edge_printInfo(graph, path_edgeout);
141 #endif
142 
143  assert(extreduce_distCloseNodesAreValid(scip, graph, distdata));
144 
145  distdata->hasPathReplacement = TRUE;
146 
147  if( distdata->sdistdata )
148  {
149  SCIP_CALL_ABORT( reduce_sdRepair(scip, edge, TRUE, graph, distdata->sdistdata) );
150  }
151 
152  {
153  const int csredge = graph->dcsr_storage->id2csredge[edge];
154  assert(graph_valid_dcsr(graph, FALSE));
155  graph_dcsr_deleteEdgeBi(scip, graph->dcsr_storage, csredge);
156  assert(graph_valid_dcsr(graph, FALSE));
157  }
158 
159  SCIP_CALL( graph_edge_delPseudoPath(scip, graph, edge, path_edgein, path_edgeout, redcosts_getEdgeCostsTop(redcostdata)) );
160  extreduce_distDataDeleteEdge(scip, graph, edge, distdata);
161 
162  if( extpermanent )
163  {
164  const int path_tail = graph->tail[path_edgein];
165  const int path_head = graph->head[path_edgeout];
166 
167  reduce_impliedNodesRepair(scip, graph, path_tail, path_head, extpermanent->nodes_implications);
168  reduce_impliedNodesRepair(scip, graph, tail, head, extpermanent->nodes_implications);
169  assert(reduce_impliedNodesIsValid(graph, (const STP_Vectype(int)*) extpermanent->nodes_implications));
170  }
171 
172  if( graph->grad[tail] == 0 )
173  {
174  if( Is_term(graph->term[tail]) )
175  {
176  assert(graph_pc_isPcMw(graph) || tail == graph->source);
177  }
178  else
179  {
180  graph->mark[tail] = FALSE;
181  }
182  }
183 
184  if( graph->grad[head] == 0 )
185  {
186  if( Is_term(graph->term[head]) || head == graph->source )
187  {
188  assert(graph_pc_isPcMw(graph));
189  }
190  else
191  {
192  graph->mark[head] = FALSE;
193  }
194  }
195 
196  assert(extreduce_distCloseNodesAreValid(scip, graph, distdata));
197 
198 
199  return SCIP_OKAY;
200 }
201 
202 
203 /** deletes an edge and makes corresponding adaptations */
204 static inline
206  SCIP* scip, /**< SCIP */
207  int edge, /**< edge to delete */
208  GRAPH* graph, /**< graph data structure (in/out) */
209  DISTDATA* distdata, /**< distance data (in/out) */
210  EXTPERMA* extpermanent /**< (in/out) */
211 )
212 {
213  const int tail = graph->tail[edge];
214  const int head = graph->head[edge];
215 
216 #ifdef SCIP_DEBUG
217  SCIPdebugMessage("removing edge ");
218  graph_edge_printInfo(graph, edge);
219 #endif
220 
221  assert(extreduce_distCloseNodesAreValid(scip, graph, distdata));
222 
223  if( distdata->sdistdata )
224  {
225  SCIP_CALL_ABORT( reduce_sdRepair(scip, edge, distdata->hasPathReplacement, graph, distdata->sdistdata) );
226  }
227 
228  /*
229  static int cc = 0;
230  char name[1000];
231  sprintf(name, "outprev%d.stp", cc);
232  graph_writeStpByName(scip, graph, name, 0.0);
233  graph_edge_printInfo(graph, edge);
234 
235  */
236 
237  graph_edge_delFull(scip, graph, edge, TRUE);
238  extreduce_distDataDeleteEdge(scip, graph, edge, distdata);
239 
240  if( extpermanent )
241  {
242  reduce_impliedNodesRepair(scip, graph, tail, head, extpermanent->nodes_implications);
243  assert(reduce_impliedNodesIsValid(graph, (const STP_Vectype(int)*) extpermanent->nodes_implications));
244  }
245 
246  if( graph->grad[tail] == 0 )
247  {
248  if( Is_term(graph->term[tail]) )
249  {
250  assert(graph_pc_isPcMw(graph) || tail == graph->source);
251  }
252  else
253  {
254  graph->mark[tail] = FALSE;
255  }
256  }
257 
258  if( graph->grad[head] == 0 )
259  {
260  if( Is_term(graph->term[head]) || head == graph->source )
261  {
262  assert(graph_pc_isPcMw(graph));
263  }
264  else
265  {
266  graph->mark[head] = FALSE;
267  }
268  }
269 
270  assert(extreduce_distCloseNodesAreValid(scip, graph, distdata));
271 }
272 
273 /** initialize */
274 static inline
276  SCIP* scip, /**< SCIP data structure */
277  SCIP_Bool useSd, /**< use special distance? */
278  GRAPH* graph, /**< graph data structure */
279  STP_Bool* edgedeletable, /**< edge array to mark which (directed) edge can be removed */
280  DISTDATA** distdata, /**< distance data (out) */
281  EXTPERMA** extpermanent /**< permanent extension data (out) */
282 )
283 {
284  assert(!graph_pc_isPcMw(graph) || !graph->extended);
285 
286  graph_mark(graph);
287 
288  SCIP_CALL( graph_init_dcsr(scip, graph) );
289  SCIP_CALL( extreduce_distDataInit(scip, graph, STP_EXT_CLOSENODES_MAXN, useSd, FALSE, distdata) );
290  SCIP_CALL( extreduce_extPermaInit(scip, extred_full, graph, edgedeletable, extpermanent) );
291 
292  return SCIP_OKAY;
293 }
294 
295 
296 /** free */
297 static inline
298 void extFree(
299  SCIP* scip, /**< SCIP data structure */
300  GRAPH* graph, /**< graph data structure */
301  DISTDATA** distdata, /**< distance data (in/out) */
302  EXTPERMA** extpermanent /**< permanent extension data (in/out) */
303 )
304 {
305  extreduce_extPermaFree(scip, extpermanent);
306  extreduce_distDataFree(scip, graph, distdata);
307  graph_free_dcsr(scip, graph);
308 }
309 
310 
311 /** initializes for check */
312 static inline
314  SCIP* scip, /**< SCIP data structure */
315  const GRAPH* g, /**< graph data structure */
316  GENSTAR* genstar /**< general star */
317 )
318 {
319  int* const nodes_mark = genstar->nodes_mark;
320  const int ntails = StpVecGetSize(genstar->edges_tail);
321  const int nheads = StpVecGetSize(genstar->edges_head);
322 
323  assert(ntails >= 1 && nheads >= 1);
324  assert(ntails + nheads >= 3);
325 
326  StpVecClear(genstar->edges_all);
327 
328  for( int i = 0; i < ntails; i++ )
329  {
330  const int edge = genstar->edges_tail[i];
331  const int head = g->head[edge];
332  assert(graph_edge_isInRange(g, edge));
333  assert(nodes_mark[head] == GENSTAR_NODE_OTHER);
334 
335  StpVecPushBack(scip, genstar->edges_all, edge);
336  nodes_mark[head] = GENSTAR_NODE_TAIL;
337  }
338 
339  for( int i = 0; i < nheads; i++ )
340  {
341  const int edge = genstar->edges_head[i];
342  const int head = g->head[edge];
343  assert(graph_edge_isInRange(g, edge));
344  assert(nodes_mark[head] == GENSTAR_NODE_OTHER || nodes_mark[head] == GENSTAR_NODE_TAIL);
345 
346  StpVecPushBack(scip, genstar->edges_all, edge);
347 
348  if( nodes_mark[head] == GENSTAR_NODE_OTHER )
349  {
350  nodes_mark[head] = GENSTAR_NODE_HEAD;
351  }
352  else
353  {
354  assert(nodes_mark[head] == GENSTAR_NODE_TAIL);
355  nodes_mark[head] = GENSTAR_NODE_COMBI;
356  }
357  }
358 
359  assert(StpVecGetSize(genstar->edges_all) == ntails + nheads);
360 
361 #ifdef SCIP_DEBUG
362  SCIPdebugMessage("\n all general star edges: \n");
363  for( int i = 0; i < StpVecGetSize(genstar->edges_all); i++ )
364  {
365  graph_edge_printInfo(g, genstar->edges_all[i]);
366  }
367 #endif
368 
369  reduce_starResetWithEdges(g, genstar->edges_all, genstar->star);
370 }
371 
372 
373 /** exits from check */
374 static inline
376  SCIP* scip, /**< SCIP data structure */
377  const GRAPH* g, /**< graph data structure */
378  GENSTAR* genstar /**< general star */
379 )
380 {
381  int* const nodes_mark = genstar->nodes_mark;
382  const int degree = StpVecGetSize(genstar->edges_all);
383 
384  assert(degree == (StpVecGetSize(genstar->edges_head) + StpVecGetSize(genstar->edges_tail)));
385 
386  for( int i = 0; i < degree; i++ )
387  {
388  const int edge = genstar->edges_all[i];
389  const int head = g->head[edge];
390  assert(graph_edge_isInRange(g, edge));
391 
392  nodes_mark[head] = GENSTAR_NODE_OTHER;
393  }
394 }
395 
396 
397 /** gets next star */
398 static inline
400  const GRAPH* g, /**< graph data structure */
401  GENSTAR* genstar, /**< general star */
402  EXTCOMP* extcomp, /**< to be filled */
403  SCIP_Bool* allVisited /**< all stars visited? */
404 )
405 {
406  const int center_edge = genstar->edge;
407  const int center_tail = g->tail[center_edge];
408  int nstaredges;
409  int* const compedges = extcomp->compedges;
410  int* const extleaves = extcomp->extleaves;
411  const int* staredges = reduce_starGetNext(genstar->star, &(nstaredges));
412  int* const nodes_mark = genstar->nodes_mark;
413  SCIP_Bool hasConflict = FALSE;
414  int ntailnodes = 0;
415  int nheadnodes = 0;
416 
417  *allVisited = FALSE;
418 
419 #ifdef SCIP_DEBUG
420  SCIPdebugMessage("star edges: \n");
421  for( int i = 0; i < nstaredges; i++ )
422  {
423  graph_edge_printInfo(g, staredges[i]);
424  }
425 #endif
426 
427  assert(graph_edge_isInRange(g, center_edge));
428  assert(nstaredges >= 3);
429 
430  /* add component edges and check for conflicts */
431  for( int i = 0; i < nstaredges; i++ )
432  {
433  const int outedge = staredges[i];
434  const int head = g->head[outedge];
435  assert(graph_edge_isInRange(g, outedge));
436  assert(nodes_mark[head] != GENSTAR_NODE_OTHER);
437 
438  if( nodes_mark[head] < 0 )
439  {
440  SCIPdebugMessage("double end node: %d ... \n", head);
441  assert(nodes_mark[head] == -GENSTAR_NODE_COMBI);
442  hasConflict = TRUE;
443  continue;
444  }
445 
446  if( nodes_mark[head] == GENSTAR_NODE_TAIL )
447  {
448  ntailnodes++;
449  assert(g->tail[outedge] == center_tail);
450  }
451  else if( nodes_mark[head] == GENSTAR_NODE_HEAD )
452  {
453  nheadnodes++;
454  assert(g->tail[outedge] == g->head[center_edge]);
455  }
456  else if( nodes_mark[head] == GENSTAR_NODE_COMBI )
457  {
458  if( g->tail[outedge] == center_tail )
459  {
460  ntailnodes++;
461  }
462  else
463  {
464  assert(g->tail[outedge] == g->head[center_edge]);
465  nheadnodes++;
466  }
467  }
468 
469  /* mark as visited */
470  nodes_mark[head] *= -1;
471  }
472 
473  /* clean up */
474  for( int i = 0; i < nstaredges; i++ )
475  {
476  const int outedge = staredges[i];
477  const int head = g->head[outedge];
478  assert(graph_edge_isInRange(g, outedge));
479  assert(nodes_mark[head] != GENSTAR_NODE_OTHER);
480 
481  if( nodes_mark[head] < 0 )
482  nodes_mark[head] *= -1;
483  }
484 
485  if( !hasConflict && (ntailnodes == 0 || nheadnodes == 0) )
486  {
487  SCIPdebugMessage("one sided star... \n");
488  hasConflict = TRUE;
489  }
490 
491  if( hasConflict )
492  {
493  SCIPdebugMessage("...conflict found! \n");
494  if( reduce_starAllAreChecked(genstar->star) )
495  {
496  *allVisited = TRUE;
497  }
498  else
499  {
500  generalStarCheckGetNextStar(g, genstar, extcomp, allVisited);
501  }
502 
503  return;
504  }
505 
506  extcomp->ncompedges = nstaredges;
507  extcomp->nextleaves = nstaredges - 1;
508 
509  assert(g->tail[staredges[0]] == center_tail);
510  compedges[0] = flipedge(staredges[0]);
511 
512  for( int i = 1; i < nstaredges; i++ )
513  {
514  const int outedge = staredges[i];
515 
516  compedges[i] = outedge;
517  }
518 
519 
520  for( int i = 1; i < nstaredges; i++ )
521  {
522  const int outedge = staredges[i];
523  extleaves[i - 1] = g->head[outedge];
524  }
525 
526 #ifdef SCIP_DEBUG
527  SCIPdebugMessage("select component edges: \n");
528  for( int i = 0; i < nstaredges; i++ )
529  {
530  graph_edge_printInfo(g, compedges[i]);
531  }
532 #endif
533 
534  assert(compedges[0] >= 0);
535  extcomp->comproot = g->tail[compedges[0]];
536 
537  assert(extcomp->ncompedges >= 3);
538  assert(extcomp->comproot >= 0);
539 }
540 
541 
542 /** check for elimination */
543 static inline
545  SCIP* scip, /**< SCIP data structure */
546  const GRAPH* graph, /**< graph data structure */
547  const REDCOST* redcostdata, /**< reduced cost data structures */
548  GENSTAR* genstar, /**< general star */
549  EXTPERMA* extpermanent, /**< data */
550  SCIP_Bool* isDeletable /**< deletable? */
551 )
552 {
553  const int* result = extpermanent->result;
554  const int edge = genstar->edge;
555  const int degree_tail = graph->grad[graph->tail[edge]];
556  const int degree_head = graph->grad[graph->head[edge]];
557 #ifndef NDEBUG
558  const int tree_maxdepth_org = extpermanent->tree_maxdepth;
559 #endif
560 
561 #ifdef SCIP_DEBUG
562  SCIPdebugMessage("checking GENERAL STAR edge ");
563  graph_edge_printInfo(graph, edge);
564 #endif
565 
566  *isDeletable = TRUE;
567 
568  assert(graph_edge_isInRange(graph, edge));
569  assert(degree_tail + degree_head <= STP_GENSTAR_MAXDEG + 2);
570 
571 
572  if( degree_tail < 3 && degree_head < 3 )
573  {
574  SCIPdebugMessage("general-star early rule-out! \n");
575  return SCIP_OKAY;
576  }
577 
578  if( degree_tail == 1 || degree_head == 1 )
579  {
580  SCIPdebugMessage("general-star early rule-out! \n");
581  return SCIP_OKAY;
582  }
583 
584  if( degree_tail + degree_head == STP_GENSTAR_MAXDEG + 2 )
585  extpermanent->tree_maxdepth--;
586 
587  generalStarCheckInit(scip, graph, genstar);
588  extpermanent->redcostEqualAllow = (extpermanent->solIsValid && result[edge] != CONNECT && result[flipedge(edge)] != CONNECT);
589 
590  /* check all general stars of degree >= 3, as long as they can be ruled-out */
591  while ( *isDeletable )
592  {
593  SCIP_Bool allVisited;
594  EXTCOMP extcomp = { .compedges = genstar->tmp_compedges, .extleaves = genstar->tmp_extleaves,
595  .nextleaves = -1, .ncompedges = -1, .genstar_centeredge = genstar->edge,
596  .comproot = -1, .allowReversion = FALSE };
597 
598  generalStarCheckGetNextStar(graph, genstar, &extcomp, &allVisited);
599 
600  if( allVisited )
601  break;
602 
603  *isDeletable = FALSE;
604  SCIP_CALL( extreduce_checkComponent(scip, graph, redcostdata, &extcomp, extpermanent, isDeletable) );
605 
606  if( reduce_starAllAreChecked(genstar->star) )
607  break;
608  }
609 
610  if( degree_tail + degree_head == STP_GENSTAR_MAXDEG + 2 )
611  extpermanent->tree_maxdepth++;
612 
613  generalStarCheckExit(scip, graph, genstar);
614 
615  assert(tree_maxdepth_org == extpermanent->tree_maxdepth);
616 
617  return SCIP_OKAY;
618 }
619 
620 
621 /** sets up the general star (especially edges_tail and edges_head)
622  * and checks whether deletion attempt makes sense */
623 static inline
625  SCIP* scip, /**< SCIP data structure */
626  const GRAPH* graph, /**< graph data structure */
627  int edge, /**< inducing edge */
628  GENSTAR* genstar, /**< general star */
629  SCIP_Bool* isPromising, /**< promising? */
630  DISTDATA* distdata /**< distance data */
631 )
632 {
633  const int tail = graph->tail[edge];
634  const int head = graph->head[edge];
635  StpVecClear(genstar->edges_tail);
636  StpVecClear(genstar->edges_head);
637  genstar->edge = edge;
638  genstar->replacedge_tail = -1;
639  genstar->replacedge_head = -1;
640 
641  *isPromising = FALSE;
642 
643  /* NOTE: considered too expensive, since SD tree would need to be rebuilt */
644  if( reduce_sdgraphEdgeIsInMst( distdata->sdistdata->sdgraph, edge) )
645  return;
646 
647  if( (graph->grad[tail] + graph->grad[head]) <= (STP_GENSTAR_MAXDEG + 2) && !Is_term(graph->term[tail]) && !Is_term(graph->term[head]) )
648  {
649  PSEUDOANS* const pseudoancestors = graph->pseudoancestors;
650  const SCIP_Real edgecost = graph->cost[edge];
651  const SCIP_Real maxsdcost = reduce_sdgraphGetMaxCost(distdata->sdistdata->sdgraph);
652  const STP_Bool* halfedges_isInSdMst = reduce_sdgraphGetMstHalfMark(distdata->sdistdata->sdgraph);
653  int* hasharr;
654  int ntails;
655  int nfails;
656  int nheads;
657  const int hashsize = graph_pseudoAncestorsGetHashArraySize(pseudoancestors);
658  const STP_Vectype(int) edges_tail;
659  const STP_Vectype(int) edges_head;
660 
661  assert(hashsize > 0);
662 
663  *isPromising = TRUE;
664 
665  SCIP_CALL_ABORT( SCIPallocCleanBufferArray(scip, &hasharr, hashsize) );
666 
667  for( int e = graph->outbeg[tail]; e != EAT_LAST; e = graph->oeat[e] )
668  {
669  const int myhead = graph->head[e];
670 
671  if( myhead != head )
672  {
673  StpVecPushBack(scip, genstar->edges_tail, e);
674  }
675  }
676 
677  for( int e = graph->outbeg[head]; e != EAT_LAST; e = graph->oeat[e] )
678  {
679  const int myhead = graph->head[e];
680 
681  if( myhead != tail )
682  {
683  StpVecPushBack(scip, genstar->edges_head, e);
684  }
685  }
686 
687  ntails = StpVecGetSize(genstar->edges_tail);
688  nheads = StpVecGetSize(genstar->edges_head);
689  edges_tail = genstar->edges_tail;
690  edges_head = genstar->edges_head;
691  assert(ntails + nheads <= 6);
692 
693  nfails = 0;
694 
695  graph_pseudoAncestors_hashEdge(pseudoancestors, edge, hasharr);
696 
697  for( int j = 0; j < ntails && *isPromising; j++ )
698  {
699  SCIP_Bool conflict;
700  const int edge_j = edges_tail[j];
701  const int node_j = graph->head[edge_j];
702  graph_pseudoAncestors_hashEdgeDirty(pseudoancestors, edge_j, TRUE, &conflict, hasharr);
703 
704  if( conflict )
705  continue;
706 
707  for( int k = 0; k < nheads; k++ )
708  {
709  const int edge_k = edges_head[k];
710  const SCIP_Real pathcost = graph->cost[edge_j] + graph->cost[edge_k] + edgecost;
711  const int node_k = graph->head[edges_head[k]];
712 
713  assert(*isPromising);
714 
715  if( node_j == node_k )
716  continue;
717 
718  graph_pseudoAncestors_hashEdgeDirty(pseudoancestors, edge_k, TRUE, &conflict, hasharr);
719 
720  if( conflict )
721  continue;
722 
723  graph_pseudoAncestors_unhashEdge(pseudoancestors, edge_k, hasharr);
724 
725  if( GE(maxsdcost, pathcost) || halfedges_isInSdMst[edge / 2] )
726  {
727  const SCIP_Real sd = extreduce_distDataGetSdDoubleForbiddenSingle(scip, graph, edge, node_j, node_k, distdata);
728 
729  SCIPdebugMessage("%d->%d sd=%f pathcost=%f \n", node_j, node_k, sd, pathcost);
730 
731  if( sd < -0.5 || GT(sd, pathcost) )
732  {
733  SCIPdebugMessage("...not promising, skip edge \n");
734 
735  if( ++nfails > 1 )
736  {
737  *isPromising = FALSE;
738  break;
739  }
740 
741  genstar->replacedge_tail = edge_j;
742  genstar->replacedge_head = edge_k;
743  }
744  }
745  }
746 
747  graph_pseudoAncestors_unhashEdge(pseudoancestors, edge_j, hasharr);
748  }
749 
750  assert(*isPromising == (nfails <= 1));
751 
752  graph_pseudoAncestors_unhashEdge(pseudoancestors, edge, hasharr);
753 
754 #ifndef NDEBUG
755  for( int i = 0; i < hashsize; i++ )
756  {
757  assert(hasharr[i] == 0);
758  }
759 #endif
760 
761  SCIPfreeCleanBufferArray(scip, &hasharr);
762  }
763 }
764 
765 
766 /** initializes */
767 static
769  SCIP* scip, /**< SCIP data structure */
770  const GRAPH* graph, /**< graph data structure */
771  GENSTAR* genstar /**< general star */
772 )
773 {
774  SCIP_CALL( SCIPallocCleanBufferArray(scip, &(genstar->nodes_mark), graph->knots) );
775  SCIP_CALL( SCIPallocBufferArray(scip, &(genstar->tmp_compedges), STP_GENSTAR_MAXDEG) );
776  SCIP_CALL( SCIPallocBufferArray(scip, &(genstar->tmp_extleaves), STP_GENSTAR_MAXDEG - 1) );
777  StpVecReserve(scip, genstar->edges_tail, STP_GENSTAR_MAXENDDEG);
778  StpVecReserve(scip, genstar->edges_head, STP_GENSTAR_MAXENDDEG);
779  StpVecReserve(scip, genstar->edges_all, STP_GENSTAR_MAXDEG);
780  SCIP_CALL( reduce_starInit(scip, STP_GENSTAR_MAXDEG, &(genstar->star)) );
781 
782  return SCIP_OKAY;
783 }
784 
785 
786 /** exits */
787 static
789  SCIP* scip, /**< SCIP data structure */
790  const GRAPH* graph, /**< graph data structure */
791  GENSTAR* genstar /**< general star */
792 )
793 {
794  StpVecFree(scip, genstar->edges_tail);
795  StpVecFree(scip, genstar->edges_head);
796  StpVecFree(scip, genstar->edges_all);
797  reduce_starFree(scip, &(genstar->star));
798  SCIPfreeBufferArray(scip, &(genstar->tmp_compedges));
799  SCIPfreeBufferArray(scip, &(genstar->tmp_extleaves));
800 #ifndef NEBDUG
801  for( int i = 0; i < graph->knots; i++ )
802  assert(genstar->nodes_mark[i] == 0);
803 #endif
804  SCIPfreeCleanBufferArray(scip, &(genstar->nodes_mark));
805 }
806 
807 
808 /** deletes center edges of general stars */
809 static
811  SCIP* scip, /**< SCIP data structure */
812  REDCOST* redcostdata, /**< reduced cost data structures */
813  EXTPERMA* extpermanent, /**< extension data */
814  GRAPH* graph, /**< graph data structure */
815  DISTDATA* distdata, /**< distance data */
816  int* nelims /**< number of eliminations (out) */
817 )
818 {
819  GENSTAR genstar = { NULL, NULL, NULL, NULL, NULL, NULL, NULL, -1, -1, -1 };
820  const int* result = extpermanent->result;
821  int ncands = 0;
822  int npseudoelims = 0;
823 
824  assert(!extpermanent->solIsValid || result);
825 
826  *nelims = 0;
827 
828  SCIPdebugMessage("General-star deletion starts \n");
829 
830  SCIP_CALL( generalStarInit(scip, graph, &genstar) );
831 
832  for( int i = 0; i < graph->edges; i += 2 )
833  {
834  SCIP_Bool isPromising;
835 
836  if( graph_edge_isDeleted(graph, i) )
837  continue;
838 
839  generalStarSetUp(scip, graph, i, &genstar, &isPromising, distdata);
840 
841  if( isPromising )
842  {
843  SCIP_Bool isDeletable;
844  SCIP_CALL( generalStarCheck(scip, graph, redcostdata, &genstar, extpermanent, &isDeletable ) );
845  ncands++;
846  if( isDeletable )
847  {
848  if( extpermanent->solIsValid && (result[i] == CONNECT || result[flipedge(i)] == CONNECT ) )
849  extpermanent->solIsValid = FALSE;
850 
851  if( genstar.replacedge_head != -1 )
852  {
853  npseudoelims++;
854  SCIP_CALL( replaceEdgeByPath(scip, i, &genstar, graph, redcostdata, distdata, extpermanent) );
855 
856  continue;
857  }
858 
859  removeEdge(scip, i, graph, distdata, extpermanent);
860  (*nelims)++;
861  }
862  }
863  }
864 
865  generalStarExit(scip, graph, &genstar);
866 
867  SCIPdebugMessage("number of general star eliminations=%d \n", *nelims);
868  SCIPdebugMessage("number of general star replacements=%d \n", npseudoelims);
869 
870  return SCIP_OKAY;
871 }
872 
873 /** initializes */
874 static inline
876  SCIP* scip, /**< SCIP data structure */
877  const int* result, /**< solution array or NULL */
878  const GRAPH* g, /**< graph data structure */
879  SCIP_Real* offsetp, /**< pointer to store offset */
880  EXTPSEUDO* extpseudo /**< to initialize */
881  )
882 {
883  SCIP_Real* cutoffs;
884  int* nodestouches;
885  const int nnodes = graph_get_nNodes(g);
886 
887  assert(extpseudo);
888 
889  if( result )
890  {
891  STP_Bool* nodeInSol;
892  assert(solstp_isValid(scip, g, result));
893 
894  SCIP_CALL( SCIPallocBufferArray(scip, &nodeInSol, nnodes) );
895  solstp_setVertexFromEdge(g, result, nodeInSol);
896 
897  extpseudo->nodeInSol = nodeInSol;
898  extpseudo->useSolForEq = TRUE;
899  }
900  else
901  {
902  extpseudo->nodeInSol = NULL;
903  extpseudo->useSolForEq = FALSE;
904  }
905 
907  SCIP_CALL( SCIPallocBufferArray(scip, &nodestouches, nnodes) );
908 
909  for( int i = 0; i < nnodes; ++i )
910  nodestouches[i] = 0;
911 
912  extpseudo->cutoffIsPromising = FALSE;
913  extpseudo->cutoffIsComputed = FALSE;
914  extpseudo->node = -1;
915  extpseudo->offsetp = offsetp;
916  extpseudo->nelims_extended = 0;
917  extpseudo->nelims_simple = 0;
918  extpseudo->nodestouches = nodestouches;
919  extpseudo->cutoffs = cutoffs;
920  extpseudo->deletionMode = delete_all;
921 
922  return SCIP_OKAY;
923 }
924 
925 
926 /** frees */
927 static inline
929  SCIP* scip, /**< SCIP data structure */
930  EXTPSEUDO* extpseudo, /**< to initialize */
931  int* nelimsp /**< pointer: number of eliminations (OUT) */
932  )
933 {
934  assert(nelimsp);
935  assert(*nelimsp == 0);
936  assert(extpseudo->nelims_extended >= 0 && extpseudo->nelims_simple >= 0);
937 
938 
939  *nelimsp = extpseudo->nelims_extended + extpseudo->nelims_simple;
940 
941  SCIPfreeBufferArray(scip, &(extpseudo->nodestouches));
942  SCIPfreeBufferArray(scip, &(extpseudo->cutoffs));
943  SCIPfreeBufferArrayNull(scip, &(extpseudo->nodeInSol));
944 }
945 
946 
947 /** initializes new star */
948 static inline
950  SCIP* scip, /**< SCIP data structure */
951  const GRAPH* g, /**< graph data structure */
952  int node, /**< node */
953  STAR* stardata, /**< star */
954  int** compedges, /**< to be allocated */
955  int** extleaves /**< to be allocated */
956 )
957 {
958  const int degree = g->grad[node];
959 
960  reduce_starReset(g, node, stardata);
961 
962  SCIP_CALL( SCIPallocBufferArray(scip, compedges, degree) );
963  SCIP_CALL( SCIPallocBufferArray(scip, extleaves, degree - 1) );
964 
965  return SCIP_OKAY;
966 }
967 
968 
969 /** frees new star */
970 static inline
972  SCIP* scip, /**< SCIP data structure */
973  int** compedges, /**< to be freed */
974  int** extleaves /**< to be freed */
975 )
976 {
977  SCIPfreeBufferArray(scip, extleaves);
978  SCIPfreeBufferArray(scip, compedges);
979 }
980 
981 
982 /** gets next star */
983 static inline
985  const GRAPH* g, /**< graph data structure */
986  STAR* stardata, /**< star */
987  EXTCOMP* extcomp /**< to be filled */
988 )
989 {
990  int nstaredges;
991  int* const compedges = extcomp->compedges;
992  int* const extleaves = extcomp->extleaves;
993  const int* staredges = reduce_starGetNext(stardata, &(nstaredges));
994 
995  extcomp->ncompedges = nstaredges;
996  extcomp->nextleaves = nstaredges - 1;
997  compedges[0] = flipedge(staredges[0]);
998  extcomp->comproot = g->head[staredges[0]];
999 
1000  for( int i = 1; i < nstaredges; i++ )
1001  {
1002  const int outedge = staredges[i];
1003  compedges[i] = outedge;
1004  extleaves[i - 1] = g->head[outedge];
1005  }
1006 
1007  assert(extcomp->ncompedges >= 3);
1008  assert(extcomp->comproot >= 0);
1009 }
1010 
1011 
1012 /** frees new star */
1013 static inline
1015  const STAR* stardata /**< star */
1016 
1017 )
1018 {
1019  return reduce_starAllAreChecked(stardata);
1020 }
1021 
1022 
1023 /** is biased SD extension promising? */
1024 static inline
1026  SCIP* scip, /**< SCIP data structure */
1027  const EXTPERMA* extperma, /**< extension data */
1028  const GRAPH* g /**< graph data structure */
1029 )
1030 {
1031  if( graph_pc_isPc(g) )
1032  {
1033  return FALSE;
1034  }
1035  else
1036  {
1037  SDPROFIT* sdprofit;
1038  double profitsratio;
1039  int nprofits = 0;
1040  const int nnodes = graph_get_nNodes(g);
1041  const int nterms = g->terms;
1042  // todo might also compute proper sd first..and give to routine
1043  SCIP_CALL_ABORT( reduce_sdprofitInit1stOnly(scip, g, g->cost, &sdprofit));
1044 
1045  for( int i = 0; i < nnodes; i++ )
1046  {
1047  if( Is_term(g->term[i]) )
1048  continue;
1049 
1050  if( GT(sdprofit->nodes_bias[i], 0.0) )
1051  {
1052  nprofits++;
1053  }
1054  }
1055 
1056  profitsratio = (double) nprofits / (double) nterms;
1057  SCIPdebugMessage("profitsratio=%f \n", profitsratio);
1058 
1059  reduce_sdprofitFree(scip, &sdprofit);
1060 
1061  if( profitsratio < EXT_PROFIT_MINRATIO )
1062  {
1063  SCIPdebugMessage("biased SD for extension not promising: %f < %f \n", profitsratio, EXT_PROFIT_MINRATIO);
1064 
1065  return FALSE;
1066  }
1067  }
1068 
1069  return TRUE;
1070 }
1071 
1072 /** is node a good candidate for pseudo deletion? */
1073 static inline
1075  const GRAPH* g, /**< graph data structure */
1076  const EXTPERMA* extperma, /**< extension data */
1077  const EXTPSEUDO* extpseudo, /**< pseudo */
1078  int node /**< node */
1079 )
1080 {
1081  const SCIP_Bool pc = graph_pc_isPc(g);
1082  int degree = -1;
1083 
1084  assert(node >= 0);
1085  assert(!g->extended);
1086 
1087  if( pc )
1088  {
1089  if( !g->mark[node] || graph_pc_knotIsFixedTerm(g, node) )
1090  return FALSE;
1091 
1092  if( Is_term(g->term[node]) && !graph_pc_termIsNonLeafTerm(g, node) )
1093  return FALSE;
1094 
1095  degree = graph_pc_realDegree(g, node, FALSE);
1096 
1097  if( Is_term(g->term[node]) && degree != 3 )
1098  return FALSE;
1099 
1100  assert(degree == g->grad[node]); // otherwise the outside loop does not work..
1101  }
1102  else
1103  {
1104  if( Is_term(g->term[node]) )
1105  return FALSE;
1106 
1107  degree = g->grad[node];
1108  }
1109 
1110  assert(degree >= 0);
1111 
1112  if( degree < EXT_PSEUDO_DEGREE_MIN || degree > EXT_PSEUDO_DEGREE_MAX )
1113  return FALSE;
1114 
1115  if( extpseudo->deletionMode != delete_all )
1116  {
1117  SCIP_Bool hasProfit;
1118  assert(extperma->distdata_biased);
1119  assert(extperma->distdata_biased->sdistdata);
1120  assert(extperma->distdata_biased->sdistdata->sdprofit);
1121  assert(!graph_pc_isPcMw(g));
1122 
1123  hasProfit = GT(reduce_sdprofitGetProfit(extperma->distdata_biased->sdistdata->sdprofit, node, -1, -1), 0.0);
1124 
1125  if( extpseudo->deletionMode == delete_profits && !hasProfit )
1126  return FALSE;
1127 
1128  if( extpseudo->deletionMode == delete_nonprofits && hasProfit )
1129  return FALSE;
1130  }
1131 
1132  return TRUE;
1133 }
1134 
1135 
1136 
1137 /** computes cutoffs for pseudo-deletion of given node */
1138 static inline
1140  SCIP* scip, /**< SCIP data structure */
1141  SCIP_Bool checkpromising, /**< check whether promising? */
1142  SCIP_Bool abortDeg3, /**< abort for degree 3? */
1143  DISTDATA* distdata, /**< distance data */
1144  int node, /**< to be deleted */
1145  GRAPH* graph, /**< graph data structure */
1146  EXTPSEUDO* extpseudo /**< data */
1147 )
1148 {
1149  int adjedges[STP_DELPSEUDO_MAXGRAD];
1150  SCIP_Real* cutoffs = extpseudo->cutoffs;
1151  const int* const nodestouches = extpseudo->nodestouches;
1152  int edgecount = 0;
1153  const int degree = graph->grad[node];
1154  const SCIP_Bool isPc = graph_pc_isPc(graph);
1155  const SCIP_Real eps = 2.0 * SCIPepsilon(scip);
1156 
1157  extpseudo->node = node;
1158 
1159  if( abortDeg3 && degree <= 3 )
1160  {
1161  extpseudo->cutoffIsPromising = TRUE;
1162  extpseudo->cutoffIsComputed = FALSE;
1163  return SCIP_OKAY;
1164  }
1165  extpseudo->cutoffIsComputed = TRUE;
1166 
1167  if( isPc && graph_pc_knotIsNonLeafTerm(graph, node) )
1168  {
1169  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
1170  {
1171  const int head = graph->head[e];
1172  if( !graph_pc_knotIsDummyTerm(graph, head) )
1173  adjedges[edgecount++] = e;
1174  }
1175  }
1176  else
1177  {
1178  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
1179  adjedges[edgecount++] = e;
1180  }
1181 
1182  edgecount = 0;
1183  for( int i = 0; i < degree - 1; i++ )
1184  {
1185  const int vert = graph->head[adjedges[i]];
1186  const SCIP_Real edgecost = graph->cost[adjedges[i]];
1187  for( int i2 = i + 1; i2 < degree; i2++ )
1188  {
1189  const int vert2 = graph->head[adjedges[i2]];
1190  const SCIP_Real edgecost2 = graph->cost[adjedges[i2]];
1191  const SCIP_Real newedgecost = edgecost + edgecost2;
1192 
1193  assert(edgecount < STP_DELPSEUDO_MAXNEDGES);
1194 
1195  cutoffs[edgecount] = extreduce_distDataGetSdDouble(scip, graph, vert, vert2, distdata);
1196 
1197  if( SCIPisEQ(scip, newedgecost, cutoffs[edgecount]) && nodestouches[node] == 0 && nodestouches[vert] == 0 && nodestouches[vert2] == 0 )
1198  {
1199  cutoffs[edgecount] = extreduce_distDataGetSdDoubleForbiddenLast(scip, graph, vert, vert2,
1200  adjedges[i2], adjedges[i], distdata);
1201  assert(SCIPisLE(scip, newedgecost, cutoffs[edgecount]) || EQ(cutoffs[edgecount], -1.0));
1202 
1203  if( SCIPisEQ(scip, newedgecost, cutoffs[edgecount]) )
1204  {
1205  cutoffs[edgecount] -= eps;
1206  assert(SCIPisGT(scip, newedgecost, cutoffs[edgecount]));
1207  }
1208  }
1209 
1210  if( LT(cutoffs[edgecount], 0.0) )
1211  {
1212  cutoffs[edgecount] = FARAWAY;
1213  }
1214 
1215  edgecount++;
1216  }
1217  }
1218 
1219  extpseudo->cutoffIsPromising = FALSE;
1220 
1221  if( checkpromising )
1222  {
1223  SCIP_CALL( graph_knot_delPseudoCheckIfPossible(scip, graph, graph->cost, cutoffs, NULL, node, &(extpseudo->cutoffIsPromising)) );
1224  }
1225 
1226  return SCIP_OKAY;
1227 }
1228 
1229 
1230 /** pseudo-deletes single node */
1231 static inline
1233  SCIP* scip, /**< SCIP data structure */
1234  int node, /**< to be deleted */
1235  REDCOST* redcostdata, /**< reduced cost data */
1236  DISTDATA* distdata, /**< distance data */
1237  GRAPH* graph, /**< graph data structure */
1238  EXTPSEUDO* extpseudo, /**< data */
1239  SCIP_Bool* success /**< success? */
1240 )
1241 {
1242  const SCIP_Real* cutoffs = extpseudo->cutoffs;
1243  int* const nodestouches = extpseudo->nodestouches;
1244  SCIP_Real prize = -1.0;
1245  SCIP_Bool rpc3term = FALSE;
1246  const SCIP_Bool isPc = graph_pc_isPc(graph);
1247 
1248  assert(redcostdata);
1249  assert(node == extpseudo->node);
1250 
1251  if( !extpseudo->cutoffIsComputed )
1252  {
1253  SCIP_CALL( pseudodeleteDeleteComputeCutoffs(scip, FALSE, FALSE, distdata, node, graph, extpseudo) );
1254  }
1255 
1256  if( isPc && graph_pc_knotIsNonLeafTerm(graph, node) && graph->grad[node] == 3 )
1257  {
1258  rpc3term = TRUE;
1259  prize = graph->prize[node];
1260  }
1261 
1262  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
1263  nodestouches[graph->head[e]]++;
1264 
1265  /* now try to eliminate... */
1266  SCIP_CALL( graph_knot_delPseudo(scip, graph, graph->cost, cutoffs, NULL, node, redcostdata, success) );
1267 
1268  if( *success )
1269  {
1270  graph->mark[node] = FALSE;
1271 
1272  if( extpseudo->useSolForEq )
1273  {
1274  assert(extpseudo->nodeInSol);
1275 
1276  if( extpseudo->nodeInSol[node] )
1277  extpseudo->useSolForEq = FALSE;
1278  }
1279 
1280  SCIPdebugMessage("deletion successful! \n");
1281 
1282  if( rpc3term )
1283  {
1284  assert(isPc);
1285  assert(extpseudo->offsetp);
1286  assert(GE(prize, 0.0));
1287 
1288  *(extpseudo->offsetp) += prize;
1289  }
1290  }
1291  else
1292  {
1293  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
1294  nodestouches[graph->head[e]]--;
1295  }
1296 
1297  return SCIP_OKAY;
1298 }
1299 
1300 
1301 /** apply pseudo eliminations for marked nodes
1302  * NOTE: bad design, but useful to reuse the SDs... */
1303 static
1305  SCIP* scip, /**< SCIP data structure */
1306  const SCIP_Bool* pseudoDelNodes, /**< node with pseudo deletable nodes */
1307  REDCOST* redcostdata, /**< reduced cost data */
1308  DISTDATA* distdata, /**< distance data */
1309  GRAPH* graph, /**< graph data structure */
1310  EXTPSEUDO* extpseudo /**< data */
1311 )
1312 {
1313  const int nnodes = graph_get_nNodes(graph);
1314 
1315  assert(pseudoDelNodes);
1316  assert(extpseudo->nelims_simple == 0);
1317 
1318  for( int degree = 2; degree <= STP_DELPSEUDO_MAXGRAD; degree++ )
1319  {
1320  for( int k = 0; k < nnodes; ++k )
1321  {
1322  if( pseudoDelNodes[k] && graph->grad[k] == degree )
1323  {
1324  SCIP_Bool success;
1325  assert(!Is_term(graph->term[k]));
1326 
1327  SCIP_CALL( pseudodeleteDeleteComputeCutoffs(scip, FALSE, FALSE, distdata, k, graph, extpseudo) );
1328  SCIP_CALL( pseudodeleteDeleteNode(scip, k, redcostdata, distdata, graph, extpseudo, &success) );
1329 
1330  if( success )
1331  extpseudo->nelims_simple++;
1332  }
1333  }
1334  }
1335 
1336  return SCIP_OKAY;
1337 }
1338 
1339 
1340 /** Extended reduction test for pseudo-eliminating nodes.
1341  * Applies pseudo-elimination if pseudoDelNodes != NULL, or just marks them otherwise */
1342 static
1344  SCIP* scip, /**< SCIP data structure */
1345  const int* result, /**< solution array or NULL */
1346  const SCIP_Bool* pseudoDelNodes, /**< nodes to pseudo-eliminate already */
1347  EXTPERMA* extperma, /**< extension data */
1348  EXTPSEUDO* extpseudo, /**< pseudo-deletion data */
1349  GRAPH* graph /**< graph data structure (in/out) */
1350 )
1351 {
1352  const int nnodes = graph_get_nNodes(graph);
1353  STAR* stardata;
1354  DISTDATA* const distdata_default = extperma->distdata_default;
1355  REDCOST* const redcostdata = extperma->redcostdata;
1356 
1357  assert(graph_isMarked(graph));
1358 
1359  extreduce_distDataRecomputeDirtyPaths(scip, graph, distdata_default);
1360 
1361  if( pseudoDelNodes )
1362  {
1363  SCIP_CALL( pseudodeleteDeleteMarkedNodes(scip, pseudoDelNodes, redcostdata, distdata_default, graph, extpseudo) );
1364  SCIPdebugMessage("number of eliminations by simple pseudo-elimination %d \n", extpseudo->nelims_simple);
1365  }
1366 
1367  SCIP_CALL( reduce_starInit(scip, EXT_PSEUDO_DEGREE_MAX, &stardata) );
1368 
1369  reduce_nodesDeg1(scip, graph);
1370 
1371  for( int degree = EXT_PSEUDO_DEGREE_MIN; degree <= EXT_PSEUDO_DEGREE_MAX; degree++ )
1372  {
1373  /* pseudo-elimination loop */
1374  for( int i = 0; i < nnodes; ++i )
1375  {
1376  SCIP_Bool isReplaced;
1377  SCIP_Bool nodeisDeletable = FALSE;
1378 
1379  if( graph->grad[i] == 1 && !Is_term(graph->term[i]) )
1380  {
1381  graph_knot_del(scip, graph, i, TRUE);
1382  graph->mark[i] = FALSE;
1383  continue;
1384  }
1385 
1386  if( graph->grad[i] != degree )
1387  continue;
1388 
1389  if( pseudodeleteNodeIsPromising(graph, extperma, extpseudo, i) )
1390  {
1391  SCIP_CALL( pseudodeleteDeleteComputeCutoffs(scip, TRUE, TRUE, distdata_default, i, graph, extpseudo) );
1392 
1393  if( extpseudo->cutoffIsPromising )
1394  {
1395  extperma->redcostEqualAllow = (extpseudo->useSolForEq && !extpseudo->nodeInSol[i]);
1396 
1397  if( extperma->useSdBias && degree == 3 )
1398  SCIP_CALL( extreduce_mstbiasedCheck3NodeSimple(scip, graph, i, distdata_default, extperma->distdata_biased, &nodeisDeletable) );
1399 
1400  if( !nodeisDeletable )
1401  SCIP_CALL( extreduce_checkNode(scip, graph, redcostdata, i, stardata, extperma, &nodeisDeletable) );
1402  }
1403  }
1404 
1405  if( !nodeisDeletable )
1406  continue;
1407 
1408  SCIP_CALL( pseudodeleteDeleteNode(scip, i, redcostdata,
1409  // todo extperma->useSdBias ? extperma->distdata_biased :
1410  distdata_default, graph, extpseudo, &isReplaced) );
1411 
1412  if( isReplaced )
1413  extpseudo->nelims_extended++;
1414  }
1415  }
1416 
1417  reduce_starFree(scip, &stardata);
1418  assert(graphmarkIsClean(redcostdata, graph));
1419 
1420  return SCIP_OKAY;
1421 }
1422 
1423 
1424 /** initializes */
1426  SCIP* scip, /**< SCIP data structure */
1427  SCIP_Bool useSd, /**< use special distance? */
1428  enum EXTRED_MODE mode, /**< mode */
1429  GRAPH* graph, /**< graph data structure */
1430  REDCOST* redcostdata, /**< reduced costs data */
1431  EXTPERMA** extpermanent /**< permanent extension data (out) */
1432 )
1433 {
1434  EXTPERMA* extperma;
1435 
1436  assert(scip && graph && redcostdata && extpermanent);
1437  assert(!graph_pc_isPcMw(graph) || !graph->extended);
1438 
1439  graph_mark(graph);
1440  SCIP_CALL( graph_init_dcsr(scip, graph) );
1441  SCIP_CALL( extreduce_extPermaInit(scip, mode, graph, NULL, extpermanent) );
1442  extperma = *extpermanent;
1443 
1444  SCIP_CALL( extreduce_distDataInit(scip, graph, STP_EXT_CLOSENODES_MAXN, useSd, FALSE, &(extperma->distdata_default)) );
1445  extperma->redcostdata = redcostdata;
1446 
1447  return SCIP_OKAY;
1448 }
1449 
1450 
1451 /** frees */
1453  SCIP* scip, /**< SCIP data structure */
1454  GRAPH* graph, /**< graph data structure */
1455  EXTPERMA** extpermanent /**< permanent extension data */
1456 )
1457 {
1458  EXTPERMA* extperma;
1459 
1460  assert(scip && graph && extpermanent);
1461 
1462  extperma = *extpermanent;
1463 
1464  if( extperma->distdata_biased )
1465  extreduce_distDataFree(scip, graph, &(extperma->distdata_biased));
1466 
1467  graph_free_dcsr(scip, graph);
1468  extreduce_distDataFree(scip, graph, &(extperma->distdata_default));
1469  extreduce_extPermaFree(scip, extpermanent);
1470 }
1471 
1472 
1473 
1474 /** Extended reduction test for arcs.
1475  * This method will also set edgedeletable[a] to TRUE if arc 'a' can be deleted, but its anti-parallel arc not. */
1477  SCIP* scip, /**< SCIP data structure */
1478  REDCOST* redcostdata, /**< reduced cost data */
1479  const int* result, /**< solution array or NULL */
1480  GRAPH* graph, /**< graph data structure */
1481  STP_Bool* edgedeletable, /**< edge array to mark which (directed) edge can be removed */
1482  int* nelims /**< number of eliminations */
1483 )
1484 {
1485  const SCIP_Bool useSd = !graph_pc_isPc(graph);
1486  const int nedges = graph_get_nEdges(graph);
1487  DISTDATA* distdata;
1488  EXTPERMA* extpermanent;
1489  SCIP_Bool withSol = (result != NULL);
1490 
1491  assert(scip && redcostdata && edgedeletable);
1492 
1493  *nelims = 0;
1494 
1495  if( SCIPisZero(scip, redcosts_getCutoffTop(redcostdata)) )
1496  return SCIP_OKAY;
1497 
1498  SCIP_CALL( extInit(scip, useSd, graph, NULL, &distdata, &extpermanent) );
1499 
1500  if( useSd )
1501  {
1502  assert(distdata->sdistdata);
1503  SCIP_CALL( reduce_sdRepairSetUp(scip, graph, distdata->sdistdata) );
1504  }
1505 
1506  extpermanent->distdata_default = distdata;
1507  extpermanent->result = result;
1508 
1509  /* main loop */
1510  for( int e = 0; e < nedges; e += 2 )
1511  {
1512  if( extreduce_edgeIsValid(graph, redcostdata, e) )
1513  {
1514  const int erev = e + 1;
1515  extpermanent->redcostEqualAllow = (withSol && result[e] != CONNECT && result[erev] != CONNECT);
1516  assert(flipedge(e) == erev && SCIPisEQ(scip, graph->cost[e], graph->cost[erev]));
1517 
1518  if( !edgedeletable[e] )
1519  {
1520  SCIP_Bool deletable;
1521  SCIP_CALL( extreduce_checkArc(scip, graph, redcostdata, e, extpermanent,
1522  &deletable) );
1523 
1524  if( deletable )
1525  {
1526  if( withSol && result[e] == CONNECT )
1527  withSol = FALSE;
1528 
1529  edgedeletable[e] = TRUE;
1530  }
1531  }
1532 
1533  if( !edgedeletable[erev] )
1534  {
1535  SCIP_Bool erevdeletable = FALSE;
1536 
1537  SCIP_CALL( extreduce_checkArc(scip, graph, redcostdata, erev, extpermanent,
1538  &erevdeletable) );
1539 
1540  if( erevdeletable )
1541  {
1542  if( withSol && result[erev] == CONNECT )
1543  withSol = FALSE;
1544 
1545  edgedeletable[erev] = TRUE;
1546  }
1547  }
1548 
1549  if( edgedeletable[e] && edgedeletable[erev] )
1550  {
1551  assert(edgedeletable[e] && edgedeletable[erev]);
1552 
1553  removeEdge(scip, e, graph, distdata, extpermanent);
1554 
1555  (*nelims)++;
1556  }
1557  }
1558  }
1559 
1560  extFree(scip, graph, &distdata, &extpermanent);
1561 
1562  assert(graphmarkIsClean(redcostdata, graph));
1563 
1564  return SCIP_OKAY;
1565 }
1566 
1567 
1568 /** extended reduction test for edges */
1570  SCIP* scip, /**< SCIP data structure */
1571  EXTPERMA* extperma, /**< extension data */
1572  GRAPH* graph, /**< graph data structure (in/out) */
1573  int* nelims /**< number of eliminations (out) */
1574 )
1575 {
1576  const SCIP_Bool useSd = !graph_pc_isPc(graph);
1577  const int nedges = graph_get_nEdges(graph);
1578  REDCOST* const redcostdata = extperma->redcostdata;
1579  DISTDATA* const distdata = extperma->distdata_default;
1580  SD* const sddata = distdata->sdistdata;
1581  const int* result = extperma->result;
1582  SCIP_Bool withSol;
1583 
1584  assert(scip && redcostdata);
1585  assert(!graph_pc_isMw(graph) && "not supported yet");
1586  assert(redcosts_getRootTop(redcostdata) >= 0 && redcosts_getRootTop(redcostdata) < graph->knots);
1587  assert(graph_isMarked(graph));
1588  assert((result != NULL) == extperma->solIsValid);
1589  assert(!extperma->solIsValid || solstp_isValid(scip, graph, result));
1590 
1591  *nelims = 0;
1592 
1593  if( SCIPisZero(scip, redcosts_getCutoffTop(redcostdata)) )
1594  return SCIP_OKAY;
1595 
1596  SCIPdebugMessage("run extreduce_deleteEdges with depth %d \n", extperma->tree_maxdepth);
1597 
1598  if( useSd )
1599  {
1600  assert(sddata);
1601  SCIP_CALL( reduce_sdRepairSetUp(scip, graph, sddata) );
1602  }
1603 
1604  if( useSd )
1605  {
1606  int npathelims = 0;
1607  SCIP_CALL( reduce_pathreplaceExt(scip, graph, extperma, &npathelims) );
1608 
1609  (*nelims) += npathelims;
1610  }
1611 
1612  withSol = extperma->solIsValid;
1613 
1614  /* main loop */
1615  for( int e = 0; e < nedges; e += 2 )
1616  {
1617  if( extreduce_edgeIsValid(graph, redcostdata, e) )
1618  {
1619  const int erev = e + 1;
1620  SCIP_Bool deletable = TRUE;
1621 
1622  assert(flipedge(e) == erev && SCIPisEQ(scip, graph->cost[e], graph->cost[erev]));
1623 
1624  if( useSd && extperma->mode == extred_fast && reduce_sdgraphEdgeIsInMst(sddata->sdgraph, e) )
1625  continue;
1626 
1627  extperma->redcostEqualAllow = (withSol && result[e] != CONNECT && result[erev] != CONNECT);
1628  SCIP_CALL( extreduce_checkEdge(scip, graph, redcostdata, e, extperma, &deletable) );
1629 
1630  if( deletable )
1631  {
1632  removeEdge(scip, e, graph, distdata, extperma);
1633 
1634  if( withSol && (result[e] == CONNECT || result[erev] == CONNECT ) )
1635  withSol = FALSE;
1636 
1637  (*nelims)++;
1638  }
1639  }
1640  }
1641 
1642  extperma->solIsValid = withSol;
1643 
1644  if( graph_typeIsSpgLike(graph) )
1645  {
1646  int sepanelims = 0;
1647  SCIP_CALL( reduce_termsepaDaWithExperma(scip, graph, extperma, NULL, &sepanelims) );
1648  *nelims += sepanelims;
1649  graph_mark(graph);
1650 
1651  if( sepanelims > 0 && extperma->solIsValid )
1652  extperma->solIsValid = solstp_isUnreduced(scip, graph, result);
1653  }
1654 
1655  if( extperma->mode == extred_full && !graph_pc_isPc(graph) )
1656  {
1657  int ngenstarelims = 0;
1658  SCIP_CALL( generalStarDeleteEdges(scip, redcostdata, extperma, graph, distdata, &ngenstarelims) );
1659  *nelims += ngenstarelims;
1660  }
1661 
1662  assert(graphmarkIsClean(redcostdata, graph));
1663 
1664  return SCIP_OKAY;
1665 }
1666 
1667 /** extended reduction test for pseudo-eliminating nodes */
1669  SCIP* scip, /**< SCIP data structure */
1670  const SCIP_Bool* pseudoDelNodes, /**< nodes to pseudo-eliminate already */
1671  EXTPERMA* extperma, /**< extension data */
1672  GRAPH* graph, /**< graph data structure (in/out) */
1673  SCIP_Real* offsetp, /**< pointer to store offset */
1674  int* nelims /**< number of eliminations (out) */
1675 )
1676 {
1677  EXTPSEUDO extpseudo;
1678  /* NOTE: hacky, needs to be kept because sub-methods do not use solIsValid flag */
1679  const int* result = extperma->solIsValid ? extperma->result : NULL;
1680  SCIP_Bool isExtendedOrg;
1681 
1682  assert(scip && extperma && extperma->redcostdata && graph && nelims);
1683  assert(!extperma->useSdBias);
1684  assert(!extperma->solIsValid || solstp_isValid(scip, graph, result));
1685 
1686  *nelims = 0;
1687 
1688  if( SCIPisZero(scip, redcosts_getCutoffTop(extperma->redcostdata)) )
1689  return SCIP_OKAY;
1690 
1691  SCIPdebugMessage("run extreduce_pseudoDeleteNodes with depth %d \n", extperma->tree_maxdepth);
1692 
1693  isExtendedOrg = graph->extended;
1694  if( graph_pc_isPc(graph) )
1695  {
1696  graph_pc_2orgcheck(scip, graph);
1697  reduce_removeDeg0NonLeafTerms(scip, graph, offsetp);
1698  }
1699  else
1700  {
1701  graph_mark(graph);
1702  }
1703 
1704  SCIP_CALL( pseudodeleteInit(scip, result, graph, offsetp, &extpseudo) );
1705 
1706  if( pseudodeleteBiasedIsPromising(scip, extperma, graph) )
1707  {
1708  assert(!extperma->distdata_biased);
1709  extperma->useSdBias = TRUE;
1710  extpseudo.deletionMode = delete_nonprofits;
1711 
1714  SCIP_CALL( extreduce_extPermaAddMLdistsbiased(scip, extperma) );
1715  }
1716  assert(extpseudo.deletionMode == delete_nonprofits || extpseudo.deletionMode == delete_all);
1717 
1718  /* call actual method */
1719  SCIP_CALL( pseudodeleteExecute(scip, result, NULL, extperma, &extpseudo, graph) );
1720  SCIPdebugMessage("number of eliminations after extended pseudo-elimination %d \n", extpseudo.nelims_extended);
1721 
1722  if( extperma->useSdBias )
1723  {
1724  assert(extperma->distdata_biased);
1725 
1726  extperma->useSdBias = FALSE;
1727  extpseudo.deletionMode = delete_profits;
1728  SCIP_CALL( pseudodeleteExecute(scip, result, pseudoDelNodes, extperma, &extpseudo, graph) );
1729 
1730  SCIPdebugMessage("number of eliminations after extended pseudo-elimination on profits %d \n", extpseudo.nelims_extended);
1731  }
1732 
1733  extperma->solIsValid = extpseudo.useSolForEq;
1734 
1735  /* NOTE: also sets "nelims" pointer*/
1736  pseudodeleteExit(scip, &extpseudo, nelims);
1737 
1738  /* todo otherwise (I015) we get isolated vertices...not sure whether this is a bug or normal behavior */
1739  if( *nelims > 0 )
1740  SCIP_CALL( reduce_unconnected(scip, graph));
1741 
1742  if( graph_pc_isPc(graph) && isExtendedOrg != graph->extended )
1743  graph_pc_2trans(scip, graph);
1744 
1745  return SCIP_OKAY;
1746 }
1747 
1748 
1749 /** deletes center edges of general stars */
1751  SCIP* scip, /**< SCIP data structure */
1752  REDCOST* redcostdata, /**< reduced cost data */
1753  const int* result, /**< solution array or NULL */
1754  GRAPH* graph, /**< graph data structure (in/out) */
1755  STP_Bool* edgedeletable, /**< edge array to mark which (directed) edge can be removed (in/out) */
1756  int* nelims /**< number of eliminations (out) */
1757 )
1758 {
1759  const SCIP_Bool useSd = !graph_pc_isPc(graph);
1760  DISTDATA* distdata;
1761  EXTPERMA* extpermanent;
1762 
1763  assert(scip && redcostdata);
1764  assert(redcosts_getRootTop(redcostdata) >= 0 && redcosts_getRootTop(redcostdata) < graph->knots);
1765 
1766  *nelims = 0;
1767 
1768  if( SCIPisZero(scip, redcosts_getCutoffTop(redcostdata)) )
1769  return SCIP_OKAY;
1770 
1771  SCIP_CALL( extInit(scip, useSd, graph, edgedeletable, &distdata, &extpermanent) );
1772 
1773  if( useSd )
1774  {
1775  assert(distdata->sdistdata);
1776  SCIP_CALL( reduce_sdRepairSetUp(scip, graph, distdata->sdistdata) );
1777  }
1778 
1779  extpermanent->distdata_default = distdata;
1780  extpermanent->result = result;
1781 
1782  SCIP_CALL( generalStarDeleteEdges(scip, redcostdata, extpermanent, graph, distdata, nelims) );
1783 
1784  extFree(scip, graph, &distdata, &extpermanent);
1785 
1786  assert(graphmarkIsClean(redcostdata, graph));
1787 
1788  return SCIP_OKAY;
1789 
1790 }
1791 
1792 
1793 /** check (directed) arc */
1795  SCIP* scip, /**< SCIP data structure */
1796  const GRAPH* graph, /**< graph data structure */
1797  REDCOST* redcostdata, /**< reduced cost data structures */
1798  int edge, /**< edge to be checked */
1799  EXTPERMA* extpermanent, /**< extension data */
1800  SCIP_Bool* edgeIsDeletable /**< is edge deletable? */
1801 )
1802 {
1803  const SCIP_Bool* isterm = extpermanent->isterm;
1804  const int root = redcosts_getRootTop(redcostdata);
1805  SCIP_Real* const redcost = redcosts_getEdgeCostsTop(redcostdata);
1806  const SCIP_Real* rootdist = redcosts_getRootToNodeDistTop(redcostdata);
1807  const PATH* nodeToTermpaths = redcosts_getNodeToTermsPathsTop(redcostdata);
1808  const SCIP_Real cutoff = redcosts_getCutoffTop(redcostdata);
1809  const int head = graph->head[edge];
1810  const int tail = graph->tail[edge];
1811  const int edge_anti = flipedge(edge);
1812  const SCIP_Real edgebound = redcost[edge] + rootdist[tail] + nodeToTermpaths[head].dist;
1813 
1814  assert(scip && graph && redcost && rootdist && nodeToTermpaths);
1815  assert(edge >= 0 && edge < graph->edges);
1816  assert(!graph_pc_isPcMw(graph) || !graph->extended);
1817  assert(graph->mark[tail] && graph->mark[head]);
1818  assert(graph_isMarked(graph));
1819  assert(extreduce_extPermaIsClean(graph, extpermanent));
1820 
1821  /* trivial rule-out? */
1822  if( SCIPisGT(scip, edgebound, cutoff) || (extpermanent->redcostEqualAllow && SCIPisEQ(scip, edgebound, cutoff)) || head == root )
1823  {
1824  *edgeIsDeletable = TRUE;
1825  return SCIP_OKAY;
1826  }
1827 
1828  *edgeIsDeletable = FALSE;
1829 
1830  /* can we extend from head of 'edge'? */
1831  if( extLeafIsExtendable(graph, isterm, head) )
1832  {
1833  const SCIP_Real restoreCost = redcost[edge_anti];
1834  int comphead = graph->head[edge];
1835  int compedge = edge;
1836  EXTCOMP extcomp = { .compedges = &compedge, .extleaves = &(comphead),
1837  .nextleaves = 1, .ncompedges = 1, .comproot = graph->tail[edge],
1838  .genstar_centeredge = -1,
1839  .allowReversion = FALSE };
1840 
1841  redcost[edge_anti] += 2.0 * cutoff;
1842 
1843  SCIP_CALL( extreduce_checkComponent(scip, graph, redcostdata, &extcomp, extpermanent, edgeIsDeletable) );
1844 
1845  redcost[edge_anti] = restoreCost;
1846  }
1847 
1848 
1849  return SCIP_OKAY;
1850 }
1851 
1852 
1853 /** check edge */
1855  SCIP* scip, /**< SCIP data structure */
1856  const GRAPH* graph, /**< graph data structure */
1857  const REDCOST* redcostdata, /**< reduced cost data structures */
1858  int edge, /**< edge to be checked */
1859  EXTPERMA* extpermanent, /**< extension data */
1860  SCIP_Bool* edgeIsDeletable /**< is edge deletable? */
1861 )
1862 {
1863  const SCIP_Bool* const isterm = extpermanent->isterm;
1864 
1865  assert(scip && graph && edgeIsDeletable && extpermanent);
1866  assert(edge >= 0 && edge < graph->edges);
1867  assert(!graph_pc_isPcMw(graph) || !graph->extended);
1868  assert(graph_isMarked(graph));
1869  assert(extreduce_extPermaIsClean(graph, extpermanent));
1870 
1871  *edgeIsDeletable = FALSE;
1872 
1873  /* is any extension possible? */
1874  if( extLeafIsExtendable(graph, isterm, graph->tail[edge]) || extLeafIsExtendable(graph, isterm, graph->head[edge]) )
1875  {
1876  int comphead = graph->head[edge];
1877  int compedge = edge;
1878  EXTCOMP extcomp = { .compedges = &compedge, .extleaves = &(comphead),
1879  .nextleaves = 1, .ncompedges = 1, .genstar_centeredge = -1,
1880  .comproot = graph->tail[edge], .allowReversion = TRUE };
1881 
1882  SCIP_CALL( extreduce_checkComponent(scip, graph, redcostdata, &extcomp, extpermanent, edgeIsDeletable) );
1883  }
1884 
1885  return SCIP_OKAY;
1886 }
1887 
1888 
1889 /** check node for possible */
1891  SCIP* scip, /**< SCIP data structure */
1892  const GRAPH* graph, /**< graph data structure */
1893  const REDCOST* redcostdata, /**< reduced cost data structures */
1894  int node, /**< the node */
1895  STAR* stardata, /**< star */
1896  EXTPERMA* extpermanent, /**< extension data */
1897  SCIP_Bool* isPseudoDeletable /**< is node pseudo-deletable? */
1898 )
1899 {
1900  int* compedges;
1901  int* extleaves;
1902 
1903  assert(scip && graph && redcostdata && extpermanent && isPseudoDeletable);
1904  assert(node >= 0 && node < graph->knots);
1905 
1906  *isPseudoDeletable = TRUE;
1907 
1908  SCIP_CALL( pseudodeleteInitStar(scip, graph, node, stardata, &compedges, &extleaves) );
1909 
1910  if( graph->grad[node] == 3 )
1911  extpermanent->tree_maxdepth++;
1912 
1913  /* check all stars of degree >= 3, as long as they can be ruled-out */
1914  while ( *isPseudoDeletable )
1915  {
1916  EXTCOMP extcomp = { .compedges = compedges, .extleaves = extleaves,
1917  .nextleaves = -1, .ncompedges = -1, .genstar_centeredge = -1,
1918  .comproot = -1, .allowReversion = TRUE };
1919 
1920  pseudodeleteGetNextStar(graph, stardata, &extcomp);
1921 
1922  *isPseudoDeletable = FALSE;
1923  SCIP_CALL( extreduce_checkComponent(scip, graph, redcostdata, &extcomp, extpermanent, isPseudoDeletable) );
1924 
1925  if( !(*isPseudoDeletable) && extcomp.ncompedges == 3 && graph->grad[node] <= 4 )
1926  {
1927  const SCIP_Bool allowEquality = (graph->grad[node] == 3);
1928  SCIP_CALL( extreduce_spgCheck3ComponentSimple(scip, graph, node, &extcomp, allowEquality,
1929  extpermanent->distdata_default, isPseudoDeletable) );
1930  }
1931 
1932  if( pseudodeleteAllStarsChecked(stardata) )
1933  break;
1934  }
1935 
1936  if( graph->grad[node] == 3 )
1937  extpermanent->tree_maxdepth--;
1938 
1939  pseudodeleteFreeStar(scip, &compedges, &extleaves);
1940 
1941  return SCIP_OKAY;
1942 }
1943 
1944 
1945 /** deletes an edge and makes corresponding adaptations */
1947  SCIP* scip, /**< SCIP */
1948  int edge, /**< edge to delete */
1949  GRAPH* graph, /**< graph data structure (in/out) */
1950  DISTDATA* distdata, /**< distance data (in/out) */
1951  EXTPERMA* extpermanent /**< (in/out) can be NULL */
1952 )
1953 {
1954  removeEdge(scip, edge, graph, distdata, extpermanent);
1955 }
1956 
1957 
1958 /** is the edge valid? */
1960  const GRAPH* graph, /**< graph data structure */
1961  const REDCOST* redcostdata, /**< reduced cost data */
1962  int e /**< edge to be checked */
1963 )
1964 {
1965  assert(graph && redcostdata);
1966  assert(graph_edge_isInRange(graph, e));
1967 
1968  if( EAT_FREE == graph->oeat[e] )
1969  {
1970  return FALSE;
1971  }
1972  else if( graph_pc_isPcMw(graph) )
1973  {
1974  const int tail = graph->tail[e];
1975  const int head = graph->head[e];
1976 
1977  if( (!graph->mark[tail] || !graph->mark[head]) )
1978  {
1979  assert(graph_pc_knotIsDummyTerm(graph, tail) || graph_pc_knotIsDummyTerm(graph, head));
1980 
1981  return FALSE;
1982  }
1983 
1984  assert(!graph_pc_knotIsDummyTerm(graph, tail));
1985  assert(!graph_pc_knotIsDummyTerm(graph, head));
1986  }
1987 
1988  if( EQ(0.0, redcosts_getEdgeCostsTop(redcostdata)[e]) && EQ(0.0, redcosts_getEdgeCostsTop(redcostdata)[flipedge(e)]) )
1989  {
1990  return FALSE;
1991  }
1992 
1993  return TRUE;
1994 }
1995 
1996 
1997 /** recompute costs and reduced costs for current tree */
1999  SCIP* scip, /**< SCIP */
2000  const GRAPH* graph, /**< graph data structure */
2001  EXTDATA* extdata /**< extension data */
2002 )
2003 {
2004 #ifndef NDEBUG
2005  const int tree_nDelUpArcs = extdata->tree_nDelUpArcs;
2006 #endif
2007  REDDATA* const reddata = extdata->reddata;
2008  const STP_Bool* const edgedeleted = reddata->edgedeleted;
2009  SCIP_Real tree_cost = 0.0;
2010  const SCIP_Real* const cost = graph->cost;
2011  const int* const tree_edges = extdata->tree_edges;
2012  const int tree_nedges = extdata->tree_nedges;
2013  const SCIP_Bool isPc = (graph->prize != NULL);
2014 
2015  extdata->tree_nDelUpArcs = 0;
2016 
2017  assert(!extreduce_treeIsFlawed(scip, graph, extdata));
2018  assert(isPc == graph_pc_isPc(graph));
2019 
2020  for( int i = 0; i < tree_nedges; i++ )
2021  {
2022  const int edge = tree_edges[i];
2023  const SCIP_Bool edgeIsDeleted = (edgedeleted && edgedeleted[edge]);
2024 
2025  assert(edge >= 0 && edge < graph->edges);
2026 
2027  tree_cost += cost[edge];
2028 
2029  if( edgeIsDeleted )
2030  {
2031  extdata->tree_nDelUpArcs++;
2032  }
2033  }
2034 
2035  assert(SCIPisEQ(scip, tree_cost, extdata->tree_cost));
2036  assert(tree_nDelUpArcs == extdata->tree_nDelUpArcs);
2037 
2038  extreduce_redcostTreeRecompute(scip, graph, extdata);
2039 
2040  extdata->tree_cost = tree_cost;
2041 
2042  if( isPc )
2043  {
2044  const int* const innerNodes = extdata->tree_innerNodes;
2045  const SCIP_Real* const prizes = graph->prize;
2046  SCIP_Real tree_innerPrize = 0.0;
2047  const int ninnnerNodes = extdata->tree_ninnerNodes;
2048 
2049  for( int i = 0; i < ninnnerNodes; ++i )
2050  {
2051  const int node = innerNodes[i];
2052  tree_innerPrize += prizes[node];
2053  }
2054 
2055  assert(EQ(tree_innerPrize, extdata->pcdata->tree_innerPrize));
2056 
2057  extdata->pcdata->tree_innerPrize = tree_innerPrize;
2058  }
2059 }
2060 
2061 /** get maximum allowed stack size */
2063 {
2064  return STP_EXT_MAXSTACKSIZE;
2065 }
2066 
2067 
2068 /** get maximum allowed number of components */
2070  const GRAPH* graph /**< graph data structure */
2071 )
2072 {
2073  assert(graph);
2074 
2075  return STP_EXT_MAXNCOMPS;
2076 }
2077 
2078 
2079 /** get maximum allowed depth for extended tree in given graph */
2081  const GRAPH* graph, /**< graph data structure */
2082  const EXTPERMA* extpermanent /**< extension data */
2083 )
2084 {
2085  int nedges;
2086  int maxdepth;
2087 
2088  graph_get_nVET(graph, NULL, &nedges, NULL);
2089 
2090  if( nedges > STP_EXT_DEPTH_MAXNEDGES )
2091  {
2092  maxdepth = STP_EXT_MINDFSDEPTH;
2093  }
2094  else if( nedges > STP_EXT_DEPTH_MIDNEDGES )
2095  {
2096  maxdepth = STP_EXT_MIDDFSDEPTH;
2097  }
2098  else
2099  {
2100  assert(nedges <= STP_EXT_DEPTH_MIDNEDGES);
2101  maxdepth = STP_EXT_MAXDFSDEPTH;
2102  }
2103 
2104  if( extpermanent->mode == extred_fast )
2105  {
2106  maxdepth--;
2107  }
2108 
2109  assert(maxdepth > 0);
2110 
2111  return maxdepth;
2112 }
void reduce_removeDeg0NonLeafTerms(SCIP *, GRAPH *, SCIP_Real *)
#define STP_Vectype(type)
Definition: stpvector.h:44
#define STP_EXT_MINDFSDEPTH
Definition: extreducedefs.h:41
SCIP_RETCODE reduce_sdprofitInit1stOnly(SCIP *, const GRAPH *, const SCIP_Real *, SDPROFIT **)
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_pseudoAncestors_unhashEdge(const PSEUDOANS *, int, int *)
SCIP_RETCODE graph_edge_delPseudoPath(SCIP *, GRAPH *, int, int, int, SCIP_Real *)
static volatile int nterms
Definition: interrupt.c:38
const STP_Bool *const edgedeleted
#define STP_DELPSEUDO_MAXGRAD
Definition: graphdefs.h:79
int graph_pc_realDegree(const GRAPH *, int, SCIP_Bool)
#define StpVecGetSize(vec)
Definition: stpvector.h:139
#define StpVecClear(vec)
Definition: stpvector.h:134
SCIP_Bool graph_pc_isMw(const GRAPH *)
void reduce_nodesDeg1(SCIP *, GRAPH *)
static void pseudodeleteFreeStar(SCIP *scip, int **compedges, int **extleaves)
SCIP_RETCODE extreduce_extPermaAddMLdistsbiased(SCIP *, EXTPERMA *)
int *RESTRICT head
Definition: graphdefs.h:224
enum EXTRED_MODE mode
SCIP_RETCODE extreduce_pseudoDeleteNodes(SCIP *scip, const SCIP_Bool *pseudoDelNodes, EXTPERMA *extperma, GRAPH *graph, SCIP_Real *offsetp, int *nelims)
int source
Definition: graphdefs.h:195
SCIP_Bool extreduce_treeIsFlawed(SCIP *, const GRAPH *, const EXTDATA *)
void extreduce_exit(SCIP *scip, GRAPH *graph, EXTPERMA **extpermanent)
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Real extreduce_distDataGetSdDouble(SCIP *, const GRAPH *, int, int, DISTDATA *)
static SCIP_RETCODE generalStarInit(SCIP *scip, const GRAPH *graph, GENSTAR *genstar)
static SCIP_Bool isPseudoDeletable(SCIP *scip, const GRAPH *g, const GRAPH *auxg, const SCIP_Real *ecost, const int *edges, int degree)
Definition: reduce_sd.c:1033
#define STP_DELPSEUDO_MAXNEDGES
Definition: graphdefs.h:80
SCIP_Bool reduce_starAllAreChecked(const STAR *)
Definition: reduce_util.c:2002
int terms
Definition: graphdefs.h:192
void extreduce_distDataFree(SCIP *, const GRAPH *, DISTDATA **)
SCIP_Real redcosts_getCutoffTop(const REDCOST *redcostdata)
Definition: redcosts.c:300
SCIP_Real tree_innerPrize
#define STP_EXT_DEPTH_MAXNEDGES
Definition: extreducedefs.h:45
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
void graph_free_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1807
includes methods for Steiner tree problem solutions
int graph_pseudoAncestorsGetHashArraySize(const PSEUDOANS *)
SCIP_RETCODE extreduce_deleteGeneralStars(SCIP *scip, REDCOST *redcostdata, const int *result, GRAPH *graph, STP_Bool *edgedeletable, int *nelims)
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
#define STP_GENSTAR_MAXDEG
void graph_dcsr_deleteEdgeBi(SCIP *, DCSR *, int)
Definition: graph_util.c:1894
#define EAT_FREE
Definition: graphdefs.h:57
void extreduce_distDataRecomputeDirtyPaths(SCIP *, const GRAPH *, DISTDATA *)
#define FALSE
Definition: def.h:87
SCIP_Bool solstp_isUnreduced(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1596
#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
#define STP_EXT_MAXSTACKSIZE
Definition: extreducedefs.h:36
static void generalStarCheckInit(SCIP *scip, const GRAPH *g, GENSTAR *genstar)
#define STP_EXT_MAXDFSDEPTH
Definition: extreducedefs.h:38
static SCIP_RETCODE pseudodeleteDeleteMarkedNodes(SCIP *scip, const SCIP_Bool *pseudoDelNodes, REDCOST *redcostdata, DISTDATA *distdata, GRAPH *graph, EXTPSEUDO *extpseudo)
int *const tree_edges
SCIP_RETCODE extreduce_deleteEdges(SCIP *scip, EXTPERMA *extperma, GRAPH *graph, int *nelims)
SCIP_RETCODE extreduce_checkArc(SCIP *scip, const GRAPH *graph, REDCOST *redcostdata, int edge, EXTPERMA *extpermanent, SCIP_Bool *edgeIsDeletable)
#define EAT_LAST
Definition: graphdefs.h:58
#define StpVecReserve(scip, vec, _size_)
Definition: stpvector.h:182
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
void graph_pseudoAncestors_hashEdge(const PSEUDOANS *, int, int *)
static SCIP_RETCODE pseudodeleteInit(SCIP *scip, const int *result, const GRAPH *g, SCIP_Real *offsetp, EXTPSEUDO *extpseudo)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE reduce_starInit(SCIP *, int, STAR **)
Definition: reduce_util.c:1725
EXTPSEUDO_MODE
SCIP_RETCODE extreduce_checkEdge(SCIP *scip, const GRAPH *graph, const REDCOST *redcostdata, int edge, EXTPERMA *extpermanent, SCIP_Bool *edgeIsDeletable)
REDDATA *const reddata
#define STP_EXT_MAXNCOMPS
Definition: extreducedefs.h:37
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1721
int extreduce_getMaxTreeDepth(const GRAPH *graph, const EXTPERMA *extpermanent)
real eps
int *RESTRICT mark
Definition: graphdefs.h:198
#define STP_EXT_CLOSENODES_MAXN
Definition: extreducedefs.h:35
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
int redcosts_getRootTop(const REDCOST *redcostdata)
Definition: redcosts.c:347
SCIP_RETCODE extreduce_spgCheck3ComponentSimple(SCIP *, const GRAPH *, int, const EXTCOMP *, SCIP_Bool, DISTDATA *, SCIP_Bool *)
void reduce_impliedNodesRepair(SCIP *, const GRAPH *, int, int, STP_Vectype(int) *)
Definition: reduce_util.c:962
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
SCIP_RETCODE extreduce_init(SCIP *scip, SCIP_Bool useSd, enum EXTRED_MODE mode, GRAPH *graph, REDCOST *redcostdata, EXTPERMA **extpermanent)
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
SCIP_RETCODE extreduce_checkComponent(SCIP *, const GRAPH *, const REDCOST *, EXTCOMP *, EXTPERMA *, SCIP_Bool *)
SCIP_RETCODE extreduce_deleteArcs(SCIP *scip, REDCOST *redcostdata, const int *result, GRAPH *graph, STP_Bool *edgedeletable, int *nelims)
#define GE(a, b)
Definition: portab.h:85
static SCIP_RETCODE generalStarCheck(SCIP *scip, const GRAPH *graph, const REDCOST *redcostdata, GENSTAR *genstar, EXTPERMA *extpermanent, SCIP_Bool *isDeletable)
#define GENSTAR_NODE_OTHER
void graph_pc_2trans(SCIP *, GRAPH *)
SCIP_Bool extended
Definition: graphdefs.h:267
SCIP_Real extreduce_distDataGetSdDoubleForbiddenLast(SCIP *, const GRAPH *, int, int, int, int, DISTDATA *)
SCIP_RETCODE extreduce_extPermaInit(SCIP *, enum EXTRED_MODE, const GRAPH *, STP_Bool *, EXTPERMA **)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
void reduce_starFree(SCIP *, STAR **)
Definition: reduce_util.c:1758
PSEUDOANS * pseudoancestors
Definition: graphdefs.h:236
SCIP_Bool extreduce_edgeIsValid(const GRAPH *graph, const REDCOST *redcostdata, int e)
int *const tree_innerNodes
SCIP_Real * redcosts_getEdgeCostsTop(const REDCOST *redcostdata)
Definition: redcosts.c:202
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
static SCIP_RETCODE pseudodeleteDeleteComputeCutoffs(SCIP *scip, SCIP_Bool checkpromising, SCIP_Bool abortDeg3, DISTDATA *distdata, int node, GRAPH *graph, EXTPSEUDO *extpseudo)
SCIP_Real dist
Definition: graphdefs.h:286
enum EXTPSEUDO_MODE deletionMode
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE graph_knot_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, REDCOST *, SCIP_Bool *)
#define EXT_PSEUDO_DEGREE_MIN
#define EQ(a, b)
Definition: portab.h:79
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_node.c:111
void reduce_sdprofitFree(SCIP *, SDPROFIT **)
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Bool hasPathReplacement
Definition: extreducedefs.h:96
static void generalStarSetUp(SCIP *scip, const GRAPH *graph, int edge, GENSTAR *genstar, SCIP_Bool *isPromising, DISTDATA *distdata)
SCIP_RETCODE graph_knot_delPseudoCheckIfPossible(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, SCIP_Bool *)
static SCIP_RETCODE pseudodeleteDeleteNode(SCIP *scip, int node, REDCOST *redcostdata, DISTDATA *distdata, GRAPH *graph, EXTPSEUDO *extpseudo, SCIP_Bool *success)
void extreduce_treeRecompCosts(SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
#define LT(a, b)
Definition: portab.h:81
static void generalStarCheckGetNextStar(const GRAPH *g, GENSTAR *genstar, EXTCOMP *extcomp, SCIP_Bool *allVisited)
void graph_edge_delFull(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:418
SCIP_Real reduce_sdgraphGetMaxCost(const SDGRAPH *)
void reduce_starResetWithEdges(const GRAPH *, const STP_Vectype(int), STAR *)
unsigned char STP_Bool
Definition: portab.h:34
static void removeEdge(SCIP *scip, int edge, GRAPH *graph, DISTDATA *distdata, EXTPERMA *extpermanent)
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
Definition: reducedefs.h:178
void extreduce_extPermaFree(SCIP *, EXTPERMA **)
const int * reduce_starGetNext(STAR *, int *)
Definition: reduce_util.c:1863
SCIP_Bool graph_valid_dcsr(const GRAPH *, SCIP_Bool verbose)
Definition: graph_util.c:1919
SCIP_RETCODE reduce_termsepaDaWithExperma(SCIP *, GRAPH *, EXTPERMA *, SCIP_Bool *, int *)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
void extreduce_distDataDeleteEdge(SCIP *, const GRAPH *, int, DISTDATA *)
SCIP_RETCODE reduce_sdRepair(SCIP *, int, SCIP_Bool, GRAPH *, SD *)
static SCIP_RETCODE pseudodeleteExecute(SCIP *scip, const int *result, const SCIP_Bool *pseudoDelNodes, EXTPERMA *extperma, EXTPSEUDO *extpseudo, GRAPH *graph)
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool graph_edge_isDeleted(const GRAPH *, int)
Definition: graph_stats.c:121
static SCIP_RETCODE generalStarDeleteEdges(SCIP *scip, REDCOST *redcostdata, EXTPERMA *extpermanent, GRAPH *graph, DISTDATA *distdata, int *nelims)
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
int *RESTRICT tail
Definition: graphdefs.h:223
static SCIP_RETCODE pseudodeleteInitStar(SCIP *scip, const GRAPH *g, int node, STAR *stardata, int **compedges, int **extleaves)
SCIP_Bool extreduce_distCloseNodesAreValid(SCIP *, const GRAPH *, const DISTDATA *)
PATH * redcosts_getNodeToTermsPathsTop(const REDCOST *redcostdata)
Definition: redcosts.c:253
#define flipedge(edge)
Definition: graphdefs.h:84
SCIP_RETCODE extreduce_checkNode(SCIP *scip, const GRAPH *graph, const REDCOST *redcostdata, int node, STAR *stardata, EXTPERMA *extpermanent, SCIP_Bool *isPseudoDeletable)
#define STP_GENSTAR_MAXENDDEG
void reduce_starReset(const GRAPH *, int, STAR *)
Definition: reduce_util.c:1781
#define GENSTAR_NODE_HEAD
static void extFree(SCIP *scip, GRAPH *graph, DISTDATA **distdata, EXTPERMA **extpermanent)
int *RESTRICT term
Definition: graphdefs.h:196
PCDATA *const pcdata
static SCIP_RETCODE extInit(SCIP *scip, SCIP_Bool useSd, GRAPH *graph, STP_Bool *edgedeletable, DISTDATA **distdata, EXTPERMA **extpermanent)
SCIP_Bool extreduce_extPermaIsClean(const GRAPH *, const EXTPERMA *)
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
void extreduce_edgeRemove(SCIP *scip, int edge, GRAPH *graph, DISTDATA *distdata, EXTPERMA *extpermanent)
SCIP_Bool reduce_sdgraphEdgeIsInMst(const SDGRAPH *, int)
int extreduce_getMaxStackSize(void)
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
void extreduce_redcostTreeRecompute(SCIP *, const GRAPH *, EXTDATA *)
SCIP_Real extreduce_distDataGetSdDoubleForbiddenSingle(SCIP *, const GRAPH *, int, int, int, DISTDATA *)
#define EXT_PROFIT_MINRATIO
#define GENSTAR_NODE_TAIL
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE extreduce_distDataInit(SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
void graph_pc_2orgcheck(SCIP *, GRAPH *)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Real *RESTRICT nodes_bias
Definition: reducedefs.h:137
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
static SCIP_Bool pseudodeleteBiasedIsPromising(SCIP *scip, const EXTPERMA *extperma, const GRAPH *g)
SCIP_RETCODE reduce_pathreplaceExt(SCIP *, GRAPH *, EXTPERMA *, int *)
Definition: reduce_path.c:1080
static SCIP_Bool graphmarkIsClean(const REDCOST *redcostdata, const GRAPH *graph)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
EXTRED_MODE
Definition: reducedefs.h:71
#define STP_EXT_MIDDFSDEPTH
Definition: extreducedefs.h:40
#define SCIP_Real
Definition: def.h:177
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
void graph_pseudoAncestors_hashEdgeDirty(const PSEUDOANS *, int, SCIP_Bool, SCIP_Bool *, int *)
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_Real * redcosts_getRootToNodeDistTop(const REDCOST *redcostdata)
Definition: redcosts.c:228
static SCIP_RETCODE replaceEdgeByPath(SCIP *scip, int edge, const GENSTAR *genstar, GRAPH *graph, REDCOST *redcostdata, DISTDATA *distdata, EXTPERMA *extpermanent)
static void generalStarExit(SCIP *scip, const GRAPH *graph, GENSTAR *genstar)
static void pseudodeleteExit(SCIP *scip, EXTPSEUDO *extpseudo, int *nelimsp)
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void solstp_setVertexFromEdge(const GRAPH *g, const int *result, STP_Bool *solnode)
Definition: solstp.c:2078
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
static void generalStarCheckExit(SCIP *scip, const GRAPH *g, GENSTAR *genstar)
SCIP_RETCODE extreduce_mstbiasedCheck3NodeSimple(SCIP *, const GRAPH *, int, DISTDATA *, DISTDATA *, SCIP_Bool *)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static void pseudodeleteGetNextStar(const GRAPH *g, STAR *stardata, EXTCOMP *extcomp)
struct extension_pseudo_deletion EXTPSEUDO
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
DCSR * dcsr_storage
Definition: graphdefs.h:271
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
static SCIP_Bool pseudodeleteAllStarsChecked(const STAR *stardata)
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_RETCODE reduce_sdRepairSetUp(SCIP *, const GRAPH *, SD *)
const STP_Bool * reduce_sdgraphGetMstHalfMark(const SDGRAPH *)
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
int extreduce_getMaxStackNcomponents(const GRAPH *graph)
#define GENSTAR_NODE_COMBI
static SCIP_Bool pseudodeleteNodeIsPromising(const GRAPH *g, const EXTPERMA *extperma, const EXTPSEUDO *extpseudo, int node)
#define EXT_PSEUDO_DEGREE_MAX
SCIP_Real tree_cost
struct general_star GENSTAR
#define STP_EXT_DEPTH_MIDNEDGES
Definition: extreducedefs.h:44
SCIP_Bool reduce_impliedNodesIsValid(const GRAPH *, const STP_Vectype(int) *)
Definition: reduce_util.c:996
static SCIP_Bool extLeafIsExtendable(const GRAPH *graph, const SCIP_Bool *isterm, int leaf)