Scippy

SCIP

Solving Constraint Integer Programs

reduce_termsepada.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_termsepada.c
17  * @brief several terminal-separator/dual-ascent based reductions for Steiner tree problems
18  * @author Daniel Rehfeldt
19  *
20  * This file implements terminal-separator based reduction techniques for several Steiner problems that
21  * use dual-ascent for reductions
22  *
23  * A list of all interface methods can be found in reduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 //#define SCIP_DEBUG
29 
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include <assert.h>
34 #include "graph.h"
35 #include "dualascent.h"
36 #include "reduce.h"
37 #include "extreduce.h"
38 #include "solstp.h"
39 #include "heur_local.h"
40 #include "mincut.h"
41 #include "heur_ascendprune.h"
42 #include "portab.h"
43 #include "stpvector.h"
44 #include "scip/scip.h"
45 
46 // todo tune values, more or less random
47 
48 #define COMPONENT_NODESRATIO_MIN 0.01
49 #define COMPONENT_NODESRATIO_SMALL 0.1
50 #define COMPONENT_NODESRATIO_MAX 0.5
51 
52 #define SEPARATOR_MAXSIZE 5
53 #define SEPARATOR_MAXNCHECKS 75
54 #define SEPARATOR_MAXSIZE_FAST 4
55 #define SEPARATOR_MAXNCHECKS_FAST 40
56 #define SEPARATOR_MINTERMRATIO 0.12
57 #define SEPARATOR_MINTERMRATIO_FAST 0.005
58 
59 
60 /*
61  * Local methods
62  */
63 
64 
65 /** deletes */
66 static
68  SCIP* scip, /**< SCIP data structure */
69  const REDCOST* redcostdata, /**< reduced costs */
70  const TERMCOMP* termcomp, /**< component */
71  GRAPH* g, /**< graph data structure */
72  EXTPERMA* extperma, /**< extension data */
73  int* nelims /**< number of eliminations*/
74  )
75 {
76  GRAPH* subgraph = termcomp->subgraph;
77  const int subnnodes = graph_get_nNodes(subgraph);
78  const PATH* vnoi = redcosts_getNodeToTermsPathsTop(redcostdata);
79  const SCIP_Real* cost = redcosts_getEdgeCostsTop(redcostdata);
80  const SCIP_Real* pathdist = redcosts_getRootToNodeDistTop(redcostdata);
81  const SCIP_Real cutoffbound = redcosts_getCutoffTop(redcostdata);
82  const int* const edgemap_subToOrg = termcomp->edgemap_subToOrg;
83  const int* result = extperma->result;
84 
85  assert(graph_isMarked(g));
86  assert(!extperma->solIsValid || result);
87 
88  for( int k = 0; k < subnnodes; k++ )
89  {
90  int e = subgraph->outbeg[k];
91  while( e != EAT_LAST )
92  {
93  const int enext = subgraph->oeat[e];
94  const int subhead = subgraph->head[e];
95  const int eorg = edgemap_subToOrg[e];
96 
97  /* NOTE: we avoid double checking and deletion of artificial edges */
98  if( subhead > k && eorg >= 0)
99  {
100  SCIP_Real redcost = pathdist[k] + cost[e] + vnoi[subhead].dist;
101 
102  if( !SCIPisGT(scip, redcost, cutoffbound) )
103  {
104  e = enext;
105  continue;
106  }
107 
108  redcost = pathdist[subhead] + cost[flipedge(e)] + vnoi[k].dist;
109 
110  if( SCIPisGT(scip, redcost, cutoffbound) && !graph_edge_isDeleted(g, eorg) )
111  {
112 #ifdef SCIP_DEBUG
113  SCIPdebugMessage("deleting original edge (%f>%f): ", redcost, cutoffbound);
114  graph_edge_printInfo(g, eorg);
115 #endif
116  extreduce_edgeRemove(scip, eorg, g, extperma->distdata_default, extperma);
117  // todo todo is that ok??? might also change the primal bound
118  graph_edge_del(scip, subgraph, e, FALSE);
119  if( extperma->solIsValid && (result[e] == CONNECT || result[flipedge(e)] == CONNECT) )
120  extperma->solIsValid = FALSE;
121 
122  (*nelims)++;
123  }
124  }
125 
126  e = enext;
127  }
128  }
129 
130 
131 
132  assert(graph_valid(scip, g));
133 }
134 
135 
136 
137 /** marks nodes for pseudo-deletion */
138 static
140  SCIP* scip, /**< SCIP data structure */
141  const REDCOST* redcostdata, /**< reduced costs */
142  const TERMCOMP* termcomp, /**< component */
143  GRAPH* g, /**< graph data structure */
144  EXTPERMA* extperma, /**< extension data */
145  SCIP_Bool* pseudoDelNodes /**< array to mark pseudo deletable nodes */
146  )
147 {
148  GRAPH* subgraph = termcomp->subgraph;
149  const int subnnodes = graph_get_nNodes(subgraph);
150  const PATH* const vnoi = redcosts_getNodeToTermsPathsTop(redcostdata);
151  const SCIP_Real* const pathdist = redcosts_getRootToNodeDistTop(redcostdata);
152  const int* const nodemap_subToOrg = termcomp->nodemap_subToOrg;
153  const SCIP_Real cutoffbound = redcosts_getCutoffTop(redcostdata);
154 
155  for( int k = 0; k < subnnodes; k++ )
156  {
157  if( !Is_term(subgraph->term[k]) )
158  {
159  const SCIP_Real redcost = pathdist[k] + vnoi[k].dist + vnoi[k + subnnodes].dist;
160 
161  if( SCIPisGT(scip, redcost, cutoffbound) )
162  {
163  const int orgnode = nodemap_subToOrg[k];
164  assert(graph_knot_isInRange(g, orgnode));
165  pseudoDelNodes[orgnode] = TRUE;
166 
167 #ifdef SCIP_DEBUG
168  SCIPdebugMessage("marking original node (%f>%f): ", redcost, cutoffbound);
169  graph_knot_printInfo(g, orgnode);
170 #endif
171  }
172  }
173  }
174 }
175 
176 
177 /** perform reductions */
178 static
180  SCIP* scip, /**< SCIP data structure */
181  DAPARAMS* daparams, /**< dual-ascent parameters */
182  GRAPH* g, /**< graph data structure */
183  EXTPERMA* extperma, /**< extension data */
184  TERMCOMP* termcomp, /**< component */
185  SCIP_Bool* pseudoDelNodes, /**< array to mark pseudo deletable nodes or NULL (OUT) */
186  int* nelims /**< number of eliminations*/
187  )
188 {
189  GRAPH* subgraph = termcomp->subgraph;
190  RCPARAMS rcparams = { .cutoff = -1.0, .nLevels = 1, .nCloseTerms = 2, .nnodes = subgraph->knots,
191  .nedges = subgraph->edges, .redCostRoot = daparams->root };
192  REDCOST* redcostdata;
193  const SCIP_Real subprimal = termcomp->subprimalobj;
194  SCIP_Real subdual;
195 
196  assert(GE(subprimal, 0.0));
197 
198  SCIP_CALL( redcosts_initFromParams(scip, &rcparams, &redcostdata) );
199 
200  SCIP_CALL( dualascent_exec(scip, subgraph, NULL, daparams, redcosts_getEdgeCostsTop(redcostdata), &subdual) );
201 
202  SCIPdebugMessage("subdual=%f, subprimal=%f \n", subdual, subprimal);
203 
204  redcosts_setDualBoundTop(subdual, redcostdata);
205  graph_mark(subgraph);
206  SCIP_CALL( redcosts_initializeDistancesTop(scip, subgraph, redcostdata) );
207  redcosts_setCutoffFromBoundTop(subprimal, redcostdata);
208 
209  termcompDeleteEdges(scip, redcostdata, termcomp, g, extperma, nelims);
210 
211  if( pseudoDelNodes )
212  {
213  termcompMarkPseudoDelNodes(scip, redcostdata, termcomp, g, extperma, pseudoDelNodes);
214  }
215 
216  redcosts_free(scip, &redcostdata);
217 
218  return SCIP_OKAY;
219 }
220 
221 
222 /** perform reductions */
223 static
225  SCIP* scip, /**< SCIP data structure */
226  GRAPH* g, /**< graph data structure */
227  EXTPERMA* extperma, /**< extension data */
228  TERMCOMP* termcomp, /**< component */
229  SCIP_Bool* pseudoDelNodes, /**< array to mark pseudo deletable nodes or NULL (OUT) */
230  int* nelims /**< number of eliminations*/
231  )
232 {
233  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = -1,
234  .is_pseudoroot = FALSE, .damaxdeviation = -1.0 };
235  const COMPBUILDER* builder = termcomp->builder;
236 
237  daparams.root = termcomp->subgraph->source;
238  SCIP_CALL( termcompReduceWithParams(scip, &daparams, g, extperma, termcomp, pseudoDelNodes, nelims) );
239 
240  if( reduce_compbuilderGetSubNodesRatio(builder) <= COMPONENT_NODESRATIO_SMALL && *nelims > 0 )
241  {
242  const int sepaterm = builder->sepaterms[0];
243  assert(daparams.root != termcomp->nodemap_orgToSub[sepaterm]);
244  assert(graph_knot_isInRange(termcomp->subgraph, termcomp->nodemap_orgToSub[sepaterm]));
245 
246  daparams.root = termcomp->nodemap_orgToSub[sepaterm];
247 
248  SCIP_CALL( termcompReduceWithParams(scip, &daparams, g, extperma, termcomp, pseudoDelNodes, nelims) );
249  }
250 
251  return SCIP_OKAY;
252 }
253 
254 
255 /** computes primal solution on subgraph */
256 static
258  SCIP* scip, /**< SCIP data structure */
259  TERMCOMP* termcomp /**< component */
260  )
261 {
262  DAPARAMS daparams = { .addcuts = FALSE, .ascendandprune = FALSE, .root = -1,
263  .is_pseudoroot = FALSE, .damaxdeviation = -1.0 };
264 
265  GRAPH* subgraph = termcomp->subgraph;
266  SCIP_Real* redcosts;
267  int* subsol;
268  const int* const nodemap_orgToSub = termcomp->nodemap_orgToSub;
269  SCIP_Real dualobjval;
270  SCIP_Bool success;
271  const int nedges = graph_get_nEdges(subgraph);
272  const int sourceterm_org = termcomp->builder->sourceterm;
273 
274  assert(nedges >= 2);
275  assert(!termcomp->subsolution);
276  assert(nodemap_orgToSub);
277  assert(sourceterm_org >= 0);
278 
279  SCIP_CALL( SCIPallocMemoryArray(scip, &(subsol), nedges) );
280  SCIP_CALL( SCIPallocBufferArray(scip, &(redcosts), nedges) );
281 
282  daparams.root = nodemap_orgToSub[sourceterm_org];
283  SCIP_CALL( dualascent_exec(scip, subgraph, NULL, &daparams, redcosts, &dualobjval) );
284 
285  SCIP_CALL( SCIPStpHeurAscendPruneRun(scip, NULL, subgraph, redcosts, subsol,
286  daparams.root, &success, FALSE));
287  assert(success);
288 
289  // todo maybe deactivate if still too expensive...
291  SCIP_CALL( SCIPStpHeurLocalRun(scip, subgraph, subsol) );
292 
293  termcomp->subsolution = subsol;
294  termcomp->subprimalobj = solstp_getObj(subgraph, subsol, 0.0);
295  SCIPfreeBufferArray(scip, &redcosts);
296 
297 #ifdef SCIP_DEBUG
298  SCIPdebugMessage("primal sub-sol value: %f \n", solstp_getObj(subgraph, subsol, 0.0));
299 #endif
300 
301  SCIP_CALL( reduce_termcompInitTbottleneck(scip, subsol, termcomp) );
302 
303  return SCIP_OKAY;
304 }
305 
306 
307 /** promising to perform reductions on given component? */
308 static
310  const GRAPH* g, /**< graph data structure */
311  const COMPBUILDER* builder /**< terminal separator component initializer */
312  )
313 {
314  const SCIP_Real noderatio = reduce_compbuilderGetSubNodesRatio(builder);
315 
316  assert(GT(noderatio, 0.0));
317  SCIPdebugMessage(" noderatio=%f \n", noderatio);
318 
319  /* NOTE: we allow a few components regardless of their size */
320  if( builder->componentnumber < 10 && noderatio < COMPONENT_NODESRATIO_MAX )
321  {
322 
323  SCIPdebugMessage("...component is promising \n");
324 
325  return TRUE;
326  }
327  else
328  {
329  if( noderatio < COMPONENT_NODESRATIO_MAX )
330  {
331  SCIPdebugMessage("...component is promising \n");
332  return TRUE;
333  }
334  }
335 
336  // todo correct currently, we always give true, but seems to be no problem....
337 
338  SCIPdebugMessage("...component is NOT promising! \n");
339  return TRUE;
340 }
341 
342 
343 /** processes subgraph associated with SEPADA */
344 static
346  SCIP* scip, /**< SCIP data structure */
347  COMPBUILDER* builder, /**< terminal separator component initializer */
348  GRAPH* g, /**< graph data structure */
349  EXTPERMA* extperma, /**< extension data */
350  SCIP_Bool* pseudoDelNodes, /**< array to mark pseudo deletable nodes or NULL (OUT) */
351  int* nelims /**< number of eliminations*/
352  )
353 {
354  TERMCOMP* termcomp;
355  SCIP_Bool success;
356 
357  SCIPdebugMessage("component nodes=%d \n", builder->ncomponentnodes);
358 
359  SCIP_CALL( reduce_termcompInit(scip, g, builder, &termcomp) );
360  SCIP_CALL( reduce_termcompBuildSubgraphWithSds(scip, g, extperma, termcomp) );
361  SCIP_CALL( termcompComputeSubgraphSol(scip, termcomp) );
362  SCIP_CALL( reduce_termcompChangeSubgraphToBottleneck(scip, g, termcomp, &success) );
363 
364  assert(success || *nelims > 0);
365 
366  /* NOTE: we might fail because the separator is not connected anymore one one side */
367  if( success )
368  {
369  SCIP_CALL( termcompReduce(scip, g, extperma, termcomp, pseudoDelNodes, nelims) );
370  }
371 
372  reduce_termcompFree(scip, &termcomp);
373 
374  return SCIP_OKAY;
375 }
376 
377 
378 /** initializes helpers */
379 static
381  SCIP* scip, /**< SCIP data structure */
382  const GRAPH* g, /**< graph data structure */
383  const EXTPERMA* extperma, /**< extension data */
384  COMPBUILDER** builder, /**< to initialize */
385  TERMSEPAS** termsepas /**< to initialize */
386  )
387 {
388  int mincheckbound;
389  int maxsepasize;
390  int maxncompchecks;
391 
392  if( extperma->mode == extred_fast )
393  {
394  mincheckbound = (int) (SEPARATOR_MINTERMRATIO_FAST * g->terms);
395  maxsepasize = SEPARATOR_MAXSIZE_FAST;
396  maxncompchecks = SEPARATOR_MAXNCHECKS_FAST;
397  }
398  else
399  {
400  mincheckbound = (int) (SEPARATOR_MINTERMRATIO * g->terms);
401  maxsepasize = SEPARATOR_MAXSIZE;
402  maxncompchecks = SEPARATOR_MAXNCHECKS;
403  }
404 
405  if( maxncompchecks < mincheckbound )
406  {
407  SCIPdebugMessage("update nChecks %d->%d \n", maxncompchecks, mincheckbound);
408  maxncompchecks = mincheckbound;
409  }
410 
411  /* NOTE: we want to allow a few more terminal separators to be able to choose small ones */
412  SCIP_CALL( mincut_termsepasInit(scip, g, (int) (1.5 * maxncompchecks), maxsepasize, termsepas) );
413  SCIP_CALL( reduce_compbuilderInit(scip, g, builder) );
414 
415  (*builder)->maxncompchecks = maxncompchecks;
416  (*builder)->maxsepasize = maxsepasize;
417 
418  return SCIP_OKAY;
419 }
420 
421 /** frees helper */
422 static
424  SCIP* scip, /**< SCIP data structure */
425  COMPBUILDER** builder, /**< to initialize */
426  TERMSEPAS** termsepas /**< to initialize */
427  )
428 {
429  reduce_compbuilderFree(scip, builder);
430  mincut_termsepasFree(scip, termsepas);
431 }
432 
433 
434 /*
435  * Interface methods
436  */
437 
438 
439 /** terminal-separator/dual-ascent reduction method given extperma
440  * todo maybe we want to also give terminal separators to be able to reuse them? */
442  SCIP* scip, /**< SCIP data structure */
443  GRAPH* g, /**< graph data structure */
444  EXTPERMA* extperma, /**< extension data */
445  SCIP_Bool* pseudoDelNodes, /**< array to mark pseudo deletable nodes or NULL (OUT) */
446  int* nelims /**< number of eliminations (OUT)*/
447  )
448 {
449  COMPBUILDER* builder;
450  TERMSEPAS* termsepas;
451 
452  assert(scip && g && nelims && extperma);
453  *nelims = 0;
454 
455  if( pseudoDelNodes )
456  BMSclearMemoryArray(pseudoDelNodes, g->knots);
457 
458  if( g->terms == 1 )
459  {
460  return SCIP_OKAY;
461  }
462 
463  SCIP_CALL( initHelpers(scip, g, extperma, &builder, &termsepas) );
464  SCIP_CALL( mincut_findTerminalSeparators(scip, extperma->randnumgen, g, termsepas) );
465 
466  for( ;; )
467  {
468  SCIP_Bool compWasFound;
469 
470  reduce_termsepaGetNextComp(scip, g, termsepas, builder, &compWasFound);
471 
472  if( !compWasFound )
473  break;
474 
475  if( !termcompIsPromising(g, builder) )
476  continue;
477 
478  SCIP_CALL( processComponent(scip, builder, g, extperma, pseudoDelNodes, nelims) );
479 
480  builder->componentnumber++;
481  }
482 
483  freeHelpers(scip, &builder, &termsepas);
484 
485  return SCIP_OKAY;
486 }
487 
488 
489 /** terminal-separator/dual-ascent reduction method
490  * NOTE: intended to be used for debugging and unit tests, since creation of SD data is expensive
491  * and is best combined with extended reduction techniques */
493  SCIP* scip, /**< SCIP data structure */
494  GRAPH* g, /**< graph data structure */
495  int* nelims /**< number of eliminations*/
496  )
497 {
498  EXTPERMA* extperma;
499  const SCIP_Bool useSd = TRUE;
500 
501  assert(scip && g && nelims);
502 
503  if( g->terms == 1 )
504  {
505  *nelims = 0;
506  return SCIP_OKAY;
507  }
508 
509  SCIP_CALL( graph_init_dcsr(scip, g) );
510  SCIP_CALL( extreduce_extPermaInit(scip, extred_fast, g, NULL, &extperma) );
511  SCIP_CALL( extreduce_distDataInit(scip, g, 50, useSd, FALSE, &(extperma->distdata_default)) );
513 
514  SCIP_CALL( reduce_termsepaDaWithExperma(scip, g, extperma, NULL, nelims) );
515 
516  /* NOTE: also frees DCSR */
517  extreduce_exit(scip, g, &extperma);
518 
519  return SCIP_OKAY;
520 }
SCIP_RETCODE reduce_termsepaDa(SCIP *scip, GRAPH *g, int *nelims)
SCIP_RETCODE reduce_termsepaDaWithExperma(SCIP *scip, GRAPH *g, EXTPERMA *extperma, SCIP_Bool *pseudoDelNodes, int *nelims)
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
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
enum EXTRED_MODE mode
#define SEPARATOR_MAXNCHECKS
SCIP_RETCODE reduce_termcompChangeSubgraphToBottleneck(SCIP *, GRAPH *, TERMCOMP *, SCIP_Bool *)
int source
Definition: graphdefs.h:195
static SCIP_RETCODE termcompComputeSubgraphSol(SCIP *scip, TERMCOMP *termcomp)
#define Is_term(a)
Definition: graphdefs.h:102
#define SEPARATOR_MINTERMRATIO
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
static SCIP_RETCODE termcompReduce(SCIP *scip, GRAPH *g, EXTPERMA *extperma, TERMCOMP *termcomp, SCIP_Bool *pseudoDelNodes, int *nelims)
int terms
Definition: graphdefs.h:192
SCIP_Real redcosts_getCutoffTop(const REDCOST *redcostdata)
Definition: redcosts.c:300
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_mark(GRAPH *)
Definition: graph_base.c:1130
includes methods for Steiner tree problem solutions
void reduce_termsepaGetNextComp(SCIP *, const GRAPH *, TERMSEPAS *, COMPBUILDER *, SCIP_Bool *)
void graph_knot_printInfo(const GRAPH *, int)
Definition: graph_stats.c:151
reduction and dual-cost based primal heuristic for Steiner problems
SCIP_RETCODE reduce_compbuilderInit(SCIP *, const GRAPH *, COMPBUILDER **)
#define FALSE
Definition: def.h:87
Includes dual-ascent for classic Steiner tree and some variants.
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_Real reduce_compbuilderGetSubNodesRatio(const COMPBUILDER *)
void redcosts_free(SCIP *scip, REDCOST **redcostdata)
Definition: redcosts.c:743
static void freeHelpers(SCIP *scip, COMPBUILDER **builder, TERMSEPAS **termsepas)
static SCIP_RETCODE initHelpers(SCIP *scip, const GRAPH *g, const EXTPERMA *extperma, COMPBUILDER **builder, TERMSEPAS **termsepas)
#define EAT_LAST
Definition: graphdefs.h:58
#define SCIPdebugMessage
Definition: pub_message.h:87
#define COMPONENT_NODESRATIO_MAX
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE redcosts_initializeDistancesTop(SCIP *scip, GRAPH *g, REDCOST *redcostdata)
Definition: redcosts.c:573
#define SEPARATOR_MAXSIZE
header only, simple implementation of an STL like vector
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
Definition: graph_util.c:1721
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
#define SEPARATOR_MAXSIZE_FAST
static SCIP_RETCODE processComponent(SCIP *scip, COMPBUILDER *builder, GRAPH *g, EXTPERMA *extperma, SCIP_Bool *pseudoDelNodes, int *nelims)
SCIP_RETCODE reduce_termcompInitTbottleneck(SCIP *, const int *, TERMCOMP *)
int *RESTRICT oeat
Definition: graphdefs.h:231
This file implements extended reduction techniques for several Steiner problems.
#define GE(a, b)
Definition: portab.h:85
#define COMPONENT_NODESRATIO_SMALL
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)
SCIP_RETCODE extreduce_extPermaInit(SCIP *, enum EXTRED_MODE, const GRAPH *, STP_Bool *, EXTPERMA **)
SCIP_RETCODE mincut_findTerminalSeparators(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, TERMSEPAS *termsepas)
Definition: mincut.c:2274
SCIP_Real * redcosts_getEdgeCostsTop(const REDCOST *redcostdata)
Definition: redcosts.c:202
SCIP_Real dist
Definition: graphdefs.h:286
static SCIP_Bool termcompIsPromising(const GRAPH *g, const COMPBUILDER *builder)
#define NULL
Definition: lpi_spx1.cpp:155
void extreduce_edgeRemove(SCIP *, int, GRAPH *, DISTDATA *, EXTPERMA *)
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RANDNUMGEN * randnumgen
Improvement heuristic for Steiner problems.
void reduce_termcompFree(SCIP *, TERMCOMP **)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SEPARATOR_MINTERMRATIO_FAST
#define GT(a, b)
Definition: portab.h:84
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool graph_edge_isDeleted(const GRAPH *, int)
Definition: graph_stats.c:121
SCIP_Bool graph_isMarked(const GRAPH *)
Definition: graph_base.c:1165
PATH * redcosts_getNodeToTermsPathsTop(const REDCOST *redcostdata)
Definition: redcosts.c:253
void mincut_termsepasFree(SCIP *scip, TERMSEPAS **termsepas)
Definition: mincut.c:2113
#define flipedge(edge)
Definition: graphdefs.h:84
int *RESTRICT term
Definition: graphdefs.h:196
void graph_edge_printInfo(const GRAPH *, int)
Definition: graph_stats.c:133
#define SEPARATOR_MAXNCHECKS_FAST
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
SCIP_RETCODE mincut_termsepasInit(SCIP *scip, const GRAPH *g, int maxnsepas, int maxsepasize, TERMSEPAS **termsepas)
Definition: mincut.c:2074
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE reduce_termcompInit(SCIP *, const GRAPH *, COMPBUILDER *, TERMCOMP **)
SCIP_RETCODE extreduce_distDataInit(SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
SCIP_RETCODE reduce_termcompBuildSubgraphWithSds(SCIP *, GRAPH *, EXTPERMA *, TERMCOMP *)
void redcosts_setDualBoundTop(SCIP_Real dualbound, REDCOST *redcostdata)
Definition: redcosts.c:420
void reduce_compbuilderFree(SCIP *, COMPBUILDER **)
static SCIP_RETCODE termcompReduceWithParams(SCIP *scip, DAPARAMS *daparams, GRAPH *g, EXTPERMA *extperma, TERMCOMP *termcomp, SCIP_Bool *pseudoDelNodes, int *nelims)
#define SCIP_Real
Definition: def.h:177
int *RESTRICT outbeg
Definition: graphdefs.h:204
SCIP_Real * redcosts_getRootToNodeDistTop(const REDCOST *redcostdata)
Definition: redcosts.c:228
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
static DPSUBSOL ** subsol
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:123
static void termcompMarkPseudoDelNodes(SCIP *scip, const REDCOST *redcostdata, const TERMCOMP *termcomp, GRAPH *g, EXTPERMA *extperma, SCIP_Bool *pseudoDelNodes)
Minimum cut routines for Steiner problems.
SCIP_RETCODE reduce_sdRepairSetUp(SCIP *, const GRAPH *, SD *)
static void termcompDeleteEdges(SCIP *scip, const REDCOST *redcostdata, const TERMCOMP *termcomp, GRAPH *g, EXTPERMA *extperma, int *nelims)
includes various reduction methods for Steiner tree problems
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
SCIP callable library.
SCIP_RETCODE redcosts_initFromParams(SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
Definition: redcosts.c:590