Detailed Description

Core of dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.

Author: Daniel Rehfeldt

Contains core methods.

#include "scip/scipdefplugins.h"
#include "scip/rbtree.h"
#include "dpterms.h"
#include "dptermsinterns.h"
#include "stpbitset.h"
#include "stpvector.h"
#include "stpprioqueue.h"

Go to the source code of this file.

Data Structures
struct	trace_triplet

struct	dynamic_programming_iterator

Typedefs
typedef struct trace_triplet	TTRIPLET

typedef struct dynamic_programming_iterator	DPITER

Functions
static void	debugPrintSeparator (SCIP_Real maxvaliddist, const DPITER *dpiterator)

static	STP_Vectype (int)

static SCIP_Bool	nodeIsNonSolTerm (STP_Bitset sol_bitset, const int *nodes_termId, int node)

static SCIP_Bool	allExtensionsAreInvalid (const GRAPH graph, const DPSOLVER dpsolver, const DPITER *dpiterator)

static SCIP_RETCODE	getOrderedRootIndices (SCIP scip, DPITER dpiterator, int *roots_indices)

static SCIP_RETCODE	dpiterInit (SCIP scip, const GRAPH graph, DPITER **dpiterator)

static void	dpiterFree (SCIP scip, DPITER *dpiterator)

static void	dpiterSetDefault (SCIP scip, DPITER dpiterator)

static void	dpiterPopSol (SCIP scip, DPSOLVER dpsolver, DPITER *dpiterator)

static void	dpiterGetNextSol (SCIP scip, DPSOLVER dpsolver, DPITER *dpiterator)

static SCIP_RETCODE	subtreesBuild (SCIP scip, DPMISC dpmisc, DPITER *dpiterator)

static SCIP_RETCODE	subtreesExtend (SCIP scip, const GRAPH graph, DPSOLVER dpsolver, DPITER dpiterator)

static SCIP_RETCODE	dpiterAddNewPrepare (SCIP scip, DPMISC dpmisc, DPITER dpiterator, SCIP_Bool hasExtension)

static	STP_Vectype (SOLTRACE)

static void	subsolUpdate (SCIP scip, STP_Vectype(SOLTRACE) combined_traces, DPITER dpiterator, DPSUBSOL *dpsubsol)

static SCIP_RETCODE	combineWithIntersecting (SCIP scip, const GRAPH graph, int index, DPSOLVER dpsolver, DPITER dpiterator)

static void	updateIncumbent (SCIP scip, DPSOLVER dpsolver, DPITER *dpiterator)

static SCIP_RETCODE	subtreesAddNewFinalize (SCIP scip, const GRAPH graph, DPSOLVER dpsolver, DPITER dpiterator)

static SCIP_RETCODE	subtreesAddNew (SCIP scip, const GRAPH graph, DPSOLVER dpsolver, DPITER dpiterator)

static void	propagateUBs (const GRAPH graph, DPSOLVER dpsolver, DPITER *dpiterator)

static SCIP_RETCODE	subtreesRemoveNonValids (SCIP scip, const GRAPH graph, DPSOLVER dpsolver, DPITER dpiterator)

static void	dpiterFinalizeSol (SCIP scip, DPITER dpiterator)

SCIP_RETCODE	dpterms_coreSolve (SCIP scip, GRAPH graph, DPSOLVER dpsolver, SCIP_Bool wasSolved)

Typedef Documentation

◆ TTRIPLET

typedef struct trace_triplet TTRIPLET

helper data

◆ DPITER

typedef struct dynamic_programming_iterator DPITER

saves some data updated in every iteration

Function Documentation

◆ debugPrintSeparator()

static void debugPrintSeparator	(	SCIP_Real	maxvaliddist,
		const DPITER *	dpiterator
	)

static

prints separator nodes in SCIP_DEBUG mode

Parameters

maxvaliddist	maximum value distance
dpiterator	iterator

Definition at line 79 of file dpterms_core.c.

References GT, LE, nnodes, SCIP_Real, and SCIPdebugMessage.

Referenced by subtreesRemoveNonValids().

◆ STP_Vectype() [1/2]

static STP_Vectype ( int )

static

assembles final solution nodes iterator

Definition at line 115 of file dpterms_core.c.

References NULL, dynamic_programming_misc::opt_prev, dynamic_programming_misc::opt_root, SCIPdebugMessage, StpVecClear, StpVecGetSize, StpVecPopBack, and StpVecPushBack.

Referenced by combineWithIntersecting(), dpiterAddNewPrepare(), getOrderedRootIndices(), STP_Vectype(), subsolUpdate(), subtreesAddNew(), subtreesBuild(), subtreesRemoveNonValids(), and updateIncumbent().

◆ nodeIsNonSolTerm()

static SCIP_Bool nodeIsNonSolTerm	(	STP_Bitset	sol_bitset,
		const int *	nodes_termId,
		int	node
	)

inlinestatic

helper

Parameters

sol_bitset	bitset
nodes_termId	ID
node	node to check

Definition at line 170 of file dpterms_core.c.

References stpbitset_bitIsTrue().

Referenced by subtreesExtend(), and subtreesRemoveNonValids().

◆ allExtensionsAreInvalid()

static SCIP_Bool allExtensionsAreInvalid	(	const GRAPH *	graph,
		const DPSOLVER *	dpsolver,
		const DPITER *	dpiterator
	)

static

helper

Parameters

graph	graph
dpsolver	solver
dpiterator	iterator

Definition at line 182 of file dpterms_core.c.

References dynamic_programming_solver::dpgraph, FALSE, GT, nterms, SCIP_Real, SCIPdebugMessage, STP_Bitset, stpbitset_bitIsTrue(), dynamic_programming_graph::terminals, GRAPH::terms, and TRUE.

Referenced by subtreesRemoveNonValids().

◆ getOrderedRootIndices()

static SCIP_RETCODE getOrderedRootIndices	(	SCIP *	scip,
		DPITER *	dpiterator,
		int *	roots_indices
	)

static

gets ordered root indices according to the solution costs

Parameters

scip	SCIP data structure
dpiterator	iterator
roots_indices	to initialize

Definition at line 209 of file dpterms_core.c.

References LE, nnodes, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), STP_Vectype(), and StpVecGetSize.

Referenced by subtreesBuild().

◆ dpiterInit()

static SCIP_RETCODE dpiterInit	(	SCIP *	scip,
		const GRAPH *	graph,
		DPITER **	dpiterator
	)

static

initializes

Parameters

scip	SCIP data structure
graph	original graph
dpiterator	to initialize

Definition at line 247 of file dpterms_core.c.

References graph_get_nNodes(), nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and StpVecReserve.

Referenced by dpterms_coreSolve().

◆ dpiterFree()

static void dpiterFree	(	SCIP *	scip,
		DPITER **	dpiterator
	)

static

frees

Parameters

scip	SCIP data structure
dpiterator	to free

Definition at line 288 of file dpterms_core.c.

References SCIPfreeMemory, SCIPfreeMemoryArray, and StpVecFree.

Referenced by dpterms_coreSolve().

◆ dpiterSetDefault()

static void dpiterSetDefault	(	SCIP *	scip,
		DPITER *	dpiterator
	)

static

sets arrays to default values

Parameters

scip	SCIP data structure
dpiterator	to update

Definition at line 315 of file dpterms_core.c.

References BMSclearMemoryArray, FARAWAY, nnodes, SCIP_Bool, and SCIP_Real.

Referenced by dpiterGetNextSol().

◆ dpiterPopSol()

static void dpiterPopSol	(	SCIP *	scip,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

gets solution from tree

Parameters

scip	SCIP data structure
dpsolver	solver
dpiterator	to update

Definition at line 355 of file dpterms_core.c.

References dynamic_programming_subsolution::bitkey, dynamic_programming_iterator::dpsubsol, SCIPdebugMessage, SCIPrbtreeDelete, dynamic_programming_solver::solpqueue, dynamic_programming_solver::soltree_root, stpbitset_areEqual(), stpbitset_free(), stpbitset_getPopcount(), stpprioqueue_deleteMin(), StpVecGetSize, and subsol.

Referenced by dpiterGetNextSol().

◆ dpiterGetNextSol()

static void dpiterGetNextSol	(	SCIP *	scip,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

updates

Parameters

scip	SCIP data structure
dpsolver	solver
dpiterator	to update

Definition at line 387 of file dpterms_core.c.

References dynamic_programming_solver::dpgraph, dpiterPopSol(), dpiterSetDefault(), dynamic_programming_graph::nterms, SCIPdebugMessage, stpbitset_bitIsTrue(), stpbitset_print(), and dynamic_programming_graph::terminals.

Referenced by dpterms_coreSolve().

◆ subtreesBuild()

static SCIP_RETCODE subtreesBuild	(	SCIP *	scip,
		DPMISC *	dpmisc,
		DPITER *	dpiterator
	)

static

(Implicitly) constructs sub-Steiner trees

Parameters

scip	SCIP data structure
dpmisc	misc
dpiterator	to update

Definition at line 415 of file dpterms_core.c.

References trace_triplet::bdist_global, trace_triplet::bdist_local, solution_trace::cost, GE, getOrderedRootIndices(), GT, trace_triplet::index, LT, MAX, nnodes, solution_trace::prevs, solution_trace::root, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_Vectype(), StpVecGetSize, StpVecPopBack, StpVecPushBack, and TRUE.

Referenced by dpterms_coreSolve().

◆ subtreesExtend()

static SCIP_RETCODE subtreesExtend	(	SCIP *	scip,
		const GRAPH *	graph,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

extends sub-Steiner trees

Parameters

scip	SCIP data structure
graph	graph
dpsolver	solver
dpiterator	iterator

Definition at line 542 of file dpterms_core.c.

References csr_storage::cost, GRAPH::csr_storage, dynamic_programming_solver::dheap, dynamic_programming_solver::dpgraph, EQ, FALSE, FARAWAY, GRAPH::grad, graph_heap_clean(), graph_heap_correct(), graph_heap_deleteMin(), csr_storage::head, GRAPH::knots, LT, nnodes, nodeIsNonSolTerm(), dynamic_programming_graph::nodes_termId, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocClearBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, dijkstra_heap::size, csr_storage::start, STP_Bitset, GRAPH::terms, and TRUE.

Referenced by dpterms_coreSolve().

◆ dpiterAddNewPrepare()

static SCIP_RETCODE dpiterAddNewPrepare	(	SCIP *	scip,
		DPMISC *	dpmisc,
		DPITER *	dpiterator,
		SCIP_Bool *	hasExtension
	)

static

helper

Parameters

scip	SCIP data structure
dpmisc	DP misc data structure
dpiterator	iterator
hasExtension	extensions existing?

Definition at line 659 of file dpterms_core.c.

References FALSE, FARAWAY, GE, dynamic_programming_misc::global_size, LT, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBuffer, STP_Bitset, STP_Vectype(), stpbitset_free(), stpbitset_new(), stpbitset_setBitTrue(), StpVecClear, StpVecGetSize, StpVecPushBack, and TRUE.

Referenced by subtreesAddNew().

◆ STP_Vectype() [2/2]

static STP_Vectype ( SOLTRACE )

static

helper

Definition at line 741 of file dpterms_core.c.

References solution_trace::cost, NULL, solution_trace::root, STP_Vectype(), StpVecGetSize, and StpVecPushBack.

◆ subsolUpdate()

static void subsolUpdate	(	SCIP *	scip,
		STP_Vectype(SOLTRACE)	combined_traces,
		DPITER *	dpiterator,
		DPSUBSOL *	dpsubsol
	)

static

updates existing subsol

Parameters

scip	SCIP data structure
combined_traces	for updating
dpiterator	iterator
dpsubsol	to be updated

Definition at line 805 of file dpterms_core.c.

References LE, nnodes, NULL, STP_Vectype(), StpVecFree, StpVecGetSize, and StpVecPushBack.

Referenced by combineWithIntersecting().

◆ combineWithIntersecting()

static SCIP_RETCODE combineWithIntersecting	(	SCIP *	scip,
		const GRAPH *	graph,
		int	index,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

combines new sub-Steiner trees

Parameters

scip	SCIP data structure
graph	graph
index	index of intersecting
dpsolver	solver
dpiterator	iterator

Definition at line 856 of file dpterms_core.c.

References dynamic_programming_subsolution::bitkey, dynamic_programming_solver::dpmisc, dynamic_programming_misc::global_size, trace_triplet::index, SCIP_CALL, SCIP_OKAY, SCIPrbtreeInsert, dynamic_programming_solver::solpqueue, dynamic_programming_solver::soltree_root, STP_Bitset, STP_Vectype(), stpbitset_free(), stpbitset_getPopcount(), stpbitset_newCopy(), stpbitset_newOr(), stpprioqueue_insert(), StpVecFree, subsol, and subsolUpdate().

Referenced by subtreesAddNew().

◆ updateIncumbent()

static void updateIncumbent	(	SCIP *	scip,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

updates best (global) solution

Parameters

scip	SCIP data structure
dpsolver	solver
dpiterator	iterator

Definition at line 909 of file dpterms_core.c.

References dynamic_programming_solver::dpgraph, dynamic_programming_solver::dpmisc, dynamic_programming_misc::global_size, LT, dynamic_programming_graph::nterms, dynamic_programming_misc::opt_obj, dynamic_programming_misc::opt_prev, dynamic_programming_misc::opt_root, SCIP_Real, SCIPdebugMessage, dynamic_programming_solver::soltree_root, STP_Bitset, STP_Vectype(), stpbitset_free(), stpbitset_newNot(), stpbitset_print(), and StpVecGetSize.

Referenced by subtreesAddNew().

◆ subtreesAddNewFinalize()

static SCIP_RETCODE subtreesAddNewFinalize	(	SCIP *	scip,
		const GRAPH *	graph,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

finalizes

Parameters

scip	SCIP data structure
graph	graph
dpsolver	solver
dpiterator	iterator

Definition at line 972 of file dpterms_core.c.

References dynamic_programming_solver::dpmisc, dynamic_programming_solver::dpstree, dpterms_streeInsert(), dynamic_programming_misc::global_size, NULL, SCIP_CALL, SCIP_OKAY, stpbitset_free(), stpbitset_newCopy(), StpVecGetSize, StpVecPushBack, and GRAPH::terms.

Referenced by subtreesAddNew().

◆ subtreesAddNew()

static SCIP_RETCODE subtreesAddNew	(	SCIP *	scip,
		const GRAPH *	graph,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

adds new sub-Steiner trees

Parameters

scip	SCIP data structure
graph	graph
dpsolver	solver
dpiterator	iterator

Definition at line 1015 of file dpterms_core.c.

References combineWithIntersecting(), dpiterAddNewPrepare(), dynamic_programming_solver::dpmisc, dynamic_programming_solver::dpstree, nterms, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_Vectype(), stpbitset_getPopcount(), stpbitset_print(), StpVecFree, StpVecGetSize, subtreesAddNewFinalize(), GRAPH::terms, and updateIncumbent().

Referenced by dpterms_coreSolve().

◆ propagateUBs()

static void propagateUBs	(	const GRAPH *	graph,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

remove non-valid sub-Steiner trees

Parameters

graph	graph
dpsolver	solver
dpiterator	iterator

Definition at line 1064 of file dpterms_core.c.

References csr_storage::cost, GRAPH::csr_storage, dynamic_programming_solver::dheap, EQ, graph_heap_clean(), graph_heap_correct(), graph_heap_deleteMin(), GT, csr_storage::head, GRAPH::knots, nnodes, SCIP_Real, dijkstra_heap::size, csr_storage::start, and TRUE.

Referenced by dpterms_coreSolve().

◆ subtreesRemoveNonValids()

static SCIP_RETCODE subtreesRemoveNonValids	(	SCIP *	scip,
		const GRAPH *	graph,
		DPSOLVER *	dpsolver,
		DPITER *	dpiterator
	)

static

remove non-valid sub-Steiner trees

Parameters

scip	SCIP data structure
graph	graph
dpsolver	solver
dpiterator	iterator

Definition at line 1120 of file dpterms_core.c.

References allExtensionsAreInvalid(), BMSclearMemoryArray, GRAPH::csr_storage, debugPrintSeparator(), dynamic_programming_solver::dheap, dynamic_programming_solver::dpgraph, EQ, FALSE, GE, graph_heap_clean(), graph_heap_correct(), graph_heap_deleteMin(), graph_knot_isInRange(), GT, csr_storage::head, GRAPH::knots, LE, nnodes, nodeIsNonSolTerm(), dynamic_programming_graph::nodes_termId, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, dijkstra_heap::size, csr_storage::start, STP_Bitset, STP_Vectype(), StpVecClear, StpVecGetSize, StpVecPopBack, StpVecPushBack, GRAPH::terms, and TRUE.

Referenced by dpterms_coreSolve().

◆ dpiterFinalizeSol()

static void dpiterFinalizeSol	(	SCIP *	scip,
		DPITER *	dpiterator
	)

static

frees etc.

Parameters

scip	SCIP data structure
dpiterator	to update

Definition at line 1265 of file dpterms_core.c.

References dynamic_programming_iterator::dpsubsol, dpterms_dpsubsolFree(), NULL, and stpbitset_free().

Referenced by dpterms_coreSolve().

◆ dpterms_coreSolve()

SCIP_RETCODE dpterms_coreSolve	(	SCIP *	scip,
		GRAPH *	graph,
		DPSOLVER *	dpsolver,
		SCIP_Bool *	wasSolved
	)

solves problem

Parameters

scip	SCIP data structure
graph	graph
dpsolver	solver
wasSolved	was problem solved to optimality?

Definition at line 1288 of file dpterms_core.c.

References dynamic_programming_solver::dpgraph, dpiterFinalizeSol(), dpiterFree(), dpiterGetNextSol(), dpiterInit(), dynamic_programming_solver::dpmisc, dynamic_programming_solver::dpstree, FALSE, dynamic_programming_misc::global_size, dynamic_programming_misc::opt_obj, propagateUBs(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisStopped(), dynamic_programming_solver::solpqueue, dynamic_programming_solver::soltree_root, stpprioqueue_isClean(), subtreesAddNew(), subtreesBuild(), subtreesExtend(), subtreesRemoveNonValids(), GRAPH::terms, and TRUE.

Referenced by dpsolverSolve().

SCIP

Detailed Description

Data Structures

Typedefs

Functions

Typedef Documentation

◆ TTRIPLET

◆ DPITER

Function Documentation

◆ debugPrintSeparator()

◆ STP_Vectype() [1/2]

◆ nodeIsNonSolTerm()

◆ allExtensionsAreInvalid()

◆ getOrderedRootIndices()

◆ dpiterInit()

◆ dpiterFree()

◆ dpiterSetDefault()

◆ dpiterPopSol()

◆ dpiterGetNextSol()

◆ subtreesBuild()

◆ subtreesExtend()

◆ dpiterAddNewPrepare()

◆ STP_Vectype() [2/2]

◆ subsolUpdate()

◆ combineWithIntersecting()

◆ updateIncumbent()

◆ subtreesAddNewFinalize()

◆ subtreesAddNew()

◆ propagateUBs()

◆ subtreesRemoveNonValids()

◆ dpiterFinalizeSol()

◆ dpterms_coreSolve()