Scippy

SCIP

Solving Constraint Integer Programs

reduce_bnd.c
Go to the documentation of this file.
1 
2 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
3 /* */
4 /* This file is part of the program and library */
5 /* SCIP --- Solving Constraint Integer Programs */
6 /* */
7 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
8 /* fuer Informationstechnik Berlin */
9 /* */
10 /* SCIP is distributed under the terms of the ZIB Academic License. */
11 /* */
12 /* You should have received a copy of the ZIB Academic License */
13 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
14 /* */
15 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
16 
17 /**@file reduce_bnd.c
18  * @brief bound based reductions for Steiner tree problems
19  * @author Daniel Rehfeldt
20  *
21  * This file implements bound-based reduction techniques for several Steiner problems.
22  * Most tests can be found in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
23  *
24  * A list of all interface methods can be found in reduce.h.
25  *
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 //#define SCIP_DEBUG
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <math.h>
35 #include <assert.h>
36 #include "graph.h"
37 #include "reduce.h"
38 #include "heur_tm.h"
39 #include "heur_ascendprune.h"
40 #include "misc_stp.h"
41 #include "solstp.h"
42 #include "probdata_stp.h"
43 #include "prop_stp.h"
44 
45 
46 #define BND_TMHEUR_NRUNS 20 /**< number of runs of constructive heuristic */
47 
48 
49 /** bound-based reductions for the (R)PCSTP, the MWCSP and the STP */
50 static
52  SCIP* scip, /**< SCIP data structure */
53  GRAPH* graph, /**< graph data structure */
54  SCIP_Real* cost, /**< edge cost array */
55  SCIP_Real* costrev, /**< reversed edge cost array */
56  int* result, /**< result edges */
57  STP_Bool* stnode, /**< result nodes */
58  SCIP_Real* upperbound, /**< pointer to an upper bound */
59  SCIP_Bool* success /**< success? */
60  )
61 {
62  int* starts = NULL;
63  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
64  int runs;
65  SCIP_Real obj;
66  const int nnodes = graph_get_nNodes(graph);
67  const int nedges = graph_get_nEdges(graph);
68  SCIP_Real hoplimit = -1.0;
69 
70  SCIPdebugMessage("compute Steiner tree \n");
71 
72  assert(!graph_pc_isMw(graph));
73 
74  runs = 0;
75  *upperbound = -FARAWAY;
76 
77  for( int k = 0; k < nnodes; ++k )
78  {
79  stnode[k] = FALSE;
80 
81  if( graph->mark[k] )
82  runs++;
83  }
84 
85  for( int e = 0; e < nedges; ++e )
86  result[e] = UNKNOWN;
87 
88  runs = MIN(runs, BND_TMHEUR_NRUNS);
89 
90  if( !pcmw )
91  {
92  SCIP_CALL( SCIPallocBufferArray(scip, &starts, nnodes) );
93  SCIPStpHeurTMCompStarts(graph, starts, &runs);
94  }
95 
96  if( pcmw )
97  {
98  graph_pc_2trans(scip, graph);
99 
100  graph_getEdgeCosts(graph, cost, costrev);
101  }
102 
104  graph, starts, NULL, result, runs, graph->source, cost, costrev, &hoplimit, NULL, success));
105 
106  if( pcmw )
107  {
108  obj = graph_pc_solGetObj(scip, graph, result, 0.0);
109 
110  graph_pc_2org(scip, graph);
111 
112  assert(SCIPisEQ(scip, obj, graph_pc_solGetObj(scip, graph, result, 0.0)));
113 
114  graph_getEdgeCosts(graph, cost, costrev);
115  }
116  else
117  {
118  obj = solstp_getObjBounded(graph, result, 0.0, nedges);
119  }
120 
121  if( !(*success) )
122  return SCIP_OKAY;
123 
124 
125  if( graph_pc_isPc(graph) && !graph->extended )
126 
127  for( int e = 0; e < nedges; e++ )
128  {
129  if( result[e] == CONNECT )
130  {
131  const int head = graph->head[e];
132  const int tail = graph->tail[e];
133 
134  stnode[head] = TRUE;
135  stnode[tail] = TRUE;
136  }
137  }
138 
139  *upperbound = obj;
140 
141  SCIPfreeBufferArrayNull(scip, &starts);
142 
143  return SCIP_OKAY;
144 }
145 
146 
147 /** heuristic bound-based reductions for non (R)MWCS */
148 static
150  SCIP* scip, /**< SCIP data structure */
151  GRAPH* graph, /**< graph data structure */
152  PATH* vnoi, /**< Voronoi data structure */
153  SCIP_Real* cost, /**< edge cost array */
154  SCIP_Real* radius, /**< radius array */
155  SCIP_Real* costrev, /**< reversed edge cost array */
156  SCIP_Real* offset, /**< pointer to the offset */
157  int* heap, /**< heap array */
158  int* state, /**< array to store state of a node during Voronoi computation */
159  int* vbase, /**< Voronoi base to each node */
160  const int* solnode, /**< array of nodes of current solution that is not to be destroyed */
161  const int* soledge, /**< array of edges of current solution that is not to be destroyed */
162  int* nelims, /**< pointer to store number of eliminated edges */
163  int minelims /**< minimum number of edges to be eliminated */
164  )
165 {
166  SCIP_Real* const prize = graph->prize;
167  SCIP_Real obj;
168  SCIP_Real max;
170  SCIP_Real tmpcost;
171  SCIP_Real mstobj;
172  SCIP_Real radiim2;
173  SCIP_Real radiim3;
174  const int root = graph->source;
175  const int nnodes = graph->knots;
176  const int nedges = graph->edges;
177  const SCIP_Bool pc = (graph->stp_type == STP_RPCSPG) || (graph->stp_type == STP_PCSPG);
178  const int nterms = graph->terms - ((graph->stp_type == STP_PCSPG) ? 1 : 0);
179  SCIP_Bool eliminate;
180 
181  assert(!graph_pc_isMw(graph));
182 
183  mstobj = 0.0;
184  *nelims = 0;
185 
186  if( nterms <= 2 )
187  return SCIP_OKAY;
188 
189  graph_getEdgeCosts(graph, cost, costrev);
190 
191  if( !pc )
192  {
193  GRAPH* adjgraph;
194  PATH* mst;
195 
196  for( int k = 0; k < nnodes; k++ )
197  graph->mark[k] = (graph->grad[k] > 0);
198 
199  SCIP_CALL( graph_init(scip, &adjgraph, nterms, MIN(nedges, (nterms - 1) * nterms), 1) );
200 
201  /* build Voronoi regions, concomitantly building adjgraph and computing radii values*/
202  SCIP_CALL( graph_voronoiWithRadius(scip, graph, adjgraph, vnoi, radius, cost, costrev, vbase, heap, state) );
203 
204  graph_add2ndTermPaths(graph, cost, costrev, vnoi, vbase, state);
205  graph_add3rdTermPaths(graph, cost, costrev, vnoi, vbase, state);
206 
207  assert(adjgraph != NULL);
208  graph_knot_chg(adjgraph, 0, 0);
209  adjgraph->source = 0;
210  assert(graph_valid(scip, adjgraph));
211 
212  /* compute MST on adjgraph */
213  SCIP_CALL( SCIPallocBufferArray(scip, &mst, nterms) );
214  SCIP_CALL( graph_path_init(scip, adjgraph) );
215  graph_path_exec(scip, adjgraph, MST_MODE, 0, adjgraph->cost, mst);
216 
217  max = -1.0;
218  for( int k = 1; k < nterms; k++ )
219  {
220  const int e = mst[k].edge;
221  assert(adjgraph->path_state[k] == CONNECT);
222  assert(e >= 0);
223  tmpcost = adjgraph->cost[e];
224  mstobj += tmpcost;
225  if( SCIPisGT(scip, tmpcost, max) )
226  max = tmpcost;
227  }
228  mstobj -= max;
229 
230  /* free memory*/
231  SCIPfreeBufferArray(scip, &mst);
232  graph_path_exit(scip, adjgraph);
233  graph_free(scip, &adjgraph, TRUE);
234 
235  }
236  else
237  {
238  SCIP_CALL( graph_voronoiWithRadius(scip, graph, NULL, vnoi, radius, cost, costrev, vbase, heap, state) );
239  graph_add2ndTermPaths(graph, cost, costrev, vnoi, vbase, state);
240  graph_add3rdTermPaths(graph, cost, costrev, vnoi, vbase, state);
241  }
242 
243  /* for (rooted) prize collecting an maximum weight problems: correct radius values */
244  if( graph->stp_type == STP_RPCSPG )
245  {
246  assert(graph->mark[graph->source]);
247  for( int k = 0; k < nnodes; k++ )
248  {
249  if( !Is_term(graph->term[k]) || !graph->mark[k] )
250  continue;
251 
252  if( SCIPisGT(scip, radius[k], prize[k]) && k != graph->source )
253  radius[k] = prize[k];
254  }
255  }
256  else if( graph->stp_type == STP_PCSPG )
257  {
258  for( int k = 0; k < nnodes; k++ )
259  {
260  if( !graph->mark[k] )
261  continue;
262 
263  if( Is_term(graph->term[k]) && SCIPisGT(scip, radius[k], prize[k]) )
264  radius[k] = prize[k];
265  }
266  }
267 
268  /* sort radius values */
269  SCIPsortReal(radius, nnodes);
270 
271  radiim2 = 0.0;
272 
273  for( int e = 0; e < nedges; e++ )
274  costrev[e] = -1.0;
275 
276  /* sum all but two radius values of highest/lowest value */
277  for( int k = 0; k < nterms - 2; k++ )
278  {
279  assert( SCIPisGT(scip, FARAWAY, radius[k]) );
280  radiim2 += radius[k];
281  }
282  if( nterms >= 3 )
283  radiim3 = radiim2 - radius[nterms - 3];
284  else
285  radiim3 = 0.0;
286 
287  if( SCIPisGT(scip, radiim2, mstobj) )
288  bound = radiim2;
289  else
290  {
291  assert(!pc);
292  bound = mstobj;
293  }
294 
295  for( int redrounds = 0; redrounds < 3; redrounds++ )
296  {
297  int nrealelims = MIN(2 * minelims, nedges - 1);
298 
299  if( redrounds == 0 )
300  {
301  eliminate = FALSE;
302  obj = FARAWAY;
303  }
304  else if( redrounds == 1 )
305  {
306  assert(minelims > 0);
307  assert(2 * minelims < nedges);
308  eliminate = TRUE;
309  SCIPsortReal(costrev, nedges);
310 
311  obj = costrev[nedges - nrealelims];
312 
313  if( SCIPisLT(scip, obj, 0.0) )
314  obj = 0.0;
315  }
316  else
317  {
318  obj = costrev[nedges - nrealelims] - 2 * SCIPepsilon(scip);
319 
320  if( SCIPisLT(scip, obj, 0.0) )
321  obj = 0.0;
322 
323  eliminate = TRUE;
324  }
325 
326  {
327  /* traverse all nodes, try to eliminate each node or incident edges */
328  for( int k = 0; k < nnodes; k++ )
329  {
330  if( (*nelims) >= minelims )
331  break;
332  if( root == k )
333  continue;
334 
335  if( (!graph->mark[k] && (pc)) || graph->grad[k] == 0 )
336  continue;
337 
338  tmpcost = vnoi[k].dist + vnoi[k + nnodes].dist + bound;
339 
340  /* can node k be deleted? */
341  if( !Is_term(graph->term[k]) && (!eliminate || SCIPisGT(scip, tmpcost, obj)) && solnode[k] != CONNECT )
342  {
343  /* delete all incident edges */
344  if( eliminate )
345  {
346  while( graph->outbeg[k] != EAT_LAST )
347  {
348  const int e = graph->outbeg[k];
349  (*nelims)++;
350 
351  assert(!pc || graph->tail[e] != graph->source);
352  assert(!pc || graph->mark[graph->head[e]]);
353  assert(!Is_pseudoTerm(graph->term[graph->head[e]]));
354  assert(!Is_pseudoTerm(graph->term[graph->tail[e]]));
355 
356  graph_edge_del(scip, graph, e, TRUE);
357  }
358  }
359  else
360  {
361  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
362  {
363  if( SCIPisGT(scip, tmpcost, costrev[e]) )
364  {
365  costrev[e] = tmpcost;
366  costrev[flipedge(e)] = tmpcost;
367  }
368  }
369  }
370  }
371  else
372  {
373  int e = graph->outbeg[k];
374  while( e != EAT_LAST )
375  {
376  const int etemp = graph->oeat[e];
377  const int tail = graph->tail[e];
378  const int head = graph->head[e];
379 
380  if( tail > head )
381  {
382  e = etemp;
383  continue;
384  }
385 
386  if( soledge[e] == CONNECT || soledge[flipedge(e)] == CONNECT )
387  {
388  e = etemp;
389  continue;
390  }
391 
392  tmpcost = graph->cost[e] + bound;
393 
394  if( vbase[tail] != vbase[head] )
395  {
396  tmpcost += vnoi[head].dist + vnoi[tail].dist;
397  }
398  else
399  {
400  if( SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
401  tmpcost += vnoi[tail + nnodes].dist + vnoi[head].dist;
402  else
403  tmpcost += vnoi[tail].dist + vnoi[head + nnodes].dist;
404 
405  assert(SCIPisGE(scip, tmpcost, vnoi[head].dist + vnoi[tail].dist + graph->cost[e] + bound));
406  }
407  /* can edge e or arc e be deleted? */
408  if( (!eliminate || SCIPisGT(scip, tmpcost, obj))
409  && SCIPisLT(scip, graph->cost[e], FARAWAY) && (!(pc) || graph->mark[head]) )
410  {
411  assert(!Is_pseudoTerm(graph->term[head]));
412  assert(!Is_pseudoTerm(graph->term[tail]));
413 
414  if( eliminate )
415  {
416  graph_edge_del(scip, graph, e, TRUE);
417  (*nelims)++;
418  }
419  else if( SCIPisGT(scip, tmpcost, costrev[e]) )
420  {
421  costrev[e] = tmpcost;
422  costrev[flipedge(e)] = tmpcost;
423  }
424  }
425  e = etemp;
426  }
427  }
428  }
429 #if 1
430  /* traverse all nodes, try to eliminate 3,4 degree nodes */
431  for( int k = 0; k < nnodes; k++ )
432  {
433  if( (*nelims) >= minelims )
434  break;
435 
436  if( (!graph->mark[k] && pc) || graph->grad[k] <= 0 )
437  continue;
438 
439  if( solnode[k] == CONNECT )
440  continue;
441 
442  if( !eliminate )
443  {
444  if( graph->grad[k] >= 3 && graph->grad[k] <= 4 && !Is_term(graph->term[k]) )
445  {
446  tmpcost = vnoi[k].dist + vnoi[k + nnodes].dist + vnoi[k + 2 * nnodes].dist + radiim3;
447  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
448  {
449  if( SCIPisGT(scip, tmpcost, costrev[e]) )
450  {
451  costrev[e] = tmpcost;
452  costrev[flipedge(e)] = tmpcost;
453  }
454  }
455  }
456  continue;
457  }
458 
459  if( graph->grad[k] >= 3 && graph->grad[k] <= 4 && !Is_term(graph->term[k]) )
460  {
461  tmpcost = vnoi[k].dist + vnoi[k + nnodes].dist + vnoi[k + 2 * nnodes].dist + radiim3;
462  if( SCIPisGT(scip, tmpcost, obj) )
463  {
464  SCIP_Bool success;
465 
466  SCIP_CALL( graph_knot_delPseudo(scip, graph, graph->cost, NULL, NULL, k, NULL, &success) );
467 
468  assert(graph->grad[k] == 0 || (graph->grad[k] == 4 && !success));
469 
470  if( success )
471  (*nelims)++;
472  }
473  }
474  }
475  }
476 #endif
477  } /* redrounds */
478 
479  SCIPdebugMessage("nelims (edges) in bound reduce: %d,\n", *nelims);
480 
481  return SCIP_OKAY;
482 }
483 
484 
485 /** heuristic bound-based reductions for (R)MWCS */
486 static
488  SCIP* scip, /**< SCIP data structure */
489  GRAPH* graph, /**< graph data structure */
490  PATH* vnoi, /**< Voronoi data structure */
491  SCIP_Real* cost, /**< edge cost array */
492  SCIP_Real* radius, /**< radius array */
493  SCIP_Real* costrev, /**< reversed edge cost array */
494  SCIP_Real* offset, /**< pointer to the offset */
495  int* heap, /**< heap array */
496  int* state, /**< array to store state of a node during Voronoi computation */
497  int* vbase, /**< Voronoi base to each node */
498  const int* solnode, /**< array of nodes of current solution that is not to be destroyed */
499  const int* soledge, /**< array of edges of current solution that is not to be destroyed */
500  int* nelims, /**< pointer to store number of eliminated edges */
501  int minelims /**< minimum number of edges to be eliminated */
502  )
503 {
504  SCIP_Real obj;
505  SCIP_Real tmpcost;
506  const int root = graph->source;
507  const int nnodes = graph->knots;
508  const int nedges = graph->edges;
509  const int nterms = graph->terms - ( (graph->stp_type == STP_MWCSP) ? 1 : 0 );
510  SCIP_Bool eliminate;
511 
512  assert(graph_pc_isMw(graph));
513  assert(graph->source >= 0);
514  assert(graph_valid(scip, graph));
515  assert(!graph->extended);
516 
517  *nelims = 0;
518 
519  if( nterms <= 2 )
520  return SCIP_OKAY;
521 
522  graph_getEdgeCosts(graph, cost, costrev);
523  graph_voronoiMw(scip, graph, costrev, vnoi, vbase, heap, state);
524  graph_add2ndTermPaths(graph, cost, costrev, vnoi, vbase, state);
525 
526  for( int e = 0; e < nedges; e++ )
527  costrev[e] = FARAWAY;
528 
529  for( int redrounds = 0; redrounds < 3; redrounds++ )
530  {
531  int nrealelims = MIN(2 * minelims, nedges - 1);
532 
533  if( redrounds == 0 )
534  {
535  eliminate = FALSE;
536  obj = FARAWAY;
537  }
538  else if( redrounds == 1 )
539  {
540  assert(minelims > 0);
541  assert(2 * minelims < nedges);
542  eliminate = TRUE;
543  SCIPsortReal(costrev, nedges);
544 
545  obj = costrev[nrealelims];
546  }
547  else
548  {
549  obj = costrev[nrealelims] + 2 * SCIPepsilon(scip);
550 
551  eliminate = TRUE;
552  }
553 
554  for( int k = 0; k < nnodes; k++ )
555  {
556  if( (*nelims) >= minelims )
557  break;
558 
559  if( root == k )
560  continue;
561 
562  if( !graph->mark[k] || graph->grad[k] == 0 || Is_anyTerm(graph->term[k] ) )
563  continue;
564 
565  tmpcost = -vnoi[k].dist - vnoi[k + nnodes].dist + graph->prize[k];
566 
567  if( (!eliminate || SCIPisLT(scip, tmpcost, obj)) && solnode[k] != CONNECT )
568  {
569  if( eliminate )
570  {
571  while (graph->outbeg[k] != EAT_LAST)
572  {
573  (*nelims)++;
574  graph_edge_del(scip, graph, graph->outbeg[k], TRUE);
575  }
576  }
577  else
578  {
579  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
580  {
581  if( SCIPisLT(scip, tmpcost, costrev[e]) )
582  {
583  costrev[e] = tmpcost;
584  costrev[flipedge(e)] = tmpcost;
585  }
586  }
587  }
588  }
589  else if( solnode[k] == CONNECT )
590  {
591  int e = graph->outbeg[k];
592 
593  while( e != EAT_LAST )
594  {
595  const int etemp = graph->oeat[e];
596  const int tail = graph->tail[e];
597  const int head = graph->head[e];
598 
599  if( tail > head || soledge[e] == CONNECT || soledge[flipedge(e)] == CONNECT )
600  {
601  e = etemp;
602  continue;
603  }
604 
605  tmpcost = graph->prize[head] + graph->prize[tail];
606 
607  if( vbase[tail] != vbase[head] )
608  {
609  tmpcost -= vnoi[head].dist + vnoi[tail].dist;
610  }
611  else
612  {
613  if( SCIPisGT(scip, -vnoi[tail].dist -vnoi[head + nnodes].dist, -vnoi[tail + nnodes].dist -vnoi[head].dist) )
614  tmpcost -= vnoi[tail].dist + vnoi[head + nnodes].dist;
615  else
616  tmpcost -= vnoi[tail + nnodes].dist + vnoi[head].dist;
617  }
618  /* can edge e or arc e be deleted? */
619  if( (!eliminate || SCIPisLT(scip, tmpcost, obj))
620  && SCIPisLT(scip, graph->cost[e], FARAWAY) && (graph->mark[head]) )
621  {
622  assert(!Is_pseudoTerm(graph->term[head]));
623  assert(!Is_pseudoTerm(graph->term[tail]));
624 
625  if( eliminate )
626  {
627  graph_edge_del(scip, graph, e, TRUE);
628  (*nelims)++;
629  }
630  else if( SCIPisLT(scip, tmpcost, costrev[e]) )
631  {
632  costrev[e] = tmpcost;
633  costrev[flipedge(e)] = tmpcost;
634  }
635 
636  }
637  e = etemp;
638  }
639  }
640  }
641  } /* redrounds */
642 
643  SCIPdebugMessage("nelims (edges) in bound reduce: %d,\n", *nelims);
644 
645  return SCIP_OKAY;
646 }
647 
648 
649 /*
650  * Interface methods
651  */
652 
653 
654 /** bound-based reductions for the (R)PCSTP, the MWCSP and the STP */
656  SCIP* scip, /**< SCIP data structure */
657  GRAPH* graph, /**< graph data structure */
658  PATH* vnoi, /**< Voronoi data structure */
659  SCIP_Real* radius, /**< radius array */
660  SCIP_Real* offset, /**< pointer to the offset */
661  SCIP_Real* upperbound, /**< pointer to an upper bound */
662  int* heap, /**< heap array */
663  int* state, /**< array to store state of a node during Voronoi computation*/
664  int* vbase, /**< Voronoi base to each node */
665  int* nelims /**< pointer to store number of eliminated edges */
666  )
667 {
668  GRAPH* adjgraph = NULL;
669  PATH* mst = NULL;
670  SCIP_Real* prize = NULL;
671  SCIP_Real* cost = NULL;
672  SCIP_Real* costrev = NULL;
673  SCIP_Real r;
674  SCIP_Real obj;
675  SCIP_Real max;
676  SCIP_Real radii;
678  SCIP_Real tmpcost;
679  SCIP_Real mstobj;
680  SCIP_Real mstobj2;
681  SCIP_Real radiim2;
682  SCIP_Real radiim3;
683  int* perm = NULL;
684  int* result = NULL;
685  int e;
686  int nterms;
687  const int nnodes = graph_get_nNodes(graph);
688  const int nedges = graph_get_nEdges(graph);
689  STP_Bool* stnode = NULL;
690  SCIP_Bool hasInitialUb;
691  const SCIP_Bool pc = graph_pc_isPc(graph);
692  const SCIP_Bool pcmw = graph_pc_isPcMw(graph);
693  SCIP_Bool success = TRUE;
694 
695  assert(scip && nelims);
696  assert(graph->source >= 0);
697  assert(upperbound != NULL);
698  assert(graph->stp_type != STP_MWCSP);
699  assert(graph->stp_type != STP_RMWCSP);
700 
701  obj = FARAWAY;
702  mstobj = 0.0;
703  *nelims = 0;
704  mstobj2 = 0.0;
705  hasInitialUb = GT(*upperbound, 0.0) && LT(*upperbound, FARAWAY);
706 
707  graph_mark(graph);
708 
709  if( pcmw )
710  prize = graph->prize;
711 
712  if( graph->terms <= 2 )
713  return SCIP_OKAY;
714 
715  if( graph->grad[graph->source] == 0 )
716  return SCIP_OKAY;
717 
718  nterms = (graph->terms - ((graph->stp_type == STP_PCSPG)? 1 : 0));
719 
720  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
721  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
722 
723  graph_getEdgeCosts(graph, cost, costrev);
724 
725  /* init auxiliary graph */
726  SCIP_CALL( graph_init(scip, &adjgraph, nterms, MIN(nedges, (nterms - 1) * nterms), 1) );
727 
728  /* build voronoi regions, concomitantly building adjgraph and computing radii values*/
729  SCIP_CALL( graph_voronoiWithRadius(scip, graph, adjgraph, vnoi, radius, cost, costrev, vbase, heap, state) );
730  graph_add2ndTermPaths(graph, cost, costrev, vnoi, vbase, state);
731  graph_add3rdTermPaths(graph, cost, costrev, vnoi, vbase, state);
732 
733  if( pc )
734  graph_add4thTermPaths(graph, cost, costrev, vnoi, vbase, state);
735 
736  assert(adjgraph != NULL);
737  graph_knot_chg(adjgraph, 0, 0);
738  adjgraph->source = 0;
739 
740  /* compute MST on adjgraph */
741  SCIP_CALL( SCIPallocBufferArray(scip, &mst, nterms) );
742  SCIP_CALL( graph_path_init(scip, adjgraph) );
743  graph_path_exec(scip, adjgraph, MST_MODE, 0, adjgraph->cost, mst);
744 
745  max = -1.0;
746  r = -1.0;
747  for( int k = 1; k < nterms; k++ )
748  {
749  assert(adjgraph->path_state[k] == CONNECT); /* basically asserts that adjgraph is connected */
750 
751  e = mst[k].edge;
752  assert(e >= 0);
753  tmpcost = adjgraph->cost[e];
754  mstobj += tmpcost;
755  if( SCIPisGT(scip, tmpcost, max) )
756  max = tmpcost;
757  else if( SCIPisGT(scip, tmpcost, r) )
758  r = tmpcost;
759  }
760 
761  mstobj -= max;
762  mstobj2 = mstobj - r;
763 
764  /* for (rooted) prize collecting an maximum weight problems: correct radius values */
765  if( graph->stp_type == STP_RPCSPG )
766  {
767  assert(graph->mark[graph->source]);
768  for( int k = 0; k < nnodes; k++ )
769  {
770  if( !Is_term(graph->term[k]) || !graph->mark[k] )
771  continue;
772 
773  if( SCIPisGT(scip, radius[k], prize[k]) && k != graph->source )
774  radius[k] = prize[k];
775  }
776  }
777  else if( graph->stp_type == STP_PCSPG )
778  {
779  for( int k = 0; k < nnodes; k++ )
780  {
781  if( !graph->mark[k] )
782  continue;
783 
784  if( Is_term(graph->term[k]) && SCIPisGT(scip, radius[k], prize[k]) )
785  radius[k] = prize[k];
786  }
787  }
788 
789  /* sort radius values */
790  if( pc )
791  {
792  SCIP_CALL( SCIPallocBufferArray(scip, &perm, nnodes) );
793  for( int k = 0; k < nnodes; k++ )
794  perm[k] = k;
795 
796  SCIPsortRealInt(radius, perm, nnodes);
797  }
798  else
799  {
800  SCIPsortReal(radius, nnodes);
801  }
802 
803  radiim2 = 0.0;
804 
805  /* sum all but two radius values of highest/lowest value */
806  for( int k = 0; k < nterms - 2; k++ )
807  {
808  assert( SCIPisGT(scip, FARAWAY, radius[k]) );
809  radiim2 += radius[k];
810  }
811 
812  radii = radiim2 + radius[nterms - 2] + radius[nterms - 1];
813 
814  if( nterms >= 3 )
815  radiim3 = radiim2 - radius[nterms - 3];
816  else
817  radiim3 = 0;
818 
819  /* no upper bound available? */
820  if( !hasInitialUb )
821  {
822  SCIP_CALL( SCIPallocBufferArray(scip, &stnode, nnodes) );
823  SCIP_CALL( SCIPallocBufferArray(scip, &result, nedges) );
824 
825  SCIP_CALL( computeSteinerTree(scip, graph, cost, costrev, result, stnode, &obj, &success) );
826 
827  if( !success )
828  {
829  assert(graph->stp_type == STP_DHCSTP);
830 
831  /* free memory and return */
832  graph_path_exit(scip, adjgraph);
833  graph_free(scip, &adjgraph, TRUE);
834  SCIPfreeBufferArrayNull(scip, &mst);
835  SCIPfreeBufferArrayNull(scip, &result);
836  SCIPfreeBufferArrayNull(scip, &stnode);
837  SCIPfreeBufferArray(scip, &costrev);
838  SCIPfreeBufferArray(scip, &cost);
839 
840 
841  return SCIP_OKAY;
842  }
843 
844  *upperbound = obj;
845  }
846  else
847  {
848  obj = *upperbound;
849  assert(SCIPisGE(scip, obj, 0.0));
850  }
851 
852  assert(SCIPisLT(scip, obj, FARAWAY));
853 
854  if( SCIPisGT(scip, radiim2, mstobj) )
855  {
856  SCIPdebugMessage("select radii bound \n");
857 
858  bound = radiim2;
859  }
860  else
861  {
862  SCIPdebugMessage("select MST bound \n");
863 
864  bound = mstobj;
865  }
866 
867  SCIPdebugMessage("bound=%f obj=%f \n", bound, obj);
868 
869  assert(SCIPisLE(scip, bound, obj));
870 
871  /* traverse all node, try to eliminate each node or incident edges */
872  for( int k = 0; k < nnodes; k++ )
873  {
874  if( (!graph->mark[k] && pcmw) || graph->grad[k] == 0 )
875  continue;
876 
877  tmpcost = vnoi[k].dist + vnoi[k + nnodes].dist + bound;
878 
879  /* can node k be deleted? */
880  if( !Is_term(graph->term[k]) && (SCIPisGT(scip, tmpcost, obj)
881  || (((stnode != NULL) ? !stnode[k] : 0) && SCIPisGE(scip, tmpcost, obj))) )
882  {
883  /* delete all incident edges */
884  while( graph->outbeg[k] != EAT_LAST )
885  {
886  e = graph->outbeg[k];
887  (*nelims)++;
888  assert(!pc || graph->tail[e] != graph->source);
889  assert(!pc || graph->mark[graph->head[e]]);
890  assert(!Is_pseudoTerm(graph->term[graph->head[e]]));
891  assert(!Is_pseudoTerm(graph->term[graph->tail[e]]));
892 
893  SCIPdebugMessage("delete non-terminal edge \n");
894 
895  graph_edge_del(scip, graph, e, TRUE);
896  }
897  }
898  else
899  {
900  e = graph->outbeg[k];
901  while( e != EAT_LAST )
902  {
903  const int etemp = graph->oeat[e];
904  const int tail = graph->tail[e];
905  const int head = graph->head[e];
906  tmpcost = graph->cost[e] + bound;
907 
908  if( vbase[tail] != vbase[head] )
909  {
910  tmpcost += vnoi[head].dist + vnoi[tail].dist;
911  }
912  else
913  {
914  if( SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
915  tmpcost += vnoi[tail + nnodes].dist + vnoi[head].dist;
916  else
917  tmpcost += vnoi[tail].dist + vnoi[head + nnodes].dist;
918 
919  assert(SCIPisGE(scip, tmpcost, vnoi[head].dist + vnoi[tail].dist + graph->cost[e] + bound));
920  }
921  /* can edge e or arc e be deleted? */
922  if( (SCIPisGT(scip, tmpcost, obj) || (((result != NULL) ? (result[e] != CONNECT) : 0) && result[flipedge(e)] != CONNECT && SCIPisGE(scip, tmpcost, obj)))
923  && SCIPisLT(scip, graph->cost[e], FARAWAY) && (!pc || graph->mark[head]) )
924  {
925  if( graph->stp_type == STP_DHCSTP && SCIPisGT(scip, graph->cost[e], graph->cost[flipedge(e)]) )
926  {
927  graph->cost[e] = FARAWAY;
928  (*nelims)++;
929  }
930  else
931  {
932  assert(!Is_pseudoTerm(graph->term[head]));
933  assert(!Is_pseudoTerm(graph->term[tail]));
934 
935  SCIPdebugMessage("delete terminal edge \n");
936 
937  graph_edge_del(scip, graph, e, TRUE);
938  (*nelims)++;
939  }
940  }
941  e = etemp;
942  }
943  }
944  }
945 #if 1
946  /* traverse all node, try to eliminate 3 degree nodes */
947  for( int k = 0; k < nnodes; k++ )
948  {
949  if( (!graph->mark[k] && pc) || graph->grad[k] == 0 )
950  continue;
951 
952  if( (graph->grad[k] == 3 || graph->grad[k] == 4) && !Is_term(graph->term[k]) )
953  {
954  tmpcost = vnoi[k].dist + vnoi[k + nnodes].dist + vnoi[k + 2 * nnodes].dist + radiim3;
955  if( SCIPisGT(scip, tmpcost, obj) )
956  {
957 #if 0
958  printf("pseudo-delete non-terminal node \n");
959  graph_knot_printInfo(graph, k);
960  graph_printInfo(graph);
961 #endif
962 
963  SCIP_CALL( graph_knot_delPseudo(scip, graph, graph->cost, NULL, NULL, k, NULL, &success) );
964 
965  assert(graph->grad[k] == 0 || (graph->grad[k] == 4 && !success));
966  }
967  }
968  }
969 #endif
970 
971  /* for(R)PC: try to eliminate terminals */
972  if( pc )
973  {
974  assert(!graph->extended);
975 
976  SCIP_CALL( graph_get4nextTTerms(scip, graph, cost, vnoi, vbase, heap, state) );
977 
978  for( int k = 0; k < nnodes; k++ )
979  {
980  /* is k a terminal other than the root? */
981  if( Is_term(graph->term[k]) && graph->mark[k] && graph->grad[k] > 2 && !graph_pc_knotIsFixedTerm(graph, k) )
982  {
983  int l;
984  assert(graph->source != k);
985 
986  assert(perm != NULL);
987  for( l = 0; l < nterms; l++ )
988  if( perm[l] == k )
989  break;
990 
991  tmpcost = vnoi[k].dist + radii - radius[l];
992 
993  if( l == nterms - 1 )
994  tmpcost -= radius[nterms - 2];
995  else
996  tmpcost -= radius[nterms - 1];
997 
998 
999  if( SCIPisGT(scip, tmpcost, obj) )
1000  {
1001  SCIPdebugMessage("alternative bnd elimination! \n\n");
1002 
1003  (*nelims) += graph_pc_deleteTerm(scip, graph, k, offset);
1004  }
1005  else
1006  {
1007  tmpcost += vnoi[k + nnodes].dist;
1008  if( l >= nterms - 2 )
1009  tmpcost -= radius[nterms - 3];
1010  else
1011  tmpcost -= radius[nterms - 2];
1012  if( SCIPisGT(scip, tmpcost, obj) || SCIPisGT(scip, mstobj2 + vnoi[k].dist + vnoi[k + nnodes].dist, obj) )
1013  {
1014  for( e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
1015  if( graph->mark[graph->head[e]] && SCIPisLT(scip, graph->cost[e], graph->prize[k]) )
1016  break;
1017 
1018  if( e == EAT_LAST )
1019  {
1020  SCIPdebugMessage("second elimination! prize: %f \n\n", graph->prize[k]);
1021  (*nelims) += graph_pc_deleteTerm(scip, graph, k, offset);
1022  }
1023  }
1024  }
1025  }
1026  }
1027  }
1028 
1029  SCIPdebugMessage("nelims (edges) in bound reduce: %d,\n", *nelims);
1030 
1031  /* free adjgraph */
1032  graph_path_exit(scip, adjgraph);
1033  graph_free(scip, &adjgraph, TRUE);
1034 
1035  /* free memory*/
1036  SCIPfreeBufferArrayNull(scip, &perm);
1037  SCIPfreeBufferArrayNull(scip, &mst);
1038  SCIPfreeBufferArrayNull(scip, &stnode);
1039  SCIPfreeBufferArrayNull(scip, &result);
1040  SCIPfreeBufferArray(scip, &costrev);
1041  SCIPfreeBufferArray(scip, &cost);
1042 
1043  assert(graph_valid(scip, graph));
1044 
1045  return SCIP_OKAY;
1046 }
1047 
1048 
1049 
1050 
1051 /** Bound-based reduction method for the MWCSP .
1052  * The reduction method tries to eliminate nodes and vertices
1053  * by checking whether an upper bound for each solution that contains them
1054  * is smaller than the best known solution value.
1055  * The essence of the approach is a decomposition of the graph such that this upper bound
1056  * is minimized.
1057  * */
1059  SCIP* scip, /**< SCIP data structure */
1060  GRAPH* graph, /**< graph data structure */
1061  PATH* vnoi, /**< Voronoi data structure (size 3 * nnodes) */
1062  SCIP_Real* offset, /**< pointer to the offset */
1063  int* heap, /**< heap array */
1064  int* state, /**< array to store state of a node during Voronoi computation*/
1065  int* vbase, /**< Voronoi base to each node */
1066  int* result, /**< solution array or NULL */
1067  int* nelims /**< pointer to store number of eliminated edges */
1068  )
1069 {
1070  PATH* path;
1071  PATH* mst;
1072  SCIP_Real* costrev;
1073  SCIP_Real* prize;
1074  SCIP_Real* radius;
1075  SCIP_Real* cost;
1076  SCIP_Real obj;
1077  SCIP_Real bound;
1078  SCIP_Real tmpcost;
1079  SCIP_Real radiim2;
1080  int e;
1081  int k;
1082  int head;
1083  int nterms;
1084  int nnodes;
1085  int nedges;
1086 
1087  assert(scip != NULL);
1088  assert(graph != NULL);
1089  assert(vnoi != NULL);
1090  assert(heap != NULL);
1091  assert(state != NULL);
1092  assert(vbase != NULL);
1093  assert(nelims != NULL);
1094  assert(graph->source >= 0);
1095 
1096  mst = NULL;
1097  prize = graph->prize;
1098  nedges = graph->edges;
1099  nnodes = graph->knots;
1100  nterms = graph->terms - 1;
1101  *nelims = 0;
1102 
1103  assert(prize != NULL);
1104 
1105  /* not more than two nodes of positive weight? */
1106  if( nterms <= 2 )
1107  return SCIP_OKAY;
1108 
1109  /* not promising and does probably not work without modifications of the code */
1110  if( graph_pc_isRootedPcMw(graph) )
1111  return SCIP_OKAY;
1112 
1113  SCIP_CALL( SCIPallocBufferArray(scip, &radius, nnodes + 1) );
1114  SCIP_CALL( SCIPallocBufferArray(scip, &path, nnodes + 1) );
1115  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
1116  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
1117 
1118  /* initialize cost and costrev array */
1119  for( e = 0; e < nedges; e++ )
1120  {
1121  cost[e] = graph->cost[e];
1122  costrev[e] = graph->cost[flipedge(e)];
1123 
1124  assert(SCIPisGE(scip, cost[e], 0.0));
1125  }
1126 
1127  /* compute decomposition of graph and radius values */
1128  graph_voronoiWithRadiusMw(scip, graph, path, cost, radius, vbase, heap, state);
1129 
1130  /* sum all radius values, exclude two radius values of lowest value */
1131  for( k = 0; k < nnodes; k++ )
1132  {
1133  if( !Is_term(graph->term[k]) || !graph->mark[k] )
1134  continue;
1135 
1136  assert(vbase[k] == k);
1137  assert(SCIPisGE(scip, prize[k], 0.0));
1138 
1139  if( SCIPisGE(scip, radius[k], FARAWAY) )
1140  radius[k] = 0.0;
1141  else
1142  {
1143  if( SCIPisGE(scip, radius[k], prize[k] ) )
1144  radius[k] = 0.0;
1145  else
1146  radius[k] = prize[k] - radius[k];
1147  }
1148  }
1149 
1150  for( k = 0; k < nnodes; k++ )
1151  {
1152  if( !graph->mark[k] || graph->grad[k] == 0 || Is_term(graph->term[k]) )
1153  continue;
1154  }
1155 
1156  /* build Voronoi regions */
1157  graph_voronoiMw(scip, graph, costrev, vnoi, vbase, heap, state);
1158 
1159  /* get 2nd next positive node to all non-positive nodes */
1160  graph_add2ndTermPaths(graph, cost, costrev, vnoi, vbase, state);
1161 
1162  for( k = 0; k < nnodes; k++ )
1163  {
1164  if( !Is_term(graph->term[k]) || !graph->mark[k] )
1165  continue;
1166 
1167  assert(vbase[k] == k);
1168  }
1169 
1170  SCIPsortReal(radius, nnodes);
1171 
1172  radiim2 = 0.0;
1173 
1174  for( k = 2; k < nterms; k++ )
1175  {
1176  assert( SCIPisGT(scip, FARAWAY, radius[k]) );
1177  radiim2 += radius[k];
1178  }
1179 
1180  /* solution available? */
1181  if( result != NULL)
1182  {
1183  /* calculate objective value of solution */
1184  obj = 0.0;
1185  for( e = 0; e < nedges; e++ )
1186  {
1187  if( result[e] == CONNECT )
1188  {
1189  head = graph->head[e];
1190 
1191  if( graph->mark[head] )
1192  obj += prize[head];
1193  }
1194  }
1195  }
1196  else
1197  {
1198  obj = 0.0;
1199  }
1200 
1201  bound = radiim2;
1202 
1203  /* traverse all nodes, try to eliminate each non-positive node */
1204  for( k = 0; k < nnodes; k++ )
1205  {
1206  if( !graph->mark[k] || graph->grad[k] == 0 || Is_term(graph->term[k]) )
1207  continue;
1208 
1209  assert(SCIPisLE(scip, graph->prize[k], 0.0));
1210 
1211  tmpcost = -vnoi[k].dist - vnoi[k + nnodes].dist + bound + graph->prize[k];
1212 
1213  if( (SCIPisLT(scip, tmpcost, obj)) )
1214  {
1215  while( graph->outbeg[k] != EAT_LAST )
1216  {
1217  (*nelims)++;
1218  graph_edge_del(scip, graph, graph->outbeg[k], TRUE);
1219  }
1220  }
1221  }
1222 
1223  SCIPdebugMessage("nelims (edges) in MWCSP bound reduce: %d,\n", *nelims);
1224 
1225  SCIPfreeBufferArrayNull(scip, &mst);
1226  SCIPfreeBufferArray(scip, &cost);
1227  SCIPfreeBufferArray(scip, &costrev);
1228  SCIPfreeBufferArray(scip, &path);
1229  SCIPfreeBufferArray(scip, &radius);
1230 
1231  return SCIP_OKAY;
1232 }
1233 
1234 
1235 
1236 /** heuristic bound-based reductions for the (R)PCSTP, the MWCSP and the STP; used by prune heuristic */
1238  SCIP* scip, /**< SCIP data structure */
1239  GRAPH* graph, /**< graph data structure */
1240  PATH* vnoi, /**< Voronoi data structure */
1241  SCIP_Real* cost, /**< edge cost array */
1242  SCIP_Real* radius, /**< radius array */
1243  SCIP_Real* costrev, /**< reversed edge cost array */
1244  SCIP_Real* offset, /**< pointer to the offset */
1245  int* heap, /**< heap array */
1246  int* state, /**< array to store state of a node during Voronoi computation */
1247  int* vbase, /**< Voronoi base to each node */
1248  const int* solnode, /**< array of nodes of current solution that is not to be destroyed */
1249  const int* soledge, /**< array of edges of current solution that is not to be destroyed */
1250  int* nelims, /**< pointer to store number of eliminated edges */
1251  int minelims /**< minimum number of edges to be eliminated */
1252  )
1253 {
1254  assert(scip != NULL);
1255  assert(vnoi != NULL);
1256  assert(cost != NULL);
1257  assert(heap != NULL);
1258  assert(graph != NULL);
1259  assert(state != NULL);
1260  assert(vbase != NULL);
1261  assert(nelims != NULL);
1262  assert(radius != NULL);
1263  assert(costrev != NULL);
1264  assert(solnode != NULL);
1265  assert(soledge != NULL);
1266  assert(graph->source >= 0);
1267  assert(graph_valid(scip, graph));
1268  assert(!graph->extended);
1269 
1270  if( graph_pc_isMw(graph) )
1271  {
1272  SCIP_CALL( boundPruneHeurMw(scip, graph, vnoi, cost, radius, costrev, offset, heap, state, vbase, solnode, soledge, nelims, minelims) );
1273  }
1274  else
1275  {
1276  SCIP_CALL( boundPruneHeur(scip, graph, vnoi, cost, radius, costrev, offset, heap, state, vbase, solnode, soledge, nelims, minelims) );
1277  }
1278 
1279  SCIPdebugMessage("nelims (edges) in bound reduce: %d,\n", *nelims);
1280 
1281  return SCIP_OKAY;
1282 }
1283 
1284 
1285 /** dual ascent based hop reductions for HCDSTP */
1287  SCIP* scip, /**< SCIP data structure */
1288  GRAPH* graph, /**< graph data structure */
1289  int* nelims, /**< pointer to store number of reduced edges */
1290  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
1291 )
1292 {
1293  const RPDA paramsda = { .damode = STP_DAMODE_HOPS, .useSlackPrune = FALSE, .useRec = FALSE, .extredMode = extred_none,
1294  .nodereplacing = FALSE};
1295  SCIP_Real* orgcosts;
1296  SCIP_Real fixed = 0.0;
1297  const int nedges = graph_get_nEdges(graph);
1298 
1299  SCIP_CALL( SCIPallocBufferArray(scip, &orgcosts, nedges) );
1300  BMScopyMemoryArray(orgcosts, graph->cost, nedges);
1301 
1302  for( int i = 0; i < nedges; i++ )
1303  {
1304  if( LT(graph->cost[i], FARAWAY) )
1305  graph->cost[i] = 1.0;
1306  }
1307 
1308  SCIP_CALL( reduce_da(scip, graph, &paramsda, NULL, &fixed, nelims, randnumgen) );
1309  assert(EQ(fixed, 0.0));
1310 
1311  BMScopyMemoryArray(graph->cost, orgcosts, nedges);
1312 
1313  SCIPfreeBufferArray(scip, &orgcosts);
1314 
1315  assert(graph_valid(scip, graph));
1316  SCIP_CALL( reduce_unconnectedForDirected(scip, graph) );
1317 
1318  return SCIP_OKAY;
1319 }
1320 
1321 
1322 /** bound-based reduction test for the HCDSTP */
1324  SCIP* scip,
1325  GRAPH* graph,
1326  PATH* vnoi,
1327  SCIP_Real* cost,
1328  SCIP_Real* radius,
1329  SCIP_Real* costrev,
1330  int* heap,
1331  int* state,
1332  int* vbase,
1333  int* nelims
1334  )
1335 {
1336  SCIP_Real max;
1337  SCIP_Real tmpcost;
1338  SCIP_Real bound;
1339  SCIP_Real mstobj;
1340  SCIP_Real radiim2;
1341 
1342  GRAPH* adjgraph;
1343  PATH* mst;
1344  int e;
1345  int k;
1346  int tail;
1347  int head;
1348  int etemp;
1349  int nnodes;
1350  int nedges;
1351  int nterms;
1352  SCIP_Real hoplimit;
1353 
1354  assert(scip != NULL);
1355  assert(graph != NULL);
1356  assert(vnoi != NULL);
1357  assert(cost != NULL);
1358  assert(radius != NULL);
1359  assert(costrev != NULL);
1360  assert(heap != NULL);
1361  assert(state != NULL);
1362  assert(vbase != NULL);
1363  assert(nelims != NULL);
1364 
1365  *nelims = 0;
1366  nterms = 0;
1367  nedges = graph->edges;
1368  nnodes = graph->knots;
1369 
1370  for( k = 0; k < nnodes; k++ )
1371  {
1372  graph->mark[k] = (graph->grad[k] > 0);
1373  if( graph->mark[k] && Is_term(graph->term[k]) )
1374  nterms++;
1375  }
1376 
1377  for( e = 0; e < nedges; e++ )
1378  {
1379  if( SCIPisLT(scip, graph->cost[e], FARAWAY) )
1380  cost[e] = 1.0;
1381  else
1382  cost[e] = FARAWAY;
1383  if( SCIPisLT(scip, graph->cost[flipedge(e)], FARAWAY) )
1384  costrev[e] = 1.0;
1385  else
1386  costrev[e] = FARAWAY;
1387  }
1388 
1389  /* init auxiliary graph */
1390  SCIP_CALL( graph_init(scip, &adjgraph, nterms, MIN(nedges, (nterms - 1) * nterms), 1) );
1391 
1392  SCIP_CALL( graph_voronoiWithRadius(scip, graph, adjgraph, vnoi, radius, cost, costrev, vbase, heap, state) );
1393 
1394  /* get 2nd next terminals to all nodes */
1395  graph_add2ndTermPaths(graph, cost, costrev, vnoi, vbase, state);
1396 
1397  /* compute MST on adjgraph */
1398  graph_knot_chg(adjgraph, 0, 0);
1399  adjgraph->source = 0;
1400  assert(graph_valid(scip, adjgraph));
1401  SCIP_CALL( SCIPallocBufferArray(scip, &mst, nterms) );
1402  SCIP_CALL( graph_path_init(scip, adjgraph) );
1403  graph_path_exec(scip, adjgraph, MST_MODE, 0, adjgraph->cost, mst);
1404 
1405  max = -1;
1406  assert(mst[0].edge == -1);
1407  mstobj = 0.0;
1408 
1409  /* compute MST cost ...*/
1410  for( k = 1; k < nterms; k++ )
1411  {
1412  e = mst[k].edge;
1413  assert(adjgraph->path_state[k] == CONNECT);
1414  assert(e >= 0);
1415  tmpcost = adjgraph->cost[e];
1416  mstobj += tmpcost;
1417  if( SCIPisGT(scip, tmpcost, max) )
1418  max = tmpcost;
1419  }
1420  /* ...minus longest edge */
1421  mstobj -= max;
1422 
1423  SCIPsortReal(radius, nnodes);
1424  radiim2 = 0.0;
1425 
1426  for( e = 0; e < nterms - 2; e++ )
1427  {
1428  assert( SCIPisGT(scip, FARAWAY, radius[e]) );
1429  radiim2 += radius[e];
1430  }
1431 
1432  hoplimit = (SCIP_Real) graph->hoplimit;
1433 
1434  if( SCIPisGT(scip, radiim2, mstobj) )
1435  bound = radiim2;
1436  else
1437  bound = mstobj;
1438 
1439  /* traverse all node, try to eliminate first the node and then all incident edges */
1440  for( k = 0; k < nnodes; k++ )
1441  {
1442  /* can node k be deleted? */
1443  if( !Is_term(graph->term[k]) && SCIPisGT(scip, vnoi[k].dist + vnoi[k + nnodes].dist + bound, hoplimit) )
1444  {
1445  e = graph->outbeg[k];
1446 
1447  /* delete incident edges */
1448  while( e != EAT_LAST )
1449  {
1450  assert(e >= 0);
1451  (*nelims)++;
1452  etemp = graph->oeat[e];
1453  graph_edge_del(scip, graph, e, TRUE);
1454  e = etemp;
1455  }
1456  }
1457  else
1458  {
1459  e = graph->outbeg[k];
1460  while( e != EAT_LAST )
1461  {
1462  assert(e >= 0);
1463  tail = graph->tail[e];
1464  head = graph->head[e];
1465  tmpcost = 1.0 + bound;
1466  if( vbase[tail] != vbase[head] )
1467  {
1468  tmpcost += vnoi[head].dist + vnoi[tail].dist;
1469  }
1470  else
1471  {
1472  if( SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
1473  tmpcost += vnoi[tail + nnodes].dist + vnoi[head].dist;
1474  else
1475  tmpcost += vnoi[tail].dist + vnoi[head + nnodes].dist;
1476  // todo reactivate
1477  // assert(SCIPisGE(scip, tmpcost, vnoi[head].dist + vnoi[tail].dist + 1.0 + bound));
1478  }
1479 
1480  /* can edge e (i.e. both arc e and its reverse arc) or arc e be deleted? */
1481  if( SCIPisGT(scip, tmpcost, hoplimit) && SCIPisLT(scip, graph->cost[e], FARAWAY) )
1482  {
1483  etemp = graph->oeat[e];
1484  if( SCIPisGT(scip, graph->cost[e], graph->cost[flipedge(e)]) )
1485  {
1486  graph->cost[e] = FARAWAY;
1487  (*nelims)++;
1488  }
1489  else
1490  {
1491  graph_edge_del(scip, graph, e, TRUE);
1492  (*nelims)++;
1493  }
1494  e = etemp;
1495  }
1496  else
1497  {
1498  e = graph->oeat[e];
1499  }
1500  }
1501  }
1502  }
1503 
1504  SCIPdebugMessage("nelimsX (edges) in hop bound reduce: %d,\n", *nelims);
1505 
1506  /* free adjgraph */
1507  graph_path_exit(scip, adjgraph);
1508  graph_free(scip, &adjgraph, TRUE);
1509 
1510  /* free memory*/
1511  SCIPfreeBufferArray(scip, &mst);
1512  assert(graph_valid(scip, graph));
1513 
1514  return SCIP_OKAY;
1515 }
1516 
1517 /** hop bound-based reduction test for the HCDSTP */
1519  SCIP* scip,
1520  GRAPH* graph,
1521  PATH* vnoi,
1522  SCIP_Real* cost,
1523  SCIP_Real* costrev,
1524  SCIP_Real* pathdist,
1525  int* heap,
1526  int* state,
1527  int* vbase,
1528  int* nelims,
1529  int* pathedge
1530  )
1531 {
1532  SCIP_Real tmpcost;
1533  int e;
1534  int k;
1535  int root;
1536  int head;
1537  int etemp;
1538  int bound;
1539  int nnodes;
1540  int nedges;
1541  int nterms;
1542  int hoplimit;
1543 
1544  assert(scip != NULL);
1545  assert(graph != NULL);
1546  assert(vnoi != NULL);
1547  assert(cost != NULL);
1548  assert(costrev != NULL);
1549  assert(heap != NULL);
1550  assert(state != NULL);
1551  assert(vbase != NULL);
1552  assert(nelims != NULL);
1553 
1554  *nelims = 0;
1555  nterms = 0;
1556  root = graph->source;
1557  nedges = graph->edges;
1558  nnodes = graph->knots;
1559  hoplimit = graph->hoplimit;
1560 
1561  for( k = 0; k < nnodes; k++ )
1562  {
1563  graph->mark[k] = (graph->grad[k] > 0);
1564  if( graph->mark[k] && Is_term(graph->term[k]) )
1565  nterms++;
1566  }
1567  bound = nterms - 2;
1568  for( e = 0; e < nedges; e++ )
1569  {
1570  if( SCIPisLT(scip, graph->cost[e], FARAWAY) )
1571  cost[e] = 1.0;
1572  else
1573  cost[e] = graph->cost[e];
1574  if( SCIPisLT(scip, graph->cost[flipedge(e)], FARAWAY) )
1575  costrev[e] = 1.0;
1576  else
1577  costrev[e] = graph->cost[flipedge(e)];
1578  }
1579 
1580  /* distance from root to all nodes */
1581  graph_path_execX(scip, graph, root, cost, pathdist, pathedge);
1582 
1583  /* no paths should go back to the root */
1584  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1585  costrev[e] = FARAWAY;
1586 
1587  /* build voronoi diagram */
1588  graph_add1stTermPaths(graph, costrev, vnoi, vbase, state);
1589 
1590  /* traverse all node, try to eliminate first the node and then all incident edges */
1591  for( k = 0; k < nnodes; k++ )
1592  {
1593  /* can node k be deleted? */
1594  if( !Is_term(graph->term[k]) && SCIPisGT(scip, vnoi[k].dist + pathdist[k] + (double) bound, (double) hoplimit) )
1595  {
1596  e = graph->outbeg[k];
1597 
1598  /* delete incident edges */
1599  while( e != EAT_LAST )
1600  {
1601  assert(e >= 0);
1602  (*nelims)++;
1603  etemp = graph->oeat[e];
1604  graph_edge_del(scip, graph, e, TRUE);
1605  e = etemp;
1606  }
1607  }
1608  else
1609  {
1610  e = graph->outbeg[k];
1611  while( e != EAT_LAST )
1612  {
1613  assert(e >= 0);
1614  head = graph->head[e];
1615  tmpcost = pathdist[k] + 1.0 + vnoi[head].dist + bound;
1616 
1617  etemp = graph->oeat[e];
1618  /* can edge e (i.e. both arc e and its reverse arc) or arc e be deleted? */
1619  if( SCIPisGT(scip, tmpcost, (double) hoplimit) && SCIPisLT(scip, graph->cost[e], FARAWAY) )
1620  {
1621 
1622  if( SCIPisGT(scip, FARAWAY, graph->cost[flipedge(e)]) )
1623  {
1624  graph->cost[e] = FARAWAY;
1625  (*nelims)++;
1626  }
1627  else
1628  {
1629  graph_edge_del(scip, graph, e, TRUE);
1630  (*nelims)++;
1631  }
1632  }
1633  e = etemp;
1634  }
1635  }
1636  }
1637 
1638  SCIPdebugMessage("eliminated (edges) in hcr bound reduce: %d,\n", *nelims);
1639 
1640  assert(graph_valid(scip, graph));
1641 
1642  return SCIP_OKAY;
1643 }
1644 
1645 /* reduction method for HCSTP */
1647  SCIP* scip,
1648  GRAPH* graph,
1649  PATH* vnoi,
1650  SCIP_Real* cost,
1651  SCIP_Real* costrev,
1652  SCIP_Real* pathdist,
1653  SCIP_Real objval,
1654  int* heap,
1655  int* state,
1656  int* vbase,
1657  int* nelims,
1658  int* pathedge,
1659  SCIP_Bool fix
1660  )
1661 {
1662  SCIP_VAR** vars;
1663  SCIP_Real min;
1664  SCIP_Real bound;
1665  SCIP_Real maxmin;
1666  SCIP_Real tmpcost;
1667  SCIP_Real hopfactor;
1668  int* result;
1669  int e;
1670  int k;
1671  int root;
1672  int head;
1673  int etemp;
1674  int nnodes;
1675  int nedges;
1676  SCIP_Bool success;
1677 
1678  assert(scip != NULL);
1679  assert(graph != NULL);
1680  assert(vnoi != NULL);
1681  assert(cost != NULL);
1682  assert(costrev != NULL);
1683  assert(heap != NULL);
1684  assert(state != NULL);
1685  assert(vbase != NULL);
1686  assert(nelims != NULL);
1687 
1688  hopfactor = DEFAULT_HOPFACTOR;
1689  bound = 0.0;
1690  *nelims = 0;
1691  success = TRUE;
1692  vars = NULL;
1693  root = graph->source;
1694  nedges = graph->edges;
1695  nnodes = graph->knots;
1696 
1697  SCIP_CALL( SCIPallocBufferArray(scip, &result, nedges) );
1698 
1699  if( fix )
1700  {
1701  vars = SCIPprobdataGetVars(scip);
1702  assert(vars != NULL);
1703  for( e = 0; e < nedges; e += 2 )
1704  {
1705  result[e] = UNKNOWN;
1706  result[e + 1] = UNKNOWN;
1707 
1708  if( SCIPvarGetUbLocal(vars[e + 1]) < 0.5 )
1709  {
1710  costrev[e] = BLOCKED;
1711  }
1712  else
1713  {
1714  costrev[e] = graph->cost[e + 1];
1715  }
1716  cost[e + 1] = costrev[e];
1717  if( SCIPvarGetUbLocal(vars[e]) < 0.5 )
1718  {
1719  costrev[e + 1] = BLOCKED;
1720  }
1721  else
1722  {
1723  costrev[e + 1] = graph->cost[e];
1724  }
1725  cost[e] = costrev[e + 1];
1726  }
1727  }
1728  else
1729  {
1730  for( e = 0; e < nedges; e++ )
1731  {
1732  result[e] = UNKNOWN;
1733  cost[e] = graph->cost[e];
1734  costrev[e] = graph->cost[flipedge(e)];
1735  }
1736  }
1737 
1738  maxmin = -1.0;
1739  for( k = 0; k < nnodes; k++ )
1740  {
1741  graph->mark[k] = (graph->grad[k] > 0);
1742  if( graph->mark[k] && Is_term(graph->term[k]) )
1743  {
1744  if( k != root )
1745  {
1746  min = FARAWAY;
1747  for( e = graph->inpbeg[k]; e != EAT_LAST; e = graph->ieat[e] )
1748  if( SCIPisLT(scip, cost[e], min) )
1749  min = cost[e];
1750  assert(SCIPisGT(scip, BLOCKED, min));
1751  if( SCIPisGT(scip, min, maxmin) )
1752  maxmin = min;
1753  bound += min;
1754  }
1755  }
1756  }
1757  bound -= maxmin;
1758 
1759 
1760  /* distance from root to all nodes */
1761  graph_path_execX(scip, graph, root, cost, pathdist, pathedge);
1762 
1763  /* no paths should go back to the root */
1764  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1765  costrev[e] = FARAWAY;
1766 
1767  /* build voronoi diagram */
1768  graph_add1stTermPaths(graph, costrev, vnoi, vbase, state);
1769 
1770  if( SCIPisLT(scip, objval, 0.0) )
1771  {
1772  /* compute UB */
1774  NULL, NULL, result, 50, root, cost, costrev, &hopfactor, NULL, &success) );
1775 
1776  objval = 0.0;
1777  for( e = 0; e < nedges; e++ )
1778  if( result[e] == CONNECT )
1779  objval += graph->cost[e];
1780  }
1781  else
1782  {
1783  /* objval = objval - fixed; */
1784  objval = SCIPgetCutoffbound(scip);
1785  assert(SCIPisGT(scip, objval, 0.0));
1786  }
1787 
1788  /* traverse all node, try to eliminate first the node and then all incident edges */
1789  for( k = 0; k < nnodes; k++ )
1790  {
1791  if( Is_term(graph->term[k]) )
1792  continue;
1793  /* can node k be deleted? */
1794  if( SCIPisGT(scip, vnoi[k].dist + pathdist[k] + bound, objval) )
1795  {
1796  e = graph->outbeg[k];
1797 
1798  /* delete incident edges */
1799  while( e != EAT_LAST )
1800  {
1801  assert(e >= 0);
1802 
1803  etemp = graph->oeat[e];
1804  if( fix )
1805  {
1806  SCIP_Bool wasFixed;
1807  assert(vars != NULL);
1808  /* try to fix edge */
1809  SCIP_CALL( SCIPStpFixEdgeVarTo0(scip, vars[e], &wasFixed) );
1810  if( wasFixed )
1811  (*nelims)++;
1812 
1813  /* try to fix reversed edge */
1814  SCIP_CALL( SCIPStpFixEdgeVarTo0(scip, vars[flipedge(e)], &wasFixed) );
1815  if( wasFixed )
1816  (*nelims)++;
1817  }
1818  else
1819  {
1820  graph_edge_del(scip, graph, e, TRUE);
1821  (*nelims)++;
1822  }
1823  e = etemp;
1824  }
1825  }
1826  else
1827  {
1828  e = graph->outbeg[k];
1829  while( e != EAT_LAST )
1830  {
1831  assert(e >= 0);
1832  head = graph->head[e];
1833  tmpcost = pathdist[k] + graph->cost[e] + vnoi[head].dist + bound;
1834 
1835  etemp = graph->oeat[e];
1836  /* can edge e (i.e. both arc e and its reverse arc) or arc e be deleted? */
1837  if( SCIPisGT(scip, tmpcost, objval) && SCIPisLT(scip, graph->cost[e], FARAWAY) )
1838  {
1839  if( fix )
1840  {
1841  SCIP_Bool wasFixed;
1842  assert(vars != NULL);
1843 
1844  /* try to fix edge */
1845  SCIP_CALL( SCIPStpFixEdgeVarTo0(scip, vars[e], &wasFixed) );
1846  if( wasFixed )
1847  (*nelims)++;
1848  }
1849  else
1850  {
1851  if( SCIPisGT(scip, FARAWAY, graph->cost[flipedge(e)]) )
1852  {
1853  graph->cost[e] = FARAWAY;
1854  (*nelims)++;
1855  }
1856  else
1857  {
1858  graph_edge_del(scip, graph, e, TRUE);
1859  (*nelims)++;
1860  }
1861  }
1862  }
1863  e = etemp;
1864  }
1865  }
1866  }
1867 
1868  SCIPdebugMessage("CCC eliminated (edges) in hcrc bound reduce: %d,\n", *nelims);
1869  /* free memory */
1870  SCIPfreeBufferArray(scip, &result);
1871 
1872  assert(graph_valid(scip, graph));
1873 
1874  return SCIP_OKAY;
1875 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static volatile int nterms
Definition: interrupt.c:38
SCIP_RETCODE reduce_da(SCIP *, GRAPH *, const RPDA *, REDSOLLOCAL *, SCIP_Real *, int *, SCIP_RANDNUMGEN *)
Definition: reduce_da.c:2471
SCIP_Bool graph_pc_isMw(const GRAPH *)
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
int source
Definition: graphdefs.h:195
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_RETCODE reduce_boundHopDa(SCIP *scip, GRAPH *graph, int *nelims, SCIP_RANDNUMGEN *randnumgen)
Definition: reduce_bnd.c:1286
signed int edge
Definition: graphdefs.h:287
#define DEFAULT_HOPFACTOR
Definition: heur_tm.h:42
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
void graph_add3rdTermPaths(const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1501
int terms
Definition: graphdefs.h:192
static long bound
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE reduce_boundHop(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, int *heap, int *state, int *vbase, int *nelims)
Definition: reduce_bnd.c:1323
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
includes methods for Steiner tree problem solutions
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
reduction and dual-cost based primal heuristic for Steiner problems
void graph_free(SCIP *, GRAPH **, SCIP_Bool)
Definition: graph_base.c:796
void graph_pc_2org(SCIP *, GRAPH *)
SCIP_RETCODE graph_path_init(SCIP *, GRAPH *)
Definition: graph_path.c:480
#define FALSE
Definition: def.h:87
int *RESTRICT inpbeg
Definition: graphdefs.h:202
int *RESTRICT path_state
Definition: graphdefs.h:256
Problem data for stp problem.
#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
void graph_add4thTermPaths(const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1521
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_RETCODE reduce_bound(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *radius, SCIP_Real *offset, SCIP_Real *upperbound, int *heap, int *state, int *vbase, int *nelims)
Definition: reduce_bnd.c:655
#define FARAWAY
Definition: graphdefs.h:89
SCIP_RETCODE graph_voronoiWithRadius(SCIP *, const GRAPH *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: graph_vnoi.c:774
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void graph_printInfo(const GRAPH *)
Definition: graph_stats.c:299
SCIP_Real SCIPepsilon(SCIP *scip)
int *RESTRICT mark
Definition: graphdefs.h:198
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE SCIPStpFixEdgeVarTo0(SCIP *scip, SCIP_VAR *edgevar, SCIP_Bool *success)
Definition: prop_stp.c:2419
SCIP_RETCODE graph_get4nextTTerms(SCIP *, GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: graph_tpath.c:1601
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
miscellaneous methods used for solving Steiner problems
void graph_pc_2trans(SCIP *, GRAPH *)
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
SCIP_RETCODE reduce_boundHopR(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *heap, int *state, int *vbase, int *nelims, int *pathedge)
Definition: reduce_bnd.c:1518
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
SCIP_RETCODE reduce_boundMw(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *offset, int *heap, int *state, int *vbase, int *result, int *nelims)
Definition: reduce_bnd.c:1058
void SCIPsortReal(SCIP_Real *realarray, int len)
SCIP_Real dist
Definition: graphdefs.h:286
int *RESTRICT grad
Definition: graphdefs.h:201
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_RETCODE graph_knot_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, REDCOST *, SCIP_Bool *)
#define STP_RMWCSP
Definition: graphdefs.h:54
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
#define MST_MODE
Definition: graphdefs.h:98
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
SCIP_Real graph_pc_solGetObj(SCIP *, const GRAPH *, const int *, SCIP_Real)
unsigned char STP_Bool
Definition: portab.h:34
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
propagator for Steiner tree problems, using the LP reduced costs
#define STP_DAMODE_HOPS
Definition: reducedefs.h:43
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT tail
Definition: graphdefs.h:223
#define flipedge(edge)
Definition: graphdefs.h:84
SCIP_RETCODE reduce_boundHopRc(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, SCIP_Real objval, int *heap, int *state, int *vbase, int *nelims, int *pathedge, SCIP_Bool fix)
Definition: reduce_bnd.c:1646
void graph_getEdgeCosts(const GRAPH *, SCIP_Real *RESTRICT, SCIP_Real *RESTRICT)
void graph_voronoiMw(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: graph_vnoi.c:517
SCIP_RETCODE reduce_boundPruneHeur(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
Definition: reduce_bnd.c:1237
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
static SCIP_RETCODE computeSteinerTree(SCIP *scip, GRAPH *graph, SCIP_Real *cost, SCIP_Real *costrev, int *result, STP_Bool *stnode, SCIP_Real *upperbound, SCIP_Bool *success)
Definition: reduce_bnd.c:51
static SCIP_RETCODE boundPruneHeur(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
Definition: reduce_bnd.c:149
static SCIP_RETCODE boundPruneHeurMw(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
Definition: reduce_bnd.c:487
#define BND_TMHEUR_NRUNS
Definition: reduce_bnd.c:46
SCIP_RETCODE reduce_unconnectedForDirected(SCIP *, GRAPH *)
void graph_path_exit(SCIP *, GRAPH *)
Definition: graph_path.c:515
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
SCIP_Real * r
Definition: circlepacking.c:50
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
int graph_pc_deleteTerm(SCIP *, GRAPH *, int, SCIP_Real *)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
void graph_add2ndTermPaths(const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1482
#define SCIP_Real
Definition: def.h:177
#define BLOCKED
Definition: graphdefs.h:90
int *RESTRICT outbeg
Definition: graphdefs.h:204
shortest paths based primal heuristics for Steiner problems
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
void graph_add1stTermPaths(const GRAPH *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1464
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
#define Is_anyTerm(a)
Definition: graphdefs.h:105
int hoplimit
Definition: graphdefs.h:216
includes various reduction methods for Steiner tree problems
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
void graph_voronoiWithRadiusMw(SCIP *, const GRAPH *, PATH *, const SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: graph_vnoi.c:973