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
A list of all interface methods can be found in heur_tm.h
Definition in file heur_tm.c.
#include <assert.h>
#include <string.h>
#include "heur_tm.h"
#include "probdata_stp.h"
#include "portab.h"
#include "scip/misc.h"
#include <math.h>
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "TM" |
#define | HEUR_DESC "shortest path based primal heuristics for Steiner trees" |
#define | HEUR_DISPCHAR '+' |
#define | HEUR_PRIORITY 10000000 |
#define | HEUR_FREQ 1 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE) |
#define | HEUR_USESSUBSCIP FALSE |
#define | DEFAULT_EVALRUNS 25 |
#define | DEFAULT_INITRUNS 100 |
#define | DEFAULT_LEAFRUNS 15 |
#define | DEFAULT_ROOTRUNS 50 |
#define | DEFAULT_DURINGLPFREQ 5 |
#define | DEFAULT_TYPE 0 |
#define | DEFAULT_RANDSEED 5 |
#define | AUTO 0 |
#define | TM_SP 1 |
#define | TM_VORONOI 2 |
#define | TM_DIJKSTRA 3 |
Functions | |
static | SCIP_DECL_PARAMCHGD (paramChgdRandomseed) |
void | SCIPStpHeurTMCompStarts (GRAPH *graph, int *starts, int *runs) |
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 | SCIPStpHeurTMPrune (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int layer, int *result, STP_Bool *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) |
static SCIP_RETCODE | prune (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, int *result, STP_Bool *connected) |
static SCIP_RETCODE | computeSteinerTreeDijk (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *dijkdist, int *result, int *dijkedge, int start, SCIP_RANDNUMGEN *randnumgen, STP_Bool *connected) |
static SCIP_RETCODE | computeSteinerTreeDijkPcMw (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *dijkdist, int *result, int *dijkedge, int start, STP_Bool *connected) |
static SCIP_RETCODE | computeSteinerTreeDijkPcMwFull (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *dijkdist, int *result, int *dijkedge, int start, STP_Bool *connected) |
static SCIP_RETCODE | computeSteinerTree (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real **pathdist, int start, int *perm, int *result, int *cluster, int **pathedge, STP_Bool *connected, SCIP_RANDNUMGEN *randnumgen) |
static SCIP_RETCODE | computeDegConsTree (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real **pathdist, int start, int *perm, int *result, int *cluster, int **pathedge, SCIP_RANDNUMGEN *randnumgen, STP_Bool *connected, STP_Bool *solfound) |
static SCIP_RETCODE | computeSteinerTreeVnoi (SCIP *scip, const GRAPH *g, SCIP_PQUEUE *pqueue, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real **node_dist, int start, int *result, int *vcount, int *nodenterms, int **node_base, int **node_edge, STP_Bool firstrun, STP_Bool *connected) |
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) |
static | SCIP_DECL_HEURCOPY (heurCopyTM) |
static | SCIP_DECL_HEURFREE (heurFreeTM) |
static | SCIP_DECL_HEURINIT (heurInitTM) |
static | SCIP_DECL_HEUREXEC (heurExecTM) |
SCIP_RETCODE | SCIPStpIncludeHeurTM (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "TM" |
Definition at line 39 of file heur_tm.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINIT(), and SCIPStpIncludeHeurTM().
◆ HEUR_DESC
#define HEUR_DESC "shortest path based primal heuristics for Steiner trees" |
Definition at line 40 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR '+' |
Definition at line 41 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY 10000000 |
Definition at line 42 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_FREQ
#define HEUR_FREQ 1 |
Definition at line 43 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 44 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 45 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_TIMING
#define HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE) |
Definition at line 46 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 47 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ DEFAULT_EVALRUNS
#define DEFAULT_EVALRUNS 25 |
◆ DEFAULT_INITRUNS
#define DEFAULT_INITRUNS 100 |
number of initial runs
Definition at line 50 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ DEFAULT_LEAFRUNS
#define DEFAULT_LEAFRUNS 15 |
number of runs at leafs
Definition at line 51 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ DEFAULT_ROOTRUNS
#define DEFAULT_ROOTRUNS 50 |
number of runs at the root
Definition at line 52 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ DEFAULT_DURINGLPFREQ
#define DEFAULT_DURINGLPFREQ 5 |
frequency during LP solving
Definition at line 53 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ DEFAULT_TYPE
#define DEFAULT_TYPE 0 |
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 5 |
seed for pseudo-random functions
Definition at line 55 of file heur_tm.c.
Referenced by SCIPStpIncludeHeurTM().
◆ AUTO
#define AUTO 0 |
Definition at line 57 of file heur_tm.c.
Referenced by SCIPStpHeurTMRun().
◆ TM_SP
#define TM_SP 1 |
Definition at line 58 of file heur_tm.c.
Referenced by SCIPStpHeurTMRun().
◆ TM_VORONOI
#define TM_VORONOI 2 |
Definition at line 59 of file heur_tm.c.
Referenced by SCIPStpHeurTMRun().
◆ TM_DIJKSTRA
#define TM_DIJKSTRA 3 |
Definition at line 60 of file heur_tm.c.
Referenced by SCIPStpHeurTMRun().
Function Documentation
◆ SCIP_DECL_PARAMCHGD()
|
static |
information method for a parameter change of random seed
Definition at line 97 of file heur_tm.c.
References NULL, SCIP_OKAY, SCIPparamGetData(), and SCIPparamGetInt().
◆ 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().
◆ 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 (need to be set to UNKNOWN) 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 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().
◆ 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().
◆ 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().
◆ prune()
|
static |
- Parameters
-
scip SCIP data structure g graph structure cost edge costs for DHCSTP result ST edges connected ST nodes
Definition at line 831 of file heur_tm.c.
References GRAPH::cost, GRAPH::edges, SCIP_CALL, SCIP_OKAY, SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, and UNKNOWN.
Referenced by computeSteinerTree(), computeSteinerTreeDijk(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), and computeSteinerTreeVnoi().
◆ computeSteinerTreeDijk()
|
static |
Dijkstra based shortest paths heuristic
- Parameters
-
scip SCIP data structure g graph structure cost edge costs dijkdist distance array result solution array (on edges) dijkedge predecessor edge array start start vertex randnumgen random number generator connected array marking all solution vertices
Definition at line 855 of file heur_tm.c.
References GRAPH::grad, graph_path_st(), GRAPH::knots, GRAPH::mark, nnodes, NULL, prune(), SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPStpHeurTMRun().
◆ computeSteinerTreeDijkPcMw()
|
static |
Dijkstra based shortest paths heuristic for PCSTP and MWCSP
- Parameters
-
scip SCIP data structure g graph structure cost edge costs dijkdist distance array result solution array (on edges) dijkedge predecessor edge array start start vertex connected array marking all solution vertices
Definition at line 886 of file heur_tm.c.
References graph_path_st_pcmw(), graph_path_st_rmw(), graph_path_st_rpc(), prune(), SCIP_CALL, SCIP_OKAY, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.
Referenced by SCIPStpHeurTMRun().
◆ computeSteinerTreeDijkPcMwFull()
|
static |
Dijkstra based shortest paths heuristic for PCSTP and MWCSP that computes tree spanning all positive vertex weights and subsequently prunes this tree
- Parameters
-
scip SCIP data structure g graph structure cost edge costs dijkdist distance array result solution array (on edges) dijkedge predecessor edge array start start vertex connected array marking all solution vertices
Definition at line 912 of file heur_tm.c.
References graph_path_st_pcmw_full(), prune(), SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPStpHeurTMRun().
◆ computeSteinerTree()
|
static |
shortest paths based heuristic
- Parameters
-
scip SCIP data structure g graph structure cost edge costs costrev reversed edge costs pathdist distance array start start vertex perm permutation array (on nodes) result solution array (on edges) cluster array used to store current vertices of each subtree during construction pathedge predecessor edge array connected array marking all solution vertices randnumgen random number generator
Definition at line 933 of file heur_tm.c.
References FALSE, FARAWAY, GRAPH::grad, graph_valid(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, prune(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPisLT(), SCIPisStopped(), SCIPrandomGetInt(), SCIPrandomPermuteIntArray(), GRAPH::source, STP_DHCSTP, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.
Referenced by SCIPStpHeurTMRun().
◆ computeDegConsTree()
|
static |
heuristic for degree constrained STPs
- Parameters
-
scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs pathdist distances from each terminal to all nodes start start vertex perm permutation array result array to indicate whether an edge is in the solution cluster array for internal computations pathedge ancestor edges for shortest paths from each terminal to all nodes randnumgen random number generator connected array to indicate whether a vertex is in the solution solfound pointer to store whether a solution has been found
Definition at line 1073 of file heur_tm.c.
References CONNECT, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::maxdeg, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebug, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPrandomGetInt(), SCIPrandomPermuteIntArray(), SCIPStpHeurTMBuildTreeDc(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by SCIPStpHeurTMRun().
◆ computeSteinerTreeVnoi()
|
static |
Voronoi based shortest path heuristic
- Parameters
-
scip SCIP data structure g graph structure pqueue priority queue gnodearr internal array cost edge costs costrev reversed edge costs node_dist internal array start start vertex result array to indicate whether an edge is in the solution vcount internal array nodenterms internal array node_base internal array node_edge internal array firstrun method called for the first time? (during one heuristic round) connected array to indicate whether a vertex is in the solution
Definition at line 1328 of file heur_tm.c.
References CONNECT, Graph_Node::dist, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, GRAPH::grad, graph_voronoi(), graph_voronoiExtend(), GRAPH::head, heap_add(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, number, Graph_Node::number, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, prune(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisStopped(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPsortRealIntInt(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by SCIPStpHeurTMRun().
◆ 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().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 2635 of file heur_tm.c.
References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurTM().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 2649 of file heur_tm.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeRandom(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 2673 of file heur_tm.c.
References HEUR_NAME, NULL, SCIP_OKAY, SCIPgetProbData(), SCIPheurGetData(), SCIPheurGetName(), SCIPprobdataGetGraph(), STP_SPG, and GRAPH::stp_type.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 2708 of file heur_tm.c.
References GRAPH::cost, GRAPH::edges, FALSE, graph_sol_getObj(), HEUR_NAME, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_HEURTIMING_AFTERLPLOOP, SCIP_HEURTIMING_AFTERNODE, SCIP_HEURTIMING_BEFORENODE, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetProbData(), SCIPheurGetData(), SCIPheurGetName(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPStpHeurTMRunLP(), SCIPStpValidateSol(), STP_MWCSP, STP_PCSPG, and GRAPH::stp_type.
◆ 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().