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

Definition in file heur_tm.h.

#include "scip/scip.h"
#include "grph.h"

Go to the source code of this file.

Macros
#define	DEFAULT_HOPFACTOR 0.33

Functions
SCIP_RETCODE	SCIPincludeHeurTM (SCIP *scip)

SCIP_RETCODE	SCIPheurComputeSteinerTree (SCIP scip, SCIP_HEURDATA heurdata, const 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_RETCODE	SCIPheurPruneSteinerTree (SCIP scip, const GRAPH g, SCIP_Real cost, int layer, int result, char *connected)

SCIP_RETCODE	SCIPheurPrunePCSteinerTree (SCIP scip, const GRAPH g, SCIP_Real cost, int result, char *connected)

SCIP_RETCODE	SCIPheurPruneDegConsSteinerTree (SCIP scip, const GRAPH g, int result, char connected)

Macro Definition Documentation

#define DEFAULT_HOPFACTOR 0.33

Definition at line 37 of file heur_tm.h.

Referenced by bound_reduce(), da_reduce(), daPc_reduce(), hcrcbound_reduce(), and SCIPincludeHeurTM().

Function Documentation

SCIP_RETCODE SCIPheurComputeSteinerTree	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		const 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
	)

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

Definition at line 1419 of file heur_tm.c.

References AUTO, BLOCKED, computeDegConsTree(), computeSteinerTree(), computeSteinerTreeDijk(), computeSteinerTreeVnoi(), CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GNODECmpByDist(), GRAPH::grad, graph_path_execX(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::mark, SCIP_HeurData::nexecs, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_DEG_CONS, STP_DIRECTED, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, SCIP_HeurData::stp_type, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TM_DIJKSTRA, TM_SP, TM_VORONOI, TRUE, and UNKNOWN.

Referenced by bound_reduce(), da_reduce(), daPc_reduce(), hcrcbound_reduce(), and SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPheurPruneDegConsSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result,
		char *	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

Definition at line 527 of file heur_tm.c.

References CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeDegConsTree(), and SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPheurPrunePCSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		int *	result,
		char *	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 197 of file heur_tm.c.

References CONNECT, EAT_LAST, shortest_path::edge, FALSE, graph_path_exec(), graph_sol_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::source, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by extendSteinerTreePcMw(), prune(), SCIP_DECL_HEUREXEC(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE SCIPheurPruneSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		int	layer,
		int *	result,
		char *	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
connected	ST nodes

Definition at line 381 of file heur_tm.c.

References CONNECT, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_DIRECTED, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::term, and GRAPH::terms.

Referenced by prune(), SCIP_DECL_HEUREXEC(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE SCIPincludeHeurTM ( SCIP * scip )

creates the TM primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2687 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, and TRUE.

Referenced by runShell(), and SCIP_DECL_HEURCOPY().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation