Detailed Description

Shortest paths based primal heuristics for Steiner problems.

Author: Gerald Gamrath; Thorsten Koch; Daniel Rehfeldt; Michael Winkler

This file implements several shortest paths based primal heuristics for Steiner problems, see "SCIP-Jack - A solver for STP and variants with parallelization extensions" by Gamrath, Koch, Maher, Rehfeldt and Shinano and "Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem" by Rehfeldt and Koch

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

Definition in file heur_tm.c.

#include <assert.h>
#include <string.h>
#include "heur_tm.h"
#include "relax_stp.h"
#include "probdata_stp.h"
#include "portab.h"
#include "solstp.h"
#include "scip/misc.h"
#include "shortestpath.h"
#include "reduce.h"
#include <math.h>

Go to the source code of this file.

Data Structures
struct	TM_base_data

struct	TM_all_shortestpath

struct	TM_voronoi

Macros
#define	HEUR_NAME "TM"

#define	HEUR_DESC "shortest path based primal heuristics for Steiner trees"

#define	HEUR_DISPCHAR '+'

#define	HEUR_PRIORITY 10000000

#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_EVALRUNS 20

#define	DEFAULT_INITRUNS 100

#define	DEFAULT_LEAFRUNS 25

#define	DEFAULT_HARD_RUNSMULT 1.75

#define	DEFAULT_ROOTRUNS 50

#define	DEFAULT_DURINGLPFREQ 5

#define	DEFAULT_TYPE 0

#define	DEFAULT_PCMODE 4

#define	DEFAULT_RANDSEED 5

#define	TM_HARD_MAXNEDGES 15000

#define	AUTO 0

#define	TM_SP 1

#define	TM_VORONOI 2

#define	TM_DIJKSTRA 3

#define	TM_USE_CSR

#define	TM_USE_CSR_PCMW

Typedefs
typedef struct TM_base_data	TMBASE

typedef struct TM_all_shortestpath	TMALLSP

typedef struct TM_voronoi	TMVNOI

Functions
static SCIP_Bool	pcmwUpdateBestSol_csrInSync (SCIP scip, const GRAPH graph, const TMBASE *tmbase)

static	SCIP_DECL_PARAMCHGD (paramChgdRandomseed)

static SCIP_RETCODE	tmBaseInit (SCIP scip, const GRAPH graph, TMBASE *tmbase)

static void	tmBaseFree (SCIP scip, const GRAPH graph, TMBASE *tmbase)

static SCIP_RETCODE	tmAllspInit (SCIP scip, const GRAPH graph, TMALLSP *tmallsp)

static void	tmAllspFree (SCIP scip, const GRAPH graph, TMALLSP *tmallsp)

static SCIP_RETCODE	tmVnoiInit (SCIP scip, const GRAPH graph, TMVNOI *tmvnoi)

static void	tmVnoiFree (SCIP scip, const GRAPH graph, TMVNOI *tmvnoi)

static SCIP_HEURDATA *	getTMheurData (SCIP *scip)

static SCIP_Real	getTmEdgeCostZeroOffset (SCIP scip, const GRAPH graph)

static SCIP_Bool	isTMSpType (const GRAPH *graph)

static int	getTmMode (SCIP_HEURDATA heurdata, const GRAPH graph)

static void	updateBestSol (SCIP scip, const GRAPH graph, int startnode, SCIP_Bool solfound, TMBASE tmbase, SCIP_Bool success)

static void	pcmwUpdateBestSol (SCIP scip, const GRAPH graph, TMBASE tmbase, SCIP_Bool success)

static void	pcmwAdaptStarts (SCIP_HEURDATA heurdata, const GRAPH graph, int maxtmruns, int bestincstart, int *terminalperm)

static SCIP_RETCODE	pcmwGetStartNodes (SCIP scip, const SCIP_Real nodepriority, int maxtmruns, int bestincstart, GRAPH graph, int terminalperm)

static void	pcmwSetEdgeCosts (const GRAPH graph, const SCIP_Real cost, const SCIP_Real costorg, const SCIP_Real costfullbiased, enum PCMW_TmMode pcmwmode, TMBASE *tmbase)

static SCIP_RETCODE	computeStarts (SCIP scip, const GRAPH graph, const int orgstarts, SCIP_Bool startsgiven, SCIP_Real nodepriority, TMBASE tmbase, int bestp)

static void	keyNodesSetTerms (SCIP scip, const int soledge, GRAPH g, int solnodes_degree)

static void	keyNodesResetTerms (const int solnodes_degree, GRAPH g)

static SCIP_RETCODE	computeSteinerTreeCsr (SCIP scip, const GRAPH g, int startnode, TMBASE *tmbase)

static SCIP_RETCODE	computeSteinerTreeKeyNodesCsr (SCIP scip, GRAPH g, int startnode, TMBASE *tmbase)

static SCIP_RETCODE	computeSteinerTreeDijk (SCIP scip, GRAPH g, int start, TMBASE *tmbase)

static SCIP_RETCODE	computeSteinerTreeDijkBMw (SCIP scip, GRAPH g, const SCIP_Real cost_org, const SCIP_Real prize, int start, TMBASE tmbase, SCIP_Bool solfound)

static SCIP_RETCODE	computeSteinerTreeDijkPcMw (SCIP scip, GRAPH g, const SCIP_Real cost_org, const SCIP_Real prize, SCIP_Bool costsAreBiased, int start, SPATHSPC sppc, TMBASE tmbase)

static SCIP_RETCODE	computeSteinerTreeDijkPcMwFull (SCIP scip, GRAPH g, const SCIP_Real cost_org, int start, TMBASE tmbase)

static SCIP_RETCODE	computeSteinerTree (SCIP scip, const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, int start, int result, TMALLSP tmallsp, STP_Bool connected, SCIP_RANDNUMGEN randnumgen)

static void	computeSteinerTreeSingleNode (const GRAPH graph, int node, TMBASE tmbase, SCIP_Bool *success)

static SCIP_RETCODE	computeDegConsTree (SCIP scip, const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, int start, int result, TMALLSP tmallsp, SCIP_RANDNUMGEN randnumgen, STP_Bool connected, STP_Bool *solfound)

static SCIP_RETCODE	computeSteinerTreeVnoi (SCIP scip, const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, int start, STP_Bool firstrun, TMVNOI tmvnoi, int result, STP_Bool *connected)

static void	tmLpGetEdgeRandomizations (SCIP scip, SCIP_HEURDATA heurdata, const GRAPH graph, SCIP_Bool partrand, SCIP_Bool *totalrand)

static void	initCostsAndPrioLP (SCIP scip, SCIP_HEURDATA heurdata, SCIP_VAR *vars, const GRAPH graph, SCIP_Real randupper, SCIP_Real randlower, const SCIP_Real xval, SCIP_Real RESTRICT nodepriority, SCIP_Real RESTRICT prize, SCIP_Real RESTRICT cost)

static void	buildTmAllSp (SCIP scip, const GRAPH graph, const SCIP_Real cost, const SCIP_Real costrev, TMALLSP *tmallsp)

static SCIP_RETCODE	dhcstpWarmUp (SCIP scip, GRAPH graph, SCIP_Real cost, SCIP_Real costrev, SCIP_Real hopfactor, TMBASE tmbase, SCIP_Bool *success)

static SCIP_RETCODE	runTm (SCIP scip, GRAPH graph, TMBASE tmbase, TMALLSP tmallsp, TMVNOI tmvnoi, SCIP_Bool success)

static SCIP_RETCODE	runTmPcMW_mode (SCIP scip, GRAPH graph, const SCIP_Real cost, const SCIP_Real prize, enum PCMW_TmMode pcmwmode, int bestincstart, SCIP_Real nodepriority, TMBASE tmbase, SCIP_Bool *success)

static SCIP_RETCODE	runTmPcMW (SCIP scip, GRAPH graph, const SCIP_Real cost, const SCIP_Real prize, enum PCMW_TmMode pcmw_tmmode, int beststart, SCIP_Real nodepriority, TMBASE tmbase, SCIP_Bool *success)

static SCIP_RETCODE	runTmDhcstp (SCIP scip, GRAPH graph, TMBASE tmbase, TMALLSP tmallsp, TMVNOI tmvnoi, SCIP_Real hopfactor, SCIP_Bool *success)

static	SCIP_DECL_HEURCOPY (heurCopyTM)

static	SCIP_DECL_HEURFREE (heurFreeTM)

static	SCIP_DECL_HEURINIT (heurInitTM)

static	SCIP_DECL_HEUREXEC (heurExecTM)

void	SCIPStpHeurTMCompStarts (GRAPH graph, int starts, int *runs)

void	SCIPStpHeurTMBuildTree (SCIP scip, GRAPH g, PATH mst, const SCIP_Real cost, SCIP_Real objresult, int connected)

SCIP_RETCODE	SCIPStpHeurTMBuildTreePcMw (SCIP scip, const GRAPH g, SCIP_Bool useRootSym, PATH mst, const SCIP_Real cost, SCIP_Real objresult, int connected)

SCIP_RETCODE	SCIPStpHeurTMBuildTreeDc (SCIP scip, const GRAPH g, int result, STP_Bool connected)

SCIP_RETCODE	SCIPStpHeurTMRun (SCIP scip, enum PCMW_TmMode pcmw_tmmode, GRAPH graph, int starts, const SCIP_Real prize, int best_result, int runs, int bestincstart, SCIP_Real cost, SCIP_Real costrev, SCIP_Real hopfactor, SCIP_Real nodepriority, SCIP_Bool success)

SCIP_RETCODE	SCIPStpHeurTMRunLP (SCIP scip, GRAPH graph, SCIP_HEUR heur, int result, int runs, SCIP_Bool *success)

SCIP_RETCODE	SCIPStpIncludeHeurTM (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "TM"

Definition at line 49 of file heur_tm.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURFREE(), SCIP_DECL_HEURINIT(), and SCIPStpIncludeHeurTM().

◆ HEUR_DESC

#define HEUR_DESC "shortest path based primal heuristics for Steiner trees"

Definition at line 50 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR '+'

Definition at line 51 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 10000000

Definition at line 52 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 53 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 54 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 55 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_TIMING

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

Definition at line 56 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 57 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_EVALRUNS

#define DEFAULT_EVALRUNS 20

number of runs

Definition at line 59 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_INITRUNS

#define DEFAULT_INITRUNS 100

number of initial runs

Definition at line 60 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_LEAFRUNS

#define DEFAULT_LEAFRUNS 25

number of runs at leafs

Definition at line 61 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_HARD_RUNSMULT

#define DEFAULT_HARD_RUNSMULT 1.75

multiplier

Definition at line 62 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_ROOTRUNS

#define DEFAULT_ROOTRUNS 50

number of runs at the root

Definition at line 63 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_DURINGLPFREQ

#define DEFAULT_DURINGLPFREQ 5

frequency during LP solving

Definition at line 64 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_TYPE

#define DEFAULT_TYPE 0

heuristic to execute

Definition at line 65 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_PCMODE

#define DEFAULT_PCMODE 4

solving mode for PC/MW

Definition at line 66 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 5

seed for pseudo-random functions

Definition at line 68 of file heur_tm.c.

Referenced by SCIPStpIncludeHeurTM().

◆ TM_HARD_MAXNEDGES

#define TM_HARD_MAXNEDGES 15000

Definition at line 70 of file heur_tm.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ AUTO

#define AUTO 0

Definition at line 72 of file heur_tm.c.

Referenced by getTmMode().

◆ TM_SP

#define TM_SP 1

Definition at line 73 of file heur_tm.c.

Referenced by getTmMode(), runTm(), and SCIPStpHeurTMRun().

◆ TM_VORONOI

#define TM_VORONOI 2

Definition at line 74 of file heur_tm.c.

Referenced by getTmMode(), and SCIPStpHeurTMRun().

◆ TM_DIJKSTRA

#define TM_DIJKSTRA 3

Definition at line 75 of file heur_tm.c.

Referenced by getTmMode(), and runTm().

◆ TM_USE_CSR

#define TM_USE_CSR

Definition at line 77 of file heur_tm.c.

◆ TM_USE_CSR_PCMW

#define TM_USE_CSR_PCMW

Definition at line 78 of file heur_tm.c.

Typedef Documentation

◆ TMBASE

typedef struct TM_base_data TMBASE

◆ TMALLSP

typedef struct TM_all_shortestpath TMALLSP

All shortest paths data NOTE: DEPRECATED

◆ TMVNOI

typedef struct TM_voronoi TMVNOI

Voronoi TM heuristic data NOTE: DEPRECATED

Function Documentation

◆ pcmwUpdateBestSol_csrInSync()

static SCIP_Bool pcmwUpdateBestSol_csrInSync	(	SCIP *	scip,
		const GRAPH *	graph,
		const TMBASE *	tmbase
	)

static

debug method; checks whether CSR solution objective is actually computed correctly

Parameters

scip	SCIP data structure
graph	graph data structure
tmbase	data

Definition at line 168 of file heur_tm.c.

References BMScopyMemoryArray, TM_base_data::connected, TM_base_data::csr_orgcosts, graph_get_nEdges(), graph_get_nNodes(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), nnodes, TM_base_data::result, SCIP_CALL_ABORT, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, SCIPisEQ(), solstp_convertCsrToGraph(), solstp_getObjBounded(), solstp_pcGetObjCsr(), and stpsol_pruningIsPossible().

Referenced by pcmwUpdateBestSol().

◆ SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdRandomseed )

static

information method for a parameter change of random seed

Definition at line 204 of file heur_tm.c.

References NULL, SCIP_OKAY, SCIPparamGetData(), and SCIPparamGetInt().

◆ tmBaseInit()

static SCIP_RETCODE tmBaseInit	(	SCIP *	scip,
		const GRAPH *	graph,
		TMBASE *	tmbase
	)

static

initializes

Parameters

scip	SCIP data structure
graph	graph structure
tmbase	data

Definition at line 226 of file heur_tm.c.

References TM_base_data::connected, TM_base_data::cost, csr_storage::cost, GRAPH::cost, TM_base_data::csr, TM_base_data::csr_orgcosts, TM_base_data::dheap, graph_csr_allocWithEdgeId(), graph_csr_build(), graph_csr_buildCosts(), graph_get_nEdges(), graph_get_nNodes(), graph_heap_create(), graph_pc_getOrgCostsCsr(), graph_pc_isPc(), graph_typeIsSpgLike(), TM_base_data::heap_entries, TM_base_data::heap_position, nnodes, TM_base_data::nodes_dist, TM_base_data::nodes_pred, TM_base_data::nruns, NULL, reduce_sdprofitInit1stOnly(), TM_base_data::result, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemory, TM_base_data::sdprofit1st, and TM_base_data::startnodes.

Referenced by SCIPStpHeurTMRun().

◆ tmBaseFree()

static void tmBaseFree	(	SCIP *	scip,
		const GRAPH *	graph,
		TMBASE *	tmbase
	)

static

frees

Parameters

scip	SCIP data structure
graph	graph structure
tmbase	data

Definition at line 298 of file heur_tm.c.

References TM_base_data::connected, csr_storage::cost, TM_base_data::csr, TM_base_data::csr_orgcosts, TM_base_data::dheap, FALSE, graph_csr_free(), graph_heap_free(), TM_base_data::heap_entries, TM_base_data::heap_position, TM_base_data::nodes_dist, TM_base_data::nodes_pred, NULL, reduce_sdprofitFree(), TM_base_data::result, SCIPfreeBufferArray, SCIPfreeMemory, TM_base_data::sdprofit1st, and TM_base_data::startnodes.

Referenced by SCIPStpHeurTMRun().

◆ tmAllspInit()

static SCIP_RETCODE tmAllspInit	(	SCIP *	scip,
		const GRAPH *	graph,
		TMALLSP *	tmallsp
	)

static

initializes

Parameters

scip	SCIP data structure
graph	graph structure
tmallsp	data

Definition at line 332 of file heur_tm.c.

References BMSclearMemoryArray, GRAPH::grad, graph_get_nNodes(), Is_term, GRAPH::mark, nnodes, NULL, TM_all_shortestpath::pathdist, TM_all_shortestpath::pathedge, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and GRAPH::term.

Referenced by SCIPStpHeurTMRun().

◆ tmAllspFree()

static void tmAllspFree	(	SCIP *	scip,
		const GRAPH *	graph,
		TMALLSP *	tmallsp
	)

static

frees

Parameters

scip	SCIP data structure
graph	graph structure
tmallsp	data

Definition at line 367 of file heur_tm.c.

References graph_get_nNodes(), nnodes, TM_all_shortestpath::pathdist, TM_all_shortestpath::pathedge, SCIPfreeBufferArray, and SCIPfreeBufferArrayNull.

Referenced by SCIPStpHeurTMRun().

◆ tmVnoiInit()

static SCIP_RETCODE tmVnoiInit	(	SCIP *	scip,
		const GRAPH *	graph,
		TMVNOI *	tmvnoi
	)

static

initializes

Parameters

scip	SCIP data structure
graph	graph structure
tmvnoi	data

Definition at line 391 of file heur_tm.c.

References TM_voronoi::gnodearr, GNODECmpByDist(), graph_get_nNodes(), nnodes, TM_voronoi::node_base, TM_voronoi::node_dist, TM_voronoi::node_edge, TM_voronoi::nodenterms, nterms, NULL, TM_voronoi::pqueue, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPpqueueCreate(), and GRAPH::terms.

Referenced by SCIPStpHeurTMRun().

◆ tmVnoiFree()

static void tmVnoiFree	(	SCIP *	scip,
		const GRAPH *	graph,
		TMVNOI *	tmvnoi
	)

static

frees

Parameters

scip	SCIP data structure
graph	graph structure
tmvnoi	data

Definition at line 424 of file heur_tm.c.

References TM_voronoi::gnodearr, graph_get_nNodes(), nnodes, TM_voronoi::node_base, TM_voronoi::node_dist, TM_voronoi::node_edge, TM_voronoi::nodenterms, NULL, TM_voronoi::pqueue, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPpqueueFree().

Referenced by SCIPStpHeurTMRun().

◆ getTMheurData()

static SCIP_HEURDATA* getTMheurData ( SCIP * scip )

inlinestatic

returns TM heur data

Parameters

scip	SCIP data structure

Definition at line 457 of file heur_tm.c.

References SCIPfindHeur(), and SCIPheurGetData().

Referenced by computeStarts(), pcmwGetStartNodes(), runTm(), runTmPcMW(), and SCIPStpHeurTMRun().

◆ getTmEdgeCostZeroOffset()

static SCIP_Real getTmEdgeCostZeroOffset	(	SCIP *	scip,
		const GRAPH *	graph
	)

static

returns offset for edge costs

Parameters

scip	SCIP data structure
graph	graph data structure

Definition at line 474 of file heur_tm.c.

References eps, SCIP_Real, and SCIPepsilon().

Referenced by computeSteinerTreeCsr(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), computeSteinerTreeKeyNodesCsr(), and SCIPStpHeurTMRunLP().

◆ isTMSpType()

static SCIP_Bool isTMSpType ( const GRAPH * graph )

static

returns whether TM SP type

Parameters

graph graph data structure

Definition at line 488 of file heur_tm.c.

References STP_DCSTP, STP_DHCSTP, and GRAPH::stp_type.

Referenced by getTmMode(), and updateBestSol().

◆ getTmMode()

static int getTmMode	(	SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph
	)

static

returns mode

Parameters

heurdata	SCIP data structure
graph	graph data structure

Definition at line 499 of file heur_tm.c.

References AUTO, graph_pc_isPcMw(), isTMSpType(), TM_DIJKSTRA, TM_SP, and TM_VORONOI.

Referenced by runTm(), and SCIPStpHeurTMRun().

◆ updateBestSol()

static void updateBestSol	(	SCIP *	scip,
		const GRAPH *	graph,
		int	startnode,
		SCIP_Bool	solfound,
		TMBASE *	tmbase,
		SCIP_Bool *	success
	)

inlinestatic

updates best (non PC/MW) solution if possible

Parameters

scip	SCIP data structure
graph	graph data structure
startnode	start vertex
solfound	solution found in this run?
tmbase	data
success	pointer to store whether a solution could be found

Definition at line 529 of file heur_tm.c.

References TM_base_data::best_obj, TM_base_data::best_result, TM_base_data::best_start, BMScopyMemoryArray, TM_base_data::connected, TM_base_data::csr_orgcosts, FALSE, graph_get_nEdges(), graph_typeIsSpgLike(), GRAPH::hoplimit, isTMSpType(), LT, TM_base_data::result, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPisLT(), solstp_convertCsrToGraph(), solstp_getNedges(), solstp_getObjBounded(), solstp_getObjCsr(), solstp_isValid(), STP_DCSTP, STP_DHCSTP, GRAPH::stp_type, and TRUE.

Referenced by runTm().

◆ pcmwUpdateBestSol()

static void pcmwUpdateBestSol	(	SCIP *	scip,
		const GRAPH *	graph,
		TMBASE *	tmbase,
		SCIP_Bool *	success
	)

inlinestatic

updates best PC/MW solution if possible

Parameters

scip	SCIP data structure
graph	graph data structure
tmbase	data
success	pointer to store whether a solution could be found

Definition at line 597 of file heur_tm.c.

References TM_base_data::best_obj, TM_base_data::best_result, BMScopyMemoryArray, TM_base_data::connected, TM_base_data::csr_orgcosts, graph_get_nEdges(), LT, pcmwUpdateBestSol_csrInSync(), TM_base_data::result, SCIP_Real, SCIPdebugMessage, solstp_convertCsrToGraph(), solstp_getObjBounded(), solstp_pcGetObjCsr(), and TRUE.

Referenced by runTmPcMW_mode().

◆ pcmwAdaptStarts()

static void pcmwAdaptStarts	(	SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		int	maxtmruns,
		int	bestincstart,
		int *	terminalperm
	)

static

submethod for SCIPStpHeurTMRun in PC or MW mode

Parameters

heurdata	heurdata
graph	graph data structure
maxtmruns	number of TM runs
bestincstart	best incumbent start vertex
terminalperm	terminal permutation

Definition at line 640 of file heur_tm.c.

References graph_get_nNodes(), Is_pseudoTerm, nnodes, r, SCIPrandomGetInt(), and GRAPH::term.

Referenced by pcmwGetStartNodes().

◆ pcmwGetStartNodes()

static SCIP_RETCODE pcmwGetStartNodes	(	SCIP *	scip,
		const SCIP_Real *	nodepriority,
		int	maxtmruns,
		int	bestincstart,
		GRAPH *	graph,
		int *	terminalperm
	)

static

submethod for runPCMW

< terminal priority

Parameters

scip	SCIP data structure
nodepriority	vertex priorities for vertices to be starting points (NULL for no priorities)
maxtmruns	number of TM runs
bestincstart	best incumbent start vertex
graph	graph data structure
terminalperm	terminal permutation

Definition at line 671 of file heur_tm.c.

References GRAPH::extended, FARAWAY, getTMheurData(), GRAPH::grad, graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_markOrgGraph(), Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, pcmwAdaptStarts(), GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), SCIPrandomGetReal(), SCIPsortRealInt(), GRAPH::source, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by runTmPcMW_mode().

◆ pcmwSetEdgeCosts()

static void pcmwSetEdgeCosts	(	const GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	costorg,
		const SCIP_Real *	costfullbiased,
		enum PCMW_TmMode	pcmwmode,
		TMBASE *	tmbase
	)

static

submethod for SCIPStpHeurTMRun in PC or MW mode

Parameters

graph	graph data structure
cost	arc costs
costorg	arc costs
costfullbiased	arc costs
pcmwmode	mode
tmbase	data

Definition at line 755 of file heur_tm.c.

References TM_base_data::cost, TM_base_data::csr, graph_csr_chgCosts(), graph_pc_isPc(), pcmode_bias, pcmode_biasfull, pcmode_fulltree, and pcmode_simple.

Referenced by runTmPcMW_mode().

◆ computeStarts()

static SCIP_RETCODE computeStarts	(	SCIP *	scip,
		const GRAPH *	graph,
		const int *	orgstarts,
		SCIP_Bool	startsgiven,
		SCIP_Real *	nodepriority,
		TMBASE *	tmbase,
		int *	bestp
	)

static

Parameters

scip	SCIP data structure
graph	graph structure
orgstarts	original start vertices
startsgiven	start vertices given?
nodepriority	nodepriority
tmbase	data
bestp	pointer to best start vertex

Definition at line 787 of file heur_tm.c.

References BLOCKED, TM_base_data::cost, getTMheurData(), graph_knotIsNWLeaf(), graph_path_execX(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, TM_base_data::nodes_dist, TM_base_data::nodes_pred, TM_base_data::nruns, nterms, NULL, r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisLE(), SCIPisLT(), SCIPrandomGetInt(), SCIPrandomGetReal(), SCIPrandomPermuteIntArray(), SCIPsortRealInt(), GRAPH::source, TM_base_data::startnodes, STP_DHCSTP, STP_NWPTSPG, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by SCIPStpHeurTMRun().

◆ keyNodesSetTerms()

static void keyNodesSetTerms	(	SCIP *	scip,
		const int *	soledge,
		GRAPH *	g,
		int *	solnodes_degree
	)

inlinestatic

set terminals

Parameters

scip	SCIP data structure
soledge	solution edges
g	graph structure (in/out)
solnodes_degree	degree in solution (out)

Definition at line 983 of file heur_tm.c.

References CONNECT, graph_get_nEdges(), graph_get_nNodes(), graph_knot_chg(), GRAPH::head, Is_term, nnodes, SCIPdebugMessage, solstp_isValid(), STP_TERM, GRAPH::tail, and GRAPH::term.

Referenced by computeSteinerTreeKeyNodesCsr().

◆ keyNodesResetTerms()

static void keyNodesResetTerms	(	const int *	solnodes_degree,
		GRAPH *	g
	)

inlinestatic

reset terminals

Parameters

solnodes_degree	degree in solution (in)
g	graph structure

Definition at line 1022 of file heur_tm.c.

References GRAPH::grad, graph_get_nNodes(), graph_knot_chg(), Is_term, nnodes, SCIPdebugMessage, STP_TERM_NONE, and GRAPH::term.

Referenced by computeSteinerTreeKeyNodesCsr().

◆ computeSteinerTreeCsr()

static SCIP_RETCODE computeSteinerTreeCsr	(	SCIP *	scip,
		const GRAPH *	g,
		int	startnode,
		TMBASE *	tmbase
	)

inlinestatic

CSR based shortest paths heuristic

Parameters

scip	SCIP data structure
g	graph structure
startnode	start vertex
tmbase	(in/out)

Definition at line 1047 of file heur_tm.c.

References TM_base_data::connected, stortest_paths::csr, TM_base_data::csr, TM_base_data::csr_orgcosts, TM_base_data::dheap, getTmEdgeCostZeroOffset(), graph_typeIsDirected(), TM_base_data::nodes_dist, TM_base_data::nodes_pred, TM_base_data::result, SCIP_CALL, SCIP_OKAY, TM_base_data::sdprofit1st, shortestpath_computeSteinerTree(), shortestpath_computeSteinerTreeBiased(), shortestpath_computeSteinerTreeDirected(), solstp_pruneFromTmHeur_csr(), STP_DHCSTP, and GRAPH::stp_type.

Referenced by runTm().

◆ computeSteinerTreeKeyNodesCsr()

static SCIP_RETCODE computeSteinerTreeKeyNodesCsr	(	SCIP *	scip,
		GRAPH *	g,
		int	startnode,
		TMBASE *	tmbase
	)

inlinestatic

CSR based shortest paths heuristic that exploits key nodes of best solution

Parameters

scip	SCIP data structure
g	graph structure
startnode	start vertex
tmbase	(in/out)

Definition at line 1076 of file heur_tm.c.

References TM_base_data::best_result, TM_base_data::connected, stortest_paths::csr, TM_base_data::csr, TM_base_data::csr_orgcosts, TM_base_data::dheap, getTmEdgeCostZeroOffset(), graph_typeIsSpgLike(), keyNodesResetTerms(), keyNodesSetTerms(), GRAPH::knots, TM_base_data::nodes_dist, TM_base_data::nodes_pred, nterms, TM_base_data::result, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBuffer, TM_base_data::sdprofit1st, shortestpath_computeSteinerTree(), shortestpath_computeSteinerTreeBiased(), solstp_pruneFromTmHeur_csr(), STP_DHCSTP, GRAPH::stp_type, and GRAPH::terms.

Referenced by runTm().

◆ computeSteinerTreeDijk()

static SCIP_RETCODE computeSteinerTreeDijk	(	SCIP *	scip,
		GRAPH *	g,
		int	start,
		TMBASE *	tmbase
	)

inlinestatic

Dijkstra based shortest paths heuristic

Parameters

scip	SCIP data structure
g	graph structure
start	start vertex
tmbase	(in/out)

Definition at line 1116 of file heur_tm.c.

References TM_base_data::connected, TM_base_data::cost, graph_mark(), graph_path_st(), graph_pc_isPcMw(), TM_base_data::nodes_dist, TM_base_data::nodes_pred, TM_base_data::result, SCIP_CALL, SCIP_OKAY, SCIP_Real, and solstp_pruneFromTmHeur().

Referenced by dhcstpWarmUp(), and runTm().

◆ computeSteinerTreeDijkBMw()

static SCIP_RETCODE computeSteinerTreeDijkBMw	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cost_org,
		const SCIP_Real *	prize,
		int	start,
		TMBASE *	tmbase,
		SCIP_Bool *	solfound
	)

static

Dijkstra based shortest paths heuristic for PCSTP and MWCSP

Parameters

scip	SCIP data structure
g	graph structure
cost_org	(un-biased) edge costs, only needed for PC/RPC
prize	(possibly biased) vertex prizes
start	start vertex
tmbase	data
solfound	solution found? (OUT)

Definition at line 1143 of file heur_tm.c.

References TM_base_data::connected, graph_path_st_brmwcs(), TM_base_data::nodes_dist, TM_base_data::nodes_pred, TM_base_data::result, SCIP_CALL, SCIP_OKAY, solstp_pruneFromTmHeur(), STP_BRMWCSP, GRAPH::stp_type, and TRUE.

Referenced by runTmPcMW_mode().

◆ computeSteinerTreeDijkPcMw()

static SCIP_RETCODE computeSteinerTreeDijkPcMw	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cost_org,
		const SCIP_Real *	prize,
		SCIP_Bool	costsAreBiased,
		int	start,
		SPATHSPC *	sppc,
		TMBASE *	tmbase
	)

static

Dijkstra based shortest paths heuristic for PCSTP and MWCSP

Parameters

scip	SCIP data structure
g	graph structure
cost_org	(un-biased) edge costs, only needed for PC/RPC
prize	(possibly biased) vertex prizes
costsAreBiased	biased?
start	start vertex
sppc	PC/MW shortest path data
tmbase	data

Definition at line 1168 of file heur_tm.c.

References TM_base_data::connected, TM_base_data::cost, stortest_paths::csr, TM_base_data::csr, TM_base_data::csr_orgcosts, TM_base_data::dheap, getTmEdgeCostZeroOffset(), graph_path_st_pcmw(), graph_path_st_rpcmw(), graph_pc_isPcMw(), TM_base_data::nodes_dist, TM_base_data::nodes_pred, stortest_path_prizecollecting::orderedprizes, stortest_path_prizecollecting::orderedprizes_id, TM_base_data::result, SCIP_CALL, SCIP_OKAY, shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreeRpcMw(), solstp_pruneFromTmHeur(), solstp_pruneFromTmHeur_csr(), STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by runTmPcMW_mode().

◆ computeSteinerTreeDijkPcMwFull()

static SCIP_RETCODE computeSteinerTreeDijkPcMwFull	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cost_org,
		int	start,
		TMBASE *	tmbase
	)

static

Dijkstra based shortest paths heuristic for PCSTP and MWCSP that computes tree spanning all positive vertex weights and subsequently prunes this tree

Parameters

scip	SCIP data structure
g	graph structure
cost_org	(un-biased) edge costs, only needed for PC/RPC
start	start vertex
tmbase	data

Definition at line 1224 of file heur_tm.c.

References TM_base_data::connected, TM_base_data::cost, stortest_paths::csr, TM_base_data::csr, TM_base_data::csr_orgcosts, TM_base_data::dheap, getTmEdgeCostZeroOffset(), graph_path_st_pcmw_full(), TM_base_data::nodes_dist, TM_base_data::nodes_pred, TM_base_data::result, SCIP_CALL, SCIP_OKAY, shortestpath_computeSteinerTreePcMwFull(), solstp_pruneFromTmHeur(), and solstp_pruneFromTmHeur_csr().

Referenced by runTmPcMW_mode().

◆ computeSteinerTree()

static SCIP_RETCODE computeSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		int	start,
		int *	result,
		TMALLSP *	tmallsp,
		STP_Bool *	connected,
		SCIP_RANDNUMGEN *	randnumgen
	)

static

shortest paths based heuristic NOTE: DEPRECATED

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
costrev	reversed edge costs
start	start vertex
result	solution array (on edges)
tmallsp	all SP
connected	array marking all solution vertices
randnumgen	random number generator

Definition at line 1253 of file heur_tm.c.

References GRAPH::edges, FALSE, FARAWAY, GRAPH::grad, graph_valid(), Is_term, GRAPH::knots, LT, GRAPH::mark, nnodes, nterms, NULL, TM_all_shortestpath::pathdist, TM_all_shortestpath::pathedge, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisStopped(), SCIPrandomGetInt(), SCIPrandomPermuteIntArray(), solstp_pruneFromTmHeur(), GRAPH::source, STP_DHCSTP, STP_NWPTSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by runTm().

◆ computeSteinerTreeSingleNode()

static void computeSteinerTreeSingleNode	(	const GRAPH *	graph,
		int	node,
		TMBASE *	tmbase,
		SCIP_Bool *	success
	)

inlinestatic

cumputes single node Steiner tree; only for rooted PC/MW

Parameters

graph	graph data structure
node	the nodes
tmbase	data
success	telling name

Definition at line 1407 of file heur_tm.c.

References TM_base_data::best_result, graph_get_nEdges(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), GRAPH::source, TRUE, and UNKNOWN.

Referenced by runTmPcMW_mode().

◆ computeDegConsTree()

static SCIP_RETCODE computeDegConsTree	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		int	start,
		int *	result,
		TMALLSP *	tmallsp,
		SCIP_RANDNUMGEN *	randnumgen,
		STP_Bool *	connected,
		STP_Bool *	solfound
	)

static

heuristic for degree constrained STPs NOTE: DEPRECATED

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
start	start vertex
result	array to indicate whether an edge is in the solution
tmallsp	all SP
randnumgen	random number generator
connected	array to indicate whether a vertex is in the solution
solfound	pointer to store whether a solution has been found

Definition at line 1434 of file heur_tm.c.

References CONNECT, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::maxdeg, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, TM_all_shortestpath::pathdist, TM_all_shortestpath::pathedge, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPrandomGetInt(), SCIPrandomPermuteIntArray(), SCIPStpHeurTMBuildTreeDc(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by runTm().

◆ computeSteinerTreeVnoi()

static SCIP_RETCODE computeSteinerTreeVnoi	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		int	start,
		STP_Bool	firstrun,
		TMVNOI *	tmvnoi,
		int *	result,
		STP_Bool *	connected
	)

static

Voronoi based shortest path heuristic. NOTE: DEPRECATED

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
costrev	reversed edge costs
start	start vertex
firstrun	method called for the first time? (during one heuristic round)
tmvnoi	TM data
result	array to indicate whether an edge is in the solution
connected	array to indicate whether a vertex is in the solution

Definition at line 1697 of file heur_tm.c.

References CONNECT, Graph_Node::dist, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, TM_voronoi::gnodearr, GRAPH::grad, graph_pathHeapAdd(), graph_voronoi(), graph_voronoiExtend(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, TM_voronoi::node_base, TM_voronoi::node_dist, TM_voronoi::node_edge, TM_voronoi::nodenterms, nterms, NULL, number, Graph_Node::number, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, TM_voronoi::pqueue, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisStopped(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPsortRealIntInt(), solstp_pruneFromTmHeur(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by runTm().

◆ tmLpGetEdgeRandomizations()

static void tmLpGetEdgeRandomizations	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		SCIP_Bool *	partrand,
		SCIP_Bool *	totalrand
	)

static

initialize edge costs, vertex prizes, and start node priorities

Parameters

scip	SCIP data structure
heurdata	heurdata
graph	graph data structure
partrand	use partial randomization? (OUT)
totalrand	use total randomization? (OUT)

Definition at line 2025 of file heur_tm.c.

References FALSE, GRAPH::maxdeg, SCIPgetNLPIterations(), SCIPrandomGetInt(), GRAPH::source, STP_DCSTP, GRAPH::stp_type, and TRUE.

Referenced by initCostsAndPrioLP().

◆ initCostsAndPrioLP()

static void initCostsAndPrioLP	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		SCIP_VAR **	vars,
		const GRAPH *	graph,
		SCIP_Real	randupper,
		SCIP_Real	randlower,
		const SCIP_Real *	xval,
		SCIP_Real *RESTRICT	nodepriority,
		SCIP_Real *RESTRICT	prize,
		SCIP_Real *RESTRICT	cost
	)

static

initialize edge costs, vertex prizes, and start node priorities

Parameters

scip	SCIP data structure
heurdata	heurdata
vars	variables
graph	graph data structure
randupper	random value bound
randlower	random value bound
xval	xval
nodepriority	node priority (uninitialized)
prize	prize (uninitialized) or NULL
cost	arc costs (uninitialized)

Definition at line 2053 of file heur_tm.c.

References BLOCKED, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, flipedge_Uint, GE, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isMw(), graph_pc_isPcMw(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, LT, MAX, nnodes, GRAPH::oeat, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGE(), SCIPrandomGetReal(), SCIPvarGetUbLocal(), STP_DHCSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and tmLpGetEdgeRandomizations().

Referenced by SCIPStpHeurTMRunLP().

◆ buildTmAllSp()

static void buildTmAllSp	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		TMALLSP *	tmallsp
	)

static

initializes for TM SP runs (computes shortest paths from all terminals)

Parameters

scip	SCIP data structure
graph	graph data structure
cost	arc costs
costrev	reversed arc costs
tmallsp	TM data

Definition at line 2191 of file heur_tm.c.

References GRAPH::grad, graph_get_nNodes(), graph_path_execX(), Is_term, GRAPH::mark, nnodes, NULL, TM_all_shortestpath::pathdist, TM_all_shortestpath::pathedge, SCIP_Real, GRAPH::source, and GRAPH::term.

Referenced by runTm().

◆ dhcstpWarmUp()

static SCIP_RETCODE dhcstpWarmUp	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	hopfactor,
		TMBASE *	tmbase,
		SCIP_Bool *	success
	)

static

initial runs for DHCSTP to figure out a good hop factor

Parameters

scip	SCIP data structure
graph	graph data structure
cost	hacky
costrev	hacky
hopfactor	(in/out)
tmbase	(in/out)
success	success?

Definition at line 2225 of file heur_tm.c.

References TM_base_data::best_obj, TM_base_data::best_result, BLOCKED, BMScopyMemoryArray, computeSteinerTreeDijk(), CONNECT, TM_base_data::connected, GRAPH::cost, DEFAULT_HOPFACTOR, FALSE, flipedge, GE, graph_get_nEdges(), graph_get_nNodes(), GT, GRAPH::hoplimit, LE, LT, nnodes, r, TM_base_data::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPisGT(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, TRUE, and UNKNOWN.

Referenced by runTmDhcstp().

◆ runTm()

static SCIP_RETCODE runTm	(	SCIP *	scip,
		GRAPH *	graph,
		TMBASE *	tmbase,
		TMALLSP *	tmallsp,
		TMVNOI *	tmvnoi,
		SCIP_Bool *	success
	)

static

submethod for SCIPStpHeurTMRun

Parameters

scip	SCIP data structure
graph	graph data structure
tmbase	TM base data
tmallsp	TM data
tmvnoi	TM data
success	pointer to store whether a solution could be found

Definition at line 2366 of file heur_tm.c.

References TM_base_data::best_start, buildTmAllSp(), computeDegConsTree(), computeSteinerTree(), computeSteinerTreeCsr(), computeSteinerTreeDijk(), computeSteinerTreeKeyNodesCsr(), computeSteinerTreeVnoi(), TM_base_data::connected, TM_base_data::cost, TM_base_data::costrev, FALSE, getTMheurData(), getTmMode(), graph_knotIsNWLeaf(), graph_pc_isPcMw(), graph_typeIsSpgLike(), GRAPH::knots, TM_base_data::nruns, r, TM_base_data::result, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisStopped(), TM_base_data::startnodes, STP_DCSTP, STP_NWPTSPG, GRAPH::stp_type, TM_DIJKSTRA, TM_SP, and updateBestSol().

Referenced by runTmDhcstp(), and SCIPStpHeurTMRun().

◆ runTmPcMW_mode()

static SCIP_RETCODE runTmPcMW_mode	(	SCIP *	scip,
		GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	prize,
		enum PCMW_TmMode	pcmwmode,
		int	bestincstart,
		SCIP_Real *	nodepriority,
		TMBASE *	tmbase,
		SCIP_Bool *	success
	)

static

submethod for SCIPStpHeurTMRun in PC or MW mode

Parameters

scip	SCIP data structure
graph	graph data structure
cost	arc costs
prize	prizes (for PCMW) or NULL
pcmwmode	mode
bestincstart	best incumbent start vertex
nodepriority	vertex priorities for vertices to be starting points (NULL for no priorities)
tmbase	data
success	pointer to store whether a solution could be found

Definition at line 2446 of file heur_tm.c.

References TM_base_data::best_obj, TM_base_data::best_result, BMScopyMemoryArray, computeSteinerTreeDijkBMw(), computeSteinerTreeDijkPcMw(), computeSteinerTreeDijkPcMwFull(), computeSteinerTreeSingleNode(), TM_base_data::csr_orgcosts, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::grad, graph_csr_costsAreInSync(), graph_pc_getBiased(), graph_pc_getOrgCosts(), graph_pc_isPc(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_valid(), GRAPH::knots, LT, nnodes, TM_base_data::nruns, NULL, pcmode_all, pcmode_bias, pcmode_biasfull, pcmode_fulltree, pcmode_simple, pcmwGetStartNodes(), pcmwSetEdgeCosts(), pcmwUpdateBestSol(), GRAPH::prize, r, TM_base_data::result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisStopped(), shortestpath_pcFree(), shortestpath_pcInit(), solstp_getObjBounded(), GRAPH::source, TM_base_data::startnodes, STP_BRMWCSP, GRAPH::stp_type, GRAPH::terms, and TRUE.

Referenced by runTmPcMW().

◆ runTmPcMW()

static SCIP_RETCODE runTmPcMW	(	SCIP *	scip,
		GRAPH *	graph,
		const SCIP_Real *	cost,
		const SCIP_Real *	prize,
		enum PCMW_TmMode	pcmw_tmmode,
		int	beststart,
		SCIP_Real *	nodepriority,
		TMBASE *	tmbase,
		SCIP_Bool *	success
	)

inlinestatic

SCIPStpHeurTMRun in PC or MW mode

Parameters

scip	SCIP data structure
graph	graph data structure
cost	arc costs
prize	prizes (for PCMW) or NULL
pcmw_tmmode	mode
beststart	best incumbent start vertex
nodepriority	vertex priorities for vertices to be starting points (NULL for no priorities)
tmbase	data
success	pointer to store whether a solution could be found

Definition at line 2585 of file heur_tm.c.

References FALSE, getTMheurData(), graph_pc_isPc(), graph_pc_isPcMw(), pcmode_all, pcmode_bias, pcmode_biasAndFulltree, pcmode_biasfull, pcmode_fromheurdata, pcmode_fulltree, pcmode_simple, runTmPcMW_mode(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, STP_BRMWCSP, and GRAPH::stp_type.

Referenced by SCIPStpHeurTMRun().

◆ runTmDhcstp()

static SCIP_RETCODE runTmDhcstp	(	SCIP *	scip,
		GRAPH *	graph,
		TMBASE *	tmbase,
		TMALLSP *	tmallsp,
		TMVNOI *	tmvnoi,
		SCIP_Real *	hopfactor,
		SCIP_Bool *	success
	)

static

submethod for SCIPStpHeurTMRun

Parameters

scip	SCIP data structure
graph	graph data structure
tmbase	TM base data
tmallsp	TM data
tmvnoi	TM data
hopfactor	hopfactor
success	pointer to store whether a solution could be found

Definition at line 2635 of file heur_tm.c.

References BMScopyMemoryArray, TM_base_data::cost, TM_base_data::costrev, dhcstpWarmUp(), graph_get_nEdges(), runTm(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, STP_DHCSTP, and GRAPH::stp_type.

Referenced by SCIPStpHeurTMRun().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyTM )

static

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

Definition at line 2682 of file heur_tm.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeTM )

static

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

Definition at line 2696 of file heur_tm.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitTM )

static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 2719 of file heur_tm.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPgetIntParam(), SCIPgetProbData(), SCIPheurGetData(), SCIPheurGetName(), SCIPprobdataGetGraph(), STP_SPG, and GRAPH::stp_type.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecTM )

static

◆ SCIPStpHeurTMCompStarts()

void SCIPStpHeurTMCompStarts	(	GRAPH *	graph,
		int *	starts,
		int *	runs
	)

compute starting points among marked (w.r.t. g->mark) vertices for constructive heuristics

Parameters

graph	graph data structure
starts	starting points array
runs	pointer to number of runs

Definition at line 2879 of file heur_tm.c.

References Is_term, GRAPH::knots, GRAPH::mark, nnodes, TM_base_data::nruns, nterms, NULL, r, GRAPH::source, GRAPH::term, and GRAPH::terms.

Referenced by computeNewSols(), computeSteinerTree(), computeSteinerTreeTM(), redcostGraphComputeSteinerTreeDirected(), and updateSolution().

◆ SCIPStpHeurTMBuildTree()

void SCIPStpHeurTMBuildTree	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	mst,
		const SCIP_Real *	cost,
		SCIP_Real *	objresult,
		int *	connected
	)

build Steiner tree in such a way that all leaves are terminals

Parameters

scip	SCIP data structure
g	graph structure
mst	path data structure array
cost	edge costs
objresult	pointer to store objective value of result
connected	CONNECT/UNKNOWN

Definition at line 2932 of file heur_tm.c.

References CONNECT, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, graph_path_exec(), graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by nodesolUpdate(), and SCIPStpHeurPruneUpdateSols().

◆ SCIPStpHeurTMBuildTreePcMw()

SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	useRootSym,
		PATH *	mst,
		const SCIP_Real *	cost,
		SCIP_Real *	objresult,
		int *	connected
	)

build (rooted) prize collecting Steiner tree in such a way that all leaves are terminals; objresult is set FARAWAY if infeasible

Parameters

scip	SCIP data structure
g	graph structure
useRootSym	use?
mst	path data structure array
cost	edge costs
objresult	pointer to store objective value of result
connected	CONNECT/UNKNOWN

Definition at line 3012 of file heur_tm.c.

References a, CONNECT, EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, graph_path_exec(), graph_pc_isRootedPcMw(), graph_pc_isUnrootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPprobdataGetNNodes(), SCIPprobdataGetNTerms(), SCIPprobdataGetPctermsorder(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by nodesolUpdate(), and SCIPStpHeurPruneUpdateSols().

◆ SCIPStpHeurTMBuildTreeDc()

SCIP_RETCODE SCIPStpHeurTMBuildTreeDc	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result,
		STP_Bool *	connected
	)

prune a degree constrained Steiner tree in such a way that all leaves are terminals

Parameters

scip	SCIP data structure
g	graph structure
result	ST edges
connected	ST nodes (to be set)

Definition at line 3226 of file heur_tm.c.

References CONNECT, GRAPH::cost, EAT_LAST, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, LT, GRAPH::maxdeg, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebug, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeDegConsTree(), and SCIPStpHeurRecRun().

◆ SCIPStpHeurTMRun()

SCIP_RETCODE SCIPStpHeurTMRun	(	SCIP *	scip,
		enum PCMW_TmMode	pcmw_tmmode,
		GRAPH *	graph,
		int *	starts,
		const SCIP_Real *	prize,
		int *	best_result,
		int	runs,
		int	bestincstart,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	hopfactor,
		SCIP_Real *	nodepriority,
		SCIP_Bool *	success
	)

execute shortest paths heuristic to obtain a Steiner tree

Parameters

scip	SCIP data structure
pcmw_tmmode	mode for PC/MW
graph	graph data structure
starts	array containing start vertices (NULL to not provide any)
prize	prizes (for PCMW) or NULL
best_result	array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
runs	number of runs
bestincstart	best incumbent start vertex
cost	arc costs
costrev	reversed arc costs
hopfactor	edge cost multiplicator for HC problems
nodepriority	vertex priorities for vertices to be starting points (NULL for no priorities)
success	pointer to store whether a solution could be found

Definition at line 3418 of file heur_tm.c.

References TM_base_data::best_result, computeStarts(), TM_base_data::cost, TM_base_data::costrev, TM_base_data::dheap, FALSE, FARAWAY, getTMheurData(), getTmMode(), graph_get_nEdges(), graph_pc_2transcheck(), graph_pc_isPcMw(), graph_printInfoReduced(), NULL, runTm(), runTmDhcstp(), runTmPcMW(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), solstp_getObj(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, TM_SP, TM_VORONOI, tmAllspFree(), tmAllspInit(), tmBaseFree(), tmBaseInit(), tmVnoiFree(), and tmVnoiInit().

Referenced by computeNewSols(), computeReducedProbSolutionBiased(), computeSteinerTree(), computeSteinerTreeTM(), createInitialCuts(), daPcAddTmSolToPool(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), reduce_boundHopRc(), runTmPcFull(), SCIPStpHeurRecExclude(), SCIPStpHeurTMRunLP(), and updateSolution().

◆ SCIPStpHeurTMRunLP()

SCIP_RETCODE SCIPStpHeurTMRunLP	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_HEUR *	heur,
		int *	result,
		int	runs,
		SCIP_Bool *	success
	)

run shortest path heuristic, but bias edge costs towards best current LP solution

Parameters

scip	SCIP data structure
graph	graph data structure
heur	heuristic or NULL
result	(uninitialized) array indicating whether an arc is part of the solution (CONNECTED/UNKNOWN)
runs	number of runs
success	pointer to store whether a solution could be found

Definition at line 3509 of file heur_tm.c.

References BLOCKED, BMScopyMemoryArray, TM_base_data::cost, GRAPH::cost, TM_base_data::costrev, eps, FALSE, flipedge_Uint, getTmEdgeCostZeroOffset(), GRAPH::grad, graph_get_nEdges(), graph_get_nNodes(), graph_knot_chg(), graph_pc_isPcMw(), graph_typeIsSpgLike(), GRAPH::head, initCostsAndPrioLP(), Is_term, LE, MAX, nnodes, NULL, pcmode_bias, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPepsilon(), SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSol(), SCIPgetLPSolstat(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPisZero(), SCIPlinkLPSol(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPrandomGetReal(), SCIPStpHeurTMRun(), SCIPvarGetUbGlobal(), solstp_addSolToProb(), solstp_pruneFromEdges(), GRAPH::source, STP_BRMWCSP, STP_DHCSTP, STP_TERM, GRAPH::stp_type, GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC(), and selectBranchingVertexBySol().

◆ SCIPStpIncludeHeurTM()

SCIP_RETCODE SCIPStpIncludeHeurTM ( SCIP * scip )

creates the TM primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 3711 of file heur_tm.c.

References DEFAULT_DURINGLPFREQ, DEFAULT_EVALRUNS, DEFAULT_HARD_RUNSMULT, DEFAULT_HOPFACTOR, DEFAULT_INITRUNS, DEFAULT_LEAFRUNS, DEFAULT_PCMODE, DEFAULT_RANDSEED, DEFAULT_ROOTRUNS, DEFAULT_TYPE, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_HEURTIMING_AFTERLPLOOP, SCIP_HEURTIMING_AFTERNODE, SCIP_HEURTIMING_AFTERPSEUDONODE, SCIP_HEURTIMING_BEFORENODE, SCIP_HEURTIMING_DURINGLPLOOP, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPcreateRandom(), SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurFree(), SCIPsetHeurInit(), SCIPsnprintf(), 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_EVALRUNS

◆ DEFAULT_INITRUNS

◆ DEFAULT_LEAFRUNS

◆ DEFAULT_HARD_RUNSMULT

◆ DEFAULT_ROOTRUNS

◆ DEFAULT_DURINGLPFREQ

◆ DEFAULT_TYPE

◆ DEFAULT_PCMODE

◆ DEFAULT_RANDSEED

◆ TM_HARD_MAXNEDGES

◆ AUTO

◆ TM_SP

◆ TM_VORONOI

◆ TM_DIJKSTRA

◆ TM_USE_CSR

◆ TM_USE_CSR_PCMW

Typedef Documentation

◆ TMBASE

◆ TMALLSP

◆ TMVNOI

Function Documentation

◆ pcmwUpdateBestSol_csrInSync()

◆ SCIP_DECL_PARAMCHGD()

◆ tmBaseInit()

◆ tmBaseFree()

◆ tmAllspInit()

◆ tmAllspFree()

◆ tmVnoiInit()

◆ tmVnoiFree()

◆ getTMheurData()

◆ getTmEdgeCostZeroOffset()

◆ isTMSpType()

◆ getTmMode()

◆ updateBestSol()

◆ pcmwUpdateBestSol()

◆ pcmwAdaptStarts()

◆ pcmwGetStartNodes()

◆ pcmwSetEdgeCosts()

◆ computeStarts()

◆ keyNodesSetTerms()

◆ keyNodesResetTerms()

◆ computeSteinerTreeCsr()

◆ computeSteinerTreeKeyNodesCsr()

◆ computeSteinerTreeDijk()

◆ computeSteinerTreeDijkBMw()

◆ computeSteinerTreeDijkPcMw()

◆ computeSteinerTreeDijkPcMwFull()

◆ computeSteinerTree()

◆ computeSteinerTreeSingleNode()

◆ computeDegConsTree()

◆ computeSteinerTreeVnoi()

◆ tmLpGetEdgeRandomizations()

◆ initCostsAndPrioLP()

◆ buildTmAllSp()

◆ dhcstpWarmUp()

◆ runTm()

◆ runTmPcMW_mode()

◆ runTmPcMW()

◆ runTmDhcstp()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPStpHeurTMCompStarts()