reduce.c
Go to the documentation of this file.
23 * This file includes several packages of reduction techniques for different Steiner problem variants.
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
114 SCIP_CALL( reduce_nvAdv(scip, g, vnoi, nodearrreal, fixed, edgearrint, heap, state, vbase, neighb, distnode, solnode, &nvelims) );
120 SCIP_CALL( reduce_sl(scip, g, vnoi, fixed, heap, state, vbase, neighb, visited, solnode, &slelims) );
307 SCIP_CALL( redLoopStp(scip, g, vnoi, path, gnodearr, nodearrreal, edgearrreal, edgearrreal2, heap, state,
308 vbase, nodearrint, edgearrint, nodearrint2, NULL, nodearrchar, fixed, -1.0, dualascent, bred, nodereplacing, reductbound, userec, (dualascent && userec)) );
430 SCIP_CALL( redLoopPc(scip, g, vnoi, path, gnodearr, nodearrreal, exedgearrreal, exedgearrreal2, heap, state,
431 vbase, nodearrint, edgearrint, nodearrint2, NULL, nodearrchar, fixed, dualascent, bred, reductbound, userec) );
542 SCIP_CALL( redLoopMw(scip, g, vnoi, path, gnodearr, nodearrreal, edgearrreal, edgearrreal2, state,
543 vbase, nodearrint, edgearrint, nodearrint2, nodearrint3, NULL, nodearrchar, fixed, advanced, bred, advanced, redbound, userec) );
643 SCIP_CALL( reduce_boundHopR(scip, g, vnoi, cost, costrev, radius, heap, state, vbase, &hcrnelims, pathedge) );
650 SCIP_CALL( reduce_boundHopRc(scip, g, vnoi, cost, costrev, radius, -1.0, heap, state, vbase, &hcrcnelims, pathedge, FALSE) );
657 SCIP_CALL( reduce_bound(scip, g, vnoi, cost, NULL, radius, costrev, fixed, &upperbound, heap, state, vbase, &brednelims) );
667 SCIP_CALL( reduce_boundHop(scip, g, vnoi, cost, radius, costrev, heap, state, vbase, &hbrednelims) );
775 SCIP_CALL( reduce_sdspSap(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdnelims, 300) );
791 SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, fixed, edgearrint, vbase, state, heap, nodearrint,
893 SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, fixed, edgearrint, vbase, state, heap, nodearrint,
938 int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
943 STP_Bool tryrmw, /**< try to convert problem to RMWCSP? Only possible if advanced = TRUE and userec = TRUE */
1032 SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, vbase, nodearrint, edgearrint,
1033 state, nodearrchar, &daelims, TRUE, FALSE, FALSE, userec, (rounds == 0), randnumgen, prizesum) );
1055 SCIP_CALL(reduce_chain2(scip, g, vnoi, path, state, vbase, nodearrint, nodearrint2, nodearrint3, &chain2elims, 500));
1068 SCIP_CALL(reduce_npv(scip, g, vnoi, path, state, vbase, nodearrint, nodearrint2, nodearrint3, &npvelims, 400));
1078 SCIP_CALL(reduce_chain2(scip, g, vnoi, path, state, vbase, nodearrint, nodearrint2, nodearrint3, &chain2elims, 300));
1102 SCIP_CALL( reduce_boundMw(scip, g, vnoi, path, edgearrreal, nodearrreal, edgearrreal2, fixed, nodearrint, state, vbase, NULL, &bredelims) );
1111 if( anselims + nnpelims + chain2elims + bredelims + npvelims + ansadelims + ansad2elims + daelims <= redbound )
1120 SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, vbase, nodearrint, edgearrint,
1121 state, nodearrchar, &daelims, TRUE, (g->terms > STP_RED_MWTERMBOUND), tryrmw, userec, FALSE, randnumgen, prizesum) );
1180 int reductbound, /**< minimal number of edges to be eliminated in order to reiterate reductions */
1252 SCIP_CALL( reduce_sdPc(scip, g, vnoi, heap, state, vbase, nodearrint, nodearrint2, &sdnelims) );
1264 SCIP_CALL( reduce_sdsp(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdcnelims,
1281 SCIP_CALL( reduce_bd34(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &bd3nelims, STP_RED_BD3BOUND) );
1288 SCIP_CALL( reduce_sdPc(scip, g, vnoi, heap, state, vbase, nodearrint, nodearrint2, &sdnelims) );
1289 SCIP_CALL( reduce_sdsp(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdcnelims, ((rounds > 0) ? STP_RED_SDSPBOUND2 : STP_RED_SDSPBOUND), NULL) );
1299 SCIP_CALL( nvreduce_sl(scip, g, vnoi, nodearrreal, &fix, edgearrint, heap, state, vbase, nodearrint, nodearrint2, solnode, nodearrchar, &nvslnelims, reductbound) );
1312 SCIP_CALL( reduce_bound(scip, g, vnoi, exedgearrreal, g->prize, nodearrreal, exedgearrreal2, &fix, &ub, heap, state, vbase, &brednelims) );
1330 SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap,
1333 SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, vbase, heap, edgearrint,
1334 state, nodearrchar, &danelims, TRUE, FALSE, FALSE, userec, (rounds == 0), randnumgen, prizesum) );
1346 SCIP_CALL( reduce_bound(scip, g, vnoi, exedgearrreal, g->prize, nodearrreal, exedgearrreal2, &fix, &ub, heap, state, vbase, &brednelims) );
1355 if( degnelims + sdnelims + sdcnelims + bd3nelims + danelims + brednelims + nvslnelims <= reductbound )
1366 SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap,
1371 SCIP_CALL( reduce_daPcMw(scip, g, vnoi, gnodearr, exedgearrreal, exedgearrreal2, nodearrreal, vbase, heap, edgearrint,
1433 int reductbound, /**< minimal number of edges to be eliminated in order to reiterate reductions */
1509 reduce_sd(scip, g, vnoi, edgearrreal, nodearrreal, heap, state, vbase, nodearrint, nodearrint2, edgearrint, &sdnelims,
1525 reduce_sdsp(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &sdcnelims, ((inner_rounds > 0) ? (STP_RED_SDSPBOUND2 / 2) : (STP_RED_SDSPBOUND / 2)), NULL));
1542 SCIP_CALL(reduce_bd34(scip, g, vnoi, path, heap, state, vbase, nodearrint, nodearrint2, &bd3nelims, STP_RED_BD3BOUND));
1558 nvreduce_sl(scip, g, vnoi, nodearrreal, &fix, edgearrint, heap, state, vbase, nodearrint, NULL, solnode, nodearrchar, &nvslnelims, reductbound));
1575 reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap, nodearrint,
1590 SCIP_CALL(reduce_bound(scip, g, vnoi, edgearrreal, NULL, nodearrreal, edgearrreal2, &fix, &ub, heap, state, vbase, &brednelims));
1606 if( (danelims + sdnelims + bd3nelims + nvslnelims + lenelims + brednelims + sdcnelims) <= 2 * reductbound )
1627 if( extensive && (danelims + sdnelims + bd3nelims + nvslnelims + lenelims + brednelims + sdcnelims) > 0 )
1639 SCIP_CALL( reduce_da(scip, g, vnoi, gnodearr, edgearrreal, edgearrreal2, nodearrreal, &ub, &fix, edgearrint, vbase, state, heap, nodearrint,
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
static SCIP_RETCODE reducePc(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, STP_Bool dualascent, SCIP_Bool userec)
Definition: reduce.c:338
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
Definition: struct_scip.h:59
SCIP_RETCODE reduce_rpt(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_simple.c:884
SCIP_RETCODE reduceStp(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, SCIP_Bool dualascent, SCIP_Bool nodereplacing, SCIP_Bool userec)
Definition: reduce.c:223
SCIP_RETCODE reduce_boundMw(SCIP *, GRAPH *, PATH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5243
SCIP_RETCODE reduce_contractZeroEdges(SCIP *, GRAPH *, SCIP_Bool)
Definition: reduce_simple.c:453
Problem data for stp problem.
SCIP_RETCODE reduce_boundHopRc(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real, int *, int *, int *, int *, int *, SCIP_Bool)
Definition: reduce_bnd.c:6226
Definition: struct_misc.h:259
Definition: grph.h:143
SCIP_RETCODE redLoopMw(SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *edgearrreal, SCIP_Real *edgearrreal2, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *nodearrint3, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, STP_Bool advanced, STP_Bool bred, STP_Bool tryrmw, int redbound, SCIP_Bool userec)
Definition: reduce.c:923
static SCIP_RETCODE nvreduce_sl(SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *nodearrreal, SCIP_Real *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *neighb, int *distnode, int *solnode, STP_Bool *visited, int *nelims, int minelims)
Definition: reduce.c:72
static SCIP_RETCODE reduceNw(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
Definition: reduce.c:826
SCIP_RETCODE reduce_daPcMw(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, STP_Bool *, int *, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_Bool, SCIP_RANDNUMGEN *, SCIP_Real)
Definition: reduce_bnd.c:3801
SCIP_RETCODE reduce_simple(SCIP *, GRAPH *, SCIP_Real *, int *, int *, int *)
Definition: reduce_simple.c:489
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIP_Bool graph_pc_term2edgeConsistent(const GRAPH *)
Definition: grphbase.c:853
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE reduce_boundHopR(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *)
Definition: reduce_bnd.c:6098
static SCIP_RETCODE reduceHc(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
Definition: reduce.c:571
SCIP_RETCODE reduce_simple_mw(SCIP *, GRAPH *, int *, SCIP_Real *, int *)
Definition: reduce_simple.c:953
miscellaneous methods used for solving Steiner problems
SCIP_RETCODE reduce_deleteConflictEdges(SCIP *, GRAPH *)
Definition: reduce_bnd.c:2421
SCIP_RETCODE reduce_sd(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, int *, SCIP_Bool, int *)
Definition: reduce_alt.c:1105
SCIP_RETCODE reduce_da(SCIP *, GRAPH *, PATH *, GNODE **, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *, int *, int *, STP_Bool *, int *, int, SCIP_RANDNUMGEN *, SCIP_Bool, SCIP_Bool)
Definition: reduce_bnd.c:2861
SCIP_RETCODE redLoopPc(SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *exedgearrreal, SCIP_Real *exedgearrreal2, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_Bool dualascent, SCIP_Bool bred, int reductbound, SCIP_Bool userec)
Definition: reduce.c:1160
SCIP_RETCODE reduce_simple_sap(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_simple.c:684
void print(const Container &container, const std::string &prefix="", const std::string &suffix="", std::ostream &os=std::cout, bool negate=false, int prec=6)
Definition: global_functions.h:95
Definition: type_retcode.h:33
SCIP_RETCODE reduce_bd34(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2964
SCIP_RETCODE reduce_nvAdv(SCIP *, GRAPH *, PATH *, SCIP_Real *, double *, int *, int *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:3903
SCIP_Real graph_pc_getPosPrizeSum(SCIP *, const GRAPH *)
Definition: grphbase.c:1054
SCIP_RETCODE reduce_simple_hc(SCIP *, GRAPH *, SCIP_Real *, int *)
Definition: reduce_simple.c:1252
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
propagator for Steiner tree problems, using the LP reduced costs
void reduce_ansAdv(SCIP *, GRAPH *, int *, int *, SCIP_Bool)
Definition: reduce_alt.c:4515
SCIP_RETCODE reduce(SCIP *scip, GRAPH **graph, SCIP_Real *offset, int level, int minelims, SCIP_Bool userec)
Definition: reduce.c:1675
SCIP_RETCODE reduce_simple_pc(SCIP *, GRAPH *, SCIP_Real *, int *, int *, SCIP_Bool)
Definition: reduce_simple.c:1330
SCIP_RETCODE reduce_boundHop(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:5904
static SCIP_RETCODE reduceSap(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims)
Definition: reduce.c:691
SCIP_RETCODE reduce_sl(SCIP *, GRAPH *, PATH *, double *, int *, int *, int *, int *, STP_Bool *, int *, int *)
Definition: reduce_alt.c:3483
SCIP_RETCODE reduce_ledge(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:4143
SCIP_RETCODE reduce_sdPc(SCIP *, GRAPH *, PATH *, int *, int *, int *, int *, int *, int *)
Definition: reduce_alt.c:1499
SCIP_RETCODE redLoopStp(SCIP *scip, GRAPH *g, PATH *vnoi, PATH *path, GNODE **gnodearr, SCIP_Real *nodearrreal, SCIP_Real *edgearrreal, SCIP_Real *edgearrreal2, int *heap, int *state, int *vbase, int *nodearrint, int *edgearrint, int *nodearrint2, int *solnode, STP_Bool *nodearrchar, SCIP_Real *fixed, SCIP_Real upperbound, SCIP_Bool dualascent, SCIP_Bool boundreduce, SCIP_Bool nodereplacing, int reductbound, SCIP_Bool userec, SCIP_Bool fullreduce)
Definition: reduce.c:1411
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE reduce_bound(SCIP *, GRAPH *, PATH *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, SCIP_Real *, int *, int *, int *, int *)
Definition: reduce_bnd.c:4653
Definition: misc_stp.h:41
SCIP_RETCODE reduce_sdspSap(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:2308
static SCIP_RETCODE reduceMw(SCIP *scip, GRAPH **graph, SCIP_Real *fixed, int minelims, STP_Bool advanced, SCIP_Bool userec)
Definition: reduce.c:459
shortest paths based primal heuristics for Steiner problems
static void reduceStatsPrint(SCIP_Bool print, const char *method, int nelims)
Definition: reduce.c:55
Definition: objbenders.h:33
SCIP_RETCODE reduce_npv(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5024
SCIP_RETCODE reduce_sdsp(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int, int *)
Definition: reduce_alt.c:2459
SCIP callable library.
SCIP_RETCODE reduce_chain2(SCIP *, GRAPH *, PATH *, PATH *, int *, int *, int *, int *, int *, int *, int)
Definition: reduce_alt.c:5367