Detailed Description
shortest paths based primal heuristics for Steiner problems
This file implements several shortest paths based primal heuristics for Steiner problems, see "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano
Definition in file heur_tm.h.
Go to the source code of this file.
Macros | |
#define | DEFAULT_HOPFACTOR 0.33 |
Functions | |
void | SCIPStpHeurTMCompStarts (GRAPH *graph, int *starts, int *runs) |
SCIP_RETCODE | SCIPStpIncludeHeurTM (SCIP *scip) |
SCIP_RETCODE | SCIPStpHeurTMRun (SCIP *scip, SCIP_HEURDATA *heurdata, GRAPH *graph, int *starts, int *bestnewstart, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Real maxcost, SCIP_Bool *success, SCIP_Bool pcmwfull) |
SCIP_RETCODE | SCIPStpHeurTMRunLP (SCIP *scip, GRAPH *graph, SCIP_HEUR *heur, int *result, int runs, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Bool *success) |
SCIP_RETCODE | SCIPStpHeurTMPrune (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *connected) |
SCIP_RETCODE | SCIPStpHeurTMPrunePc (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected) |
SCIP_RETCODE | SCIPStpHeurTMBuildTreePcMw (SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected) |
SCIP_RETCODE | SCIPStpHeurTMBuildTree (SCIP *scip, const GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected) |
SCIP_RETCODE | SCIPStpHeurTMBuildTreeDc (SCIP *scip, const GRAPH *g, int *result, STP_Bool *connected) |
Macro Definition Documentation
◆ DEFAULT_HOPFACTOR
#define DEFAULT_HOPFACTOR 0.33 |
Definition at line 37 of file heur_tm.h.
Referenced by reduce_bound(), reduce_boundHopRc(), reduce_daSlackPruneMw(), and SCIPStpIncludeHeurTM().
Function Documentation
◆ SCIPStpHeurTMCompStarts()
void SCIPStpHeurTMCompStarts | ( | GRAPH * | graph, |
int * | starts, | ||
int * | runs | ||
) |
compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics
- Parameters
-
graph graph data structure starts starting points array runs pointer to number of runs
Definition at line 114 of file heur_tm.c.
References Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, r, GRAPH::source, GRAPH::term, and GRAPH::terms.
Referenced by computeNewSols(), reduce_bound(), and reduce_da().
◆ SCIPStpIncludeHeurTM()
SCIP_RETCODE SCIPStpIncludeHeurTM | ( | SCIP * | scip | ) |
creates the TM primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 2832 of file heur_tm.c.
References DEFAULT_DURINGLPFREQ, DEFAULT_EVALRUNS, DEFAULT_HOPFACTOR, DEFAULT_INITRUNS, DEFAULT_LEAFRUNS, DEFAULT_RANDSEED, DEFAULT_ROOTRUNS, DEFAULT_TYPE, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_HEURTIMING_AFTERLPLOOP, SCIP_HEURTIMING_AFTERNODE, SCIP_HEURTIMING_AFTERPSEUDONODE, SCIP_HEURTIMING_BEFORENODE, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddIntParam(), SCIPallocMemory, SCIPcreateRandom(), SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurFree(), SCIPsetHeurInit(), SCIPsnprintf(), and TRUE.
Referenced by runShell(), and SCIP_DECL_HEURCOPY().
◆ SCIPStpHeurTMRun()
SCIP_RETCODE SCIPStpHeurTMRun | ( | SCIP * | scip, |
SCIP_HEURDATA * | heurdata, | ||
GRAPH * | graph, | ||
int * | starts, | ||
int * | bestnewstart, | ||
int * | best_result, | ||
int | runs, | ||
int | bestincstart, | ||
SCIP_Real * | cost, | ||
SCIP_Real * | costrev, | ||
SCIP_Real * | hopfactor, | ||
SCIP_Real * | nodepriority, | ||
SCIP_Real | maxcost, | ||
SCIP_Bool * | success, | ||
SCIP_Bool | pcmwfull | ||
) |
execute shortest paths heuristic to obtain a Steiner tree
- Parameters
-
scip SCIP data structure heurdata SCIP data structure graph graph data structure starts array containing start vertices (NULL to not provide any) bestnewstart pointer to the start vertex resulting in the best solution best_result array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) runs number of runs bestincstart best incumbent start vertex cost arc costs costrev reversed arc costs hopfactor edge cost multiplicator for HC problems nodepriority vertex priorities for vertices to be starting points (NULL for no priorities) maxcost maximal edge cost (only for HC) success pointer to store whether a solution could be found pcmwfull use full computation of tree (i.e. connect all terminals and prune), only for prize-collecting variants
Definition at line 1649 of file heur_tm.c.
References AUTO, BLOCKED, BMSclearMemoryArray, BMScopyMemoryArray, computeDegConsTree(), computeSteinerTree(), computeSteinerTreeDijk(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), computeSteinerTreeVnoi(), CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, fabs(), FALSE, FARAWAY, flipedge, GNODECmpByDist(), GRAPH::grad, graph_path_execX(), graph_pc_2transcheck(), GRAPH::head, GRAPH::hoplimit, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, r, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebugMessage, SCIPfindHeur(), SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisStopped(), SCIPpqueueCreate(), SCIPpqueueFree(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPrandomPermuteIntArray(), SCIPsortRealInt(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_SAP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TM_DIJKSTRA, TM_SP, TM_VORONOI, TRUE, and UNKNOWN.
Referenced by computeNewSols(), reduce_bound(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), and SCIPStpHeurTMRunLP().
◆ SCIPStpHeurTMRunLP()
SCIP_RETCODE SCIPStpHeurTMRunLP | ( | SCIP * | scip, |
GRAPH * | graph, | ||
SCIP_HEUR * | heur, | ||
int * | result, | ||
int | runs, | ||
SCIP_Real * | cost, | ||
SCIP_Real * | costrev, | ||
SCIP_Bool * | success | ||
) |
run shortest path heuristic, but bias edge costs towards best current LP solution
- Parameters
-
scip SCIP data structure graph graph data structure heur heuristic or NULL result array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN) runs number of runs cost arc costs (uninitialized) costrev reversed arc costs (uninitialized) success pointer to store whether a solution could be found
Definition at line 2352 of file heur_tm.c.
References BLOCKED, BMScopyMemoryArray, GRAPH::cost, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::maxdeg, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPepsilon(), SCIPfindHeur(), SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPisGE(), SCIPisGT(), SCIPisLT(), SCIPisZero(), SCIPlinkLPSol(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPStpHeurTMRun(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), GRAPH::source, STP_DCSTP, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.
Referenced by SCIP_DECL_HEUREXEC(), and selectBranchingVertexBySol().
◆ SCIPStpHeurTMPrune()
SCIP_RETCODE SCIPStpHeurTMPrune | ( | SCIP * | scip, |
const GRAPH * | g, | ||
const SCIP_Real * | cost, | ||
int | layer, | ||
int * | result, | ||
STP_Bool * | connected | ||
) |
prune a Steiner tree in such a way that all leaves are terminals
- Parameters
-
scip SCIP data structure g graph structure cost edge costs layer layer (usually 0) result ST edges, which need to be set to UNKNOWN connected ST nodes
Definition at line 555 of file heur_tm.c.
References EAT_LAST, shortest_path::edge, FALSE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.
Referenced by graph_sol_getOrg(), prune(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), and SCIPStpHeurRecRun().
◆ SCIPStpHeurTMPrunePc()
SCIP_RETCODE SCIPStpHeurTMPrunePc | ( | SCIP * | scip, |
const GRAPH * | g, | ||
const SCIP_Real * | cost, | ||
int * | result, | ||
STP_Bool * | connected | ||
) |
prune the (rooted) prize collecting Steiner tree in such a way that all leaves are terminals
- Parameters
-
scip SCIP data structure g graph structure cost edge costs result ST edges connected ST nodes
Definition at line 167 of file heur_tm.c.
References a, CONNECT, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, graph_path_exec(), graph_sol_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.
Referenced by graph_sol_getOrg(), prune(), reduce_daSlackPruneMw(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), and SCIPStpHeurSlackPruneRunPcMw().
◆ SCIPStpHeurTMBuildTreePcMw()
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw | ( | SCIP * | scip, |
const GRAPH * | g, | ||
PATH * | mst, | ||
const SCIP_Real * | cost, | ||
SCIP_Real * | objresult, | ||
int * | connected | ||
) |
build (rooted) prize collecting Steiner tree in such a way that all leaves are positive-weight vertices
build (rooted) prize collecting Steiner tree in such a way that all leaves are terminals
- Parameters
-
scip SCIP data structure g graph structure mst path data structure array cost edge costs objresult pointer to store objective value of result connected CONNECT/UNKNOWN
Definition at line 382 of file heur_tm.c.
References a, CONNECT, EAT_LAST, shortest_path::edge, FALSE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_OKAY, SCIP_Real, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.
Referenced by SCIPStpHeurPruneUpdateSols().
◆ SCIPStpHeurTMBuildTree()
SCIP_RETCODE SCIPStpHeurTMBuildTree | ( | SCIP * | scip, |
const GRAPH * | g, | ||
PATH * | mst, | ||
const SCIP_Real * | cost, | ||
SCIP_Real * | objresult, | ||
int * | connected | ||
) |
build Steiner tree in such a way that all leaves are terminals
- Parameters
-
scip SCIP data structure g graph structure mst path data structure array cost edge costs objresult pointer to store objective value of result connected CONNECT/UNKNOWN
Definition at line 653 of file heur_tm.c.
References CONNECT, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, graph_path_exec(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, GRAPH::source, GRAPH::term, and UNKNOWN.
Referenced by SCIPStpHeurPruneUpdateSols().
◆ SCIPStpHeurTMBuildTreeDc()
SCIP_RETCODE SCIPStpHeurTMBuildTreeDc | ( | SCIP * | scip, |
const GRAPH * | g, | ||
int * | result, | ||
STP_Bool * | connected | ||
) |
prune a degree constrained Steiner tree in such a way that all leaves are terminals
- Parameters
-
scip SCIP data structure g graph structure result ST edges connected ST nodes (to be set)
Definition at line 732 of file heur_tm.c.
References CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.
Referenced by computeDegConsTree(), and SCIPStpHeurRecRun().