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
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 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().

◆ 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().

◆ 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().

◆ 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().

◆ 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 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 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 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().

◆ 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ DEFAULT_HOPFACTOR

Function Documentation

◆ SCIPStpHeurTMCompStarts()

◆ SCIPStpIncludeHeurTM()

◆ SCIPStpHeurTMRun()

◆ SCIPStpHeurTMRunLP()

◆ SCIPStpHeurTMPrune()

◆ SCIPStpHeurTMPrunePc()

◆ SCIPStpHeurTMBuildTreePcMw()

◆ SCIPStpHeurTMBuildTree()

◆ SCIPStpHeurTMBuildTreeDc()