dpborder.h File Reference

Detailed Description

Dynamic programming solver for Steiner tree (sub-) problems with small border.

Author

Daniel Rehfeldt

This file implements a dynamic programming method from Polzin and Vahdati to solve Steiner tree problems to optimality. See also "Practical Partitioning-Based Methods for the Steiner Problem", WEA 2006

Definition in file dpborder.h.

#include "scip/scip.h"
#include "graph.h"

Go to the source code of this file.

Typedefs
typedef struct dynamic_programming_border	DPBORDER

Functions
SCIP_RETCODE	dpborder_init (SCIP *, const GRAPH *, DPBORDER **)
SCIP_RETCODE	dpborder_probePotential (SCIP *, GRAPH *, DPBORDER *, SCIP_Bool *)
SCIP_RETCODE	dpborder_solve (SCIP *, GRAPH *, DPBORDER *, int *, SCIP_Bool *)
void	dpborder_free (SCIP *, DPBORDER **)

Typedef Documentation

DPBORDER

typedef struct dynamic_programming_border DPBORDER

Definition at line 40 of file dpborder.h.

Function Documentation

dpborder_init()

SCIP_RETCODE dpborder_init	(	SCIP *	scip,
		const GRAPH *	graph,
		DPBORDER **	dpborder
	)

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpborder	to initialize

Definition at line 278 of file dpborder_base.c.

References dynamic_programming_border::borderchardists, dynamic_programming_border::bordercharmap, dynamic_programming_border::dpbsequence, hashmap_s::elements, FARAWAY, dynamic_programming_border::global_npartitions, dynamic_programming_border::global_obj, dynamic_programming_border::global_optposition, dynamic_programming_border::global_partcap, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, GRAPH::knots, dynamic_programming_border::nnodes, dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, dynamic_programming_border::nterms, dynamic_programming_border::ntermsvisited, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and GRAPH::terms.

Referenced by SCIPStpDpRelaxIsPromising().

dpborder_probePotential()

SCIP_RETCODE dpborder_probePotential	(	SCIP *	scip,
		GRAPH *	graph,
		DPBORDER *	dpborder,
		SCIP_Bool *	hasPotential
	)

checks whether DP border has potential NOTE: needs to be called before dpborder_solve!

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpborder	border
hasPotential	was problem solved to optimality?

Definition at line 186 of file dpborder_base.c.

References BPBORDER_MAXBORDERSIZE, BPBORDER_MAXNPARTITIONS, dpborder_coreComputeOrderingSimple(), dpborderInitHelper(), dpborderIsNonPromising(), dynamic_programming_border::dpbsequence, FALSE, graph_free_csr(), graph_init_csrWithEdgeId(), dynamic_programming_border_nodes_sequence::maxbordersize, dynamic_programming_border_nodes_sequence::maxnpartitions, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by SCIPStpDpRelaxIsPromising().

dpborder_solve()

SCIP_RETCODE dpborder_solve	(	SCIP *	scip,
		GRAPH *	graph,
		DPBORDER *	dpborder,
		int *	solution,
		SCIP_Bool *	wasSolved
	)

solves problem given by graph

Parameters

scip	SCIP data structure
graph	graph of sub-problem
dpborder	border
solution	optimal solution (out)
wasSolved	was problem solved to optimality?

Definition at line 230 of file dpborder_base.c.

References dpborder_coreSolve(), dpborder_coreUpdateOrdering(), DPBORDER_GROWTH_FACTOR, dpborder_markSolNodes(), dynamic_programming_border::dpbsequence, EQ, dynamic_programming_border::global_obj, graph_free_csr(), graph_init_csr(), dynamic_programming_border::hashmap, hashmap_create(), GRAPH::knots, dynamic_programming_border_nodes_sequence::maxnpartitions, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_getObj(), solstp_isValid(), and solstp_pruneFromNodes().

Referenced by solveWithDpBorder().

dpborder_free()

void dpborder_free	(	SCIP *	scip,
		DPBORDER **	dpborder
	)

frees

Parameters

scip	SCIP data structure
dpborder	to be freed

Definition at line 317 of file dpborder_base.c.

References dynamic_programming_border::borderchardists, dynamic_programming_border::bordercharmap, dpborder_dpblevelFree(), dpborder_dpbsequenceFree(), dynamic_programming_border::dpbsequence, hashmap_s::elements, dynamic_programming_border::global_partitions, dynamic_programming_border::hashmap, hashmap_destroy(), dynamic_programming_border::nodes_isBorder, dynamic_programming_border::nodes_outdeg, SCIPfreeMemory, SCIPfreeMemoryArrayNull, StpVecFree, and StpVecGetSize.

Referenced by SCIP_DECL_RELAXFREE().