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"

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

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 98 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 115 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 168 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 383 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 556 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 654 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 733 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

scip	SCIP data structure
g	graph structure
cost	edge costs for DHCSTP
result	ST edges
connected	ST nodes

Definition at line 832 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

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 856 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

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 887 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

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 913 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

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 934 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

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 1074 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, MIN, 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

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 1329 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 1650 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, MIN, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, r, RESTRICT, 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 2353 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, MIN, 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 2636 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 2650 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 2674 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 SCIP_DECL_HEUREXEC ( heurExecTM )

static

execution method of primal heuristic

Definition at line 2709 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 2833 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_EVALRUNS

◆ DEFAULT_INITRUNS

◆ DEFAULT_LEAFRUNS

◆ DEFAULT_ROOTRUNS

◆ DEFAULT_DURINGLPFREQ

◆ DEFAULT_TYPE

◆ DEFAULT_RANDSEED

◆ AUTO

◆ TM_SP

◆ TM_VORONOI

◆ TM_DIJKSTRA

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

◆ SCIPStpHeurTMCompStarts()

◆ SCIPStpHeurTMPrunePc()

◆ SCIPStpHeurTMBuildTreePcMw()

◆ SCIPStpHeurTMPrune()

◆ SCIPStpHeurTMBuildTree()

◆ SCIPStpHeurTMBuildTreeDc()

◆ prune()

◆ computeSteinerTreeDijk()

◆ computeSteinerTreeDijkPcMw()

◆ computeSteinerTreeDijkPcMwFull()

◆ computeSteinerTree()

◆ computeDegConsTree()

◆ computeSteinerTreeVnoi()

◆ SCIPStpHeurTMRun()

◆ SCIPStpHeurTMRunLP()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpIncludeHeurTM()