heur_tm.c File Reference

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

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 "probdata_stp.h"
#include "portab.h"
#include "scip/misc.h"
#include <math.h>

Go to the source code of this file.

Macros
#define	HEUR_NAME   "TM"
#define	HEUR_DESC   "takahashi matsuyama primal heuristic 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   15
#define	DEFAULT_INITRUNS   100
#define	DEFAULT_LEAFRUNS   15
#define	DEFAULT_ROOTRUNS   50
#define	DEFAULT_DURINGLPFREQ   10
#define	DEFAULT_TYPE   0
#define	DEFAULT_RANDSEED   0
#define	AUTO   0
#define	TM_SP   1
#define	TM_VORONOI   2
#define	TM_DIJKSTRA   3

Functions
static	SCIP_DECL_PARAMCHGD (paramChgdRandomseed)
SCIP_RETCODE	SCIPheurPrunePCSteinerTree (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *result, char *connected)
SCIP_RETCODE	SCIPheurPruneSteinerTree (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int layer, int *result, char *connected)
static SCIP_RETCODE	prune (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, int *result, char *connected)
SCIP_RETCODE	SCIPheurPruneDegConsSteinerTree (SCIP *scip, const GRAPH *g, int *result, char *connected)
static SCIP_RETCODE	computeSteinerTreeDijk (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *dijkdist, int *result, int *dijkedge, int start, unsigned int *randseed, char *connected)
static SCIP_RETCODE	computeSteinerTree (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real **pathdist, int start, int *perm, int *result, int *cluster, int **pathedge, char *connected, unsigned int *randseed)
static SCIP_RETCODE	computeDegConsTree (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real **pathdist, int start, int *perm, int *result, int *cluster, int **pathedge, unsigned int *randseed, char *connected, char *solfound)
static SCIP_RETCODE	computeSteinerTreeVnoi (SCIP *scip, const GRAPH *g, SCIP_PQUEUE *pqueue, GNODE **gnodearr, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real **node_dist, int start, int *result, int *vcount, int *nodenterms, int **node_base, int **node_edge, char firstrun, char *connected)
static void	do_prizecoll_trivial (SCIP *scip, const GRAPH *graph, int *best_result)
SCIP_RETCODE	SCIPheurComputeSteinerTree (SCIP *scip, SCIP_HEURDATA *heurdata, const GRAPH *graph, int *starts, int *bestnewstart, int *best_result, int runs, int bestincstart, SCIP_Real *cost, SCIP_Real *costrev, SCIP_Real *hopfactor, SCIP_Real *nodepriority, SCIP_Real maxcost, SCIP_Bool *success)
static	SCIP_DECL_HEURCOPY (heurCopyTM)
static	SCIP_DECL_HEURFREE (heurFreeTM)
static	SCIP_DECL_HEURINIT (heurInitTM)
static	SCIP_DECL_HEUREXEC (heurExecTM)
SCIP_RETCODE	SCIPincludeHeurTM (SCIP *scip)

Macro Definition Documentation

#define AUTO   0

Definition at line 57 of file heur_tm.c.

Referenced by SCIPheurComputeSteinerTree().

#define DEFAULT_DURINGLPFREQ   10

frequency during LP solving

Definition at line 53 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define DEFAULT_EVALRUNS   15

number of runs

Definition at line 49 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define DEFAULT_INITRUNS   100

number of initial runs

Definition at line 50 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define DEFAULT_LEAFRUNS   15

number of runs at leafs

Definition at line 51 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define DEFAULT_RANDSEED   0

seed for pseudo-random functions

Definition at line 55 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define DEFAULT_ROOTRUNS   50

number of runs at the root

Definition at line 52 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define DEFAULT_TYPE   0

heuristic to execute

Definition at line 54 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_DESC   "takahashi matsuyama primal heuristic for steiner trees"

Definition at line 40 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_DISPCHAR   '+'

Definition at line 41 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_FREQ   1

Definition at line 43 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_FREQOFS   0

Definition at line 44 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_MAXDEPTH   -1

Definition at line 45 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_NAME   "TM"

Definition at line 39 of file heur_tm.c.

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

#define HEUR_PRIORITY   10000000

Definition at line 42 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

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

Definition at line 46 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 47 of file heur_tm.c.

Referenced by SCIPincludeHeurTM().

#define TM_DIJKSTRA   3

Definition at line 60 of file heur_tm.c.

Referenced by SCIPheurComputeSteinerTree().

#define TM_SP   1

Definition at line 58 of file heur_tm.c.

Referenced by SCIPheurComputeSteinerTree().

#define TM_VORONOI   2

Definition at line 59 of file heur_tm.c.

Referenced by SCIPheurComputeSteinerTree().

Function Documentation

static SCIP_RETCODE computeDegConsTree ( SCIP *  scip, const GRAPH *  g, SCIP_Real *  cost, SCIP_Real *  costrev, SCIP_Real **  pathdist, int  start, int *  perm, int *  result, int *  cluster, int **  pathedge, unsigned int *  randseed, char *  connected, char *  solfound  )

static

heuristic for degree constrained STPs

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
costrev	reversed edge costs
pathdist	distances from each terminal to all nodes
start	start vertex
perm	permutation array
result	array to indicate whether an edge is in the solution
cluster	array for internal computations
pathedge	ancestor edges for shortest paths from each terminal to all nodes
randseed	random seed
connected	array to indicate whether a vertex is in the solution
solfound	pointer to store whether a solution has been found

Definition at line 789 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, GRAPH::oeat, GRAPH::outbeg, SCIPheurPruneDegConsSteinerTree(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPheurComputeSteinerTree().

static SCIP_RETCODE computeSteinerTree ( SCIP *  scip, const GRAPH *  g, SCIP_Real *  cost, SCIP_Real *  costrev, SCIP_Real **  pathdist, int  start, int *  perm, int *  result, int *  cluster, int **  pathedge, char *  connected, unsigned int *  randseed  )

static

shortest paths based heuristic

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
costrev	reversed edge costs
pathdist	distance array
start	start vertex
perm	permutation array (on nodes)
result	solution array (on edges)
cluster	array used to store current vertices of each subtree during construction
pathedge	predecessor edge array
connected	array marking all solution vertices
randseed	random seed

Definition at line 648 of file heur_tm.c.

References FALSE, FARAWAY, GRAPH::grad, Is_term, GRAPH::knots, GRAPH::mark, prune(), GRAPH::source, STP_DIRECTED, STP_HOP_CONS, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by SCIPheurComputeSteinerTree().

static SCIP_RETCODE computeSteinerTreeDijk ( SCIP *  scip, const GRAPH *  g, SCIP_Real *  cost, SCIP_Real *  costrev, SCIP_Real *  dijkdist, int *  result, int *  dijkedge, int  start, unsigned int *  randseed, char *  connected  )

static

Dijkstra based shortest paths heuristic

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
costrev	reversed edge costs
dijkdist	distance array
result	solution array (on edges)
dijkedge	predecessor edge array
start	start vertex
randseed	random seed
connected	array marking all solution vertices

Definition at line 620 of file heur_tm.c.

References GRAPH::grad, graph_path_st(), GRAPH::knots, GRAPH::mark, and prune().

Referenced by SCIPheurComputeSteinerTree().

static SCIP_RETCODE computeSteinerTreeVnoi ( SCIP *  scip, const GRAPH *  g, SCIP_PQUEUE *  pqueue, GNODE **  gnodearr, SCIP_Real *  cost, SCIP_Real *  costrev, SCIP_Real **  node_dist, int  start, int *  result, int *  vcount, int *  nodenterms, int **  node_base, int **  node_edge, char  firstrun, char *  connected  )

static

Voronoi based shortest path heuristic

Parameters

scip	SCIP data structure
g	graph structure
pqueue	priority queue
gnodearr	internal array
cost	edge costs
costrev	reversed edge costs
node_dist	internal array
start	start vertex
result	array to indicate whether an edge is in the solution
vcount	internal array
nodenterms	internal array
node_base	internal array
node_edge	internal array
firstrun	method called for the first time? (during one heuristic round)
connected	array to indicate whether a vertex is in the solution

Definition at line 1046 of file heur_tm.c.

References CONNECT, Graph_Node::dist, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, heap_add(), Is_term, GRAPH::knots, GRAPH::mark, Graph_Node::number, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, prune(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, voronoi(), and voronoi_extend2().

Referenced by SCIPheurComputeSteinerTree().

static void do_prizecoll_trivial ( SCIP *  scip, const GRAPH *  graph, int *  best_result  )

static

trivial PC heuristic, selecting most expensive terminal as solution

Parameters

scip	SCIP data structure
graph	graph data structure
best_result	array to indicate whether an edge is in the solution

Definition at line 1368 of file heur_tm.c.

References CONNECT, GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::tail, GRAPH::term, and UNKNOWN.

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_RETCODE prune ( SCIP *  scip, const GRAPH *  g, SCIP_Real *  cost, SCIP_Real *  costrev, int *  result, char *  connected  )

static

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
costrev	reversed edge costs
result	ST edges
connected	ST nodes

Definition at line 497 of file heur_tm.c.

References BLOCKED, GRAPH::cost, GRAPH::edges, flipedge, SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, and GRAPH::stp_type.

Referenced by computeSteinerTree(), computeSteinerTreeDijk(), and computeSteinerTreeVnoi().

static SCIP_DECL_HEURCOPY ( heurCopyTM  )

static

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

Definition at line 2208 of file heur_tm.c.

References HEUR_NAME, and SCIPincludeHeurTM().

static SCIP_DECL_HEUREXEC ( heurExecTM  )

static

execution method of primal heuristic

Definition at line 2280 of file heur_tm.c.

References BLOCKED, CONNECT, GRAPH::cost, do_prizecoll_trivial(), GRAPH::edges, FALSE, FARAWAY, flipedge, GRAPH::grad, GRAPH::head, HEUR_NAME, SCIP_HeurData::hopfactor, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::maxdeg, SCIPheurComputeSteinerTree(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPvalidateStpSol(), GRAPH::source, STP_DEG_CONS, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

static SCIP_DECL_HEURFREE ( heurFreeTM  )

static

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

Definition at line 2222 of file heur_tm.c.

References HEUR_NAME.

static SCIP_DECL_HEURINIT ( heurInitTM  )

static

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

Definition at line 2243 of file heur_tm.c.

References HEUR_NAME, SCIPprobdataGetGraph(), GRAPH::stp_type, and STP_UNDIRECTED.

static SCIP_DECL_PARAMCHGD ( paramChgdRandomseed  )

static

information method for a parameter change of random seed

Definition at line 98 of file heur_tm.c.

References CONNECT, GRAPH::cost, GRAPH::edges, FALSE, GRAPH::head, GRAPH::knots, GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

SCIP_RETCODE SCIPheurComputeSteinerTree	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		const GRAPH *	graph,
		int *	starts,
		int *	bestnewstart,
		int *	best_result,
		int	runs,
		int	bestincstart,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		SCIP_Real *	hopfactor,
		SCIP_Real *	nodepriority,
		SCIP_Real	maxcost,
		SCIP_Bool *	success
	)

execute shortest paths heuristic to obtain a Steiner tree

Parameters

scip	SCIP data structure
heurdata	SCIP data structure
graph	graph data structure
starts	array containing start vertices (NULL to not provide any)
bestnewstart	pointer to the start vertex resulting in the best soluton
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)
maxcost	maximal edge cost (only for HC)
success	pointer to store whether a solution could be found

Definition at line 1419 of file heur_tm.c.

References AUTO, BLOCKED, computeDegConsTree(), computeSteinerTree(), computeSteinerTreeDijk(), computeSteinerTreeVnoi(), CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, FALSE, FARAWAY, flipedge, GNODECmpByDist(), GRAPH::grad, graph_path_execX(), GRAPH::head, GRAPH::hoplimit, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::mark, SCIP_HeurData::nexecs, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_DEG_CONS, STP_DIRECTED, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, SCIP_HeurData::stp_type, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TM_DIJKSTRA, TM_SP, TM_VORONOI, TRUE, and UNKNOWN.

Referenced by bound_reduce(), da_reduce(), daPc_reduce(), hcrcbound_reduce(), and SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPheurPruneDegConsSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		int *	result,
		char *	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

Definition at line 527 of file heur_tm.c.

References CONNECT, EAT_LAST, FALSE, flipedge, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeDegConsTree(), and SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPheurPrunePCSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		int *	result,
		char *	connected
	)

prune the (rooted) prize collecting Steiner tree in such a way that all leaves are terminals

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
result	ST edges
connected	ST nodes

Definition at line 197 of file heur_tm.c.

References CONNECT, EAT_LAST, shortest_path::edge, FALSE, graph_path_exec(), graph_sol_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::source, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by extendSteinerTreePcMw(), prune(), SCIP_DECL_HEUREXEC(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE SCIPheurPruneSteinerTree	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real *	cost,
		int	layer,
		int *	result,
		char *	connected
	)

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

Parameters

scip	SCIP data structure
g	graph structure
cost	edge costs
layer	layer (usually 0)
result	ST edges
connected	ST nodes

Definition at line 381 of file heur_tm.c.

References CONNECT, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, graph_path_exec(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_DIRECTED, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::term, and GRAPH::terms.

Referenced by prune(), SCIP_DECL_HEUREXEC(), and SCIPheurImproveSteinerTree().

SCIP_RETCODE SCIPincludeHeurTM

(

SCIP *

scip

)

creates the TM primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2687 of file heur_tm.c.

References DEFAULT_DURINGLPFREQ, DEFAULT_EVALRUNS, DEFAULT_HOPFACTOR, DEFAULT_INITRUNS, DEFAULT_LEAFRUNS, 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, and TRUE.

Referenced by runShell(), and SCIP_DECL_HEURCOPY().