reduce_termsepafull.c
Go to the documentation of this file.
21 * These techniques require to solve subproblems to optimality. See reduce_termsepada.c for related,
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
71 SCIP_Real* subgraph_orgcosts; /**< original edge costs, with artificial edges having cost FARAWAY */
72 STP_Vectype(int*) solcands_sepaedges; /**< bottleneck edges (w.r.t. subgraph) for each solution candidate */
73 STP_Vectype(int*) solcands_sepapart; /**< partition of the separator terminals for each solution candidate */
81 STP_Vectype(int*) partitions; /**< all partitions; each stores as array with mark 0,1,..., according to subset membership
359 SCIP_CALL( extreduce_distDataInit(scip, subgraph, 50, useSd, useBias, &(tsepafull->subdistdata)) );
454 assert(StpVecGetSize(tsepafull->solcands_sepaedges) == StpVecGetSize(tsepafull->solcands_sepapart));
514 /** computes artificial edges for each solution candidate (and tries to rule-out some candidates already) */
739 SCIPdebugMessage("ruled out: ngroupsoledges=%d ngroupnodes=%d \n", ngroupsoledges, ngroupnodes);
799 assert(StpVecGetSize(tsepafull->solcands_sepaedges) == StpVecGetSize(tsepafull->solcands_sepapart));
907 /* NOTE: edge will be automatically contracted later; we avoid trouble other terminal separators */
1077 SCIP_CALL( mincut_termsepasInit(scip, g, (int) (2.0 * maxncompchecks), maxsepasize, termsepas) );
1135 SCIPdebugMessage("starting termsepFull, with %d separators \n", mincut_termsepasGetNall(termsepas));
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
static SCIP_RETCODE sepafullInit(SCIP *scip, GRAPH *subgraph, TSEPAFULL **tsepafull)
Definition: reduce_termsepafull.c:368
static SCIP_Bool subSolIsRedundant(SCIP *scip, const TERMCOMP *termcomp, const int *subsol, const int *sepapartition, STP_Vectype(int) solcand_sepaedges)
Definition: reduce_termsepafull.c:686
Definition: graphdefs.h:184
SCIP_RETCODE reduce_termcompChangeSubgraphToBottleneck(SCIP *, GRAPH *, TERMCOMP *, SCIP_Bool *)
Definition: reduce_termsepa.c:837
void reduce_compbuilderPrintSeparators(const GRAPH *, const COMPBUILDER *)
Definition: reduce_termsepa.c:779
Definition: struct_scip.h:59
SCIP_Real extreduce_distDataGetSdDouble(SCIP *, const GRAPH *, int, int, DISTDATA *)
Definition: extreduce_dist.c:1463
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
static SCIP_RETCODE sepafullReduce(SCIP *scip, GRAPH *orggraph, REDBASE *redbase, TSEPAFULL *tsepafull, TERMCOMP *termcomp, int *nelims)
Definition: reduce_termsepafull.c:933
static SCIP_Bool termcompIsPromising(const GRAPH *g, const COMPBUILDER *builder)
Definition: reduce_termsepafull.c:961
void extreduce_distDataFree(SCIP *, const GRAPH *, DISTDATA **)
Definition: extreduce_dist.c:1784
void reduce_termcompChangeSubgraphToOrgCosts(const GRAPH *, TERMCOMP *)
Definition: reduce_termsepa.c:930
SCIP_RETCODE reduce_termsepaFull(SCIP *scip, GRAPH *g, int *solnode, REDBASE *redbase, int *nelims)
Definition: reduce_termsepafull.c:1107
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: substpsolver.c:58
includes methods for Steiner tree problem solutions
void reduce_termsepaGetNextComp(SCIP *, const GRAPH *, TERMSEPAS *, COMPBUILDER *, SCIP_Bool *)
Definition: reduce_termsepa.c:1072
SCIP_RETCODE substpsolver_setProbFullPresolve(SUBSTP *substp)
Definition: substpsolver.c:568
static SCIP_RETCODE bpartitionsCompute(SCIP *scip, BPARTITIONS *bparts)
Definition: reduce_termsepafull.c:249
SCIP_RETCODE reduce_compbuilderInit(SCIP *, const GRAPH *, COMPBUILDER **)
Definition: reduce_termsepa.c:716
includes various files containing graph methods used for Steiner tree problems
Definition: struct_misc.h:259
static SCIP_RETCODE bsubpartAdd(SCIP *scip, int subsize, int maxgroupid, BPARTITIONS *bparts)
Definition: reduce_termsepafull.c:171
#define COMPONENT_MAXNODESRATIO_3SEPA
Definition: reduce_termsepafull.c:50
Definition: termsepadefs.h:43
SCIP_Real reduce_compbuilderGetSubNodesRatio(const COMPBUILDER *)
Definition: reduce_termsepa.c:765
Definition: reducedefs.h:100
#define COMPONENT_MAXNODESRATIO_4SEPA
Definition: reduce_termsepafull.c:51
int mincut_termsepasGetNall(const TERMSEPAS *termsepas)
Definition: mincut.c:2135
header only, simple implementation of an STL like vector
SCIP_RETCODE substpsolver_initBC(SCIP *scip, GRAPH *subgraph, SUBSTP **substp)
Definition: substpsolver.c:359
static SCIP_RETCODE sepafullBuildSolcandsEdges(SCIP *scip, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
Definition: reduce_termsepafull.c:516
#define COMPONENT_MAXNODESRATIO_2CANDS
Definition: reduce_termsepafull.c:54
This file implements extended reduction techniques for several Steiner problems.
static void sepafullAddSingleSolcandEdges(SCIP *scip, int partitionidx, const TERMCOMP *termcomp, BPARTITIONS *bpartitions, TSEPAFULL *tsepafull)
Definition: reduce_termsepafull.c:436
static SCIP_RETCODE sepafullAddSolForCand(SCIP *scip, int cand, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
Definition: reduce_termsepafull.c:785
SCIP_RETCODE mincut_findTerminalSeparators(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, TERMSEPAS *termsepas)
Definition: mincut.c:2274
#define COMPONENT_MAXNODESRATIO_2SEPA
Definition: reduce_termsepafull.c:49
Definition: reduce_termsepafull.c:65
static SCIP_RETCODE bpartitionsInit(SCIP *scip, int nelems, BPARTITIONS **bparitions)
Definition: reduce_termsepafull.c:296
#define COMPONENT_MAXNODESRATIO_1CANDS
Definition: reduce_termsepafull.c:53
static void freeHelpers(SCIP *scip, COMPBUILDER **builder, TERMSEPAS **termsepas)
Definition: reduce_termsepafull.c:1089
SCIP_RETCODE substpsolver_initHistory(SUBSTP *substp)
Definition: substpsolver.c:430
static SCIP_RETCODE solveSub(SCIP *scip, const GRAPH *subgraph, int *subedges_sol)
Definition: reduce_termsepafull.c:645
Solver for Steiner tree (sub-) problems.
Definition: type_retcode.h:33
static SCIP_RETCODE sepafullBuildSolcands(SCIP *scip, GRAPH *orggraph, TERMCOMP *termcomp, TSEPAFULL *tsepafull, SCIP_Bool *success)
Definition: reduce_termsepafull.c:551
static void sepafullFree(SCIP *scip, TSEPAFULL **tsepafull)
Definition: reduce_termsepafull.c:396
Definition: reduce_termsepafull.c:79
static void setSubBottleneckEdges(int cand, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
Definition: reduce_termsepafull.c:755
static int getPartitionNgroups(int nelems, const int *partition)
Definition: reduce_termsepafull.c:95
SCIP_RETCODE reduce_termcompBuildSubgraph(SCIP *, GRAPH *, TERMCOMP *)
Definition: reduce_termsepa.c:818
static SCIP_RETCODE processComponent(SCIP *scip, COMPBUILDER *builder, GRAPH *g, REDBASE *redbase, int *nelims)
Definition: reduce_termsepafull.c:1002
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
Definition: mincut.c:89
SCIP_RETCODE substpsolver_getSolution(SUBSTP *substp, int *edgesol)
Definition: substpsolver.c:500
void mincut_termsepasFree(SCIP *scip, TERMSEPAS **termsepas)
Definition: mincut.c:2113
#define COMPONENT_MAXNODESRATIO_5PLUSCANDS
Definition: reduce_termsepafull.c:57
Definition: extreducedefs.h:79
static void bpartitionsDebugPrintTop(const BPARTITIONS *bparitions)
Definition: reduce_termsepafull.c:149
Portable definitions.
SCIP_RETCODE mincut_termsepasInit(SCIP *scip, const GRAPH *g, int maxnsepas, int maxsepasize, TERMSEPAS **termsepas)
Definition: mincut.c:2074
static void bpartitionsFree(SCIP *scip, BPARTITIONS **bparitions)
Definition: reduce_termsepafull.c:320
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
void reduce_compbuilderFree(SCIP *, COMPBUILDER **)
Definition: reduce_termsepa.c:751
static SCIP_RETCODE sepafullReduceFromSols(SCIP *scip, GRAPH *orggraph, REDBASE *redbase, TSEPAFULL *tsepafull, TERMCOMP *termcomp, int *nelims)
Definition: reduce_termsepafull.c:826
#define COMPONENT_MAXNODESRATIO_3CANDS
Definition: reduce_termsepafull.c:55
SCIP_Real * reduce_solGetOffsetPointer(REDSOL *)
Definition: reduce_sol.c:1285
struct bell_parititioner BPARTITIONS
static SCIP_Bool sepafullSolcandsArePromising(const TERMCOMP *termcomp, const TSEPAFULL *tsepafull)
Definition: reduce_termsepafull.c:594
static SCIP_RETCODE initHelpers(SCIP *scip, const GRAPH *g, COMPBUILDER **builder, TERMSEPAS **termsepas)
Definition: reduce_termsepafull.c:1042
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
SCIP_RETCODE reduce_contract0Edges(SCIP *, GRAPH *, int *, SCIP_Bool)
Definition: reduce_simple.c:733
Minimum cut routines for Steiner problems.
Definition: objbenders.h:33
SCIP_RETCODE substpsolver_solve(SCIP *scip, SUBSTP *substp, SCIP_Bool *success)
Definition: substpsolver.c:452
includes various reduction methods for Steiner tree problems
Definition: termsepadefs.h:61
SCIP_RETCODE reduce_bidecompositionExact(SCIP *, GRAPH *, REDBASE *, int *, int *)
Definition: reduce_sepa.c:1085
static SCIP_RETCODE sepafullInitDistdata(SCIP *scip, TERMCOMP *termcomp, TSEPAFULL *tsepafull)
Definition: reduce_termsepafull.c:343
static void getPartitionGroupsSizes(int nelems, int ngroups, const int *partition, int *groups_sizes)
Definition: reduce_termsepafull.c:124
SCIP callable library.
struct terminal_separator_full TSEPAFULL