Scippy

SCIP

Solving Constraint Integer Programs

reduce_da.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_da.c
17  * @brief dual-ascent based reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements dual-ascent based techniques for several Steiner problems.
21  *
22  * A list of all interface methods can be found in reduce.h.
23  *
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 //#define SCIP_DEBUG
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <assert.h>
32 #include "graph.h"
33 #include "reduce.h"
34 #include "extreduce.h"
35 #include "heur_tm.h"
36 #include "heur_ascendprune.h"
37 #include "heur_lurkprune.h"
38 #include "heur_slackprune.h"
39 #include "heur_local.h"
40 #include "heur_rec.h"
41 #include "solpool.h"
42 #include "solstp.h"
43 #include "dualascent.h"
44 #include "probdata_stp.h"
45 
46 #define BND_TMHEUR_NRUNS 100 /**< number of runs of constructive heuristic */
47 #define BND_TMHEUR_NRUNS_RESTRICT 16 /**< number of runs of constructive heuristic */
48 #define BND_TMHEUR_NRUNS_RPC 16 /**< number of runs for RPC */
49 #define DEFAULT_DARUNS_DIRECTED 3
50 #define DEFAULT_DARUNS 8 /**< number of runs for dual ascent heuristic */
51 #define DEFAULT_DARUNS_FAST 4 /**< number of runs for dual ascent heuristic */
52 #define DEFAULT_NMAXROOTS 8 /**< max number of roots to use for new graph in dual ascent heuristic */
53 #define SOLPOOL_SIZE 20 /**< size of presolving solution pool */
54 #define DARUNS_TERMRATIO_LOW 0.05
55 #define DARUNS_TERMRATIO_MED 0.075
56 #define DARUNS_TERMRATIO_HIGH 0.1
57 #define DARUNS_TERMRATIO_HUGE 0.2
58 #define STP_RED_MINBNDTERMS 750
59 #define STP_DABD_MAXDEGREE 5
60 #define STP_DABD_MAXDNEDGES 10
61 #define DAMAXDEVIATION_RANDOM_LOWER 0.20 /**< random upper bound for max deviation for dual ascent */
62 #define DAMAXDEVIATION_RANDOM_UPPER 0.30 /**< random upper bound for max deviation for dual ascent */
63 #define DAMAXDEVIATION_FAST 0.75
64 
65 
66 /** returns solution value for given edge-solution array (CONNECT/UNKNOWN) and offset, takes prizes into account! */
67 static
69  SCIP* scip, /**< SCIP data structure */
70  const GRAPH* g, /**< the graph */
71  const int* soledge /**< solution */
72 )
73 {
74  SCIP_Real obj;
75  if( graph_pc_isPcMw(g) )
76  obj = graph_pc_solGetObj(scip, g, soledge, 0.0);
77  else
78  obj = solstp_getObjBounded(g, soledge, 0.0, g->edges);
79 
80  return obj;
81 }
82 
83 
84 /** computes dual solution with dual-ascent and guided solution (and possibly reroots given solution) */
85 static
87  SCIP* scip, /**< SCIP data structure */
88  GRAPH* graph, /**< graph data structure */
89  SCIP_Real damaxdeviation, /**< maximum deviation for DA */
90  REDCOST* redcostdata, /**< reduced cost data */
91  int* result /**< solution array */
92 )
93 {
94  const int daroot = redcosts_getRootTop(redcostdata);
95  SCIP_Real* const redcost = redcosts_getEdgeCostsTop(redcostdata);
96  SCIP_Real dualobjval = -1.0;
97  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = daroot,
98  .is_pseudoroot = FALSE, .damaxdeviation = damaxdeviation };
99 
100  /* solution might not be valid anymore */
101  if( !solstp_isValid(scip, graph, result) )
102  {
103  SCIPdebugMessage("solution not valid; run normal dual-ascent \n");
104 
105  if( graph->stp_type == STP_DCSTP )
106  {
107  SCIP_CALL( dualascent_execDegCons(scip, graph, NULL, &daparams, redcost, &dualobjval) );
108  }
109  else
110  {
111  SCIP_CALL( dualascent_exec(scip, graph, NULL, &daparams, redcost, &dualobjval) );
112  }
113  }
114  else
115  {
116  if( graph_typeIsUndirected(graph) )
117  {
118  SCIPdebugMessage("reroot solution and run guided dual-ascent \n");
119  SCIP_CALL(solstp_reroot(scip, graph, result, daroot));
120  }
121  else
122  {
123  assert(daroot == graph->source);
124  SCIPdebugMessage("run guided dual-ascent \n");
125  }
126 
127  if( graph->stp_type == STP_DCSTP )
128  {
129  SCIP_CALL( dualascent_execDegCons(scip, graph, result, &daparams, redcost, &dualobjval));
130  }
131  else
132  {
133  SCIP_CALL( dualascent_exec(scip, graph, result, &daparams, redcost, &dualobjval) );
134  }
135  }
136 
137  if( STP_RPCSPG == graph->stp_type )
138  {
139  SCIPdebugMessage("RPC: add %f to dual objective \n", graph_pc_getNonLeafTermOffset(scip, graph));
140 
141  dualobjval += graph_pc_getNonLeafTermOffset(scip, graph);
142  }
143 
144  redcosts_setDualBoundTop(dualobjval, redcostdata);
145 
146  return SCIP_OKAY;
147 }
148 
149 
150 /** computes dual solution with dual-ascent */
151 static
153  SCIP* scip, /**< SCIP data structure */
154  GRAPH* graph, /**< graph data structure */
155  SCIP_Real damaxdeviation, /**< maximum deviation for DA */
156  REDCOST* redcostdata /**< reduced cost data */
157 )
158 {
159  const int daroot = redcosts_getRootTop(redcostdata);
160  SCIP_Real* const redcost = redcosts_getEdgeCostsTop(redcostdata);
161  SCIP_Real dualobjval = -1.0;
162  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = daroot,
163  .is_pseudoroot = FALSE, .damaxdeviation = damaxdeviation };
164 
165  SCIPdebugMessage("no rerooting, run normal dual-ascent \n");
166 
167  if( graph->stp_type == STP_DCSTP )
168  {
169  SCIP_CALL( dualascent_execDegCons(scip, graph, NULL, &daparams, redcost, &dualobjval) );
170  }
171  else
172  {
173  SCIP_CALL( dualascent_exec(scip, graph, NULL, &daparams, redcost, &dualobjval) );
174 
175  }
176 
177  if( STP_RPCSPG == graph->stp_type )
178  {
179  SCIPdebugMessage("RPC: add %f to dual objective \n", graph_pc_getNonLeafTermOffset(scip, graph));
180 
181  dualobjval += graph_pc_getNonLeafTermOffset(scip, graph);
182  }
183 
184  redcosts_setDualBoundTop(dualobjval, redcostdata);
185 
186  return SCIP_OKAY;
187 }
188 
189 
190 /** computes TM solution */
191 static
193  SCIP* scip, /**< SCIP data structure */
194  GRAPH* graph, /**< graph data structure */
195  int* result, /**< solution array */
196  SCIP_Real* bestobjval, /**< pointer to the objective value */
197  SCIP_Bool* success /**< success? */
198 )
199 {
200  SCIP_Real* cost = NULL;
201  SCIP_Real* costrev = NULL;
202  int* startstm = NULL;
203  const int nnodes = graph_get_nNodes(graph);
204  const int nedges = graph_get_nEdges(graph);
205  int runstm;
206  SCIP_Real hopfactor = -1.0; /* automatic set to default */
207 
208  if( graph_typeIsDirected(graph) || graph->stp_type == STP_DCSTP )
209  {
210  runstm = BND_TMHEUR_NRUNS;
211  }
212  else if( graph_pc_isRootedPcMw(graph) )
213  {
214  runstm = BND_TMHEUR_NRUNS_RPC;
215  }
216  else
217  {
218  runstm = BND_TMHEUR_NRUNS_RESTRICT;
219  }
220 
221  assert(graph->stp_type != STP_RPCSPG || !graph->extended);
222 
223  SCIP_CALL( SCIPallocBufferArray(scip, &startstm, nnodes) );
224  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
225  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
226 
227  graph_getEdgeCosts(graph, cost, costrev);
228 
229  SCIPStpHeurTMCompStarts(graph, startstm, &runstm);
230 
232  graph, startstm, NULL, result, runstm, graph->source, cost, costrev, &hopfactor, NULL, success) );
233 
234  if( *success )
235  {
236  const SCIP_Real obj = getSolObj(scip, graph, result);
237 
238  SCIPdebugMessage("TM successful, obj=%f \n", obj);
239 
240  if( obj < *bestobjval )
241  *bestobjval = obj;
242  }
243  else
244  {
245  assert(graph->stp_type == STP_DHCSTP || graph->stp_type == STP_DCSTP);
246  SCIPdebugMessage("TM failed \n");
247  }
248 
249  SCIPfreeBufferArray(scip, &costrev);
250  SCIPfreeBufferArray(scip, &cost);
251  SCIPfreeBufferArray(scip, &startstm);
252 
253  return SCIP_OKAY;
254 }
255 
256 
257 
258 /** computes solution from reduced costs */
259 static
261  SCIP* scip, /**< SCIP data structure */
262  GRAPH* graph, /**< graph data structure */
263  const REDCOST* redcostdata, /**< reduced cost data */
264  SCIP_Bool useSlackPrune, /**< use slack prune? */
265  SCIP_Bool useRec, /**< use recombination? */
266  STPSOLPOOL* pool, /**< solution pool */
267  int* result, /**< result array */
268  int* bestresult, /**< result array */
269  SCIP_Bool* havebestsol, /**< could best solution be stored in bestresult? */
270  SCIP_Real* bestobjval /**< pointer to the objective value */
271 )
272 {
273  const SCIP_Real* redcosts = redcosts_getEdgeCostsTop(redcostdata);
274  const int daroot = redcosts_getRootTop(redcostdata);
275  const int nedges = graph->edges;
276  SCIP_Bool success;
277  SCIP_Bool soladded;
278  SCIP_Real objval;
279 
280  soladded = FALSE;
281 
282  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, graph, redcosts, result, daroot, &success, FALSE));
283  assert(success && solstp_isValid(scip, graph, result));
284 
285  SCIP_CALL(SCIPStpHeurLocalRunFast(scip, graph, result));
286  assert(solstp_isValid(scip, graph, result));
287 
288  objval = getSolObj(scip, graph, result);
289 
290  if( useRec )
291  SCIP_CALL(solpool_addSol(scip, objval, result, pool, &soladded));
292 
293  /* should we try recombination? */
294  if( useRec && soladded && pool->size >= 2 && LT(objval, *bestobjval) )
295  {
296  /* get index of just added solution */
297  int solindex = pool->maxindex;
298  SCIP_Bool solfound;
299 
300  SCIPdebugMessage("POOLSIZE %d \n", pool->size);
301 
302  SCIP_CALL(SCIPStpHeurRecRun(scip, pool, NULL, NULL, graph, NULL, &solindex, 1, pool->size, FALSE, &solfound));
303 
304  if( solfound )
305  {
306  const STPSOL* const sol = solpool_solFromIndex(pool, solindex);
307  SCIP_Real solobjval;
308 
309  assert(sol != NULL);
310 
311  solobjval = sol->obj;
312 
313  if( graph->stp_type == STP_RPCSPG )
314  solobjval += graph_pc_getNonLeafTermOffset(scip, graph);
315 
316  assert(SCIPisEQ(scip, getSolObj(scip, graph, sol->soledges), solobjval));
317 
318  SCIPdebugMessage("DA: rec found better solution with obj %f vs %f \n", sol->obj, objval);
319 
320  if( SCIPisLT(scip, solobjval, objval) )
321  {
322  assert(SCIPisLT(scip, getSolObj(scip, graph, sol->soledges), getSolObj(scip, graph, result)));
323 
324  BMScopyMemoryArray(result, sol->soledges, nedges);
325 
326  SCIP_CALL(SCIPStpHeurLocalRun(scip, graph, result));
327  objval = getSolObj(scip, graph, result);
328 
329  assert(SCIPisLE(scip, objval, solobjval));
330 
331  if( objval < solobjval )
332  SCIP_CALL(solpool_addSol(scip, objval, result, pool, &solfound));
333  }
334  }
335  }
336 
337  if( useSlackPrune )
338  {
339  SCIP_Real upperbound_sp;
340  SCIP_CALL( SCIPStpHeurSlackPruneRun(scip, NULL, graph, result, &success, FALSE, FALSE) );
341  upperbound_sp = getSolObj(scip, graph, result);
342 
343  if( LT(upperbound_sp, objval) )
344  {
345  objval = upperbound_sp;
346  }
347  }
348 
349  if( SCIPisLE(scip, objval, *bestobjval) )
350  {
351  *havebestsol = TRUE;
352  *bestobjval = objval;
353  BMScopyMemoryArray(bestresult, result, nedges);
354  }
355  else if( *havebestsol )
356  {
357  *havebestsol = solstp_isUnreduced(scip, graph, bestresult);
358  }
359 
360  assert(*havebestsol == FALSE || solstp_isValid(scip, graph, bestresult));
361 
362  return SCIP_OKAY;
363 }
364 
365 
366 
367 /** computes solution from reduced costs for directed graph */
368 static
370  SCIP* scip, /**< SCIP data structure */
371  GRAPH* graph, /**< graph data structure */
372  const REDCOST* redcostdata, /**< reduced cost data */
373  int* result, /**< result array */
374  int* bestresult, /**< result array */
375  SCIP_Bool* havebestsol, /**< could best solution be stored in bestresult? */
376  SCIP_Real* bestobjval /**< pointer to the objective value */
377 )
378 {
379  const SCIP_Real* redcosts = redcosts_getEdgeCostsTop(redcostdata);
380  const int daroot = redcosts_getRootTop(redcostdata);
381  const int nedges = graph->edges;
382  SCIP_Bool success;
383  SCIP_Real objval;
384 
385  assert(graph_typeIsDirected(graph) || graph->stp_type == STP_DCSTP);
386  assert(daroot == graph->source || graph->stp_type == STP_DCSTP);
387 
388  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, graph, redcosts, result, daroot, &success, FALSE));
389 
390  if( !success )
391  {
392  assert(graph->stp_type == STP_DHCSTP || graph->stp_type == STP_DCSTP);
393  *havebestsol = FALSE;
394 
395  SCIPdebugMessage("ascend-prune failed \n");
396 
397  SCIP_CALL( computeSteinerTreeTM(scip, graph, result, bestobjval, &success) );
398 
399  if( !success )
400  return SCIP_OKAY;
401  }
402 
403  objval = solstp_getObj(graph, result, 0.0);
404  SCIPdebugMessage("old obj=%f ascend-prune obj=%f \n", *bestobjval, objval);
405 
406  assert(success && solstp_isValid(scip, graph, result));
407 
408  if( SCIPisLE(scip, objval, *bestobjval) )
409  {
410  *havebestsol = TRUE;
411  *bestobjval = objval;
412  BMScopyMemoryArray(bestresult, result, nedges);
413  }
414  else if( *havebestsol )
415  {
416  *havebestsol = solstp_isUnreduced(scip, graph, bestresult);
417  }
418 
419  assert(*havebestsol == FALSE || solstp_isValid(scip, graph, bestresult));
420 
421  return SCIP_OKAY;
422 }
423 
424 
425 /** compute primal solution during dual-ascent routine for PCSTP or MWCSP based on reduced costs */
426 static
428  SCIP* scip, /**< SCIP data structure */
429  GRAPH* graph, /**< graph data structure */
430  STPSOLPOOL* pool, /**< solution pool */
431  const SCIP_Real* cost, /**< dual ascent costs */
432  SCIP_Real* upperbound, /**< upperbound pointer */
433  int* result1, /**< sol int array corresponding to upper bound */
434  int* result2, /**< sol int array corresponding to best new solution (might be worse than upper bound) */
435  int* pathedge, /**< int array */
436  STP_Bool* nodearrchar, /**< node array storing solution vertices */
437  SCIP_Bool* apsol /**< ascend-prune sol? */
438 )
439 {
440  SCIP_Real ub2;
441  const int nedges = graph->edges;
442  SCIP_Bool success;
443 
444  assert(graph_pc_isPcMw(graph));
445 
446  /* compute new solution and store it in result2 */
447 
448  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, graph, cost, result2, -1, &success, FALSE) );
449  assert(success);
450 
451  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, result2) );
452 
453  assert(solstp_isValid(scip, graph, result2));
454 
455  ub2 = getSolObj(scip, graph, result2);
456  SCIPdebugMessage("DA: first new sol value in computeSteinerTreeRedCostsPcMw: %f ... old value: %f \n", ub2, *upperbound);
457 
458  /* try recombination? */
459  if( pool != NULL )
460  {
461  SCIPdebugMessage("ub %f vs best sol %f\n", ub2, pool->sols[0]->obj);
462  SCIP_CALL( solpool_addSol(scip, ub2, result2, pool, &success) );
463 
464 #ifdef SCIP_DEBUG
465  for( int i = 0; i < pool->size; i++ )
466  printf(" %f ", pool->sols[i]->obj);
467  printf("\n ");
468 #endif
469 
470  if( success && pool->size >= 2 )
471  {
472  /* get index of just added solution */
473  int solindex = pool->maxindex;
474 
475  SCIP_Bool solfound;
476 
477  SCIPdebugMessage("POOLSIZE %d \n", pool->size);
478 
479  SCIP_CALL( SCIPStpHeurRecRun(scip, pool, NULL, NULL, graph, NULL, &solindex, 3, pool->size, FALSE, &solfound) );
480 
481  if( solfound )
482  {
483  STPSOL* sol = solpool_solFromIndex(pool, solindex);
484  SCIP_Real solobjval;
485 
486  assert(sol != NULL);
487  solobjval = sol->obj;
488 
489  if( graph_pc_isPc(graph) )
490  solobjval += graph_pc_getNonLeafTermOffset(scip, graph);
491 
492  assert(SCIPisEQ(scip, getSolObj(scip, graph, sol->soledges), solobjval));
493 
494  SCIPdebugMessage("DA: rec found better solution with obj %f vs %f \n", sol->obj, ub2);
495 
496  if( SCIPisLT(scip, solobjval, ub2) )
497  {
498  assert(SCIPisLT(scip, getSolObj(scip, graph, sol->soledges), getSolObj(scip, graph, result2)));
499 
500  BMScopyMemoryArray(result2, sol->soledges, nedges);
501 
502  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, result2) );
503 
504  assert(SCIPisLT(scip, getSolObj(scip, graph, result2), ub2));
505 
506  ub2 = getSolObj(scip, graph, result2);
507 
508  if( SCIPisLT(scip, ub2, sol->obj) )
509  SCIP_CALL( solpool_addSol(scip, ub2, result2, pool, &success) );
510  }
511  }
512  }
513  }
514 
515  if( SCIPisLE(scip, ub2, *upperbound) )
516  {
517  SCIPdebugMessage("DA: improved incumbent %f vs %f, return \n", ub2, *upperbound);
518 
519  *apsol = TRUE;
520  *upperbound = ub2;
521  BMScopyMemoryArray(result1, result2, nedges);
522  }
523 
524  if( graph->stp_type != STP_MWCSP || !(*apsol) )
525  return SCIP_OKAY;
526 
527 #if 1
528  SCIP_CALL( SCIPStpHeurRecExclude(scip, graph, result1, result2, pathedge, nodearrchar, &success) );
529 
530  if( success )
531  {
532  BMScopyMemoryArray(result1, result2, nedges);
533  *upperbound = getSolObj(scip, graph, result1);
534  SCIPdebugMessage("DA: afterLastExclusion %f \n", *upperbound);
535  }
536 #endif
537 
538  return SCIP_OKAY;
539 }
540 
541 
542 
543 /** collected terminals (fixed ones for RPC/RMW) */
544 static inline
546  const GRAPH* graph, /**< graph data structure */
547  int* terminals, /**< terminals array (of size graph->terms) */
548  int* nterms /**< number of terminals (might differ for RPC) */
549 )
550 {
551  int n = 0;
552  const int nnodes = graph->knots;
553  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(graph);
554 
555  assert(graph->stp_type != STP_PCSPG && graph->stp_type != STP_MWCSP);
556  assert(!isRpcmw || !graph->extended);
557 
558  for( int i = 0; i < nnodes; i++ )
559  {
560  if( Is_term(graph->term[i]) )
561  {
562  assert(graph->mark[i]);
563  if( !isRpcmw || graph_pc_knotIsFixedTerm(graph, i) )
564  terminals[n++] = i;
565  }
566  }
567 
568  assert(isRpcmw || graph->terms == n);
569  *nterms = n;
570 }
571 
572 
573 /** updates node bounds for reduced cost fixings */
574 static
576  SCIP_Real* fixingbounds, /**< fixing bounds */
577  const GRAPH* graph, /**< graph data structure */
578  const SCIP_Real* pathdist, /**< shortest path distances */
579  const PATH* vnoi, /**< Voronoi paths */
580  SCIP_Real lpobjval, /**< LP objective */
581  SCIP_Bool initialize /**< initialize fixing bounds? */
582 )
583 {
584  const int nnodes = graph->knots;
585 
586  assert(graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || !graph->extended);
587 
588  if( initialize )
589  for( int k = 0; k < nnodes; k++ )
590  fixingbounds[k] = -FARAWAY;
591 
592  for( int k = 0; k < nnodes; k++ )
593  {
594  SCIP_Real fixbnd;
595 
596  if( !graph->mark[k] )
597  continue;
598 
599  assert(!Is_pseudoTerm(graph->term[k]));
600 
601  fixbnd = pathdist[k] + vnoi[k].dist + lpobjval;
602 
603  if( fixbnd > fixingbounds[k] )
604  {
605  fixingbounds[k] = fixbnd;
606  }
607  }
608 }
609 
610 /** updates node bounds for reduced cost replacement */
611 static
613  SCIP* scip, /**< SCIP */
614  const REDCOST* redcostdata, /**< reduced cost data */
615  const GRAPH* graph, /**< graph data structure */
616  SCIP_Real* replacebounds, /**< replacement bounds */
617  SCIP_Real upperbound, /**< upper bound */
618  SCIP_Bool initialize, /**< initialize fixing bounds? */
619  SCIP_Bool extendedsearch /**< perform extended searching? */
620 )
621 {
622  unsigned int* eqstack = NULL;
623  SCIP_Bool* eqmark = NULL;
624  int outedges[STP_DABD_MAXDEGREE];
625  const int nnodes = graph->knots;
626  const SCIP_Real lpobjval = redcosts_getDualBoundTop(redcostdata);
627  const SCIP_Real cutoff = MAX(upperbound - lpobjval, 0.0);
628  const int halfnedges = graph->edges / 2;
629  const SCIP_Real *redcost = redcosts_getEdgeCostsTop(redcostdata);
630  const SCIP_Real *pathdist = redcosts_getRootToNodeDistTop(redcostdata);
631  const PATH *vnoi = redcosts_getNodeToTermsPathsTop(redcostdata);
632  const int *vbase = redcosts_getNodeToTermsBasesTop(redcostdata);
633  const int root = redcosts_getRootTop(redcostdata);
634 
635  assert(!graph_pc_isMw(graph));
636  assert(SCIPisFeasGE(scip, upperbound, lpobjval));
637 
638  assert(graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || !graph->extended);
639  assert(!extendedsearch && "deprecated!");
640 
641  if( initialize )
642  {
643  for( int k = 0; k < nnodes; k++ )
644  replacebounds[k] = -FARAWAY;
645  }
646 
647  if( extendedsearch )
648  {
649  SCIP_CALL( SCIPallocCleanBufferArray(scip, &eqmark, halfnedges) );
650  SCIP_CALL( SCIPallocBufferArray(scip, &eqstack, halfnedges) );
651  }
652 
653  for( int node = 0; node < nnodes; node++ )
654  {
655  const int degree = graph->grad[node];
656 
657  if( degree >= 3 && !Is_anyTerm(graph->term[node]) )
658  {
659  SCIP_Real fixbnd;
660 
661  /* bound already good enough? */
662  if( SCIPisFeasLT(scip, upperbound, replacebounds[node]) )
663  continue;
664 
665  fixbnd = pathdist[node] + vnoi[node].dist + vnoi[node + nnodes].dist + lpobjval;
666 
667  assert(!Is_pseudoTerm(graph->term[node]));
668 
669  /* Y-test for small degrees */
670  if( degree <= STP_DABD_MAXDEGREE && !SCIPisFeasLT(scip, upperbound, fixbnd) )
671  {
672  int eqstack_size = 0;
673  int edgecount = 0;
674 
675  fixbnd = FARAWAY;
676 
677  for( int e = graph->outbeg[node]; e != EAT_LAST; e = graph->oeat[e] )
678  outedges[edgecount++] = e;
679 
680  assert(edgecount == degree);
681 
682  /* compute cost for each root and save minimum */
683  for( int i = 0; i < degree; i++ )
684  {
685  const int tmproot = graph->head[outedges[i]];
686  const int rootedge = flipedge(outedges[i]);
687 
688  /* loop over all combinations of Y with root tmproot */
689  for( int j = i + 1; j <= i + degree - 2; j++ )
690  {
691  for( int k = j + 1; k <= i + degree - 1; k++ )
692  {
693  const int outedge1 = outedges[j % degree];
694  const int outedge2 = outedges[k % degree];
695  const int leaf1 = graph->head[outedge1];
696  const int leaf2 = graph->head[outedge2];
697 
698  SCIP_Real tmpcostY;
699 
700  assert(leaf1 != leaf2 && tmproot != leaf1 && tmproot != leaf2);
701  assert(vbase[leaf1] >= 0 || vnoi[leaf1].dist >= FARAWAY);
702  assert(vbase[leaf2] >= 0 || vnoi[leaf2].dist >= FARAWAY);
703 
704  if( leaf1 == root || leaf2 == root )
705  continue;
706 
707  tmpcostY = pathdist[tmproot] + redcost[rootedge] + redcost[outedge1] + redcost[outedge2];
708 
709  if( vbase[leaf1] != vbase[leaf2] )
710  {
711  tmpcostY += vnoi[leaf1].dist + vnoi[leaf2].dist;
712  }
713  else
714  {
715  /* also covers the case that leaf is a terminal */
716  const SCIP_Real leaf1far = vnoi[leaf1 + nnodes].dist;
717  const SCIP_Real leaf2far = vnoi[leaf2 + nnodes].dist;
718 
719  assert(vbase[leaf1 + nnodes] >= 0 || leaf1far == FARAWAY);
720  assert(vbase[leaf2 + nnodes] >= 0 || leaf2far == FARAWAY);
721 
722  tmpcostY += MIN(leaf1far + vnoi[leaf2].dist, vnoi[leaf1].dist + leaf2far);
723  }
724 
725  if( tmpcostY < fixbnd )
726  {
727  if( extendedsearch && SCIPisLE(scip, tmpcostY, cutoff) )
728  {
729  int tree3outedges[2];
730  SCIP_Bool ruleout;
731 #ifndef NDEBUG
732  const SCIP_Real tmpcostYorg = tmpcostY;
733 #endif
734  tree3outedges[0] = outedge1;
735  tree3outedges[1] = outedge2;
736 
737  SCIP_CALL( reduce_extendedCheck3Tree(scip, graph, root, redcost, pathdist, vnoi, vbase, cutoff, tree3outedges, rootedge,
738  &tmpcostY, &ruleout, eqstack, &eqstack_size, eqmark) );
739 
740  if( ruleout )
741  tmpcostY = FARAWAY;
742 
743 #ifndef NDEBUG
744  assert(tmpcostY >= tmpcostYorg);
745 #endif
746  }
747 
748  if( tmpcostY < fixbnd )
749  fixbnd = tmpcostY;
750  }
751  }
752  } /* Y loop */
753  } /* root loop */
754 
755  fixbnd += lpobjval;
756 
757  assert(SCIPisGE(scip, fixbnd, pathdist[node] + vnoi[node].dist + vnoi[node + nnodes].dist + lpobjval)
758  || fixbnd >= FARAWAY);
759 
760  if( extendedsearch )
761  {
762  for( int i = 0; i < eqstack_size; i++ )
763  eqmark[eqstack[i]] = FALSE;
764 
765  for( int i = 0; i < halfnedges; i++ )
766  assert(eqmark[i] == FALSE);
767  }
768  }
769 
770  if( fixbnd > replacebounds[node] )
771  replacebounds[node] = fixbnd;
772  }
773  }
774  if( extendedsearch )
775  {
776  assert(eqstack != NULL && eqmark != NULL);
777 
778  SCIPfreeBufferArray(scip, &eqstack);
779  SCIPfreeCleanBufferArray(scip, &eqmark);
780  }
781 
782  return SCIP_OKAY;
783 }
784 
785 
786 /** updates edge fixing bounds for reduced cost fixings */
787 static
789  SCIP_Real* fixingbounds, /**< fixing bounds */
790  const GRAPH* graph, /**< graph data structure */
791  const SCIP_Real* cost, /**< reduced costs */
792  const SCIP_Real* pathdist, /**< shortest path distances */
793  const PATH* vnoi, /**< Voronoi paths */
794  SCIP_Real lpobjval, /**< LP objective */
795  int extnedges, /**< number of edges for extended problem */
796  SCIP_Bool initialize, /**< initialize fixing bounds? */
797  SCIP_Bool undirected /**< only consider undirected edges */
798 )
799 {
800  const int nnodes = graph->knots;
801 
802  assert(graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || !graph->extended);
803  assert(extnedges > 0);
804 
805  if( initialize )
806  for( int e = 0; e < extnedges; e++ )
807  fixingbounds[e] = -FARAWAY;
808 
809  for( int k = 0; k < nnodes; k++ )
810  {
811  if( !graph->mark[k] )
812  continue;
813 
814  assert(!Is_pseudoTerm(graph->term[k]));
815 
816  if( undirected )
817  {
818  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
819  {
820  const int head = graph->head[e];
821 
822  if( graph->mark[head] )
823  {
824  const int erev = flipedge(e);
825  const SCIP_Real fixbnd = pathdist[k] + cost[e] + vnoi[head].dist + lpobjval;
826  const SCIP_Real fixbndrev = pathdist[head] + cost[erev] + vnoi[k].dist + lpobjval;
827  const SCIP_Real minbnd = MIN(fixbnd, fixbndrev);
828 
829  assert(fixingbounds[e] == fixingbounds[erev]);
830 
831  if( minbnd > fixingbounds[e] )
832  {
833  fixingbounds[e] = minbnd;
834  fixingbounds[erev] = minbnd;
835  }
836  }
837  }
838  }
839  else
840  {
841  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
842  {
843  const int head = graph->head[e];
844 
845  if( graph->mark[head] )
846  {
847  const SCIP_Real fixbnd = pathdist[k] + cost[e] + vnoi[head].dist + lpobjval;
848 
849  if( fixbnd > fixingbounds[e] )
850  fixingbounds[e] = fixbnd;
851  }
852  }
853  }
854  }
855 }
856 
857 /** eliminate nodes by using fixing-bounds and reduced costs */
858 static
860  SCIP* scip, /**< SCIP data structure */
861  GRAPH* graph, /**< graph data structure */
862  GRAPH* transgraph, /**< graph data structure or NULL */
863  const SCIP_Real* fixingbounds, /**< fixing bounds */
864  SCIP_Real upperbound /**< best upperbound */
865 )
866 {
867  int nfixed = 0;
868  const int nnodes = graph->knots;
869 
870  assert(graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || !graph->extended);
871 
872  graph_mark(graph);
873 
874  for( int k = 0; k < nnodes; k++ )
875  {
876  if( !graph->mark[k] || Is_term(graph->term[k]) )
877  continue;
878 
879  assert(!Is_pseudoTerm(graph->term[k]));
880 
881  if( SCIPisFeasLT(scip, upperbound, fixingbounds[k]) )
882  {
883  SCIPdebugMessage("delete knot %d %f < %f %d\n", k, upperbound, fixingbounds[k], graph->grad[k]);
884  nfixed += graph->grad[k];
885 
886  graph_knot_del(scip, graph, k, TRUE);
887 
888  if( transgraph != NULL )
889  graph_knot_del(scip, transgraph, k, FALSE);
890  }
891  }
892 
893  return nfixed;
894 }
895 
896 
897 /** eliminate edges by using fixing-bounds and reduced costs */
898 static
900  SCIP* scip, /**< SCIP data structure */
901  GRAPH* graph, /**< graph data structure */
902  GRAPH* transgraph, /**< graph data structure or NULL */
903  const SCIP_Real* fixingbounds, /**< fixing bounds */
904  const int* result, /**< solution */
905  SCIP_Real upperbound /**< best upperbound */
906 )
907 {
908  int nfixed = 0;
909  int nnodes = graph->knots;
910  const SCIP_Bool solgiven = (result != NULL);
911  const SCIP_Bool probIsDirected = graph_typeIsDirected(graph);
912 
913  assert(graph->stp_type == STP_SPG || graph->stp_type == STP_RSMT || !graph->extended);
914  assert(!solgiven || SCIPisEQ(scip, upperbound, getSolObj(scip, graph, result)));
915  assert(!solgiven || solstp_isValid(scip, graph, result));
916 
917  for( int k = 0; k < nnodes; k++ )
918  {
919  int e;
920  if( !graph->mark[k] )
921  continue;
922 
923  assert(!Is_pseudoTerm(graph->term[k]));
924 
925  e = graph->outbeg[k];
926  while( e != EAT_LAST )
927  {
928  const int enext = graph->oeat[e];
929 
930  if( graph->mark[graph->head[e]] )
931  {
932  const int erev = flipedge(e);
934 
935  if( !solgiven || result[e] == CONNECT || result[erev] == CONNECT )
936  deleteEdge = (SCIPisFeasLT(scip, upperbound, fixingbounds[e]) && SCIPisFeasLT(scip, upperbound, fixingbounds[erev]));
937  else
938  deleteEdge = (SCIPisLE(scip, upperbound, fixingbounds[e]) && SCIPisLE(scip, upperbound, fixingbounds[erev]));
939 
940  if( deleteEdge )
941  {
942  assert(EQ(graph->cost[e], graph->cost[erev]) || graph_pc_isMw(graph) || probIsDirected);
943 
944  SCIPdebugMessage("delete edge %d (upperbound=%f fixingbound=%f) \n", e, upperbound, fixingbounds[e]);
945 
946  graph_edge_del(scip, graph, e, TRUE);
947 
948  if( transgraph != NULL )
949  graph_edge_del(scip, transgraph, e, FALSE);
950 
951  nfixed++;
952  }
953  else if( probIsDirected && LT(graph->cost[e], FARAWAY) )
954  {
955  SCIP_Bool deleteArc;
956  if( !solgiven || result[e] == CONNECT )
957  deleteArc = (SCIPisFeasLT(scip, upperbound, fixingbounds[e]) );
958  else
959  deleteArc = (SCIPisLE(scip, upperbound, fixingbounds[e]) );
960 
961  if( deleteArc )
962  {
963  graph->cost[e] = FARAWAY;
964  }
965  }
966  }
967 
968  e = enext;
969  }
970  }
971 
972  return nfixed;
973 }
974 
975 
976 
977 /** eliminate edges with extended reductions */
978 static
980  SCIP* scip, /**< SCIP data structure */
981  SCIP_Real upperbound, /**< best upperbound */
982  EXTPERMA* extperma, /**< extension data */
983  GRAPH* graph, /**< graph data structure */
984  int* ndeletions_run /**< all deleted edges */
985 )
986 {
987  REDCOST* const redcostdata = extperma->redcostdata;
988  const int nlevels = redcosts_getNlevels(redcostdata);
989  int nextdeleted = 0;
990 
991  assert(*ndeletions_run >= 0);
992 
993  for( int i = 0; i < nlevels; i++ )
994  {
995  redcosts_setCutoffFromBound(upperbound, i, redcostdata);
996 
997 #ifdef SCIP_DEBUG
998  {
999  const SCIP_Real cutoff = redcosts_getCutoff(redcostdata, i);
1000  printf("Edge ext. reds., cutoff for level %d: %f \n", i, cutoff);
1001  }
1002 #endif
1003  }
1004 
1005  SCIP_CALL( extreduce_deleteEdges(scip, extperma, graph, &nextdeleted) );
1006 
1007 //#define EXT_WRITE
1008 // graph_printInfo(graph); printf("newly fixedSECOND =%d \n", *nextdeleted);
1009 #ifdef EXT_WRITE
1010  FILE *fp;
1011  //char filename[SCIP_MAXSTRLEN];
1012  //(void) SCIPsnprintf(filename, SCIP_MAXSTRLEN,"/nfs/optimi/kombadon/bzfrehfe/projects/scip/applications/STP/x%d_pred.stp", node);
1013  fp = fopen("/nfs/optimi/kombadon/bzfrehfe/projects/scip/applications/STP/STATS/stpall_hash.txt", "a+");
1014  fprintf(fp, "%s %d \n", SCIPgetProbName(scip), extfixed);
1015  fclose(fp);
1016  exit(1);
1017 #endif
1018 
1019  *ndeletions_run += nextdeleted;
1020 
1021  return SCIP_OKAY;
1022 }
1023 
1024 
1025 
1026 
1027 /* marks nodes that can be pseudo-eliminated */
1028 static
1030  SCIP* scip, /**< SCIP data structure */
1031  GRAPH* graph, /**< graph data structure */
1032  const SCIP_Real* replacebounds, /**< replacement bounds */
1033  SCIP_Real upperbound, /**< best upper bound */
1034  SCIP_Bool* pseudoDelNodes /**< pseudo deletable nodes */
1035 )
1036 {
1037  const int nnodes = graph->knots;
1038  const SCIP_Bool rpc = (graph->stp_type == STP_RPCSPG);
1039 
1040  for( int k = 0; k < nnodes; k++ )
1041  pseudoDelNodes[k] = FALSE;
1042 
1043  /* main loop */
1044  for( int degree = 3; degree <= STP_DABD_MAXDEGREE; degree++ )
1045  {
1046  for( int k = 0; k < nnodes; k++ )
1047  {
1048  if( rpc && degree == 3 && graph_pc_knotIsNonLeafTerm(graph, k) && graph->grad[k] == 3 )
1049  {
1050  SCIPdebugMessage("found rpc deg3 candidate %d \n", k);
1051  }
1052  else if( (degree != graph->grad[k] || Is_anyTerm(graph->term[k])) )
1053  {
1054  continue;
1055  }
1056 
1057  if( SCIPisFeasLT(scip, upperbound, replacebounds[k]))
1058  {
1059  pseudoDelNodes[k] = TRUE;
1060  }
1061  }
1062  }
1063 }
1064 
1065 
1066 /** submethod for daFindRoots */
1067 static
1069  SCIP* scip, /**< SCIP data structure */
1070  GRAPH* graph, /**< graph data structure */
1071  const GRAPH* transgraph, /**< graph data structure */
1072  const int* termmark, /**< terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise) */
1073  const SCIP_Real* cost, /**< da reduced cost */
1074  const SCIP_Real* bestcost, /**< best incumbent da reduced cost */
1075  SCIP_Real lpobjval, /**< da lower bound */
1076  SCIP_Real bestlpobjval, /**< best da lower bound */
1077  SCIP_Real upperbound, /**< da upper bound */
1078  SCIP_Bool rerun, /**< not the first run? */
1079  SCIP_Bool probrooted, /**< is transgraph a rooted RMW or RPC? */
1080  int pseudoterm, /**< pseudo terminal */
1081  int pseudoedge, /**< pseudo terminal edge */
1082  STP_Bool* isfixedterm, /**< bool array to indicate fixed terminals */
1083  int* roots, /**< root array */
1084  int* rootscount, /**< number of roots */
1085  int* pathedge, /**< array */
1086  STP_Bool* visited, /**< stores whether a node has been visited */
1087  SCIP_Real* dist /**< distances array, initially set to FARAWAY */
1088 )
1089 {
1090  int realterm = -1;
1091  SCIP_Bool mark = FALSE;
1092  const SCIP_Real objgap = MAX(upperbound - lpobjval, 0.0);
1093  const SCIP_Real objgap_best = MAX(upperbound - bestlpobjval, 0.0);
1094 
1095  assert(!graph->extended && transgraph->extended);
1096  assert(graph->grad[pseudoterm] == 2);
1097 
1098  if( probrooted )
1099  {
1100  assert(transgraph->tail[transgraph->term2edge[pseudoterm]] == pseudoterm);
1101 
1102  realterm = transgraph->head[transgraph->term2edge[pseudoterm]];
1103  }
1104  else
1105  {
1106  for( int e2 = transgraph->inpbeg[pseudoterm]; e2 != EAT_LAST; e2 = transgraph->ieat[e2] )
1107  {
1108  if( transgraph->cost[e2] == 0.0 )
1109  realterm = transgraph->tail[e2];
1110  else
1111  assert(pseudoedge == e2); /* that holds because of correspondence between graph and transgraph for the pseudo-terminal edge */
1112  }
1113  }
1114 
1115  assert(realterm >= 0 && graph->mark[realterm]);
1116  assert(realterm != graph->source && realterm != transgraph->source);
1117  assert(Is_pseudoTerm(transgraph->term[realterm]) && Is_term(graph->term[realterm]));
1118 
1119  if( rerun && isfixedterm[realterm] )
1120  return;
1121 
1122  if( SCIPisGT(scip, cost[pseudoedge], objgap) || SCIPisGT(scip, bestcost[pseudoedge], objgap_best) )
1123  {
1124  mark = TRUE;
1125  }
1126  else
1127  {
1128  /* get terminals that imply realterm and add corresponding reduced costs up */
1129  int nvisits;
1130  double costsum = cost[pseudoedge];
1131  double bestcostsum = bestcost[pseudoedge];
1132 
1133  assert(graph->path_heap != NULL);
1134  mark = graph_sdWalksConnected(scip, graph, termmark, graph->cost, isfixedterm, realterm, 1500, dist, pathedge, &nvisits,
1135  visited, TRUE);
1136 
1137 #ifndef NDEBUG
1138  for( int k = 0; k < graph->knots; k++ )
1139  assert(graph->path_state[k] == UNKNOWN && visited[k] == FALSE && dist[k] == FARAWAY);
1140 #endif
1141 
1142  if( !mark )
1143  {
1144  for( int k = 0; k < nvisits; k++ )
1145  {
1146  const int node = pathedge[k];
1147 
1148  assert((termmark[node] == 2) == (Is_term(graph->term[node]) && !graph_pc_termIsNonLeafTerm(graph, node)));
1149 
1150  if( termmark[node] == 2 && node != realterm )
1151  {
1152  const int nodepterm = graph_pc_getTwinTerm(graph, node);
1153  const int rootedge = graph_pc_getRoot2PtermEdge(graph, nodepterm);
1154 
1155  assert(graph->mark[node]);
1156  assert(!graph_pc_knotIsFixedTerm(graph, node));
1157  assert(graph->grad[nodepterm] == 2);
1158  assert(rootedge >= 0);
1159  assert(graph->cost[rootedge] == transgraph->cost[rootedge]);
1160  assert(graph->cost[rootedge] == graph->prize[node]);
1161 
1162  costsum += cost[rootedge];
1163  bestcostsum += bestcost[rootedge];
1164  }
1165  }
1166 
1167  if( SCIPisGT(scip, costsum, objgap) || SCIPisGT(scip, bestcostsum, objgap_best) )
1168  mark = TRUE;
1169  }
1170  }
1171 
1172  if( mark )
1173  {
1174  assert(realterm >= 0);
1175 
1176  assert(SCIPisPositive(scip, graph->prize[realterm]));
1177  assert((*rootscount) < graph->terms);
1178 
1179  roots[(*rootscount)++] = realterm;
1180  isfixedterm[realterm] = TRUE;
1181  }
1182 }
1183 
1184 
1185 /** special method for RPC/RMW that deletes incident edges of terminal, but not the terminal and the extension itself */
1186 static
1188  SCIP* scip, /**< SCIP data structure */
1189  const PATH* vnoi, /**< Voronoi data structure */
1190  int term, /**< the terminal */
1191  GRAPH* graph, /**< graph data structure */
1192  int* incidents, /**< int array */
1193  int* nfixedp /**< number of fixed edges pointer */
1194 )
1195 {
1196  const int twinterm = graph_pc_getTwinTerm(graph, term);
1197  int incidcount = 0;
1198 
1199 #ifndef NDEBUG
1200  const int termedge = graph->term2edge[term];
1201  assert(termedge >= 0 && Is_pseudoTerm(graph->term[twinterm]) && graph->cost[termedge] == 0.0);
1202  assert(graph_pc_isRootedPcMw(graph));
1203 #endif
1204 
1205  for( int e = graph->outbeg[term]; e != EAT_LAST; e = graph->oeat[e] )
1206  incidents[incidcount++] = e;
1207 
1208  assert(incidcount == graph->grad[term]);
1209  (*nfixedp) += graph->grad[term] - 1;
1210 
1211  for( int e = 0; e < incidcount; e++ )
1212  {
1213  const int edge = incidents[e];
1214 
1215  assert(graph->tail[edge] == term);
1216 
1217  if( graph->head[edge] == twinterm )
1218  continue;
1219 
1220  graph_edge_del(scip, graph, edge, TRUE);
1221  }
1222 
1223  assert(graph->grad[term] == 1);
1224  assert(graph->outbeg[term] == graph->term2edge[term] && twinterm == graph_pc_getTwinTerm(graph, term));
1225 }
1226 
1227 /** find roots for PC and MW during DA reduction */
1228 static
1230  SCIP* scip, /**< SCIP data structure */
1231  GRAPH* graph, /**< graph data structure */
1232  const GRAPH* transgraph, /**< graph data structure */
1233  const SCIP_Real* cost, /**< da reduced cost */
1234  const SCIP_Real* bestcost, /**< best incumbent da reduced cost */
1235  SCIP_Real lpobjval, /**< da lower bound */
1236  SCIP_Real bestlpobjval, /**< best da lower bound */
1237  SCIP_Real upperbound, /**< da upper bound */
1238  SCIP_Bool rerun, /**< not the first run? */
1239  SCIP_Bool probrooted, /**< is transgraph a rooted RMW or RPC? */
1240  PATH* vnoi, /**< SP array */
1241  int* pathedge, /**< array */
1242  int* vbase, /**< array */
1243  STP_Bool* isfixedterm, /**< bool array */
1244  int* roots, /**< roots (fixed terminals) array */
1245  int* rootscount /**< number of roots */
1246 )
1247 {
1248  SCIP_Real* dist;
1249  STP_Bool* visited;
1250  int* termmark;
1251  int* const state = graph->path_state;
1252  const int root = graph->source;
1253  const int nnodes = graph->knots;
1254  const SCIP_Bool graphextended = graph->extended;
1255  int nroots = *rootscount;
1256  int nvisits;
1257 
1258  assert(state);
1259  assert(graph_pc_isPcMw(graph));
1260  assert(!graph_pc_isRootedPcMw(graph));
1261 
1262  SCIP_CALL(SCIPallocBufferArray(scip, &dist, nnodes));
1263  SCIP_CALL(SCIPallocBufferArray(scip, &visited, nnodes));
1264  SCIP_CALL(SCIPallocBufferArray(scip, &termmark, nnodes));
1265 
1266  for( int i = 0; i < nnodes; i++ )
1267  {
1268  visited[i] = FALSE;
1269  state[i] = UNKNOWN;
1270  dist[i] = FARAWAY;
1271  }
1272 
1273  assert(transgraph->extended);
1274 
1275  if( graphextended )
1276  graph_pc_2org(scip, graph);
1277 
1278  graph_pc_termMarkProper(graph, termmark);
1279 
1280  assert(rerun || nroots == 0);
1281 
1282  /*
1283  * get possible roots
1284  */
1285 
1286  BMSclearMemoryArray(isfixedterm, nnodes);
1287 
1288  if( rerun )
1289  {
1290  for( int i = 0; i < nroots; i++ )
1291  isfixedterm[roots[i]] = TRUE;
1292  }
1293 
1294  SCIPdebugMessage("before findDaRootsMark: all roots: %d, nodes: %d edges: %d terms: %d \n",
1295  nroots, nnodes, graph->edges, graph->terms);
1296 
1297  /* has transgraph non-artificial root (and arcs to pseudo-terminals)? */
1298  if( probrooted )
1299  {
1300  const int transroot = transgraph->source;
1301 
1302  assert(transgraph->term2edge != NULL);
1303 
1304  for( int e = transgraph->outbeg[transroot]; e != EAT_LAST; e = transgraph->oeat[e] )
1305  {
1306  const int pseudoterm = transgraph->head[e];
1307 
1308  if( Is_term(transgraph->term[pseudoterm]) && transgraph->term2edge[pseudoterm] >= 0 )
1309  {
1310  findRootsMark(scip, graph, transgraph, termmark, cost, bestcost, lpobjval, bestlpobjval, upperbound, rerun, probrooted, pseudoterm, e,
1311  isfixedterm, roots, &nroots, pathedge, visited, dist);
1312  }
1313  }
1314  }
1315  /* transgraph has artificial root, so no arcs to pseudo-terminals */
1316  else
1317  {
1318  for( int e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1319  {
1320  const int pseudoterm = graph->head[e];
1321 
1322  if( Is_pseudoTerm(graph->term[pseudoterm]) )
1323  {
1324  findRootsMark(scip, graph, transgraph, termmark, cost, bestcost, lpobjval, bestlpobjval, upperbound, rerun, probrooted, pseudoterm, e,
1325  isfixedterm, roots, &nroots, pathedge, visited, dist);
1326  }
1327  }
1328  }
1329 
1330  SCIPdebugMessage("...after: new roots in rerun %d all roots: %d, nodes: %d edges: %d terms: %d \n\n", nroots - *rootscount,
1331  nroots, nnodes, graph->edges, graph->terms);
1332 
1333  /* could more roots be found? */
1334  if( nroots > *rootscount && graph->terms > 2 )
1335  {
1336  /*
1337  * try to find additional roots by connecting walks
1338  */
1339  SCIP_Bool rerunwalks = TRUE;
1340 
1341  for( int rounds = 0; rounds < 3 && rerunwalks; rounds++ )
1342  {
1343  rerunwalks = FALSE;
1344 
1345  for( int i = 0; i < nnodes; i++ )
1346  {
1347  SCIP_Bool connected;
1348 
1349  if( !Is_term(graph->term[i]) || isfixedterm[i] || graph_pc_knotIsFixedTerm(graph, i) )
1350  continue;
1351 
1352  if( graph->grad[i] == 0 )
1353  {
1354  assert(graph_pc_isPcMw(graph) && graph_pc_knotIsNonLeafTerm(graph, i));
1355  continue;
1356  }
1357 
1358  connected = graph_sdWalksConnected(scip, graph, termmark, graph->cost, isfixedterm, i, 1500, dist, pathedge, &nvisits,
1359  visited, TRUE);
1360 
1361  if( connected )
1362  {
1363  assert(nroots < graph->terms);
1364 
1365  roots[nroots++] = i;
1366  isfixedterm[i] = TRUE;
1367  rerunwalks = TRUE;
1368 
1369  SCIPdebugMessage("WALK-CONNECT: added new root %d prize: %f \n", i, graph->prize[i]);
1370  }
1371 
1372 #ifndef NDEBUG
1373  for( int k = 0; k < nnodes; k++ )
1374  {
1375  assert(state[k] == UNKNOWN);
1376  assert(visited[k] == FALSE);
1377  assert(dist[k] == FARAWAY);
1378  }
1379 #endif
1380  }
1381  } /* for rounds < 3 */
1382 
1383  SCIPdebugMessage("number of terminals found by DA: %d \n", nroots);
1384 
1385  } /* look for additional roots */
1386 
1387  SCIPdebugMessage("new roots in rerun %d all roots: %d, nodes: %d \n", nroots - *rootscount, nroots, nnodes);
1388 
1389  *rootscount = nroots;
1390 
1391  if( graphextended )
1392  graph_pc_2trans(scip, graph);
1393 
1394  SCIPfreeBufferArray(scip, &termmark);
1395  SCIPfreeBufferArray(scip, &visited);
1396  SCIPfreeBufferArray(scip, &dist);
1397 
1398  return SCIP_OKAY;
1399 }
1400 
1401 
1402 /** computes TM solution and adds it too pool */
1403 static
1405  SCIP* scip, /**< SCIP data structure */
1406  GRAPH* graph, /**< graph data structure */
1407  int* result, /**< solution */
1408  STPSOLPOOL* pool /**< the pool */
1409 )
1410 {
1411  SCIP_Bool success;
1412  SCIP_Real ub;
1413 
1414  /* compute second solution and add to pool */
1416  graph, NULL, NULL, result, BND_TMHEUR_NRUNS_RPC, graph->source, graph->cost, graph->cost, NULL, NULL, &success) );
1417  assert(success);
1418 
1419  SCIP_CALL( SCIPStpHeurLocalRun(scip, graph, result) );
1420  ub = getSolObj(scip, graph, result);
1421 
1422  SCIP_CALL( solpool_addSol(scip, ub, result, pool, &success) );
1423  SCIPdebugMessage("added initial TM sol to pool? %d , ub %f \n", success, ub);
1424 
1425  return SCIP_OKAY;
1426 }
1427 
1428 
1429 /** set prize of marked terminals to blocked */
1430 static
1432  SCIP* scip, /**< SCIP data structure */
1433  const int* roots, /**< root array */
1434  int nrootsold, /**< old number of roots */
1435  int nrootsnew, /**< new number of roots */
1436  SCIP_Real prizesum, /**< sum of positive prizes */
1437  GRAPH* graph, /**< graph data structure */
1438  SCIP_Bool* userec, /**< recombination? */
1439  STPSOLPOOL** solpool /**< solution pool */
1440 )
1441 {
1442  const int root = graph->source;
1443  const SCIP_Bool graphextended = graph->extended;
1444 
1445  if( graphextended )
1446  graph_pc_2org(scip, graph);
1447 
1448  if( *userec && *solpool != NULL )
1449  {
1450  *userec = FALSE;
1451  solpool_free(scip, solpool);
1452  *solpool = NULL;
1453  }
1454 
1455  assert(graph != NULL);
1456  assert(roots != NULL);
1457  assert(!graph->extended);
1458  assert(nrootsnew >= 0 && nrootsold >= 0);
1459 
1460  for( int i = nrootsold; i < nrootsnew; i++ )
1461  {
1462  int e;
1463  const int term = roots[i];
1464  const int pterm = graph_pc_getTwinTerm(graph, term);
1465 
1466  assert(Is_term(graph->term[term]));
1467  assert(SCIPisPositive(scip, graph->prize[term]));
1468  assert(pterm >= 0);
1469  assert(Is_pseudoTerm(graph->term[pterm]));
1470 
1471  for( e = graph->inpbeg[pterm]; e != EAT_LAST; e = graph->ieat[e] )
1472  if( root == graph->tail[e] )
1473  break;
1474 
1475  assert(e != EAT_LAST);
1476  assert(SCIPisEQ(scip, graph->prize[term], graph->cost[e]));
1477 
1478  graph->prize[term] = prizesum;
1479  graph->cost[e] = prizesum;
1480  }
1481 
1482  if( graphextended )
1483  graph_pc_2trans(scip, graph);
1484 }
1485 
1486 /** are the reduced costs still valid, i.e. are there zero cost paths from the root to all terminals? */
1487 static
1489  SCIP* scip, /**< SCIP data structure */
1490  GRAPH* transgraph, /**< graph data structure */
1491  const SCIP_Real* cost, /**< dual ascent costs */
1492  int* nodearrint, /**< int array */
1493  STP_Bool* nodearrbool /**< bool array */
1494 )
1495 {
1496  int* const queue = nodearrint;
1497  STP_Bool* visited = nodearrbool;
1498  int qsize;
1499  const int root = transgraph->source;
1500  const int nnodes = transgraph->knots;
1501 
1502  /*
1503  * construct new graph corresponding to zero cost paths from the root to all terminals
1504  */
1505 
1506  BMSclearMemoryArray(visited, nnodes);
1507 
1508  qsize = 0;
1509  visited[root] = TRUE;
1510  queue[qsize++] = root;
1511 
1512  /* DFS */
1513  while( qsize )
1514  {
1515  const int k = queue[--qsize];
1516 
1517  /* traverse outgoing arcs */
1518  for( int a = transgraph->outbeg[k]; a != EAT_LAST; a = transgraph->oeat[a] )
1519  {
1520  const int head = transgraph->head[a];
1521 
1522  if( !visited[head] && SCIPisZero(scip, cost[a]) )
1523  {
1524  visited[head] = TRUE;
1525  queue[qsize++] = head;
1526  }
1527  }
1528  assert(qsize <= nnodes);
1529  }
1530 
1531  for( int k = 0; k < nnodes; k++ )
1532  if( Is_term(transgraph->term[k]) && !visited[k] )
1533  {
1534  return FALSE;
1535  }
1536 
1537  return TRUE;
1538 }
1539 
1540 
1541 /** returns maximum allowed deviation for dual-ascent */
1542 static
1544  const RPDA* paramsda, /**< parameters */
1545  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
1546 )
1547 {
1548  SCIP_Real damaxdeviation;
1549 
1550  assert(paramsda && randnumgen);
1551 
1552 #if 1
1554 #else
1555  if( paramsda->damode > 0 )
1557  else
1558  damaxdeviation = -1.0;
1559 #endif
1560 
1561  return damaxdeviation;
1562 }
1563 
1564 
1565 /** decide whether guided DA is promising */
1566 static
1568  const GRAPH* graph, /**< graph structure */
1569  int run, /**< number of current run */
1570  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
1571 )
1572 {
1573  assert(run >= 0);
1574 
1575  if( !graph_typeIsUndirected(graph) )
1576  {
1577  assert(run < DEFAULT_DARUNS_DIRECTED);
1578  if( run > 0 )
1579  return TRUE;
1580  }
1581 
1582  return ((run > 1) && (SCIPrandomGetInt(randnumgen, 0, 2) < 2));
1583 }
1584 
1585 /** order roots */
1586 static
1588  SCIP* scip, /**< SCIP data structure */
1589  const GRAPH* graph, /**< graph structure */
1590  int* terms, /**< sol int array corresponding to upper bound */
1591  int nterms, /**< number of terminals */
1592  SCIP_Bool randomize, /**< randomize? */
1593  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
1594 )
1595 {
1596  int* termdegs;
1597  int maxdeg = 0;
1598  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(graph);
1599 
1600  assert(terms != NULL);
1601  assert(nterms > 0);
1602 
1603  if( graph_typeIsDirected(graph) )
1604  {
1605  for( int i = 0; i < nterms; i++ )
1606  terms[i] = graph->source;
1607 
1608  return SCIP_OKAY;
1609  }
1610 
1611  SCIP_CALL( SCIPallocBufferArray(scip, &termdegs, nterms) );
1612 
1613  for( int i = 0; i < nterms; i++ )
1614  {
1615  const int grad = graph->grad[terms[i]];
1616  assert(terms[i] >= 0);
1617 
1618  termdegs[i] = grad;
1619 
1620  if( grad > maxdeg )
1621  maxdeg = termdegs[i];
1622 
1623  if( isRpcmw )
1624  {
1625  assert(graph_pc_knotIsFixedTerm(graph, terms[i] ));
1626 
1627  /* make sure root is selected for RPC/RMW */
1628  if( terms[i] == graph->source )
1629  termdegs[i] = 2 * graph->knots;
1630  }
1631  }
1632 
1633  if( randomize )
1634  {
1635  assert(randnumgen);
1636  for( int i = 0; i < nterms; i++ )
1637  termdegs[i] += SCIPrandomGetInt(randnumgen, 0, 2 * maxdeg);
1638  }
1639 
1640  SCIPsortDownIntInt(termdegs, terms, nterms);
1641 
1642  SCIPfreeBufferArray(scip, &termdegs);
1643 
1644  return SCIP_OKAY;
1645 }
1646 
1647 
1648 /** initializes reduced costs data */
1649 static
1651  SCIP* scip, /**< SCIP data structure */
1652  const GRAPH* graph, /**< graph data structure */
1653  const RPDA* paramsda, /**< parameters */
1654  int nLevels, /**< number of levels for extended reductions */
1655  REDCOST** redcostdata /**< reduced cost data */
1656 )
1657 {
1658  const int nnodes = graph_get_nNodes(graph);
1659  const int nedges = graph_get_nEdges(graph);
1660  RCPARAMS rcparams = { .cutoff = -1.0, .nLevels = 1, .nCloseTerms = 3,
1661  .nnodes = nnodes, .nedges = nedges, .redCostRoot = UNKNOWN };
1662 
1663  if( paramsda->extredMode != extred_none )
1664  {
1665  rcparams.nLevels = nLevels;
1666  }
1667 
1668  SCIP_CALL( redcosts_initFromParams(scip, &rcparams, redcostdata) );
1669 
1670  return SCIP_OKAY;
1671 }
1672 
1673 
1674 /** frees reduced costs data */
1675 static
1677  SCIP* scip, /**< SCIP data structure */
1678  REDCOST** redcostdata /**< reduced cost data */
1679 )
1680 {
1681  redcosts_free(scip, redcostdata);
1682 }
1683 
1684 
1685 /** number of runs */
1686 static
1688  const GRAPH* graph, /**< graph structure */
1689  const RPDA* paramsda, /**< parameters */
1690  int nterms /**< number of terminals */
1691 )
1692 {
1693  int nruns;
1694 
1695  if( paramsda->damode == STP_DAMODE_FAST )
1696  {
1697  nruns = MIN(nterms, DEFAULT_DARUNS_FAST);
1698  }
1699  else
1700  {
1701  nruns = MIN(nterms, DEFAULT_DARUNS);
1702 
1703  if( graph_typeIsSpgLike(graph) )
1704  {
1705  SCIP_Real ratio;
1706  int nnodes;
1707  graph_get_nVET(graph, &nnodes, NULL, NULL);
1708  ratio = (SCIP_Real) graph->terms / (SCIP_Real) nnodes;
1709 
1710  if( ratio >= DARUNS_TERMRATIO_LOW )
1711  nruns--;
1712  if( ratio >= DARUNS_TERMRATIO_MED )
1713  nruns--;
1714  if( ratio >= DARUNS_TERMRATIO_HIGH )
1715  nruns--;
1716  if( ratio >= DARUNS_TERMRATIO_HUGE )
1717  nruns--;
1718  }
1719  }
1720 
1721  if( !graph_typeIsUndirected(graph) )
1722  {
1723  nruns = MIN(nruns, DEFAULT_DARUNS_DIRECTED);
1724  }
1725 
1726  if( paramsda->damode == STP_DAMODE_HOPS )
1727  {
1728  assert(graph->stp_type == STP_DHCSTP);
1729  nruns = MIN(nruns, 2);
1730  }
1731 
1732  nruns = MAX(nruns, 1);
1733 
1734  return nruns;
1735 }
1736 
1737 
1738 /** initializes DA round */
1739 static
1741  SCIP* scip, /**< SCIP data structure */
1742  SCIP_Real upperbound, /**< upper bound */
1743  GRAPH* graph, /**< graph structure */
1744  REDCOST* redcostdata, /**< reduced cost data */
1745  STP_Bool* arcsdeleted, /**< array */
1746  SCIP_Real* cutoffbound /**< cut-off bound */
1747 )
1748 {
1749  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(graph);
1750 
1751  redcosts_setAndReturnCutoffFromBoundTop(upperbound, redcostdata, cutoffbound);
1752 
1753  if( isRpcmw )
1754  graph_pc_2org(scip, graph);
1755  else
1756  graph_mark(graph);
1757 
1758  if( graph_typeIsUndirected(graph) )
1759  {
1760  const int nedges = graph_get_nEdges(graph);
1761 
1762  /* NOTE: because we change the root node for dual-ascent, the deleted arcs don't
1763  * stay valid between rounds */
1764  for( int e = 0; e < nedges; e++ )
1765  arcsdeleted[e] = FALSE;
1766  }
1767 
1768  SCIP_CALL( redcosts_initializeDistancesTop(scip, graph, redcostdata) );
1769 
1770  return SCIP_OKAY;
1771 }
1772 
1773 
1774 /** for exiting DA round */
1775 static
1777  SCIP* scip, /**< SCIP data structure */
1778  int ndeletions_run, /**< number of deletions */
1779  GRAPH* graph, /**< graph structure */
1780  int* nelims /**< number of eliminations */
1781 )
1782 {
1783  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(graph);
1784 
1785  assert(scip && nelims);
1786  assert(ndeletions_run >= 0 && *nelims >= 0);
1787 
1788  if( ndeletions_run > 0 && !isRpcmw )
1789  {
1790  if( graph_typeIsDirected(graph) )
1791  reduce_unconnectedForDirected(scip, graph);
1792  else
1793  reduce_unconnected(scip, graph);
1794  }
1795 
1796  assert(graph_valid(scip, graph));
1797 
1798  if( !isRpcmw )
1799  graph_mark(graph);
1800  else
1801  graph_pc_2trans(scip, graph);
1802 
1803  *nelims += ndeletions_run;
1804  SCIPdebugMessage("new deletions: %d \n", ndeletions_run);
1805 }
1806 
1807 
1808 /** try to improve both dual and primal solution */
1809 static
1811  SCIP* scip,
1812  GRAPH* graph,
1813  GRAPH* transgraph,
1814  STPSOLPOOL* pool,
1815  PATH* vnoi,
1816  SCIP_Real* cost,
1817  SCIP_Real* bestcost,
1818  SCIP_Real* pathdist,
1819  int* pathedge,
1820  int* result,
1821  int* result2,
1822  int* transresult,
1823  STP_Bool* nodearrchar,
1824  SCIP_Real* upperbound,
1825  SCIP_Real* lpobjval,
1826  SCIP_Real* bestlpobjval,
1827  SCIP_Real* minpathcost,
1828  SCIP_Bool* apsol,
1829  SCIP_Real offset,
1830  int extnedges
1831  )
1832 {
1833  SCIP_Real lb;
1834  int e;
1835  const int root = graph->source;
1836  const int nedges = graph->edges;
1837  const int transnedges = transgraph->edges;
1838 
1839  assert(graph_pc_isPcMw(graph));
1840 
1841  graph_pc_2transcheck(scip, graph);
1842 
1843  SCIP_CALL( computeSteinerTreeRedCostsPcMw(scip, graph, pool, cost, upperbound, result, result2, pathedge, nodearrchar, apsol) );
1844 
1845  /* does result not contain a valid solution? */
1846  if( !(*apsol) )
1847  BMScopyMemoryArray(result, result2, nedges);
1848 
1849  SCIPdebugMessage("DA: pertubated sol value %f \n", *upperbound);
1850 
1851  /* compute guiding solution */
1852 
1853  BMScopyMemoryArray(transresult, result, nedges);
1854 
1855  for( e = nedges; e < transnedges; e++ )
1856  transresult[e] = UNKNOWN;
1857 
1858  /* non-trivial solution */
1859  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1860  if( Is_term(graph->term[graph->head[e]]) && result[e] != CONNECT )
1861  break;
1862 
1863  if( e != EAT_LAST)
1864  {
1865  int k;
1866  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
1867  if( !Is_term(graph->term[graph->head[e]]) && result[e] == CONNECT )
1868  break;
1869 
1870  assert(e != EAT_LAST);
1871  k = graph->head[e];
1872 
1873  for( e = transgraph->outbeg[k]; e != EAT_LAST; e = transgraph->oeat[e] )
1874  {
1875  if( transgraph->head[e] == graph->knots )
1876  {
1877  transresult[e] = CONNECT;
1878  break;
1879  }
1880  }
1881  }
1882 
1883  assert(!(*apsol) || solstp_isValid(scip, graph, result));
1884  assert(graph_valid(scip, transgraph));
1885  assert(root == transgraph->source);
1886 
1887  {
1888  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = root,
1889  .is_pseudoroot = TRUE, .damaxdeviation = -1.0 };
1890 
1891  SCIP_CALL( dualascent_exec(scip, transgraph, transresult, &daparams, cost, &lb) );
1892  }
1893 
1894  lb += offset;
1895  *lpobjval = lb;
1896 
1897  SCIP_CALL( computeSteinerTreeRedCostsPcMw(scip, graph, pool, cost, upperbound, result, result2, pathedge, nodearrchar, apsol) );
1898 
1899  assert(!(*apsol) || solstp_isValid(scip, graph, result));
1900 
1901  if( SCIPisGE(scip, lb, *bestlpobjval) )
1902  {
1903  *bestlpobjval = lb;
1904  BMScopyMemoryArray(bestcost, cost, extnedges);
1905  }
1906 
1907  /* the required reduced path cost to be surpassed */
1908  *minpathcost = *upperbound - *lpobjval;
1909 
1910  return SCIP_OKAY;
1911 }
1912 
1913 /** compute Voronoi region for dual-ascent elimination for PC/MW */
1914 static
1916  SCIP* scip,
1917  GRAPH* transgraph,
1918  PATH* vnoi,
1919  const SCIP_Real* cost,
1920  SCIP_Real* costrev,
1921  SCIP_Real* pathdist,
1922  int* vbase,
1923  int* pathedge
1924 )
1925 {
1926  const int root = transgraph->source;
1927  const int transnnodes = transgraph->knots;
1928  const int transnedges = transgraph->edges;
1929 
1930  for( int k = 0; k < transnnodes; k++ )
1931  transgraph->mark[k] = (transgraph->grad[k] > 0);
1932 
1933  /* distance from root to all nodes */
1934  graph_path_execX(scip, transgraph, root, cost, pathdist, pathedge);
1935 
1936  for( int k = 0; k < transnnodes; k++ )
1937  if( Is_term(transgraph->term[k]) )
1938  assert(SCIPisEQ(scip, pathdist[k], 0.0));
1939 
1940  for( int e = 0; e < transnedges; e++ )
1941  costrev[e] = cost[flipedge(e)];
1942 
1943  /* no paths should go back to the root */
1944  for( int e = transgraph->outbeg[root]; e != EAT_LAST; e = transgraph->oeat[e] )
1945  costrev[e] = FARAWAY;
1946 
1947  /* build Voronoi diagram wrt incoming arcs */
1948  graph_add1stTermPaths(transgraph, costrev, vnoi, vbase, transgraph->path_state);
1949 }
1950 
1951 
1952 /** reduce graph with non-artificial root (SPG, RPC ...) based on information from dual ascent and given upper bound */
1953 static
1955  SCIP* scip, /**< SCIP data structure */
1956  GRAPH* graph, /**< graph data structure */
1957  STP_Bool* marked, /**< edge array to mark which (directed) edge can be removed */
1958  const REDCOST* redcostdata, /**< reduced cost data */
1959  const int* result, /**< sol int array */
1960  SCIP_Bool solgiven, /**< is sol given? */
1961  int* nfixedp /**< number of fixed edges pointer */
1962 )
1963 {
1964  const PATH *vnoi = redcosts_getNodeToTermsPathsTop(redcostdata);
1965  const SCIP_Real *cost = redcosts_getEdgeCostsTop(redcostdata);
1966  const SCIP_Real *pathdist = redcosts_getRootToNodeDistTop(redcostdata);
1967  const SCIP_Real cutoffbound = redcosts_getCutoffTop(redcostdata);
1968  int* incidents = NULL;
1969  STP_Bool* nodearrchar = NULL;
1970  const int nnodes = graph->knots;
1971  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(graph);
1972  const SCIP_Bool keepsol = (solgiven && SCIPisZero(scip, cutoffbound));
1973  const SCIP_Bool isDirected = !graph_typeIsUndirected(graph);
1974 
1975  assert(GE(cutoffbound, 0.0));
1976 
1977  if( isRpcmw )
1978  {
1979  SCIP_CALL( SCIPallocBufferArray(scip, &incidents, nnodes) );
1980 
1981 #ifndef NDEBUG
1982  assert(!graph->extended);
1983  for( int k = 0; k < nnodes; k++ )
1984  {
1985  if( Is_pseudoTerm(graph->term[k]) )
1986  assert(!graph->mark[k] && graph->grad[k] == 2);
1987  else
1988  assert(graph->mark[k] || graph->grad[k] == 0);
1989  }
1990 #endif
1991  }
1992 
1993  if( solgiven )
1994  {
1995  SCIP_CALL( SCIPallocBufferArray(scip, &nodearrchar, nnodes) );
1996  solstp_setVertexFromEdge(graph, result, nodearrchar);
1997  }
1998 
1999  /* main loop: try to reduce */
2000  for( int k = 0; k < nnodes; k++ )
2001  {
2002  SCIP_Real redcost;
2003  int e;
2004 
2005  if( !graph->mark[k] )
2006  continue;
2007 
2008  assert(!Is_pseudoTerm(graph->term[k]));
2009 
2010  redcost = pathdist[k] + vnoi[k].dist;
2011 
2012  if( isRpcmw && Is_term(graph->term[k]) && !graph_pc_knotIsFixedTerm(graph, k) && !graph_pc_termIsNonLeafTerm(graph, k)
2013  && SCIPisGT(scip, redcost, cutoffbound) )
2014  {
2015  daRpcmwDeleteTermIncidents(scip, vnoi, k, graph, incidents, nfixedp);
2016  continue;
2017  }
2018 
2019  /* note: if we want to keep the solution we cannot just delete vertices */
2020  if( !Is_term(graph->term[k]) && !keepsol &&
2021  (SCIPisFeasGT(scip, redcost, cutoffbound) || (solgiven && SCIPisEQ(scip, redcost, cutoffbound) && !nodearrchar[k])) )
2022  {
2023  (*nfixedp) += graph->grad[k];
2024  graph_knot_del(scip, graph, k, TRUE);
2025  continue;
2026  }
2027 
2028  e = graph->outbeg[k];
2029  while( e != EAT_LAST )
2030  {
2031  const int head = graph->head[e];
2032  const int enext = graph->oeat[e];
2033 
2034  /* for rpc no artificial terminal arcs should be deleted */
2035  if( (isRpcmw && !graph->mark[head])
2036  || (keepsol && (result[e] == CONNECT || result[flipedge(e)] == CONNECT)) )
2037  {
2038  e = enext;
2039  continue;
2040  }
2041 
2042  redcost = pathdist[k] + cost[e] + vnoi[head].dist;
2043 
2044  if( SCIPisGT(scip, redcost, cutoffbound)
2045  || (solgiven && SCIPisEQ(scip, redcost, cutoffbound) && result[e] != CONNECT && result[flipedge(e)] != CONNECT) )
2046  {
2047  if( marked[flipedge(e)] )
2048  {
2049  graph_edge_del(scip, graph, e, TRUE);
2050  (*nfixedp)++;
2051  }
2052  else
2053  {
2054  marked[e] = TRUE;
2055  if( isDirected )
2056  graph->cost[e] = FARAWAY;
2057  }
2058  }
2059  e = enext;
2060  }
2061  }
2062 
2063  SCIPfreeBufferArrayNull(scip, &nodearrchar);
2064  SCIPfreeBufferArrayNull(scip, &incidents);
2065 
2066  return SCIP_OKAY;
2067 }
2068 
2069 /** reduce PCSTP or MWCS graph based on information from dual ascent and given upper bound */
2070 static
2072  SCIP* scip, /**< SCIP data structure */
2073  GRAPH* graph, /**< graph data structure */
2074  GRAPH* transgraph, /**< graph data structure */
2075  const PATH* vnoi, /**< Voronoi data structure */
2076  const SCIP_Real* cost, /**< dual ascent costs */
2077  const SCIP_Real* pathdist, /**< distance array from shortest path calculations */
2078  SCIP_Real minpathcost, /**< the required reduced path cost to be surpassed */
2079  const int* result, /**< sol int array */
2080  STP_Bool* marked, /**< edge array to mark which (directed) edge can be removed */
2081  STP_Bool* nodearrchar, /**< node array storing solution vertices */
2082  SCIP_Bool solgiven, /**< is sol given? */
2083  SCIP_Bool deleteTransEdges /**< delete edges of transformed graph */
2084 )
2085 {
2086  const int nnodes = graph_get_nNodes(graph);
2087  int nfixed;
2088  SCIP_Real tmpcost;
2089  SCIP_Bool keepsol = FALSE;
2090  STP_Vectype(int) edges_delete = NULL;
2091 
2092  assert(SCIPisGE(scip, minpathcost, 0.0));
2093 
2094  if( minpathcost < 0.0 )
2095  minpathcost = 0.0;
2096 
2097  nfixed = 0;
2098 
2099  graph_pc_2orgcheck(scip, graph);
2100 
2101  if( solgiven )
2102  {
2103  assert(solstp_isValid(scip, graph, result));
2104 
2105  solstp_setVertexFromEdge(graph, result, nodearrchar);
2106 
2107  if( SCIPisZero(scip, minpathcost) )
2108  keepsol = TRUE;
2109  }
2110 
2111  /* try to eliminate vertices and edges */
2112  for( int k = 0; k < nnodes; k++ )
2113  {
2114  if( !graph->mark[k] )
2115  continue;
2116 
2117  assert(!Is_pseudoTerm(graph->term[k]));
2118 
2119  if( Is_term(graph->term[k]) )
2120  {
2121  int e = graph->outbeg[k];
2122  while( e != EAT_LAST )
2123  {
2124  const int etmp = graph->oeat[e];
2125  tmpcost = pathdist[k] + cost[e] + vnoi[graph->head[e]].dist;
2126 
2127  if( graph->mark[graph->head[e]] &&
2128  ((SCIPisGT(scip, tmpcost, minpathcost) && (!keepsol || (result[e] != CONNECT && result[flipedge(e)] != CONNECT))) ||
2129  (solgiven && tmpcost >= minpathcost && result[e] != CONNECT && result[flipedge(e)] != CONNECT)) )
2130  {
2131  if( marked[flipedge(e)] )
2132  {
2133  assert(!Is_pseudoTerm(graph->term[graph->head[e]]));
2134 
2135  StpVecPushBack(scip, edges_delete, e);
2136 
2137  // graph_edge_del(scip, graph, e, TRUE);
2138  // graph_edge_del(scip, transgraph, e, FALSE);
2139  }
2140  else
2141  {
2142  marked[e] = TRUE;
2143  }
2144  }
2145  e = etmp;
2146  }
2147  continue;
2148  }
2149 
2150  tmpcost = pathdist[k] + vnoi[k].dist;
2151 
2152  if( (SCIPisGT(scip, tmpcost, minpathcost) && !keepsol) ||
2153  (solgiven && tmpcost >= minpathcost && !nodearrchar[k]))
2154  {
2155  for( int e = transgraph->outbeg[k]; e != EAT_LAST; e = transgraph->oeat[e] )
2156  {
2157  StpVecPushBack(scip, edges_delete, e);
2158 
2159  //graph_edge_del(scip, transgraph, e, FALSE);
2160  //graph_edge_del(scip, graph, e, TRUE);
2161  }
2162  }
2163  else
2164  {
2165  int e = transgraph->outbeg[k];
2166  while( e != EAT_LAST )
2167  {
2168  const int etmp = transgraph->oeat[e];
2169  tmpcost = pathdist[k] + cost[e] + vnoi[transgraph->head[e]].dist;
2170 
2171  if( (SCIPisGT(scip, tmpcost, minpathcost) && (!keepsol || (result[e] != CONNECT && result[flipedge(e)] != CONNECT))) ||
2172  (solgiven && tmpcost >= minpathcost && result[e] != CONNECT && result[flipedge(e)] != CONNECT) )
2173  {
2174  if( marked[flipedge(e)] )
2175  {
2176  // graph_edge_del(scip, graph, e, TRUE);
2177  // graph_edge_del(scip, transgraph, e, FALSE);
2178  StpVecPushBack(scip, edges_delete, e);
2179  }
2180  else
2181  {
2182  marked[e] = TRUE;
2183  }
2184  }
2185  e = etmp;
2186  }
2187  }
2188  }
2189 
2190  for( int i = 0; i < StpVecGetSize(edges_delete); i++ )
2191  {
2192  const int e = edges_delete[i];
2193 
2194  if( graph->oeat[e] == EAT_FREE )
2195  continue;
2196 
2197  graph_edge_del(scip, graph, e, TRUE);
2198  nfixed++;
2199 
2200  if( deleteTransEdges )
2201  graph_edge_del(scip, transgraph, e, FALSE);
2202  }
2203 
2204  StpVecFree(scip, edges_delete);
2205  SCIPdebugMessage("DA: eliminations %d \n", nfixed);
2206 
2207  return nfixed;
2208 }
2209 
2210 /** try to run reduction method for best known reduced costs (if they are valid) */
2211 static
2213  SCIP* scip, /**< SCIP data structure */
2214  GRAPH* graph, /**< graph data structure */
2215  GRAPH* transgraph, /**< graph data structure */
2216  PATH* vnoi, /**< Voronoi data structure */
2217  const SCIP_Real* cost, /**< dual ascent costs */
2218  SCIP_Real* costrev, /**< SCIP_Real array */
2219  SCIP_Real* bestcost, /**< best dual ascent costs */
2220  SCIP_Real* pathdist, /**< distance array from shortest path calculations */
2221  SCIP_Real* upperbound, /**< upper bound */
2222  SCIP_Real* lpobjval, /**< reduced cost value */
2223  SCIP_Real* bestlpobjval, /**< best reduced cost value */
2224  SCIP_Real* minpathcost, /**< the required reduced path cost to be surpassed */
2225  SCIP_Real oldupperbound, /**< old upper bound */
2226  const int* result, /**< sol int array */
2227  int* vbase, /**< array for Voronoi bases */
2228  int* state, /**< int 4 * nnodes array for internal computations */
2229  int* pathedge, /**< array for predecessor edge on a path */
2230  STP_Bool* marked, /**< edge array to mark which (directed) edge can be removed */
2231  STP_Bool* nodearrchar, /**< node array storing solution vertices */
2232  SCIP_Bool* solgiven, /**< is sol given? */
2233  int extnedges /**< number of edges for transgraph */
2234 )
2235 {
2236  const SCIP_Bool dualisvalid = daRedCostIsValid(scip, transgraph, bestcost, state, nodearrchar);
2237 
2238  if( !dualisvalid )
2239  {
2240  *bestlpobjval = *lpobjval;
2241  BMScopyMemoryArray(bestcost, cost, extnedges);
2242  }
2243 
2244  /* has upperbound and changed, and is best reduced cost valid and different from cost? */
2245  if( SCIPisGT(scip, *bestlpobjval, *lpobjval) && SCIPisLT(scip, *upperbound, oldupperbound) )
2246  {
2247  *solgiven = *solgiven && solstp_isUnreduced(scip, graph, result);
2248 
2249  assert(!(*solgiven) || solstp_isValid(scip, graph, result));
2250 
2251  *minpathcost = *upperbound - *bestlpobjval;
2252  assert(SCIPisGE(scip, *minpathcost, 0.0));
2253 
2254  computeTransVoronoi(scip, transgraph, vnoi, bestcost, costrev, pathdist, vbase, pathedge);
2255 
2256  return reducePcMw(scip, graph, transgraph, vnoi, bestcost, pathdist, *minpathcost, result, marked, nodearrchar, *solgiven, TRUE);
2257  }
2258  return 0;
2259 }
2260 
2261 /** promising? */
2262 static
2264  const GRAPH* g /**< graph data structure */
2265 )
2266 {
2267  SCIP_Bool isPromising;
2268  int nterms;
2269  int nnodes;
2270 
2271  assert(g);
2272 
2273  graph_get_nVET(g, &nnodes, NULL, &nterms);
2274 
2275  isPromising = ((SCIP_Real) nterms / (SCIP_Real) nnodes < 0.1);
2276 
2277  return isPromising;
2278 }
2279 
2280 
2281 /** deletes edges */
2282 static
2284  SCIP* scip, /**< SCIP data structure */
2285  const REDCOST* redcostdata, /**< reduced cost data */
2286  const int* result, /**< solution */
2287  GRAPH* g, /**< graph data structure */
2288  int* nelims /**< pointer to store number of reduced edges */
2289  )
2290 {
2291  STP_Bool* edges_isDeletable;
2292 
2293  const int nedges = graph_get_nEdges(g);
2294 
2295  SCIP_CALL( SCIPallocBufferArray(scip, &edges_isDeletable, nedges) );
2296  BMSclearMemoryArray(edges_isDeletable, nedges);
2297 
2298  SCIP_CALL( reduceRootedProb(scip, g, edges_isDeletable, redcostdata, result, TRUE, nelims) );
2299 
2300  SCIPfreeBufferArray(scip, &edges_isDeletable);
2301 
2302  return SCIP_OKAY;
2303 }
2304 
2305 
2306 /** pseudo-eliminates nodes */
2307 static
2309  SCIP* scip, /**< SCIP data structure */
2310  REDCOST* redcostdata, /**< reduced cost data */
2311  const int* result, /**< solution */
2312  SCIP_Real objbound_upper, /**< objective */
2313  GRAPH* g, /**< graph data structure */
2314  SCIP_Real* offsetp, /**< pointer to store offset */
2315  int* nelims /**< pointer to store number of reduced edges */
2316  )
2317 {
2318  SCIP_Real* nodereplacebounds;
2319  SCIP_Bool* pseudoDelNodes;
2320  int nreplacings = 0;
2321 
2322  SCIP_CALL( SCIPallocBufferArray(scip, &nodereplacebounds, g->knots) );
2323  SCIP_CALL( SCIPallocBufferArray(scip, &pseudoDelNodes, g->knots) );
2324 
2325  SCIP_CALL( updateNodeReplaceBounds(scip, redcostdata, g, nodereplacebounds, objbound_upper, TRUE, FALSE));
2326  markPseudoDeletablesFromBounds(scip, g, nodereplacebounds, objbound_upper, pseudoDelNodes);
2327  SCIP_CALL( reduce_applyPseudoDeletions(scip, pseudoDelNodes, redcostdata, g, offsetp, &nreplacings) );
2328 
2329  SCIPfreeBufferArray(scip, &pseudoDelNodes);
2330  SCIPfreeBufferArray(scip, &nodereplacebounds);
2331 
2332  *nelims += nreplacings;
2333 
2334  return SCIP_OKAY;
2335 }
2336 
2337 /** eliminates RPC/RMW potential-terminals */
2338 static
2340  SCIP* scip, /**< SCIP data structure */
2341  const REDCOST* redcostdata, /**< reduced cost data */
2342  GRAPH* g, /**< graph data structure */
2343  SCIP_Real* offsetp, /**< pointer to store offset */
2344  int* nelims /**< pointer to store number of reduced edges */
2345  )
2346 {
2347  int* fixlist;
2348  const SCIP_Real* const redEdgeCost = redcosts_getEdgeCostsTop(redcostdata);
2349  const SCIP_Real cutoff = redcosts_getCutoffTop(redcostdata);
2350  int nfixes = 0;
2351  const int root = g->source;
2352 
2353  assert(graph_pc_isRootedPcMw(g));
2354  assert(!g->extended);
2355 
2356  SCIP_CALL( SCIPallocBufferArray(scip, &fixlist, g->terms) );
2357 
2358  for( int e = g->outbeg[root]; e != EAT_LAST; e = g->oeat[e] )
2359  {
2360  const int head = g->head[e];
2361 
2362  if( graph_pc_knotIsDummyTerm(g, head) )
2363  {
2364  if( GT(redEdgeCost[e], cutoff) )
2365  {
2366  assert(nfixes < g->terms);
2367 
2368  fixlist[nfixes++] = head;
2369  }
2370  }
2371  }
2372 
2373  for( int i = 0; i < nfixes; ++i )
2374  {
2375  const int pterm = fixlist[i];
2376  const int twin = graph_pc_getTwinTerm(g, pterm);
2377  assert(g->grad[pterm] == 2);
2378  assert(Is_term(g->term[twin]));
2379 
2380 #ifdef SCIP_DEBUG
2381  printf("dapath fixes: ");
2382  graph_knot_printInfo(g, twin);
2383 #endif
2384 
2385  graph_pc_knotToFixedTerm(scip, g, twin, offsetp);
2386  }
2387 
2388  *nelims += nfixes;
2389 
2390  SCIPfreeBufferArray(scip, &fixlist);
2391 
2392  return SCIP_OKAY;
2393 }
2394 
2395 
2396 /** dual ascent path based reductions */
2398  SCIP* scip, /**< SCIP data structure */
2399  GRAPH* g, /**< graph data structure */
2400  SCIP_Real* offsetp, /**< pointer to store offset */
2401  int* nelims /**< pointer to store number of reduced edges */
2402  )
2403 {
2404  REDCOST* redcostdata;
2405  const int nedges = graph_get_nEdges(g);
2406  int* RESTRICT result;
2407  SCIP_Real objbound_upper = FARAWAY;
2408  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(g);
2409  SCIP_Real dualobjval = -1.0;
2410  SCIP_Bool solFound;
2411 
2412  assert(scip && offsetp && nelims);
2413 
2414  *nelims = 0;
2415 
2416  if( g->terms <= 2 || !dapathsIsPromising(g) )
2417  return SCIP_OKAY;
2418 
2419  SCIP_CALL( SCIPallocBufferArray(scip, &result, nedges) );
2420 
2421  graph_mark(g);
2422  SCIP_CALL( redcosts_init(scip, g->knots, nedges, FARAWAY, g->source, &redcostdata) );
2423  SCIP_CALL( computeSteinerTreeTM(scip, g, result, &objbound_upper, &solFound) );
2424  SCIP_CALL( dualascent_paths(scip, g, redcosts_getEdgeCostsTop(redcostdata), &dualobjval, result) );
2425  redcosts_setDualBoundTop(dualobjval, redcostdata);
2426  SCIP_CALL( redcosts_initializeDistancesTop(scip, g, redcostdata) );
2427 
2428  assert(graph_isMarked(g));
2429 
2430  redcosts_setCutoffFromBoundTop(objbound_upper, redcostdata);
2431  SCIP_CALL( dapathsDeleteEdges(scip, redcostdata, result, g, nelims) );
2432 
2433  if( *nelims > 0 && solstp_isUnreduced(scip, g, result) )
2434  {
2435  if( isRpcmw )
2436  graph_pc_2trans(scip, g);
2437 
2438  SCIP_CALL( SCIPStpHeurLocalRun(scip, g, result) );
2439  objbound_upper = solstp_getObj(g, result, 0.0);
2440  redcosts_setCutoffFromBoundTop(objbound_upper, redcostdata);
2441 
2442  if( isRpcmw )
2443  graph_pc_2org(scip, g);
2444  else
2445  graph_mark(g);
2446 
2447  assert(graph_isMarked(g));
2448 
2449  SCIP_CALL( dapathsDeleteEdges(scip, redcostdata, result, g, nelims) );
2450  }
2451 
2452  SCIP_CALL( dapathsReplaceNodes(scip, redcostdata, result, objbound_upper, g, offsetp, nelims) );
2453 
2454  if( graph_pc_isRootedPcMw(g) )
2455  {
2456  SCIP_CALL( dapathsFixPotTerms(scip, redcostdata, g, offsetp, nelims) );
2457  }
2458 
2459  redcosts_free(scip, &redcostdata);
2460  SCIPfreeBufferArray(scip, &result);
2461 
2462  SCIP_CALL( reduce_unconnected(scip, g) );
2463 
2464  assert(!graph_pc_isPcMw(g) || !g->extended);
2465  assert(graph_valid(scip, g));
2466 
2467  return SCIP_OKAY;
2468 }
2469 
2470 /** dual ascent based reductions */
2472  SCIP* scip, /**< SCIP data structure */
2473  GRAPH* graph, /**< graph data structure */
2474  const RPDA* paramsda, /**< parameters */
2475  REDSOLLOCAL* redsollocal, /**< primal bound info or NULL */
2476  SCIP_Real* offsetp, /**< pointer to store offset */
2477  int* nelims, /**< pointer to store number of reduced edges */
2478  SCIP_RANDNUMGEN* randnumgen /**< random number generator */
2479 )
2480 {
2481  EXTPERMA* extpermanent = NULL;
2482  STPSOLPOOL* pool = NULL;
2483  SCIP_Real* edgefixingbounds = NULL;
2484  SCIP_Real* nodefixingbounds = NULL;
2485  SCIP_Real* nodereplacebounds = NULL;
2486  SCIP_Real upperbound;
2487  const SCIP_Bool isRpc = (graph->stp_type == STP_RPCSPG);
2488  const SCIP_Bool isRpcmw = graph_pc_isRootedPcMw(graph);
2489  const SCIP_Bool isDirected = graph_typeIsDirected(graph) || (graph->stp_type == STP_DCSTP);
2490  int* terms;
2491  int* result;
2492  int* bestresult;
2493  SCIP_Bool* pseudoDelNodes;
2494  int nFixedTerms;
2495  const int nedges = graph->edges;
2496  const int nnodes = graph->knots;
2497  STP_Bool* arcsdeleted;
2498  SCIP_Bool useExtRed = (paramsda->extredMode != extred_none);
2499  const SCIP_Bool nodereplacing = paramsda->nodereplacing;
2500  const SCIP_Bool userec = paramsda->useRec;
2501  SCIP_Bool havebestsol = FALSE;
2502  const SCIP_Bool useHops = (paramsda->damode == STP_DAMODE_HOPS); // todo do that properly
2503 
2504  assert(scip && graph && nelims);
2505  assert(graph_valid_ancestors(scip, graph) && graph_valid(scip, graph));
2506  assert(!isRpcmw || !graph->extended);
2507  assert(!(useExtRed && graph_pc_isMw(graph)));
2508 
2509  if( graph->terms <= 1 )
2510  return SCIP_OKAY;
2511 
2512 #ifdef STP_RPC_FIXEDPROPER
2513  assert(0 && "check");
2514  if( isRpcmw )
2515  return SCIP_OKAY;
2516 #endif
2517 
2518  SCIP_CALL( SCIPallocBufferArray(scip, &pseudoDelNodes, nnodes) );
2519  SCIP_CALL( SCIPallocBufferArray(scip, &result, nedges) );
2520  SCIP_CALL( SCIPallocBufferArray(scip, &bestresult, nedges) );
2521  SCIP_CALL( SCIPallocBufferArray(scip, &arcsdeleted, nedges) );
2522  SCIP_CALL( SCIPallocBufferArray(scip, &edgefixingbounds, nedges) );
2523  SCIP_CALL( SCIPallocBufferArray(scip, &nodefixingbounds, nnodes) );
2524  SCIP_CALL( SCIPallocBufferArray(scip, &nodereplacebounds, nnodes) );
2525  SCIP_CALL( SCIPallocBufferArray(scip, &terms, graph->terms) );
2526 
2527  if( userec )
2528  SCIP_CALL( solpool_init(scip, &pool, nedges, SOLPOOL_SIZE) );
2529 
2530  if( isRpc )
2531  reduce_identifyNonLeafTerms(scip, graph);
2532 
2533  if( isDirected )
2534  {
2535  for( int e = 0; e < nedges; e++ )
2536  arcsdeleted[e] = GE(graph->cost[e], FARAWAY);
2537  }
2538 
2539  upperbound = FARAWAY;
2540 
2541  if( redsollocal )
2542  {
2543  reduce_sollocalSetOffset(*offsetp, redsollocal);
2544  if( isRpcmw )
2545  SCIP_CALL( reduce_sollocalRebuildTry(scip, graph, redsollocal) );
2546 
2547  upperbound = reduce_sollocalGetUpperBound(redsollocal);
2548  }
2549 
2550  if( useHops )
2551  {
2552  assert(graph->stp_type == STP_DHCSTP);
2553  upperbound = (SCIP_Real) graph->hoplimit;
2554  }
2555 
2556  graph_mark(graph);
2557  collectFixedTerminals(graph, terms, &nFixedTerms);
2558 
2559  if( isRpcmw )
2560  graph_pc_2trans(scip, graph);
2561 
2562  /* select roots for dual ascent */
2563  SCIP_CALL( daOrderRoots(scip, graph, terms, nFixedTerms, TRUE, randnumgen) );
2564 
2565  {
2566  REDCOST* redcostdata;
2567  const int nruns = daGetNruns(graph, paramsda, nFixedTerms);
2568  SCIP_Real cutoffbound = -1.0;
2569  havebestsol = FALSE;
2570 
2571  SCIP_CALL( daRedcostsInit(scip, graph, paramsda, nruns, &redcostdata) );
2572 
2573  /* main reduction loop */
2574  for( int run = 0; run < nruns && graph->grad[graph->source] > 0; run++ )
2575  {
2576  int ndeletions_run = 0;
2577  const SCIP_Real damaxdeviation = daGetMaxDeviation(paramsda, randnumgen);
2578  SCIPdebugMessage("new DA root %d in round %d \n", terms[run], run);
2579 
2580  if( useExtRed && run > 0 )
2581  redcosts_addLevel(redcostdata);
2582 
2583  redcosts_setRootTop(terms[run], redcostdata);
2584 
2585  // if( rpc ) { // int todo; // check for more terminals to be added }
2586  if( !useHops && daGuidedIsPromising(graph, run, randnumgen) )
2587  {
2588  /* run dual-ascent (and possibly re-root solution stored in 'result') */
2589  SCIP_CALL( computeDualSolutionGuided(scip, graph, damaxdeviation, redcostdata, result) );
2590  }
2591  else
2592  {
2593  SCIP_CALL( computeDualSolution(scip, graph, damaxdeviation, redcostdata) );
2594  }
2595 
2596  if( isDirected )
2597  {
2598  if( !useHops )
2599  SCIP_CALL( computeSteinerTreeRedCostsDirected(scip, graph, redcostdata, result, bestresult, &havebestsol, &upperbound) );
2600  }
2601  else
2602  {
2603  if( useExtRed || run < 2 )
2604  {
2605  const SCIP_Bool useSlackPrune = (run == 1 && paramsda->useSlackPrune);
2606  SCIP_CALL( computeSteinerTreeRedCosts(scip, graph, redcostdata, useSlackPrune,
2607  userec, pool, result, bestresult, &havebestsol, &upperbound) );
2608  }
2609  else
2610  {
2611  havebestsol = havebestsol && solstp_isUnreduced(scip, graph, bestresult);
2612  }
2613  }
2614 
2615  // todo remove
2616  if( SCIPisFeasGT(scip, redcosts_getDualBoundTop(redcostdata), upperbound) )
2617  {
2618  printf("WRONG BOUND: upper=%f lower=%f (round=%d havenewsol=%d)\n", upperbound, redcosts_getDualBoundTop(redcostdata), run, havebestsol);
2619  return SCIP_ERROR;
2620  }
2621 
2622  SCIPdebugMessage("upper=%f lower=%f (round=%d havenewsol=%d)\n", upperbound, redcosts_getDualBoundTop(redcostdata), run, havebestsol);
2623 
2624  SCIP_CALL( daRoundInit(scip, upperbound, graph, redcostdata, arcsdeleted, &cutoffbound) );
2625 
2626  updateNodeFixingBounds(nodefixingbounds, graph, redcosts_getRootToNodeDistTop(redcostdata),
2627  redcosts_getNodeToTermsPathsTop(redcostdata), redcosts_getDualBoundTop(redcostdata), (run == 0));
2628  updateEdgeFixingBounds(edgefixingbounds, graph, redcosts_getEdgeCostsTop(redcostdata),
2630  nedges, (run == 0), TRUE);
2631 
2632  SCIP_CALL( reduceRootedProb(scip, graph, arcsdeleted, redcostdata, bestresult, havebestsol, &ndeletions_run) );
2633  ndeletions_run += reduceWithNodeFixingBounds(scip, graph, NULL, nodefixingbounds, upperbound);
2634  havebestsol = havebestsol && solstp_isUnreduced(scip, graph, bestresult);
2635  ndeletions_run += reduceWithEdgeFixingBounds(scip, graph, NULL, edgefixingbounds, (havebestsol ? bestresult : NULL), upperbound);
2636 
2637  if( useExtRed )
2638  redcosts_increaseOnDeletedArcsTop(graph, arcsdeleted, redcostdata);
2639 
2640  if( useExtRed && run == nruns - 1 )
2641  {
2642  const SCIP_Bool useSd = !graph_pc_isPc(graph);
2643  SCIP_CALL( extreduce_init(scip, useSd, paramsda->extredMode, graph, redcostdata, &extpermanent) );
2644  extreduce_extPermaAddRandnumgen(randnumgen, extpermanent);
2645  havebestsol = havebestsol && solstp_isUnreduced(scip, graph, bestresult);
2646 
2647  extpermanent->solIsValid = havebestsol;
2648  extpermanent->result = havebestsol ? bestresult : NULL;
2649 
2650  SCIP_CALL( reduceWithEdgeExtReds(scip, upperbound, extpermanent, graph, &ndeletions_run) );
2651  }
2652  else if( !isDirected && nodereplacing )
2653  {
2654  SCIP_CALL( updateNodeReplaceBounds(scip, redcostdata, graph, nodereplacebounds, upperbound, (run == 0), FALSE));
2655  }
2656 
2657  daRoundExit(scip, ndeletions_run, graph, nelims);
2658  } /* root loop */
2659 
2660  if( redsollocal )
2661  {
2662  reduce_sollocalSetOffset(*offsetp, redsollocal);
2663  reduce_sollocalUpdateUpperBound(upperbound, redsollocal);
2664 
2665  if( reduce_sollocalUsesNodesol(redsollocal) )
2666  {
2667  havebestsol = havebestsol && solstp_isUnreduced(scip, graph, bestresult);
2668  if( havebestsol )
2669  {
2670  SCIP_Bool isinfeas;
2671  SCIP_CALL(solstp_rerootInfeas(scip, graph, bestresult, graph->source, &isinfeas));
2672 
2673  if( !isinfeas )
2674  {
2675  SCIP_CALL( reduce_sollocalUpdateNodesol(scip, bestresult, graph, redsollocal) );
2676  }
2677  }
2678  }
2679  }
2680 
2681  /* do pseudo-elimination? */
2682  if( !isDirected && !SCIPisZero(scip, cutoffbound) && nodereplacing )
2683  {
2684  int nreplacings = 0;
2685  assert(!graph_pc_isMw(graph));
2686 
2687  markPseudoDeletablesFromBounds(scip, graph, nodereplacebounds, upperbound, pseudoDelNodes);
2688 
2689  if( useExtRed )
2690  {
2692  pseudoDelNodes, extpermanent, graph, offsetp, &nreplacings) );
2693  }
2694  else
2695  {
2696  SCIP_CALL( reduce_applyPseudoDeletions(scip, pseudoDelNodes, redcostdata, graph, offsetp, &nreplacings) );
2697  }
2698  *nelims += nreplacings;
2699 
2700  if( nreplacings > 0 && userec )
2701  {
2702  /* solutions in pool might not be valid anymore */
2703  solpool_free(scip, &pool);
2704  SCIP_CALL(solpool_init(scip, &pool, nedges, SOLPOOL_SIZE));
2705  }
2706 
2707  assert(graph_valid_ancestors(scip, graph));
2708  graph_mark(graph);
2709  }
2710 
2711  if( extpermanent )
2712  {
2713  extreduce_exit(scip, graph, &extpermanent);
2714  }
2715 
2716  daRedcostsExit(scip, &redcostdata);
2717  }
2718 
2719  if( isRpcmw )
2720  graph_pc_2orgcheck(scip, graph);
2721 
2722  if( userec )
2723  solpool_free(scip, &pool);
2724 
2725  SCIPfreeBufferArray(scip, &terms);
2726  SCIPfreeBufferArray(scip, &nodereplacebounds);
2727  SCIPfreeBufferArray(scip, &nodefixingbounds);
2728  SCIPfreeBufferArray(scip, &edgefixingbounds);
2729  SCIPfreeBufferArray(scip, &arcsdeleted);
2730  SCIPfreeBufferArray(scip, &bestresult);
2731  SCIPfreeBufferArray(scip, &result);
2732  SCIPfreeBufferArray(scip, &pseudoDelNodes);
2733 
2734  assert(graph_valid(scip, graph));
2735 
2736  return SCIP_OKAY;
2737 }
2738 
2739 
2740 /** dual ascent reduction for slack-and-prune heuristic */
2742  SCIP* scip, /**< SCIP data structure */
2743  GRAPH* graph, /**< graph data structure */
2744  int minelims, /**< minimum number of edges to eliminate */
2745  SCIP_Bool solgiven, /**< solution provided? */
2746  int* soledge, /**< solution edges (in/out) */
2747  int* solnode, /**< array of nodes of current solution that is not to be destroyed (in/out) */
2748  int* nelims, /**< pointer to store number of reduced edges */
2749  SCIP_Real* upperbound, /**< pointer to store new upper bound */
2750  SCIP_Bool* solImproved, /**< solution improved? */
2751  SCIP_Bool* solReconstructed /**< solution reconstructed? */
2752  )
2753 {
2754  PATH *vnoi;
2755  SCIP_Real *cost;
2756  SCIP_Real *costrev;
2757  SCIP_Real *pathdist;
2758  int *state;
2759  int *vbase;
2760  int *edgearrint2;
2761  int *pathprededge;
2762  SCIP_Real obj;
2763  SCIP_Real tmpcost;
2764  SCIP_Real lpobjval;
2765  SCIP_Real objprune;
2766  SCIP_Real minpathcost;
2767  SCIP_Bool success;
2768  SCIP_Bool eliminate;
2769  int k;
2770  int e;
2771  int etmp;
2772  int head;
2773  const int nedges = graph_get_nEdges(graph);
2774  const int nnodes = graph_get_nNodes(graph);
2775  const int root = graph->source;
2776  const int* grad = graph->grad;
2777  const SCIP_Bool rpcmw = graph_pc_isRootedPcMw(graph);
2778  SCIP_Bool solutionIsRebuilt = FALSE;
2779  int nfixed = 0;
2780  int redrounds;
2781  STP_Bool* marked;
2782 
2783  assert(scip && graph && nelims && solnode && soledge);
2784  assert(solReconstructed && solImproved);
2785  assert(!graph_pc_isPcMw(graph) || rpcmw);
2786 
2787  /* 1. step: initialize */
2788 
2789  *solReconstructed = FALSE;
2790  *solImproved = FALSE;
2791 
2792  if( graph->terms <= 2 )
2793  goto TERMINATE;
2794 
2795  SCIP_CALL( SCIPallocBufferArray(scip, &cost, nedges) );
2796  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, nedges) );
2797  SCIP_CALL( SCIPallocBufferArray(scip, &marked, nedges) );
2798  SCIP_CALL( SCIPallocBufferArray(scip, &state, 4 * nnodes) );
2799  SCIP_CALL( SCIPallocBufferArray(scip, &pathdist, nnodes) );
2800  SCIP_CALL( SCIPallocBufferArray(scip, &vbase, 4 * nnodes) );
2801  SCIP_CALL( SCIPallocBufferArray(scip, &pathprededge, nnodes) );
2802  SCIP_CALL( SCIPallocBufferArray(scip, &edgearrint2, nedges) );
2803  SCIP_CALL( SCIPallocBufferArray(scip, &vnoi, 4 * nnodes) );
2804 
2805  /* 2. step: - if not provided, compute lower bound and reduced costs
2806  * - try to eliminate edges and nodes */
2807 
2808  assert(!rpcmw || graph->extended);
2809 
2810  graph_mark(graph);
2811 
2812  if( !solgiven )
2813  {
2814  solutionIsRebuilt = TRUE;
2815 
2816  /* try to build MST on solnode nodes */
2817  for( int i = 0; i < nnodes; i++ )
2818  graph->mark[i] = (solnode[i] == CONNECT);
2819 
2820  assert(graph->mark[graph->source]);
2821 
2822  for( e = 0; e < nedges; e++ )
2823  soledge[e] = UNKNOWN;
2824 
2825  graph_path_exec(scip, graph, MST_MODE, root, graph->cost, vnoi);
2826 
2827  for( int i = 0; i < nnodes; i++ )
2828  {
2829  e = vnoi[i].edge;
2830  if( e >= 0 )
2831  {
2832  soledge[e] = CONNECT;
2833  }
2834  else if( Is_term(graph->term[i]) && i != root )
2835  {
2836  solutionIsRebuilt = FALSE;
2837  break;
2838  }
2839  }
2840 
2841  if( solutionIsRebuilt )
2842  {
2843  int count;
2844 
2845  do
2846  {
2847  count = 0;
2848 
2849  for( int i = nnodes - 1; i >= 0; --i )
2850  {
2851  if( (solnode[i] != CONNECT) || Is_term(graph->term[i]) )
2852  continue;
2853 
2854  for( e = graph->outbeg[i]; e != EAT_LAST; e = graph->oeat[e] )
2855  if( soledge[e] == CONNECT )
2856  break;
2857 
2858  if( e == EAT_LAST )
2859  {
2860  /* there has to be exactly one incoming edge */
2861  for( e = graph->inpbeg[i]; e != EAT_LAST; e = graph->ieat[e] )
2862  {
2863  if( soledge[e] == CONNECT )
2864  {
2865  soledge[e] = UNKNOWN;
2866  solnode[i] = UNKNOWN;
2867  count++;
2868  break;
2869  }
2870  }
2871  }
2872  }
2873  }
2874  while( count > 0 );
2875 
2876  solutionIsRebuilt = solstp_isValid(scip, graph, soledge);
2877  }
2878  }
2879 
2880  *solReconstructed = solutionIsRebuilt;
2881  SCIPdebugMessage("solutionIsRebuilt=%d \n", solutionIsRebuilt);
2882 
2883  if( solgiven || solutionIsRebuilt )
2884  {
2885  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = root,
2886  .is_pseudoroot = FALSE, .damaxdeviation = -1.0 };
2887  obj = getSolObj(scip, graph, soledge);
2888 
2889  SCIP_CALL( dualascent_exec(scip, graph, soledge, &daparams, cost, &lpobjval) );
2890  }
2891  else
2892  {
2893  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = root,
2894  .is_pseudoroot = FALSE, .damaxdeviation = -1.0 };
2895  obj = FARAWAY;
2896 
2897  SCIP_CALL( dualascent_exec(scip, graph, NULL, &daparams, cost, &lpobjval) );
2898  }
2899 
2900  assert(dualascent_allTermsReachable(scip, graph, root, cost));
2901 
2902  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, graph, cost, edgearrint2, root, &success, FALSE) );
2903  objprune = getSolObj(scip, graph, edgearrint2);
2904 
2905  assert(success);
2906 
2907  if( success && SCIPisLT(scip, objprune, obj ) )
2908  {
2909  *solImproved = TRUE;
2910 
2911  for( int i = 0; i < nnodes; i++ )
2912  solnode[i] = UNKNOWN;
2913 
2914  for( e = 0; e < nedges; e++ )
2915  {
2916  soledge[e] = edgearrint2[e];
2917  if( soledge[e] == CONNECT )
2918  {
2919  solnode[graph->tail[e]] = CONNECT;
2920  solnode[graph->head[e]] = CONNECT;
2921  }
2922  }
2923  }
2924 
2925  obj = getSolObj(scip, graph, soledge);
2926 
2927  for( e = 0; e < nedges; e++ )
2928  {
2929  marked[e] = FALSE;
2930  costrev[e] = cost[flipedge(e)];
2931  }
2932 
2933  *upperbound = obj;
2934  graph_mark(graph);
2935 
2936  /* distance from root to all nodes */
2937  graph_path_execX(scip, graph, root, cost, pathdist, pathprededge);
2938 
2939  /* no paths should go back to the root */
2940  for( e = graph->outbeg[root]; e != EAT_LAST; e = graph->oeat[e] )
2941  costrev[e] = FARAWAY;
2942 
2943  /* build Voronoi diagram */
2944  graph_get2nextTermPaths(graph, costrev, costrev, vnoi, vbase, state);
2945 
2946 #ifndef NDEBUG
2947  for( k = 0; k < nnodes; k++ )
2948  if( !Is_term(graph->term[k]) )
2949  assert(vbase[k + nnodes] != root );
2950 #endif
2951 
2952  /* RPC? If yes, restore original graph */
2953  if( rpcmw )
2954  {
2955  graph_pc_2org(scip, graph);
2956  graph->mark[root] = FALSE;
2957  }
2958 
2959  for( e = 0; e < nedges; e++ )
2960  costrev[e] = -1.0;
2961 
2962  for( redrounds = 0; redrounds < 3; redrounds++ )
2963  {
2964  if( redrounds == 0 )
2965  {
2966  eliminate = FALSE;
2967  minpathcost = FARAWAY;
2968  }
2969  else if( redrounds == 1 )
2970  {
2971  assert(minelims > 0);
2972  assert(2 * minelims < nedges);
2973 
2974  eliminate = TRUE;
2975  SCIPsortReal(costrev, nedges);
2976 
2977  /* the required reduced path cost to be surpassed */
2978  minpathcost = costrev[nedges - 2 * minelims];
2979 
2980  if( SCIPisLE(scip, minpathcost, 0.0) )
2981  minpathcost = 2 * SCIPepsilon(scip);
2982 
2983  k = nedges - 2 * minelims;
2984 
2985  /* try to first eliminate edges with higher gap */
2986  for( e = nedges - 1; e > k && e >= 2; e = e - 2 )
2987  {
2988  if( SCIPisLE(scip, costrev[e - 2], minpathcost) )
2989  break;
2990  }
2991 
2992  if( SCIPisGT(scip, costrev[e], minpathcost) )
2993  minpathcost = costrev[e];
2994 
2995  if( SCIPisLE(scip, minpathcost, 0.0) )
2996  minpathcost = 2 * SCIPepsilon(scip);
2997 
2998  for( e = 0; e < nedges; e++ )
2999  marked[e] = FALSE;
3000  }
3001  else
3002  {
3003  eliminate = TRUE;
3004 
3005  /* the required reduced path cost to be surpassed */
3006  minpathcost = costrev[nedges - 2 * minelims];
3007 
3008  if( SCIPisLE(scip, minpathcost, 0.0) )
3009  minpathcost = 2 * SCIPepsilon(scip);
3010 
3011  for( e = 0; e < nedges; e++ )
3012  marked[e] = FALSE;
3013  }
3014 
3015  for( k = 0; k < nnodes; k++ )
3016  {
3017  if( grad[k] <= 0 )
3018  continue;
3019 
3020  if( nfixed > minelims )
3021  break;
3022 
3023  if( rpcmw && !graph->mark[k] )
3024  {
3025  assert(graph_pc_knotIsDummyTerm(graph, k) || k == root);
3026  continue;
3027  }
3028 
3029  if( !Is_term(graph->term[k]) && (!eliminate || pathdist[k] + vnoi[k].dist >= minpathcost) && solnode[k] != CONNECT )
3030  {
3031  if( !eliminate )
3032  {
3033  tmpcost = pathdist[k] + vnoi[k].dist;
3034 
3035  for( e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
3036  {
3037  const int e2 = flipedge(e);
3038  if( SCIPisGT(scip, tmpcost, costrev[e]) )
3039  costrev[e] = tmpcost;
3040 
3041  if( SCIPisGT(scip, tmpcost, costrev[e2]) )
3042  costrev[e2] = tmpcost;
3043  }
3044 
3045  continue;
3046  }
3047  nfixed += grad[k];
3048 
3049  assert(!rpcmw || !graph_pc_knotIsDummyTerm(graph, k));
3050  graph_knot_del(scip, graph, k, TRUE);
3051  }
3052  else
3053  {
3054  e = graph->outbeg[k];
3055  while( e != EAT_LAST )
3056  {
3057  etmp = graph->oeat[e];
3058  head = graph->head[e];
3059 
3060  if( rpcmw && !graph->mark[head] )
3061  {
3062  assert(graph_pc_knotIsDummyTerm(graph, head) || head == root);
3063  e = etmp;
3064  continue;
3065  }
3066 
3067  if( (soledge[e] == CONNECT) || (soledge[flipedge(e)] == CONNECT) )
3068  {
3069  e = etmp;
3070  continue;
3071  }
3072 
3073  tmpcost = pathdist[k] + cost[e] + vnoi[head].dist;
3074 
3075  if( (!eliminate) || tmpcost >= minpathcost )
3076  {
3077  if( marked[flipedge(e)] )
3078  {
3079  if( eliminate )
3080  {
3081  graph_edge_del(scip, graph, e, TRUE);
3082  nfixed++;
3083  }
3084  else
3085  {
3086  if( SCIPisGT(scip, tmpcost, costrev[e]) )
3087  costrev[e] = tmpcost;
3088 
3089  if( SCIPisGT(scip, tmpcost, costrev[flipedge(e)]) )
3090  costrev[flipedge(e)] = tmpcost;
3091  }
3092  }
3093  else
3094  {
3095  marked[e] = TRUE;
3096  }
3097  }
3098  e = etmp;
3099  }
3100  }
3101  }
3102 
3103  for( k = 0; k < nnodes; k++ )
3104  {
3105  if( nfixed > minelims )
3106  break;
3107 
3108  if( !graph->mark[k] || Is_term(graph->term[k]) || solnode[k] == CONNECT )
3109  continue;
3110 
3111  if( grad[k] == 3 )
3112  {
3113  tmpcost = pathdist[k] + vnoi[k].dist + vnoi[k + nnodes].dist;
3114 
3115  if( !eliminate || tmpcost >= minpathcost )
3116  {
3117  int e2;
3118  int e3;
3119  e = graph->outbeg[k];
3120  assert(graph->oeat[e] != EAT_LAST);
3121  e2 = graph->oeat[e];
3122  assert(graph->oeat[e2] != EAT_LAST);
3123  e3 = graph->oeat[e2];
3124  assert(graph->oeat[e3] == EAT_LAST);
3125 
3126  if( SCIPisLE(scip, cost[e], 0.0) || SCIPisLE(scip, cost[e2], 0.0) || SCIPisLE(scip, cost[e3], 0.0) )
3127  continue;
3128 
3129  if( !eliminate )
3130  {
3131  for( e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
3132  {
3133  if( SCIPisGT(scip, tmpcost, costrev[e]) )
3134  costrev[e] = tmpcost;
3135 
3136  e2 = flipedge(e);
3137 
3138  if( SCIPisGT(scip, tmpcost, costrev[e2]) )
3139  costrev[e2] = tmpcost;
3140  }
3141 
3142  continue;
3143  }
3144  nfixed += 3;
3145  while( graph->outbeg[k] != EAT_LAST )
3146  graph_edge_del(scip, graph, graph->outbeg[k], TRUE);
3147  }
3148  }
3149  }
3150  }
3151  SCIPdebugMessage("deleted by da: %d \n", nfixed );
3152 
3153  if( rpcmw )
3154  graph_pc_2trans(scip, graph);
3155  assert(graph->mark[root]);
3156 
3157  TERMINATE:
3158  *nelims = nfixed;
3159  SCIPfreeBufferArray(scip, &vnoi);
3160  SCIPfreeBufferArray(scip, &edgearrint2);
3161  SCIPfreeBufferArray(scip, &pathprededge);
3162  SCIPfreeBufferArray(scip, &vbase);
3163  SCIPfreeBufferArray(scip, &pathdist);
3164  SCIPfreeBufferArray(scip, &state);
3165  SCIPfreeBufferArray(scip, &marked);
3166  SCIPfreeBufferArray(scip, &costrev);
3167  SCIPfreeBufferArray(scip, &cost);
3168 
3169  return SCIP_OKAY;
3170 }
3171 
3172 
3173 /** dual ascent based reductions for PCSPG and MWCSP */
3175  SCIP* scip, /**< SCIP data structure */
3176  GRAPH* graph, /**< graph data structure */
3177  const RPDA* paramsda, /**< parameters */
3178  REDSOLLOCAL* redprimal, /**< primal bound info or NULL */
3179  PATH* vnoi, /**< Voronoi data structure array */
3180  SCIP_Real* pathdist, /**< distance array for shortest path calculations */
3181  int* vbase, /**< Voronoi base array */
3182  int* pathedge, /**< shortest path incoming edge array for shortest path calculations */
3183  int* state, /**< int 4 * vertices array */
3184  STP_Bool* nodearrchar, /**< STP_Bool node array for internal computations */
3185  int* nelims, /**< pointer to store number of reduced edges */
3186  SCIP_RANDNUMGEN* randnumgen, /**< random number generator */
3187  SCIP_Real prizesum /**< sum of positive prizes */
3188 )
3189 {
3190  STPSOLPOOL* pool = NULL;
3191  GRAPH* transgraph = NULL;
3192  SCIP_Real* cost = NULL;
3193  SCIP_Real* costrev = NULL;
3194  SCIP_Real* bestcost = NULL;
3195  SCIP_Real* edgefixingbounds = NULL;
3196  SCIP_Real* nodefixingbounds = NULL;
3197  SCIP_Real offset;
3198  SCIP_Real lpobjval;
3199  SCIP_Real bestlpobjval;
3200  SCIP_Real upperbound;
3201  SCIP_Real minpathcost;
3202  int* roots = NULL;
3203  int* result = NULL;
3204  int* result2 = NULL;
3205  int* transresult = NULL;
3206  STP_Bool* marked = NULL;
3207  int nroots = 0;
3208  int nfixed = 0;
3209  int nusedroots;
3210  const int nnodes = graph_get_nNodes(graph);
3211  const int nedges = graph_get_nEdges(graph);
3212  const int extnedges = nedges + 2 * (graph->terms - 1);
3213  const int root = graph->source;
3214  SCIP_Bool havenewsol;
3215  SCIP_Bool userec = paramsda->useRec;
3216  const SCIP_Bool solbasedda = paramsda->pcmw_solbasedda;
3217  const SCIP_Bool useDifferentRoots = paramsda->pcmw_useMultRoots;
3218  const SCIP_Bool markroots = paramsda->pcmw_markroots;
3219  SCIP_Bool varyroot = useDifferentRoots && userec;
3220  const SCIP_Real damaxdeviation = paramsda->pcmw_fastDa ? DAMAXDEVIATION_FAST : -1.0;
3221  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = root,
3222  .is_pseudoroot = TRUE, .damaxdeviation = damaxdeviation };
3223 
3224  assert(scip && nelims && nodearrchar);
3225 
3226  if( graph->terms <= 3 )
3227  return SCIP_OKAY;
3228 
3229  SCIP_CALL( SCIPallocBufferArray(scip, &result, nedges) );
3230  SCIP_CALL( SCIPallocBufferArray(scip, &transresult, extnedges) );
3231  SCIP_CALL( SCIPallocBufferArray(scip, &marked, extnedges) );
3232  SCIP_CALL( SCIPallocBufferArray(scip, &result2, nedges) );
3233  SCIP_CALL( SCIPallocBufferArray(scip, &cost, extnedges) );
3234  SCIP_CALL( SCIPallocBufferArray(scip, &costrev, extnedges) );
3235  SCIP_CALL( SCIPallocBufferArray(scip, &bestcost, extnedges) );
3236  SCIP_CALL( SCIPallocBufferArray(scip, &edgefixingbounds, extnedges) );
3237  SCIP_CALL( SCIPallocBufferArray(scip, &nodefixingbounds, nnodes + 1) );
3238 
3239  if( userec )
3240  SCIP_CALL( solpool_init(scip, &pool, nedges, SOLPOOL_SIZE) );
3241 
3242  if( graph_pc_isPc(graph) )
3243  reduce_identifyNonLeafTerms(scip, graph);
3244 
3245  /*
3246  * 1. step: compute lower bound and reduced costs
3247  */
3248 
3249  graph_pc_2trans(scip, graph);
3250  offset = 0.0;
3251 
3252  /* transform the problem to a real SAP */
3253  SCIP_CALL( graph_transPcGetSap(scip, graph, &transgraph, &offset) );
3254 
3255  /* initialize data structures for shortest paths */
3256  SCIP_CALL( graph_path_init(scip, transgraph) );
3257 
3258  if( paramsda->pcmw_fastDa )
3259  {
3260  SCIP_CALL( dualascent_pathsPcMw(scip, transgraph, cost, &lpobjval, NULL) );
3261 
3262  // todo probably we might try to continue from the reduced cost we have already
3263  if( !dualascent_allTermsReachable(scip, graph, transgraph->source, cost) )
3264  SCIP_CALL( dualascent_exec(scip, transgraph, NULL, &daparams, cost, &lpobjval) );
3265  }
3266  else
3267  {
3268  SCIP_CALL( dualascent_exec(scip, transgraph, NULL, &daparams, cost, &lpobjval) );
3269  }
3270 
3271  lpobjval += offset;
3272  bestlpobjval = lpobjval;
3273  BMScopyMemoryArray(bestcost, cost, extnedges);
3274 
3275  /* compute first primal solution */
3276  upperbound = FARAWAY;
3277  havenewsol = FALSE;
3278 
3279  if( redprimal )
3280  {
3281  upperbound = reduce_sollocalGetUpperBound(redprimal);
3282  }
3283 
3284  SCIP_CALL( computeSteinerTreeRedCostsPcMw(scip, graph, NULL, cost, &upperbound, result, result2, pathedge, nodearrchar, &havenewsol) );
3285 
3286  assert(LT(upperbound, FARAWAY));
3287 
3288  /* the required reduced path cost to be surpassed */
3289  minpathcost = upperbound - lpobjval;
3290 
3291  assert(GE(minpathcost, 0.0));
3292  SCIPdebugMessage("havenewsol=%d upperbound=%f lpobjval=%f \n", havenewsol, upperbound, lpobjval);
3293 
3294  if( userec)
3295  SCIPdebugMessage("DA first minpathcost %f \n", minpathcost);
3296 
3297  /* initialize data structures for transgraph */
3298  // SCIP_CALL( graph_initHistory(scip, transgraph) );
3299  computeTransVoronoi(scip, transgraph, vnoi, cost, costrev, pathdist, vbase, pathedge);
3300 
3301  /*
3302  * 2. step: try to eliminate
3303  */
3304 
3305  /* restore original graph */
3306  graph_pc_2org(scip, graph);
3307 
3308  for( int e = 0; e < extnedges; e++ )
3309  marked[e] = FALSE;
3310 
3311  /* try to reduce the graph */
3312  assert(daRedCostIsValid(scip, transgraph, cost, state, nodearrchar));
3313 
3314  updateEdgeFixingBounds(edgefixingbounds, graph, cost, pathdist, vnoi, lpobjval, extnedges, TRUE, FALSE);
3315  updateNodeFixingBounds(nodefixingbounds, graph, pathdist, vnoi, lpobjval, TRUE);
3316 
3317  {
3318  const SCIP_Bool deleteTransEdges = (solbasedda || varyroot || markroots);
3319  nfixed += reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar,
3320  havenewsol, deleteTransEdges);
3321  }
3322 
3323  /* edges from result might have been deleted! */
3324  havenewsol = havenewsol && solstp_isUnreduced(scip, graph, result);
3325  assert(!havenewsol || solstp_isValid(scip, graph, result));
3326 
3327  if( userec )
3328  SCIPdebugMessage("DA: 1. NFIXED %d \n", nfixed);
3329 
3330  /* rerun dual ascent? */
3331  if( solbasedda && graph->terms > 2 && SCIPisGT(scip, minpathcost, 0.0) )
3332  {
3333  const SCIP_Real oldupperbound = upperbound;
3334 
3335  /* with recombination? */
3336  if( userec && graph->stp_type != STP_MWCSP )
3337  {
3338  // todo is that really useful?
3339  SCIP_CALL( daPcAddTmSolToPool(scip, graph, result2, pool) );
3340  }
3341 
3342  /* try to improve both dual and primal bound */
3343  SCIP_CALL( computePertubedSol(scip, graph, transgraph, pool, vnoi, cost, bestcost, pathdist, pathedge, result, result2,
3344  transresult, nodearrchar, &upperbound, &lpobjval, &bestlpobjval, &minpathcost, &havenewsol, offset, extnedges) );
3345 
3346  assert(solstp_isValid(scip, graph, result));
3347  assert(!havenewsol || SCIPisEQ(scip, getSolObj(scip, graph, result), upperbound));
3348 
3349  graph_pc_2orgcheck(scip, graph);
3350 
3351  assert(daRedCostIsValid(scip, transgraph, cost, state, nodearrchar));
3352  computeTransVoronoi(scip, transgraph, vnoi, cost, costrev, pathdist, vbase, pathedge);
3353  updateEdgeFixingBounds(edgefixingbounds, graph, cost, pathdist, vnoi, lpobjval, extnedges, FALSE, FALSE);
3354  updateNodeFixingBounds(nodefixingbounds, graph, pathdist, vnoi, lpobjval, FALSE);
3355 
3356  nfixed += reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar, havenewsol, TRUE);
3357 
3358  nfixed += reducePcMwTryBest(scip, graph, transgraph, vnoi, cost, costrev, bestcost, pathdist, &upperbound,
3359  &lpobjval, &bestlpobjval, &minpathcost, oldupperbound, result, vbase, state, pathedge, marked, nodearrchar, &havenewsol, extnedges);
3360 
3361  nfixed += reduceWithEdgeFixingBounds(scip, graph, transgraph, edgefixingbounds, NULL, upperbound);
3362  nfixed += reduceWithNodeFixingBounds(scip, graph, transgraph, nodefixingbounds, upperbound);
3363 
3364  if( userec )
3365  SCIPdebugMessage("eliminations after sol based run2 with best dual sol %d bestlb %f newlb %f\n", nfixed, bestlpobjval, lpobjval);
3366  }
3367 
3368 
3369  if( reduce_sollocalUsesNodesol(redprimal) )
3370  {
3371  havenewsol = havenewsol && solstp_isUnreduced(scip, graph, result);
3372  if( havenewsol )
3373  {
3374  graph_pc_2trans(scip, graph);
3375  SCIP_CALL( reduce_sollocalUpdateNodesol(scip, result, graph, redprimal) );
3376  graph_pc_2org(scip, graph);
3377  }
3378  }
3379 
3380  if( graph->stp_type == STP_MWCSP && graph->terms < STP_RED_MINBNDTERMS )
3381  varyroot = FALSE;
3382 
3383  /* change or mark roots? */
3384  if( varyroot || markroots )
3385  {
3386  SCIP_CALL( SCIPallocBufferArray(scip, &roots, graph->terms) );
3387 
3388  SCIP_CALL( daPcFindRoots(scip, graph, transgraph, cost, bestcost, lpobjval, bestlpobjval, upperbound, FALSE, FALSE,
3389  vnoi, pathedge, vbase, nodearrchar, roots, &nroots));
3390 
3391  /* should prize of terminals be changed? */
3392  if( nroots > 0 && markroots )
3393  daPcMarkRoots(scip, roots, 0, nroots, prizesum, graph, &userec, &pool);
3394 
3395  if( nroots > 0 && varyroot )
3396  SCIP_CALL( daOrderRoots(scip, graph, roots, nroots, TRUE, randnumgen) );
3397  }
3398 
3399  if( varyroot )
3400  nusedroots = MIN(DEFAULT_NMAXROOTS, nroots);
3401  else
3402  nusedroots = -1;
3403 
3404  graph_path_exit(scip, transgraph);
3405  graph_free(scip, &transgraph, TRUE);
3406 
3407  /* loop and change root for dual ascent run */
3408  for( int run = 0; run < nusedroots; run++ )
3409  {
3410  const int tmproot = roots[run];
3411  int transnnodes;
3412  int transnedges;
3413 
3414  assert(nroots > 0);
3415  assert(roots != NULL);
3416  assert(Is_term(graph->term[tmproot]));
3417 
3418  if( graph->terms <= 2 )
3419  break;
3420 
3421  assert(!graph_pc_knotIsNonLeafTerm(graph, tmproot));
3422 
3423  SCIP_CALL( graph_transPcGetRsap(scip, graph, &transgraph, roots, nroots, tmproot) );
3424 
3425  assert(graph_valid(scip, transgraph) && STP_SAP == transgraph->stp_type);
3426 
3427  transnnodes = transgraph->knots;
3428  transnedges = transgraph->edges;
3429 
3430  graph_mark(transgraph);
3431 
3432  /* init data structures for shortest paths and history */
3433  SCIP_CALL( graph_path_init(scip, transgraph) );
3434 
3435  if( havenewsol && run > 1 )
3436  {
3437  BMScopyMemoryArray(transresult, result, graph->edges);
3438  SCIP_CALL(solstp_reroot(scip, transgraph, transresult, tmproot));
3439  daparams.root = tmproot;
3440  daparams.is_pseudoroot = FALSE;
3441  daparams.damaxdeviation = -1.0;
3442 
3443  SCIP_CALL( dualascent_exec(scip, transgraph, transresult, &daparams, cost, &lpobjval) );
3444  }
3445  else
3446  {
3447  daparams.root = tmproot;
3448  daparams.is_pseudoroot = FALSE;
3449  daparams.damaxdeviation = -1.0;
3450 
3451  SCIP_CALL( dualascent_exec(scip, transgraph, NULL, &daparams, cost, &lpobjval) );
3452  }
3453 
3454  assert(graph_valid(scip, transgraph));
3455 
3456  for( int e = graph->outbeg[tmproot]; e != EAT_LAST; e = graph->oeat[e] )
3457  {
3458  const int k = graph->head[e];
3459  if( Is_term(graph->term[k]) )
3460  {
3461  if( k == root )
3462  cost[flipedge(e)] = 0.0;
3463  else
3464  cost[e] = 0.0;
3465  }
3466  }
3467 
3468  for( int k = 0; k < nnodes; k++ )
3469  {
3470  if( Is_pseudoTerm(graph->term[k]) && SCIPisGE(scip, graph->prize[k], prizesum) )
3471  {
3472  for( int e = graph->outbeg[k]; e != EAT_LAST; e = graph->oeat[e] )
3473  {
3474  const int head = graph->head[e];
3475  if( Is_term(graph->term[head]) && head != root )
3476  cost[e] = 0.0;
3477  }
3478  }
3479  }
3480 
3481  havenewsol = FALSE;
3482  SCIP_CALL( computeSteinerTreeRedCostsPcMw(scip, graph, pool, cost, &upperbound, result, result2, pathedge, nodearrchar, &havenewsol) );
3483 
3484  SCIPdebugMessage("ROOTRUNS upperbound %f \n", upperbound);
3485  if( pool )
3486  SCIPdebugMessage("ROOTRUNS best sol in pool %f \n", pool->sols[0]->obj);
3487 
3488  for( int k = 0; k < transnnodes; k++ )
3489  transgraph->mark[k] = (transgraph->grad[k] > 0);
3490 
3491  /* the required reduced path cost to be surpassed */
3492  minpathcost = upperbound - lpobjval;
3493 
3494  if( markroots )
3495  {
3496  const int oldnroots = nroots;
3497  SCIP_CALL( daPcFindRoots(scip, graph, transgraph, cost, cost, lpobjval, lpobjval, upperbound, TRUE, TRUE,
3498  vnoi, pathedge, vbase, nodearrchar, roots, &nroots) );
3499 
3500  /* should prize of terminals be changed? */
3501  if( nroots > oldnroots )
3502  daPcMarkRoots(scip, roots, oldnroots, nroots, prizesum, graph, &userec, &pool);
3503  }
3504 
3505  SCIPdebugMessage("ROOTRUNS: minpathcost %f \n", minpathcost);
3506  SCIPdebugMessage("lb: %f ub: %f \n", lpobjval, upperbound);
3507 
3508  /* distance from root to all nodes */
3509  graph_path_execX(scip, transgraph, tmproot, cost, pathdist, pathedge);
3510 
3511  for( int e = 0; e < transnedges; e++ )
3512  costrev[e] = cost[flipedge(e)];
3513 
3514  /* no paths should go back to the root */
3515  for( int e = transgraph->outbeg[tmproot]; e != EAT_LAST; e = transgraph->oeat[e] )
3516  costrev[e] = FARAWAY;
3517 
3518  /* build Voronoi diagram */
3519  graph_add1stTermPaths(transgraph, costrev, vnoi, vbase, state);
3520  graph_add2ndTermPaths(transgraph, costrev, costrev, vnoi, vbase, state);
3521 
3522  /* restore original graph */
3523  graph_pc_2org(scip, graph);
3524 
3525  assert(graph->mark[tmproot]);
3526  graph->mark[tmproot] = FALSE;
3527 
3528  /* at first run switch to undirected case */
3529  if( run == 0 )
3530  for( int e = 0; e < extnedges; e++ )
3531  edgefixingbounds[e] = MIN(edgefixingbounds[e], edgefixingbounds[flipedge(e)]);
3532 
3533  updateEdgeFixingBounds(edgefixingbounds, graph, cost, pathdist, vnoi, lpobjval, extnedges, FALSE, TRUE);
3534  updateNodeFixingBounds(nodefixingbounds, graph, pathdist, vnoi, lpobjval, FALSE);
3535 
3536  for( int e = 0; e < transnedges; e++ )
3537  marked[e] = FALSE;
3538 
3539  /* try to eliminate vertices and edges */
3540  nfixed += reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar, havenewsol, TRUE);
3541  nfixed += reduceWithEdgeFixingBounds(scip, graph, transgraph, edgefixingbounds, NULL, upperbound);
3542  nfixed += reduceWithNodeFixingBounds(scip, graph, transgraph, nodefixingbounds, upperbound);
3543 
3544  havenewsol = havenewsol && solstp_isUnreduced(scip, graph, result);
3545  assert(!havenewsol || solstp_isValid(scip, graph, result));
3546  SCIPdebugMessage("FIXED with changed root %d \n\n", nfixed);
3547 
3548  graph->mark[tmproot] = TRUE;
3549 
3550  transgraph->stp_type = STP_RPCSPG;
3551  graph_path_exit(scip, transgraph);
3552  graph_free(scip, &transgraph, TRUE);
3553  }
3554 
3555  *nelims = nfixed;
3556 
3557  if( pool != NULL )
3558  solpool_free(scip, &pool);
3559 
3560  SCIPfreeBufferArrayNull(scip, &roots);
3561  SCIPfreeBufferArray(scip, &nodefixingbounds);
3562  SCIPfreeBufferArray(scip, &edgefixingbounds);
3563  SCIPfreeBufferArray(scip, &bestcost);
3564  SCIPfreeBufferArray(scip, &costrev);
3565  SCIPfreeBufferArray(scip, &cost);
3566  SCIPfreeBufferArray(scip, &result2);
3567  SCIPfreeBufferArray(scip, &marked);
3568  SCIPfreeBufferArray(scip, &transresult);
3569  SCIPfreeBufferArray(scip, &result);
3570 
3571  if( redprimal )
3572  {
3573  reduce_sollocalUpdateUpperBound(upperbound, redprimal);
3574  }
3575 
3576  assert(graph_valid(scip, graph));
3577 
3578  return SCIP_OKAY;
3579 }
#define DARUNS_TERMRATIO_HUGE
Definition: reduce_da.c:57
SCIP_RETCODE reduce_daPcMw(SCIP *scip, GRAPH *graph, const RPDA *paramsda, REDSOLLOCAL *redprimal, PATH *vnoi, SCIP_Real *pathdist, int *vbase, int *pathedge, int *state, STP_Bool *nodearrchar, int *nelims, SCIP_RANDNUMGEN *randnumgen, SCIP_Real prizesum)
Definition: reduce_da.c:3174
#define STP_Vectype(type)
Definition: stpvector.h:44
#define DAMAXDEVIATION_FAST
Definition: reduce_da.c:63
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
#define BND_TMHEUR_NRUNS_RPC
Definition: reduce_da.c:48
SCIP_Bool graph_valid_ancestors(SCIP *, const GRAPH *)
static volatile int nterms
Definition: interrupt.c:38
#define StpVecGetSize(vec)
Definition: stpvector.h:139
SCIP_Bool graph_pc_isMw(const GRAPH *)
void redcosts_setAndReturnCutoffFromBoundTop(SCIP_Real upperbound, REDCOST *redcostdata, SCIP_Real *cutoffbound)
Definition: redcosts.c:624
void extreduce_exit(SCIP *, GRAPH *, EXTPERMA **)
int *RESTRICT head
Definition: graphdefs.h:224
void graph_edge_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_edge.c:368
SCIP_Bool graph_sdWalksConnected(SCIP *, const GRAPH *, const int *, const SCIP_Real *, const STP_Bool *, int, int, SCIP_Real *, int *, int *, STP_Bool *, SCIP_Bool)
SCIP_Bool graph_typeIsDirected(const GRAPH *)
Definition: graph_stats.c:83
static SCIP_RETCODE daRoundInit(SCIP *scip, SCIP_Real upperbound, GRAPH *graph, REDCOST *redcostdata, STP_Bool *arcsdeleted, SCIP_Real *cutoffbound)
Definition: reduce_da.c:1740
int source
Definition: graphdefs.h:195
static void updateNodeFixingBounds(SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjval, SCIP_Bool initialize)
Definition: reduce_da.c:575
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool graph_pc_isRootedPcMw(const GRAPH *)
SCIP_RETCODE dualascent_execDegCons(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1256
static void daRpcmwDeleteTermIncidents(SCIP *scip, const PATH *vnoi, int term, GRAPH *graph, int *incidents, int *nfixedp)
Definition: reduce_da.c:1187
#define Is_term(a)
Definition: graphdefs.h:102
static void computeTransVoronoi(SCIP *scip, GRAPH *transgraph, PATH *vnoi, const SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *vbase, int *pathedge)
Definition: reduce_da.c:1915
signed int edge
Definition: graphdefs.h:287
SCIP_RETCODE reduce_daSlackPrune(SCIP *scip, GRAPH *graph, int minelims, SCIP_Bool solgiven, int *soledge, int *solnode, int *nelims, SCIP_Real *upperbound, SCIP_Bool *solImproved, SCIP_Bool *solReconstructed)
Definition: reduce_da.c:2741
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
void reduce_identifyNonLeafTerms(SCIP *, GRAPH *)
int redcosts_getNlevels(const REDCOST *redcostdata)
Definition: redcosts.c:369
#define DEFAULT_DARUNS_DIRECTED
Definition: reduce_da.c:49
int terms
Definition: graphdefs.h:192
static SCIP_Bool daGuidedIsPromising(const GRAPH *graph, int run, SCIP_RANDNUMGEN *randnumgen)
Definition: reduce_da.c:1567
void graph_pc_termMarkProper(const GRAPH *, int *)
static int reducePcMwTryBest(SCIP *scip, GRAPH *graph, GRAPH *transgraph, PATH *vnoi, const SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *bestcost, SCIP_Real *pathdist, SCIP_Real *upperbound, SCIP_Real *lpobjval, SCIP_Real *bestlpobjval, SCIP_Real *minpathcost, SCIP_Real oldupperbound, const int *result, int *vbase, int *state, int *pathedge, STP_Bool *marked, STP_Bool *nodearrchar, SCIP_Bool *solgiven, int extnedges)
Definition: reduce_da.c:2212
SCIP_Real redcosts_getCutoffTop(const REDCOST *redcostdata)
Definition: redcosts.c:300
static SCIP_RETCODE reduceWithEdgeExtReds(SCIP *scip, SCIP_Real upperbound, EXTPERMA *extperma, GRAPH *graph, int *ndeletions_run)
Definition: reduce_da.c:979
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
void reduce_sollocalSetOffset(SCIP_Real, REDSOLLOCAL *)
Definition: reduce_sol.c:488
STPSOL * solpool_solFromIndex(STPSOLPOOL *pool, const int soindex)
Definition: solpool.c:66
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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_Real damaxdeviation
Definition: dualascent.h:45
SCIP_RETCODE SCIPStpHeurLocalRunFast(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3911
static SCIP_RETCODE daPcFindRoots(SCIP *scip, GRAPH *graph, const GRAPH *transgraph, const SCIP_Real *cost, const SCIP_Real *bestcost, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real upperbound, SCIP_Bool rerun, SCIP_Bool probrooted, PATH *vnoi, int *pathedge, int *vbase, STP_Bool *isfixedterm, int *roots, int *rootscount)
Definition: reduce_da.c:1229
void redcosts_addLevel(REDCOST *redcostdata)
Definition: redcosts.c:460
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
dual-ascent and reduction based primal heuristic for Steiner problems
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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 EAT_FREE
Definition: graphdefs.h:57
SCIP_RETCODE reduce_da(SCIP *scip, GRAPH *graph, const RPDA *paramsda, REDSOLLOCAL *redsollocal, SCIP_Real *offsetp, int *nelims, SCIP_RANDNUMGEN *randnumgen)
Definition: reduce_da.c:2471
#define FALSE
Definition: def.h:87
Includes dual-ascent for classic Steiner tree and some variants.
int *RESTRICT inpbeg
Definition: graphdefs.h:202
int *RESTRICT path_state
Definition: graphdefs.h:256
#define DEFAULT_NMAXROOTS
Definition: reduce_da.c:52
SCIP_Bool solstp_isUnreduced(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1596
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
#define STP_SAP
Definition: graphdefs.h:43
#define STP_DCSTP
Definition: graphdefs.h:47
SCIP_RETCODE solpool_init(SCIP *scip, STPSOLPOOL **pool, const int nedges, const int maxsize)
Definition: solpool.c:91
void redcosts_free(SCIP *scip, REDCOST **redcostdata)
Definition: redcosts.c:743
SCIP_RETCODE graph_transPcGetSap(SCIP *, GRAPH *, GRAPH **, SCIP_Real *)
Definition: graph_trans.c:931
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
#define BND_TMHEUR_NRUNS_RESTRICT
Definition: reduce_da.c:47
#define EAT_LAST
Definition: graphdefs.h:58
#define STP_SPG
Definition: graphdefs.h:42
#define SCIPdebugMessage
Definition: pub_message.h:87
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10003
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
#define BND_TMHEUR_NRUNS
Definition: reduce_da.c:46
static SCIP_Real daGetMaxDeviation(const RPDA *paramsda, SCIP_RANDNUMGEN *randnumgen)
Definition: reduce_da.c:1543
static SCIP_RETCODE computePertubedSol(SCIP *scip, GRAPH *graph, GRAPH *transgraph, STPSOLPOOL *pool, PATH *vnoi, SCIP_Real *cost, SCIP_Real *bestcost, SCIP_Real *pathdist, int *pathedge, int *result, int *result2, int *transresult, STP_Bool *nodearrchar, SCIP_Real *upperbound, SCIP_Real *lpobjval, SCIP_Real *bestlpobjval, SCIP_Real *minpathcost, SCIP_Bool *apsol, SCIP_Real offset, int extnedges)
Definition: reduce_da.c:1810
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE redcosts_initializeDistancesTop(SCIP *scip, GRAPH *g, REDCOST *redcostdata)
Definition: redcosts.c:573
SCIP_RETCODE reduce_sollocalRebuildTry(SCIP *, GRAPH *, REDSOLLOCAL *)
Definition: reduce_sol.c:507
#define DEFAULT_DARUNS
Definition: reduce_da.c:50
SCIP_Real SCIPepsilon(SCIP *scip)
void graph_get2nextTermPaths(GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1542
SCIP_RETCODE dualascent_exec(SCIP *scip, const GRAPH *g, const int *result, const DAPARAMS *daparams, SCIP_Real *RESTRICT redcost, SCIP_Real *objval)
Definition: dualascent.c:1191
static void markPseudoDeletablesFromBounds(SCIP *scip, GRAPH *graph, const SCIP_Real *replacebounds, SCIP_Real upperbound, SCIP_Bool *pseudoDelNodes)
Definition: reduce_da.c:1029
int *RESTRICT mark
Definition: graphdefs.h:198
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
int redcosts_getRootTop(const REDCOST *redcostdata)
Definition: redcosts.c:347
SCIP_RETCODE reduce_sollocalUpdateNodesol(SCIP *, const int *, GRAPH *, REDSOLLOCAL *)
Definition: reduce_sol.c:565
static void findRootsMark(SCIP *scip, GRAPH *graph, const GRAPH *transgraph, const int *termmark, const SCIP_Real *cost, const SCIP_Real *bestcost, SCIP_Real lpobjval, SCIP_Real bestlpobjval, SCIP_Real upperbound, SCIP_Bool rerun, SCIP_Bool probrooted, int pseudoterm, int pseudoedge, STP_Bool *isfixedterm, int *roots, int *rootscount, int *pathedge, STP_Bool *visited, SCIP_Real *dist)
Definition: reduce_da.c:1068
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1066
SCIP_RETCODE solstp_rerootInfeas(SCIP *scip, GRAPH *g, int *result, int newroot, SCIP_Bool *isInfeasible)
Definition: solstp.c:1579
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
void solpool_free(SCIP *scip, STPSOLPOOL **pool)
Definition: solpool.c:122
STPSOL ** sols
Definition: solpool.h:48
#define STP_RSMT
Definition: graphdefs.h:49
int *RESTRICT oeat
Definition: graphdefs.h:231
SCIP_RETCODE dualascent_paths(SCIP *scip, GRAPH *graph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval, const int *result)
Definition: dualascent.c:1803
This file implements extended reduction techniques for several Steiner problems.
static int reducePcMw(SCIP *scip, GRAPH *graph, GRAPH *transgraph, const PATH *vnoi, const SCIP_Real *cost, const SCIP_Real *pathdist, SCIP_Real minpathcost, const int *result, STP_Bool *marked, STP_Bool *nodearrchar, SCIP_Bool solgiven, SCIP_Bool deleteTransEdges)
Definition: reduce_da.c:2071
SCIP_Real redcosts_getDualBoundTop(const REDCOST *redcostdata)
Definition: redcosts.c:324
int graph_pc_getRoot2PtermEdge(const GRAPH *, int)
#define GE(a, b)
Definition: portab.h:85
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
static SCIP_RETCODE reduceRootedProb(SCIP *scip, GRAPH *graph, STP_Bool *marked, const REDCOST *redcostdata, const int *result, SCIP_Bool solgiven, int *nfixedp)
Definition: reduce_da.c:1954
void graph_pc_2trans(SCIP *, GRAPH *)
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
void redcosts_setCutoffFromBoundTop(SCIP_Real upperbound, REDCOST *redcostdata)
Definition: redcosts.c:670
SCIP_RETCODE SCIPStpHeurAscendPruneRun(SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *result, int root, SCIP_Bool *solfound, SCIP_Bool addsol)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
SCIP_RETCODE solpool_addSol(SCIP *scip, const SCIP_Real obj, const int *soledges, STPSOLPOOL *pool, SCIP_Bool *success)
Definition: solpool.c:183
#define DAMAXDEVIATION_RANDOM_LOWER
Definition: reduce_da.c:61
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void graph_pc_2transcheck(SCIP *, GRAPH *)
SCIP_Real * redcosts_getEdgeCostsTop(const REDCOST *redcostdata)
Definition: redcosts.c:202
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
SCIP_Bool is_pseudoroot
Definition: dualascent.h:44
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:128
SCIP_Real * prize
Definition: graphdefs.h:210
void SCIPsortReal(SCIP_Real *realarray, int len)
SCIP_Real dist
Definition: graphdefs.h:286
int *RESTRICT grad
Definition: graphdefs.h:201
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
static SCIP_RETCODE daRedcostsInit(SCIP *scip, const GRAPH *graph, const RPDA *paramsda, int nLevels, REDCOST **redcostdata)
Definition: reduce_da.c:1650
#define DARUNS_TERMRATIO_LOW
Definition: reduce_da.c:54
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
SCIP_RETCODE reduce_applyPseudoDeletions(SCIP *, const SCIP_Bool *, REDCOST *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_util.c:1042
SCIP_RETCODE SCIPStpHeurRecExclude(SCIP *scip, const GRAPH *graph, const int *result, int *newresult, int *dnodemap, STP_Bool *stvertex, SCIP_Bool *success)
Definition: heur_rec.c:1649
#define EQ(a, b)
Definition: portab.h:79
void graph_knot_del(SCIP *, GRAPH *, int, SCIP_Bool)
Definition: graph_node.c:111
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_RETCODE daPcAddTmSolToPool(SCIP *scip, GRAPH *graph, int *result, STPSOLPOOL *pool)
Definition: reduce_da.c:1404
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int * term2edge
Definition: graphdefs.h:208
#define MST_MODE
Definition: graphdefs.h:98
static void daRedcostsExit(SCIP *scip, REDCOST **redcostdata)
Definition: reduce_da.c:1676
SCIP_Real redcosts_getCutoff(const REDCOST *redcostdata, int level)
Definition: redcosts.c:288
#define STP_PCSPG
Definition: graphdefs.h:44
static SCIP_RETCODE computeSteinerTreeRedCostsPcMw(SCIP *scip, GRAPH *graph, STPSOLPOOL *pool, const SCIP_Real *cost, SCIP_Real *upperbound, int *result1, int *result2, int *pathedge, STP_Bool *nodearrchar, SCIP_Bool *apsol)
Definition: reduce_da.c:427
#define LT(a, b)
Definition: portab.h:81
SCIP_Real graph_pc_solGetObj(SCIP *, const GRAPH *, const int *, SCIP_Real)
static SCIP_RETCODE computeDualSolution(SCIP *scip, GRAPH *graph, SCIP_Real damaxdeviation, REDCOST *redcostdata)
Definition: reduce_da.c:152
#define SOLPOOL_SIZE
Definition: reduce_da.c:53
Improvement heuristic for Steiner problems.
SCIP_Bool dualascent_allTermsReachable(SCIP *scip, const GRAPH *g, int root, const SCIP_Real *redcost)
Definition: dualascent.c:1835
includes solution pool for Steiner tree problems
unsigned char STP_Bool
Definition: portab.h:34
#define STP_DAMODE_FAST
Definition: reducedefs.h:44
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
#define STP_RED_MINBNDTERMS
Definition: reduce_da.c:58
#define STP_DAMODE_HOPS
Definition: reducedefs.h:43
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static int daGetNruns(const GRAPH *graph, const RPDA *paramsda, int nterms)
Definition: reduce_da.c:1687
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
int *RESTRICT path_heap
Definition: graphdefs.h:255
SCIP_Real obj
Definition: solpool.h:40
static SCIP_RETCODE dapathsFixPotTerms(SCIP *scip, const REDCOST *redcostdata, GRAPH *g, SCIP_Real *offsetp, int *nelims)
Definition: reduce_da.c:2339
static void daRoundExit(SCIP *scip, int ndeletions_run, GRAPH *graph, int *nelims)
Definition: reduce_da.c:1776
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
void reduce_sollocalUpdateUpperBound(SCIP_Real, REDSOLLOCAL *)
Definition: reduce_sol.c:610
int *RESTRICT tail
Definition: graphdefs.h:223
PATH * redcosts_getNodeToTermsPathsTop(const REDCOST *redcostdata)
Definition: redcosts.c:253
static SCIP_RETCODE computeDualSolutionGuided(SCIP *scip, GRAPH *graph, SCIP_Real damaxdeviation, REDCOST *redcostdata, int *result)
Definition: reduce_da.c:86
SCIP_RETCODE redcosts_init(SCIP *scip, int nnodes, int nedges, SCIP_Real cutoff, int redCostRoot, REDCOST **redcostdata)
Definition: redcosts.c:605
#define flipedge(edge)
Definition: graphdefs.h:84
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPStpHeurSlackPruneRun(SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool initialreduce, SCIP_Bool fullreduce)
void graph_getEdgeCosts(const GRAPH *, SCIP_Real *RESTRICT, SCIP_Real *RESTRICT)
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
static SCIP_Bool dapathsIsPromising(const GRAPH *g)
Definition: reduce_da.c:2263
static SCIP_RETCODE daOrderRoots(SCIP *scip, const GRAPH *graph, int *terms, int nterms, SCIP_Bool randomize, SCIP_RANDNUMGEN *randnumgen)
Definition: reduce_da.c:1587
SCIP_RETCODE reduce_unconnectedForDirected(SCIP *, GRAPH *)
static int reduceWithEdgeFixingBounds(SCIP *scip, GRAPH *graph, GRAPH *transgraph, const SCIP_Real *fixingbounds, const int *result, SCIP_Real upperbound)
Definition: reduce_da.c:899
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 SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10025
int * redcosts_getNodeToTermsBasesTop(const REDCOST *redcostdata)
Definition: redcosts.c:277
SCIP_Bool graph_typeIsUndirected(const GRAPH *)
Definition: graph_stats.c:69
void redcosts_setCutoffFromBound(SCIP_Real upperbound, int level, REDCOST *redcostdata)
Definition: redcosts.c:645
int * soledges
Definition: solpool.h:41
static SCIP_RETCODE computeSteinerTreeRedCostsDirected(SCIP *scip, GRAPH *graph, const REDCOST *redcostdata, int *result, int *bestresult, SCIP_Bool *havebestsol, SCIP_Real *bestobjval)
Definition: reduce_da.c:369
#define Is_pseudoTerm(a)
Definition: graphdefs.h:103
#define DARUNS_TERMRATIO_MED
Definition: reduce_da.c:55
static void deleteEdge(SCIP *scip, int edge, GRAPH *g, PR *pr)
Definition: reduce_path.c:127
SCIP_RETCODE reduce_extendedCheck3Tree(SCIP *, const GRAPH *, int, const SCIP_Real *, const SCIP_Real *, const PATH *, const int *, SCIP_Real, const int *, int, SCIP_Real *, SCIP_Bool *, unsigned int *, int *, SCIP_Bool *)
Definition: reduce_ext.c:842
SCIP_RETCODE SCIPStpHeurRecRun(SCIP *scip, STPSOLPOOL *pool, SCIP_HEUR *heur, SCIP_HEURDATA *heurdata, const GRAPH *graph, SCIP_VAR **vars, int *newsolindex, int runs, int nsols, SCIP_Bool restrictheur, SCIP_Bool *solfound)
Definition: heur_rec.c:1455
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE extreduce_deleteEdges(SCIP *, EXTPERMA *, GRAPH *, int *)
void redcosts_setDualBoundTop(SCIP_Real dualbound, REDCOST *redcostdata)
Definition: redcosts.c:420
static SCIP_RETCODE dapathsDeleteEdges(SCIP *scip, const REDCOST *redcostdata, const int *result, GRAPH *g, int *nelims)
Definition: reduce_da.c:2283
SCIP_RETCODE graph_transPcGetRsap(SCIP *, GRAPH *, GRAPH **, const int *, int, int)
Definition: graph_trans.c:1043
void graph_pc_2orgcheck(SCIP *, GRAPH *)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
#define DARUNS_TERMRATIO_HIGH
Definition: reduce_da.c:56
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_RETCODE solstp_reroot(SCIP *scip, const GRAPH *g, int *result, int newroot)
Definition: solstp.c:1559
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
SCIP_VAR * a
Definition: circlepacking.c:57
static SCIP_RETCODE dapathsReplaceNodes(SCIP *scip, REDCOST *redcostdata, const int *result, SCIP_Real objbound_upper, GRAPH *g, SCIP_Real *offsetp, int *nelims)
Definition: reduce_da.c:2308
static void daPcMarkRoots(SCIP *scip, const int *roots, int nrootsold, int nrootsnew, SCIP_Real prizesum, GRAPH *graph, SCIP_Bool *userec, STPSOLPOOL **solpool)
Definition: reduce_da.c:1431
#define SCIP_Real
Definition: def.h:177
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:137
#define StpVecFree(scip, vec)
Definition: stpvector.h:153
Primal recombination heuristic for Steiner problems.
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_Real * redcosts_getRootToNodeDistTop(const REDCOST *redcostdata)
Definition: redcosts.c:228
static SCIP_RETCODE computeSteinerTreeTM(SCIP *scip, GRAPH *graph, int *result, SCIP_Real *bestobjval, SCIP_Bool *success)
Definition: reduce_da.c:192
shortest paths based primal heuristics for Steiner problems
reduction based primal heuristic for Steiner problems
int edges
Definition: graphdefs.h:219
static int reduceWithNodeFixingBounds(SCIP *scip, GRAPH *graph, GRAPH *transgraph, const SCIP_Real *fixingbounds, SCIP_Real upperbound)
Definition: reduce_da.c:859
SCIP_RETCODE reduce_dapaths(SCIP *scip, GRAPH *g, SCIP_Real *offsetp, int *nelims)
Definition: reduce_da.c:2397
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
void graph_pc_knotToFixedTerm(SCIP *, GRAPH *, int, SCIP_Real *)
SCIP_RETCODE extreduce_init(SCIP *, SCIP_Bool, enum EXTRED_MODE, GRAPH *, REDCOST *, EXTPERMA **)
void solstp_setVertexFromEdge(const GRAPH *g, const int *result, STP_Bool *solnode)
Definition: solstp.c:2078
static SCIP_Real getSolObj(SCIP *scip, const GRAPH *g, const int *soledge)
Definition: reduce_da.c:68
#define DEFAULT_DARUNS_FAST
Definition: reduce_da.c:51
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define UNKNOWN
Definition: sepa_mcf.c:4095
static SCIP_Bool daRedCostIsValid(SCIP *scip, GRAPH *transgraph, const SCIP_Real *cost, int *nodearrint, STP_Bool *nodearrbool)
Definition: reduce_da.c:1488
static void updateEdgeFixingBounds(SCIP_Real *fixingbounds, const GRAPH *graph, const SCIP_Real *cost, const SCIP_Real *pathdist, const PATH *vnoi, SCIP_Real lpobjval, int extnedges, SCIP_Bool initialize, SCIP_Bool undirected)
Definition: reduce_da.c:788
#define nnodes
Definition: gastrans.c:65
void graph_add1stTermPaths(const GRAPH *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1464
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:167
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
void extreduce_extPermaAddRandnumgen(SCIP_RANDNUMGEN *, EXTPERMA *)
static SCIP_RETCODE updateNodeReplaceBounds(SCIP *scip, const REDCOST *redcostdata, const GRAPH *graph, SCIP_Real *replacebounds, SCIP_Real upperbound, SCIP_Bool initialize, SCIP_Bool extendedsearch)
Definition: reduce_da.c:612
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
#define Is_anyTerm(a)
Definition: graphdefs.h:105
#define DAMAXDEVIATION_RANDOM_UPPER
Definition: reduce_da.c:62
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
int hoplimit
Definition: graphdefs.h:216
includes various reduction methods for Steiner tree problems
static void collectFixedTerminals(const GRAPH *graph, int *terminals, int *nterms)
Definition: reduce_da.c:545
SCIP_Real reduce_sollocalGetUpperBound(const REDSOLLOCAL *)
Definition: reduce_sol.c:633
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
#define STP_DABD_MAXDEGREE
Definition: reduce_da.c:59
void redcosts_setRootTop(int root, REDCOST *redcostdata)
Definition: redcosts.c:447
SCIP_RETCODE dualascent_pathsPcMw(SCIP *scip, const GRAPH *transgraph, SCIP_Real *RESTRICT redcost, SCIP_Real *objval, const int *result)
Definition: dualascent.c:1780
SCIP_RETCODE redcosts_initFromParams(SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
Definition: redcosts.c:590
int graph_pc_getTwinTerm(const GRAPH *, int)
void redcosts_increaseOnDeletedArcsTop(const GRAPH *graph, const STP_Bool *arcsdeleted, REDCOST *redcostdata)
Definition: redcosts.c:728
SCIP_Bool reduce_sollocalUsesNodesol(const REDSOLLOCAL *)
Definition: reduce_sol.c:554
static SCIP_RETCODE computeSteinerTreeRedCosts(SCIP *scip, GRAPH *graph, const REDCOST *redcostdata, SCIP_Bool useSlackPrune, SCIP_Bool useRec, STPSOLPOOL *pool, int *result, int *bestresult, SCIP_Bool *havebestsol, SCIP_Real *bestobjval)
Definition: reduce_da.c:260
SCIP_RETCODE extreduce_pseudoDeleteNodes(SCIP *, const SCIP_Bool *, EXTPERMA *, GRAPH *, SCIP_Real *, int *)