Detailed Description

Improvement heuristic for Steiner problems.

Author: Daniel Rehfeldt

This file implements three local heuristics, namely vertex insertion, key-path exchange and key-vertex elimination, see "Fast Local Search for Steiner Trees in Graphs" by Uchoa and Werneck.

Definition in file heur_local.h.

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

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeHeurLocal (SCIP *scip)

SCIP_RETCODE	SCIPheurImproveSteinerTree (SCIP scip, GRAPH graph, SCIP_Real cost, SCIP_Real costrev, int *best_result)

SCIP_RETCODE	extendSteinerTreePcMw (SCIP scip, const GRAPH graph, PATH vnoi, SCIP_Real costrev, int vbase, int stedge, char stvertex, int adds)

Function Documentation

SCIP_RETCODE extendSteinerTreePcMw	(	SCIP *	scip,
		const GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	costrev,
		int *	vbase,
		int *	stedge,
		char *	stvertex,
		int *	adds
	)

local heuristic for (R)PC and MW

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
costrev	reversed edge costs
vbase	array to store Voronoi bases to each vertex
stedge	array to indicate whether an edge is part of the Steiner tree
stvertex	uninitialized array to indicate whether an edge is part of the Steiner tree
adds	pointer to store number of added vertices

Definition at line 1941 of file heur_local.c.

References CONNECT, GRAPH::cost, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPheurPrunePCSteinerTree(), GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, and voronoiSteinerTreeExt().

Referenced by da_reduce(), daPc_reduce(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE SCIPheurImproveSteinerTree	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		int *	best_result
	)

perform local heuristics on a given Steiner tree

Key-Path Exchange

Parameters

scip	SCIP data structure
graph	graph data structure
cost	arc cost array
costrev	reversed arc cost array
best_result	array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)

Definition at line 282 of file heur_local.c.

References CONNECT, GRAPH::cost, dfsorder(), shortest_path::dist, EAT_LAST, ST_Node::edge, shortest_path::edge, GRAPH::edges, extendSteinerTreePcMw(), 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_valid(), GSTP, GRAPH::head, heap_add(), GRAPH::ieat, Int_List_Node::index, GRAPH::inpbeg, insert(), Is_pterm, Is_term, GRAPH::knots, lca(), GRAPH::mark, MST_MODE, nodeIsCrucial(), GRAPH::oeat, GRAPH::outbeg, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPlinkcuttreeCut(), SCIPlinkcuttreeEvert(), SCIPlinkcuttreeFindMax(), SCIPlinkcuttreeFindMinMW(), SCIPlinkcuttreeInit(), SCIPlinkcuttreeLink(), SCIPpairheapDeletemin(), SCIPpairheapFree(), SCIPpairheapInsert(), SCIPpairheapMeldheaps(), SCIPprobdataPrintGraph2(), SCIPunionfindFind(), SCIPunionfindFree(), SCIPunionfindInit(), SCIPunionfindUnion(), GRAPH::source, STP_GRID, STP_MAX_NODE_WEIGHT, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, voronoi(), voronoi_repair(), and voronoi_repair_mult().

Referenced by SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPincludeHeurLocal ( SCIP * scip )

creates the local primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2421 of file heur_local.c.

References DEFAULT_DURINGROOT, DEFAULT_MAXFREQLOC, DEFAULT_MAXNBESTSOLS, DEFAULT_NBESTSOLS, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.

Referenced by runShell(), and SCIP_DECL_HEURCOPY().

SCIP

Detailed Description

Functions

Function Documentation