reduce_pcsimple.c
Go to the documentation of this file.
20 * This file implements basic reduction techniques for prize-collecting Steiner tree and maximum-weight connected subgraph.
21 * Mosts tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
138 if( !Is_term(g->term[tail]) && !Is_term(g->term[head]) && g->grad[head] == 2 && g->grad[tail] == 2 )
178 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), graph_edge_getAncestors(g, e), NULL) );
199 SCIP_CALL( SCIPintListNodeAppendCopy(scip, &(ancestors), graph_edge_getAncestors(g, e), NULL) );
295 int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
348 int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
464 int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
574 SCIPdebugMessage("degree-1 contraction: %d->%d new weight of %d: %f \n", i1, i, i, g->prize[i]);
588 /* we also need to adapt the outgoing arcs because the contraction might have destroyed something */
969 if( SCIPisLE(scip, g->prize[i], g->cost[edges2[0]]) && SCIPisLE(scip, g->prize[i], g->cost[edges2[1]]) )
1002 else if( SCIPisLE(scip, g->prize[i], g->cost[edges2[0]]) || SCIPisLE(scip, g->prize[i], g->cost[edges2[1]]) )
1110 int* solnode, /**< array to indicate whether a node is part of the current solution (==CONNECT) */
1190 SCIPdebugMessage("delete degree 0 term %d prize: %f count:%d\n ", i, g->prize[i], nelims_local);
1336 SCIP_CALL( pcReduceTermDeg1(scip, edgestate, g, fixed, solnode, countnew, i, &rerun, &maxprize) );
1341 SCIP_CALL( pcReduceTermDeg2(scip, edgestate, g, fixed, solnode, countnew, i, &rerun, &maxprize) );
1347 SCIP_CALL( pcContractWithAdjacentTerm(scip, edgestate, g, fixed, solnode, countnew, i, &rerun) );
1395 if( g->grad[k] == 0 && graph_pc_knotIsNonLeafTerm(g, k) && !isMaxprizeTerm(scip, g, k, &maxprize) )
1403 /* remove unconnected vertices, including pseudo terminals, and checks for feasibility (adapts g->mark) */
Definition: misc_stp.h:88
SCIP_RETCODE graph_singletonAncestors_init(SCIP *, const GRAPH *, int, SINGLETONANS *)
Definition: graph_history.c:684
static SCIP_RETCODE mwContractTerminalsChainWise(SCIP *scip, GRAPH *g, SCIP_Real *offset, int *solnode, int *nelims)
Definition: reduce_pcsimple.c:344
int graph_pc_realDegree(const GRAPH *, int, SCIP_Bool)
Definition: graph_pcbase.c:2112
SCIP_RETCODE graph_pc_contractNodeAncestors(SCIP *, GRAPH *, int, int, int)
Definition: graph_pcbase.c:2352
static SCIP_RETCODE pcReduceTermDeg2(SCIP *scip, const int *edgestate, GRAPH *g, SCIP_Real *offset, int *solnode, int *nelims, int i, SCIP_Bool *rerun, SCIP_Real *maxprize)
Definition: reduce_pcsimple.c:936
Definition: graphdefs.h:184
Definition: struct_scip.h:59
static SCIP_RETCODE pcReduceTermDeg1(SCIP *scip, const int *edgestate, GRAPH *g, SCIP_Real *offset, int *solnode, int *nelims, int i, SCIP_Bool *rerun, SCIP_Real *maxprize)
Definition: reduce_pcsimple.c:862
static SCIP_RETCODE pcContractWithAdjacentTerm(SCIP *scip, const int *edgestate, GRAPH *g, SCIP_Real *offset, int *solnode, int *nelims, int i, SCIP_Bool *rerun)
Definition: reduce_pcsimple.c:1038
void reduce_identifyNonLeafTerms(SCIP *, GRAPH *)
Definition: reduce_simple.c:1052
static SCIP_RETCODE mwContract0WeightVertices(SCIP *scip, GRAPH *g, int *solnode, int *nelims)
Definition: reduce_pcsimple.c:292
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
includes various files containing graph methods used for Steiner tree problems
int graph_edge_redirect(SCIP *, GRAPH *, int, int, int, SCIP_Real, SCIP_Bool, SCIP_Bool)
Definition: graph_edge.c:103
void reduce_removeDeg0NonLeafTerms(SCIP *scip, GRAPH *g, SCIP_Real *offsetp)
Definition: reduce_pcsimple.c:1380
SCIP_RETCODE graph_knot_replaceDeg2(SCIP *, int, SCIP_Real, int, GRAPH *, SCIP_Bool *)
Definition: graph_node.c:158
SCIP_RETCODE graph_knot_contract(SCIP *, GRAPH *, int *, int, int)
Definition: graph_node.c:264
includes enumeration algorithms for Steiner tree problems
SCIP_RETCODE enumeration_findSolPcMw(SCIP *scip, GRAPH *g, int *RESTRICT result)
Definition: enumeration.c:253
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_RETCODE graph_edge_reinsert(SCIP *, GRAPH *, int, int, int, SCIP_Real, int, SINGLETONANS *, SINGLETONANS *, int *, SCIP_Bool *)
Definition: graph_edge.c:200
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1431
static SCIP_Bool hasAdjacentTerminals(const GRAPH *g)
Definition: reduce_pcsimple.c:44
static void pcmwReduceTerm0Prize(SCIP *scip, GRAPH *g, int i)
Definition: reduce_pcsimple.c:709
static SCIP_RETCODE pcmwEnumerationTry(SCIP *scip, GRAPH *g, int *nelims, SCIP_Bool *rerun)
Definition: reduce_pcsimple.c:815
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
static SCIP_RETCODE mwContractTerminalsSimple(SCIP *scip, GRAPH *g, SCIP_Real *offset, int *solnode, int *nelims)
Definition: reduce_pcsimple.c:460
SCIP_RETCODE reduce_simple_pc(SCIP *scip, const int *edgestate, GRAPH *g, SCIP_Real *fixed, int *countnew, int *countall, int *solnode)
Definition: reduce_pcsimple.c:1239
void graph_pc_knotToNonTermProperty(GRAPH *, int)
Definition: graph_pcbase.c:1044
Definition: type_retcode.h:33
SCIP_RETCODE graph_pc_contractEdge(SCIP *, GRAPH *, int *, int, int, int)
Definition: graph_pcbase.c:2385
static SCIP_RETCODE pcReduceKnotDeg2(SCIP *scip, GRAPH *g, int i, int *solnode, SCIP_Bool *rerun)
Definition: reduce_pcsimple.c:681
static SCIP_RETCODE mwContractNonPositiveChain(SCIP *scip, int i, GRAPH *g, int *nelims)
Definition: reduce_pcsimple.c:240
SCIP_RETCODE reduce_unconnectedRpcRmwInfeas(SCIP *scip, GRAPH *g, SCIP_Real *offsetp, SCIP_Bool *infeas)
Definition: reduce_pcsimple.c:1404
Definition: type_retcode.h:34
static SCIP_RETCODE mwTraverseChain(SCIP *scip, GRAPH *g, int *length, int *final, int i, int i1, int i2, int e1)
Definition: reduce_pcsimple.c:149
static void pcmwReduceKnotDeg1(SCIP *scip, GRAPH *g, int i, SCIP_Bool *rerun)
Definition: reduce_pcsimple.c:649
void graph_singletonAncestors_freeMembers(SCIP *, SINGLETONANS *)
Definition: graph_history.c:734
int graph_pc_nProperPotentialTerms(const GRAPH *)
Definition: graph_pcbase.c:2582
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1383
SCIP_RETCODE reduce_simple_mw(SCIP *scip, GRAPH *g, int *solnode, SCIP_Real *fixed, int *nelims)
Definition: reduce_pcsimple.c:1107
Definition: graphdefs.h:173
Portable definitions.
static SCIP_RETCODE mwReduceTermDeg1(SCIP *scip, const int *edgestate, GRAPH *g, SCIP_Real *offset, int *solnode, int *nelims, int i, int iout, SCIP_Bool *rerun, SCIP_Real *maxprize)
Definition: reduce_pcsimple.c:526
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1344
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1257
SCIP_RETCODE graph_pc_contractEdgeUnordered(SCIP *, GRAPH *, int *, int, int)
Definition: graph_pcbase.c:2439
int graph_pc_deleteTerm(SCIP *, GRAPH *, int, SCIP_Real *)
Definition: graph_pcbase.c:2235
static void pcmwDeleteNonSolEdges(SCIP *scip, const int *result, GRAPH *g, int *nelims)
Definition: reduce_pcsimple.c:764
static SCIP_Bool isMaxprizeTerm(SCIP *scip, const GRAPH *g, int i, SCIP_Real *maxprize)
Definition: reduce_pcsimple.c:66
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
SCIP_RETCODE reduce_unconnectedRpcRmw(SCIP *scip, GRAPH *g, SCIP_Real *offsetp)
Definition: reduce_pcsimple.c:1524
Definition: objbenders.h:33
includes various reduction methods for Steiner tree problems
SCIP callable library.
IDX * graph_edge_getAncestors(const GRAPH *, int)
Definition: graph_history.c:1202