Detailed Description
reduction-based primal heuristic for Steiner problems
This file implements a reducion based heuristic for Steiner problems. It is based on an approach described in T. Polzin's "Algorithms for the Steiner problem in networks".
Definition in file heur_prune.h.
Go to the source code of this file.
Functions | |
SCIP_RETCODE | SCIPStpHeurPruneUpdateSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, int *solnode, int *soledge, int *globalsoledge, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success) |
SCIP_RETCODE | SCIPStpIncludeHeurPrune (SCIP *scip) |
SCIP_RETCODE | SCIPStpHeurPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph) |
Function Documentation
◆ SCIPStpHeurPruneUpdateSols()
SCIP_RETCODE SCIPStpHeurPruneUpdateSols | ( | SCIP * | scip, |
GRAPH * | g, | ||
GRAPH * | prunegraph, | ||
int * | solnode, | ||
int * | soledge, | ||
int * | globalsoledge, | ||
SCIP_Real * | globalobj, | ||
SCIP_Bool | incumbentgiven, | ||
SCIP_Bool * | success | ||
) |
updates solutions for pruned graph
- Parameters
-
scip SCIP data structure g graph data structure prunegraph pruned graph data structure solnode array for best solution nodes wrt prunegraph soledge array for best solution edges wrt prunegraph globalsoledge array storing best solution wrt g globalobj pointer to objective value of best solution wrt g incumbentgiven incumbent solution for pruned graph given? success pointer to store whether a solution could be found
Definition at line 489 of file heur_prune.c.
References BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, graph_mark(), GRAPH::knots, LT, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisEQ(), SCIPisLE(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), setNodeSolArray(), solstp_getObjBounded(), solstp_getOrg(), solstp_isValid(), STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, TRUE, and UNKNOWN.
Referenced by computeNewSols(), SCIPStpHeurSlackPruneRun(), and updateSolution().
◆ SCIPStpIncludeHeurPrune()
SCIP_RETCODE SCIPStpIncludeHeurPrune | ( | SCIP * | scip | ) |
creates the prune primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 951 of file heur_prune.c.
References DEFAULT_PRUNE_MAXFRQ, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and SCIPsetHeurInitsol().
Referenced by runShell(), SCIP_DECL_HEURCOPY(), and subscipSetupCallbacks().
◆ SCIPStpHeurPruneRun()
SCIP_RETCODE SCIPStpHeurPruneRun | ( | SCIP * | scip, |
SCIP_VAR ** | vars, | ||
GRAPH * | g, | ||
int * | soledge, | ||
SCIP_Bool * | success, | ||
const SCIP_Bool | withinitialsol, | ||
const SCIP_Bool | reducegraph | ||
) |
execute prune heuristic on given graph
- Parameters
-
scip SCIP data structure vars problem variables or NULL (need to be provided whenever available) g the graph soledge array to store primal solution (if no solution is provided, withinitialsol must be set to FALSE) success feasible solution found? withinitialsol solution given? reducegraph try to reduce graph initially?
Definition at line 599 of file heur_prune.c.
References BMScopyMemoryArray, computeNewSols(), CONNECT, bidecomposition_reduction_parameters::depth, reduction_parameters::dualascent, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, getRedBound(), graph_copy(), graph_edge_del(), graph_free(), graph_get_nVET(), graph_initHistory(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, PRUNE_MAXREDROUNDS, PRUNE_MINREDELIMS, reduction_base::redparameters, reduce_boundPruneHeur(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_redLoopStp(), reduce_solAddNodesol(), reduce_solFree(), reduce_solGetNodesol(), reduce_solGetOffset(), reduce_solInit(), reduce_unconnected(), reduce_unconnectedRpcRmw(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPvarGetUbLocal(), setMinMaxElims(), setNodeSolArray(), solstp_getObjBounded(), solstp_isValid(), STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, UNKNOWN, and GRAPH::withInexactReductions.
Referenced by redcostGraphComputeSteinerTree(), and SCIP_DECL_HEUREXEC().