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"
#include "cons_stp.h"
#include "solstp.h"
#include "stpvector.h"

Go to the source code of this file.

Data Structures
struct	Voronoi_data_structures

struct	connectivity_data

struct	keypaths_data_structures

struct	solution_tree_data

struct	supergraph_data

struct	pcmw_data

struct	insertion_data

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 50

#define	DEFAULT_NBESTSOLS 15

#define	DEFAULT_NBESTSOLS_HARD 50

#define	DEFAULT_NELITESOLS 3

#define	DEFAULT_MINNBESTSOLS 10

#define	DEFAULT_MINNBESTSOLS_HARD 30

#define	DEFAULT_RANDSEED 1492

#define	LOCAL_MAXRESTARTS 10

#define	LOCAL_MAXRESTARTS_FAST 3

#define	GREEDY_MAXRESTARTS 3

#define	GREEDY_EXTENSIONS_MW 6

#define	GREEDY_EXTENSIONS 5

Typedefs
typedef struct Voronoi_data_structures	VNOILOC

typedef struct connectivity_data	CONN

typedef struct keypaths_data_structures	KPATHS

typedef struct solution_tree_data	SOLTREE

typedef struct supergraph_data	SGRAPH

typedef struct pcmw_data	PCMW

typedef struct insertion_data	INSERT

Functions
static SCIP_Bool	solNeedsPruning (SCIP_SOL *initialsol)

static SCIP_RETCODE	solPrune (SCIP scip, const GRAPH graph, int *results)

static void	solGetStpSol (SCIP scip, const GRAPH graph, SCIP_SOL initialsol, int results)

static void	initSolNumberBounds (SCIP scip, SCIP_HEURDATA heurdata)

static SCIP_RETCODE	solAddTry (SCIP scip, SCIP_SOL sols, SCIP_HEUR heur, const GRAPH graph, SCIP_Real initialsol_obj, SCIP_SOL initialsol, int results, SCIP_RESULT result)

static SCIP_Bool	probtypeIsValidForLocal (const GRAPH *graph)

static SCIP_RETCODE	addToCandidates (SCIP scip, const GRAPH graph, const PATH path, int i, int greedyextensions, int nextensions, GNODE candidates, SCIP_PQUEUE pqueue)

static void	markSolTreeNodes (SCIP scip, const GRAPH graph, const int solEdges, LCNODE linkcutNodes, STP_Bool *solNodes)

static SCIP_Bool	solIsTrivialPcMw (const GRAPH graph, const int solEdges)

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

static SCIP_RETCODE	getLowestCommonAncestors (SCIP scip, const GRAPH graph, const VNOILOC vnoiData, const SOLTREE soltreeData, CONN *connectData)

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

static SCIP_Real	getNewPrizeNode (const GRAPH graph, const STP_Bool steinertree, const SCIP_Real prize_biased, const int graphmark, int node, STP_Bool prizemark, int prizemarklist, int *prizemarkcount)

static int	pcmwGetSolRoot (const GRAPH graph, const int solEdges)

static SCIP_Real	pcmwGetNewEdgePrize (const GRAPH graph, const STP_Bool steinertree, int edge, PCMW *pcmwData)

static SCIP_Bool	pcmwDataIsClean (const GRAPH graph, const PCMW pcmwData)

static void	pcmwDataClean (const GRAPH graph, PCMW pcmwData)

static SCIP_RETCODE	pcmwUpdate (SCIP scip, GRAPH graph, SOLTREE soltreeData, PCMW pcmwData)

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

static SCIP_Real	getEdgeCostUnbiased (const GRAPH graph, const PCMW pcmwData, int edge)

static SCIP_Real	getBoundaryPathCost (const GRAPH graph, const VNOILOC vnoiData, const PCMW *pcmwData, int boundaryedge)

static SCIP_Real	getBoundaryPathCostPrized (const GRAPH graph, const VNOILOC vnoiData, const SOLTREE soltreeData, int boundaryedge, PCMW pcmwData)

static const SCIP_Real *	getEdgeCosts (const GRAPH graph, const PCMW pcmwData)

static SCIP_RETCODE	connectivityDataKeyElimUpdate (SCIP scip, const GRAPH graph, const VNOILOC vnoiData, const SGRAPH supergraphData, int crucnode, CONN *connectData)

static SCIP_RETCODE	connectivityDataInit (SCIP scip, const GRAPH graph, const VNOILOC vnoiData, const SOLTREE soltreeData, const PCMW pcmwData, CONN connectData)

static void	getKeyPathUpper (SCIP scip, int crucnode, const GRAPH graph, const SOLTREE soltreeData, const PCMW pcmwData, CONN connectData, KPATHS keypathsData, SCIP_Bool *allGood)

static void	soltreeUnmarkKpNodes (const GRAPH graph, const KPATHS keypathsData, SOLTREE *soltreeData)

static void	soltreeMarkKpNodes (const GRAPH graph, const KPATHS keypathsData, SOLTREE *soltreeData)

static SCIP_RETCODE	soltreeExchangeKeyPath (SCIP scip, GRAPH graph, const CONN connectData, const VNOILOC vnoiData, const KPATHS keypathsData, const int dfstree, const STP_Bool scanned, int dfstree_pos, int boundedge_new, SOLTREE soltreeData)

static SCIP_RETCODE	soltreeElimKeyPathsStar (SCIP scip, const GRAPH graph, const CONN connectData, const VNOILOC vnoiData, const KPATHS keypathsData, const SGRAPH supergraphData, const int dfstree, const STP_Bool scanned, int dfstree_pos, SOLTREE *soltreeData)

static SCIP_Real	getKeyPathReplaceCost (SCIP scip, const GRAPH graph, const VNOILOC vnoiData, const SOLTREE soltreeData, SCIP_Real edgecost_old_in, int boundedge_old, PCMW pcmwData, int boundedge_new)

static void	supergraphDataRestore (const GRAPH graph, SGRAPH supergraphData)

static SCIP_RETCODE	supergraphComputeMst (SCIP scip, const GRAPH graph, const CONN connectData, const VNOILOC vnoiData, const KPATHS keypathsData, int crucnode, SOLTREE soltreeData, PCMW pcmwData, SGRAPH supergraphData)

static void	getKeyPathsStar (int keyvertex, const GRAPH graph, const CONN connectData, const SOLTREE soltreeData, const PCMW pcmwData, KPATHS keypathsData, SGRAPH supergraphData, SCIP_Bool *success)

static void	vnoiDataRepairPreprocess (SCIP scip, const GRAPH graph, const KPATHS keypathsData, const CONN connectData, const PCMW pcmwData, VNOILOC vnoiData, int *nheapelems)

static void	vnoiDataRestore (const CONN connectData, const KPATHS keypathsData, VNOILOC *vnoiData)

static void	vnoiDataReset (const CONN connectData, const KPATHS keypathsData, const int graphmark, VNOILOC vnoiData)

static SCIP_Bool	solDegIsValid (SCIP scip, const GRAPH graph, const int solDegree, const LCNODE linkcutNodes)

static SCIP_Bool	solNodeIsValid (SCIP scip, const GRAPH graph, const STP_Bool solNodes, const LCNODE linkcutNodes)

static void	insertionDecrementSolDegree (const GRAPH graph, int node, INSERT insertData)

static void	insertionIncrementSolDegree (const GRAPH graph, int node, INSERT insertData)

static void	insertionInit (SCIP_HEURDATA heurdata, const GRAPH graph, const int solEdges, int solDegreeNonTerm, SCIP_Bool nodeIsBlocked, int vertices)

static void	insertionInitInsert (SCIP scip, const GRAPH graph, int v_insert, int initialEdge, LCNODE linkcutNodes, INSERT insertData, SCIP_Real *diff)

static void	insertionFinalizeReplacement (const GRAPH graph, int v_insert, LCNODE linkcutNodes, INSERT *insertData)

static void	insertionResetBlockedNodes (INSERT *insertData)

static void	insertionBlockChain (const GRAPH graph, const LCNODE lctree, int chainfirst_index, int chainlast_index, INSERT *insertData)

static void	insertionRestoreTree (const GRAPH graph, const int insertCands, int lcvertex_insert, LCNODE linkcutNodes, INSERT insertData)

static void	insertionReplaceChain (const GRAPH graph, int newedge, LCNODE lctree, INSERT *insertData, int v_lc, int headCurr_lc, int chainfirst_index, int chainlast_index)

static void	insertionGetCandidateEdges (SCIP scip, SCIP_HEURDATA heurdata, const GRAPH graph, const STP_Bool solNodes, int vertex, int insertcands, int ncands)

static SCIP_RETCODE	localVertexInsertion (SCIP scip, SCIP_HEURDATA heurdata, const GRAPH graph, STP_Bool solNodes, LCNODE linkcutNodes, int solEdges)

static SCIP_RETCODE	localKeyVertexHeuristics (SCIP scip, GRAPH graph, SCIP_Bool useFast, STP_Bool solNodes, LCNODE linkcutNodes, int solEdges, SCIP_Bool success)

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)

static SCIP_RETCODE	localRun (SCIP scip, GRAPH graph, SCIP_Bool useFast, int *solEdges)

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

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

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)

SCIP_RETCODE	SCIPStpIncludeHeurLocal (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "local"

Definition at line 43 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 44 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR '-'

Definition at line 45 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 100

Definition at line 46 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 47 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 48 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 49 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 50 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 52 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_DURINGROOT

#define DEFAULT_DURINGROOT TRUE

Definition at line 54 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_MAXFREQLOC

#define DEFAULT_MAXFREQLOC FALSE

Definition at line 55 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_MAXNBESTSOLS

#define DEFAULT_MAXNBESTSOLS 50

Definition at line 56 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ DEFAULT_NBESTSOLS

#define DEFAULT_NBESTSOLS 15

Definition at line 57 of file heur_local.c.

Referenced by initSolNumberBounds().

◆ DEFAULT_NBESTSOLS_HARD

#define DEFAULT_NBESTSOLS_HARD 50

Definition at line 58 of file heur_local.c.

Referenced by initSolNumberBounds(), and SCIPStpIncludeHeurLocal().

◆ DEFAULT_NELITESOLS

#define DEFAULT_NELITESOLS 3

Definition at line 59 of file heur_local.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ DEFAULT_MINNBESTSOLS

#define DEFAULT_MINNBESTSOLS 10

Definition at line 60 of file heur_local.c.

Referenced by initSolNumberBounds().

◆ DEFAULT_MINNBESTSOLS_HARD

#define DEFAULT_MINNBESTSOLS_HARD 30

Definition at line 61 of file heur_local.c.

Referenced by initSolNumberBounds().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 1492

random seed

Definition at line 62 of file heur_local.c.

Referenced by SCIPStpIncludeHeurLocal().

◆ LOCAL_MAXRESTARTS

#define LOCAL_MAXRESTARTS 10

Definition at line 63 of file heur_local.c.

Referenced by localKeyVertexHeuristics().

◆ LOCAL_MAXRESTARTS_FAST

#define LOCAL_MAXRESTARTS_FAST 3

Definition at line 64 of file heur_local.c.

Referenced by localKeyVertexHeuristics().

◆ GREEDY_MAXRESTARTS

#define GREEDY_MAXRESTARTS 3

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

Definition at line 67 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 68 of file heur_local.c.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ GREEDY_EXTENSIONS

#define GREEDY_EXTENSIONS 5

Number of extensions for greedy PC heuristic.

Definition at line 69 of file heur_local.c.

Referenced by SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurLocalExtendPcMwOut().

Typedef Documentation

◆ VNOILOC

typedef struct Voronoi_data_structures VNOILOC

Voronoi data for local heuristic

◆ CONN

typedef struct connectivity_data CONN

Connectivity data

◆ KPATHS

typedef struct keypaths_data_structures KPATHS

Key-paths data

◆ SOLTREE

typedef struct solution_tree_data SOLTREE

Solution tree data

◆ SGRAPH

typedef struct supergraph_data SGRAPH

Super graph data

◆ PCMW

typedef struct pcmw_data PCMW

Prize-collecting/maximum-weight connected subgraph data

◆ INSERT

typedef struct insertion_data INSERT

local insertion heuristic data

Function Documentation

◆ solNeedsPruning()

static SCIP_Bool solNeedsPruning ( SCIP_SOL * initialsol )

inlinestatic

prune the solution?

Parameters

initialsol SCIP data structure

Definition at line 194 of file heur_local.c.

References FALSE, NULL, SCIPheurGetName(), SCIPsolGetHeur(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ solPrune()

static SCIP_RETCODE solPrune	(	SCIP *	scip,
		const GRAPH *	graph,
		int *	results
	)

inlinestatic

prune the solution?

Parameters

scip	SCIP data structure
graph	graph data structure
results	Steiner tree edges (in/out)

Definition at line 220 of file heur_local.c.

References GRAPH::edges, GRAPH::knots, nnodes, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), solstp_getObjBounded(), solstp_isValid(), solstp_prune(), and solstp_setVertexFromEdge().

Referenced by SCIP_DECL_HEUREXEC().

◆ solGetStpSol()

static void solGetStpSol	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_SOL *	initialsol,
		int *	results
	)

inlinestatic

fills solution array 'results'

Parameters

scip	SCIP data structure
graph	graph data structure
initialsol	SCIP data structure
results	Steiner tree edges (out)

Definition at line 258 of file heur_local.c.

References CONNECT, graph_get_nEdges(), SCIP_Real, SCIPisEQ(), SCIPprobdataGetXval(), and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC().

◆ initSolNumberBounds()

static void initSolNumberBounds	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata
	)

static

initializes

Parameters

scip	SCIP data structure
heurdata	heuristic's data

Definition at line 290 of file heur_local.c.

References DEFAULT_MINNBESTSOLS, DEFAULT_MINNBESTSOLS_HARD, DEFAULT_NBESTSOLS, DEFAULT_NBESTSOLS_HARD, and SCIPprobdataProbIsAdversarial().

Referenced by SCIP_DECL_HEUREXEC().

◆ solAddTry()

static SCIP_RETCODE solAddTry	(	SCIP *	scip,
		SCIP_SOL **	sols,
		SCIP_HEUR *	heur,
		const GRAPH *	graph,
		SCIP_Real	initialsol_obj,
		SCIP_SOL *	initialsol,
		int *	results,
		SCIP_RESULT *	result
	)

inlinestatic

tries to add solution stored in 'results' to SCIP solution pool

Parameters

scip	SCIP data structure
sols	SCIP solutions
heur	heuristic
graph	graph data structure
initialsol_obj	objective
initialsol	SCIP data structure
results	Steiner tree edges (out)
result	pointer

Definition at line 312 of file heur_local.c.

References CONNECT, GRAPH::cost, FALSE, graph_get_nEdges(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetSolOrigObj(), SCIPheurGetData(), SCIPisEQ(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPprobdataAddNewSol(), SCIPprobdataGetOffset(), SCIPStpValidateSol(), and solstp_getObjBounded().

Referenced by SCIP_DECL_HEUREXEC().

◆ probtypeIsValidForLocal()

static SCIP_Bool probtypeIsValidForLocal ( const GRAPH * graph )

inlinestatic

can the problem class be used?

Parameters

graph graph data structure

Definition at line 401 of file heur_local.c.

References FALSE, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SPG, GRAPH::stp_type, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ addToCandidates()

static SCIP_RETCODE addToCandidates	(	SCIP *	scip,
		const GRAPH *	graph,
		const PATH *	path,
		int	i,
		int	greedyextensions,
		int *	nextensions,
		GNODE *	candidates,
		SCIP_PQUEUE *	pqueue
	)

static

submethod for local extend

Parameters

scip	SCIP data structure
graph	graph data structure
path	shortest data structure array
i	node
greedyextensions	greedyextensions
nextensions	nextensions
candidates	candidates
pqueue	pqueue

Definition at line 415 of file heur_local.c.

References Graph_Node::dist, shortest_path::dist, graph_pc_knotIsFixedTerm(), Is_pseudoTerm, Graph_Node::number, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPisLT(), SCIPpqueueFirst(), SCIPpqueueInsert(), SCIPpqueueRemove(), and GRAPH::term.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ markSolTreeNodes()

static void markSolTreeNodes	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	solEdges,
		LCNODE *	linkcutNodes,
		STP_Bool *	solNodes
	)

static

perform local vertex insertion heuristic on given Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
solEdges	Steiner tree edges
linkcutNodes	Steiner tree nodes
solNodes	Steiner tree nodes

Definition at line 455 of file heur_local.c.

References CONNECT, link_cut_node::edge, GRAPH::edges, FALSE, flipedge, GRAPH::head, GRAPH::knots, nnodes, SCIPlinkcuttreeInitNode(), SCIPlinkcuttreeLink(), solstp_isValid(), GRAPH::source, GRAPH::tail, and TRUE.

Referenced by localRun().

◆ solIsTrivialPcMw()

static SCIP_Bool solIsTrivialPcMw	(	const GRAPH *	graph,
		const int *	solEdges
	)

static

is given Steiner tree a trivial solution (i.e. contains only one vertex?)

Parameters

graph	graph data structure
solEdges	Steiner tree edges

Definition at line 499 of file heur_local.c.

References EAT_LAST, GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, GRAPH::source, GRAPH::term, and TRUE.

Referenced by localRun().

◆ lca()

static SCIP_RETCODE lca	(	SCIP *	scip,
		const GRAPH *	graph,
		int	u,
		UF *	uf,
		STP_Bool *	nodesmark,
		const int *	steineredges,
		STP_Vectype(int) *	lcalists,
		PHNODE **	boundpaths,
		const int *	heapsize,
		const 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 543 of file heur_local.c.

References CONNECT, EAT_LAST, FALSE, GRAPH::head, GRAPH::oeat, GRAPH::outbeg, UnionFind_Structure::parent, SCIP_CALL, SCIP_OKAY, SCIPfreeBufferArrayNull, SCIPpairheapBuffarr(), SCIPStpunionfindFind(), SCIPStpunionfindUnion(), StpVecPushBack, and TRUE.

Referenced by getLowestCommonAncestors().

◆ getLowestCommonAncestors()

static SCIP_RETCODE getLowestCommonAncestors	(	SCIP *	scip,
		const GRAPH *	graph,
		const VNOILOC *	vnoiData,
		const SOLTREE *	soltreeData,
		CONN *	connectData
	)

static

computes lowest common ancestors for all pairs {vbase(v), vbase(u)} such that {u,w} is a boundary edge

Parameters

scip	SCIP data structure
graph	graph data structure
vnoiData	Voronoi data
soltreeData	solution tree data
connectData	data

Definition at line 600 of file heur_local.c.

References FALSE, GRAPH::knots, lca(), nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPStpunionfindIsClear(), solution_tree_data::solEdges, GRAPH::source, STP_Vectype, and Voronoi_data_structures::vnoi_base.

Referenced by connectivityDataInit().

◆ dfsorder()

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

static

recursive method for a DFS ordering of graph 'g'

Definition at line 633 of file heur_local.c.

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

Referenced by localKeyVertexHeuristics().

◆ getNewPrizeNode()

static SCIP_Real getNewPrizeNode	(	const GRAPH *	graph,
		const STP_Bool *	steinertree,
		const SCIP_Real *	prize_biased,
		const int *	graphmark,
		int	node,
		STP_Bool *	prizemark,
		int *	prizemarklist,
		int *	prizemarkcount
	)

inlinestatic

helper method for pcmwGetNewEdgePrize

Definition at line 659 of file heur_local.c.

References graph_pc_isPcMw(), Is_pseudoTerm, SCIP_Real, GRAPH::term, and TRUE.

Referenced by pcmwGetNewEdgePrize().

◆ pcmwGetSolRoot()

static int pcmwGetSolRoot	(	const GRAPH *	graph,
		const int *	solEdges
	)

static

gets root of solution for Pc/Mw or -1 otherwise

Definition at line 686 of file heur_local.c.

References CONNECT, GRAPH::cost, EAT_LAST, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, and GRAPH::term.

Referenced by localKeyVertexHeuristics().

◆ pcmwGetNewEdgePrize()

static SCIP_Real pcmwGetNewEdgePrize	(	const GRAPH *	graph,
		const STP_Bool *	steinertree,
		int	edge,
		PCMW *	pcmwData
	)

static

get prize not already counted that is associated to edge, not including solution nodes or forbidden ones

Parameters

graph	graph
steinertree	Steiner tree
edge	the edge
pcmwData	data

Definition at line 716 of file heur_local.c.

References getNewPrizeNode(), graph_pc_isPcMw(), GRAPH::head, pcmw_data::isActive, GRAPH::mark, pcmw_data::nprizemarks, pcmw_data::prize_biased, pcmw_data::prizemark, pcmw_data::prizemarklist, SCIP_Real, and GRAPH::tail.

Referenced by getBoundaryPathCostPrized(), and supergraphComputeMst().

◆ pcmwDataIsClean()

static SCIP_Bool pcmwDataIsClean	(	const GRAPH *	graph,
		const PCMW *	pcmwData
	)

static

is the data clean?

Parameters

graph	graph data structure
pcmwData	data

Definition at line 750 of file heur_local.c.

References FALSE, pcmw_data::isActive, GRAPH::knots, pcmw_data::nprizemarks, pcmw_data::prizemark, SCIPdebugMessage, and TRUE.

Referenced by getKeyPathReplaceCost(), pcmwDataClean(), and supergraphComputeMst().

◆ pcmwDataClean()

static void pcmwDataClean	(	const GRAPH *	graph,
		PCMW *	pcmwData
	)

static

clean the data

Parameters

graph	graph data structure
pcmwData	data

Definition at line 780 of file heur_local.c.

References FALSE, pcmw_data::isActive, pcmw_data::nprizemarks, pcmwDataIsClean(), pcmw_data::prizemark, and pcmw_data::prizemarklist.

Referenced by getKeyPathReplaceCost(), and supergraphComputeMst().

◆ pcmwUpdate()

static SCIP_RETCODE pcmwUpdate	(	SCIP *	scip,
		GRAPH *	graph,
		SOLTREE *	soltreeData,
		PCMW *	pcmwData
	)

static

updates for PC/MW: graph->mark and pinned

Parameters

scip	SCIP data structure
graph	graph data structure
soltreeData	solution tree data
pcmwData	data

Definition at line 804 of file heur_local.c.

References EAT_LAST, GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_trail_costAware(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, solution_tree_data::nodeIsPinned, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, solution_tree_data::solNodes, pcmw_data::solroot, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TRUE.

Referenced by localKeyVertexHeuristics().

◆ nodeIsCrucial()

static STP_Bool nodeIsCrucial	(	const GRAPH *	graph,
		const 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 Steiner tree)

Parameters

graph	graph data structure
steineredges	Steiner edges
node	node to check

Definition at line 863 of file heur_local.c.

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

Referenced by getKeyPathsStar(), getKeyPathUpper(), localKeyVertexHeuristics(), soltreeElimKeyPathsStar(), and soltreeExchangeKeyPath().

◆ getEdgeCostUnbiased()

static SCIP_Real getEdgeCostUnbiased	(	const GRAPH *	graph,
		const PCMW *	pcmwData,
		int	edge
	)

inlinestatic

gets unbiased edge cost

Parameters

graph	graph data structure
pcmwData	data
edge	edge

Definition at line 897 of file heur_local.c.

References GRAPH::cost, pcmw_data::edgecost_org, GRAPH::extended, graph_pc_isPc(), pcmw_data::isActive, SCIP_Real, STP_MWCSP, STP_RMWCSP, and GRAPH::stp_type.

Referenced by getBoundaryPathCost(), getKeyPathUpper(), and supergraphComputeMst().

◆ getBoundaryPathCost()

static SCIP_Real getBoundaryPathCost	(	const GRAPH *	graph,
		const VNOILOC *	vnoiData,
		const PCMW *	pcmwData,
		int	boundaryedge
	)

static

Get cost of shortest path along boundary edge. For Pc/Mw: Will consider biased edge costs, but not the actual prizes of proper terminals!

Parameters

graph	graph data structure
vnoiData	data
pcmwData	data
boundaryedge	boundary edge

Definition at line 937 of file heur_local.c.

References GRAPH::cost, shortest_path::dist, getEdgeCostUnbiased(), graph_pc_isPcMw(), GRAPH::head, pcmw_data::isActive, SCIP_Real, GRAPH::tail, Voronoi_data_structures::vnoi_base, and Voronoi_data_structures::vnoi_path.

Referenced by connectivityDataInit(), and getBoundaryPathCostPrized().

◆ getBoundaryPathCostPrized()

static SCIP_Real getBoundaryPathCostPrized	(	const GRAPH *	graph,
		const VNOILOC *	vnoiData,
		const SOLTREE *	soltreeData,
		int	boundaryedge,
		PCMW *	pcmwData
	)

static

For Pc/Mw: Consider biased edge costs, and the actual prizes of proper terminals!

Parameters

graph	graph data structure
vnoiData	data
soltreeData	solution tree data
boundaryedge	boundary edge
pcmwData	data

Definition at line 974 of file heur_local.c.

References shortest_path::edge, getBoundaryPathCost(), graph_edge_printInfo(), graph_pc_isPcMw(), GRAPH::head, pcmw_data::isActive, pcmwGetNewEdgePrize(), SCIP_Real, solution_tree_data::solNodes, GRAPH::tail, Voronoi_data_structures::vnoi_base, and Voronoi_data_structures::vnoi_path.

Referenced by getKeyPathReplaceCost(), and supergraphComputeMst().

◆ getEdgeCosts()

static const SCIP_Real* getEdgeCosts	(	const GRAPH *	graph,
		const PCMW *	pcmwData
	)

inlinestatic

returns edge costs (biased for Pc/Mw)

Parameters

graph	graph data structure
pcmwData	data

Definition at line 1033 of file heur_local.c.

References GRAPH::cost, pcmw_data::edgecost_biased, graph_pc_isPcMw(), and pcmw_data::isActive.

Referenced by getKeyPathsStar(), getKeyPathUpper(), supergraphComputeMst(), and vnoiDataRepairPreprocess().

◆ connectivityDataKeyElimUpdate()

static SCIP_RETCODE connectivityDataKeyElimUpdate	(	SCIP *	scip,
		const GRAPH *	graph,
		const VNOILOC *	vnoiData,
		const SGRAPH *	supergraphData,
		int	crucnode,
		CONN *	connectData
	)

static

update for key-vertex elimination: Save current boundary edges

Parameters

scip	SCIP data structure
graph	graph data structure
vnoiData	Voronoi data
supergraphData	super-graph
crucnode	node to eliminate
connectData	data

Definition at line 1046 of file heur_local.c.

References GRAPH::head, GRAPH::mark, supergraph_data::nodeIsLowSupernode, supergraph_data::nsupernodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPpairheapDeletemin(), SCIPpairheapInsert(), SCIPStpunionfindFind(), STP_Vectype, StpVecGetSize, supergraph_data::supernodes, GRAPH::tail, UNKNOWN, and Voronoi_data_structures::vnoi_base.

Referenced by localKeyVertexHeuristics().

◆ connectivityDataInit()

static SCIP_RETCODE connectivityDataInit	(	SCIP *	scip,
		const GRAPH *	graph,
		const VNOILOC *	vnoiData,
		const SOLTREE *	soltreeData,
		const PCMW *	pcmwData,
		CONN *	connectData
	)

static

initialize

Parameters

scip	SCIP data structure
graph	graph data structure
vnoiData	Voronoi data
soltreeData	solution tree data
pcmwData	data
connectData	data

Definition at line 1122 of file heur_local.c.

References BMSclearMemoryArray, CONNECT, EAT_FREE, GRAPH::edges, flipedge, getBoundaryPathCost(), getLowestCommonAncestors(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisGE(), SCIPpairheapInsert(), STP_Vectype, StpVecClear, StpVecPushBack, GRAPH::tail, UNKNOWN, and Voronoi_data_structures::vnoi_base.

Referenced by localKeyVertexHeuristics().

◆ getKeyPathUpper()

static void getKeyPathUpper	(	SCIP *	scip,
		int	crucnode,
		const GRAPH *	graph,
		const SOLTREE *	soltreeData,
		const PCMW *	pcmwData,
		CONN *	connectData,
		KPATHS *	keypathsData,
		SCIP_Bool *	allGood
	)

static

get key path above given crucial node

Parameters

scip	SCIP data structure
crucnode	crucial node to start from
graph	graph data structure
soltreeData	solution tree data
pcmwData	data
connectData	data
keypathsData	key paths
allGood	all good?

Definition at line 1201 of file heur_local.c.

References CONNECT, GRAPH::cost, EAT_LAST, link_cut_node::edge, FALSE, FARAWAY, flipedge, getEdgeCosts(), getEdgeCostUnbiased(), graph_edge_printInfo(), graph_pc_isPcMw(), GRAPH::head, Is_term, pcmw_data::isActive, keypaths_data_structures::kpcost, keypaths_data_structures::kpnodes, keypaths_data_structures::kptailnode, solution_tree_data::linkcutNodes, GRAPH::mark, keypaths_data_structures::nkpnodes, nodeIsCrucial(), solution_tree_data::nodeIsPinned, solution_tree_data::nodeIsScanned, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPisGE(), SCIPpairheapMeldheaps(), SCIPStpunionfindFind(), SCIPStpunionfindUnion(), solution_tree_data::solEdges, solution_tree_data::solNodes, GRAPH::source, GRAPH::tail, GRAPH::term, and UNKNOWN.

Referenced by localKeyVertexHeuristics().

◆ soltreeUnmarkKpNodes()

static void soltreeUnmarkKpNodes	(	const GRAPH *	graph,
		const KPATHS *	keypathsData,
		SOLTREE *	soltreeData
	)

static

unmarks key path nodes

Parameters

graph	graph data structure
keypathsData	key paths
soltreeData	solution tree data

Definition at line 1337 of file heur_local.c.

References FALSE, keypaths_data_structures::kpnodes, keypaths_data_structures::nkpnodes, and solution_tree_data::solNodes.

Referenced by supergraphComputeMst().

◆ soltreeMarkKpNodes()

static void soltreeMarkKpNodes	(	const GRAPH *	graph,
		const KPATHS *	keypathsData,
		SOLTREE *	soltreeData
	)

static

(re-)marks key path nodes

Parameters

graph	graph data structure
keypathsData	key paths
soltreeData	solution tree data

Definition at line 1361 of file heur_local.c.

References keypaths_data_structures::kpnodes, keypaths_data_structures::nkpnodes, solution_tree_data::solNodes, and TRUE.

Referenced by supergraphComputeMst().

◆ soltreeExchangeKeyPath()

static SCIP_RETCODE soltreeExchangeKeyPath	(	SCIP *	scip,
		GRAPH *	graph,
		const CONN *	connectData,
		const VNOILOC *	vnoiData,
		const KPATHS *	keypathsData,
		const int *	dfstree,
		const STP_Bool *	scanned,
		int	dfstree_pos,
		int	boundedge_new,
		SOLTREE *	soltreeData
	)

static

exchanges key path

Parameters

scip	SCIP data structure
graph	graph data structure
connectData	data
vnoiData	data
keypathsData	key paths
dfstree	DFS tree
scanned	array to mark which nodes have been scanned
dfstree_pos	current position in dfs tree
boundedge_new	new Voronoi boundary edge
soltreeData	solution tree data

Definition at line 1385 of file heur_local.c.

References CONNECT, EAT_LAST, link_cut_node::edge, shortest_path::edge, FALSE, flipedge, GRAPH::head, Is_term, keypaths_data_structures::kpnodes, keypaths_data_structures::kptailnode, solution_tree_data::linkcutNodes, GRAPH::mark, keypaths_data_structures::nkpnodes, nodeIsCrucial(), solution_tree_data::nodeIsPinned, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIPpairheapMeldheaps(), SCIPStpunionfindFind(), SCIPStpunionfindUnion(), solution_tree_data::solEdges, solution_tree_data::solNodes, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, Voronoi_data_structures::vnoi_base, and Voronoi_data_structures::vnoi_path.

Referenced by localKeyVertexHeuristics().

◆ soltreeElimKeyPathsStar()

static SCIP_RETCODE soltreeElimKeyPathsStar	(	SCIP *	scip,
		const GRAPH *	graph,
		const CONN *	connectData,
		const VNOILOC *	vnoiData,
		const KPATHS *	keypathsData,
		const SGRAPH *	supergraphData,
		const int *	dfstree,
		const STP_Bool *	scanned,
		int	dfstree_pos,
		SOLTREE *	soltreeData
	)

static

exchanges key-paths star

Parameters

scip	SCIP data structure
graph	graph data structure
connectData	data
vnoiData	data
keypathsData	key paths
supergraphData	super-graph
dfstree	DFS tree
scanned	array to mark which nodes have been scanned
dfstree_pos	current position in dfs tree
soltreeData	solution tree data

Definition at line 1534 of file heur_local.c.

References CONNECT, EAT_LAST, link_cut_node::edge, shortest_path::edge, FALSE, flipedge, GRAPH::head, Is_term, keypaths_data_structures::kpedges, keypaths_data_structures::kpnodes, solution_tree_data::linkcutNodes, GRAPH::mark, supergraph_data::mst, keypaths_data_structures::nkpedges, keypaths_data_structures::nkpnodes, nodeIsCrucial(), supergraph_data::nodeIsLowSupernode, solution_tree_data::nodeIsPinned, supergraph_data::nsupernodes, GRAPH::oeat, GRAPH::outbeg, keypaths_data_structures::rootpathstart, SCIP_OKAY, SCIPpairheapMeldheaps(), SCIPStpunionfindFind(), SCIPStpunionfindUnion(), solution_tree_data::solEdges, solution_tree_data::solNodes, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, Voronoi_data_structures::vnoi_base, and Voronoi_data_structures::vnoi_path.

Referenced by localKeyVertexHeuristics().

◆ getKeyPathReplaceCost()

static SCIP_Real getKeyPathReplaceCost	(	SCIP *	scip,
		const GRAPH *	graph,
		const VNOILOC *	vnoiData,
		const SOLTREE *	soltreeData,
		SCIP_Real	edgecost_old_in,
		int	boundedge_old,
		PCMW *	pcmwData,
		int *	boundedge_new
	)

static

compute cost of alternative key path

Parameters

scip	SCIP data structure
graph	graph data structure
vnoiData	data
soltreeData	solution tree data
edgecost_old_in	edge cost of old edge
boundedge_old	Voronoi boundary edge
pcmwData	data
boundedge_new	new Voronoi boundary edge (in/out)

Definition at line 1732 of file heur_local.c.

References FARAWAY, getBoundaryPathCostPrized(), graph_pc_isPcMw(), GRAPH::head, pcmwDataClean(), pcmwDataIsClean(), SCIP_Real, SCIPdebugMessage, SCIPisLE(), SCIPisLT(), GRAPH::source, and UNKNOWN.

Referenced by localKeyVertexHeuristics().

◆ supergraphDataRestore()

static void supergraphDataRestore	(	const GRAPH *	graph,
		SGRAPH *	supergraphData
	)

static

restore supergraph data

Parameters

graph	graph data structure
supergraphData	super-graph

Definition at line 1791 of file heur_local.c.

References FALSE, GRAPH::knots, supergraph_data::mst, supergraph_data::nodeIsLowSupernode, supergraph_data::nsupernodes, SCIPfreeMemoryArray, and supergraph_data::supernodes.

Referenced by localKeyVertexHeuristics().

◆ supergraphComputeMst()

static SCIP_RETCODE supergraphComputeMst	(	SCIP *	scip,
		const GRAPH *	graph,
		const CONN *	connectData,
		const VNOILOC *	vnoiData,
		const KPATHS *	keypathsData,
		int	crucnode,
		SOLTREE *	soltreeData,
		PCMW *	pcmwData,
		SGRAPH *	supergraphData
	)

static

compute minimum-spanning tree

Parameters

scip	SCIP data structure
graph	graph data structure
connectData	data
vnoiData	data
keypathsData	key paths
crucnode	node to eliminate
soltreeData	solution tree data
pcmwData	data
supergraphData	super-graph

Definition at line 1813 of file heur_local.c.

References GRAPH::cost, shortest_path::edge, flipedge, getBoundaryPathCostPrized(), getEdgeCosts(), getEdgeCostUnbiased(), graph_edge_add(), graph_edge_printInfo(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_pc_isPcMw(), GRAPH::head, pcmw_data::isActive, GRAPH::knots, supergraph_data::mst, MST_MODE, supergraph_data::mstcost, solution_tree_data::newedges, nnodes, supergraph_data::nodeIsLowSupernode, supergraph_data::nsupernodes, NULL, pcmwDataClean(), pcmwDataIsClean(), pcmwGetNewEdgePrize(), GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPStpunionfindFind(), solution_tree_data::solNodes, soltreeMarkKpNodes(), soltreeUnmarkKpNodes(), STP_SPG, GRAPH::stp_type, supergraph_data::supernodes, GRAPH::tail, GRAPH::term, TRUE, Voronoi_data_structures::vnoi_base, and Voronoi_data_structures::vnoi_path.

Referenced by localKeyVertexHeuristics().

◆ getKeyPathsStar()

static void getKeyPathsStar	(	int	keyvertex,
		const GRAPH *	graph,
		const CONN *	connectData,
		const SOLTREE *	soltreeData,
		const PCMW *	pcmwData,
		KPATHS *	keypathsData,
		SGRAPH *	supergraphData,
		SCIP_Bool *	success
	)

static

get the key-paths star starting from 'keyvertex'

Parameters

keyvertex	key vertex to start from
graph	graph data structure
connectData	data
soltreeData	solution tree data
pcmwData	data
keypathsData	key paths
supergraphData	super-graph
success	success?

Definition at line 1992 of file heur_local.c.

References CONNECT, EAT_LAST, link_cut_node::edge, FALSE, flipedge, getEdgeCosts(), graph_edge_printInfo(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, pcmw_data::isActive, keypaths_data_structures::kpcost, keypaths_data_structures::kpedges, keypaths_data_structures::kpnodes, solution_tree_data::linkcutNodes, keypaths_data_structures::nkpedges, keypaths_data_structures::nkpnodes, nodeIsCrucial(), supergraph_data::nodeIsLowSupernode, solution_tree_data::nodeIsPinned, supergraph_data::nsupernodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, keypaths_data_structures::rootpathstart, SCIP_Real, SCIPStpunionfindUnion(), solution_tree_data::solEdges, solution_tree_data::solNodes, supergraph_data::supernodes, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by localKeyVertexHeuristics().

◆ vnoiDataRepairPreprocess()

static void vnoiDataRepairPreprocess	(	SCIP *	scip,
		const GRAPH *	graph,
		const KPATHS *	keypathsData,
		const CONN *	connectData,
		const PCMW *	pcmwData,
		VNOILOC *	vnoiData,
		int *	nheapelems
	)

static

preprocessing for Voronoi repair method

Parameters

scip	SCIP data structure
graph	graph data structure
keypathsData	key paths
connectData	base lists
pcmwData	data
vnoiData	data
nheapelems	to store

Definition at line 2197 of file heur_local.c.

References CONNECT, shortest_path::dist, EAT_LAST, shortest_path::edge, getEdgeCosts(), graph_knot_isInRange(), graph_pathHeapAdd(), GRAPH::ieat, GRAPH::inpbeg, keypaths_data_structures::kpnodes, GRAPH::mark, keypaths_data_structures::nkpnodes, NULL, GRAPH::path_heap, SCIP_Real, SCIPisGT(), STP_Vectype, StpVecGetSize, GRAPH::tail, UNKNOWN, Voronoi_data_structures::vnoi_base, Voronoi_data_structures::vnoi_nodestate, and Voronoi_data_structures::vnoi_path.

Referenced by localKeyVertexHeuristics().

◆ vnoiDataRestore()

static void vnoiDataRestore	(	const CONN *	connectData,
		const KPATHS *	keypathsData,
		VNOILOC *	vnoiData
	)

static

restore data

Parameters

connectData	base lists
keypathsData	key paths
vnoiData	data

Definition at line 2264 of file heur_local.c.

References shortest_path::dist, shortest_path::edge, keypaths_data_structures::kpnodes, Voronoi_data_structures::meminedges, Voronoi_data_structures::memvbase, Voronoi_data_structures::memvdist, Voronoi_data_structures::nkpnodes, keypaths_data_structures::nkpnodes, Voronoi_data_structures::nmems, SCIP_Real, STP_Vectype, StpVecGetSize, Voronoi_data_structures::vnoi_base, and Voronoi_data_structures::vnoi_path.

Referenced by localKeyVertexHeuristics().

◆ vnoiDataReset()

static void vnoiDataReset	(	const CONN *	connectData,
		const KPATHS *	keypathsData,
		const int *	graphmark,
		VNOILOC *	vnoiData
	)

static

reset data

Parameters

connectData	base lists
keypathsData	key paths
graphmark	graph mark
vnoiData	data

Definition at line 2302 of file heur_local.c.

References shortest_path::dist, shortest_path::edge, FARAWAY, keypaths_data_structures::kpnodes, Voronoi_data_structures::meminedges, Voronoi_data_structures::memvbase, Voronoi_data_structures::memvdist, Voronoi_data_structures::nkpnodes, keypaths_data_structures::nkpnodes, Voronoi_data_structures::nmems, SCIP_Real, STP_Vectype, StpVecGetSize, UNKNOWN, Voronoi_data_structures::vnoi_base, Voronoi_data_structures::vnoi_nodestate, and Voronoi_data_structures::vnoi_path.

Referenced by localKeyVertexHeuristics().

◆ solDegIsValid()

static SCIP_Bool solDegIsValid	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	solDegree,
		const LCNODE *	linkcutNodes
	)

static

Parameters

scip	SCIP data structure
graph	graph data structure
solDegree	solution degree
linkcutNodes	Steiner tree nodes

Definition at line 2354 of file heur_local.c.

References BMSclearMemoryArray, link_cut_node::edge, FALSE, graph_knot_printInfo(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by localVertexInsertion().

◆ solNodeIsValid()

static SCIP_Bool solNodeIsValid	(	SCIP *	scip,
		const GRAPH *	graph,
		const STP_Bool *	solNodes,
		const LCNODE *	linkcutNodes
	)

static

Parameters

scip	SCIP data structure
graph	graph data structure
solNodes	Steiner tree nodes
linkcutNodes	Steiner tree nodes

Definition at line 2411 of file heur_local.c.

References link_cut_node::edge, FALSE, GRAPH::head, GRAPH::knots, nnodes, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, and TRUE.

Referenced by localVertexInsertion().

◆ insertionDecrementSolDegree()

static void insertionDecrementSolDegree	(	const GRAPH *	graph,
		int	node,
		INSERT *	insertData
	)

inlinestatic

reduces solution degree

Parameters

graph	graph data structure
node	replacement edge
insertData	insertion data

Definition at line 2460 of file heur_local.c.

References Is_pseudoTerm, Is_term, insertion_data::solDegreeNonTerm, insertion_data::solNodes, GRAPH::term, and UNKNOWN.

Referenced by insertionReplaceChain(), and insertionRestoreTree().

◆ insertionIncrementSolDegree()

static void insertionIncrementSolDegree	(	const GRAPH *	graph,
		int	node,
		INSERT *	insertData
	)

inlinestatic

increases solution degree

Parameters

graph	graph data structure
node	replacement edge
insertData	insertion data

Definition at line 2486 of file heur_local.c.

References Is_pseudoTerm, Is_term, insertion_data::solDegreeNonTerm, insertion_data::solNodes, GRAPH::term, and UNKNOWN.

Referenced by insertionInitInsert(), insertionReplaceChain(), and insertionRestoreTree().

◆ insertionInit()

static void insertionInit	(	SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		const int *	solEdges,
		int *	solDegreeNonTerm,
		SCIP_Bool *	nodeIsBlocked,
		int *	vertices
	)

static

subroutine for insertion heuristic

Parameters

heurdata	heuristic data
graph	graph data structure
solEdges	Steiner tree edges
solDegreeNonTerm	degree
nodeIsBlocked	blocked
vertices	vertices permuted

Definition at line 2509 of file heur_local.c.

References BMSclearMemoryArray, CONNECT, GRAPH::edges, FALSE, GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, SCIPrandomPermuteIntArray(), GRAPH::tail, GRAPH::term, and UNKNOWN.

Referenced by localVertexInsertion().

◆ insertionInitInsert()

static void insertionInitInsert	(	SCIP *	scip,
		const GRAPH *	graph,
		int	v_insert,
		int	initialEdge,
		LCNODE *	linkcutNodes,
		INSERT *	insertData,
		SCIP_Real *	diff
	)

static

subroutine for insertion heuristic: prepare insertion of new vertex

Parameters

scip	SCIP data structure
graph	graph data structure
v_insert	the vertex to add
initialEdge	first edge from node to tree
linkcutNodes	Steiner tree nodes
insertData	insertion data (in/out)
diff	the initial diff (out)

Definition at line 2548 of file heur_local.c.

References insertion_data::edgecosts, graph_pc_isPc(), graph_pc_isPcMw(), GRAPH::head, insertionIncrementSolDegree(), insertion_data::insertionVertex, Is_term, insertion_data::nInsertions, insertion_data::nodeIsBlocked, GRAPH::prize, SCIP_Bool, SCIPdebugMessage, SCIPisPositive(), SCIPlinkcuttreeLink(), insertion_data::solDegreeNonTerm, insertion_data::solNodes, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by localVertexInsertion().

◆ insertionFinalizeReplacement()

static void insertionFinalizeReplacement	(	const GRAPH *	graph,
		int	v_insert,
		LCNODE *	linkcutNodes,
		INSERT *	insertData
	)

static

remove (blocked) chains from tree

Parameters

graph	graph data structure
v_insert	the vertex to insert
linkcutNodes	Steiner tree nodes
insertData	insertion data

Definition at line 2601 of file heur_local.c.

References insertion_data::blockedList, insertion_data::blockedListSize, FALSE, Is_pseudoTerm, Is_term, GRAPH::knots, insertion_data::nodeIsBlocked, SCIP_Bool, SCIPlinkcuttreeInitNode(), insertion_data::solDegreeNonTerm, insertion_data::solNodes, GRAPH::term, and UNKNOWN.

Referenced by localVertexInsertion().

◆ insertionResetBlockedNodes()

static void insertionResetBlockedNodes ( INSERT * insertData )

inlinestatic

remove (blocked) chains from tree

Parameters

insertData insertion data

Definition at line 2652 of file heur_local.c.

References insertion_data::blockedList, insertion_data::blockedListSize, FALSE, insertion_data::insertionVertex, insertion_data::nodeIsBlocked, SCIP_Bool, and insertion_data::solDegreeNonTerm.

Referenced by insertionRestoreTree().

◆ insertionBlockChain()

static void insertionBlockChain	(	const GRAPH *	graph,
		const LCNODE *	lctree,
		int	chainfirst_index,
		int	chainlast_index,
		INSERT *	insertData
	)

inlinestatic

mark inner chain nodes as blocked

Parameters

graph	graph data structure
lctree	tree
chainfirst_index	first chain entry
chainlast_index	last chain entry (inside)
insertData	insertion data

Definition at line 2678 of file heur_local.c.

References insertion_data::blockedList, insertion_data::blockedListSize, link_cut_node::edge, GRAPH::head, insertion_data::nodeIsBlocked, link_cut_node::parent, SCIP_Bool, and TRUE.

Referenced by insertionReplaceChain().

◆ insertionRestoreTree()

static void insertionRestoreTree	(	const GRAPH *	graph,
		const int *	insertCands,
		int	lcvertex_insert,
		LCNODE *	linkcutNodes,
		INSERT *	insertData
	)

static

reinsert (blocked) chains to tree

Parameters

graph	graph data structure
insertCands	insertion candidates
lcvertex_insert	the vertex tested for insertion
linkcutNodes	Steiner tree nodes
insertData	insertion data

Definition at line 2711 of file heur_local.c.

References insertion_data::addedEdges, insertion_data::blockedListSize, insertion_data::chainEnds, insertion_data::chainStarts, insertion_data::cutedgesEnd, insertion_data::cutedgesStart, FALSE, graph_pc_isPcMw(), GRAPH::head, insertionDecrementSolDegree(), insertionIncrementSolDegree(), insertionResetBlockedNodes(), insertion_data::insertionVertex, Is_pseudoTerm, Is_term, GRAPH::knots, insertion_data::nInsertions, insertion_data::nodeIsBlocked, SCIPlinkcuttreeCutNode(), SCIPlinkcuttreeEvert(), SCIPlinkcuttreeLink(), insertion_data::solDegreeNonTerm, insertion_data::solNodes, GRAPH::tail, GRAPH::term, and UNKNOWN.

Referenced by localVertexInsertion().

◆ insertionReplaceChain()

static void insertionReplaceChain	(	const GRAPH *	graph,
		int	newedge,
		LCNODE *	lctree,
		INSERT *	insertData,
		int	v_lc,
		int	headCurr_lc,
		int	chainfirst_index,
		int	chainlast_index
	)

static

replaces chain by a single edge

Parameters

graph	graph data structure
newedge	replacement edge
lctree	tree
insertData	insertion data
v_lc	current vertex
headCurr_lc	head of newedge
chainfirst_index	first chain entry
chainlast_index	last chain entry (inside)

Definition at line 2787 of file heur_local.c.

References insertion_data::addedEdges, insertion_data::chainEnds, insertion_data::chainStarts, insertion_data::cutedgesEnd, insertion_data::cutedgesStart, link_cut_node::edge, GRAPH::head, insertionBlockChain(), insertionDecrementSolDegree(), insertionIncrementSolDegree(), insertion_data::insertionVertex, insertion_data::nInsertions, SCIPdebugMessage, SCIPlinkcuttreeCutNode(), SCIPlinkcuttreeLink(), and GRAPH::tail.

Referenced by localVertexInsertion().

◆ insertionGetCandidateEdges()

static void insertionGetCandidateEdges	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		const STP_Bool *	solNodes,
		int	vertex,
		int *	insertcands,
		int *	ncands
	)

static

perform local vertex insertion heuristic on given Steiner tree

Parameters

scip	SCIP data structure
heurdata	heuristic data
graph	graph data structure
solNodes	Steiner tree nodes
vertex	vertex to be inserted
insertcands	candidates
ncands	number of candidates

Definition at line 2841 of file heur_local.c.

References GRAPH::cost, EAT_LAST, FARAWAY, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPisLT(), SCIPrandomPermuteIntArray(), GRAPH::source, and GRAPH::term.

Referenced by localVertexInsertion().

◆ localVertexInsertion()

static SCIP_RETCODE localVertexInsertion	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		STP_Bool *	solNodes,
		LCNODE *	linkcutNodes,
		int *	solEdges
	)

static

perform local vertex insertion heuristic on given Steiner tree

Parameters

scip	SCIP data structure
heurdata	heuristic data or NULL
graph	graph data structure
solNodes	Steiner tree nodes
linkcutNodes	Steiner tree nodes
solEdges	array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)

Definition at line 2890 of file heur_local.c.

References CONNECT, GRAPH::cost, link_cut_node::edge, GRAPH::edges, FALSE, flipedge, GRAPH::grad, graph_pc_getOrgCosts(), graph_pc_isPc(), graph_pc_isPcMw(), GRAPH::head, insertData(), insertionFinalizeReplacement(), insertionGetCandidateEdges(), insertionInit(), insertionInitInsert(), insertionReplaceChain(), insertionRestoreTree(), Is_term, GRAPH::knots, nnodes, NULL, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPlinkcuttreeEvert(), SCIPlinkcuttreeFindMaxChain(), SCIPlinkcuttreeFindMinChainMw(), SCIPlinkcuttreeInitNode(), SCIPlinkcuttreeLink(), solDegIsValid(), solNodeIsValid(), solstp_getObjBounded(), solstp_isValid(), solstp_prune(), GRAPH::source, STP_GSTP, STP_MWCSP, STP_OARSMT, STP_RMWCSP, STP_RSMT, STP_SPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by localRun().

◆ localKeyVertexHeuristics()

static SCIP_RETCODE localKeyVertexHeuristics	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Bool	useFast,
		STP_Bool *	solNodes,
		LCNODE *	linkcutNodes,
		int *	solEdges,
		SCIP_Bool *	success
	)

static

perform local vertex insertion heuristic on given Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
useFast	fast variant?
solNodes	Steiner tree nodes
linkcutNodes	Steiner tree nodes
solEdges	array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
success	solution improved?

Definition at line 3131 of file heur_local.c.

References BMSclearMemoryArray, BMScopyMemoryArray, CONNECT, connectivityDataInit(), connectivityDataKeyElimUpdate(), GRAPH::cost, dfsorder(), link_cut_node::edge, pcmw_data::edgecost_biased, pcmw_data::edgecost_org, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge, getKeyPathReplaceCost(), getKeyPathsStar(), getKeyPathUpper(), GRAPH::grad, graph_pc_getBiased(), graph_pc_getOrgCosts(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_voronoi(), graph_voronoiRepair(), graph_voronoiRepairMult(), GRAPH::head, Is_term, pcmw_data::isActive, GRAPH::knots, keypaths_data_structures::kpcost, keypaths_data_structures::kpnodes, LOCAL_MAXRESTARTS, LOCAL_MAXRESTARTS_FAST, GRAPH::mark, supergraph_data::mstcost, UnionFind_Structure::nElements, keypaths_data_structures::nkpnodes, nnodes, nodeIsCrucial(), supergraph_data::nsupernodes, NULL, GRAPH::path_state, pcmwGetSolRoot(), pcmwUpdate(), GRAPH::prize, pcmw_data::prize_biased, keypaths_data_structures::rootpathstart, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeMemoryArray, SCIPisLE(), SCIPisLT(), SCIPlinkcuttreeInitNode(), SCIPlinkcuttreeLink(), SCIPpairheapDeletemin(), SCIPpairheapFree(), SCIPpairheapInsert(), SCIPpairheapMeldheaps(), SCIPStpunionfindClear(), SCIPStpunionfindFind(), SCIPStpunionfindFreeMembers(), SCIPStpunionfindInit(), SCIPStpunionfindUnion(), solution_tree_data::solNodes, solstp_getObjBounded(), solstp_pruneFromEdges(), soltreeElimKeyPathsStar(), soltreeExchangeKeyPath(), GRAPH::source, STP_Vectype, StpVecFree, supergraphComputeMst(), supergraphDataRestore(), supergraph_data::supernodes, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, Voronoi_data_structures::vnoi_base, Voronoi_data_structures::vnoi_path, vnoiDataRepairPreprocess(), vnoiDataReset(), and vnoiDataRestore().

Referenced by localRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyLocal )

static

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

Definition at line 3607 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 3621 of file heur_local.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeRandom(), 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 3643 of file heur_local.c.

References 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 3669 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 3689 of file heur_local.c.

References DEFAULT_NELITESOLS, GRAPH::edges, graph_pc_isPcMw(), HEUR_NAME, initSolNumberBounds(), NULL, probtypeIsValidForLocal(), SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPgetProbData(), SCIPgetSols(), SCIPheurGetData(), SCIPheurGetName(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetVars(), SCIPsolGetHeur(), SCIPsolGetIndex(), SCIPStpHeurLocalExtendPcMwImp(), SCIPStpHeurLocalRun(), solAddTry(), solGetStpSol(), solNeedsPruning(), solPrune(), solstp_getObjBounded(), and solstp_isValid().

◆ localRun()

static SCIP_RETCODE localRun	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Bool	useFast,
		int *	solEdges
	)

static

perform local heuristics on a given Steiner tree

Parameters

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

Definition at line 3815 of file heur_local.c.

References GRAPH::cost, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), graph_valid(), GRAPH::knots, localKeyVertexHeuristics(), localVertexInsertion(), markSolTreeNodes(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfindHeur(), SCIPfreeBufferArray, SCIPheurGetData(), SCIPisLE(), SCIPisStopped(), SCIPStpHeurLocalExtendPcMw(), solIsTrivialPcMw(), solstp_getObjBounded(), solstp_isValid(), GRAPH::source, and GRAPH::terms.

Referenced by SCIPStpHeurLocalRun(), and SCIPStpHeurLocalRunFast().

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

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

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.

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

SCIP

Detailed Description

Data Structures

Macros

Typedefs

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_NBESTSOLS_HARD

◆ DEFAULT_NELITESOLS

◆ DEFAULT_MINNBESTSOLS

◆ DEFAULT_MINNBESTSOLS_HARD

◆ DEFAULT_RANDSEED

◆ LOCAL_MAXRESTARTS

◆ LOCAL_MAXRESTARTS_FAST

◆ GREEDY_MAXRESTARTS

◆ GREEDY_EXTENSIONS_MW

◆ GREEDY_EXTENSIONS

Typedef Documentation

◆ VNOILOC

◆ CONN

◆ KPATHS

◆ SOLTREE

◆ SGRAPH

◆ PCMW

◆ INSERT

Function Documentation

◆ solNeedsPruning()

◆ solPrune()

◆ solGetStpSol()

◆ initSolNumberBounds()

◆ solAddTry()

◆ probtypeIsValidForLocal()

◆ addToCandidates()

◆ markSolTreeNodes()

◆ solIsTrivialPcMw()

◆ lca()

◆ getLowestCommonAncestors()

◆ dfsorder()

◆ getNewPrizeNode()

◆ pcmwGetSolRoot()

◆ pcmwGetNewEdgePrize()

◆ pcmwDataIsClean()

◆ pcmwDataClean()

◆ pcmwUpdate()

◆ nodeIsCrucial()

◆ getEdgeCostUnbiased()

◆ getBoundaryPathCost()

◆ getBoundaryPathCostPrized()

◆ getEdgeCosts()

◆ connectivityDataKeyElimUpdate()

◆ connectivityDataInit()

◆ getKeyPathUpper()

◆ soltreeUnmarkKpNodes()

◆ soltreeMarkKpNodes()

◆ soltreeExchangeKeyPath()

◆ soltreeElimKeyPathsStar()

◆ getKeyPathReplaceCost()

◆ supergraphDataRestore()

◆ supergraphComputeMst()

◆ getKeyPathsStar()

◆ vnoiDataRepairPreprocess()

◆ vnoiDataRestore()

◆ vnoiDataReset()

◆ solDegIsValid()

◆ solNodeIsValid()

◆ insertionDecrementSolDegree()

◆ insertionIncrementSolDegree()