Scippy

SCIP

Solving Constraint Integer Programs

reduce_sdcomp.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_sdcomp.c
17  * @brief special distance (bottleneck distance) component reduction methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file encompasses various special distance (aka bottleneck distance) based component reduction methods
21  * for Steiner problems.
22  *
23  * A list of all interface methods can be found in reduce.h.
24  *
25  *
26  */
27 
28 //#define SCIP_DEBUG
29 
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <assert.h>
33 #include "graph.h"
34 #include "reduce.h"
35 #include "scip/scip.h"
36 #include "portab.h"
37 
38 #define STP_BDK_WITH_EDGEREPLACINGS FALSE
39 #define STP_BDKIMP_MAXDEGREE 6
40 #define STP_BDKIMP_MAXNEDGES 15
41 
42 
43 /** BD_k storage */
45 {
46  SD* sdistance; /**< special distance storage */
47  STAR* star; /**< star structure for neighborhood of node */
48  GRAPH* cliquegraph; /**< complete graph on adjacent vertices
49  NOTE: ->mark is used to see which vertices are curently used! */
50  PATH* clique_mst; /**< MST on cliquegraph */
51  int* node_outedges; /**< for node: outgoing edges (size STP_BDKIMP_MAXNEDGES) */
52  int* node_neighbors; /**< for node: adjacent vertices (size STP_BDKIMP_MAXDEGREE) */
53  SCIP_Real* star_mstsds; /**< SDs for star (size STP_BDKIMP_MAXDEGREE) */
54  const int* star_outedges; /**< for star: outgoing edges NOTE: non-owned! */
55  int* star_outedges_pos; /**< for star: position of outgoing edges NOTE: owned! */
56  const STP_Bool* edgehalf_isblocked; /**< non-owned! */
57  const SDPROFIT* sdprofit; /**< non-owned! */
58  int node_degree; /**< degree of current node */
59  int star_degree; /**< degree of star */
60  SCIP_Bool doEdgeReplacement; /**< try to replace edges as well? */
61 } BDK;
62 
63 
64 /** initializes data for bdk test */
65 static
67  SCIP* scip, /**< SCIP data structure */
68  SD* sdistance, /**< special distance storage */
69  BDK** bdk /**< storage */
70 )
71 {
72  BDK* bdk_d;
74 
75  SCIP_CALL( SCIPallocMemory(scip, bdk) );
76  bdk_d = *bdk;
77 
78  assert(reduce_sdgraphHasMstHalfMark(sdistance->sdgraph));
79 
81  bdk_d->sdistance = sdistance;
82  bdk_d->node_degree = -1;
83  bdk_d->star_degree = -1;
84  bdk_d->star_outedges = NULL;
86  bdk_d->sdprofit = sdistance->sdprofit;
88 
90  SCIP_CALL( graph_path_init(scip, cliquegraph) );
91  assert(cliquegraph->edges == 2 * STP_BDKIMP_MAXNEDGES);
92  bdk_d->cliquegraph = cliquegraph;
93  for( int i = 0; i < STP_BDKIMP_MAXDEGREE; i++ )
94  cliquegraph->mark[i] = TRUE;
95 
96  SCIP_CALL( SCIPallocMemoryArray(scip, &(bdk_d->star_outedges_pos), STP_BDKIMP_MAXDEGREE) );
97  SCIP_CALL( SCIPallocMemoryArray(scip, &(bdk_d->clique_mst), STP_BDKIMP_MAXDEGREE) );
99  SCIP_CALL( SCIPallocMemoryArray(scip, &(bdk_d->node_neighbors), STP_BDKIMP_MAXDEGREE) );
100  SCIP_CALL( SCIPallocMemoryArray(scip, &(bdk_d->star_mstsds), STP_BDKIMP_MAXDEGREE) );
101 
102  assert(sdistance->isBiased == (bdk_d->sdprofit != NULL));
103 
104  return SCIP_OKAY;
105 }
106 
107 /** frees data for bdk test */
108 static
109 void bdkFree(
110  SCIP* scip, /**< SCIP data structure */
111  BDK** bdk /**< storage */
112 )
113 {
114  BDK* bdk_d = *bdk;
115  GRAPH* cliquegraph = bdk_d->cliquegraph;
116 
117  SCIPfreeMemoryArray(scip, &(bdk_d->star_mstsds));
118  SCIPfreeMemoryArray(scip, &(bdk_d->node_neighbors));
119  SCIPfreeMemoryArray(scip, &(bdk_d->node_outedges));
120  SCIPfreeMemoryArray(scip, &(bdk_d->clique_mst));
121  SCIPfreeMemoryArray(scip, &(bdk_d->star_outedges_pos));
122 
123  graph_path_exit(scip, cliquegraph);
124  graph_free(scip, &cliquegraph, TRUE);
125 
126  reduce_starFree(scip, &(bdk_d->star));
127 
128  SCIPfreeMemory(scip, bdk);
129 }
130 
131 
132 /** gets neighborhood information for bdk test */
133 static inline
135  const GRAPH* g, /**< graph data structure */
136  int starcenter, /**< the node */
137  BDK* bdk /**< storage */
138 )
139 {
140  int* RESTRICT edges = bdk->node_outedges;
141  int* RESTRICT adjverts = bdk->node_neighbors;
142  int k = 0;
143 
144  bdk->node_degree = g->grad[starcenter];
145 
146  for( int e = g->outbeg[starcenter]; e != EAT_LAST; e = g->oeat[e] )
147  {
148  edges[k] = e;
149  adjverts[k++] = g->head[e];
150  }
151 
152  assert(k == bdk->node_degree);
153 }
154 
155 
156 /** is the node invalid? */
157 static inline
159  const GRAPH* g, /**< graph data structure */
160  int node, /**< the node */
161  int degree, /**< current degree */
162  const BDK* bdk /**< storage */
163 )
164 {
165  if( g->grad[node] != degree || Is_term(g->term[node]) )
166  return TRUE;
167 
168  /* are the SDs biased? */
169  if( bdk->sdprofit )
170  {
171  const STP_Bool* edges_isBlocked = bdk->edgehalf_isblocked;
172  SCIP_Bool isInTree = FALSE;
173 
174  /* no profit on node? */
175  if( EQ(reduce_sdprofitGetProfit(bdk->sdprofit, node, -1, -1), 0.0) )
176  {
177  return FALSE;
178  }
179 
180  for( int e = g->outbeg[node]; e != EAT_LAST; e = g->oeat[e] )
181  {
182  if( edges_isBlocked[e / 2] )
183  {
184  isInTree = TRUE;
185  break;
186  }
187  }
188 
189  if( isInTree )
190  return TRUE;
191  }
192 
193  return FALSE;
194 }
195 
196 
197 /** gets SDs bdk test; stored in cliquegraph */
198 static inline
200  SCIP* scip, /**< SCIP data structure */
201  const GRAPH* g, /**< graph data structure */
202  int node, /**< the node */
203  DIJK* dijkdata, /**< data for repeated path computations */
204  BDK* bdk /**< storage */
205 )
206 {
207  GRAPH* cliquegraph = bdk->cliquegraph;
208  const int node_degree = bdk->node_degree;
209  int* nodemark = cliquegraph->mark;
210 
211  assert(node_degree >= 3);
212  assert(node_degree == g->grad[node]);
213 
214  assert(STP_BDKIMP_MAXDEGREE == cliquegraph->knots);
215 
216  for( int k = 0; k < node_degree; k++ )
217  nodemark[k] = TRUE;
218 
219  for( int k = node_degree; k < STP_BDKIMP_MAXDEGREE; k++ )
220  nodemark[k] = FALSE;
221 
222  SCIP_CALL( reduce_sdGetSdsCliquegraph(scip, g, node, bdk->node_neighbors, dijkdata, bdk->sdistance, cliquegraph) );
223 
224  return SCIP_OKAY;
225 }
226 
227 
228 /** gets SDs for bdk node test; stored in clique-graph */
229 static inline
231  const GRAPH* g, /**< graph data structure */
232  const BDK* bdk, /**< storage */
233  int node, /**< the node */
234  SCIP_Real* cutoffs /**< cutoffs */
235 )
236 {
237  const GRAPH* cliquegraph = bdk->cliquegraph;
238  const int node_degree = bdk->node_degree;
239  int edgecount = 0;
240 
241  // printf("go degree=%d \n", bdk->node_degree);
242 
243  for( int k = 0; k < node_degree; k++ )
244  {
245  for( int e = cliquegraph->outbeg[k]; e != EAT_LAST; e = cliquegraph->oeat[e] )
246  {
247  const int k2 = cliquegraph->head[e];
248 
249  if( k2 >= node_degree )
250  continue;
251 
252  if( k2 > k )
253  {
254  // printf("%d, %d \n", k, k2);
255  cutoffs[edgecount++] = cliquegraph->cost[e];
256  }
257  }
258  }
259 }
260 
261 
262 /** gets SDs for bdk edge test; stored in clique-graph */
263 static inline
265  const GRAPH* g, /**< graph data structure */
266  const BDK* bdk, /**< storage */
267  int edge, /**< the edge; replacement goes towards the head! */
268  SCIP_Real* cutoffs /**< cutoffs */
269 )
270 {
271  const GRAPH* cliquegraph = bdk->cliquegraph;
272  const int* const adjverts = bdk->node_neighbors;
273  const int node_degree = bdk->node_degree;
274  const int tail = g->tail[edge];
275  int tail_pos = -1;
276 #ifndef NDEBUG
277  int edgecount = 0;
278  for( int k = 0; k < node_degree; k++ )
279  cutoffs[k] = -1.0;
280 #endif
281 
282  for( int k = 0; k < node_degree; k++ )
283  {
284  if( adjverts[k] == tail )
285  {
286  tail_pos = k;
287  break;
288  }
289  }
290 
291  assert(tail_pos >= 0);
292  assert(adjverts[tail_pos] == tail);
293 
294  for( int e = cliquegraph->outbeg[tail_pos]; e != EAT_LAST; e = cliquegraph->oeat[e] )
295  {
296  const int k = cliquegraph->head[e];
297 
298  if( k < node_degree )
299  {
300  assert(EQ(cutoffs[k], -1.0));
301  cutoffs[k] = cliquegraph->cost[e];
302 
303 #ifndef NDEBUG
304  edgecount++;
305 #endif
306 
307  SCIPdebugMessage("%d->%d cutoff=%f \n", tail, adjverts[k], cliquegraph->cost[e]);
308  }
309  }
310 
311  assert(edgecount == node_degree - 1);
312 }
313 
314 
315 /** gets next star */
316 static inline
318  const GRAPH* g, /**< graph data structure */
319  BDK* bdk /**< storage */
320  )
321 {
323 
324 #ifdef SCIP_DEBUG
325  SCIPdebugMessage("checking star: \n");
326  for( int i = 0; i < bdk->star_degree; i++ )
327  {
329  }
330 #endif
331 }
332 
333 
334 /** return cost of star */
335 static inline
337  int starcenter, /**< the star center node */
338  const GRAPH* g, /**< graph data structure */
339  const BDK* bdk /**< storage */
340  )
341 {
342  const int* const star_edges = bdk->star_outedges;
343  SCIP_Real costsum = 0.0;
344  const int star_degree = bdk->star_degree;
345 
346  for( int j = 0; j < star_degree; j++ )
347  {
348  const int outedge = star_edges[j];
349  assert(outedge >= 0 && g->tail[outedge] == starcenter);
350  costsum += g->cost[outedge];
351  }
352 
353  return costsum;
354 }
355 
356 
357 /** Returns SD replacement cost of star.
358  * Chooses best combinations of SD clique MST costs and SD distance graph MST costs. */
359 static inline
361  const GRAPH* g, /**< graph data structure */
362  BDK* bdk /**< storage */
363 )
364 {
365  const int star_degree = bdk->star_degree;
366  SCIP_Real* RESTRICT star_mstsds = bdk->star_mstsds;
367  const SCIP_Real* const sdtreecosts = reduce_sdgraphGetOrderedMstCosts(bdk->sdistance->sdgraph);
368  SCIP_Real treesum = sdtreecosts[0];
369 
370 #ifndef NDEBUG
371  SCIP_Real sdsum_dbg = 0.0;
372  assert(star_degree >= 3);
373 
374  for( int i = 0; i < star_degree - 1; i++ )
375  sdsum_dbg += star_mstsds[i];
376 
377  assert(LT(sdsum_dbg, FARAWAY));
378 #endif
379 
380  SCIPsortDownReal(star_mstsds, star_degree - 1);
381  assert(GE(star_mstsds[0], star_mstsds[1]));
382  assert(GE(treesum, star_mstsds[0])); /* this value should already have been used for the SD computation*/
383 
384  for( int i = 1; i < star_degree - 1; i++ )
385  {
386  star_mstsds[i] += star_mstsds[i - 1];
387  treesum += sdtreecosts[i];
388 
389  if( star_mstsds[i] > treesum )
390  {
391  star_mstsds[i] = treesum;
392  }
393  }
394 
395 
396 #ifndef NDEBUG
397  assert(LE_FEAS(star_mstsds[star_degree - 2], sdsum_dbg)); /* make sure we did not get worse */
398 #endif
399 
400  return star_mstsds[star_degree - 2];
401 }
402 
403 
404 /** marks nodes that are in current star */
405 static inline
407  BDK* bdk /**< storage */
408 )
409 {
410  GRAPH* const cliquegraph = bdk->cliquegraph;
411  const int* const star_edges_pos = bdk->star_outedges_pos;
412  const int stardegree = bdk->star_degree;
413  int* const nodesmark = cliquegraph->mark;
414 
415  for( int i = 0; i < STP_BDKIMP_MAXDEGREE; i++ )
416  nodesmark[i] = FALSE;
417 
418  /* we need some special stuff for degree 3, because no actual star is used */
419  if( bdk->node_degree == 3 )
420  {
421  for( int i = 0; i < 3; i++ )
422  nodesmark[i] = TRUE;
423 
424  return;
425  }
426 
427  for( int i = 0; i < stardegree; i++ )
428  {
429  const int pos = star_edges_pos[i];
430 
431  assert(0 <= pos && pos < STP_BDKIMP_MAXDEGREE);
432  assert(bdk->node_outedges[pos] == bdk->star_outedges[i]);
433 
434  nodesmark[pos] = TRUE;
435  }
436 }
437 
438 
439 /** gets start node for MSt */
440 static inline
442  const GRAPH* cliquegraph /**< graph data structure */
443 )
444 {
445  int startnode = -1;
446  const int* const nodesmark = cliquegraph->mark;
447 
448  for( int i = 0; i < STP_BDKIMP_MAXDEGREE; i++ )
449  {
450  if( nodesmark[i] )
451  {
452  startnode = i;
453  break;
454  }
455  }
456  assert(startnode != -1);
457 
458  return startnode;
459 }
460 
461 
462 /** stores MST costs for later use */
463 static inline
465  int startnode, /**< start node */
466  BDK* bdk /**< storage */
467 )
468 {
469  int count = 0;
470  const GRAPH* const cliquegraph = bdk->cliquegraph;
471  const PATH* const mst = bdk->clique_mst;
472  const int* const nodesmark = cliquegraph->mark;
473  SCIP_Real* const star_mstsds = bdk->star_mstsds;
474 
475  for( int i = 0; i < STP_BDKIMP_MAXDEGREE; i++ )
476  {
477  if( nodesmark[i] && i != startnode )
478  {
479  assert(LT(mst[i].dist, FARAWAY));
480  star_mstsds[count++] = mst[i].dist;
481  }
482  else
483  {
484  assert(GE(mst[i].dist, FARAWAY) || i == startnode);
485  }
486  }
487 
488  assert(count == bdk->star_degree - 1);
489 }
490 
491 
492 /** can star be replaced by SD MST? */
493 static inline
495  SCIP* scip, /**< SCIP data structure */
496  SCIP_Real starcost, /**< cost of star */
497  const GRAPH* g, /**< graph data structure */
498  BDK* bdk /**< storage */
499 )
500 {
501  GRAPH* const cliquegraph = bdk->cliquegraph;
502  PATH* const mst = bdk->clique_mst;
503  SCIP_Real sdcost;
504  int startnode;
505 
507 
508  startnode = bdkStarGetMstStartNode(cliquegraph);
509 
510  /* compute MST */
511  graph_path_exec(scip, cliquegraph, MST_MODE, startnode, cliquegraph->cost, mst);
512 
513  bdkStarStoreMstsCosts(startnode, bdk);
514 
515  /* get best combination of MST edge costs and SD distance graph MST costs */
516  sdcost = bdkStarGetCombinedSdCost(g, bdk);
517 
518  SCIPdebugMessage("sdcost=%f, starcost=%f \n", sdcost, starcost);
519 
520  if( SCIPisLE(scip, sdcost, starcost) )
521  {
522  SCIPdebugMessage("star is SD MST replacable \n");
523 
524  return TRUE;
525  }
526 
527  return FALSE;
528 }
529 
530 
531 /** can star be replaced by SD MST? */
532 static inline
534  SCIP* scip, /**< SCIP data structure */
535  SCIP_Real starcost, /**< cost of star */
536  const GRAPH* g, /**< graph data structure */
537  BDK* bdk /**< storage */
538 )
539 {
540  const SCIP_Real* const sdtreecosts = reduce_sdgraphGetOrderedMstCosts(bdk->sdistance->sdgraph);
541  SCIP_Real treecost = 0.0;
542  const int star_degree = bdk->star_degree;
543 
544  for( int j = 0; j < star_degree - 1; j++ )
545  {
546  assert(GE(sdtreecosts[j], 0.0));
547  assert(j == 0 || GE(sdtreecosts[j - 1], sdtreecosts[j]));
548 
549  treecost += sdtreecosts[j];
550  }
551 
552  /* NOTE: special distance is allowed to be equal to costsum,
553  * because in the case the corresponding walks cannot contain the whole star! */
554  if( SCIPisLE(scip, treecost, starcost) )
555  {
556  SCIPdebugMessage("star is distance-graph MST replacable \n");
557 
558  return TRUE;
559  }
560 
561  return FALSE;
562 }
563 
564 
565 /** can vertex of degree 3 be replaced? */
566 static inline
568  SCIP* scip, /**< SCIP data structure */
569  int i, /**< the node */
570  const GRAPH* g, /**< graph data structure */
571  BDK* bdk /**< storage */
572 )
573 {
574  const SCIP_Real* const maxcosts = reduce_sdgraphGetOrderedMstCosts(bdk->sdistance->sdgraph);
575  const SCIP_Real* const gCost = g->cost;
576  const int* const star_edges = bdk->star_outedges;
577  const SCIP_Real starcost = gCost[star_edges[0]] + gCost[star_edges[1]] + gCost[star_edges[2]];
578 
579  assert(bdk->star_degree == 3);
580  assert(GE(maxcosts[0], 0.0) && GE(maxcosts[1], 0.0));
581 
582  /* NOTE: special distance is allowed to be equal to costsum,
583  * because in the case the corresponding walks cannot contain the whole star! */
584  if( SCIPisLE(scip, maxcosts[0] + maxcosts[1], starcost) )
585  {
586  SCIPdebugMessage("3-star is distance-graph MST replacable: %f <= %f \n", maxcosts[0] + maxcosts[1], starcost);
587 
588  return TRUE;
589  }
590 
591  if( bdkStarIsSdMstReplacable(scip, starcost, g, bdk) )
592  return TRUE;
593 
595  return TRUE;
596 
597  return FALSE;
598 }
599 
600 
601 /** can star of degree 4 or greater be replaced? */
602 static inline
604  SCIP* scip, /**< SCIP data structure */
605  int starcenter, /**< the node */
606  const GRAPH* g, /**< graph data structure */
607  BDK* bdk /**< storage */
608 )
609 {
610  const int star_degree = bdk->star_degree;
611  const SCIP_Real starcost = bdkStarGetCost(starcenter, g, bdk);
612 
613  assert(g->terms >= star_degree);
614  assert(4 <= star_degree && star_degree <= STP_BDKIMP_MAXDEGREE);
615 
616  if( bdkStarIsSdTreeReplacable(scip, starcost, g, bdk) )
617  return TRUE;
618 
619  if( bdkStarIsSdMstReplacable(scip, starcost, g, bdk) )
620  return TRUE;
621 
622  if( graph_pseudoAncestors_edgesInConflict(scip, g, bdk->star_outedges, star_degree) )
623  return TRUE;
624 
625  return FALSE;
626 }
627 
628 
629 /** does bdk test for vertex of degree 3
630  * NOTE: one could also use DegGe4 instead, but this method is slightly more efficient */
631 static inline
633  SCIP* scip, /**< SCIP data structure */
634  int node, /**< the node */
635  GRAPH* g, /**< graph data structure */
636  BDK* bdk, /**< storage */
637  int* nelims /**< number of eliminations */
638 )
639 {
640  assert(g->grad[node] == 3);
641  assert(bdk->node_degree == 3);
642  assert(g->terms >= 3);
643 
644  bdk->star_degree = 3;
645  bdk->star_outedges = bdk->node_outedges;
646 
647  if( bdkStarIsReplacableDeg3(scip, node, g, bdk) )
648  {
649  SCIP_Real cutoffs[3];
650  SCIP_Bool success;
651  bdkGetCutoffs(g, bdk, node, cutoffs);
652 
653  SCIP_CALL(graph_knot_delPseudo(scip, g, g->cost, cutoffs, NULL, node, NULL, &success));
654 
655  assert(success);
656  assert(g->grad[node] == 0);
657 
658  SCIPdebugMessage("BD3-implied reduction of node %d with SDs: %f %f %f \n ",node, cutoffs[0], cutoffs[1], cutoffs[2]);
659  (*nelims)++;
660  }
661 
662  return SCIP_OKAY;
663 }
664 
665 
666 /** does bdk test for vertex of degree 4 or more */
667 static inline
669  SCIP* scip, /**< SCIP data structure */
670  int node, /**< the node */
671  GRAPH* g, /**< graph data structure */
672  BDK* bdk, /**< storage */
673  int* nelims /**< number of eliminations */
674 )
675 {
676  STAR* const star = bdk->star;
678  SCIP_Bool nodeIsReplacable = TRUE;
679  SCIP_Bool isDeleted = FALSE;
680 
681  assert(4 <= g->grad[node] && g->grad[node] <= STP_BDKIMP_MAXDEGREE);
682 
683  reduce_starReset(g, node, star);
684 
685  /* check all stars of degree >= 3, as long as at least one edge might be ruled-out */
686  while ( !reduce_starAllAreChecked(star) )
687  {
689 
690  bdkStarLoadNext(g, bdk);
691 
692  if( bdk->star_degree == 3 )
693  {
694  isPseudoDeletable = bdkStarIsReplacableDeg3(scip, node, g, bdk);
695  }
696  else
697  {
698  isPseudoDeletable = bdkStarIsReplacableDegGe4(scip, node, g, bdk);
699  }
700 
701  if( !isPseudoDeletable )
702  {
703  SCIPdebugMessage("...not deletable \n");
704  nodeIsReplacable = FALSE;
705 
706  if( !doEdgeReplacement )
707  break;
708 
710  }
711 
712  if( !reduce_starHasPromisingEdges(star) )
713  {
714  assert(!nodeIsReplacable);
715  assert(!isPseudoDeletable);
716  break;
717  }
718  }
719 
720  if( nodeIsReplacable )
721  {
723 
724  bdkGetCutoffs(g, bdk, node, cutoffs);
725 
726  SCIP_CALL(graph_knot_delPseudo(scip, g, g->cost, cutoffs, NULL, node, NULL, &isDeleted));
727 
728  if( isDeleted )
729  SCIPdebugMessage("BD%d-implied reduction of node %d \n ", bdk->node_degree, node);
730  }
731 
732  if( doEdgeReplacement && !isDeleted && reduce_starHasPromisingEdges(star) )
733  {
735  int ndeledges;
736  const int* const deledges = reduce_starGetRuledOutEdges(star, &ndeledges);
737 
738  assert(ndeledges >= 1);
739 
740  for( int i = 0; i < ndeledges; i++ )
741  {
742  const int edge = flipedge(deledges[i]);
743 
744  assert(graph_edge_isInRange(g, deledges[i]));
745  assert(g->head[edge] == node);
746  assert(!isDeleted);
747 
748  bdkGetEdgeCutoffs(g, bdk, edge, cutoffs);
749 
750  SCIP_CALL(graph_edge_delPseudo(scip, g, g->cost, cutoffs, NULL, edge, NULL, &isDeleted));
751 
752  if( isDeleted )
753  {
754  SCIPdebugMessage("BD%d-implied reduction of edge %d \n ", bdk->node_degree, edge);
755  break;
756  }
757  }
758  }
759 
760  if( isDeleted )
761  (*nelims)++;
762 
763  return SCIP_OKAY;
764 }
765 
766 
767 
768 /*
769  * Interface methods
770  */
771 
772 
773 /** bd_k test without given Steiner bottleneck distances */
775  SCIP* scip, /**< SCIP data structure */
776  int edgevisitlimit, /**< maximum edge visited per iteration */
777  GRAPH* g, /**< graph structure */
778  int* nelims /**< number of eliminations */
779  )
780 {
781  SD* sdistance;
782 
783  /* NOTE: in the case of g->terms < 3 the method does not work properly, and the case is easy enough to ignore it */
784  if( g->terms < 3 )
785  return SCIP_OKAY;
786 
787  SCIP_CALL( reduce_sdInit(scip, g, &sdistance) );
788  SCIP_CALL( reduce_bdkWithSd(scip, edgevisitlimit, sdistance, g, nelims) );
789  reduce_sdFree(scip, &sdistance);
790 
791  return SCIP_OKAY;
792 }
793 
794 
795 /** biased bd_k test without given Steiner bottleneck distances */
797  SCIP* scip, /**< SCIP data structure */
798  int edgevisitlimit, /**< maximum edge visited per iteration */
799  GRAPH* g, /**< graph structure */
800  int* nelims /**< number of eliminations */
801  )
802 {
803  SD* sdistance;
804 
805  /* NOTE: in the case of g->terms < 3 the method does not work properly, and the case is easy enough to ignore it */
806  if( g->terms < 3 )
807  return SCIP_OKAY;
808 
809  SCIP_CALL( reduce_sdInitBiased(scip, g, &sdistance) );
810  SCIP_CALL( reduce_bdkWithSd(scip, edgevisitlimit, sdistance, g, nelims) );
811  reduce_sdFree(scip, &sdistance);
812 
813  return SCIP_OKAY;
814 }
815 
816 
817 /** bd_k test for given Steiner bottleneck distances */
819  SCIP* scip, /**< SCIP data structure */
820  int edgevisitlimit, /**< maximum edge visited per iteration */
821  SD* sdistance, /**< special distances storage */
822  GRAPH* g, /**< graph structure */
823  int* nelims /**< number of eliminations */
824  )
825 {
826  BDK* bdk;
827  DIJK* dijkdata;
828  const int nnodes = graph_get_nNodes(g);
829  const int maxdegree = MIN(g->terms, STP_BDKIMP_MAXDEGREE);
830  const int nelims_initial = *nelims;
831 
832  assert(scip && sdistance && nelims);
833  assert(nelims_initial >= 0);
834  assert(!graph_pc_isPcMw(g));
835  assert(edgevisitlimit > 0);
836 
837  /* NOTE: in the case of g->terms < 3 the method does not work properly, and the case is easy enough to ignore it */
838  if( g->terms < 3 )
839  return SCIP_OKAY;
840 
841  //SCIP_CALL( reduce_sdBiased(scip, sdistance, g, nelims) );
842 
843  //return SCIP_OKAY;
844 
845  SCIP_CALL( bdkInit(scip, sdistance, &bdk) );
846  SCIPdebugMessage("starting BDK-SD Reduction: \n");
847  graph_mark(g);
848 
849  // todo have a reduction structure REDUCT that contains DIJK and SD, etc...
850  SCIP_CALL( graph_dijkLimited_init(scip, g, &(dijkdata)) );
851  graph_dijkLimited_clean(g, dijkdata);
852  dijkdata->edgelimit = edgevisitlimit;
853 
854  for( int degree = 3; degree <= maxdegree; degree ++ )
855  {
856  for( int i = 0; i < nnodes; i++ )
857  {
858  if( bdkNodeIsInvalid(g, i, degree, bdk) )
859  continue;
860 
861  SCIPdebugMessage("\n check node %d (degree=%d) \n", i, degree);
862 
863  bdkGetNeighborhood(g, i, bdk);
864  SCIP_CALL( bdkGetCliqueSds(scip, g, i, dijkdata, bdk) );
865 
866  if( degree == 3 )
867  {
868  SCIP_CALL( bdkTryDeg3(scip, i, g, bdk, nelims) );
869  }
870  else
871  {
872  SCIP_CALL( bdkTryDegGe4(scip, i, g, bdk, nelims) );
873  }
874 
875  graph_dijkLimited_reset(g, dijkdata);
876  }
877  }
878 
879  graph_dijkLimited_free(scip, &(dijkdata));
880  bdkFree(scip, &bdk);
881 
882  if( *nelims > nelims_initial )
883  {
884  SCIP_CALL( reduce_unconnected(scip, g) );
885  }
886 
887  return SCIP_OKAY;
888 }
SCIP_RETCODE reduce_sdInit(SCIP *, GRAPH *, SD **)
static SCIP_Bool bdkStarIsReplacableDeg3(SCIP *scip, int i, const GRAPH *g, BDK *bdk)
const int * reduce_starGetNextAndPosition(STAR *, int *, int *)
Definition: reduce_util.c:1886
int *RESTRICT head
Definition: graphdefs.h:224
static SCIP_RETCODE bdkGetCliqueSds(SCIP *scip, const GRAPH *g, int node, DIJK *dijkdata, BDK *bdk)
static void bdkGetCutoffs(const GRAPH *g, const BDK *bdk, int node, SCIP_Real *cutoffs)
#define Is_term(a)
Definition: graphdefs.h:102
static void bdkFree(SCIP *scip, BDK **bdk)
static SCIP_Bool bdkStarIsReplacableDegGe4(SCIP *scip, int starcenter, const GRAPH *g, BDK *bdk)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
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:1028
SCIP_Bool reduce_starAllAreChecked(const STAR *)
Definition: reduce_util.c:2002
int terms
Definition: graphdefs.h:192
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
static SCIP_Bool bdkStarIsSdMstReplacable(SCIP *scip, SCIP_Real starcost, const GRAPH *g, BDK *bdk)
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_sdInitBiased(SCIP *, GRAPH *, SD **)
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
const int * reduce_starGetRuledOutEdges(STAR *, int *)
Definition: reduce_util.c:1918
#define FARAWAY
Definition: graphdefs.h:89
#define STP_BDKIMP_MAXNEDGES
Definition: reduce_sdcomp.c:40
static SCIP_RETCODE bdkTryDegGe4(SCIP *scip, int node, GRAPH *g, BDK *bdk, int *nelims)
SCIP_Bool reduce_starHasPromisingEdges(const STAR *)
Definition: reduce_util.c:1990
SCIP_RETCODE reduce_starInit(SCIP *, int, STAR **)
Definition: reduce_util.c:1725
const SCIP_Real * reduce_sdgraphGetOrderedMstCosts(const SDGRAPH *)
static SCIP_Bool bdkNodeIsInvalid(const GRAPH *g, int node, int degree, const BDK *bdk)
static SCIP_Real bdkStarGetCombinedSdCost(const GRAPH *g, BDK *bdk)
int *RESTRICT mark
Definition: graphdefs.h:198
void graph_dijkLimited_reset(const GRAPH *, DIJK *)
Definition: graph_util.c:2105
int *RESTRICT oeat
Definition: graphdefs.h:231
const SDPROFIT * sdprofit
Definition: reduce_sdcomp.c:57
#define GE(a, b)
Definition: portab.h:85
SCIP_RETCODE graph_edge_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, SCIP_Real *, SCIP_Bool *)
SCIP_RETCODE reduce_bdkWithSd(SCIP *scip, int edgevisitlimit, SD *sdistance, GRAPH *g, int *nelims)
void reduce_starFree(SCIP *, STAR **)
Definition: reduce_util.c:1758
SCIP_Real dist
Definition: graphdefs.h:286
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 EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
SCIP_Bool graph_pseudoAncestors_edgesInConflict(SCIP *, const GRAPH *, const int *, int)
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_RETCODE bdkInit(SCIP *scip, SD *sdistance, BDK **bdk)
Definition: reduce_sdcomp.c:66
void reduce_sdFree(SCIP *, SD **)
#define MST_MODE
Definition: graphdefs.h:98
#define STP_BDKIMP_MAXDEGREE
Definition: reduce_sdcomp.c:39
#define LT(a, b)
Definition: portab.h:81
static void bdkGetNeighborhood(const GRAPH *g, int starcenter, BDK *bdk)
unsigned char STP_Bool
Definition: portab.h:34
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
Definition: reducedefs.h:178
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
void graph_dijkLimited_free(SCIP *, DIJK **)
Definition: graph_util.c:2143
#define SCIP_Bool
Definition: def.h:84
struct bottleneck_distance_storage BDK
SCIP_RETCODE reduce_bdk(SCIP *scip, int edgevisitlimit, GRAPH *g, int *nelims)
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
void reduce_starReset(const GRAPH *, int, STAR *)
Definition: reduce_util.c:1781
#define STP_BDK_WITH_EDGEREPLACINGS
Definition: reduce_sdcomp.c:38
void reduce_starCurrentSetFailed(STAR *)
Definition: reduce_util.c:1960
int *RESTRICT term
Definition: graphdefs.h:196
const STP_Bool * edgehalf_isblocked
Definition: reduce_sdcomp.c:56
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
static int bdkStarGetMstStartNode(const GRAPH *cliquegraph)
Portable definitions.
SCIP_RETCODE reduce_sdGetSdsCliquegraph(SCIP *, const GRAPH *, int, const int *, DIJK *, SD *, GRAPH *)
Definition: reduce_sd.c:1389
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
static void bdkGetEdgeCutoffs(const GRAPH *g, const BDK *bdk, int edge, SCIP_Real *cutoffs)
static SCIP_Real bdkStarGetCost(int starcenter, const GRAPH *g, const BDK *bdk)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
static void bdkStarStoreMstsCosts(int startnode, BDK *bdk)
SCIP_Bool reduce_sdgraphHasMstHalfMark(const SDGRAPH *)
static SCIP_Bool bdkStarIsSdTreeReplacable(SCIP *scip, SCIP_Real starcost, const GRAPH *g, BDK *bdk)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
void graph_dijkLimited_clean(const GRAPH *, DIJK *)
Definition: graph_util.c:2083
#define SCIP_Real
Definition: def.h:177
static void bdkStarLoadNext(const GRAPH *g, BDK *bdk)
int *RESTRICT outbeg
Definition: graphdefs.h:204
int edges
Definition: graphdefs.h:219
static SCIP_RETCODE bdkTryDeg3(SCIP *scip, int node, GRAPH *g, BDK *bdk, int *nelims)
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_RETCODE reduce_bdkBiased(SCIP *scip, int edgevisitlimit, GRAPH *g, int *nelims)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE graph_buildCompleteGraph(SCIP *, GRAPH **, int)
Definition: graph_base.c:440
#define nnodes
Definition: gastrans.c:65
const STP_Bool * reduce_sdgraphGetMstHalfMark(const SDGRAPH *)
includes various reduction methods for Steiner tree problems
static void bdkStarMarkCliqueNodes(BDK *bdk)
void SCIPsortDownReal(SCIP_Real *realarray, int len)
#define LE_FEAS(a, b)
Definition: portab.h:70
SCIP callable library.