heur_ascendprune.h File Reference

Detailed Description

reduction and dual-cost based primal heuristic for Steiner problems

Author

Daniel Rehfeldt

This file implements a reducion and dual-cost 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_ascendprune.h.

#include "scip/scip.h"
#include "graph.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPStpIncludeHeurAscendPrune (SCIP *scip)
SCIP_RETCODE	SCIPStpHeurAscendPruneRun (SCIP *scip, SCIP_HEUR *heur, const GRAPH *g, const SCIP_Real *redcosts, int *edgearrint, int root, SCIP_Bool *solfound, SCIP_Bool addsol)

Function Documentation

SCIPStpIncludeHeurAscendPrune()

SCIP_RETCODE SCIPStpIncludeHeurAscendPrune

(

SCIP *

scip

)

creates the prune primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1015 of file heur_ascendprune.c.

References DEFAULT_MAXFREQPRUNE, 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(), SCIPsetHeurFree(), and SCIPsetHeurInit().

Referenced by runShell(), SCIP_DECL_HEURCOPY(), and subscipSetupCallbacks().

SCIPStpHeurAscendPruneRun()

SCIP_RETCODE SCIPStpHeurAscendPruneRun	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		const GRAPH *	g,
		const SCIP_Real *	redcosts,
		int *	result,
		int	root,
		SCIP_Bool *	solfound,
		SCIP_Bool	addsol
	)

ascent and prune

Parameters

scip	SCIP data structure
heur	heuristic data structure or NULL
g	the graph
redcosts	the reduced costs
result	int edges array to store solution
root	the root (used for dual ascent)
solfound	has a solution been found? And added, if requested?
addsol	should the solution be added to SCIP by this method?

Definition at line 940 of file heur_ascendprune.c.

References GRAPH::extended, graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_printInfo(), graph_typeIsUndirected(), graph_valid(), Is_term, redcost0_graph::nedges_half, redcost0_graph::newgraph, NULL, redcostGraphBuild(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), redcostGraphFree(), redcostGraphMark(), redcost0_graph::root, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, solpool_addSolToScip(), solstp_getObj(), solstp_getTrivialSol(), solstp_isValid(), GRAPH::source, STP_DCSTP, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsDirected(), computeSteinerTreeRedCostsPcMw(), daExec(), dualascent_execPcMw(), reduce_daSlackPrune(), SCIP_DECL_HEUREXEC(), termcompComputeSubgraphSol(), and updateSolution().