Scippy

SCIP

Solving Constraint Integer Programs

heur_tm.c File Reference

Detailed Description

Shortest paths based primal heuristics for Steiner problems.

Author
Gerald Gamrath
Thorsten Koch
Daniel Rehfeldt
Michael Winkler

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"

◆ 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

◆ 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

number of runs

Definition at line 49 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ 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

heuristic to execute

Definition at line 54 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ 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 SCIP_DECL_PARAMCHGD ( paramChgdRandomseed  )
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
graphgraph data structure
startsstarting points array
runspointer 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 
)

◆ 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
scipSCIP data structure
ggraph structure
mstpath data structure array
costedge costs
objresultpointer to store objective value of result
connectedCONNECT/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
scipSCIP data structure
ggraph structure
costedge costs
layerlayer (usually 0)
resultST edges, which need to be set to UNKNOWN
connectedST 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
scipSCIP data structure
ggraph structure
mstpath data structure array
costedge costs
objresultpointer to store objective value of result
connectedCONNECT/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
scipSCIP data structure
ggraph structure
resultST edges
connectedST 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 SCIP_RETCODE prune ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
int *  result,
STP_Bool connected 
)
static
Parameters
scipSCIP data structure
ggraph structure
costedge costs for DHCSTP
resultST edges
connectedST 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 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

Dijkstra based shortest paths heuristic

Parameters
scipSCIP data structure
ggraph structure
costedge costs
dijkdistdistance array
resultsolution array (on edges)
dijkedgepredecessor edge array
startstart vertex
randnumgenrandom number generator
connectedarray 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 SCIP_RETCODE computeSteinerTreeDijkPcMw ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real dijkdist,
int *  result,
int *  dijkedge,
int  start,
STP_Bool connected 
)
static

Dijkstra based shortest paths heuristic for PCSTP and MWCSP

Parameters
scipSCIP data structure
ggraph structure
costedge costs
dijkdistdistance array
resultsolution array (on edges)
dijkedgepredecessor edge array
startstart vertex
connectedarray 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 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

Dijkstra based shortest paths heuristic for PCSTP and MWCSP that computes tree spanning all positive vertex weights and subsequently prunes this tree

Parameters
scipSCIP data structure
ggraph structure
costedge costs
dijkdistdistance array
resultsolution array (on edges)
dijkedgepredecessor edge array
startstart vertex
connectedarray 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 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

shortest paths based heuristic

Parameters
scipSCIP data structure
ggraph structure
costedge costs
costrevreversed edge costs
pathdistdistance array
startstart vertex
permpermutation array (on nodes)
resultsolution array (on edges)
clusterarray used to store current vertices of each subtree during construction
pathedgepredecessor edge array
connectedarray marking all solution vertices
randnumgenrandom 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 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

heuristic for degree constrained STPs

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathdistdistances from each terminal to all nodes
startstart vertex
permpermutation array
resultarray to indicate whether an edge is in the solution
clusterarray for internal computations
pathedgeancestor edges for shortest paths from each terminal to all nodes
randnumgenrandom number generator
connectedarray to indicate whether a vertex is in the solution
solfoundpointer 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 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 
)
static

Voronoi based shortest path heuristic

Parameters
scipSCIP data structure
ggraph structure
pqueuepriority queue
gnodearrinternal array
costedge costs
costrevreversed edge costs
node_distinternal array
startstart vertex
resultarray to indicate whether an edge is in the solution
vcountinternal array
nodentermsinternal array
node_baseinternal array
node_edgeinternal array
firstrunmethod called for the first time? (during one heuristic round)
connectedarray 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
scipSCIP data structure
heurdataSCIP data structure
graphgraph data structure
startsarray containing start vertices (NULL to not provide any)
bestnewstartpointer to the start vertex resulting in the best solution
best_resultarray indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
runsnumber of runs
bestincstartbest incumbent start vertex
costarc costs
costrevreversed arc costs
hopfactoredge cost multiplicator for HC problems
nodepriorityvertex priorities for vertices to be starting points (NULL for no priorities)
maxcostmaximal edge cost (only for HC)
successpointer to store whether a solution could be found
pcmwfulluse 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
scipSCIP data structure
graphgraph data structure
heurheuristic or NULL
resultarray indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
runsnumber of runs
costarc costs (uninitialized)
costrevreversed arc costs (uninitialized)
successpointer 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 SCIP_DECL_HEURCOPY ( heurCopyTM  )
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 SCIP_DECL_HEURFREE ( heurFreeTM  )
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 SCIP_DECL_HEURINIT ( heurInitTM  )
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()

◆ SCIPStpIncludeHeurTM()