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 "graph.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPStpIncludeHeurLocal (SCIP *scip)

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

SCIP_RETCODE	SCIPStpHeurLocalRunFast (SCIP scip, GRAPH graph, int *best_result)

SCIP_RETCODE	SCIPStpHeurLocalExtendPcMwImp (SCIP scip, const GRAPH graph, int *result)

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

SCIP_RETCODE	SCIPStpHeurLocalExtendPcMwOut (SCIP scip, GRAPH graph, int stedge, STP_Bool stvertex)

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 4353 of file heur_local.c.

References DEFAULT_DURINGROOT, DEFAULT_MAXFREQLOC, DEFAULT_MAXNBESTSOLS, DEFAULT_NBESTSOLS_HARD, DEFAULT_RANDSEED, 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, SCIPcreateRandom(), SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExitsol(), SCIPsetHeurFree(), SCIPsetHeurInitsol(), and TRUE.

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

◆ SCIPStpHeurLocalRun()

SCIP_RETCODE SCIPStpHeurLocalRun	(	SCIP *	scip,
		GRAPH *	graph,
		int *	solEdges
	)

perform local heuristics on a given Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
solEdges	array indicating whether an arc is part of the solution: CONNECTED/UNKNOWN (in/out)

Definition at line 3899 of file heur_local.c.

References FALSE, localRun(), SCIP_CALL, and SCIP_OKAY.

Referenced by computeNewSols(), computeReducedProbSolutionBiased(), computeSteinerTreeRedCosts(), computeSteinerTreeRedCostsPcMw(), daPcAddTmSolToPool(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), redcostGraphComputeSteinerTree(), reduce_dapaths(), SCIP_DECL_HEUREXEC(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurSlackPruneRun(), selectBranchingVertexBySol(), termcompComputeSubgraphSol(), and updateSolution().

◆ SCIPStpHeurLocalRunFast()

SCIP_RETCODE SCIPStpHeurLocalRunFast	(	SCIP *	scip,
		GRAPH *	graph,
		int *	solEdges
	)

perform fast local heuristics on a given Steiner tree

perform local heuristics on a given Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
solEdges	array indicating whether an arc is part of the solution: CONNECTED/UNKNOWN (in/out)

Definition at line 3911 of file heur_local.c.

References localRun(), SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by computeSteinerTreeRedCosts().

◆ SCIPStpHeurLocalExtendPcMwImp()

SCIP_RETCODE SCIPStpHeurLocalExtendPcMwImp	(	SCIP *	scip,
		const GRAPH *	graph,
		int *	result
	)

Implication based local heuristic for (R)PC and MW

Parameters

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

Definition at line 3923 of file heur_local.c.

References GRAPH::extended, graph_knot_printInfo(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_nNonFixedTerms(), Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, NULL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPStpGetPcImplStarts(), SCIPStpGetPcImplVerts(), solstp_setVertexFromEdge(), and GRAPH::term.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIPStpHeurLocalExtendPcMw()

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

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
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

Definition at line 3991 of file heur_local.c.

References addToCandidates(), BMSclearMemoryArray, BMScopyMemoryArray, CONNECT, GRAPH::cost, shortest_path::edge, GRAPH::edges, GRAPH::extended, FALSE, GNODECmpByDist(), GRAPH::grad, graph_edge_printInfo(), graph_knot_printInfo(), graph_path_st_pcmw_extend(), graph_pc_2transcheck(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GREEDY_EXTENSIONS, GREEDY_EXTENSIONS_MW, GREEDY_MAXRESTARTS, GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, NULL, Graph_Node::number, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisLE(), SCIPisLT(), SCIPpqueueCreate(), SCIPpqueueFree(), SCIPpqueueNElems(), SCIPpqueueRemove(), solstp_getObjBounded(), solstp_isValid(), solstp_prune(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by localExtendPc(), and localRun().

◆ SCIPStpHeurLocalExtendPcMwOut()

SCIP_RETCODE SCIPStpHeurLocalExtendPcMwOut	(	SCIP *	scip,
		GRAPH *	graph,
		int *	stedge,
		STP_Bool *	stvertex
	)

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
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

Definition at line 4225 of file heur_local.c.

References GRAPH::edges, GRAPH::extended, FALSE, graph_free_csr(), graph_heap_create(), graph_heap_free(), graph_init_csr(), graph_path_st_pcmw_extendOut(), graph_pc_2org(), graph_pc_2orgcheck(), graph_pc_2trans(), graph_pc_isPcMw(), graph_pc_termIsNonLeafTerm(), GREEDY_EXTENSIONS, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateRandom(), SCIPfreeBufferArray, SCIPfreeRandom(), SCIPisLE(), SCIPrandomGetInt(), solstp_getObjBounded(), solstp_prune(), solstp_setVertexFromEdge(), GRAPH::term, and TRUE.

SCIP

Detailed Description

Functions

Function Documentation

◆ SCIPStpIncludeHeurLocal()

◆ SCIPStpHeurLocalRun()

◆ SCIPStpHeurLocalRunFast()

◆ SCIPStpHeurLocalExtendPcMwImp()

◆ SCIPStpHeurLocalExtendPcMw()

◆ SCIPStpHeurLocalExtendPcMwOut()