heur_local.c File Reference

Detailed Description

Improvement heuristic for Steiner problems.

Author

Daniel Rehfeldt

This file implements three local heuristics, namely vertex insertion, key-path exchange and key-vertex elimination, see "Fast Local Search for Steiner Trees in Graphs" by Uchoa and Werneck.

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

Definition in file heur_local.c.

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

Go to the source code of this file.

Macros
#define	HEUR_NAME   "local"
#define	HEUR_DESC   "improvement heuristic for STP"
#define	HEUR_DISPCHAR   '-'
#define	HEUR_PRIORITY   100
#define	HEUR_FREQ   1
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   (SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_AFTERLPLOOP | SCIP_HEURTIMING_AFTERNODE)
#define	HEUR_USESSUBSCIP   FALSE
#define	DEFAULT_DURINGROOT   TRUE
#define	DEFAULT_MAXFREQLOC   FALSE
#define	DEFAULT_MAXNBESTSOLS   6
#define	DEFAULT_NBESTSOLS   3

Functions
static void	dfsorder (const GRAPH *graph, int *edges, int *node, int *counter, int *dfst)
static SCIP_RETCODE	lca (SCIP *scip, const GRAPH *graph, int u, UF *uf, char *nodesmark, int *steineredges, IDX **lcalists, PHNODE **boundpaths, int *heapsize, int *vbase)
static char	nodeIsCrucial (const GRAPH *graph, int *steineredges, int node)
SCIP_RETCODE	SCIPheurImproveSteinerTree (SCIP *scip, GRAPH *graph, SCIP_Real *cost, SCIP_Real *costrev, int *best_result)
SCIP_RETCODE	extendSteinerTreePcMw (SCIP *scip, const GRAPH *graph, PATH *vnoi, SCIP_Real *costrev, int *vbase, int *stedge, char *stvertex, int *adds)
static	SCIP_DECL_HEURCOPY (heurCopyLocal)
static	SCIP_DECL_HEURFREE (heurFreeLocal)
static	SCIP_DECL_HEUREXEC (heurExecLocal)
SCIP_RETCODE	SCIPincludeHeurLocal (SCIP *scip)

Macro Definition Documentation

#define DEFAULT_DURINGROOT   TRUE

Definition at line 52 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define DEFAULT_MAXFREQLOC   FALSE

Definition at line 53 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define DEFAULT_MAXNBESTSOLS   6

Definition at line 54 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define DEFAULT_NBESTSOLS   3

Definition at line 55 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_DESC   "improvement heuristic for STP"

Definition at line 42 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_DISPCHAR   '-'

Definition at line 43 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_FREQ   1

Definition at line 45 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_FREQOFS   0

Definition at line 46 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_MAXDEPTH   -1

Definition at line 47 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_NAME   "local"

Definition at line 41 of file heur_local.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEURFREE(), and SCIPincludeHeurLocal().

#define HEUR_PRIORITY   100

Definition at line 44 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

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

Definition at line 48 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 50 of file heur_local.c.

Referenced by SCIPincludeHeurLocal().

Function Documentation

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

static

recursive methode for a DFS ordering of graph 'g'

Definition at line 79 of file heur_local.c.

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

Referenced by SCIPheurImproveSteinerTree().

SCIP_RETCODE extendSteinerTreePcMw	(	SCIP *	scip,
		const GRAPH *	graph,
		PATH *	vnoi,
		SCIP_Real *	costrev,
		int *	vbase,
		int *	stedge,
		char *	stvertex,
		int *	adds
	)

local heuristic for (R)PC and MW

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure array
costrev	reversed edge costs
vbase	array to store Voronoi bases to each vertex
stedge	array to indicate whether an edge is part of the Steiner tree
stvertex	uninitialized array to indicate whether an edge is part of the Steiner tree
adds	pointer to store number of added vertices

Definition at line 1941 of file heur_local.c.

References CONNECT, GRAPH::cost, EAT_LAST, shortest_path::edge, GRAPH::edges, FALSE, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPheurPrunePCSteinerTree(), GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, and voronoiSteinerTreeExt().

Referenced by da_reduce(), daPc_reduce(), and SCIPheurImproveSteinerTree().

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

static

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

Definition at line 106 of file heur_local.c.

References EAT_LAST, FALSE, GRAPH::head, Int_List_Node::index, GRAPH::oeat, GRAPH::outbeg, UnionFind_Structure::parent, Int_List_Node::parent, SCIPpairheapBuffarr(), SCIPunionfindFind(), SCIPunionfindUnion(), and TRUE.

Referenced by SCIPheurImproveSteinerTree().

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

static

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

Definition at line 168 of file heur_local.c.

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

Referenced by SCIPheurImproveSteinerTree().

static SCIP_DECL_HEURCOPY ( heurCopyLocal  )

static

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

Definition at line 2074 of file heur_local.c.

References HEUR_NAME, and SCIPincludeHeurLocal().

static SCIP_DECL_HEUREXEC ( heurExecLocal  )

static

execution method of primal heuristic

Definition at line 2108 of file heur_local.c.

References BLOCKED, CONNECT, GRAPH::cost, EAT_LAST, GRAPH::edges, GSTP, GRAPH::head, HEUR_NAME, Is_term, GRAPH::knots, SCIP_HeurData::lastsolindices, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::oeat, GRAPH::orgedges, GRAPH::orgknots, GRAPH::outbeg, SCIPheurImproveSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataAddNewSol(), SCIPprobdataGetGraph(), SCIPprobdataGetNVars(), SCIPprobdataGetOffset(), SCIPprobdataGetVars(), SCIPprobdataGetXval(), SCIPvalidateStpSol(), GRAPH::source, STP_GRID, STP_MAX_NODE_WEIGHT, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

static SCIP_DECL_HEURFREE ( heurFreeLocal  )

static

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

Definition at line 2088 of file heur_local.c.

References HEUR_NAME.

SCIP_RETCODE SCIPheurImproveSteinerTree	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real *	cost,
		SCIP_Real *	costrev,
		int *	best_result
	)

perform local heuristics on a given Steiner tree

Key-Path Exchange

Parameters

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

Definition at line 282 of file heur_local.c.

References CONNECT, GRAPH::cost, dfsorder(), shortest_path::dist, EAT_LAST, ST_Node::edge, shortest_path::edge, GRAPH::edges, extendSteinerTreePcMw(), FALSE, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GSTP, GRAPH::head, heap_add(), GRAPH::ieat, Int_List_Node::index, GRAPH::inpbeg, insert(), Is_pterm, Is_term, GRAPH::knots, lca(), GRAPH::mark, MST_MODE, nodeIsCrucial(), GRAPH::oeat, GRAPH::outbeg, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPlinkcuttreeCut(), SCIPlinkcuttreeEvert(), SCIPlinkcuttreeFindMax(), SCIPlinkcuttreeFindMinMW(), SCIPlinkcuttreeInit(), SCIPlinkcuttreeLink(), SCIPpairheapDeletemin(), SCIPpairheapFree(), SCIPpairheapInsert(), SCIPpairheapMeldheaps(), SCIPprobdataPrintGraph2(), SCIPunionfindFind(), SCIPunionfindFree(), SCIPunionfindInit(), SCIPunionfindUnion(), GRAPH::source, STP_GRID, STP_MAX_NODE_WEIGHT, STP_OBSTACLES_GRID, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, STP_UNDIRECTED, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, voronoi(), voronoi_repair(), and voronoi_repair_mult().

Referenced by SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPincludeHeurLocal

(

SCIP *

scip

)

creates the local primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2421 of file heur_local.c.

References DEFAULT_DURINGROOT, DEFAULT_MAXFREQLOC, DEFAULT_MAXNBESTSOLS, DEFAULT_NBESTSOLS, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, and HEUR_USESSUBSCIP.

Referenced by runShell(), and SCIP_DECL_HEURCOPY().