heur_prune.h File Reference

Detailed Description

reduction-based primal heuristic for Steiner problems

Author

Daniel Rehfeldt

This file implements a reducion based heuristic for Steiner problems. It is based on an approach described in T. Polzin's "Algorithms for the Steiner problem in networks".

Definition in file heur_prune.h.

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

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPStpHeurPruneUpdateSols (SCIP *scip, GRAPH *g, GRAPH *prunegraph, PATH *path, int *nodearrint, int *edgearrint, int *solnode, int *soledge, int *globalsoledge, STP_Bool *nodearrchar, SCIP_Real *globalobj, SCIP_Bool incumbentgiven, SCIP_Bool *success)
SCIP_RETCODE	SCIPStpIncludeHeurPrune (SCIP *scip)
SCIP_RETCODE	SCIPStpHeurPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, const SCIP_Bool withinitialsol, const SCIP_Bool reducegraph)

Function Documentation

SCIPStpHeurPruneUpdateSols()

SCIP_RETCODE SCIPStpHeurPruneUpdateSols	(	SCIP *	scip,
		GRAPH *	g,
		GRAPH *	prunegraph,
		PATH *	path,
		int *	nodearrint,
		int *	edgearrint,
		int *	solnode,
		int *	soledge,
		int *	globalsoledge,
		STP_Bool *	nodearrchar,
		SCIP_Real *	globalobj,
		SCIP_Bool	incumbentgiven,
		SCIP_Bool *	success
	)

updates solutions for pruned graph

Parameters

scip	SCIP data structure
g	graph data structure
prunegraph	pruned graph data structure
path	shortest path struct
nodearrint	array
edgearrint	array
solnode	array for best solution nodes wrt prunegraph
soledge	array for best solution edges wrt prunegraph
globalsoledge	array storing best solution wrt g
nodearrchar	array
globalobj	pointer to objective value of best solution wrt g
incumbentgiven	incumbent solution for pruned graph given?
success	pointer to store whether a solution could be found

Definition at line 482 of file heur_prune.c.

References BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, FARAWAY, GRAPH::grad, graph_sol_getObj(), graph_sol_getOrg(), graph_sol_valid(), GRAPH::knots, GRAPH::mark, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), setNodeSolArray(), STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, GRAPH::stp_type, TRUE, and UNKNOWN.

Referenced by computeNewSols(), and SCIPStpHeurSlackPruneRun().

SCIPStpIncludeHeurPrune()

SCIP_RETCODE SCIPStpIncludeHeurPrune

(

SCIP *

scip

)

creates the prune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 908 of file heur_prune.c.

References DEFAULT_PRUNE_MAXFRQ, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInit(), and SCIPsetHeurInitsol().

Referenced by runShell(), and SCIP_DECL_HEURCOPY().

SCIPStpHeurPruneRun()

SCIP_RETCODE SCIPStpHeurPruneRun	(	SCIP *	scip,
		SCIP_VAR **	vars,
		GRAPH *	g,
		int *	soledge,
		SCIP_Bool *	success,
		const SCIP_Bool	withinitialsol,
		const SCIP_Bool	reducegraph
	)

execute prune heuristic on given graph

Parameters

scip	SCIP data structure
vars	problem variables or NULL (need to be provided whenever available)
g	the graph
soledge	array to store primal solution (if no solution is provided, withinitialsol must be set to FALSE)
success	feasible solution found?
withinitialsol	solution given?
reducegraph	try to reduce graph initially?

Definition at line 598 of file heur_prune.c.

References BMScopyMemoryArray, computeNewSols(), CONNECT, GRAPH::cost, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, getRedBound(), graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_pc_2org(), graph_pc_2trans(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, PRUNE_MAXREDROUNDS, redLoopMw(), redLoopPc(), redLoopStp(), reduce_boundPrune(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPvarGetUbLocal(), setMinMaxElims(), setNodeSolArray(), STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().