reduce_termsepada.c
Go to the documentation of this file.
20 * This file implements terminal-separator based reduction techniques for several Steiner problems that
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
190 RCPARAMS rcparams = { .cutoff = -1.0, .nLevels = 1, .nCloseTerms = 2, .nnodes = subgraph->knots,
200 SCIP_CALL( dualascent_exec(scip, subgraph, NULL, daparams, redcosts_getEdgeCostsTop(redcostdata), &subdual) );
238 SCIP_CALL( termcompReduceWithParams(scip, &daparams, g, extperma, termcomp, pseudoDelNodes, nelims) );
248 SCIP_CALL( termcompReduceWithParams(scip, &daparams, g, extperma, termcomp, pseudoDelNodes, nelims) );
412 SCIP_CALL( mincut_termsepasInit(scip, g, (int) (1.5 * maxncompchecks), maxsepasize, termsepas) );
490 * NOTE: intended to be used for debugging and unit tests, since creation of SD data is expensive
SCIP_RETCODE reduce_termsepaDa(SCIP *scip, GRAPH *g, int *nelims)
Definition: reduce_termsepada.c:492
SCIP_RETCODE reduce_termsepaDaWithExperma(SCIP *scip, GRAPH *g, EXTPERMA *extperma, SCIP_Bool *pseudoDelNodes, int *nelims)
Definition: reduce_termsepada.c:441
Definition: reducedefs.h:71
Definition: graphdefs.h:184
SCIP_RETCODE reduce_termcompChangeSubgraphToBottleneck(SCIP *, GRAPH *, TERMCOMP *, SCIP_Bool *)
Definition: reduce_termsepa.c:837
Definition: struct_scip.h:59
static SCIP_RETCODE termcompComputeSubgraphSol(SCIP *scip, TERMCOMP *termcomp)
Definition: reduce_termsepada.c:257
static SCIP_RETCODE termcompReduce(SCIP *scip, GRAPH *g, EXTPERMA *extperma, TERMCOMP *termcomp, SCIP_Bool *pseudoDelNodes, int *nelims)
Definition: reduce_termsepada.c:224
SCIP_Real redcosts_getCutoffTop(const REDCOST *redcostdata)
Definition: redcosts.c:300
Definition: dualascent.h:39
includes methods for Steiner tree problem solutions
void reduce_termsepaGetNextComp(SCIP *, const GRAPH *, TERMSEPAS *, COMPBUILDER *, SCIP_Bool *)
Definition: reduce_termsepa.c:1072
Definition: extreducedefs.h:101
reduction and dual-cost based primal heuristic for Steiner problems
SCIP_RETCODE reduce_compbuilderInit(SCIP *, const GRAPH *, COMPBUILDER **)
Definition: reduce_termsepa.c:716
Includes dual-ascent for classic Steiner tree and some variants.
DISTDATA * distdata_default
Definition: extreducedefs.h:106
includes various files containing graph methods used for Steiner tree problems
Definition: graphdefs.h:284
Definition: termsepadefs.h:43
SCIP_Real reduce_compbuilderGetSubNodesRatio(const COMPBUILDER *)
Definition: reduce_termsepa.c:765
static void freeHelpers(SCIP *scip, COMPBUILDER **builder, TERMSEPAS **termsepas)
Definition: reduce_termsepada.c:423
static SCIP_RETCODE initHelpers(SCIP *scip, const GRAPH *g, const EXTPERMA *extperma, COMPBUILDER **builder, TERMSEPAS **termsepas)
Definition: reduce_termsepada.c:380
SCIP_RETCODE redcosts_initializeDistancesTop(SCIP *scip, GRAPH *g, REDCOST *redcostdata)
Definition: redcosts.c:573
header only, simple implementation of an STL like vector
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 SCIP_RETCODE processComponent(SCIP *scip, COMPBUILDER *builder, GRAPH *g, EXTPERMA *extperma, SCIP_Bool *pseudoDelNodes, int *nelims)
Definition: reduce_termsepada.c:345
SCIP_RETCODE reduce_termcompInitTbottleneck(SCIP *, const int *, TERMCOMP *)
Definition: reduce_termsepa.c:1019
This file implements extended reduction techniques for several Steiner problems.
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)
Definition: heur_ascendprune.c:940
SCIP_RETCODE extreduce_extPermaInit(SCIP *, enum EXTRED_MODE, const GRAPH *, STP_Bool *, EXTPERMA **)
Definition: extreduce_data.c:162
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
static SCIP_Bool termcompIsPromising(const GRAPH *g, const COMPBUILDER *builder)
Definition: reduce_termsepada.c:309
void extreduce_edgeRemove(SCIP *, int, GRAPH *, DISTDATA *, EXTPERMA *)
Definition: extreduce_base.c:1946
SCIP_RETCODE SCIPStpHeurLocalRun(SCIP *scip, GRAPH *graph, int *solEdges)
Definition: heur_local.c:3899
Definition: type_retcode.h:33
Improvement heuristic for Steiner problems.
Definition: mincut.c:89
PATH * redcosts_getNodeToTermsPathsTop(const REDCOST *redcostdata)
Definition: redcosts.c:253
void mincut_termsepasFree(SCIP *scip, TERMSEPAS **termsepas)
Definition: mincut.c:2113
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)
Definition: scip_numerics.c:477
SCIP_RETCODE reduce_termcompInit(SCIP *, const GRAPH *, COMPBUILDER *, TERMCOMP **)
Definition: reduce_termsepa.c:982
SCIP_RETCODE extreduce_distDataInit(SCIP *, GRAPH *, int, SCIP_Bool, SCIP_Bool, DISTDATA **)
Definition: extreduce_dist.c:1218
SCIP_RETCODE reduce_termcompBuildSubgraphWithSds(SCIP *, GRAPH *, EXTPERMA *, TERMCOMP *)
Definition: reduce_termsepa.c:799
void redcosts_setDualBoundTop(SCIP_Real dualbound, REDCOST *redcostdata)
Definition: redcosts.c:420
void reduce_compbuilderFree(SCIP *, COMPBUILDER **)
Definition: reduce_termsepa.c:751
static SCIP_RETCODE termcompReduceWithParams(SCIP *scip, DAPARAMS *daparams, GRAPH *g, EXTPERMA *extperma, TERMCOMP *termcomp, SCIP_Bool *pseudoDelNodes, int *nelims)
Definition: reduce_termsepada.c:179
SCIP_Real * redcosts_getRootToNodeDistTop(const REDCOST *redcostdata)
Definition: redcosts.c:228
Definition: redcosts.h:42
Definition: redcosts.c:34
static void termcompMarkPseudoDelNodes(SCIP *scip, const REDCOST *redcostdata, const TERMCOMP *termcomp, GRAPH *g, EXTPERMA *extperma, SCIP_Bool *pseudoDelNodes)
Definition: reduce_termsepada.c:139
Minimum cut routines for Steiner problems.
Definition: objbenders.h:33
SCIP_RETCODE reduce_sdRepairSetUp(SCIP *, const GRAPH *, SD *)
Definition: reduce_sdutil.c:853
static void termcompDeleteEdges(SCIP *scip, const REDCOST *redcostdata, const TERMCOMP *termcomp, GRAPH *g, EXTPERMA *extperma, int *nelims)
Definition: reduce_termsepada.c:67
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
Definition: termsepadefs.h:61
SCIP callable library.
SCIP_RETCODE redcosts_initFromParams(SCIP *scip, const RCPARAMS *parameters, REDCOST **redcostdata)
Definition: redcosts.c:590