Detailed Description
dual-ascent and reduction based primal heuristic for Steiner problems
This file implements a dual-ascent and reduction 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_slackprune.h.
Go to the source code of this file.
Functions | |
SCIP_RETCODE | SCIPStpIncludeHeurSlackPrune (SCIP *scip) |
SCIP_RETCODE | SCIPStpHeurSlackPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool reducegraph, SCIP_Bool fullreduce) |
SCIP_RETCODE | SCIPStpHeurSlackPruneRunPcMw (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success) |
Function Documentation
◆ SCIPStpIncludeHeurSlackPrune()
SCIP_RETCODE SCIPStpIncludeHeurSlackPrune | ( | SCIP * | scip | ) |
creates the slack prune primal heuristic and includes it in SCIP
creates the slackprune primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 1129 of file heur_slackprune.c.
References DEFAULT_SLACKPRUNE_MAXFREQ, 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(), and SCIP_DECL_HEURCOPY().
◆ SCIPStpHeurSlackPruneRun()
SCIP_RETCODE SCIPStpHeurSlackPruneRun | ( | SCIP * | scip, |
SCIP_VAR ** | vars, | ||
GRAPH * | g, | ||
int * | soledge, | ||
SCIP_Bool * | success, | ||
SCIP_Bool | reducegraph, | ||
SCIP_Bool | fullreduce | ||
) |
execute slack-and-prune heuristic on given graph
- Parameters
-
scip SCIP data structure vars problem variables or NULL g graph data structure soledge array to 1. provide and 2. return primal solution success feasible solution found? reducegraph try to reduce graph initially? fullreduce use full reduction techniques?
Definition at line 524 of file heur_slackprune.c.
References BMScopyMemoryArray, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, getRedBound(), GRAPH::grad, graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, GRAPH::knots, level0(), nnodes, nterms, NULL, redLoopStp(), reduce_daSlackPrune(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPisLE(), SCIPprobdataGetOffset(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, GRAPH::source, STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIPStpHeurSlackPruneRunPcMw()
SCIP_RETCODE SCIPStpHeurSlackPruneRunPcMw | ( | SCIP * | scip, |
SCIP_VAR ** | vars, | ||
GRAPH * | g, | ||
int * | soledge, | ||
SCIP_Bool * | success | ||
) |
execute MWCSP slack-and-prune heuristic on given graph
execute slack-and-prune heuristic on given graph
- Parameters
-
scip SCIP data structure vars problem variables or NULL g graph data structure soledge array to 1. provide and 2. return primal solution success feasible solution found?
Definition at line 802 of file heur_slackprune.c.
References GRAPH::ancestors, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::fixedges, getRedBound(), GRAPH::grad, graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_setNodeList(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, redLoopMw(), reduce_daSlackPruneMw(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPisLT(), SCIPprobdataGetOffset(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurTMPrunePc(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and updateSolNodeArray().