heur_local.h File Reference

Detailed Description

Improvement heuristic for Steiner problems.

Author

Daniel Rehfeldt

This file implements three local search heuristics, namely vertex insertion, key-path exchange and key-vertex elimination, see "Fast Local Search for Steiner Trees in Graphs" by Uchoa and Werneck. Furthermore, it includes several non-published local search heuristics for prize-collecting Steiner problem tree variants.

Definition in file heur_local.h.

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

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPStpIncludeHeurLocal (SCIP *scip)
SCIP_RETCODE	SCIPStpHeurLocalRun (SCIP *scip, GRAPH *graph, const SCIP_Real *cost, int *best_result)
SCIP_RETCODE	SCIPStpHeurLocalExtendPcMw (SCIP *scip, GRAPH *graph, const SCIP_Real *cost, PATH *path, int *stedge, STP_Bool *stvertex, SCIP_Bool *extensions)

Function Documentation

SCIPStpIncludeHeurLocal()

SCIP_RETCODE SCIPStpIncludeHeurLocal

(

SCIP *

scip

)

creates the local primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2272 of file heur_local.c.

References DEFAULT_DURINGROOT, DEFAULT_MAXFREQLOC, DEFAULT_MAXNBESTSOLS, 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(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), and SCIPsetHeurInitsol().

Referenced by runShell(), and SCIP_DECL_HEURCOPY().

SCIPStpHeurLocalRun()

SCIP_RETCODE SCIPStpHeurLocalRun	(	SCIP *	scip,
		GRAPH *	graph,
		const SCIP_Real *	cost,
		int *	best_result
	)

perform local heuristics on a given Steiner tree

perform local heuristics on a given Steiner tree todo delete cost parameter

Key-Path Exchange

Parameters

scip	SCIP data structure
graph	graph data structure
cost	arc cost array todo delete this parameter and use graph->cost
best_result	array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)

Definition at line 208 of file heur_local.c.

References BMSclearMemoryArray, CONNECT, GRAPH::cost, dfsorder(), shortest_path::dist, EAT_FREE, EAT_LAST, ST_Node::edge, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_sol_getObj(), graph_sol_valid(), graph_valid(), graph_voronoi(), graph_voronoiRepair(), graph_voronoiRepairMult(), GRAPH::head, heap_add(), GRAPH::ieat, Int_List_Node::index, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, lca(), GRAPH::mark, MST_MODE, nnodes, nodeIsCrucial(), NULL, GRAPH::oeat, GRAPH::outbeg, ST_Node::parent, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisPositive(), SCIPlinkcuttreeCut(), SCIPlinkcuttreeEvert(), SCIPlinkcuttreeFindMax(), SCIPlinkcuttreeFindMinChain(), SCIPlinkcuttreeInit(), SCIPlinkcuttreeLink(), SCIPpairheapDeletemin(), SCIPpairheapFree(), SCIPpairheapInsert(), SCIPpairheapMeldheaps(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), SCIPStpunionfindClear(), SCIPStpunionfindFind(), SCIPStpunionfindFree(), SCIPStpunionfindInit(), SCIPStpunionfindUnion(), GRAPH::source, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeDaSolPcMw(), computeNewSols(), computePertubedSol(), reduce_da(), reduce_daPcMw(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and selectBranchingVertexBySol().

SCIPStpHeurLocalExtendPcMw()

SCIP_RETCODE SCIPStpHeurLocalExtendPcMw	(	SCIP *	scip,
		GRAPH *	graph,
		const SCIP_Real *	cost,
		PATH *	path,
		int *	stedge,
		STP_Bool *	stvertex,
		SCIP_Bool *	extensions
	)

greedy extension local heuristic for (R)PC and MW

Greedy Extension local heuristic for (R)PC and MW

Parameters

scip	SCIP data structure
graph	graph data structure
cost	edge cost array
path	shortest data structure array
stedge	initialized array to indicate whether an edge is part of the Steiner tree
stvertex	uninitialized array to indicate whether a vertex is part of the Steiner tree
extensions	pointer to store whether extensions have been made

Definition at line 1692 of file heur_local.c.

References BMSclearMemoryArray, BMScopyMemoryArray, CONNECT, GRAPH::cost, Graph_Node::dist, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, GNODECmpByDist(), GRAPH::grad, graph_path_st_pcmw_extend(), graph_pc_2transcheck(), GREEDY_EXTENSIONS, GREEDY_EXTENSIONS_MW, GREEDY_MAXRESTARTS, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::knots, MAX, nnodes, NULL, Graph_Node::number, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisLT(), SCIPpqueueCreate(), SCIPpqueueFirst(), SCIPpqueueFree(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPStpHeurTMPrunePc(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalRun().