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 "grph.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 *nodearrint, int root, STP_Bool *nodearrchar, 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 620 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(), and SCIP_DECL_HEURCOPY().

SCIPStpHeurAscendPruneRun()

SCIP_RETCODE SCIPStpHeurAscendPruneRun	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		const GRAPH *	g,
		const SCIP_Real *	redcosts,
		int *	edgearrint,
		int *	nodearrint,
		int	root,
		STP_Bool *	nodearrchar,
		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
edgearrint	int edges array to store solution
nodearrint	int vertices array for internal computations
root	the root (used for dual ascent)
nodearrchar	STP_Bool vertices array for internal computations
solfound	has a solution been found?
addsol	should the solution be added to SCIP by this method?

Definition at line 291 of file heur_ascendprune.c.

References a, BMSclearMemoryArray, CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_init_history(), graph_knot_add(), graph_path_exit(), graph_path_init(), graph_pc_init(), graph_pc_updateTerm2edge(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, level0(), GRAPH::mark, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisZero(), SCIPprobdataAddNewSol(), SCIPprobdataGetNVars(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), GRAPH::source, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.

Referenced by computeDaSolPcMw(), computePertubedSol(), reduce_da(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), SCIP_DECL_HEUREXEC(), SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().