Detailed Description

Improvement heuristic for Steiner problems.

Author: Daniel Rehfeldt

This file implements several local heuristics, including vertex insertion, key-path exchange and key-vertex elimination, ("Fast Local Search for Steiner Trees in Graphs" by Uchoa and Werneck). Other heuristics are for PCSTP and MWCSP.

A list of all interface methods can be found in heur_local.h.

Definition in file heur_local.c.

#include <assert.h>
#include <string.h>
#include "heur_local.h"
#include "heur_tm.h"
#include "probdata_stp.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME "local"

#define	HEUR_DESC "improvement heuristic for STP"

#define	HEUR_DISPCHAR '-'

#define	HEUR_PRIORITY 100

#define	HEUR_FREQ 1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE \| SCIP_HEURTIMING_DURINGLPLOOP \| SCIP_HEURTIMING_AFTERLPLOOP \| SCIP_HEURTIMING_AFTERNODE)

#define	HEUR_USESSUBSCIP FALSE

#define	DEFAULT_DURINGROOT TRUE

#define	DEFAULT_MAXFREQLOC FALSE

#define	DEFAULT_MAXNBESTSOLS 25

#define	DEFAULT_NBESTSOLS 10

#define	DEFAULT_MINNBESTSOLS 6

#define	LOCAL_MAXRESTARTS 5

#define	GREEDY_MAXRESTARTS 3

#define	GREEDY_EXTENSIONS_MW 6

#define	GREEDY_EXTENSIONS 5

Functions
static void	dfsorder (const GRAPH graph, const int edges, const int node, int counter, int *dfst)

static SCIP_RETCODE	lca (SCIP scip, const GRAPH graph, int u, UF uf, STP_Bool nodesmark, int steineredges, IDX lcalists, PHNODE boundpaths, int heapsize, int *vbase)

static STP_Bool	nodeIsCrucial (const GRAPH graph, int steineredges, int node)

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)

static	SCIP_DECL_HEURCOPY (heurCopyLocal)

static	SCIP_DECL_HEURFREE (heurFreeLocal)

static	SCIP_DECL_HEURINITSOL (heurInitsolLocal)

static	SCIP_DECL_HEUREXITSOL (heurExitsolLocal)

static	SCIP_DECL_HEUREXEC (heurExecLocal)

SCIP_RETCODE	SCIPStpIncludeHeurLocal (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "local"

Definition at line 41 of file heur_local.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXITSOL(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINITSOL(), and SCIPStpIncludeHeurLocal().

◆ HEUR_DESC

#define HEUR_DESC "improvement heuristic for STP"

Definition at line 42 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR '-'

Definition at line 43 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 100

Definition at line 44 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 45 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 46 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 47 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_TIMING

#define HEUR_TIMING (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)

Definition at line 48 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 50 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_DURINGROOT

#define DEFAULT_DURINGROOT TRUE

Definition at line 52 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_MAXFREQLOC

#define DEFAULT_MAXFREQLOC FALSE

Definition at line 53 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_MAXNBESTSOLS

#define DEFAULT_MAXNBESTSOLS 25

Definition at line 54 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_NBESTSOLS

#define DEFAULT_NBESTSOLS 10

Definition at line 55 of file heur_local.c.

Referenced by SCIP_DECL_HEURINITSOL().

◆ DEFAULT_MINNBESTSOLS

#define DEFAULT_MINNBESTSOLS 6

Definition at line 56 of file heur_local.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ LOCAL_MAXRESTARTS

#define LOCAL_MAXRESTARTS 5

Definition at line 57 of file heur_local.c.

◆ GREEDY_MAXRESTARTS

#define GREEDY_MAXRESTARTS 3

Max number of restarts for greedy PC/MW heuristic if improving solution has been found.

Definition at line 59 of file heur_local.c.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ GREEDY_EXTENSIONS_MW

#define GREEDY_EXTENSIONS_MW 6

Number of extensions for greedy MW heuristic. MUST BE HIGHER THAN GREEDY_EXTENSIONS

Definition at line 60 of file heur_local.c.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ GREEDY_EXTENSIONS

#define GREEDY_EXTENSIONS 5

Number of extensions for greedy PC heuristic.

Definition at line 61 of file heur_local.c.

Referenced by SCIPStpHeurLocalExtendPcMw().

Function Documentation

◆ dfsorder()

static void dfsorder	(	const GRAPH *	graph,
		const int *	edges,
		const int *	node,
		int *	counter,
		int *	dfst
	)

static

recursive methode for a DFS ordering of graph 'g'

Definition at line 86 of file heur_local.c.

References GRAPH::head, GRAPH::oeat, and GRAPH::outbeg.

Referenced by SCIPStpHeurLocalRun().

◆ lca()

static SCIP_RETCODE lca	(	SCIP *	scip,
		const GRAPH *	graph,
		int	u,
		UF *	uf,
		STP_Bool *	nodesmark,
		int *	steineredges,
		IDX **	lcalists,
		PHNODE **	boundpaths,
		int *	heapsize,
		int *	vbase
	)

static

computes lowest common ancestors for all pairs {vbase(v), vbase(u)} such that {u,w} is a boundary edge, first call should be with u := root

Definition at line 113 of file heur_local.c.

References EAT_LAST, FALSE, GRAPH::head, Int_List_Node::index, GRAPH::oeat, GRAPH::outbeg, UnionFind_Structure::parent, Int_List_Node::parent, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPfreeBufferArray, SCIPpairheapBuffarr(), SCIPStpunionfindFind(), SCIPStpunionfindUnion(), and TRUE.

Referenced by SCIPStpHeurLocalRun().

◆ nodeIsCrucial()

static STP_Bool nodeIsCrucial	(	const GRAPH *	graph,
		int *	steineredges,
		int	node
	)

static

checks whether node is crucial, i.e. a terminal or a vertex with degree at least 3 (w.r.t. the steinertree)

Definition at line 175 of file heur_local.c.

References FALSE, flipedge, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and TRUE.

Referenced by SCIPStpHeurLocalRun().

◆ SCIPStpHeurLocalRun()

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

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

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().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyLocal )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 1963 of file heur_local.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPStpIncludeHeurLocal().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeLocal )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 1977 of file heur_local.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolLocal )

static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 1996 of file heur_local.c.

References DEFAULT_NBESTSOLS, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPheurGetData(), and SCIPheurGetName().

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolLocal )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 2021 of file heur_local.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeMemoryArray, SCIPheurGetData(), and SCIPheurGetName().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecLocal )

static

execution method of primal heuristic

Definition at line 2042 of file heur_local.c.

References CONNECT, GRAPH::cost, DEFAULT_MINNBESTSOLS, EAT_LAST, GRAPH::edges, FALSE, graph_sol_valid(), GRAPH::head, HEUR_NAME, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetProbData(), SCIPgetSolOrigObj(), SCIPgetSols(), SCIPgetSubscipDepth(), SCIPheurGetData(), SCIPheurGetName(), SCIPisEQ(), SCIPisGT(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPStpHeurLocalRun(), SCIPStpHeurTMPrune(), SCIPStpHeurTMPrunePc(), SCIPStpValidateSol(), GRAPH::source, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_DURINGROOT

◆ DEFAULT_MAXFREQLOC

◆ DEFAULT_MAXNBESTSOLS

◆ DEFAULT_NBESTSOLS

◆ DEFAULT_MINNBESTSOLS

◆ LOCAL_MAXRESTARTS

◆ GREEDY_MAXRESTARTS

◆ GREEDY_EXTENSIONS_MW

◆ GREEDY_EXTENSIONS

Function Documentation

◆ dfsorder()

◆ lca()

◆ nodeIsCrucial()

◆ SCIPStpHeurLocalRun()

◆ SCIPStpHeurLocalExtendPcMw()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpIncludeHeurLocal()