reduce_bnd.c
Go to the documentation of this file.
22 * Most tests can be found in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
202 SCIP_CALL( graph_voronoiWithRadius(scip, graph, adjgraph, vnoi, radius, cost, costrev, vbase, heap, state) );
238 SCIP_CALL( graph_voronoiWithRadius(scip, graph, NULL, vnoi, radius, cost, costrev, vbase, heap, state) );
341 if( !Is_term(graph->term[k]) && (!eliminate || SCIPisGT(scip, tmpcost, obj)) && solnode[k] != CONNECT )
400 if( SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
613 if( SCIPisGT(scip, -vnoi[tail].dist -vnoi[head + nnodes].dist, -vnoi[tail + nnodes].dist -vnoi[head].dist) )
729 SCIP_CALL( graph_voronoiWithRadius(scip, graph, adjgraph, vnoi, radius, cost, costrev, vbase, heap, state) );
914 if( SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
922 if( (SCIPisGT(scip, tmpcost, obj) || (((result != NULL) ? (result[e] != CONNECT) : 0) && result[flipedge(e)] != CONNECT && SCIPisGE(scip, tmpcost, obj)))
981 if( Is_term(graph->term[k]) && graph->mark[k] && graph->grad[k] > 2 && !graph_pc_knotIsFixedTerm(graph, k) )
1012 if( SCIPisGT(scip, tmpcost, obj) || SCIPisGT(scip, mstobj2 + vnoi[k].dist + vnoi[k + nnodes].dist, obj) )
1236 /** heuristic bound-based reductions for the (R)PCSTP, the MWCSP and the STP; used by prune heuristic */
1272 SCIP_CALL( boundPruneHeurMw(scip, graph, vnoi, cost, radius, costrev, offset, heap, state, vbase, solnode, soledge, nelims, minelims) );
1276 SCIP_CALL( boundPruneHeur(scip, graph, vnoi, cost, radius, costrev, offset, heap, state, vbase, solnode, soledge, nelims, minelims) );
1293 const RPDA paramsda = { .damode = STP_DAMODE_HOPS, .useSlackPrune = FALSE, .useRec = FALSE, .extredMode = extred_none,
1392 SCIP_CALL( graph_voronoiWithRadius(scip, graph, adjgraph, vnoi, radius, cost, costrev, vbase, heap, state) );
1443 if( !Is_term(graph->term[k]) && SCIPisGT(scip, vnoi[k].dist + vnoi[k + nnodes].dist + bound, hoplimit) )
1472 if( SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
1594 if( !Is_term(graph->term[k]) && SCIPisGT(scip, vnoi[k].dist + pathdist[k] + (double) bound, (double) hoplimit) )
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE reduce_da(SCIP *, GRAPH *, const RPDA *, REDSOLLOCAL *, SCIP_Real *, int *, SCIP_RANDNUMGEN *)
Definition: reduce_da.c:2471
Definition: graphdefs.h:184
Definition: struct_scip.h:59
SCIP_RETCODE reduce_boundHopDa(SCIP *scip, GRAPH *graph, int *nelims, SCIP_RANDNUMGEN *randnumgen)
Definition: reduce_bnd.c:1286
void graph_add3rdTermPaths(const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1501
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
SCIP_RETCODE reduce_boundHop(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, int *heap, int *state, int *vbase, int *nelims)
Definition: reduce_bnd.c:1323
void graph_path_exec(SCIP *, const GRAPH *, int, int, const SCIP_Real *, PATH *)
Definition: graph_path.c:541
Definition: struct_var.h:198
includes methods for Steiner tree problem solutions
SCIP_RETCODE SCIPStpHeurTMRun(SCIP *scip, enum PCMW_TmMode pcmw_tmmode, GRAPH *graph, int *starts, const SCIP_Real *prize, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Bool *success)
Definition: heur_tm.c:3418
reduction and dual-cost based primal heuristic for Steiner problems
Definition: reducedefs.h:71
Problem data for stp problem.
includes various files containing graph methods used for Steiner tree problems
Definition: struct_misc.h:259
Definition: graphdefs.h:284
void graph_add4thTermPaths(const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1521
SCIP_RETCODE reduce_bound(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *radius, SCIP_Real *offset, SCIP_Real *upperbound, int *heap, int *state, int *vbase, int *nelims)
Definition: reduce_bnd.c:655
SCIP_RETCODE graph_voronoiWithRadius(SCIP *, const GRAPH *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: graph_vnoi.c:774
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
Definition: heur_tm.h:48
SCIP_RETCODE SCIPStpFixEdgeVarTo0(SCIP *scip, SCIP_VAR *edgevar, SCIP_Bool *success)
Definition: prop_stp.c:2419
SCIP_RETCODE graph_get4nextTTerms(SCIP *, GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: graph_tpath.c:1601
void graph_path_execX(SCIP *, const GRAPH *, int, const SCIP_Real *, SCIP_Real *, int *)
Definition: graph_path.c:905
miscellaneous methods used for solving Steiner problems
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
void SCIPStpHeurTMCompStarts(GRAPH *graph, int *starts, int *runs)
Definition: heur_tm.c:2879
SCIP_RETCODE reduce_boundHopR(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, int *heap, int *state, int *vbase, int *nelims, int *pathedge)
Definition: reduce_bnd.c:1518
SCIP_RETCODE reduce_boundMw(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *offset, int *heap, int *state, int *vbase, int *result, int *nelims)
Definition: reduce_bnd.c:1058
void SCIPsortReal(SCIP_Real *realarray, int len)
SCIP_RETCODE graph_knot_delPseudo(SCIP *, GRAPH *, const SCIP_Real *, const SCIP_Real *, const SCIP_Real *, int, REDCOST *, SCIP_Bool *)
Definition: graph_delpseudo.c:1015
Definition: type_retcode.h:33
SCIP_Real graph_pc_solGetObj(SCIP *, const GRAPH *, const int *, SCIP_Real)
Definition: graph_pcbase.c:2603
SCIP_Real solstp_getObjBounded(const GRAPH *g, const int *soledge, SCIP_Real offset, int nedges)
Definition: solstp.c:1833
propagator for Steiner tree problems, using the LP reduced costs
SCIP_RETCODE reduce_boundHopRc(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *pathdist, SCIP_Real objval, int *heap, int *state, int *vbase, int *nelims, int *pathedge, SCIP_Bool fix)
Definition: reduce_bnd.c:1646
void graph_getEdgeCosts(const GRAPH *, SCIP_Real *RESTRICT, SCIP_Real *RESTRICT)
void graph_voronoiMw(SCIP *, const GRAPH *, const SCIP_Real *, PATH *, int *, int *, int *)
Definition: graph_vnoi.c:517
SCIP_RETCODE reduce_boundPruneHeur(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
Definition: reduce_bnd.c:1237
static SCIP_RETCODE computeSteinerTree(SCIP *scip, GRAPH *graph, SCIP_Real *cost, SCIP_Real *costrev, int *result, STP_Bool *stnode, SCIP_Real *upperbound, SCIP_Bool *success)
Definition: reduce_bnd.c:51
static SCIP_RETCODE boundPruneHeur(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
Definition: reduce_bnd.c:149
static SCIP_RETCODE boundPruneHeurMw(SCIP *scip, GRAPH *graph, PATH *vnoi, SCIP_Real *cost, SCIP_Real *radius, SCIP_Real *costrev, SCIP_Real *offset, int *heap, int *state, int *vbase, const int *solnode, const int *soledge, int *nelims, int minelims)
Definition: reduce_bnd.c:487
SCIP_RETCODE reduce_unconnectedForDirected(SCIP *, GRAPH *)
Definition: reduce_simple.c:1134
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1257
int graph_pc_deleteTerm(SCIP *, GRAPH *, int, SCIP_Real *)
Definition: graph_pcbase.c:2235
void graph_add2ndTermPaths(const GRAPH *, const SCIP_Real *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1482
shortest paths based primal heuristics for Steiner problems
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
void graph_add1stTermPaths(const GRAPH *, const SCIP_Real *, PATH *, int *, int *)
Definition: graph_tpath.c:1464
Definition: objbenders.h:33
includes various reduction methods for Steiner tree problems
void graph_voronoiWithRadiusMw(SCIP *, const GRAPH *, PATH *, const SCIP_Real *, SCIP_Real *, int *, int *, int *)
Definition: graph_vnoi.c:973