heur_slackprune.h File Reference

Detailed Description

dual-ascent and reduction based primal heuristic for Steiner problems

Author

Daniel Rehfeldt

This file implements a dual-ascent and reduction 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_slackprune.h.

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

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPStpIncludeHeurSlackPrune (SCIP *scip)
SCIP_RETCODE	SCIPStpHeurSlackPruneRun (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success, SCIP_Bool reducegraph, SCIP_Bool fullreduce)
SCIP_RETCODE	SCIPStpHeurSlackPruneRunPcMw (SCIP *scip, SCIP_VAR **vars, GRAPH *g, int *soledge, SCIP_Bool *success)

Function Documentation

SCIPStpIncludeHeurSlackPrune()

SCIP_RETCODE SCIPStpIncludeHeurSlackPrune

(

SCIP *

scip

)

creates the slack prune primal heuristic and includes it in SCIP

creates the slackprune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1130 of file heur_slackprune.c.

References DEFAULT_SLACKPRUNE_MAXFREQ, 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().

SCIPStpHeurSlackPruneRun()

SCIP_RETCODE SCIPStpHeurSlackPruneRun	(	SCIP *	scip,
		SCIP_VAR **	vars,
		GRAPH *	g,
		int *	soledge,
		SCIP_Bool *	success,
		SCIP_Bool	reducegraph,
		SCIP_Bool	fullreduce
	)

execute slack-and-prune heuristic on given graph

Parameters

scip	SCIP data structure
vars	problem variables or NULL
g	graph data structure
soledge	array to 1. provide and 2. return primal solution
success	feasible solution found?
reducegraph	try to reduce graph initially?
fullreduce	use full reduction techniques?

Definition at line 525 of file heur_slackprune.c.

References BMScopyMemoryArray, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, getRedBound(), GRAPH::grad, graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, GRAPH::knots, level0(), nnodes, nterms, NULL, redLoopStp(), reduce_daSlackPrune(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPisLE(), SCIPprobdataGetOffset(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneUpdateSols(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, GRAPH::source, STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC().

SCIPStpHeurSlackPruneRunPcMw()

SCIP_RETCODE SCIPStpHeurSlackPruneRunPcMw	(	SCIP *	scip,
		SCIP_VAR **	vars,
		GRAPH *	g,
		int *	soledge,
		SCIP_Bool *	success
	)

execute MWCSP slack-and-prune heuristic on given graph

execute slack-and-prune heuristic on given graph

Parameters

scip	SCIP data structure
vars	problem variables or NULL
g	graph data structure
soledge	array to 1. provide and 2. return primal solution
success	feasible solution found?

Definition at line 803 of file heur_slackprune.c.

References GRAPH::ancestors, CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::fixedges, getRedBound(), GRAPH::grad, graph_copy(), graph_edge_del(), graph_free(), graph_get_NVET(), graph_init_history(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_markPcancestors(), graph_sol_setNodeList(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, redLoopMw(), reduce_daSlackPruneMw(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBuffer, SCIPfreeBufferArray, SCIPisLT(), SCIPprobdataGetOffset(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurTMPrunePc(), SCIPvarGetUbLocal(), setMinMaxElims(), SLACKPRUNE_MAXREDROUNDS, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and updateSolNodeArray().